Решающая идея принадлежит Эрнсту Цермело. Он предложил принять в качестве аксиом теории множеств только те варианты аксиом свертывания, которые реально используются в математике. К 1908 г. Э.Цермело уже завершил "переучет" средств, которые используются в математике для образования множеств, и опубликовал свой вариант аксиом теории множеств. Оставим пока в стороне вопрос о том, какие конкретные аксиомы содержала эта система. Понятно, что аксиомы Z2{~(y in y)}, приводящей к парадоксу Рассела, в ней не было, поскольку рассуждения такого рода в математической практике не встречаются.
Но как же быть в случаях, когда с помощью некоторой формулы F(y) из всех множеств y выделяются те, которые "обладают свойством F", однако, предположив, что все выделенные y, собранные вместе, образуют множество, приходится констатировать противоречие? Так, {y|~(y in y)} является, по-видимому, некоторым "собранием" множеств (в частности, пустое множество 0 является элементом этого собрания: ~(0 in 0)). Однако если объявить такое собрание, множеством и обозначить его через x, то получится парадокс Рассела: x in x приводит к ~(x in x) и наоборот. Как же быть? Решение, достойное царя Соломона: выведенное нами противоречие будем считать доказательством (от противного), что собрание Рассела... не является множеством!
Действуя в таком духе, мы должны ввести понятие "собраний" множеств, более широкое, чем понятие множества. Этим более широким понятием является понятие класса, которое определяется следующим образом. Пусть F(y,z1, ..., zn ) - формула на языке теории множеств (z1, ..., zn могут отсутствовать). Тогда будем говорить, что при фиксированных z1, ..., zn формула F определяет nкласс
A = {y | F(y, z1, ..., zn )}.
Ясно, что, изменяя параметры z1, ..., zn, получим, вообще говоря, другой класс. Например, класс {y | ~(y=z1)} состоит из всех множеств, исключая z1, и поэтому зависит от того, как зафиксировано z1. С другой стороны, класс
V = {y | y=y}
состоит из всех вообще множеств и ни от каких параметров не зависит.
Всякое множество является классом: множество x совпадает с классом {y | y in x}. Однако не всякий класс можно отнести к множествам. Например, класс Рассела
R = {y | ~(y in y)}
не совпадает ни с одним множеством (если допустить, что R совпадает с x, то y in x равносильно ~(y in y) и при y=x получается противоречие). Такие классы принято называть собственными классами. То, что раньше считалось парадоксами теории множеств, теперь будет считаться доказательствами "собственности" соответствующих классов.
Классы будем обозначать прописными буквами: A, B, C, ... (в отличие от множеств, обозначаемых строчными буквами: a, b, c, ... ). Такие обозначения должны лишний раз напомнить, что записи вроде
y in A, A=B, A<=B, A^B, AUB, A-B
не относятся непосредственно к языку теории множеств (в котором нет "прописных переменных"), а являются всего-навсего более наглядной для нашего восприятия записью следующих формул (формула F определяет класс A, формула G - класс B):
F(y), (Ay)(F(y)<->G(y)), (Ay)(F(y)->G(y)), F(y)&G(y), F(y)VG(y), F(y)&~G(y).
А теперь мы должны, следуя Э.Цермело, сформулировать те варианты схемы свертывания, которые реально используются в математике. Наше изложение отличается от изложения Э.Цермело некоторыми усовершенствованиями, предложенными позднее.
Самый, по-видимому, распространенный способ образования новых множеств - выделение с помощью явно сформулированного условия части элементов уже известного множества. Так определяются, например, различные подмножества натуральных чисел - четные числа, простые числа и т.д. В общем же случае имеем следующую картину: условие F(y), представленное формулой из языка теории множеств (эта формула может содержать кроме y еще и параметры z1, ..., zn), выделяет среди элементов множества x те, которые удовлетворяют F. Эти выделенные элементы образуют подмножество множества х, обозначенное через z.
Чтобы узаконить такой способ рассуждения, вводится следующая схема аксиом выделения: если F(y, z1, ..., zn ) - любая формула со свободными переменными y, z1, ..., zn, не содержащая переменных x, z, то следующая формула объявляется аксиомой:
(Az1 ... Azn)(Ez)(Ay)(y in z <-> y in x & F(y, z1, ..., zn)). (Z21{F})
Ясно, что это частный случай схемы свертывания, а именно Z2{y in x & F(y, z1, ..., zn)}. Особенно наглядно аксиомы выделения формулируются в терминах классов: если формула F определяет класс A, то аксиома Z21{F} утверждает, что пересечение A^x (класса A и множества x) является множеством: A^x = z.
Теперь можно доказать существование пустого множества, т.е. формулу (Ex)(Ay)~(y in x). В самом деле, мы уже знаем, что какие-то множества существуют (это следствие аксиом логики). Пусть x0 - одно из таких множеств. Тогда с помощью невозможного условия ~(y=y) и аксиомы Z21{~(y=y)} получаем множество x со свойством
(Ay)(y in x <-> y in x0 & ~(y=y)),
т.е. (Ay)~(y in x), что и требовалось.
С другой стороны, аксиома Z1 гарантирует, что существует только одно пустое множество: если множества x1, x2 оба пусты, т.е. (Ay)~(y in x1) и (Ay)~(y in x2), то (Ay)(y in x1 <-> y in x2), а отсюда согласно Z1 вытекает, что x1 = x2.
Для удобства записи хотелось бы ввести для пустого множества особое обозначение, например 0. Но, к сожалению, в языке теории множеств нет констант. Если мы введем одну такую константу, это не решит проблемы, поскольку затем захочется ввести еще одну константу и т.д. без конца. Оказывается, однако, что можно обойтись вообще без констант, не ограничивая возможности рассуждений.
Если мы хотим использовать в своих рассуждениях константу 0, не входящую в язык теории множеств, мы должны указать общий метод, позволяющий переводить наши утверждения, содержащие 0, в "чистую форму" языка теории множеств. И это, оказывается, совсем просто: если мы утверждаем, например, что множество 0 обладает свойством, выраженным в формуле F(x), т.е. утверждаем, что имеет место F(0), это можно выразить и с помощью формулы, не содержащей символ 0:
(Ax)((Ay)~(y in x) -> F(x)),
т.е. если x - пустое множество, то F(x). Так как существование и единственность пустого множества мы уже доказали, никаких неточностей здесь не возникает. Допустимо, таким образом, использовать в рассуждениях символ 0 - его всегда можно исключить, не изменяя смысл рассуждений (но усложняя их запись).
Аналогично можно поступать и в других случаях, когда удается доказать существование и единственность множества, удовлетворяющего некоторой формуле tau(x), т.е. удается доказать формулы
(Ex)tau(x), (Ax1Ax2)(tau(x1)&tau(x2) -> x1 = x2).
Мы можем в таком случае ввести особое обозначение t для этого единственного объекта, и пользоваться им в своих рассуждениях. При этом всякое утверждение F(t) ("t обладает свойством F") можно сформулировать и без t: (Ax)(tau(x)->F(x)). Вполне допустимо, что формула tau(x) содержит не только свободную переменную x, но и параметры, скажем, z1, z2, т.е. формула имеет вид tau(x, z1, z2). В этом случае, если доказано, что каждой паре z1, z2 соответствует единственное x, формула tau определяет по существу некоторую операцию над множествами. Если обозначить эту операцию через %, то x=z1 % z2 будет более наглядной записью формулы tau(x, z1, z2). Этим обозначением можно свободно пользоваться, поскольку утверждение, что имеет место, например, F(z1%z2), можно переписать без символа "%":
(Ax)(tau(x,z1, z2)->F(x)).
Возможностью введения и исключения новых констант и операций широко пользуются в полуформальных рассуждениях теории множеств. Полная формализация означала бы исключение всех вспомогательных символов.
Упражнение 2.4. а) Докажите, что для любых двух множеств x,y их пересечение x^y и разность x-y также являются множествами. Обоснуйте (описанным выше способом) допустимость использования символов операций "^" и "-".
б) Докажите, что если A<=B и A - собственный класс, то и B - собственный класс.
Утверждение б) проливает свет на причины, почему некоторые классы являются собственными. Это их "величина" - если класс охватывает слишком большое разнообразие элементов-множеств, то его самого уже нельзя считать множеством. В частности, нельзя считать множеством класс всех множеств:
V={y | y=y},
поскольку R<=V, где R={y | ~(y in y)} - класс Рассела.
К сожалению, аксиомы выделения позволяют получать только "меньшие" множества из "больших". В итоге оказывается, что сами по себе они гарантируют существование только наименьшего множества - пустого. Поэтому придется ввести также увеличивающие аксиомы.
Простейшей из них является аксиома пары. Если x1, x2 - множества, то можно образовать новое множество, обозначаемое обычно через {x1, x2}. Чтобы узаконить такой способ рассуждения, аксиомой объявляется следующая формула:
(Ax1Ax2)(Ez)(Ay)(y in z <-> y=x1 V y=x2). (Z22)
Ясно, что это - частный случай схемы свертывания, а именно Z2{y=x1 V y=x2}.
Очень важным элементом языка математики является понятие упорядоченной пары. Такую пару, состоящую из x1 и x2, будем обозначать через (x1, x2), чтобы подчеркнуть отличие от неупорядоченной пары {x1, x2}. Но каким образом ввести (x1, x2) в нашу теорию множеств? Ведь у нас "все есть множество"! Как добиться нужного порядка x1 и x2? В 1921 г. К.Куратовский предложил следующее остроумное определение упорядоченной пары через неупорядоченную:
(x1, x2) = {{x1},{x1, x2}}.
Интуитивно ясно, что x1 играет здесь отличную роль по сравнению с x2 , т.е. между ними установлен некоторый порядок.
Упражнение 2.5. Докажите корректность определения К.Куратовского:
~(x1=y1 & x2=y2) -> (x1, x2)<>(y1, y2).
Отсюда, в частности, вытекает, что x1<> x2 -> (x1, x2)<>(x2, x1).
Теперь мы можем ввести обычное для математики понятие декартова произведения:
AxB = {(u,v) | u in A & v in B},
или, более точно:
AxB = {z | (EuEv)(u in A & v in B & z=(u,v)}.
Хотелось бы полагать, что декартово произведение x x y двух множеств x, y окажется множеством. Этот вопрос будет решен положительно после принятия аксиомы множества подмножеств (см. дальше).
Теперь мы можем ввести также понятие отношения. В самом общем случае отношением следует называть произвольный класс, состоящий только из упорядоченных пар. Т.е. класс Q={y | F(y)} будет называться отношением, если
(Ay)(y in Q -> (EuEv)y=(u,v)).
Если через F(u,v) обозначить формулу (Ey)(y=(u,v)&F(y)), то можно писать также: Q={(u,v) | F (u,v)}.
Несколько позднее мы докажем, что некоторые отношения являются собственными классами, например:
E = {(u,v) | u=v}, C = {(u,v) | u in v)}.
Наша следующая аксиома должна обеспечить возможность произвольных объединений множеств. Кроме широко используемых конечных объединений типа xUy в математике нужны объединения бесконечного числа множеств. Самый же общий случай - объединение произвольного "множества множеств":
Ux={y | (Ez)(y in z & z in x)}.
Таким образом, класс Ux получается, если объединить все элементы множества x, т.е. собрать вместе все "элементы элементов" x. В частности, U{x,y} - это обычное xUy. Например, U{0, {0}}={0}.
Аксиома объединения (или аксиома суммы) объявляет класс Uх множеством:
(Ax)(Eu)(Ay)(y in u <-> (Ez)(z in x & y in z)) (Z23)
Это опять частный случай схемы свертывания, а именно Z2{(Ez)(z in x & y in z)}.
Упражнение 2.6. а) Докажите, что если A - собственный класс, а x - множество, то A-x является собственным классом.
б) Покажите, что с помощью аксиом выделения, пары и объединения можно доказать существование любого конкретного конечного множества, построенного на базе 0, например {0, {0, {0}}, {0, {0, {0}}}}.
С помощью аксиомы объединения можно доказать, что если A, B - непустые классы и декартово произведение AxB - множество, то A, B также являются множествами. В самом деле, возьмем какой- нибудь элемент v0 in B, тогда для каждого u in A:
(u,v0) in AxB,
{{u},{u,v0}} in AxB,
{u} in U(AxB),
u in UU(AxB).
Таким образом, A <= UU(AxB). Поскольку AxB - множество, то по аксиоме объединения, UU(AxB) - множество, т.е. класс A содержится в множестве, поэтому сам является множеством. Аналогично доказывается, что множеством является B.
Упражнение 2.7. Покажите, что отношения E, C, определенные выше, являются собственными классами.
Следующий способ свертывания вошел в математику в 70-х гг. прошлого века - вместе с точными определениями системы действительных чисел на основе системы рациональных чисел. Будь то определение посредством "сходящихся в себе" последовательностей рациональных чисел (Г.Кантор), "сечений" множества рациональных чисел (Р.Дедекинд) или посредством бесконечных двоичных дробей, говоря о "произвольном" действительном числе, приходится привлекать понятие "произвольного" множества натуральных чисел. Лучше всего это видно на примере двоичных дробей: всякую бесконечную дробь, например
0,1010110011000010111...,
можно истолковать как характеристическую функцию некоторого множества натуральных чисел, в данном случае
{1,3,5,6,9,10,15,17,18,19,... }.
Обратное также верно. Таким образом, исследуя "произвольные" действительные числа, мы тем самым вводим в работу систему всех множеств натуральных чисел. И нам кажется, мы настолько хорошо знакомы с "устройством" этой системы, что можем считать его множеством.
Чтобы сделать эту новую операцию законной, нужна специальная аксиома свертывания. Через x<=y будем обозначать формулу (Az)(z in x -> z in y), т.е. формулу, утверждающую, что x есть подмножество y.
Аксиома множества подмножеств (ее называют также аксиомой степени):
(Ax)(Ez)(Ay)(y in z <-> y<=x). (Z24)
Это частный случай схемы свертывания, а именно Z2{y<=x}. В терминах классов смысл аксиомы Z24 сводится к следующему. Для всякого множества x определяется класс
P(x)={y | y<=x}
всех его подмножеств. Аксиома Z24 утверждает, что если x - множество, то P(x) - также множество.
Из аксиомы множества подмножеств вытекает, что множеством является декартово произведение любых двух множеств x и y:
x x y={(u,v) | u in x & v in y}.
В самом деле, если u in x и v in y, то {u} in P(x), {u, v} in P(xUy) и, следовательно, (u, v) = {u, {u, v}} in PP(xUy). Класс x x y содержится, таким образом, в множестве PP(xUy). Из соответствующей аксиомы выделения тогда вытекает, что сам этот класс также является множеством.
Отношение F={(u,v) | F(u,v)} называется функцией, если каждому u соответствует не более одного v:
(u, v1) in F & (u, v2) in F -> v1 = v2,
другими словами,
(AuAv1Av2)(F(u, v1) & F(u, v2) -> v1 = v2).
В этом случае будем записывать (u,v) in F в виде F(u)=v.
Каждой функции соответствуют область определения и область значений. Формально эти области можно определить и для произ- вольного отношения Q:
dom(Q)={u | (Ev)(u,v) in Q},
rng(Q)={v | (Eu)(u,v) in Q}
(domain, range). Если Q - класс, то, вообще говоря, dom(Q), rng(Q) также будут классами и необязательно - множествами. Например, для отношения E = {(u,v) | u=v} (оно является по существу тождественной функцией: E(u)=u) имеем dom(E)=rng(E)=V.
Упражнение 2.9. Докажите, что отношение Q является множеством, если и только если dom(Q) и rng(Q) - множества.
Функция, тождественно равная 0, т.е. O={(u,v) | v=0}, дает пример функции - собственного класса, область значений которой является множеством: rng(O)={0}. Ясно, что область определения такой функции должна быть собственным классом (и действительно: dom(O)=V). Но если известно, что F - функция, а dom(F) - множество, то может ли оказаться, что rng(F) является собственным классом? Кажется, этого не должно быть: если область определения функции является множеством, то и область значений должна быть множеством. Однако, чтобы сделать такой способ рассуждения законным, нужны специальные аксиомы, так называемая схема аксиом подстановки. Э.Цермело упустил эту схему в своей первоначальной системе аксиом 1908 г. То, что она необходима при доказательстве некоторых теорем "высшей" теории множеств, заметил лишь в 1922 г. А.Френкель.
Если F - функция и A - класс, то через F"A принято обозна- чать образ A при отображении посредством F:
F"A={v | (Eu)(u in A & F(u)=v)}.
Упражнение 2.10. Покажите, что если f - функция-множество, то для любого класса A образ f"A является множеством.
В частности, если f - функция-множество, то для любого множества a образ f"a также является множеством. Но если вместо f взять функцию-класс F? Будет ли тогда образ F"a множеством, если множеством является a? Если F является собственным классом, то в нашей теории множеств такую функцию нельзя рассматривать как вещь. В этом случае F - соответствие, заданное некоторой формулой
F={(u, v) | F(u, v)}.
Говоря, что F - функция, мы имеем в виду только то, что формула F(u, v) сопоставляет u не более одного v. Если мы возьмем элементы u множества a и подставим вместо каждого такого u соответствующее ему v, то во что превратится множество a? Разумеется, в другое множество. Такой способ рассуждений кажется естественным, однако он редко используется в математике (возможно, поэтому Э.Цермело и не обратил на него внимания). Обычно математические функции строятся сразу как некоторые множества пар (натуральных, действительных или комплексных чисел), а не как заданные формулами соответствия, которые нельзя считать множествами. В теории множеств, однако, такие соответствия встречаются, поэтому чтобы сделать указанный выше способ рассуждения законным, следуя А.Френкелю, принимаем схему аксиом подстановки:
F-функция -> (Aa)(Eb)F"a=b,
или, более точно, если формула F(u, v, z1, ..., zn) не содержит переменных v1, v2, x, y, a, b, то аксиомой Z25{F} объявляется следующая формула:
(AuAv1Av2)(F(u, v1, z1, ..., zn) & F(u, v2, z1, ..., zn) -> v1 = v2) ->
->(Aa)(Eb)(y in b <-> (Ex)(x in a & F(x ,y ,z1, ..., zn))).
Здесь мы опять имеем дело с частным случаем схемы свертывания, а именно с аксиомами Z2{(Ex)(x in a & F(x,y))}, однако применять эти аксиомы разрешается, только если доказано, что каждому x соответствует не более одного y такого, что F(x,y).
Упражнение 2.11. а) Покажите, что если A - собственный класс и a - множество, то невозможна одно-однозначная (инъективная) функция, отображающая A в a.
б) Покажите, что схема подстановки влечет схему выделения Z21.
в) Покажите, следуя Я.Мыцельскому, что аксиому пары можно вывести из остальных аксиом (примените дважды Z24, а затем - Z25).
Сформулированные до сих пор аксиомы сами по себе способны доказать только существование конечных множеств, построенных на базе пустого множества 0, например {{0}, {0, {0}}, {{0}}, 0} (см. упражнение 2.6б). В самом деле, все эти аксиомы выполняются в области конечных множеств (проверьте). Следуя предложению Дж.фон Неймана, некоторые из этих множеств можно использовать в качестве натуральных чисел: 0 можно считать нулем, {0} - единицей, {0, {0}}={0, 1} - числом 2, {0, 1, 2} - числом 3 и т.д. Если множество cn объявлено числом n, то cn+1 = cn U{cn} объявляется числом n+1. Казалось бы, мы имеем теперь и множество всех натуральных чисел:
{0, 1, 2, 3,..., n, n+1,... }.
К сожалению, так как принятые до сих пор аксиомы свертывания выполняются в области конечных множеств, то с их помощью невозможно доказать существование множества, состоящего из всех натуральных чисел. Непросто определить (формулой) даже класс всех натуральных чисел. Ведь бесконечные дизъюнкции вроде
x=c0 V x=c1 V x=c2 V... Vx=cn V...
nнедопустимы в нашем языке теории множеств. По Дж.фон Нейману, понятие натурального числа в теории множеств определяется путем сочетания двух следующих свойств:
а) Транзитивности. Множество x называется транзитивным, если вместе с каждым своим элементом оно содержит также все элементы этого элемента:
(AuAv)(u in v & v in x -> u in x).
Легко проверить, что определенные выше натуральные числа являются транзитивными множествами.
б) Идеального порядка. Отношение "<" называется отношением порядка на множестве x, если
(Aa)(a in x -> ~(a<a)),
(AaAbAc)(a,b,c in x -> (a<b & b<c -> a<c)).
Будем говорить, что "<" идеально упорядочивает x, если всякое непустое подмножество х содержит как наименьший, так и наибольший элементы. Интуитивно ясно, что в последнем случае множество x должно быть конечным. Возможность идеального порядка можно принять даже за определение конечности множества.
Дж.фон Нейман предложил определить класс N всех натуральных чисел следующим образом:
N ={y | y транзитивно & y идеально упорядочено отношением принадлежности " in "}.
Упражнение 2.12. а) Покажите, что "стандартные" натуральные числа все являются элементами класса N, т.е. что cn in N для всех n. Заметьте, что это утверждение является схемой теорем, которую мы не умеем "свернуть" в одну общую теорему.
б) Докажите, что если x in N, x<>0 и y - наибольший элемент x, то
x-{y}in N, x - {y}in x, x -{y} = y.
Выведите отсюда, что N содержит только одно множество, содержащее ровно n элементов - cn.
в) (курсовая работа) Покажите, что в классе N выполняются аксиомы элементарной арифметики (т.е. теории EA из раздела 3.1). Ср. упражнение 2.13.
Если мы намерены считать, что натуральные числа образуют множество, то следует принять соответствующую аксиому свертывания Z2{y in N} или
(Ex)(Ay)(y in x <-> y in N). (Z26)
Так как аксиома Z26 обеспечивает существование бесконечных множеств, ее принято называть аксиомой бесконечности.
Замечание. Обычно аксиома бесконечности формулируется более просто, например
(Ex)(0 in x & (Ay)(y in x -> yU{y}in x)).
Здесь речь идет о множестве, содержащем все натуральные числа. Из этой аксиомы можно вывести Z26 (и наоборот).
Аксиома Z26 гарантирует существование только счетных множеств. Существование несчетных множеств вытекает (теперь, после принятия Z26) из аксиомы множества подмножеств Z24: если через w обозначить множество всех натуральных чисел, то множество P(w) будет несчетным.
Упражнение 2.13. Покажите, что в множестве w выполняются аксиомы арифметики Пеано (см. раздел 3.1).
Этим завершается наш "переучет" случаев схемы свертывания, которые применяются в математике (и допустимость которых почти не подвергается сомнению).
В своем изложении философии множеств мы отметили, что для построения нашего мира множеств не требуется никакого исходного материала - все можно построить, отправляясь от пустого множества 0. Однако принятые нами до сих аксиомы не могут гарантировать, что всякое множество, о котором идет речь в нашей теории, действительно построено "из ничего". Ведь в этих аксиомах идет речь о том, какие множества существуют, и не сказано ничего о множествах, которые "не должны существовать". Наши аксиомы не исключают, например, существования множества x такого, что x in x (т.е. x - элемент самого себя), или существования пары множеств y,z таких, что y in z & z in y.
Каким образом, однако, записать утверждение, что "всякое множество построено из ничего"? Один из возможных подходов состоит в следующем: если мы переходим от множества x0 к его элементу x1, затем к x2 - элементу x1 и т.д.:
... in x3 in x2 in x1 in x0 ,
то этот "спуск" должен где-то оборваться. Окажись он безграничным, мы получили бы множество x = {x0, x1, x2, x3, ...}, обладающее свойством: для любого y in x найдется z in x такое, что z in y. В запрещении таких множеств и состоит смысл аксиомы регулярности (или аксиомы фундирования):
~(Ex)(~(x=0) & (Ay)(y in x -> (Ez)(z in x & z in y))). (Z3)
Аксиому регулярности ввел в 1925 г. Дж.фон Нейман. Почему так поздно? Дело в том, что работая в "положительной" теории множеств, т.е. занимаясь построением различных множеств с помощью аксиом свертывания (натуральных чисел, действительных чисел, функций и т.д.) и изучением их свойств, нет надобности в постулировании несуществования прочих множеств. Все построенные множества автоматически обладают свойством, утверждаемым в аксиоме регулярности. И только переходя к исследованию принципиальных возможностей аксиом теории множеств, приходится учитывать свойства, которыми должны обладать все множества вообще.
Упражнение 2.14. Выведите из аксиомы регулярности, что
а) R=V (здесь R - класс Рассела, V - класс всех множеств), т.е. покажите, что ~(x in x) для всех x,
б) невозможны множества y, z такие, что y in z & z in y.
Формальную теорию, собственными аксиомами которой являются Z1 (аксиома экстенсиональности), Z21 (схема выделения), Z22 (аксиома пары), Z23 (аксиома объединения), Z24 (аксиома множества подмножеств), Z25 (схема подстановки), Z26 (аксиома бесконечности) и Z3 (аксиома регулярности), принято называть теорией множеств Цермело-Френкеля и обозначать через ZF (Zermelo, Fraenkel).
Правда, сам Э.Цермело включал в свою систему аксиом еще аксиому выбора.
Если элементами множества x являются только непустые множества, то можно попытаться определить функцию f, которая каждому y in x сопоставляет f(у), равное некоторому z in y (поскольку y непусто). Такую функцию естественно назвать функцией выбора для (семейства множеств) x: в каждом из непустых членов семейства она выбирает по одному элементу. Для всякого ли семейства непустых множеств существует функция выбора? Желая всегда иметь положительный ответ на этот вопрос, мы можем принять специальную аксиому - это и есть аксиома выбора:
(Ax)((Ay)(y in x->y<>0) ->
->(Ef)(f-функция & dom(f)=x & (Ay)(y in x->f(y) in y))).
В 1904 г. Э.Цермело использовал этот "принцип произвольного выбора" для доказательства теоремы, согласно которой любое множество можно вполне упорядочить. (Пара (x,<) называется вполне упорядоченным множеством, если всякое непустое подмножество x содержит наименьший элемент в смысле отношения "<".)
Упражнение 2.15. а) Докажите обратное утверждение: если множество Ux можно вполне упорядочить, то для х существует функция выбора.
б) Докажите, используя аксиому выбора, что каждое бесконечное множество содержит счетное подмножество.
Следует особо отметить, что аксиома выбора не является аксиомой свертывания: функция f, существование которой постулируется, не определяется формулой, выражающей отношение f(u)=v. Именно этот неконструктивный характер аксиомы выбора подчеркивается в названии "принцип произвольного выбора" (выбор считается осуществимым несмотря на то, что никакого определенного формулой правила выбора мы не имеем). И именно этим ее характером были вызваны протесты французских математиков после опубликования работы Э.Цермело в 1904 г. Главными оппонентами были Э.Борель, А.Лебег и Р.Бэр. По их мнению, бесконечное число актов произвольного выбора - это способ рассуждения, выходящий за пределы математики и относящийся скорее к области черной магии (более подробно об истории аксиомы выбора см. книгу Ф.А.Медведева [1982]).
И сейчас среди математиков нет единства по вопросу, следует принять аксиому выбора или отвергнуть ее. Поэтому для формальной теории множеств, в которой наряду с аксиомами ZF принимается и аксиома выбора, используется особое обозначение ZFC (от axiom of choice). В теории ZFC можно воспроизвести все результаты интуитивной теории множеств Г.Кантора и его последователей (см. книгу Т.Йеха [1973]). И поскольку остальные математические теории могут быть воспроизведены средствами теории множеств (это было осознано еще в конце XIX в.), то ZFC - формальная теория, которая охватывает всю математику. Так был выполнен первый этап программы Гильберта.