39
правок
Изменения
Нет описания правки
[[Категория: Математическая логика]]
= Теория множеств. =
Теория множеств строится поверх исчисления предикатов подобно формальной арифметике.
Мы добавим к исчислению предикатов один новый двуместный предикат — отношение
принадлежности <tex>\in</tex>. Еще несколько предикатов мы выразим
внутри теории множеств.
Для изучения теории множеств мы также введем новую связку в исчисление
предикатов — эквивалентность. <tex>a \leftrightarrow b := a \rightarrow b \& b \rightarrow a</tex>.
{{Определение
|definition=
Будем говорить, что множество <tex>x</tex> является подмножеством
множества <tex>y</tex>, если любой элемент <tex>x</tex> принадлежит <tex>y</tex>.
Формально: <tex>x \subseteq y</tex> означает, что <tex>\forall z (z \in x \rightarrow z \in y)</tex>.
}}
{{Определение
|about=Принцип объемности
|definition=
Два множества называются
равными, если они являются подмножествами друг друга. Формально:
<tex>x = y</tex> означает, что <tex>x \subseteq y \& y \subseteq x</tex>.
}}
{{Аксиома
|about=Аксиома равенства
|axiom=
Равные множества содержатся в одних и тех же множествах. Формально:
<tex>\forall x \forall y \forall z (x = y \& x \in z \rightarrow y \in z)</tex>.
}}
{{Аксиома
|about=Аксиома пары
|axiom=
Каковы бы ни были два различных множества <tex>x</tex> и <tex>y</tex>, существует множество, состоящее
в точности из них. Будем записывать это так: <tex>\{x,y\}</tex>.
Формально: <tex>\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)))</tex>.
}}
{{Аксиома
|about=Аксиома объединения
|axiom=
Для любого множества <tex>x</tex>, содержащего хотя бы один элемент, найдется такое множество, которое состоит в точности
из тех элементов, из которых состоят элементы <tex>x</tex>. Будем записывать это так: <tex>\cup x</tex>.
Формально: <tex>\forall x (\exists y y \in x \rightarrow \exists p \forall y (y \in p \leftrightarrow \exists s (y \in s \& s \in x)))</tex>
}}
{{Аксиома
|about=Аксиома степени
|axiom=
Каково бы ни было множество <tex>x</tex>, существует множество <tex>2^x</tex>, содержащее в точности
все возможные подмножества множества <tex>x</tex>.
Формально: <tex>\forall x \exists p \forall y (y \subseteq p \leftrightarrow y \in x)</tex>.
}}
{{Аксиома
|about=Схема аксиом выделения
|axiom=
Для любого множества <tex>x</tex> и любой формулы от одного аргумента <tex>\phi(y)</tex>, такой, что
<tex>b</tex> в нее не входит свободно, найдется такое множество <tex>b</tex>, в которое
входят те и только те элементы из множества <tex>x</tex>, что <tex>\phi(y)</tex> истинно.
Формально: <tex>\forall x \exists b \forall y (y \in b \leftrightarrow (y \in x \& \phi(y)))</tex>
}}
{{Определение
|definition=
Пересечением множеств <tex>x</tex> и <tex>y</tex> называется множество, состоящее
в точности из тех элементов, которые присутствуют и в <tex>x</tex> и в <tex>y</tex>. Формально:
<tex>x \cap y</tex> — это такое множество <tex>z</tex>, что <tex>\forall t (t \in z \leftrightarrow t \in x \& t \in y)</tex>
}}
{{Определение
|definition=
Пустое множество <tex>\emptyset</tex> — множество, которому не принадлежит
никакой элемент: <tex>\forall x \neg x \in \emptyset</tex>.
}}
{{Теорема
|statement=
1. Для любого множества <tex>X</tex> существует множество <tex>\{X\}</tex>, содержащее в точности <tex>X</tex>.<br>
2. Если существует хотя бы одно множество, то существует пустое множество.<br>
3. Пустое множество единственно.<br>
4. Для двух множеств существует множество, являющееся их пересечением.
}}
{{Определение
|definition=
Дизъюнктным (разделенным) множеством называется множество, элементы которого
не пересекаются. Формально: <tex>x</tex> дизъюнктно, если
<tex>\forall y \forall z (y \in x \& z \in x \& \neg y=z \rightarrow y \cap z = \emptyset)</tex>.
}}
{{Определение
|definition=
Прямым произведением дизъюнктного множества <tex>a</tex> называется
множество <tex>\times a</tex> всех таких множеств <tex>b</tex>, что <tex>b</tex> пересекается с каждым из элементов
множества <tex>a</tex> в точности в одном элементе.
<tex>\forall b (b \in \times a \leftrightarrow (\forall y (y \in a \rightarrow \exists ! x (x \in y \& x \in b))))</tex>
}}
{{Аксиома
|about=Аксиома выбора
|axiom=
Прямое произведение непустого дизъюнктного множества, не содержащего пустых элементов, непусто.
Формально: упражнение.
}}
{{Аксиома
|about=Аксиома бесконечности
|axiom=
Существует множество N, такое, что:<br>
<tex>\emptyset \in N \& \forall x(x \in N \rightarrow x\cup\{x\} \in N)</tex>
}}
{{Аксиома
|about=Аксиома фундирования
|axiom=
В каждом непустом множестве найдется элемент, не пересекающийся с исходным множеством.<br>
<tex>\forall x (x = \emptyset \vee \exists y (y \in x \& y \cap x = \emptyset))</tex>
}}
Аксиома фундирования исключает множества, которые могут принадлежать
сами себе (возможно, через цепочку принадлежностей):
<tex>X \in Y \in Z \in X</tex>
{{Аксиома
|about=Аксиома подстановки
|axiom=
Если задана некоторая функция f, представимая в исчислении предикатов
(то есть, есть предикат A, что f(x) = y тогда и только тогда,
когда <tex>A(x,y) \& \exists ! z A(x,z)</tex>)
то для любого множества Y существует множество f(Y) — образ
множества Y при отображении f.
}}
Ясно, что данная аксиома перекрывает аксиому выделения.
Наличие аксиомы подстановки отличает аксиоматику Цермело-Френкеля от
аксиоматики Цермело.
{{Определение
|definition=
Упорядоченной парой двух множеств <tex>a</tex> и <tex>b</tex> назовем множество
<tex>\{a,\{a,b\}\}</tex>, еще будем записывать его так: <tex>\langle{}a,b\rangle</tex>
}}
{{Лемма
|statement=
Упорядоченная пара существует для любых множеств, также
<tex>\langle{}a,b\rangle = \langle{}c,d\rangle</tex> тогда и только тогда,
когда <tex>a = b</tex> и <tex>c = d</tex>.
}}
{{Определение
|definition=
Бинарным отношением на множестве <tex>X</tex> назовем подмножество множества
всех упорядоченных пар элементов из <tex>X</tex>.
}}
На бинарных отношениях естественным образом вводятся отношения
рефлексивности, симметричтности и транзитивности.
{{Определение
|definition=
Отношение <tex>R</tex> на множестве <tex>S</tex> упорядочивает <tex>X</tex>, если это отношение
транзитивно и оно образует линейный порядок (строгое неравенство).
Отношение вполне упорядочивает <tex>S</tex>, если к тому же для любого
непустого подмножества <tex>S</tex> выполнено
<tex>\exists x (x \in B \& \forall y (y \in B \rightarrow \neg y < x))</tex>.
}}
Также можно ввести понятие максимума, минимума, верхней грани, супремума.
{{Определение
|definition=
Множество <tex>x</tex> — транзитивное, если <tex>z \in y, y \in x \rightarrow z \in x</tex>.
}}
{{Определение
|definition=
Ординал (порядковое число) — транзитивное, вполне упорядоченное с
помощью <tex>\in</tex> множество.
}}
Рассмотрим ординалы подробнее. Для начала рассмотрим ''конечные'' ординалы:
<tex>0 := \emptyset</tex>; <tex>1 := \{\emptyset\}</tex>; <tex>2 := 1 \cup \{1\}</tex> и т.п.
Существование этих ординалов легко доказать.
Помимо конечных, бывают бесконечные ординалы. Например, таковым является
множество <tex>N</tex> из аксиомы бесконечности. Заметим, что <tex>N \cup \{N\}</tex> — это
новый ординал, не равный исходному.
{{Определение
|definition=
Ординал <tex>x</tex> называется предельным, если
<tex>\neg x = \emptyset \& \neg \exists y (y \cup \{y\} = x)</tex>.
}}
{{Определение
|definition=
Ординал <tex>x</tex> называется натуральным числом,
если любой <tex>y</tex>, меньший <tex>x</tex> — это либо <tex>0</tex>, либо про него
справедливо, что <tex>\exists z (z \cup \{z\} = y)</tex>.
}}
Минимальный предельный ординал мы обозначим <tex>\omega</tex>. Ясно, что любое
натуральное число меньше, чем <tex>\omega</tex>.
Операцию <tex>x \cup \{x\}</tex> можно выбрать за операцию прибавления 1.
Для ординалов можно определить арифметические операции <tex>(+)</tex>, <tex>(\cdot)<tex>.
Получится некоторое обобщение натуральных чисел со странными свойствами.
Скажем, будет справедливо <tex>1 + \omega = \omega</tex>.
Ординалы становятся важными, например, при доказательстве утверждений с помощью
трансфинитной индукции: пусть есть некоторое утверждение <tex>P(x)</tex>,
определенное на ординалах. Пусть мы можем показать, что из того, что
<tex>P(y)</tex> справедливо на всех ординалах <tex>y < z</tex>, следует, что <tex>P(z)</tex> тоже справедливо.
Тогда <tex>P(x)</tex> верно для любого ординала. Трансфинитная индукция есть обобщение
обычной индукции. Например, с ее помощью доказана непротиворечивость
формальной арифметики.
{{Определение
|definition=
Назовем множества <tex>X</tex> и <tex>Y</tex> равномощными, если найдется биективное
отображение <tex>X</tex> на <tex>Y</tex>. Будем записывать это как <tex>|X| = |Y|</tex>.
Будем говорить, что множество <tex>X</tex> имеет мощность не превышающую <tex>Y</tex>,
если найдется инъективное отображение <tex>X</tex> в <tex>Y</tex>. Будем записывать
это как <tex>|X| \le |Y|</tex>. Будем записывать <tex>|X| < |Y|</tex>, если известно,
что <tex>|X| \le |Y|</tex>, но неверно, что <tex>|X| = |Y|</tex>.
}}
{{Определение
|definition=
Кардинальное число — такой ординал <tex>x</tex>, что <tex>y < x \leftrightarrow |y| < |x|</tex>.
}}
Все натуральные числа являются кардинальными. Также, например <tex>\omega</tex> — кардинальное
число (еще оно обозначается как <tex>\aleph_0</tex>, если речь идет о мощности множеств).
<tex>2^\omega</tex> — кардинальное число <tex>\aleph_1</tex>, соответствует мощности континуум.
Есть ли какое-нибудь кардинальное число между <tex>\aleph_0</tex> и <tex>\aleph_1</tex>?
Континуум-гипотеза (что никаких других кардинальных чисел между ними нет) была высказана
довольно давно, и длительное время была одной из главных проблем в теории множеств.
Сначала Геделем было показано, что континуум-гипотеза не
противоречит ZF. Утверждение о том, что и отрицание континуум-гипотезы не
противоречит ZF, было доказано через 30 лет Коэном.
