Теория множеств

Материал из Викиконспекты
(перенаправлено с «Лекция 10»)
Перейти к: навигация, поиск

<< >> На главную

Теория множеств строится поверх исчисления предикатов подобно формальной арифметике. Мы добавим к исчислению предикатов один новый двуместный предикат — отношение принадлежности [math]\in[/math]. Еще несколько предикатов мы выразим внутри теории множеств.

Для изучения теории множеств мы также введем новую связку в исчисление предикатов — эквивалентность. [math]a \leftrightarrow b := a \rightarrow b \& b \rightarrow a[/math].


Определение:
Будем говорить, что множество [math]x[/math] является подмножеством

множества [math]y[/math], если любой элемент [math]x[/math] принадлежит [math]y[/math].

Формально: [math]x \subseteq y[/math] означает, что [math]\forall z (z \in x \rightarrow z \in y)[/math].


Определение:
Два множества называются

равными, если они являются подмножествами друг друга. Формально:

[math]x = y[/math] означает, что [math]x \subseteq y \& y \subseteq x[/math].


Аксиома (Аксиома равенства):
Равные множества содержатся в одних и тех же множествах. Формально: [math]\forall x \forall y \forall z ((x = y \& x \in z) \rightarrow y \in z)[/math].


Аксиома (Аксиома пары):
Каковы бы ни были два различных множества [math]x[/math] и [math]y[/math], существует множество, состоящее

в точности из них. Будем записывать это так: [math]\{x,y\}[/math].

