Олексанлдр Рудик

Аксіоматичний підхід до теорії множин.
Нелогічні аксіоми системи Цермело — Френкеля ZF

1. Передумови створення

Аксіоматична теорія множин напрям у математичній логіці, присвячений вивченню фраґментів змістовної теорії множин методами математичної логіки. З цією метою фраґменти теорії множин подають у вигляді аксіоматичної теорії. В основі сучасної теорії множин лежить система аксіом, які приймають без доведення і з яких виводять усі теореми теорії множин. Передумовами створення такої теорії стало відкриття деяких парадоксів (антиномій, суперечностей) так званої «наївної» теорії множин. Серед таких парадоксів найбільш відомими є парадокси Кантора і Рассела.

1.1. Парадокс Рассела (B.Russel, 1902), незалежно відкритий також Цермело (E.Zermelo).

Запровадимо таку властивість P множин: будемо вважати, що для множини X справджується P тоді й лише тоді, коли X не є елементом самої себе. Розглянемо тепер множину Т, що містить усі ті множини, для яких справджується Р, і лише їх. Згідно з означенням Т маємо:

1.2. Парадокс Кантора (G.Cantor, 1899)

Позначимо через М множину усіх множин, а через Р(М) — множину усіх підмножин М. Згідно з означенням М справджується включення: М ⊃ Р(М). З іншого боку, згідно з теоремою Кантора, множина Р(М) має потужність більшу, ніж потужність М, а тому не може бути підмножиною М.

1.3. Причини парадоксів «наївної» теорії множин та способи подолання їх

Існування вказаних суперечностей зумовлено існуванням у «наївній» теорії множин неявного припущення про те, що для будь-якої властивості існує множина, яка складається зі всіх елементів, які мають цю властивість. Таке припущення отримало назву «принципу згортання».

Аксіоматичні теорії множин вносять деякі корективи в цей принцип або іншим чином знімають наявні суперечності. Найбільш відомою з таких систем є система аксіом Цермело-Френкеля (ZF-система), яка накладає певні обмеження на принцип згортання, пропонуючи натомість низку спеціальних аксіом. У цій системі аксіом окремо виділяють аксіому вибору, відношення до якої у математичному товаристві є суперечливим. Аксіоматику Цермело-Френкеля з аксіомою вибору називають ZFC-системою.

ZF-аксіоми було сформульовано в сучасному стані Торальфом Сколемом в 1922 році у результаті розвитку системи аксіом Адольфа Френкеля, яка в свою чергу базувалась на системі аксіом, сформульованій Ернестом Цермело.

В рамках теорії ZFC можна викласти всі загальноприйняті методи математичних міркувань. Навіть кажуть, що на сучасному етапі розвитку математики така «узгодженість» з ZFC є з формальної точки зору універсальним мірилом математичної строгості. Зважаючи на категоричність і фундаментальний характер цього твердження, така позиція не є одностайною.

Побудову формальної аксіоматичної теорії множин розпочинають з вичерпного опису числення предикатів. Надалі ми будемо дотримуватися традиційних позначень числення предикатів. Подамо приклади позначень для термів і формул теорії множин, використовуючи знак, який читають: «запис ліворуч позначає те, що записано праворуч» і записують так: ⇋.

Порожня множина: ∅ ⇋ ɩ x ∀ y ¬ y ∈ x.

Множина таких x, при яких справджується A(x):

{x | A(x)} ⇋ ɩ y ∀ x (x ∈ y ⇔ A(x)).

Тут y не є параметром формули A(x).

Невпорядкована пара x та y: {x, y} ⇋ {z | z = x ∨ z = y}.

Одноелементна множина з х: {x} ⇋ {x, x}.

Впорядкована пара x та y: < x, y > ⇋ {{x}, {x, y}}.

Перетин x та y: x ⋂ y ⇋ {z | z ∈ x ∧ z ∈ y}.

Об’єднання x та y: x ⋃ y ⇋ {z | z ∈ x ∨ z ∈ y}.

Об’єднання усіх елементів x: ⋃ x ⇋ {z | ∃ y (z ∈ y ∧ y ∈ x)}.

Декартів добуток x та y:

