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

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 есть значение этой функции, примененной к у (В дальнейшем будем по мере необходимости вводить новые функциональные буквы и предметные константы, как только будет ясно, что соответствующее определение может быть обосновано теоремой о единственности. В настоящем случае происходит введение некоторой новой функциональной буквы h с сокращенным обозначением Х‘Y вместо h (X, Y)).

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

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

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

Определения

X Irr Y означает y (y Y   X) & Rel (X).

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

X Tr Y означает Rel (X) & uvw (uY & vY & wY &

& X &X & X X).

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

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

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

X Con Y означает Rel(X) & uv (uY & vY & 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 (ZY &

& 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))

yu (u  x 1w (w  u ∩ y)).

П р и н ц и п в п о л н е у п о р я д о ч е н и я (W. O.): Всякое множество может быть вполне упорядочено. x y (y We x).

Т р и х о т о м и я (Trich): xy (x  y y  x).

Л е м м а Ц о р н а (Zorn): Если в частично упорядоченном множестве х всякая цепь (т. е. всякое упорядоченное подмножество) имеет верхнюю грань, то в х существует максимальный элемент.

xy ((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 и gf, что противоречит максимальности g. Следовательно, g‘‘ α = z, т. е. α  z. Посредством функции g отношение Еα, вполне упорядочивающее множество α, преобразуется в некоторое отношение, вполне упорядочивающее z.

Заключение

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

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

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

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

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

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