Лекции Просолупов

Доказательство.

.

– = ( ) ( ) = ( ∩ ) ( ∩ ) =

=(( ∩ ) ) ∩ (( ∩ ) ) =

=( ) ∩ ( ) ∩ ( ) ∩ ( ) =

=( ) ∩ ( ) = ( ) ∩ ( ∩ ) =

=( ) ( ∩ )

Утверждение 5.3 . Для любых множеств и следующие предположения попарно эквивалентны:

1);

2)∩ = ;

3)= ;

4)= ;

5)= ?.

Доказательство. 1) 2) Очевидно, ∩ . Покажем ∩ . Действительно , так как и, следовательно, ∩ .

2)3) Пусть ∩ = . Следовательно, ( ∩ ) = . По закону поглощения и коммутативности ( ∩ ) = . Таким образом, =

3)1) По предположению = . Тогда = , что и требовалось

доказать.

3) 4) В объединении множеств и сделаем замену согласно свойству =

:

= = = .

4)5) Возьмем дополнение от предположения пункта 4) и воспользуемся правилом де Моргана:

?= = = ∩ = .

5)3) Пусть ? = . Объединим левую и правую части этого равенства с

:

= ( ) = ( ∩ ) = ( ) ∩ ( ) =

=( ) ∩ = .

Что и требовалось доказать.

11

§6. Диаграммы Эйлера-Венна

Диаграммы Эйлера-Венна помогают наглядно проиллюстрировать многие соотношения между множествами. На рисунке 1 показано применение диаграмм Эйлера-Венна для наглядного изображения основных операций над множествами.

Рисунок 1: Использование диаграмм Эйлера-Венна для иллюстрации основных операций над множествами

§7. Прямое произведение множеств

Пусть = { 1, 2, ..., }, = { 1, 2, ..., }

× = {( 1, 1), ( 1, 2), ..., ( 1, ), ( 2, 1), ..., ( , )} =

={( , ) | , }

—прямое (декартово) произведение множеств и .

Во многих случаях порядок проведения операций произведения не важен. Тогда считают, что

× ( × ) = ( × ) × = {( , , ) | , , }.

Аналогично определяется прямое произведение любого конечного числа множеств.

1 × 2 × ... × = {( 1, 2, ..., ) | , = 1, }

12

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

× × ... × = .

§8. Парадокс Рассела

Теория множеств в ее наивном изложении может приводить к парадоксам. Рассмотрим парадокс Б. Рассела.

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

(самих себя):

= { | / }.

Принадлежит ли само себе как элемент? Если , то по определению этого множества получим / . Если предположить, что / , то оказывается . В любом случае получается, что и ̸ — противоречие.

§9. Аксиомы ZFC

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

Одной из таких систем аксиом является теория Цермело-Френкеля (ZF). К этой системе аксиом часто добавляют аксиому выбора, и называют системой ЦермелоФренкеля с аксиомой выбора (ZFC). Ниже приведен список аксиом ZFC с кратким описанием и формальной записью на языке логики первого порядка.

Критерий равенства множеств

1. Аксиома объёмности. Два множества и равны тогда и только тогда, когда они состоят из одних и тех же элементов.

(( = ) ( )).

Аксиомы о существовании множеств

2. Аксиома пустого множества. Существует множество без единого элемента. Это множество обычно обозначается {} или ?.

( / ).

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

{ }) каждого своего элемента. Аксиома бесконечности утверждает, что индуктивные множества существуют.

13

((? ) ( ( { }) )).

То есть существует по крайней мере одно бесконечное множество:

{?, ? {?}, ? {?} {? {?}}, ...}.

Аксиомы об образовании множеств

4. Аксиома пары. Для любых множеств и существует множество такое, что и являются его единственными элементами. Множество обозначается { , } и называется неупорядоченной парой и . Если = , то состоит из одного элемента.

(( ) ( = = )).

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

(( ) ( )).

Если ввести отношение подмножества , то эту формулу можно упростить.

(( ) ( )).

6. Аксиома объединения. Для любого семейства множеств существует множество = , называемое объединением множества , состоящее из тех и только тех элементов, которые содержатся в элементах множества .

(( ) ( )).

