Элементы теории множеств

Понятие множества

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

Теория множеств посвящена в основном изучению именно бесконечных множеств . Теория конечных множеств называется иногда комбинаторикой .

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

Заметим, что в математике допускается к рассмотрению множество, не содержащее элементов – пустое множество. Запись а Î Х означает, что а есть элемент множества Х.

Определение. Множество В называется подмножеством множества А, если каждый элемент множества В является в то же время элементом множества А.

Каждый отдельный элемент множества А образует подмножество, состоящего из этого одного элемента. Кроме того, пустое множество является подмножеством всякого множества.

Подмножество множества А называется несобственным , если оно совпадает с множеством А.

Если множество В есть подмножество множества А, то говорим, что В содержится в А и обозначаем В Í А. Подмножество В множества А называется собственным подмножеством, если В не пусто и не совпадает с А (т.е. имеется элемент множества А, не содержащийся в В).

Операции над множествами

Пусть А и В – произвольные множества.

Определение. Объединением двух множеств А и В называется множество С = АÈВ, состоящее из всех элементов, принадлежащих хотя бы одному из множеств А и В. (см. рис. 1).

Аналогично определяется объединение любого (конечного или бесконечного) числа множеств: если А i – произвольные множества, то их объединение есть совокупность элементов, каждый из которых принадлежит хотя бы одному из множеств А i .

Рис.1 Рис.2

Определение. Пересечением множеств А и В называется множество С = АÇВ, состоящее из всех элементов, принадлежащих как А, так и В (см. рис. 2). Пересечением любого (конечного или бесконечного) числа множеств А i называется множество элементов, принадлежащих каждому из множеств А i .

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

АÈВ = В È А, (А ÈВ) ÈС = А È (В È С),

А Ç В = В Ç А, (А Ç В) Ç С = А Ç (В Ç С).

Кроме того, они взаимно дистрибутивны:

(А È В) Ç С = (А Ç С) È (В Ç С), (1)

(А Ç В) È С = (А È С) Ç (В È С). (2)

Определение. Разностью множеств А и В называется множество тех элементов из А, которые не содержатся в В (рис. 3 ).

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

Пусть X и Y – два произвольных множества.

Определение. Говорят, что на X определена функция f , принимающая значение из Y, если каждому элементу x Î X поставлен в соответствие один и только один элемент y Î Y. При этом множество X называется областью определения данной функции, а множество Y – её областью значений .

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

Если а элемент из X, то соответствующий ему элемент b = f (а ) из Y называется образом а при отображении f . Совокупность всех тех элементов а из X, образом которых является данный элемент b Î Y, называется прообразом (или точнее полным прообразом ) элемента b и обозначается f –1 (b ).

Пусть А – некоторое множество из X; совокупность {f (а ): а Î А} всех элементов вида f (а ), где а Î А, называется образом А и обозначается f (А). В свою очередь для каждого множества В из Y определяется его полный прообраз f –1 (В), а именно: f –1 (В) есть совокупность всех тех элементов из X, образы которых принадлежат В.

Определение. Будем говорить, что f есть отображение множества X на множество Y, если f (X) = Y; такое отображение называют сюръекцией . В общем случае, т.е. когда f (X) Ì Y, говорят, что f есть отображение в Y. Если для любых двух различных элементов х 1 и х 2 из X их образы y 1 = f (x 1) и y 2 = f (x 2) также различны, то f называется инъекцией. Отображение f : X®Y, которое одновременно является сюръекцией и инъекцией, называется взаимно однозначным соответствием междуX и Y.

Отображения (функции)

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

Определение. Отношение f на AB называется отображением (функцией) из A в B, если для каждого xA существует один и только один yB. множество бинарный отношение эквивалентность

f: AB или y=f(x)

Множество A называется областью определения. Множество B - областью значений.

Если y=f(x), то x называют аргументом , а y - значением функции.