x × y ⇋ {z | ∃ u ∃ v (z = < u, v > ∧ u ∈ x ∧ v ∈ y}.

«x є стандартною нескінченою множиною»:

Inf (x) ⇋ (∅ ∈ x) ∧ (∀ y (y ∈ x) ⇒ (y ⋃ {y} ∈ x));

«w є функцією»:

Fnc(w) ⇋ ∃ v   (w ⊆ v × v) ∧ (∀ u ∀ v1 ∀ v2   (<  u, v1 > ∈ w ∧ <  u, v2 > ∈ w) ⇒ (v1 = v2));

Значення функції w на елементі x:

w*x ⇋ ɩ y < x, y > ∈ w.

2. Спроба аксіоматизації «наївної» теорії множин

Подана далі система аксіом А1-А2 повністю відображає принципи «наївної» теорії множин.

А1. Аксіома об’ємності (екстенсиональності). Дві множини збігаються (рівні між собою) тоді й лише тоді, коли вони мають одні й ті самі елементи:

∀ x ∀ y    (x = y) ⇔ ∀ z (z ∈ x ⇔ z ∈ y).

Замість поданого твердження інколи записують, що елементи вважають однаковими, якщо вони належать до одних і тих самих множин. Інакше кажучи, їх неможливо розрізнити за допомогою належності до множин:

∀ x ∀ y    (x = y) ⇔ ∀ z (x ∈ z ⇔ y ∈ z).

А2. Аксіома згортання. Для довільної формули А, що не містить параметра x,

∃ x ∀ y (y ∈ x ⇔ А),

тобто існує множина x, що містить ті й лише ті елементи, для яких справджується формула А.

Система аксіом А1–А2 суперечлива. Справді, якщо в А2 за А взяти формулу ¬ (y ∈ y), то з формули

∀ y (y ∈ x ⇔ ¬ (y ∈ y))

отримуємо суперечність:

x ∈ x ⇔ ¬ (x ∈ x).

3. Різноманітність аксіоматичних систем теорії множин

Аксіоматичні системи теорії множин поділяють на такі чотири групи.

  1. Для аксіоматичних систем першої групи характерним є таке обмеження аксіоми згортання, яке забезпечує природне формулювання звичайних математичних доведень і водночас дозволяє уникнути відомих парадоксів. Першою аксіоматикою такого роду була система Z Цермело (E. Zermelo, 1908). Однак у цій системі неможливо було природним чином формалізувати деякі розділи математики, і А.Френкель (A. Frenkel, 1922) запропонував доповнити систему Z новим принципом, який назвав аксіомою підстановки. Отриману систему називають системою аксіом Цермело — Френкеля і позначають ZF. Ця система аксіом містить єдине примітивне онтологічне (фундаментальне) поняття — множина, та єдине онтологічне припущення, що всі досліджувані об’єкти є множинами. Запроваджено єдине бінарне відношення приналежності до множини.

  2. До другої групи належать системи, аксіоми яких вибрано у зв’язку з певним поясненням парадоксів. Наприклад, як наслідок непредикативних означень. Сюди відносять розгалужену теорію типів Рассела, просту теорію типів Т, теорію типів з трансфінітними індексами.

  3. Для третьої групи характерним є використання нестандарних засобів логічного виведення, багатозначність логіки, додаткові умови на доведення, нескінчені правила виведення.

  4. Четверта група містить модифікації систем перших трьох груп з певною метою. До цієї групи належать системи NBG Неймана — Бернайса — Гьоделя (J. Neumann — P. Bernays — K. Gӧdel, 1925) і NF Куайна (W. Quine, 1937).

4. Нелогічні аксіоми системи Цермело — Френкеля

Z1. Аксіома об’ємності збігається з поданою у пункті 2 аксіомою А1.

Z2. Аксіома пари (об’єднання). Для будь-яких множин x та y існує множина z така, що лише x та y є її елементами:

∀ x ∀ y ∃ z ∀ t    (t ∈ z) ⇔ (t = x ∨ t = y).

Множину z позначають {x, y} і називають невпорядкованою парою x та y.

Зауважимо, що при x = y існує множина z, що містить єдиний елемент x.

Z3. Аксіома (множини-)суми. Для довільної множини z існує множина y, що є об’єднанням усіх елементів x множин u, що належать до z, і яку (множину у) називають множиною-сумою z:

∀ z ∃ y ∀ x    (x ∈ y) ⇔ (∃ u    x ∈ u ∧ u ∈ z).

Z4. Аксіома степеня (булеана, множини підмножин). Для довільної множини x існує множина y, елементами якої є ті й лише ті елементи, що є підмножинами x.

∀ x ∃ y ∀ z    (z ∈ y) ⇔ (∀ t   (t ∈ z) ⇒ (t ∈ x)).

З використанням відношення підмножини ⊆ останню формулу можна спростити:

∀ x ∃ y ∀ z    (z ∈ y) ⇔ (z ⊆ x).

Таку множину y називають булеаном множини x та позначають P(x) або 2x.

Для скінчених множин справджується рівність | 2x | = 2| x |. Тут | x | — кількість елементів множини x.

Z5. Aксіома виділення (cхема специфікації). Для довільної множини x і властивості (предиката, висловлювання системи Z) P існує множина y, елементами якої є ті й лише ті елементи множини y, які мають властивість P (при яких справджується Р):

∀ x ∀ P ∃ y ∀ z    (z ∈ y) ⇔ (z ∈ x ∧ P(z) ).

Тут y не входить у запис P.

Z6. Аксіома нескінченності. Існує така множина x, що містить порожню множину ∅ та для довільного належного до неї елемента y включає також і множину, утворену об’єднанням y та {y}:

∃ x    (∅ ∈ x) ∧ (∀ y (y ∈ x) ⇒ (y ⋃ {y} ∈ x)).

За допомогою раніше означеного предикату Inf цю аксіому можна записати так:

∃ x    Inf (x).

Для того, щоби пояснити цю аксіому, означимо елемент y ∪ {y} як наступний для елемента y (аксіома пари дозволяє нам сформувати множину {y}, аксіома об’єднання дозволяє здійснити операцію ∪). Поняття наступного елемента використовують зокрема для побудови теорії натуральних чисел за допомогою теорії множин. У такій побудові нуль — порожня множина, одиниця — наступний елемент за нулем, два — наступний елемент за одиницею і т.і.:
0 = {};
1 = 0 ∪ {0} = {} ∪ {{}} = {{}} = {0};
2 = 1 ∪ {1} = {0} ∪ {1} = {{},{{}}} = {0,1}, і т.і.
У такій побудові кожне натуральне число є множиною усіх попередніх натуральних чисел. Без аксіоми Z6 така побудова була б неможливою.

Z7. Аксіома вибору. Для довільної множини z існує функція w, що вибирає з кожного непорожнього елемента x множини z єдиний елемент w*x:

∀ z ∃ w    ( Fnc(w) ∧ ∀ x (x ∈ z ∧ ¬ x = ∅ ⇒ w*x ∈ x) ).

Z8. Аксіома регулярності. У будь-якій непорожній множині x є елемент y, при якому перетин x та y є порожньою множиною:

∀ x   (¬ x = ∅ ⇒ ∃ y (y ∈ x ∧ y ⋂ x = ∅))

Згідно з цією аксіомою не існує нескінчених послідовностей множин, у якій кожна наступна є елементом попередньої. Замість висловлювання Z8 використовують і таке, яке легше трансформувати у віповідну аксіому системи NBG.

Z8'. Аксіома обмеження. Для довільного висловлювання (предикату) P системи Z, при якому існує множина x, для якої справджується P(x), існує множина y, для якої справджується P(y), але для довільного її елемента z не справджується P(z):

(∃ x    P(x)) ⇒ (∃ y    P(y) ∧ (∀ z    ¬ (z ∈ y ∧ P(z))).

ZF9. Аксіома підстановки Френкеля

∀ P    (1)∧(2)⇒(3),

що доповнює систему Z до ZF.

При довільному двомісному предикаті P(x, y), що задає взаємно однозначну відповідність:
(1)     ∀ x ∀ y ∀ z ∀ w ( (P(x, y) ∧ P(z, w)) ⇒ (x = z ⇔ y = w) ),

і при існуванні множини u усіх таких множин x, при яких існує таке y, що справджується P(x, y):
(2)     ∃ u ∀ x    (x ∈ u ⇔ ∃ y    P(x, y) )

існує множина v усіх таких множин y, при яких існує таке x, що справджується P(x, y):
(3)     ∃ v ∀ y    (y ∈ v ⇔ ∃ x    P(x, y) )

Про існування порожньої множини твердить аксіома нескінченності Z6. Зауважимо також надлишковість поданої системи аксіом: