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

Значение математической логики в нашем и прошлом столетии сильно возросло. Главной причиной этого явилось открытие парадоксов теории множеств и необходимость пересмотра противоречивой интуитивной теории множеств. Было предложено много различных аксиоматических теорий для обоснования теории множеств, но как бы они не отличались друг от друга своими внешними чертами, общее для всех них содержание составляют те фундаментальные теоремы, на которые в своей повседневной работе опираются математики. Выбор той или иной из имеющихся теорий является в основном делом вкуса; мы же не предъявляем к системе, которой будем пользоваться, никаких требований, кроме того, чтобы она служила достаточной основой для построения современной математики.

§1. Система аксиом

Опишем теорию первого порядка NBG, которая в основном является системой того же типа, что и система, предложенная первоначально фон Нейманом (1925), (1928), а затем тщательно пересмотренная и упрощенная Р. Робинсоном (1937), Бернайсом (1937—1954) и Гёделем (1940). (Будем в основном следовать монографии Гёделя, хотя и с некоторыми важными отклонениями.) Теория NBG имеет единственную предикатную букву и не имеет ни одной функциональной буквы или предметной константы. Чтобы быть ближе к обозначениям Бернайса (1937—1954) и Гёделя (1940), мы будем употреблять в качестве переменных вместо x1, x2, … прописные латинские буквы X1, Х2, ... (Как обычно, мы используем буквы X, Y, Z, ... для обозначения произвольных переменных.) Мы введем также сокращенные обозначения ХY для(X, Y) и XY для (X, Y). Содержательно знак понимается как символ отношения принадлежности.

Следующим образом определим равенство:

Определение. Х=Y служит сокращением для формулы .

Таким образом, два объекта равны тогда и только тогда, когда они состоят из одних и тех же элементов.

Определение. служит сокращением для формулы (включение).

Определение. XY служит сокращением для Х Y & X ≠ Y (собственное включение).

Из этих определений легко следует

Предложение 1.

(а) Х = Y (X Y & Y X);

(b) Х = Х;

(с) Х = Y Y = Х;

(d) Х = Y (Y = Z Х = Z);

(е) Х = Y (ZX ZY).

Теперь приступим к перечислению собственных аксиом теории NBG, перемежая формулировки самих аксиом различными следствиями из них и некоторыми дополнительными определениями. Предварительно, однако, отметим, что в той «интерпретации», которая здесь подразумевается, значениями переменных являются классы. Классы — это совокупности, соответствующие некоторым, однако отнюдь не всем, свойствам (те свойства, которые фактически определяют классы, будут частично указаны в аксиомах. Эти аксиомы обеспечивают нам существование необходимых в математике классов и являются, достаточно скромными, чтобы из них нельзя было вывести противоречие). (Эта «интерпретация» столь же неточна, как и понятия «совокупность», «свойство» и т. д.)

Назовем класс множеством, если он является элементом какого-нибудь класса. Класс, не являющийся множеством, назовем собственным классом.

Определение. M(X) служит сокращением для Y(XY) (X есть множество).

Определение. Pr(X) служит сокращением для M(X) (X есть собственный класс).

В дальнейшем увидим, что обычные способы вывода парадоксов приводят теперь уже не к противоречию, а всего лишь к результату, состоящему в том, что некоторые классы не являются множествами. Множества предназначены быть теми надежными, удобными классами, которыми математики пользуются в своей повседневной деятельности; в то время как собственные классы мыслятся как чудовищно необъятные собрания, которые, если позволить им быть множествами (т. е. быть элементами других классов), порождают противоречия.

Система NBG задумана как теория, трактующая о классах, а не о предметах. Мотивом в пользу этого послужило то обстоятельство, что математика не нуждается в объектах, не являющихся классами, вроде коров или молекул. Все математические объекты и отношения могут быть выражены в терминах одних только классов. Если же ради приложений в других науках возникает необходимость привлечения «неклассов», то незначительная модификация системы NBG позволяет применить ее равным образом как к классам, так и к «неклассам» (Мостовский (1939)).

Мы введем строчные латинские буквы x1, x2, … в качестве специальных, ограниченных множествами, переменных. Иными словами, x1 A (x1) будет служить сокращением для X (M(X)A (X)) , что содержательно имеет следующий смысл: «A истинно для всех множества, и x1 A (x1) будет служить сокращением для X (M(X)A (X)), что содержательно имеет смысл: «A истинно для некоторого множества». Заметим, что употребленная в этом определении переменная X должна быть отличной от переменных, входящих в A (x1). (Как и обычно, буквы х, y, z, ... будут употребляться для обозначения произвольных переменных для множеств.)

П р и м е р. Выражение ХхyZA (X, х, y, Z) служит сокращением для

ХXj (М(Xj)Y(M(Y)&ZA (X, Xj, Y, Z))).

А к с и о м а Т. (Аксиома объемности.) Х = Y (XZYZ).

Предложение 2. Система NBG является теорией первого порядка с равенством.

А к с и о м а Р. (Аксиома пары.) xyzu (u z u = xu = y), т. е. для любых множеств х и у существует множество z такое, что х и у являются единственными его элементами.

А к с и о м а N. (Аксиома пустого множества.) х y (у х), т. е. существует множество, не содержащее никаких элементов.

Из аксиомы N и аксиомы объемности следует, что существует лишь единственное множество, не содержащее никаких элементов, т. е.

1x y (у х). Поэтому мы можем ввести предметную константу 0, подчиняв ее следующему условию.

Определение. y (y 0).

Так как выполнено условие единственности для неупорядоченной пары, то можем ввести новую функциональную букву g(х, y) для обозначения неупорядоченной пары х и у. Впрочем вместо g(х, y) мы будем писать {х, у}. Заметим, что можно однозначно определить пару {X, Y} для любых двух классов Х и Y, а не только для множеств х и у. Положим {X, Y} = 0, если один из классов X, Y не является множеством. Можно доказать, что

NBG 1Z((M(X)&M(Y)&u (u Z u = X u = Y))

(( M(X) M(Y))&Z=0)).

Этим оправдано введение пары {X, Y}:

Определение. (М(Х) & М(Y) & u (и {X, Y} u = X u = Y))

(( M(X) M(Y)) & {X, Y} = 0).

Можно доказать, что NBG x y u (u {х, у} u = x u = y) и NBG x y (M({х, у})).

Определение. = {{Х}, {X, Y}}. называется упорядоченной парой классов Х и Y.

Никакого внутреннего интуитивного смысла это определение не имеет. Оно является лишь некоторым удобным способом (его предложил Ку-ратовский) определить упорядоченные пары таким образом, чтобы можно было доказать следующее предложение, выражающее характеристическое свойство упорядоченных пар.

Предложение 3.

NBG x y u v ().

Доказательство. Пусть = . Это значит, что {{x}, {x, y}} = {{u}, {u, v}}. Так как {х} {{x}, {x, y}}, то {x} {{u}, {u, v}}. Поэтому {x} = ={u} или {х} = {u, v}. В обоих случаях х = и. С другой стороны, {u, v} {{u}, {u, v}} и, следовательно, {u, v} {{x}, {x, y}}. Отсюда {u, v} = {x} или {u, v} = ={x, y}. Подобным же образом {x, y} = {u} или {х, у}={и, v}. Если или {u, v} = ={x} и {х, y} = {u}, то х = и = у = v, в противном случае {и, v} = {х, у} и, следовательно, {и, v} = {u, у}. Если при этом v ≠ u, то y = v, если же v = u, то тоже y = v. Итак, в любом случае, y = v.

Мы теперь обобщим понятие упорядоченной пары до понятия упорядоченной n-ки.

Определение

= Х,

Так, например,

и

В дальнейшем индекс NBG в записи NBG опускается.

Нетрудно доказать следующее обобщение предложения 3:

Аксиомы существования классов.

Эти аксиомы утверждают, что для некоторых свойств, выраженных формулами, существуют соответствующие классы всех множеств, обладающих этими свойствами.

А к с и о м а В1. X u v (X u v) (- отношение).

А к с и о м а В2. X Y Z u (u Z u X & u Y)

(пересечение).

А к с и о м а В3. X Z u (u Z u X) (дополнение).

А к с и о м а В4. X Z u (u Z v (X)) (область

определения).

А к с и о м а В5. X Z u v ( Z u X).

А к с и о м а В6. X Z u v w ( Z X).

А к с и о м а В7. X Z u v w ( Z X).

С помощью аксиом В2—В4 можно доказать

X Y 1Z u (u Z u X & u Y),

X 1Zu (u Z u x),

X 1Zu (u Z v ( X)).

Эти результаты оправдывают введение новых функциональных букв ∩, −, D.

Определения

u (u X ∩ Y u X & u Y) (пересечение классов Х и Y).

u (u u X) (дополнение к классу X).

u (u D (X) v ( X)) (область определения класса X).

(объединение классов Х и Y).

V = (универсальный класс).

X − Y = X ∩

Общая теорема о существовании классов.

Предложение 4. Пусть φ (X1,…,Xn, Y1,…, Ym) – формула, переменные которой берутся лишь из числа X1,…,Xn, Y1,…, Ym . Назовём такую формулу предикативной, если в ней связными являются только переменные для множеств (т.е. если она может быть приведена к такому виду с помощью принятых сокращений). Для всякой предикативной формулы φ (X1,…,Xn, Y1,…, Ym)