Пусть f: AB, тогда

множество определения функции:

множество значений функции:

Множество определения функции является подмножеством области определения, т.е. Dom f A, а множество значений функции является подмножеством области значений функции, т.е. Im f B. Если, то функция называется тотальной, а если частичной функцией. Так диаграмма Венна служит удобной иллюстрацией функции, определенной на множестве A со значениями в множестве B.

Способы задания функции:

• 1) Словесный.
• 2) Аналитический.
• 3) С помощью графика, рисунка.
• 4) С помощью таблиц.

Определение. Если MA, то множество f(M)=y f(x)=y для некоторого x из M называется образом множества M.

Если KB, то множество f -1 (K)=x f(x)K называется прообразом множества K.

Определение Функция называется функцией n аргументов, или n-местной функцией. Такая функция отображает кортеж в элемент bB, .

Свойства отображений (функций).

1) Отображение f: AB называется инъективным , если оно различные элементы из A отображает в различные элементы из B: .

Это свойство можно показать с помощью диаграмм Венна.

2) Отображение f: AB называется сюръективным или отображением на все мно-жество B, если в каждый элемент множества B отображается хотя бы один элемент из A: .

Это свойство тоже можно показать с помощью диаграмм Венна.

3) Отображение f: AB, которое одновременно инъективно и сюръективно, называется биективным или взаимно однозначным отображением множества A на множество B.

Пример. Пусть дано отображение f: RR, которое определено таким образом, что. Выяснить, какими свойствами обладает это отображение.

Решение. Функция f не является инъективной, т.к. f (2)=f (2), но 2 2.

Функция f не является также и сюръективной, поскольку не существует такого действительного числа x, для которого f (x)= 1.

Определение. Пусть f биективное отображение множества A в множество B. Если поставить в соответствие каждому элементу из B связанный с ним элемент из A, то такое соответствие является отображением B в A. Это отображение обозначается и называется отображением, обратным отображению f.

Обратное отображение обладает некоторыми свойствами, которые сформулируем в следующей теореме.

Теорема 3. Если f: AB - биекция, то

1) для любого y из B;

2) для любого x из A.

Доказательство. 1) Пусть yB и. Тогда f(x)=y. Но поскольку

2) Аналогично доказывается, что для любого x из A.

Определение. Композицией (суперпозицией, произведением) отображений f: AB и g: BC называется отображение h: , которое записывается h=g f.

Такой способ записи суперпозиции функций объясняется тем, что обозначение функции принято писать слева от списка аргументов:

Рассмотрим еще один важный частный случай общего понятия соответствия - отображения множеств. При соответствии R между множествами Х и Y образ элемента а Х может оказаться пустым, а может содержать и несколько элементов.

Отношение между элементами множеств Х и Y называется отображением Х в Y , если каждому элементу х из множества Х соответствует только один элемент множества Y . Этот элемент называют образом элемента х при данном отображении: f(x). На графе такого отображения из каждой точки множества Х будет выходить только одна стрелка (рис. 29).

Рассмотрим следующий пример. Пусть Х - множество студентов в аудитории, а Y - множество стульев в той же аудитории. Соответствие «студент х сидит на стуле у » задает отображение Х в Y . Образом студента х является стул.

Пусть Х = Y = N - множество натуральных чисел. Соответствие «десятичная запись числа х состоит из у цифр» определяет отображение N в N . При этом отображении числу 39 соответствует число 2, а числу 45981 - число 5(39 - двузначное число, 45981 - пятизначное).

Пусть Х - множество четырехугольников, Y - множество окружностей. Соответствие «четырехугольник х вписан в окружность у » не является отображением Х в Y , так как есть четырехугольники, которые нельзя вписать в окружность. Но в этом случае говорят, что получилось отображение из множества Х в множество Y .

Если отображение Х в Y таково, что каждый элемент y из множества
Y соответствует одному или нескольким элементам х из множества Х , то такое отображение называют отображением множества Х на множество Y .

