Изменения

[[Лекция 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 лет Коэном.