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

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

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

Теория множеств строится поверх исчисления предикатов подобно формальной арифметике. Мы добавим к исчислению предикатов один новый двуместный предикат — отношение принадлежности [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 лет Коэном.