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

Введение

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

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

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

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

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

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

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

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

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

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

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

(b)/> Х = Х;

(с)/> Х = Y />Y = Х;

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

(е)/> Х = Y /> (Z/>X /> Z/>Y).

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

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

Определение.M(X) служит сокращением для />Y(X/>Y) (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,… будут употребляться для обозначенияпроизвольных переменных для множеств.)

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

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

Ак с и о м а Т. (Аксиома объемности.) Х = Y />(X/>Z/>Y/>Z).

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

Ак с и о м а Р. (Аксиома пары.) />x/>y/>z/>u (u /> z /> u = x/>u = 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 />1Z/>u (u /> Z /> u /> x),

/> />X />1Z/>u (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)

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

Доказательство.Мы можем ограничиться рассмотрением только таких формул φ, которые несодержат подформул вида Yi /> W, так как всякая такая подформуламожет быть заменена на />x (x = Yi & x /> W), что в свою очередьэквивалентно формуле />x (/>z (z /> x /> z /> Yi) & x /> W). Можно такжепредполагать, что в φ не содержатся подформулы вида X/>X, которые могут бытьзаменены на />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 такой, что

/>xi/>xj (/>/>W1 /> xi /> xj).

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

/>xi/>xj (/>/>W2 /> xj /> xi),

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

/> />X/>Z />u />v (/>/>Z /> /> /> X),

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

/>xi/>xj (/>/>W3 /> xj /> xi).

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

/>xi/>xj (/>/>W /> φ (x1,…,xn, Y1,…, Ym)).

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

/> />X/>Z />v1…/>vk/>u/>w (/>/> Z /> /> /> X)

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

/>x1… />xi-1/>xi/>xj (/>/>Z1 /> φ (x1,…,xn, Y1,…, Ym)).

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

/> />X/>Z />v1…/>vm/>x1…/>xn (/>/>

/> Z/>/>/>X)

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

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

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

/> />X/>Z />v1…/>vm/>x1…/>xn (/>/>Z />/>/>X)

(1)

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

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

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

/> />X/>Z />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…/>xn/>x (/>/> W /> ψ (x1,…, xn, x, Y1,…, Ym)).

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

/> />X/>Z />x1 … />xn (/>/> Z />/>y (/>/>X)).

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

/>x1 … />xn (/>/> Z1/>/>x/>ψ (x1,…, xn, x, Y1,…, Ym)).

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

/>/>x/>ψ.

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

Определение./>x (x /> Y1 /> Y2 /> />u/>v (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. По теореме о существованииклассов и на основании аксиомы объемности, /> />1Z/>x (x /> Z /> x />Y). Таким образом, существует классZ, элементами которого являются все подмножества класса Y.

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

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

Потеореме о существовании классов и на основании аксиомы объемности, /> />1Z/>x (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 & />x1/>x2(/>/>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. (Аксиома объединения.)

/>x/>y/>u (u /> y /> />v (u /> v & v /> x)).

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

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

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

/>x/>y/>u (u /> y /> u /> x).

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

Примеры.

/> P (0) ={0}.

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

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

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

Ак с и о м а S.

/>x/>Y />z/>u (u /> z /> u /> x & u /> Y).

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

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

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

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

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

Определения

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

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

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

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

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

X‘Y/>

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

X‘‘Y= R(Y 1 X). (Если Х есть функция, то X‘‘Y есть область значений класса X,ограниченного областью Y.)

Ак с и о м а R. (Аксиома замещения.)

/>x(Un (X) /> />y/>u (u /> y /> />v (/>/>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 способом избавления отобычных парадоксов (например, парадоксов Кантора и Бурали-Форти).

Определения

XIrr Y означает />y (y />Y />/> /> X) & Rel (X).

(Xесть иррефлексивное отношение на Y.)

XTr 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.)

XCon Y означает Rel(X) & />u/>v (u/>Y & v/>Y & u ≠ v />/>/>

/> X /> /> /> X).

XTot Y означает (X Irr Y) & (X Tr Y) & (X Con Y).

(Xупорядочивает Y.)

XWe 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. Каковы бы ни были две функции, принадлежащие одной и той же цени в X, однаиз них является продолжением другой. Поэтому для любой цепи в Х объединениевсех принадлежащих ей функций есть снова взаимно однозначная функция, принадлежащаятой же цепи. Следовательно, на основании Zorn, в X имеется максимальный элементg, представляющий собой взаимно однозначную функцию, определенную на некоторомпорядковом числе я и принимающую значения из z. Допустим, что z — g‘‘ α ≠0. Пусть b/>z — g‘‘ α, и положим f = g/>{/>}. Тогда f />X и g/>f, что противоречит максимальностиg. Следовательно, g‘‘ α = z, т. е. α /> z. Посредством функции g отношениеЕα, вполне упорядочивающее множество α, преобразуется в некотороеотношение, вполне упорядочивающее z.

Заключение

Системааксиом теории множеств была создана для решения задачи обоснования базовыхположений современной математики. Таким образом существующие разделы математикиможно считать a priori непротиворечивыми, поскольку все их доказанныевысказывания логически могут быть сведены к аксиомам. В этом отношенииаксиоматика выполнила свое предназначение.

Список литературы

МендельсонЭ. Введение в математическую логику. – М.: Наука, 1984.

ЛяпинЕ. С. Полугруппы. – М.: Физматгиз, 1960.

СтолРоберт Р. Множества. Логика. Аксиоматические теории. Пер. с англ. Ю.А. Гастаеваи И.Х. Шмаина. Под ред. Ю.А. Шихановича. М.: «Просвещение», 1968.

Дляподготовки данной работы были использованы материалы с сайта www.bankreferatov.ru/