Множество Х называют областью определения отображения f: XY, а множество Y - областью прибытия этого отображения. Часть области прибытия, состоящая из всех образов y из множества Y, называется множеством значений отображения f.

Если y=f(x), то х называют прообразом элемента у при отображении f . Множество всех прообразов элемента у называют его полным прообразом: f (y).

Отображения бывают следующих видов: инъективными, сюръективными и биективными.

Если полный прообраз каждого элемента yY содержит не более одного элемента (может быть и пустым), то такие отображения называют инъективными.

Отображения XY такие, что f(X)=Y , называют отображениями Х на все множество Y или сюръективными (из каждой точки множества Х выходит стрелка, а после изменения направления в каждой точке множества Х заканчивается) (рис. 31).

Если отображение инъективно и сюръективно, то его называют взаимно однозначным или биективным.

Отображение множества Х на множество называется биективным , если каждому элементу х Х соответствует единственный элемент yY, а каждый элемент yY соответствует только одному элементу х Х (рис. 32).

Биективные отображения порождают равномощные (эквивалентные) множества: X~Y.

Пример . Пусть - Х множество пальто в гардеробе, Y - множество крючков там же. Поставим в соответствие каждому пальто крючок, на котором оно висит. Это соответствие является отображением Х в Y. Оно инъективно, если ни на одном крючке не висит более одного пальто или некоторые крючки свободны. Данное отображение сюръективно, если все крючки заняты или на некоторых висят несколько пальто. Оно будет биективным, если на каждом крючке висит только одно пальто.

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

Пусть - произвольные множества. Отображением множества X в множество Y называется всякое правило f , по которому каждому элементу множества сопоставляется вполне определенный (единственный) элемент множества .

Тот факт, что f есть отображение , кратко записывают в виде: .

Применяют также обозначение . Чаще отображения обозначают буквами f , q , F .

Итак, чтобы задать отображение множества Х в множество , надо каждому элементу поставить в соответствие один и только один элемент .

Если при этом элементу х из Х сопоставлен элемент из Y , то называют образом элементах , а х – прообразом элемента при отображении , что записывается в виде .

Из определения отображения следует, что у каждого элемента из Х образ единственный, однако для элемента прообразов может быть много, а может и вообще не быть. Множество всех прообразов элемента называется его полным прообразом и обозначается через . Таким образом, .

Естественным путем определяются образ подмножества из А и прообраз подмножества из В при отображении :

Например , пусть и - отображение А в А , сопоставляющее каждому элементу а из А остаток от деления а на число 4. Тогда имеем:

В зависимости от свойств, образов и прообразов различают отображения сюръективные, инъективные и биективные.

Отображение называется сюръективным , если , т.е. каждый элемент из отображается хотя бы один элемент из Х , или при любом .

Отображение называется инъективным , если разные элементы множества Х отображаются в разные элементы множества т.е. , или является либо пустым, либо одноэлементным множеством при любом . Инъективные отображения называются также вложениями .

Отображение называется биективным , или взаимно однозначным отображением на , если оно сюръективно и инъективно, т.е. если есть одноэлементное множество при любом . В этом случае можно определить отображения , положив для любого : . Оно называетсяобратным к и обозначается в виде .

Изобразим для наглядности виды отображений.

Сюръективное Инъективное Биективное

Рисунок 12

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

Примером подстановки множества целых чисел может служить отображение , определенное равенством .

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

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

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

1) Пусть Х – множество окружностей на плоскости. Сопоставляя каждой окружности ее центр, получим отображение Х на . Это отображение не является инъективным, поскольку одна и та же точка может быть центром бесконечного множества окружностей. Но оно сюръективно, так как любая точка – центр некоторой окружности. Поэтому обратное соответствие всюду определено, сюръективно, но не функционально.