Zx1 …xn ( Z φ (x1,…,xn, Y1,…, Ym)).

Доказательство. Мы можем ограничиться рассмотрением только таких формул φ, которые не содержат подформул вида Yi W, так как всякая такая подформула может быть заменена на x (x = Yi & x W), что в свою очередь эквивалентно формуле x (z (z x z Yi) & x W). Можно также предполагать, что в φ не содержатся подформулы вида XX, которые могут быть заменены на u (u = X & u X), последнее же эквивалентно u (z (z u z X) & u X). Доказательство проведем теперь индукцией по числу k логических связок и кванторов, входящих в формулу φ (записанную с ограниченными переменными для множеств).

1. Пусть k = 0. Формула φ имеет вид xi xj, или xj xi, или xi Yi, где 1 ≤ i < j ≤ n. В первом случае, по аксиоме В1, существует некоторый класс W1 такой, что

xixj (W1 xi xj).

Во втором случае, по той же аксиоме, существует класс W2 такой, что

xixj (W2 xj xi),

и тогда, в силу

XZ u v ( Z X),

существует класс W3 такой, что

xixj (W3 xj xi).

Итак, в любом из первых двух случаев существует класс W3 такой, что

xixj (W φ (x1,…,xn, Y1,…, Ym)).

Тогда, заменив в

XZ v1…vkuw ( Z X)

X на W, получим, что существует некоторый класс Z1 такой, что

x1… xi-1xixj (Z1 φ (x1,…,xn, Y1,…, Ym)).

Далее, на основании

XZ v1…vmx1…xn (

ZX)

там же при Z1 = X, заключаем, что существует класс Z2 такой, что

x1 … xi xi+1 … xj ( Z2 φ (x1,…,xn, Y1,…, Ym)).

Наконец, применяя

XZ v1…vmx1…xn ( Z X)

(1)

там же при Z2 = Х, получаем, что существует класс Z такой, что

x1…xn ( Z φ (x1,…,xn, Y1,…, Ym)).

Для остающегося случая xi Yi теорема следует из (1) и

XZ x v1…vm ( Z x X).

2. Предположим, что теорема доказана для любого k < s и что φ содержит s логических связок и кванторов.

(a) φ есть ψ. По индуктивному предположению, существует класс W такой, что

x1…xn ( W ψ (x1,…,xn, Y1,…, Ym)).

Теперь остается положить Z = .

(b) φ есть ψ θ. По индуктивному предположению, существуют классы Z1 и Z2 такие, что

x1…xn ( Z1 ψ (x1,…,xn, Y1,…, Ym)) и

x1…xn ( Z2 θ (x1,…,xn, Y1,…, Ym)).

Искомым классом Z в этом случае будет класс .

(c) φ есть x ψ. По индуктивному предположению, существует класс W такой, что

x1…xnx ( W ψ (x1,…, xn, x, Y1,…, Ym)).

Применим сперва

XZ x1 … xn ( Z y ( X)).

при X = и получим класс Z1 такой, что

x1 … xn ( Z1x ψ (x1,…, xn, x, Y1,…, Ym)).

Теперь положим окончательно Z = , замечая, что x ψ эквивалентно

x ψ.

Примеры. 1. Пусть φ (X, Y1, Y2) есть формула uv (X = & u Y1 & v Y2). Здесь кванторы связывают только переменные для множеств. Поэтому, в силу теоремы о существовании классов, Z x (x Z uv (x = & u Y1 & v Y2)), а на основании аксиомы объемности, 1Z x (x Z uv (x = & u Y1 & v Y2)). Поэтому возможно следующее определение, вводящее новую функциональную букву :

Определение. x (x Y1 Y2 uv (x = & u Y1 & v Y2)). (Декартово произведение классов Y1 и Y2).

Определения.

X2 обозначает X X (в частности, V2 обозначает класс всех упорядоченных пар).

…………………………………………………………………………………………………

Xn обозначает Xn-1 X (в частности, Vn обозначает класс всех упорядоченных n-ок).

Rel(X) служит сокращением для Х V2 (X есть отношение).

2. Пусть φ (X, Y) обозначает Х Y. По теореме о существовании классов и на основании аксиомы объемности, 1Zx (x Z x Y). Таким образом, существует класс Z, элементами которого являются все подмножества класса Y.

Определение. x (x P (Y) x Y). (P (Y): класс всех подмножеств класса Y.)

3. Рассмотрим в качестве φ (X, Y) формулу v (X v & v Y).

По теореме о существовании классов и на основании аксиомы объемности, 1Zx (x Z v (x v & v Y)), т.е. существует единственный класс Z, элементами которого являются все элементы элементов класса Y и только они.

Определение. x (x (Y) v (x v & v Y)). ((Y): объединение всех элементов класса Y)

