Аксиомы ZFC

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

Одной из таких систем аксиом является теория Цермело-Френкеля (ZF).

К этой системе аксиом часто добавляют аксиому выбора, и называют системой Цермело-Френкеля с аксиомой выбора (ZFC).

Ниже приведен список аксиом ZFC с кратким описанием и формальной записью на языке логики первого порядка.

Критерий равенства множеств

1. Аксиома объёмности. Два множества $a$ и $b$ равны тогда и только тогда, когда они состоят из одних и тех же элементов.

[math]\displaystyle{ \forall a\forall b ((a=b)\Leftrightarrow \forall c(c\in a \Leftrightarrow c\in b)) }[/math]

Аксиомы о существовании множеств

2. Аксиома пустого множества. Существует множество $e$ без единого элемента. Это множество обычно обозначается $\{\}$ или $\varnothing$.

[math]\displaystyle{ \exists e\forall a(a\notin e) }[/math]

3. Аксиома бесконечности. Множество называется индуктивным, если оно

а) содержит пустое множество и

б) содержит последователь (то есть элемент $a\cup\{a\}$) каждого своего элемента.

Аксиома бесконечности утверждает, что индуктивные множества существуют.

[math]\displaystyle{ \exists \omega ((\varnothing \in \omega) \wedge \forall x (x\in \omega \Rightarrow (x\cup\{x\})\in \omega)) }[/math]

То есть существует по крайней мере одно бесконечное множество:

[math]\displaystyle{ \{\varnothing, \varnothing \cup \{\varnothing\}, \varnothing \cup \{\varnothing\}\cup \{\varnothing \cup \{\varnothing\}\}, ... \} }[/math]

Аксиомы об образовании множеств

4. Аксиома пары. Для любых множеств $a$ и $b$ существует множество $c$ такое, что $a$ и $b$ являются его единственными элементами. Множество $c$ обозначается $\{a,b\}$ и называется неупорядоченной парой $a$ и $b$. Если $a = b$, то $c$ состоит из одного элемента.

[math]\displaystyle{ \forall a\forall b\exists c\forall d ((d\in c) \Leftrightarrow (d=a \vee d=b)). }[/math]

5. Аксиома множества подмножеств. Для любого множества $a$ существует множество $b$, состоящее из тех и только тех элементов, которые являются подмножествами множества $a$. Множество подмножеств множества $a$ обозначается $\mathcal{P}(a)$ или $2^a$.

[math]\displaystyle{ \forall a\exists b\forall c ((c\in b)\Leftrightarrow \forall d(d\in c\Rightarrow d\in a)). }[/math]

Если ввести отношение подмножества $\subseteq$, то эту формулу можно упростить.

[math]\displaystyle{ \forall a\exists b\forall c ((c\in b)\Leftrightarrow (c\subseteq a)). }[/math]

6. Аксиома объединения. Для любого семейства $a$ множеств существует множество $b=\cup a$, называемое объединением множества $a$, состоящее из тех и только тех элементов, которые содержатся в элементах множества $a$.

[math]\displaystyle{ \forall a\exists b \forall c ((c\in b)\Leftrightarrow\exists d(d\in a \wedge c\in d)). }[/math]

7. Схема выделения. Любому множеству $a$ и свойству $\varphi$ отвечает множество $b$, элементами которого являются те и только те элементы $a$, которые обладают свойством $\varphi$. Схема выделения содержит счётное количество аксиом, так как каждая формула $\varphi(x)$ логики первого порядка порождает аксиому.

[math]\displaystyle{ \forall a\exists b\forall c ((c\in b)\Leftrightarrow (c\in a \wedge \varphi(c))). }[/math]

8. Схема подстановки. Пусть $\varphi(x,y)$ — такая формула, что при любом $x_0$ из множества $X$ существует, и притом единственный, объект $y_0$ такой, что выражение $\varphi(x_0,y_0)$ истинно. Тогда объекты $c$, для каждого из которых существует $d$ из $X$ такой, что $\varphi(d,c)$ истинно, образуют множество. Схема подстановки содержит счётное количество аксиом, так как каждая подходящая формула $\varphi(x,y)$ порождает аксиому.

[math]\displaystyle{ \forall x\exists ! y(\varphi(x,y))\Rightarrow \forall a\exists b\forall c((c\in b)\Leftrightarrow \exists d(d\in a\wedge \varphi(d,c))). }[/math]

Аксиомы об упорядоченности множеств

9. Аксиома основания. Каждое непустое множество $s$ содержит элемент $a$ такой, что $s\cap a=\varnothing$. Другими словами, в любом семействе множеств $s$ есть, по меньшей мере, одно множество $a$, каждый элемент которого не принадлежит данному семейству $s$.

[math]\displaystyle{ \forall s (\exists x ( x\in s) \Rightarrow \exists a(a\in s \wedge \neg \exists z(z\in a \wedge z\in s) }[/math]

10. Аксиома выбора. Для любого семейства $a$ попарно непересекающихся непустых множеств существует множество $d$ (делегация) такое, что, каково бы ни было множество $b$ данного семейства, множество $b\cap d$ состоит из одного элемента.

[math]\displaystyle{ \forall a(a\neq \varnothing \wedge \forall b(b\in a\Rightarrow b\neq \varnothing) \wedge \forall b_1\forall b_2(b_1\neq b_2 \wedge \{b_1,b_2\}\subseteq a \Rightarrow b_1\cap b_2=\varnothing) \Rightarrow \exists d\forall b (b\in a \Rightarrow \exists c(b\cap d=\{c\}))) }[/math]

Рис. 1. Из каждого множества [math]\displaystyle{ b_i }[/math] попарно непересекающегося семейства выбирается по одному элементу [math]\displaystyle{ c_i }[/math]; вместе они образуют делегацию [math]\displaystyle{ d }[/math], пересекающую каждое [math]\displaystyle{ b_i }[/math] ровно по одному элементу.

Конспект: Дискретная математика