2) Соответствие является числовой функцией заданной на всем множестве действительных чисел. Множеством значений этой функции является совокупность неотрицательных чисел. Так как , то функция не сюръективна. Она и не инъективна, так как . Поэтому она не имеет обратной функции.

3) Отображение сюръективно и инъективно: для любого есть одно и только одно число такое, что . Этим числом является .

4) Отображение ( - множество неотрицательных чисел) множества в себя всюду определено, инъективно, но не сюръективно. Действительно, для дроби , выполнено .

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

5) Отображение , определенное правилом является инъективным отображением. Оно не является биективным, поскольку . Однако, если таким же образом определить отображение в , то получим биективное отображение. . ; из сюръективности следует сюръективность лишь , а из инъективности следует инъективность лишь .

3. Если и - преобразования множества А , то их композиция также является преобразованием множества А .

Введение в теорию множеств и комбинаторику

Практическая работа № 8. Отображения. Виды отображений

Вопросы к работе

1. Что такое «отображение множества в множество»?
2. Что такое «образ», что такое «прообраз» при данном отображении?
3. Что такое полный f - образ, что такое полный f - прообраз, при отображении f ?
4. Назовите типы отображений, дайте их определения и приведите примеры.
5. Какие два множества называются эквивалентными? Приведите примеры.
6. Какое множество называется счетным? Приведите примеры.

Образцы решения заданий

Пример 1. Пусть А = {1; 2; 3; 4; 5; 6; 7; 8; 9} N и В ={0; 1} Z Поставим в соответствие каждому числу x A его остаток при делении на 2.

Является ли это соответствие отображением? Какой тип у этого отображения? Какой элемент является образом элемента 6, 7? Найдем полный прообраз элемента 1.

Решение. Изобразим заданное соответствие с помощью графа:

Видим, что:

1) каждый элемент множества А , является точкой исхода;

2) у каждой точки исхода, имеется только по одной точке прибытия. (Значит, указанное соответствие является отображением множества А в множество В);

3) Каждый элемент множества В является точкой прибытия. (Значит, это отображение «на»).

Так как в множестве В есть элемент (например, 0), для которого прообразом является ни один элемент из А , то это отображение не является взаимооднозначным.

Образом числа 6 является число 0 В , образом числа 7 – число 1 В . Полный прообраз числа 1 В есть множество чисел {1; 3; 5; 7; 9} А .

Пример 2. Пусть Х – множество треугольников плоскости, Y = R. Выберем единицу измерения длин и сопоставим каждому треугольнику число – периметр этого треугольника. Будет ли это соответствие отображением? Какой тип у заданного отображения? Каков полный прообраз числа у R ?

Решение. Каждый треугольник на плоскости имеет однозначно определенный периметр. Поэтому каждому треугольнику из множества Х сопоставляется единственное число из R , т. е. это соответствие является отображение Х в R . При этом у двух разных треугольников может быть одинаковый периметр. Другими словами, отображение не является взаимооднозначным. Кроме того, не существует треугольника, периметр которого равен отрицательному числу, т.е. отображение не является отображением «на». Пусть у R . Тогда:

1. у > 0, полный образ – множество всех треугольников плоскости, периметр которых равняется числу у , это множество бесконечное.
2. у ≤ 0, полный образ – пустое множество.

Пример 3. Х = {0; 1; 2; 3; 4} N , Y = Z. Отображение f множества Х в множество Y задано следующим образом:

Определим тип этого отображения и построим его график.

Решение. Для каждого x X найдем образ y Y. Соответствующие результаты запишем в таблицу:

y=f(x)	–2

Множество значений отображения f есть множество

A = {–2; 1; 4; 7; 10} Y и В ≠ Y . У каждого элемента y В в Х имеется только по одному прообразу. Мы имеем, следовательно, отображение взаимооднозначное множества Х в множество Y .