4. Пусть φ (X) есть u (X = ). По теореме о существовании классов и на основании аксиомы объемности, существует единственный класс Z такой, что x (x Z u (x = )).

Определение. x (x I u (x = )). (Отношение тождества.)

Следствие. Для всякой предикативной формулы φ (X1,…,Xn, Y1,… …, Ym)

1W( W Vn & x1…xn ( W

φ (x1,…,xn, Y1,…, Ym)).

Доказательство. В силу предложения 4, существует класс Z, для которого x1…xn ( Z φ (x1,…,xn, Y1,…, Ym)). Очевидно, искомым классом W является класс W = Z ∩ Vn; его единственность вытекает из аксиомы объемности.

Определение. Для всякой предикативной формулы φ (X1,…,Xn, Y1,… …, Ym) через φ (x1,…,xn, Y1,…, Ym)) обозначается класс всех n-ок , удовлетворяющих формуле φ (x1,…,xn, Y1,…, Ym)), т. е. u (u φ (x1,…,xn, Y1,…, Ym) x1…xn (u = & φ (x1,…,xn, Y1,… …, Ym))). Следствие оправдывает такое определение. В частности, при n = 1 получим u (u φ (x, Y1, …, Ym) φ (u, Y1,…, Ym)) (иногда вместо φ (x1,…,xn, Y1,…, Ym) применяют запись {| φ (x1,…,xn, Y1,…, Ym)}).

Примеры. 1. Пусть φ есть Y. Обозначим ( Y) сокращенно через , тогда V2 & x1x2( Y Y). Назовем обратным отношением класса Y.

2. Пусть φ есть v ( Y). Обозначим через R(Y) выражение (v ( Y)). Тогда u (u R(Y) v ( Y)). Класс R(Y) называется областью значений класса Y. Очевидно, R(Y) = D().

Заметим, что аксиомы В1 — В7 являются частными случаями теоремы о существовании классов, т. е. предложения 4. Иными словами, вместо того, чтобы выдвигать предложение 4 в качестве схемы аксиом, можно с тем же результатом ограничиться лишь некоторым конечным числом его частных случаев. Вместе с тем, хотя предложение 4 и позволяет доказывать существование большого числа самых разнообразных классов, нам, однако, ничего еще не известно о существовании каких-либо множеств, кроме самых простых множеств таких, как 0, {0}, {0, {0}}, {{0}} и т. д. Чтобы обеспечить существование множеств более сложной структуры, введем дальнейшие аксиомы.

А к с и о м а U. (Аксиома объединения.)

xyu (u y v (u v & v x)).

Эта аксиома утверждает, что объединение (х) всех элементов множества х является также множеством, т. е. x (M((х))). Множество и (х) обозначают также через и v.

Средством порождения новых множеств из уже имеющихся является образование множества всех подмножеств данного множества.

А к с и о м а W. (Аксиома множества всех подмножеств.)

xyu (u y u x).

Эта аксиома утверждает, что класс всех подмножеств множества х есть также множество; его будем называть множеством всех подмножеств множества х. В силу этой аксиомы, x (M(P (х))).

Примеры.

P (0) = {0}.

P ({0}) = {0, {0}}.

P ({0, {0}}) = {0, {0}, {0, {0}}, {{0}}}.

Значительно более общим средством построения новых множеств является следующая аксиома выделения.

А к с и о м а S.

xY zu (u z u x & u Y).

Таким образом, для любого множества х и для любого класса Y существует множество, состоящее из элементов, общих для х и Y. Следовательно, xY (M (x ∩ Y)), т. е. пересечение множества с классом есть множество.

Предложение 5. xY (Y x M (Y)) (т. е. подкласс множества есть множество).

Доказательство. x (Y x Y ∩ x = Y) и x (M (Y ∩ x)).

Так как всякая предикативная формула A(у) порождает соответствующий класс (предложение 4), то из аксиомы S следует, что для любого множества х класс всех его элементов, удовлетворяющих данной предикативной формуле A(у), есть множество.

Однако для полного развития теории множеств потребуется аксиома, более сильная, чем аксиома S. Введем предварительно несколько определений.

Определения

Un (X) означает xyz ( X & X y = z).

(X однозначен.)

Fnc (X) означает X V2 & Un (X). (X есть функция.)

Y 1 X означает X ∩ (Y V). (Ограничение Х областью Y.)

Un1 (X) означает Un (X) & Un (). (X взаимно однозначен.)

X‘Y

Если существует единственное z такое, что X, то z = X‘y; в противном случае X‘y = 0. Если Х есть функция, а у — множество из области определения X, то X‘y есть значение этой функции, примененной к у (В дальнейшем будем по мере необходимости вводить новые функциональные буквы и предметные константы, как только будет ясно, что соответствующее определение может быть обосновано теоремой о единственн