Множества, функции, алгоритмы

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

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

Если х — элемент множества X, то говорят, что х принадлежит X, и записывают х е X. В противном случае записывают хе X или хё X. Два множества Хи Y равны (или не равны), записывается X = Y (X Ф У), если каждый элемент множества X содержится в Y и наоборот (найдется элемент одного множества, не являющийся элементом другого множества).

Семейство М с повторяющимися элементами называют мультимножеством. Если элемент х встречается k_x раз, к_х е N., то k_x называют кратностью элемента х в М.

Множество, состоящее из конечного (бесконечного) числа элементов, называют конечным (бесконечным). Если множество X состоит из п элементов х_и …, х_пу то записывают X = {x_v х_п}, порядок следования элементов несущественен. Число п элементов конечного множества X называют мощностью или порядком множества и обозначают через |х|. Множество мощности п часто называют п-множеством.

Если элементы бесконечного множества X можно занумеровать (т.е. между множеством X и натуральным рядом существует взаимно однозначное соответствие), то множество X называется счётным. Остальные бесконечные множества называются несчётными.

Пример 1.1.

• а) {1,2,…, п} и {2, 4,…, 2п) являются «-множествами;
• б) множество рациональных чисел является счетным;
• в) множество действительных чисел является несчетным. [>

Конечные и некоторые счетные множества можно задать перечислением (последовательной записью) элементов, формульный, описательный и рекурсивный способы удобно применять для задания бесконечных множеств. Например, множество М четных натуральных чисел задается формулой М = 2N; описывается М = {2i: i е N} или М = {i е N: 2 | i} задастся рекурсивным способом, М = {i е N: 2 6 М, и если i е М, то i + 2 е М).

Обозначения стандартных множеств даны в списке основных обозначений.

Если каждый элемент множествах' является элементом множествах, то X' называется подмножеством множества X, обозначается X' с X Говорят, что множество X содержит (включает) множество X' или X' содержится (включается) в X В соответствии с определением |Х'| < |х| для конечных множеств X' и X. Если при этом X' Ф X, то |Х'| < |х| и X' называется собственным подмножеством множества X, обозначается X' с X. Множество, не содержащее элементов, называется пустым и обозначается 0. Считается, что 0 является подмножеством любого множества и 101 =0.

Однозначное отображение / (далее — отображение) множества X в множество У или функция / (обозначается /: X —" У) для каждого элемента ig X определяет единственный элемент г/ е У, записывается f (x) = у. Для функции /множествахи Yназываются областями определения и значений соответственно. Относительно функции/элемент г/ называется образом элемента х, а элемент х — прообразом элемента у. Полным прообразом элемента у е Y относительно / называют множество всех прообразов элемента у (обозначается/-^(г/)).

Функции |/: X —> К равны, если совпадают их области определения, области значений и f{x) = |/(х) для любого х е X. Если X, Y — конечные множества, то функцию /: X —> У можно задать таблицей, иод которой понимается множество пар {(.х, f (x)) х е X}, упорядоченных некоторым образом. Пару (x, f (x)) назовем элементом таблицы функции /.

Пусть X' с X, У' с У. Обозначим: /(X') = {/(х): х е X'} — образ множества X' относительно /. Функция |/: X' —> У называется ограничением (или подфункцией) функции / на множестве X', если /(.г) = |/(х) для любого х е X'. Функции/ и/' равны равны ограничения этих функций на любом подмножестве множества X.

Пример 1.2.

Пусть функция /с областью определения X = {-3, -2, -1, 0, 1, 2, 3} и с областью значений У= {0, 1,9} задана формулой /(х) = х². Тогда образы элементов 0, 1, 2, 3.

суть соответственно числа 0, 1,4, 9. Полным прообразом элемента 4 относительно /.

(-3 -2 -1 0 1 2 3V.

является множество {-2,2}. 1 аблица/есть. Заданная таоли;

^ 9 4 1 0 1 4 9_у

Г-10 12 3^.

цей j q ^ о Фу^нкния |/ является ограничением (подфункцией) функции /.

на множестве {-1, 0, 1,2, 3}. >

Пусть /: X —> У, где Х_у Y — конечные. Весовой характеристикой элемента у g Y относительно функции / (обозначается w_y(J)) назовем |/И}(г/) |. Для функции / верно: X ®V (/) = |^;

уеУ Функцию/(х) называют равновероятной (сбалансированной), если весовые характеристики г^_/у(У) одинаковы для всех у е У. Функцию /называют взаимно однозначным соответствием (биективной функцией, биекцией), если = 1 для всех г/ е У, т. е. любой элемент У имеет единственный прообраз; тогда пишут /: X <-" Y. Функция / называется обратимой, если имеется функция (/: К —> АГ со свойством |/(Дх)) = х для любого х е X и /(|/(г/)) = у для любого у е Y. Функции / и |/ называют взаимно обратными, а/ — обратной к |/, обозначается / = |/^-1. Биективность функции равносильна обратимости (теорема 4.1).

Функция /: X —> X называется преобразованием множества X. Преобразование е X —" X называют тождественным, если е (х) = х для любого х е X Элемент ig X называется неподвижным элементом преобразования g*, если g'(x) = х.

«ГО 1 2 3 4).

Для функции /: {0, 1, 2, 3, 4} —" {0, 2, 4, 6, 7}, заданной таблицей.

(7 0 2 6 4_у

", «» Г° ^{2 4} 6 7) ^.

обратная функция /-* задается таблицей .О.

11 ² 4 3 0J.