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

X & v
X))).
Аксиома замещения утверждает, что если класс Х однозначен, то класс вторых компонент тех пар из X, первые компоненты которых принадлежать, является множеством (эквивалентное утверждение: M(R (x 1X))) Из этой аксиомы следует, что если Х есть функция, то область значений результата ограничения Х посредством всякой области, являющейся множеством, также есть множество.
Следующая аксиома обеспечивает существование бесконечных множеств.
А к с и о м а I. (Аксиома бесконечности.)
x
(0
x &
u
(u
x
u
{u}
x)).
Аксиома
бесконечности
утверждает,
что существует
такое множество
х, что
0
x,
и если и
x,
то и
{и}
также принадлежит
х. Для
такого множества
х, очевидно,
{0}
x,
{0, {0}}
x,
{0, {0}, {0, {0}}}
x
и т. д. Если
теперь положим
1 = {0}, 2 = {0, 1}, … , n
= {0, 1, … , n
– 1}, то для любого
целого п
≥ 0 будет
выполнено п
х, и при
этом 0 ≠ 1, 0 ≠ 2, 1 ≠ 2, 0 ≠ 3,
1 ≠ ≠ 3, 2 ≠ 3, …
Список аксиом теории NBG завершен. Видно, что NBG имеет лишь конечное число аксиом, а именно: аксиому Т (объемности), аксиому Р (пары), аксиому N (пустого множества), аксиому S (выделения), аксиому U (объединения), аксиому W (множества всех подмножеств), аксиому R (замещения), аксиому I (бесконечности) и семь аксиом существования классов В1—В7.
Убедимся
теперь в том,
что парадокс
Рассела невыводим
в NBG.
Пусть Y
=
(x
x)
,т. е.
х
(х
Y
х
х). (Такой
класс Y
существует,
в силу теоремы
о существовании
классов (предложение
4), так как формула
х
х предикативна.)
В первоначальной,
т. е. не сокращенной,
символике эта
последняя
формула записывается
так:
X
(M(X)
(X
Y
X
X)).
Допустим
M(Y).
Тогда Y
Y
Y
Y,
что, в силу
тавтологии
(A

A)
A
& &
A,
влечет Y
Y
Y
Y.
Отсюда по теореме
дедукции получаем
M(Y)
(Y
Y
Y
Y),
а затем, в силу
тавтологии
(B
(A
&
A))
B
, получаем
и
М(Y).
Таким образом,
рассуждения,
с помощью которых
обычно выводится
парадокс Рассела,
в теории NBG
приводят всего
лишь к тому
результату,
что Y
есть собственный
класс, т. е. не
множество.
Здесь имеем
дело с типичным
для теории NBG
способом избавления
от обычных
парадоксов
(например, парадоксов
Кантора и
Бурали-Форти).
Определения
X
Irr
Y
означает
y
(y
Y

X)
& Rel
(X).
(X есть иррефлексивное отношение на Y.)
X
Tr
Y
означает
Rel
(X)
&
u
v
w
(u
Y
& v
Y
& w
Y
&
&

X
&
X
& X


X).
(X есть транзитивное отношение на Y.)
X Part Y означает (X Irr Y) & (X Tr Y).
(X частично упорядочивает Y.)
X
Con
Y
означает
Rel(X)
&
u
v
(u
Y
& v
Y
& u
≠ v



X
X).
X Tot Y означает (X Irr Y) & (X Tr Y) & (X Con Y).
(X упорядочивает Y.)
X
We
Y
служит
обозначением
для Rel(X)
& (X
Irr
Y)
&
Z
(Z
Y
&
& Z
≠ 0

y
(y
Z
&
v
(v
Z
& v
≠ y

X
&
&
X))).
(X вполне упорядочивает Y, т. е. отношение Х иррефлексивно на Y, и всякий непустой подкласс класса Y имеет наименьший в смысле отношения Х элемент.)
§2. Аксиома выбора. Лемма Цорна.
Аксиома выбора является одним из самых знаменитых и наиболее оспариваемых утверждений теории множеств.
Следующие формулы эквивалентны:
А к с и о м а
в ы б о р а (АС): Для
любого множества
х существует
функция f
такая, что для
всякого непустого
подмножества
у множества
х f‘
y
y
(такая функция
называется
в ы б и р а ю щ е
й ф у н к ц и е й
для х).
М у л ь т и п л и к а т и в н а я а к с и о м а (Mult): Для любого множества х непустых и попарно непересекающихся множеств, существует множество у (называемое в ы б и р а ю щ и м м н о ж е с т в о м для х), которое содержит в точности по одному элементу из каждого множества, являющегося элементом х.
u
(u
x
u ≠ 0
&
v
(v
x & v ≠ u
v
∩ u = 0))

