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

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

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

x₁…x_n ( W ψ (x₁,…,x_n, Y₁,…, Y_m)).

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

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

x₁…x_n ( Z₁ ψ (x₁,…,x_n, Y₁,…, Y_m)) и

x₁…x_n ( Z₂ θ (x₁,…,x_n, Y₁,…, Y_m)).

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

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

x₁…x_nx ( W ψ (x₁,…, x_n, x, Y₁,…, Y_m)).

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

XZ x₁ … x_n ( Zy ( X)).

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

x₁ … x_n ( Z₁x ψ (x₁,…, x_n, x, Y₁,…, Y_m)).

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

x ψ.

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

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

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

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

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

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

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

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

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

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

По теореме о существовании классов и на основании аксиомы объем­ности, ₁Zx (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 = )). (Отношение тож­дества.)

Следствие. Для всякой предикативной формулы φ (X₁,…,X_n, Y₁,… …, Y_m)

₁W( W Vⁿ & x₁…x_n ( W

φ (x₁,…,x_n, Y₁,…, Y_m)).

Доказательство. В силу предложения 4, существует класс Z, для которого x₁…x_n ( Z φ (x₁,…,x_n, Y₁,…, Y_m)). Очевидно, искомым классом W является класс W = Z ∩ Vⁿ; его един­ственность вытекает из аксиомы объемности.

Определение. Для всякой предикативной формулы φ (X₁,…,X_n, Y₁,… …, Y_m) через φ (x₁,…,x_n, Y₁,…, Y_m)) обозначается класс всех n-ок , удовлетворяющих формуле φ (x₁,…,x_n, Y₁,…, Y_m)), т. е. u (u φ (x₁,…,x_n, Y₁,…, Y_m) x₁…x_n(u = & φ (x₁,…,x_n, Y₁,… …, Y_m))). Следствие оправдывает такое определение. В частности, при n = 1 получим u (u φ (x, Y₁, …, Y_m) φ (u, Y₁,…, Y_m)) (иногда вместо φ (x₁,…,x_n, Y₁,…, Y_m) применяют запись {| φ (x₁,…,x_n, Y₁,…, Y_m)}).

Примеры. 1. Пусть φ есть Y. Обозначим ( Y) сокращенно через , тогда V² & x₁x₂( 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 V² & Un (X). (X есть функция.)

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

Un₁ (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 ₁w (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 {и}. Пусть х₁ —область значении функции g. Легко видеть, что х₁ является множеством непустых попарно непересекающихся множеств. На основа­нии Mult, для х₁ существует выбирающее множество у. Отсюда, если 0 ≠ u и u х, то и {и} х₁ и у содержит и притом единственный элемент из и {и}. Функция 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 взаимно однозначна и что если α

Похожие работы

Элементы теории множеств

Скачать

42398

1

0

... действительных чисел. 3.3. Конечные и бесконечные множества Конечное множество - множество, состоящее из конечного числа элементов. Пример. A = {1, 2, 3, 4, 5}. Основной характеристикой конечного множества является число его элементов. Теория конечных множеств изучает правила: как, зная количество элементов некоторых множеств, вычислить количество элементов других множеств, которые составлены из ...

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

Скачать

24510

0

0

... нашем примере: сила, с которой брошена монета, форма монеты и многие другие). Невозможно учесть влияние на результат всех этих причин, поскольку число их очень велико и законы их действия неизвестны. Поэтому теория вероятностей не ставит перед собой задачу предсказать, произойдет единичное событие или нет, она просто не в силах это сделать. Еще пример, выпадение снега в Москве 30 ноября является ...

Динамика развития некоторых понятий и теорем теории вероятностей

Скачать

66135

2

3

... понятия вероятности задача некоторой несостоятельности классического определения вероятности была решена. Однако наблюдаются попытки дать трактовку вероятности с более широких позиций, в том числе и с позиций теории информации. 2. Динамика развития понятия математического ожидания   2.1 Предпосылки введения понятия математического ожидания Одним из первых приблизился к определению понятия ...

Теория вероятностей и математическая статистика

Скачать

100095

5

2

... проверить знания студента из первой части курса, которая излагается в первых четырёх модулях. Во вторых вопросах билета проверяются знания классической предельной проблемы теории вероятностей и математической статистики, которые излагаются в следующих пяти модулях. 1.  Вероятностная модель с не более чем счётным числом элементарных исходов. Пример: испытания с равновозможными исходами. 2.  ...