Пары значений (x ; у ) из таблицы образует график данного отображения f: Х→Y . В прямоугольной системе координат этот график имеет вид:

Пример 4. Даны два множества слов: Х = {красный; синий; зеленый; желтый} и Y = {галстук; свет; платок; лист}. Эквивалентны ли эти множества?

Решение. Эти множества эквивалентны, т. к. для них можно установить взаимооднозначное отображение "на".

Например:

Пример 5. Даны множества: А = { x | x = 2 n , n N } и

В = { x | x = , n N }. Эквивалентны ли эти множества?

Решение. Эти множества эквивалентны, т. к. можно подобрать взаимооднозначное отображение множества A на множество В .

Например: f: А В

x = 2 n y = .

Упражнения

1. Между множеством имя Х = {Андрей; Борис; Михаил; Алексей; Константин; Василий; Валентина; Клара; Семен; Мария; Софья; Олег; Трофим4 Юрий; Яков} и множеством Y (букв русского алфавита) установлено соответствие, при котором каждому имени сопоставляется его первая буква. Будет ли это соответствие отображением Х в Y ? Если "да", то какого типа? Найдите образ множества Х . Найдите полные прообразы букв А , Б, К, Л. Постройте граф указанного соответствия.

2. Каждой точке М отрезка АВ поставим в соответствие ее проекцию М на данную прямую L . Будет ли это соответствие отображением? Каким? Опишите область определения, область значений этого отображения.

3. Множество Х состоит из всех квадратов на плоскости, а множество Y из всех окружностей на той же плоскости. Поставим в соответствие каждому квадрату вписанную в него окружность. Является ли это соответствие отображением Х на Y ?

4. Можно ли задать отображение следующим образом: множество А из отрезков, на Y – из треугольников; каждому отрезку ставится в соответствие треугольник, для которого этот отрезок является средней линией?

5. Верно ли, что соответствие f: Z Z

X у = –5 х + 2

есть отображение "на"?

6. Пусть Х – множество вещественных чисел. Каждому числу х Х поставим в соответствие его квадрат. Можно ли это соответствие назвать обратимым отображением?

7. Покажите, что следующие множества счетны:

а) множество нечетных натуральных чисел;

б) множество неотрицательных целых чисел;

в) множество квадратов натуральных чисел;

г) множество натуральных чисел, кратных 5;

д) множество кубов натуральных чисел.

8. Даны два множества: A = {Париж; Москва; Варшава; Краков; Лондон; Саранск; Владимир; Марсель} и B = {Франция; Россия; Англия; Польша; Швеция; Австрия}. Зададим соответствие между ними: «город x A находится в стране ». Построим графики этого соответствия. Будет ли это соответствие отображением? Какого типа?

9. Эквивалентны ли множества А изображений населенных пунктов на карте и множество B населенных пунктов местности, изображенной на карте?

Индивидуальное задание

1. Среди указанных соответствий выбрать отображения. Указать их тип, построить график.

2. Изобразите в прямоугольной декартовой системе координат графики следующих отношений в Z . Для каждого отношения выясните, является ли оно отображением Z в Z , отображением Z на Z , взаимооднозначным отображением, наложением:

1) х + у = 3; 7) у < х + 2;

2) х – у ≤ 5; 8) у ≤ х + 2;

3) х + у = 4, x > 0; 9) у = 4;

4) x = y , – 4 ≤ х ≤ 6; 10) ху = 24, –6 ≤ х ≤ 6.

5) = у , – 4 ≤ х ≤ 6;

6) x > у ;

Задания для самоконтроля

Соедините следующие пары множеств знаком «=», если они равны, и знаком «~», если они эквивалентны:

1) А – множество сторон треугольника,

В - множество углов треугольника;

2) А - множество букв в слове «колос»,

В = {о; к; с; л};

3) А – множество колец на пне дерева,

В – множество лет, прожитым деревом;

4) множество материков на Земле и множество государств