7. Схема выделения. Любому множеству и свойству отвечает множество , элементами которого являются те и только те элементы , которые обладают свойством . Схема выделения содержит счётное количество аксиом, так как каждая формула ( ) логики первого порядка порождает аксиому.

(( ) ( ( ))).

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

! ( ( , )) (( ) ( ( , ))).

14

Аксиомы об упорядоченности множеств

9. Аксиома основания. Каждое непустое множество содержит элемент такой, что ∩ = ?. Другими словами, в любом семействе множеств есть, по меньшей мере, одно множество , каждый элемент которого не принадлежит данному семейству .

( ( ) ( ¬ ( ).

10. Аксиома выбора. Для любого семейства попарно непересекающихся непустых множеств существует множество (делегация) такое, что, каково бы ни было множество данного семейства, множество ∩ состоит из одного элемента.

( ̸= ? ( ̸= ?) 1 2( 1 ̸= 2 { 1, 2}1 ∩ 2 = ?) ( ( ∩ = { }))).

Замечание 9.1 . Непротиворечивость аксиоматики ZFC не была доказана.

15

Лекция 2. Бинарные отношения, функции, отношения эквивалентности

§10. Бинарные отношения

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

Пример 10.2 . 1) = {(1, 2), (2, 3), (1, 5), (3, 3)}. Тогда = {1, 2, 3}, = {2, 3, 5}.

2){( , ) | — вещественное число}. Тогда = = R.

3){( , ) | , — целые числа и найдется такое целое число , что + = }. Тогда

= = Z.

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

Замечание 10.3 . -арным отношением называют множество упорядоченных-ок. То есть, -арное отношение — это подмножество прямого произведения некоторых множеств. Любое подмножество множества можно назвать унарным отношением на множестве .

Дополнение бинарного отношения определяется так же, как дополнение множества: = . Здесь универсальное множество представляет собой

множество всех пар элементов множеств, на которых введено бинарное отношение:

= × .

Обратным отношением для отношения называют отношение

−1 = {( , ) | ( , ) }.

Композицией отношений 1 и 2 называется отношение

2 1 = {( , ) | существует такое , что 1 и 2 }.

Утверждение 10.4 . Для любых бинарных отношений , 1, 2 выполняются следующие свойства:

1)( −1)−1 = ;

2)( 2 1)−1 = −1 1 −2 1

16

Доказательство. Пункт 1 непосредственно следует из определения обратного отношения. Покажем истинность пункта 2:

( 2 1)−1 = {( , ) | : 1 , 2 } = = {( , ) | : −1 1 , −2 1 } = −1 1 −2 1

§11. Функции

Определение 11.1 . Бинарное отношение называется функцией, если из ( , ) и ( , ) следует, что = .

Две функции равны, если они состоят из одних и тех же элементов (как и любые множества).

Иногда приходится сталкиваться с трудностями в определении области значений функций. Тогда, если = и , то говорят, что функция задана на

множестве со значениями в множестве (осуществляет отображение множествав множество ), и пишут : → .

Если — функция, вместо ( , ) пишут ( ) = и говорят, что — значение, соответствующее аргументу (образ элемента ). называют прообразом элемента

.

Пример 11.2 . 1) {(1, 2), (2, 3), (48, ), ( , )} — функция;

2){(1, 2), (1, 3), (2, 4)} — не функция;

3)= {( , 2 + 2 + 1) | — вещественное число} — функция. Обратное бинарное

отношение −1 в этом случае функцией не является.

Пусть, : → .

Определение 11.3 . Функцию (отображение) назовем инъективной функцией (инъекцией), если для любых 1, 2 и любого из = ( 1) и = ( 2) следует, что 1 = 2.

Определение 11.4 . Функция называется сюръективной функцией (сюръекцией), если для любого элемента существует элемент такой, что = ( ).

Определение 11.5 . Функция называется биективной функцией (биекцией), если она и сюръективна, и инъективна.

Если указана биективная функция : → , говорят, что осуществляется взаимно-однозначное соответствие между множествами и .

17

Пример 11.6 . Рассмотрим функции : R → R.

1)( ) = инъективна, но не сюръективна (рис. 2-a));

2)( ) = 3 − сюръективна, но не инъективна (рис. 2-b));

3)( ) = 2 + 1 биективна.

a) y=ex b) y=x3-x

Рисунок 2: Примеры функций

Утверждение 11.7 . Композиция двух функций есть функция. При этом, если

: → и : → , то : → .

Доказательство. Пусть, ( , 1) и ( , 2) . Тогда существуют 1 и 2:1 = ( 1) и 2 = ( 2). При этом 1 = ( ) и 2 = ( ). Поскольку — функция, то1 = 2. Поскольку — функция, то 1 = ( 1) = ( 2) = 2. Таким образом, — функция.

Покажем, что : → . Так как : → , для любого существует: ( ) = . Так как : → , существует : = ( ) =( ( )) = ( )( ). Таким образом, для любого мы нашли такой , что

( , ) . Следовательно, = . С другой стороны, , что и требовалось доказать.

Утверждение 11.8 . Композиция двух биективных функций есть биективная функция.

Доказательство. Пусть, : → и : → — биекции. Пусть, для некоторых

1, 2 и верно = ( 1) и = ( 2). Пусть, 1, 2 те элементы, для которых 1 = ( 1) и 2 = ( 2). Тогда, = ( 1) = ( 2). Поскольку

18

инъективна, 1 = 2 и, поскольку инъективна, 1 = 2. Следовательно, — инъективна.

Пусть, . Тогда, поскольку сюръективна, существует : ( ) = . Поскольку сюръективна, существует : ( ) = . Следовательно, ( ) = и сюръективна. Таким образом, — биекция.

Пусть, −1 — отношение, обратное к . Если −1 осуществляет отображение множества в множество , говорят, что −1 — обратное отображение.

следовательно, −1 — функция.

Из сюръективности функции следует, что для любого существует :

Необходимость доказывается из тех же соображений, рассмотренных в обратном порядке: если −1 функция, то — инъективна; если −1 осуществляет отображение

из в , — сюръективна.

Замечание 11.10 . Из доказательства видно, что чтобы обратное отношение−1 было функцией, необходимо и достаточно, чтобы функция была инъективна.

Тождественным отображением множества на себя называется отображение: → такое, что для любого верно ( ) = . Если : → , тогда верно, что = и = .

Утверждение 11.11 . Если : → — биекция, то

1)( −1 ) = ;

2)( −1) = .

Доказательство. Для любого , ( −1 )( ) = −1( ( )) = . Для любого

, ( −1)( ) = ( −1( )) = .

19

§12. Отношение эквивалентности

Говорят, что — бинарное отношение на множестве , если × . Для произвольного отношения имеет смысл выбирать = .

Отношение на множестве называется рефлексивным, если для любого элемента выполняется .

Отношение на множестве называется иррефлексивным, если для любоговыполняется ( , ) / .

Отношение на множестве называется симметричным, если для любых ,из следует .

Отношение на множестве называется антисимметричным, если для любых

, из и следует = .

Отношение на множестве называется транзитивным, если для любых

, , из и следует .

Определение 12.1 . Бинарное отношение на множестве называется

отношением эквивалентности, если оно рефлексивно, транзитивно и симметрично.

Если — отношение эквивалентности и , говорят, что и эквивалентны.

Пример 12.2 . 1) = = {( , ) | , R, = } — отношение эквивалентности.

2)Отношение подобия на множестве треугольников является отношением эквивалентности.

3)Отношение сравнимости по модулю

≡ ( mod )

на множестве всех целых чисел Z является отношением эквивалентности.

Определение 12.3 . Пусть на множестве введено отношение эквивалентности . Классом эквивалентности, порожденным элементом, называется подмножество множества , состоящее из всех элементов, эквивалентных :

[ ] = { | , }.

Пример 12.4 . Продолжим пример 12.2.

1)Классы эквивалентности по отношению равенства на множестве вещественных чисел состоят из единственного элемента: [ ] = { }.

2)Класс эквивалентности по отношению подобия треугольников состоит из всех треугольников, подобных порождающему класс.

3)Класс эквивалентности для отношения сравнимости по модулю на

множестве целых чисел Z, порожденный элементом , имеет вид { + | Z}. Очевидно, что числа 0, 1, 2, ..., − 1 порождают различные классы. С другой стороны, для любого числа Z оно представимо в виде = + , где Z, а {0, 1, ..., − 1}. Значит, для любого целого числа порожденный им класс

20