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

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

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

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

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

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

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

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

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

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

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

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

Определение. Объединением двух множеств А и В называется множество С = АÈВ, состоящее из всех элементов, принадлежащих хотя бы одному из множеств А и В. (см. рис. 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.

ОТОБРАЖЕНИЯ МНОЖЕСТВ §1. Основные определения

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

Отображения также называют функциями .

Будем использовать следующие обозначения:

ƒ : А→ В. Отображение f множество А переводит в В;

А f В. Множество А отображается в В при отображении f.

Если элемент а при отображении f переходит в элемент b, то пишут f(a)=b (левая запись) или af=b (правая запись). Элемент b называется образом элемента а при отображении f; элемент а – прообразом b при

этом отображении. Множество { f (a ) | a A } = f (A ) – образ множества А при отображении f. Отметим, что

f (A ) B .

А B

f f(A)

А – область определения отображения f; В – область значений отображения f (иногда –например, в школьной математике – областью значений считается f(A), но мы будем ею считать В).

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

Из всех отображений особо выделяют следующие виды :

1. Сюръекция (отображение «на») – это отображение f : A → B такое, что f (A ) = B . При сюръекции у каждого элемента из множества В существует хотя бы один прообраз.

2. Инъекция – отображение, при котором разные элементы переходят в разные, т.е. если a , a 1 A и a ≠ a 1 , то f (a ) ≠ f (a 1 ) .

				f(a1 )

3. Биекция, или взаимно однозначное отображение – это отображение, которое одновременно является инъекцией и сюръекцией.

Примеры отображений:.

1. Пусть А – любое множество и В – множество, состоящее из одного элемента, т.е. B={b}.

А . b

Отображение f (a ) = b , a A является сюръекцией, т.к. f(A)=B.

2. Пусть множество А – некоторый отрезок на плоскости, множество В – прямая. Из каждой точки отрезка А опустим перпендикуляр на прямую В и основания этих перпендикуляров поставим в соответствие точкам отрезка А.

А а

φ(а) В

Обозначим это отображение через φ. Очевидно,

ϕ (a ) ≠ ϕ (a 1 ), a , a 1 A , a ≠ a 1 .

Следовательно, отображение φ – инъекция (но не является сюръекцией).

3. Пусть множество А – гипотенуза прямоугольного треугольника, а В – его катет. Любой точке гипотенузы поставим в соответствие её проекцию на катет. Получим взаимно однозначное отображение А на В:

т.е. f – биекция.

Отметим, что именно так в математике доказывается, что «количество» точек на гипотенузе и катете одинаково (точнее, эти множества имеют одинаковую мощность).

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

4. Если f – любая функция действительного переменного, то f – отображение R в R.

§2. Умножение отображений

Пусть А, В, С – три множества и заданы два отображения f : A → B и ϕ : B → C .

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

ϕ f

Возможны два варианта записи.

1. Левая запись.
ƒ (a)=b, ϕ (b)=c.		обозначить ϕ f :
Тогда произведение f и φ будет	переводить а в с, его следует
(ϕ f ) (a ) = ϕ (f (a ) ) = ϕ (b ) = c , ϕ f : A → C (см. выше рисунок).
По определению (ϕ f ) (a ) = ϕ (f (a ) ) ,	т.е. произведение отображений –	это сложная функция,
заданная на А.

2. Правая запись.

aƒ =b, bϕ =c. Тогда a (f ϕ ) = (af ) ϕ = b ϕ = c ,

f ϕ : A → C.

Мы будем пользоваться левой записью (отметим, что в книге используется правая). Произведение отображений ниже мы будем обозначать через f ϕ .

Замечание 1 . Из определения умножения отображений следует, что перемножать можно не любые отображения, а только те, у которых «средние» множества одинаковые. Например, если f : A → B ,ϕ : D → C , то при В=D можно перемножать отображения f и φ, а при В≠D нельзя.

Свойства умножения отображений

Определение 2 . Отображения f и g называются равными , если у них совпадают области определения и области значений, т.е. f : A → B , g : A → B и выполняется условие: a A справедливо

равенство f (a ) = g (a ) .

1. Умножение отображений некоммутативно. Другими словами, если fφ и φf существуют, то они не обязательно равны.

Пусть, например, множества A=B=C=R, f (x ) = sin x ,ϕ (x ) Рассмотрим произведения:

(ϕ f ) (x ) = ϕ (f (x )) = ϕ (sin x ) = e sin x ,

(f ϕ ) (x ) = f (ϕ (x )) = f (e x ) = sin(e x ).

Следовательно, функции fφ и φf различны.

2. Умножение отображений ассоциативно.

Пусть f : A → B , ϕ : B → C , ψ : C → D . Докажем, что (ψϕ ) f

E x , f : R → R, ϕ : R → R .

и ψ (ϕ f ) существуют и равны,т.е.(ψϕ ) f =

ψ (ϕ f ) . (1)

Очевидно, что (ψϕ ) f : A → D ,ψ (ϕ f ) : A → D .

Для доказательства равенства (1) в силу определения равенства отображений требуется проверить, чтоa A : ((ψϕ ) f ) (a ) = (ψ (ϕ f )) (a ) (2). Пользуясь определением умножения отображений (в левой записи)

((ψϕ )f )(a ) = (ψϕ )(f (a ) )= ψ (ϕ (f (a ) )),

(ψ (ϕ f ))(a ) = ψ ((ϕ f )(a ) )= ψ (ϕ (f (a ) )). (4)

Т.к. в равенствах (3) и (4) равны правые части, то равны и левые, т.е. справедливо равенство (2), а тогда выполняется и (1).

Замечание 2. Ассоциативность умножения позволяет однозначно определить произведение трех, а затем и любого конечного числа множителей.

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

Пусть f : A → B – биекция, f (a ) = b , a A , b B . Тогда для любого элемента b B по определению биекции существует единственный прообраз при отображении f – это элемент а. Теперь можно определить f − 1 : B → A , полагая f − 1 (b ) = a (b B ) . Нетрудно видеть, что f − 1 – биекция.

Итак, у всякого биективного отображения имеется обратное.

§3. Преобразования множеств

Всякое отображение f : A → A называется преобразованием множества А. В частности, любая

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

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

Так как преобразования – это частный случай отображений, то для них справедливо всё сказанное выше об отображениях. Но умножение преобразований множества А имеет и специфические свойства:

1. для любых преобразований f и φ множества А произведения fφ и φf существуют;

2. существует тождественное преобразование множества А ε : ε (a ) = a , a A .

Нетрудно видеть, что для любого преобразования f этого множества f ε = ε f = f , так как, например, (f ε ) (a ) = f (ε (a ) ) = f (a ) . Значит, преобразование ε играет роль единичного элемента при умножении преобразований.

равенства легко проверяются. Тем самым обратное преобразование играет роль обратного элемента при умножении преобразований.

Рассмотрим еще один важный частный случай общего понятия соответствия - отображения множеств. При соответствии 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. Оно инъективно, если ни на одном крючке не висит более одного пальто или некоторые крючки свободны. Данное отображение сюръективно, если все крючки заняты или на некоторых висят несколько пальто. Оно будет биективным, если на каждом крючке висит только одно пальто.

Отображение %%f%% называется инъективным ,

если для любых элементов %%x_1, x_2 \in X%%, %%x_1 \neq x_2%%, следует, что %%f(x_1) \neq f(x_2)%%. $$ \forall x_1, x_2 \in X~~x_1 \neq x_2 \rightarrow f(x_1) \neq f(x_2). $$

Другими словами, отображение %%f%% инъективно, если образы различных элементов из %%X%% также различны.

Пример

Функция %%f(x) = x^2%%, определенная на множестве %%\mathbb{R}%%, не является инъективной, так как при %%x_1 = -1, x_2 = 1%% получаем одно и тоже значение функции %%f(x_1) = f(x_2) = 1%%.

Сюръективное отображение

Отображение %%f%% называется сюръективным , если для всякого элемента %%y \in Y%% существует элемент %%x \in X%% с условием, что %%f(x) = y%%. $$ \forall y \in Y~\exists x \in X: f(x) = y. $$

Другими словами, отображение %%f%% сюръективно, если каждый элемент %%y \in Y%% является образом хотя бы одного элемента %%x \in X%%.

Пример

Отображение %%f(x) = \sin(x)%%, определенное на множестве %%\mathbb R%%, с множеством %%Y = [-2,2]%% не является сюръективным, т.к. для элемента %%y = 2 \in Y%% нельзя найти прообраз %%x \in X%%.

Биективное отображение

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

Обычно, словосочетания «инъективное отображение», «сюрьективное отображение» и «биективно отображение» заменяют на «инъекция», «сюръекция» и «биекция» соответственно.

Обратное отображение

Пусть %%f: X \to Y%% — некоторая биекция и пусть %%y \in Y%%. Обозначим через %%f^{-1}(y)%% единственный элемент %%x \in X%% такой, что %%f(x) = y%%. Тем самым мы определим некоторое новое отображение %%g: Y \to X%%, которое снова является биекцией. Ее называют обратным отображением .

Пример

Пусть %%X, Y = \mathbb R%% — множество действительных чисел. Функция %%f%% задана формулой %%y = 3x + 3%%. Имеет ли данная функция обратную? Если да, то какую?

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

1. Проверим инъекцию. Пусть %%x_1 \neq x_2%%. Проверим, что %%f(x_1) \neq f(x_2)%%, то есть %%3 x_1 + 3 \neq 3 x_2 + 3%%. Предположим противное, %%3 x_1 + 3 = 3 x_2 + 3%%. Тогда получается, что %%x_1 = x_2%%. Получили противоречие, т.к. %%x_1 \neq x_2%%. Следовательно, %%f%% — инъекция.
2. Проверим сюръекцию . Пусть %%y \in Y = \mathbb{R}%%. Найдем элемент %%x \in X = \mathbb{R}%% c условием, что %%f(x) = y%%, то есть %%3x + 3 = y%%. В данном равенстве задан элемент %%y \in \mathbb{R}%% и нужно найти элемент %%x%%. Очевидно, что $$ x = \frac{y-3}{3} \text{ и } x \in \mathbb R $$ Следовательно, отображение %%f%% сюръективно.

Так как %%f%% — инъекция и сюръекция, то %%f%% — биекция. И, соответственно, обратным отображением является %%x = \frac{y-3}{3}%%.

Изучим теперь некоторые вопросы, связанные с отношениями между множествами.

Будем говорить, что между множествами изаданоотношение (инаходятся в отношении), если некоторым (возможно всем) элементам изсоответствуют некоторые элементы из. Если множествонаходится в отношениис множеством, то будем писать:

Если при этом элементу ставится в соответствие элемент, то обозначать это будем

Определение 1.1.2. Отношение между множествамииназываетсяотображением , если каждому изпоставлен в соответствие один и только один элементиз(см. рис. 1.1.2. и 1.1.3). При специализации природы множествивозникают специальные типы отображений, которые носят особые названия “функция”," вектор-функция", "оператор", "мера", "функционал" и т.д. Мы столкнемся с ними в дальнейшем.

Для обозначения функции (отображения) из вбудем пользоваться записью

Рис.1.1.2. Отображение Рис.1.1.3.Отношение, не являющееся

отображением

Определение 1.1.3 . Если - элемент из, то отвечающий ему элементиз, называется его образом (при отображении), а множество всех тех, для которых, называется прообразоми обозначается(см.рис.1.1.4).

Рис.1.1.4. Прообраз b

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

Рис.1.1.5. Взаимно однозначное отображение

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

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

1.7. Мощность множества

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

Будем говорить, что множества иимеютодинаковую мощность , если существует взаимно однозначное отображение множества на множество(заметим, что в этом случае существует и взаимно однозначное отображение множества B на множество A).

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

Пусть - произвольные множества, тогда

т.е. любое множество эквивалентно самому себе; если множество эквивалентно множеству, тоэквивалентно; если, наконец, множествоэквивалентно множеству, которое эквивалентно множеству, тоэквивалентно.

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

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

Мощность конечного множества равна числу его элементов. Для бесконечных множеств понятие "мощность" является обобщением понятия "количество элементов".

Укажем некоторые, полезные для дальнейшего, классы множеств.

Множество называется счетным , если оно имеет такую же мощность как и некоторое подмножество множества (множества натуральных чисел). Счетное множество может быть конечным или бесконечным.

Бесконечное множество является счетным тогда и только тогда, когда оно эквивалентно множеству натуральных чисел .

Заметим, что любое множество, мощность которого меньше мощности бесконечного счетного множества, является конечным.

Множество действительных чисел на отрезке от нуля до единицы имеет мощность континуум , и само часто называется континуумом . Мощность этого множества больше мощности бесконечного счетного множества. Возникает вопрос: имеется ли множество, мощность которого больше мощности бесконечного счетного множества, но меньше мощности континуум. Эта задача была сформулирована в 1900 году одним из крупнейших математиков мира Давидом Гильбертом. Оказалось, что эта задача имеет несколько неожиданный ответ: можно считать, что такое множество существует, а можно считать, что его не существует. Получающиеся при этом математические теории будут непротиворечивыми. Доказательство этого факта было доложено американским ученым Коэном в 1965 году на всемирном конгрессе математиков в Москве. Отметим, что ситуация с этой задачей напоминает ситуацию с пятым постулатом Евклида: через точку, лежащую вне данной прямой можно провести только одну прямую, параллельную данной. Как показал Лобачевский, отказ от этого постулата не приводит к противоречиям. Мы можем строить геометрию, для которой этот постулат имеет место, и геометрии, для которых он не верен.

В заключение приведем несколько примеров, демонстрирующих методику доказательства эквивалентности множеств.

Пример 1.11. Множество целых чисел счетное.

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

Для доказательства счетности множества целых чисел надо построить взаимно однозначное отображение между множеством натуральных чисел и рассматриваемым множеством. Требуемое отображение задается правилом: расположим целые числа следующим образом:

и перенумеруем их натуральными числами, присвоив им номера (они указаны рядом с рассматриваемыми целыми числами). Очевидно, что каждое целое число получит свой номер, при этом разные числа получат разные номера. Верно и обратное: для каждого натурального числа (для каждого номера) найдется и при том единственное целое число, стоящее под этим номером. Таким образом, требуемое взаимно однозначное отображение построено.

Пример 1.12 . Множество рациональных чисел счетное.

Известно, что любое рациональное число можно представить в виде несократимой дроби p/q, используя это представление расположим рациональные числа в соответствии со схемой:

. . . . . .

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

Пример 1.13 . Объединение счетного множества счетных множеств есть множество счетное.

Доказательство этого факта аналогично доказательству утверждения предыдущего примера.

В заключение приведем важное для дальнейшего утверждение. Но для этого нам потребуется еще одна операция над множествами.

Прямым произведением множеств и(декартовым произведением ) называется множество всех упорядоченных пар , гдеи. Это множество обозначается. Таким образом:

Обозначим , произведениесомножителейбудем обозначать.

Теорема 1.1 . для любого бесконечного множестваБолее того.

В частности , т.е. множество точек на прямой имеет такую мощность, что и множество точек на плоскости. Более того, точек в пространстве столько, сколько и на прямой.

На этом мы заканчиваем знакомство с основными понятиями математической логики и теории множеств - основ современной математики. Отметим, что многие аспекты этих теорий остались, к сожалению, за рамками этой главы, познакомиться с ними можно, например, по и .