Множества и функции — Функции

• Функции в виде множеств
• Почему функции — не множества
• Как это работает на практике
• Выводы

Обычно функции соответствуют некому абстрактному правилу. Оно необязательно должно быть выразимым или даже таким, которое вы можете себе представить.

Но бывают случаи, когда правила не такие абстрактные. Как и любой другой математический объект, функцию можно представить в виде набора упорядоченных пар — то есть множества. В этом уроке мы подробнее разберем понятие функции как множества и узнаем, как функции работают в этом случае.

Функции в виде множеств

Когда мы говорим о функции, мы имеем в виду два свойства:

• Каждому входу соответствует некоторый выход
• Каждый вход соответствует только одному выходу

Чтобы лучше понять свойства функции в виде множества, рассмотрим такое определение:

• Пусть X и Y — множества
• Функция F с областью X и кодоменом Y — это подмножество X * Y такое, что для каждого x ∈ X существует ровно один y ∈ Y вместе с (x, y) ∈ F
• F также называется функцией от X к Y
• Функция F от X к Y часто обозначается F : X → Y

Обратите внимание, что функция f:X→Y может быть смоделирована множеством. Объясним подробнее, что это значит.

Сам термин «функция» — это сокращение от «функциональное отношение». Ее можно рассматривать как частный случай отношения, то есть подмножества R ⊆ X × Y.

По сути, это просто перевыражение f(x)=y как (x, y) ∈ R. Таким образом, обычная картина «функция — это правило» эквивалентна представлению о подмножестве f ⊆ X × Y. В таком случае множество f обладает особыми свойствами, которые делают его функцией.

При этом отношения необязательно должны быть на одном и том же множестве. Однако когда математики говорят «отношение на E», они имеют в виду просто сокращение от «отношение от E к E».

Почему функции — не множества

Теперь мы примерно понимаем, как представлять или моделировать функции с помощью множеств. И это правильный способ. Но нужно четко понимать, что функции — это не множества. Вот три причины:

Причина 1, самая главная. Отождествлять функцию с множеством нельзя, потому что это было бы путаницей типов. Функция отображает некоторый объект в объект. Другими словами, функции не насыщены — то есть имеют один или несколько слотов, ожидающих заполнения. Например, может быть заполнение единственного слота в унарной числовой функции.

В современной терминологии функции имеют присущую им четкость. В отличие от них, множества не являются ненасыщенными, не имеют слотов для заполнения, не имеют четкости, не занимаются отображением. Поэтому функции — это не множества.

Причина 2. Можно было бы посчитать, что двоичная функция f(x)=y соответствует некоторому множеству упорядоченных пар (x,y), а затем обработать упорядоченные пары. Но есть проблема — на обоих этапах придется выбирать из двух возможностей:

• Использовать множество упорядоченных пар (y, x)
• Выбрать другое теоретико-множественное представление упорядоченных пар

Обычная ассоциация функции с множеством предполагает произвольный выбор, поэтому не существует единственного правильного способа сделать это. Ни один способ не может полностью раскрыть, чем на самом деле является функция. Мы занимаемся представлением — то есть действуем относительно некоторой выбранной схемы представления.

Причина 3. Некоторые функции слишком велики, чтобы иметь соответствующие множества. Возьмем функцию, которая отображает множество на его синглтон. Упорядоченных пар (x,{x}) слишком много, чтобы образовать множество. Если функция слишком велика, чтобы иметь соответствующее множество, она не может быть этим множеством.

Рассмотрим тот же вопрос, но с другого конца. Функцию можно рассматривать как правило присвоения уникального значения f(x) каждому x. Построим множество F всех упорядоченных пар (x,f(x)):

Если f:X → Y, то нужно, чтобы каждый x ∈ X имел значение f(x).

Поэтому для каждого x существует упорядоченная пара (x,y) в этом множестве для некоторого y ∈ Y.

Нам также нужно, чтобы f(x) была однозначно определена по x. Это важно, чтобы всякий раз, когда множество содержит (x,y) и (x,z), мы имели y=z.

Таким образом, для каждого x существует единственное f(x), как мы и требуем. +

Упорядоченные пары можно рассматривать как элементы X*Y, так что F ⊆ X × Y. Если у нас есть набор упорядоченных пар с требуемыми свойствами, мы можем работать в обратном направлении и увидеть, что это возвращает нашу первоначальную идею функции.

С этого момента мы не будем определять область и кодомен функции как множества. Будем считать, что обозначение F : X → Y уже подразумевает это.

Как это работает на практике

Теперь посмотрим, как выглядят функции в виде множества. Для начала возьмем простой пример — факториальную функцию Fact. Она представляется в виде множества и записывается так:

{(0, 1), (1, 1), (2, 2), (3, 6), (4, 24), (5, 120). (n, n!)...}

Рассмотрим более сложный пример функции с множеством.

Предположим, что класс состоит из трех учеников. Вася сидит на втором стуле в первом ряду, Глеб сидит на шестом стуле в четвертом ряду, а Настя сидит на 37 стуле в 53 ряду. Для этого класса функция SeatOf представляет собой множество:

{(Vasya, Row1Seat2), (Gleb, Row4Seat6), (Nastya, Row53Seat37)}

Теперь обозначим дни недели:

Пусть DayOfWeek = {monday, tuesday, wednesday, thursday, friday, saturday, sunday}

В таком случае существует функция:

Бинарное отношение, которое определяется этой функцией, состоит из следующих упорядоченных пар:

{(monday, tuesday), (tuesday, wednesday), (wednesday, thursday), (thursday, friday), (friday, saturday), (saturday, sunday), (sunday, monday)}

Отношение — это подмножество декартова произведения, которое содержит только некоторые элементы из упорядоченной пары на основе отношений, определенных между первым и вторым элементами. Отношение обычно обозначается R.

Если каждый элемент множества A связан с одним и только одним элементом другого множества, то такое отношение квалифицируется как функция. Функция — это особый случай отношения, когда никакие две упорядоченные пары не могут иметь один и тот же первый элемент.

Функция присваивает каждому элементу множества ровно один элемент из родственного множества. Функции находят свое применение в различных областях, таких как представление вычислительной сложности алгоритмов, подсчет объектов, изучение последовательностей и строк, и так далее.

В зависимости от вида отношений, которые элементы двух множеств имеют друг с другом, существует в основном четыре типа функций:

• «Один к одному» (инъективная): Для каждого элемента в области существует один и только один элемент в диапазоне
• «Многие к одному»: Два или более элементов из домена отображаются на одни и те же элементы в диапазоне
• Онто-функция (суръективная): Каждый элемент диапазона отображен на элемент в домене
• «Один-к-одному» и онто (биективная): Функция, которая является функцией «один-к-одному» и онто-функцией одновременно.

Далее в курсе мы рассмотрим каждую функцию подробнее.

Выводы

В этом уроке мы познакомились с функциями как множествами. Как и любой другой математический объект, функцию можно представить в виде набора упорядоченных пар — то есть множества. Также мы узнали четыре вида типа таких функций: «Один к одному», «Многие к одному», Онто-функция и Биективная функция.

---

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты