Теория множеств — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 6 участников)
Строка 1: Строка 1:
[[Лекция 9 | <<]][[Математическая_логика | >> На главную ]]
+
[[1я и 2я теоремы Геделя о неполноте арифметики | <<]][[Математическая_логика | >> На главную ]]
  
[[Категория: В разработке]]
+
[[Категория: Математическая логика]]
 +
 
 +
Теория множеств строится поверх исчисления предикатов подобно формальной арифметике.
 +
Мы добавим к исчислению предикатов один новый двуместный предикат — отношение
 +
принадлежности <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 \in p \leftrightarrow y \subseteq 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) &mdash; образ
 +
множества 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=
 +
Кардинальное число &mdash; такой ординал <tex>x</tex>, что <tex>y < x \leftrightarrow |y| < |x|</tex>.
 +
}}
 +
 
 +
Все натуральные числа являются кардинальными. Также, например <tex>\omega</tex> &mdash; кардинальное
 +
число (еще оно обозначается как <tex>\aleph_0</tex>, если речь идет о мощности множеств).
 +
<tex>2^\omega</tex> &mdash; кардинальное число <tex>\aleph_1</tex>, соответствует мощности континуум.
 +
 
 +
Есть ли какое-нибудь кардинальное число между <tex>\aleph_0</tex> и <tex>\aleph_1</tex>?
 +
Континуум-гипотеза (что никаких других кардинальных чисел между ними нет) была высказана
 +
довольно давно, и длительное время была одной из главных проблем в теории множеств.
 +
Сначала Геделем было показано, что континуум-гипотеза не
 +
противоречит ZF. Утверждение о том, что и отрицание континуум-гипотезы не
 +
противоречит ZF, было доказано через 30 лет Коэном.

Текущая версия на 19:31, 4 сентября 2022

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

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