y
u
(u
x

1w
(w
u ∩ y)).
П р и н ц и п
в п о л н е у п о
р я д о ч е н и я
(W.
O.):
Всякое
множество
может быть
вполне упорядочено.
x
y
(y We x).
Т р и х о т о
м и я (Trich):
x
y
(x
y
y
x).
Л е м м а Ц о р н а (Zorn): Если в частично упорядоченном множестве х всякая цепь (т. е. всякое упорядоченное подмножество) имеет верхнюю грань, то в х существует максимальный элемент.
x
y
((y Part x) &
u
(u
x & y Tot u

v
(v
x &
w
(w
u
w
=
= v
y)))
v
(v
x
&
w
(w
x

y))).
Доказательство.
1.
(W.
O.)
Trich.
Пусть даны
множества х
и у.
Согласно (W.
O.),
х и у
могут быть
вполне упорядочены.
Поэтому существуют
такие порядковые
числа α и β, что
х
α и y
β. Но так
как α
β или β
α, то либо
x
y,
либо y
x.
2.
Trich
(W.
O.).
Пусть дано
множество х.
Согласно теореме
Хартогса, существует
такое порядковое
число α, которое
не равномощно
никакому подмножеству
множества х.
Тогда, в силу
Trich,
х равномощно
некоторому
подмножеству
у порядкового
числа α, и вполне
упорядочение
Еу
множества у
порождает
некоторое
вполне упорядочение
множества х.
3.
(W.
O.)
Mult.
Пусть х
есть некоторое
множество
непустых, попарно
непересекающихся
множеств. Согласно
(W.
O.),
существует
отношение R,
вполне упорядочивающее
множество
(х).
Следовательно,
существует
такая определенная
на х
функция f,
что f‘u
для любого
и
х есть
наименьший
относительно
R
элемент и.
(Заметим, что
и
(х).)
4.
Mult
AC.
Для любого
множества х
существует
функция g
такая, что
если и
есть непустое
подмножество
х, то
g‘и
= u
{и}.
Пусть х1
—область
значении функции
g.
Легко видеть,
что х1
является
множеством
непустых попарно
непересекающихся
множеств. На
основании
Mult,
для х1
существует
выбирающее
множество у.
Отсюда, если
0 ≠ u
и u
х, то
и
{и}
х1
и у
содержит и
притом единственный
элемент
из и
{и}.
Функция f‘
u
= v
является
искомой выбирающей
функцией для
х.
5.
АС
Zorn.
Пусть у
частично
упорядочивает
непустое множество
х таким
образом, что
всякая y-цепь
в х имеет
в х
верхнюю грань.
На основании
АС, для х
существует
выбирающая
функция f.
Рассмотрим
произвольный
элемент b
множества х,
и по
трансфинитной
индукции определим
функцию F
такую, чтобы
выполнялось
F‘0
= b
и F‘α
= f‘u
для любого α,
где u
есть множество
всех таких
верхних граней
v
множества F‘‘
α относительно
упорядочения
у, что
v
х и
v
F‘‘
α. Пусть
β есть наименьшее
порядковое
число, которому
соответствует
пустое множество
верхних граней
v
множества
F‘‘
β относительно
упорядочения
v,
принадлежащих
x
и не принадлежащих
F‘‘
β. (Порядковые
числа, обладающие
таким свойством,
существуют;
в противном
случае функция
F
была бы взаимно
однозначной
с областью
определения
Оп и
с некоторым
подмножеством
множества
х в
качестве области
значений, откуда
по аксиоме
замещения R
следовало бы,
что Оп
есть множество.)
Пусть g
= β
1 F.
Функция g
взаимно однозначна
и что если α <0
γ <0 β,
то
g‘α,
g‘γ
y.
Поэтому множество
g‘‘
β
является y-цепью
в x.
Согласно условию,
и x
существует
верхняя грань
w
множества g‘‘
β.
Так как множество
верхних граней
множества F‘‘
β (= g‘‘
β),
не содержащихся
в g‘‘
β,
пусто, то w
g‘‘
β,
и, следовательно,
w
является
единственной
верхней гранью
множества g‘‘
β
(ибо всякое
множество может
содержать
в себе не более
одной своей
верхней грани).
Отсюда следует,
что w
есть максимальный
относительно
упорядочения
y
элемент множества
х. (Действительно,
если

y
и z
х,
то z
должно быть
верхней гранью
g‘‘
β,
что невозможно.)
6.
Zorn
(W.
O.).
Пусть z
есть множество,
а X
есть класс всех
взаимно однозначных
функций f
таких, что D(f)
Оп
и R(f)
z.
Из теоремы
Хартогса следует,
что X
есть множество.
Очевидно также,
что 0
X. Отношение
частично
упорядочивает
X.
Каковы бы ни
были две функции,
принадлежащие
одной