Формально: [math]\forall x \forall y (\neg x=y \rightarrow \exists p (x \in p \& y \in p \& \forall z (z \in p \rightarrow (z = x \vee z = y)))[/math].


Аксиома (Аксиома объединения):
Для любого множества [math]x[/math], содержащего хотя бы один элемент, найдется такое множество, которое состоит в точности

из тех элементов, из которых состоят элементы [math]x[/math]. Будем записывать это так: [math]\cup x[/math].

Формально: [math]\forall x (\exists y y \in x \rightarrow \exists p \forall y (y \in p \leftrightarrow \exists s (y \in s \& s \in x)))[/math]


Аксиома (Аксиома степени):
Каково бы ни было множество [math]x[/math], существует множество [math]2^x[/math], содержащее в точности

все возможные подмножества множества [math]x[/math].

Формально: [math]\forall x \exists p \forall y (y \subseteq p \leftrightarrow y \in x)[/math].


Аксиома (Схема аксиом выделения):
Для любого множества [math]x[/math] и любой формулы от одного аргумента [math]\phi(y)[/math], такой, что

[math]b[/math] в нее не входит свободно, найдется такое множество [math]b[/math], в которое входят те и только те элементы из множества [math]x[/math], что [math]\phi(y)[/math] истинно.

Формально: [math]\forall x \exists b \forall y (y \in b \leftrightarrow (y \in x \& \phi(y)))[/math]


Определение:
Пересечением множеств [math]x[/math] и [math]y[/math] называется множество, состоящее

в точности из тех элементов, которые присутствуют и в [math]x[/math] и в [math]y[/math]. Формально:

[math]x \cap y[/math] — это такое множество [math]z[/math], что [math]\forall t (t \in z \leftrightarrow t \in x \& t \in y)[/math]


Определение:
Пустое множество [math]\emptyset[/math] — множество, которому не принадлежит никакой элемент: [math]\forall x \neg x \in \emptyset[/math].


Теорема:
1. Для любого множества [math]X[/math] существует множество [math]\{X\}[/math], содержащее в точности [math]X[/math].

2. Если существует хотя бы одно множество, то существует пустое множество.
3. Пустое множество единственно.

4. Для двух множеств существует множество, являющееся их пересечением.


Определение:
Дизъюнктным (разделенным) множеством называется множество, элементы которого

не пересекаются. Формально: [math]x[/math] дизъюнктно, если

[math]\forall y \forall z (y \in x \& z \in x \& \neg y=z \rightarrow y \cap z = \emptyset)[/math].


Определение:
Прямым произведением дизъюнктного множества [math]a[/math] называется

множество [math]\times a[/math] всех таких множеств [math]b[/math], что [math]b[/math] пересекается с каждым из элементов множества [math]a[/math] в точности в одном элементе.

[math]\forall b (b \in \times a \leftrightarrow (\forall y (y \in a \rightarrow \exists ! x (x \in y \& x \in b))))[/math]


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


Аксиома (Аксиома бесконечности):
Существует множество N, такое, что:
[math]\emptyset \in N \& \forall x(x \in N \rightarrow x\cup\{x\} \in N)[/math]


Аксиома (Аксиома фундирования):
В каждом непустом множестве найдется элемент, не пересекающийся с исходным множеством.
[math]\forall x (x = \emptyset \vee \exists y (y \in x \& y \cap x = \emptyset))[/math]


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

[math]X \in Y \in Z \in X[/math]


Аксиома (Аксиома подстановки):
Если задана некоторая функция f, представимая в исчислении предикатов

(то есть, есть предикат A, что f(x) = y тогда и только тогда, когда [math]A(x,y) \& \exists ! z A(x,z)[/math]) то для любого множества Y существует множество f(Y) — образ

множества Y при отображении f.


Ясно, что данная аксиома перекрывает аксиому выделения. Наличие аксиомы подстановки отличает аксиоматику Цермело-Френкеля от аксиоматики Цермело.


Определение:
Упорядоченной парой двух множеств [math]a[/math] и [math]b[/math] назовем множество [math]\{a,\{a,b\}\}[/math], еще будем записывать его так: [math]\langle{}a,b\rangle[/math]


Лемма:
Упорядоченная пара существует для любых множеств, также

[math]\langle{}a,b\rangle = \langle{}c,d\rangle[/math] тогда и только тогда,

когда [math]a = b[/math] и [math]c = d[/math].


Определение:
Бинарным отношением на множестве [math]X[/math] назовем подмножество множества всех упорядоченных пар элементов из [math]X[/math].


На бинарных отношениях естественным образом вводятся отношения рефлексивности, симметричтности и транзитивности.


Определение:
Отношение [math]R[/math] на множестве [math]S[/math] упорядочивает [math]X[/math], если это отношение

транзитивно и оно образует линейный порядок (строгое неравенство). Отношение вполне упорядочивает [math]S[/math], если к тому же для любого непустого подмножества [math]S[/math] выполнено

[math]\exists x (x \in B \& \forall y (y \in B \rightarrow \neg y \lt x))[/math].


Также можно ввести понятие максимума, минимума, верхней грани, супремума.


Определение:
Множество [math]x[/math] — транзитивное, если [math]z \in y, y \in x \rightarrow z \in x[/math].


Определение:
Ординал (порядковое число) — транзитивное, вполне упорядоченное с помощью [math]\in[/math] множество.


Рассмотрим ординалы подробнее. Для начала рассмотрим конечные ординалы: [math]0 := \emptyset[/math]; [math]1 := \{\emptyset\}[/math]; [math]2 := 1 \cup \{1\}[/math] и т.п. Существование этих ординалов легко доказать.

Помимо конечных, бывают бесконечные ординалы. Например, таковым является множество [math]N[/math] из аксиомы бесконечности. Заметим, что [math]N \cup \{N\}[/math] — это новый ординал, не равный исходному.


Определение:
Ординал [math]x[/math] называется предельным, если [math]\neg x = \emptyset \& \neg \exists y (y \cup \{y\} = x)[/math].


Определение:
Ординал [math]x[/math] называется натуральным числом,

если любой [math]y[/math], меньший [math]x[/math] — это либо [math]0[/math], либо про него

справедливо, что [math]\exists z (z \cup \{z\} = y)[/math].


Минимальный предельный ординал мы обозначим [math]\omega[/math]. Ясно, что любое натуральное число меньше, чем [math]\omega[/math].

Операцию [math]x \cup \{x\}[/math] можно выбрать за операцию прибавления 1. Для ординалов можно определить арифметические операции [math](+)[/math], [math](\cdot)\lt tex\gt . Получится некоторое обобщение натуральных чисел со странными свойствами. Скажем, будет справедливо \lt tex\gt 1 + \omega = \omega[/math].

Ординалы становятся важными, например, при доказательстве утверждений с помощью трансфинитной индукции: пусть есть некоторое утверждение [math]P(x)[/math], определенное на ординалах. Пусть мы можем показать, что из того, что [math]P(y)[/math] справедливо на всех ординалах [math]y \lt z[/math], следует, что [math]P(z)[/math] тоже справедливо. Тогда [math]P(x)[/math] верно для любого ординала. Трансфинитная индукция есть обобщение обычной индукции. Например, с ее помощью доказана непротиворечивость формальной арифметики.


Определение:
Назовем множества [math]X[/math] и [math]Y[/math] равномощными, если найдется биективное

отображение [math]X[/math] на [math]Y[/math]. Будем записывать это как [math]|X| = |Y|[/math]. Будем говорить, что множество [math]X[/math] имеет мощность не превышающую [math]Y[/math], если найдется инъективное отображение [math]X[/math] в [math]Y[/math]. Будем записывать это как [math]|X| \le |Y|[/math]. Будем записывать [math]|X| \lt |Y|[/math], если известно,

что [math]|X| \le |Y|[/math], но неверно, что [math]|X| = |Y|[/math].


Определение:
Кардинальное число — такой ординал [math]x[/math], что [math]y \lt x \leftrightarrow |y| \lt |x|[/math].


Все натуральные числа являются кардинальными. Также, например [math]\omega[/math] — кардинальное число (еще оно обозначается как [math]\aleph_0[/math], если речь идет о мощности множеств). [math]2^\omega[/math] — кардинальное число [math]\aleph_1[/math], соответствует мощности континуум.

Есть ли какое-нибудь кардинальное число между [math]\aleph_0[/math] и [math]\aleph_1[/math]? Континуум-гипотеза (что никаких других кардинальных чисел между ними нет) была высказана довольно давно, и длительное время была одной из главных проблем в теории множеств. Сначала Геделем было показано, что континуум-гипотеза не противоречит ZF. Утверждение о том, что и отрицание континуум-гипотезы не противоречит ZF, было доказано через 30 лет Коэном.