ML: Логіка та ймовірність: Приклади теорій

Вступ

Цей документ є факультативним додатком до вступу в математичну логіку.
Ми розглянемо декілька формальних теорій, аналізуючи їхню аксіоматику та приклади логічних висновків.

Квантори і число об'єктів

✒ Фраза "існують різні об'єкти, що перебувають у відношенні $R$" записується таким чином: $$ \exists_{x,y}\,\bigr[x\neq y~\,\&\,~R(x,y)\bigr]. $$ Квантори $\exists_{x,y}$ c $x,y\in \{a_1,a_2,...\}$ "перебирають" з'єднання диз'юнкціями формули $\bigr[a_i\neq a_j~\,\&\,~R(a_i,a_j)\bigr]$ для пар предметів. Члени з $i=j$ будуть хибними: $(a_i\neq a_i) ~\equiv~\F $ і не впливають на результат $\F \vee Q ~\leftrightarrow~ Q$. Так, для трьох предметів $\{a_1,a_2,a_3\}$ отримаємо: $ R(a_1,a_2)\vee R(a_1,a_3)\vee R(a_2,a_1)\vee R(a_2,a_3)\vee R(a_3,a_1)\vee R(a_3,a_2), $ що і означає стверджуване у фразі.

✒ Фраза "будь-які різні об'єкти перебувають у відношенні $R$", вимагає імплікації (якщо $x\neq y$, то ...): $$ \forall_{x,y}\,\bigr[x\neq y~\to~R(x,y)\bigr]. $$ Квантор загальності - це ланцюжок формул, з'єднаних кон'юнкцією. Для однакових предметів члени типу $a_1\neq a_1 ~\to~R(a_1,a_1)$ істинні, і їх можна опустити ($\T \,\&\,Q~\equiv~ Q$). Залишаються тільки пари різних елементів.

Взагалі, перекладаючи з природної мови на формальну, не можна плутати імплікацію та кон'юнкцію.
Фраза "для будь-якого додатного $x$ справедлива властивість $P$" записується так: $\forall_x\,[(0 \lt x)\, \to\,P(x)]$.
Якщо поставити кон'юнкцію, то $\,\forall_x\,[(0 \lt x)~\,\&\,~P(x)]$ в арифметиці буде хибним (через $\forall_x$ при $x=0$).
Формула $\forall_x\,[(0 \lt x)~\vee~ P(x)]$ для $x\in \mathbb{N}=\{0,1,2,...\}$ еквівалентна $P(0)$, що, також очевидно не про те.
Якщо ж ми говоримо, що "існує додатне $x$ із властивістю $P$", треба писати $\exists_x\,[(0\lt x)~\&~P(x)]$.

✒ Квантор існування $\exists_x P(x)$ повідомляє, що є один або декілька об'єктів, які задовольняють властивість $P$. Часто потрібно фіксувати конкретне число об'єктів, що фігурують у твердженні.

Фраза "не більше одного об'єкта ($0$ або $1$) задовольняє властивість $P$", записується таким чином: $$ \forall_{x,y}\,\bigr[P(x)\,\&\,P(y)~\to~x=y\bigr]. $$ Відповідно можна визначити квантор "існує рівно один об'єкт, що володіє властивістю $P$": $$ \exists^1_x\, P(x)~~~~~~~~\Leftrightarrow~~~~~~~~\exists_z\,P(z)~~\&~~\forall_{x,y}\,\bigr[P(x)\,\&\,P(y)~\to~x=y\bigr]. $$ Тепер символ $\exists^1_x$ можна використовувати у формулах нарівні з іншими кванторами.
Аналогічно, "принаймні два об'єкти $(2,3,...)$ володіють властивістю $P$" має вигляд: $$ \exists_{x,y}\,\bigr[P(x)~\&~P(y)~\&~x\neq y\bigr], $$ а "не більше двох об'єктів $(0,1,2)$ володіють властивістю $P$": $$ \forall_{x,y,z}\,\bigr[P(x)~\&~P(y)~\&~P(z)~\to~(x=y~\vee~x=z~\vee~ y=z)\bigr]. $$ Кон'юнкція двох останніх формул дає фразу "рівно два об'єкти володіють властивістю $P$", тобто $\exists^2_x\,P(x)$.

Натуральні числа

Множину предметів із властивостями натуральних чисел $\mathbb{N}=\{0,1,2,...\}$ можна визначити в сигнатурі з константою $0$ і унарною (один аргумент) функцією, яка має сенс наступного за числом $x$ числа $n(x)$.
Вважаємо, що в сигнатурі також є відношення $x=y$ зі стандартними властивостями (теорія з рівністю).
Нехай $n(x)$ - всюди визначена функція, тобто для неї виконується "нульова аксіома": $~~~\forall_x\,\exists^1_y\,[\,n(x)=y\,]$.

Для спрощення формул, квантори загальності, дія яких охоплює всю формулу, далі будуть опускатися (але матися на увазі). Перші дві аксіоми Пеано (PA), що визначають функцію $n(x)$, мають вигляд:

$$ \begin{array}{llll} (\mathbf{N_1})& n(x) \neq 0 & ~~~~~ &-&\text{перед 0 немає числа} \\ (\mathbf{N_2})& n(x)=n(y) \to x=y & &-&\text{якщо числа збігаються, то попередні їм числа рівні} \\ \end{array} $$

Аксіоми можуть виконуватися для різних інтерпретацій (зокрема, побудованих на скінченних множинах). На малюнках предметні об'єкти ("числа") позначатимемо точками,
а функцію $n(x)$ - стрілкою, що з'єднує $x$ і значення $n(x)$. Оскільки $n(x)$ визначена для всіх $x$, з кожної точки завжди має виходити одна стрілка (всюди визначена функція).

Аксіома ${\mathbf N_1}$ не виконується на інтерпретаціях, у яких скінченне число елементів, що включають $0$, з'єднані в кільце, оскільки в $0$ "потрапити" не можна (риска над ${\mathbf N_1}$ означає, що вона не виконується). Аксіома ${\mathbf N_2}$ на цій інтерпретації істинна. Таким чином, ${\mathbf N_1}$ невивідна з ${\mathbf N_2}$.

Аксіома ${\mathbf N_2}$ забороняє двом або більше стрілкам сходитися в одній точці. Праворуч аксіома ${\mathbf N_1}$ виконується, а ${\mathbf N_2}$ - ні, тому вони взаємонезалежні. Одночасно аксіоми ${\mathbf N_1}$ і ${\mathbf N_2}$ виконуються лише на нескінченних множинах. Нижче наведено зчисленну множину предметів, що утворюють модель для ${\mathbf N_1}$ і ${\mathbf N_2}$. Ця множина розбивається на чотири незв'язні підмножини $\mathbb{N}_0\cup\mathbb{N}_1\cup\mathbb{Z}_1\cup\mathbb{C}_1$:

Множини $\mathbb{N}_0,\,\mathbb{N}_1$ є "односпрямованими" нескінченними "послідовностями", причому $\mathbb{N}_0$ починається з нуля, а $\mathbb{N}_1$ нуля не містить. Їх можна "сконструювати" за допомогою раціональних чисел: $\mathbb{N}_0=\{0,\,1/2,...,\,n/(n+1),...\}$, $\mathbb{N}_1=\{1,\,1+1/2,...,\,1+n/(n+1),...\}$. Множина $\mathbb{Z}_1$ без початку і кінця: $\mathbb{Z}_1=\{...,\,3-2/3,\,3-1/2,\,3,\,3+1/2,\,3+2/3,...\}$. Четверта множина $\mathbb{C}_1$ - це кільце з будь-якого скінченного числа елементів.

Щоб міркувати про нескінченні послідовності, потрібна ще одна аксіома, що називається аксіомою математичної індукції. Вона залежить від довільного предиката $P(x)$: $$ (\mathbf{I})~~~~~~~~~~~~~P(0)~\to~\bigr(\,\forall_x\,\bigr[P(x)\to P(n(x))\bigr]~~\to~~ \forall_x\,P(x)\,\bigr). $$ Насправді це "схема аксіом", тобто нескінченна множина формул, з будь-якими мислимими властивостями $P(x)$. Через правило modus ponens (MP): $P,~P\to Q~\Rightarrow~Q$, ця аксіома еквівалентна правилу виводу: $$ (\mathbf{Ind})~~~~~~~P(0),~~~~~\forall_x\,\bigr[P(x)\to P(n(x))\bigr]~~~~~\Rightarrow~~~~~ \forall_x\,P(x). $$ Воно означає, що якщо $0$ володіє властивістю $P$ (база індукції) і для будь-якого $x$, що володіє $P$, випливає, що цією властивістю володіє і наступне за ним число $n(x)$, то можна укласти, що властивістю $P$ володіють усі числа.

Покажемо, що аксіома індукції забороняє модель типу $\mathbb{N}_0\cup\mathbb{N}_1$ з попереднього малюнка, а, отже, незалежна від аксіом $\mathbf{N_1},\,\mathbf{N_2}$. Точніше доведемо, що заборонені множини типу $\mathbb{N}_1$, в яких є ненульовий елемент, що не має попереднього:

$\forall_x\,\bigr[x\neq 0~\to~\exists_y\,(\,n(y)=x\,)\bigr]$
Для будь-якого ненульового $x$ існує попереднє йому число $y$.
$\lhd$ В аксіому $\mathbf{I}$ замість $P(x)$ підставимо формулу $x\neq 0~\to~\exists_y\,(\,n(y)=x\,)$ без квантора $\forall_x$.
$(1)$ У базі $P(0)$ посилка $0\neq 0$ хибна, тому, незалежно від наслідку, база $P(0)$ істинна $(\F\to A\equiv \T)$.
$(2)$ $P(n(x))$ дорівнює $n(x)\neq 0~\to~\exists_y\,[\,n(y)=n(x)\,]$. Яким би не був $x$, наслідок $\exists_y\,[\,n(y)=n(x)\,]$ істинний, оскільки існуючий $y=x$. Тому $P(n(x))$ істинне і через $A\to \T\equiv \T$ істинне $P(x)\to P(n(x))$ при будь-якому $x$. $\square$
Зауважимо, що в доведенні аксіоми $\mathbf{N_1},~\mathbf{N_2}$ не брали участі.

Заборонити послідовності $\mathbb{Z}_1$ або $\mathbb{С}_1$, що не містять нуля, складніше. Більш того, можна довести, що, яку б аксіоматику ми не обрали, завжди існують інтерпретації неізоморфні ряду натуральних чисел (т.зв. нестандартні моделі арифметики).

Додавання і множення

Додамо в сигнатуру натуральних чисел бінарні (два аргументи) функції додавання $x+y$ і множення $x\cdot y$. Нехай при будь-яких $x,y$ властивості додавання індуктивно визначають наступні дві аксіоми: $$ (\mathbf{A_1})~~~~~~~~~x+0 ~=~ x,~~~~~~~~~~~~~~~~~~~(\mathbf{A_2})~~~~~~~~~ n(x+y) ~=~ x+n(y). $$ Якщо в $\mathbf{A}_2$ покласти $y=0$ і врахувати $\mathbf{A}_1$, то отримується $n(x)=x+1$, де $1=n(0)$ - нова предметна константа, відмінна за $\mathbf{N}_1$ від $0$. Додамо її в сигнатуру. У результаті, аксіоми для додавання і множення можна записати в більш "звичному" вигляді:

$$ \begin{array}{llll} (\mathbf{A_1})~~~ & x+0 ~=~ x,\\ (\mathbf{A_2})~~~& (x+y)+1 ~=~ x+(y+1),\\ \end{array} ~~~~~~~~~~~~~~~~~~~~~~~~ \begin{array}{llll} (\mathbf{M_1})~~~& x\cdot 0 ~=~ 0,\\ (\mathbf{M_2})~~~& x\cdot (y+1)~=~x+(x\cdot y).\\ \end{array} $$

Сукупність семи формул $\mathbf{N_1},\mathbf{N_2},\mathbf{I},\mathbf{A_1},\mathbf{A_2},\mathbf{M_1},\mathbf{M_2}$ складають систему аксіом Пеано (PA) арифметики.
Як приклад, виведемо з цих аксіом комутативність і асоціативність функції додавання.

$({\bf AC_0})~~~~~x+0 ~=~ 0+x.$
$\lhd$ Покладемо в правилі індукції $P(x):~~x+0=0+x$. База очевидно істинна: $P(0):~~0+0=0+0$.
Нехай вірно $P(x)$. Доведемо істинність $P(x+1)$, записуючи над рівністю використовувану при виведенні формулу: $$ (x+1)+0 ~~\overset{\bf A_1}{=}~~x+1 ~~\overset{\bf A_1}{=}~~(x+0)+1 ~~\overset{P(x)}{=}~~(0+x)+1 ~~\overset{\bf A_2}{=}~~0+(x+1). $$ Рівність першого $(x+1)+0$ та останнього $0+(x+1)$ термів і є формула $P(x+1)$. У результаті з аксіом $\mathbf{A_1},~\mathbf{A_2}$ випливає $P(x)\to P(x+1)$, тому вивідна формула $\forall_x\,[\,P(x)\to P(x+1)\,]$, а за індукцією $\mathbf{I}$ вивідна $\forall_x\,P(x)$. $\square$

🔥 Це доведення для стислості наведено в алгебраїчному стилі. Запис $t_1=t_2=t_3$ - це скорочення, еквівалентне: $~~t_1=t_2,~~t_2=t_3~~~\Rightarrow~~~t_1=t_3$ (транзитивність). Перша рівність - це наслідок аксіоми $\mathbf{A}_1$ (зараз пишемо квантор $\forall$, якщо він є): $$ \forall_x\, (x+0=x)~~~~~\Rightarrow~~~~~x+0=x~~~~~\Rightarrow~~~~~(x+1)+0 = x+1, $$ де застосовані правила виводу $\forall_x\,Q(x)~~\Rightarrow~~Q(x)~~\Rightarrow~~Q(t)$ для терма $t=x+1$ (підстановка). Таким чином, ми маємо $\mathbf{A_1},~\mathbf{A_2},~P(x)~~\Rightarrow~~P(x+1)$, тому $\mathbf{A_1},~\mathbf{A_2}~~\Rightarrow~~P(x)\to P(x+1)$. Якщо тільки з аксіом теорії випливає деяка формула з параметром, то на нього можна навісити квантор загальності (правило узагальнення): $\text{Axioms}~~\Rightarrow~~~Q(x)~~\Rightarrow~~\forall_x\,Q(x)$. Дійсно, якщо з $\text{Axioms}$ випливає формула $Q(x)$ з параметром $x$, то вона повинна бути істинна завжди, коли істинні аксіоми, при будь-якому значенні $x$.

$({\bf AC_1})~~~~~(y+x)+1 ~=~(y+1)+x.$
$\lhd$ Покладемо $P(x):\,\forall_y\,\bigr[\,(y+x)+1=(y+1)+x\,\bigr]$. База $P(0)$ істинна: $(y+0)+1 ~~\overset{\bf A_1}{=}~~y+1 ~~\overset{\bf A_1}{=}~~(y+1)+0. $
Доведемо що з $P(x)$ випливає $P(x+1)$: $$ (y+(x+1))+1 ~~\overset{\bf A_2}{=}~~ ((y+x)+1)+1 ~~\overset{ P(x)}{=}~~ ((y+1)+x)+1 ~~\overset{\bf A_2}{=}~~ (y+1)+(x+1). $$ Рівність першого і останнього термів, це формула $P(x+1)$, тому $P(x)\to P(x+1)$. $\square$

$({\bf AC})~~~~~x+y~=~y+x. $
$\lhd$ $P(y):\forall_x\,(x+y=y+x)$. База $P(0)$: $x+0=0+x$ доведена в $({\bf C_0})$. Виведемо з $P(y)$ формулу $P(y+1)$.
$$ x+(y+1)~~\overset{\bf A_2}{=}~~(x+y)+1~~\overset{P(y)}{=}~~(y+x)+1 ~~\overset{\bf AC_1}{=}~~(y+1)+x.~~~\square $$

Звернемо увагу, що в $({\bf N_1,N_2,I,A_1,A_2})$ немає безпосереднього твердження про комутативність додавання. Мабуть цьому варто здивуватися.

Доведемо на завершення асоціативність додавання:

$({\bf AA})~~~~~x+(y+z) ~=~ (x+y)+z.$
$\lhd$ Нехай $P(z):~ \forall_{x,y}\,[x+(y+z)=(x+y)+z]$. База $P(0)$ істинна за аксіомою ${\bf A_1}$. Нехай $P(z)$, доведемо $P(z+1)$: $$ x+(y+(z+1)) ~~\overset{\bf A_2}{=}~~ x+((y+z)+1) ~~\overset{\bf A_2}{=}~~ (x+(y+z))+1. ~~\overset{P(z)}{=}~~ ((x+y)+z)+1 ~~\overset{\bf A_2}{=}~~ (x+y)+(z+1).~~~\square $$

Геометрія

Розглянемо як другий приклад частину аксіом Гільберта для планіметрії (двовимірної геометрії). Нехай є два види об'єктів - точки $x,y,...\in\mathcal{P}$ і прямі $\alpha,\beta...\in\mathcal{L}$. Ми не наділяємо їх ніякими образними властивостями. Це елементи двох абстрактних множин $\mathcal{P}$ і $\mathcal{L}$. Констант і функцій у теорії не буде.
Як перший предикат візьмемо предикат рівності об'єктів однієї множини $x=y$ або $\alpha=\beta$. Нерівність визначається за допомогою логічного заперечення: запис $x\neq y$ це скорочення для $\neg(x=y)$.
Другий предикат $(x\in\alpha)$ у "неформальній геометрії" відповідає фразам: "точка $x$ належить прямій $\alpha$" або "пряма $\alpha$ проходить через точку $x$". Для скорочення ми будемо також використовувати похідні предикати $(x,y\in\alpha)$ - це $~(x\in\alpha)\,\&\,(y\in\alpha)$ (точки $x,\,y$ лежать на прямій $\alpha$) або $(x\in \alpha,\beta)$ - це $~(x\in\alpha)\,\&\,(x\in\beta)$ (прямі $\alpha$ і $\beta$ перетинаються в точці $x$).

Оскільки у формальній теорії не повинно бути "очевидних", неявно передбачуваних тверджень, властивості предиката $(x\in\alpha)$ слід однозначно задавати за допомогою предметних аксіом.

$(\mathbf{A_1}):~~~~~\forall_{x,y}\,\exists_\alpha\,(x,y\in\alpha)$
Через будь-які дві точки $x,y$ проходить пряма $\alpha$ (можливо не одна).

Звідси випливає, що через будь-яку точку проходить хоча б одна пряма: $\forall_x \,\exists_\alpha \,(x\in\alpha)$ оскільки, у парах $(x,y)$ для $\forall_{x,y}$ є діагональні $(x,x)$, які також повинні бути істинними. Це правило $\forall_{x,y}\,A(x,y)~\Rightarrow\forall_x \,A(x,x)$.

$(\mathbf{A_2}):~~~~~\forall_{x,y}\,\bigr( x\neq y~\to~\forall_{\alpha,\beta}\,\bigr[\,(x,y\in\alpha)\,\&\,(x,y\in\beta)~\to~ \alpha=\beta\,\bigr]\bigr)$
Через будь-які дві різні точки $x,y$ проходить не більше однієї прямої ($0$ або $1$).

Разом $\mathbf{A_1}\,\&\,\mathbf{A_2}$ означають, що "через дві різні точки повинна проходити одна і тільки одна пряма".

$(\mathbf{A_3}):~~~~~\forall_{\alpha}\,\exists_{x,y}\, \bigr[\,x\neq y ~\,\&\, ~(x,y\in\alpha)\,\bigr]$
На будь-якій прямій $\alpha$ знаходиться принаймні дві різні точки $x,y$.

$(\mathbf{A_4}):~~~~~\exists_{x,y,z}\,\bigr[\,x\neq y\neq z ~\,\&\, ~\forall_{\alpha}\,\neg (x,y,z\in\alpha)\,]$
Існують принаймні три різні точки $x,y,z$, що не належать одній прямій $\alpha$.

Скорочений запис $x\neq y\neq z$ означає кон'юнкцію трьох предикатів: $(x\neq y)\,\&\,(x\neq z)\,\&\,(y\neq z)$ і, як і в попередній аксіомі, під квантором існування залишає тільки різні $x,y,z$. Ця аксіома вимагає вже не менше трьох точок і "двох вимірів" ($\mathbf{A_1}$-$\mathbf{A_3}$ виконуються і для точок, що лежать на єдиній прямій). При цьому не обов'язкове існування таких точок для кожної прямої. Достатньо хоча б однієї трійки.
З $\mathbf{A_4}$ випливає, що для будь-якої прямої є хоча б одна точка, яка на ній не знаходиться: $\forall_\alpha\,\exists_x\,\neg(x\in \alpha)$. Дійсно, ті три точки, що існують за $\mathbf{A_4}$, або не знаходяться на даній прямій $\alpha$, або на ній знаходиться не більше двох з них $\square$. У принципі, замість аксіоми $\mathbf{A_4}$ можна взяти формулу $\forall_\alpha\,\exists_x\,\neg(x\in \alpha)$, оскільки разом з $\mathbf{A_3}$ вона дає сильну версію $\mathbf{A_4}$.

Для запису п'ятої аксіоми про паралельні, визначимо предикат від трьох аргументів: $$ \text{Par}(x,\alpha,\beta):~~~~~~(x\in\beta)~\,\&~\neg \exists_y (y\in\alpha,\beta), $$ що означає: "через точку $x$ проходить пряма $\beta$, паралельна прямій $\alpha$". Паралельність розуміється в сенсі відсутності спільних точок у прямих ("не існує спільної точки $y$ для прямих $\alpha$ і $\beta$"). Як і будь-який предикат, при одних значеннях аргументів, він може бути істинним, а при інших - хибним.

$(\mathbf{A_5}):~~~~~\forall_{x}\,\forall_\alpha\,\bigr( \neg(x\in \alpha) ~\to~ \forall_{\beta,\gamma}\, \bigr[\,\text{Par}(x,\alpha,\beta)\,\&\,\text{Par}(x,\alpha,\gamma)~\to~\beta=\gamma\,]\bigr)$
Для будь-якої точки $x$ і прямої $\alpha$, якій $x$ не належить, проходить не більше однієї ($0$ або $1$) прямої, паралельної $\alpha$.

Для повного опису планіметрії необхідні також відношення "між" $B(x,y,z)$: "точка $y$ знаходиться між точками $x$ і $y$" і відношення конгруентності (геометрична рівність відрізків і кутів). Їхні властивості також задаються відповідними групами аксіом. З цих аксіом можна вивести теорему:

$(\mathbf{T_5}):~~~~~\forall_{x}\,\forall_{\alpha} \bigr[\,\neg(x\in \alpha) ~\to~\,\exists_\beta ~\text{Par}(x,\beta,\alpha)\,\bigr]$
Паралельних прямих повинно бути не менше однієї.

Тому, разом з $\mathbf{A_5}$ маємо евклідове твердження $\mathbf{E}=\mathbf{A_5}\,\&\,\mathbf{T_5}$ про те, що паралельна до $\alpha$ пряма $\beta$, що проходить через точку $x$, яка не лежить на $\alpha$, завжди одна і тільки одна.

Аналіз аксіом геометрії

Покажемо несуперечність сформульованих вище п'яти аксіом геометрії для відношення $(x\in\alpha)$:

На першому малюнку (моделі) усі п'ять аксіом істинні. Підкреслимо, що малюнок не несе жодного геометричного навантаження і відіграє лише роль переліку об'єктів і значень істинності предиката $(x\in\alpha)$. Так, для точок і прямих обрано множини з трьох елементів: $\mathcal{P}=\{a,b,c\}$ і $\mathcal{L}=\{\alpha,\beta,\gamma\}$. На цих множинах задані значення істинності предиката так, що $(b\in\alpha)\equiv (c\in\alpha)\equiv \T $, а $(a\in\alpha)\equiv \F $ і т.д. Оскільки $\mathbf{A_5}$ дозволяє відсутність паралельних прямих ("не більше однієї"), то вона на цій інтерпретації також істинна. А от теорема Евкліда $\mathbf{E}$ хибна (немає паралельних прямих), що позначено рискою над $\mathbf{E}$. Аналогічна друга модель.

У третій моделі є чотири точки і шість прямих: $\mathcal{L}=\{\alpha,\beta,\gamma,\delta,\sigma,\epsilon\}$. На цій інтерпретації істинні як $(\mathbf{A_1}-\mathbf{A_5})$, так і $\mathbf{E}$. Паралельними прямими є: $(\alpha,\epsilon)$, $(\beta,\delta)$ і $(\gamma,\sigma)$. Звернемо увагу, що в центрі прямі не перетинаються (точками є тільки чорні кружки). Четверта модель ізоморфна третій.

Ізоморфізм двох моделей у даному випадку означає, що існують перестановки точок $x'=f(x)$ і прямих $\alpha'=g(\alpha)$ при яких $(x\in\alpha)~\leftrightarrow~(x'\in\alpha')$ для всіх $x$ і $\alpha$. Наприклад, інтерпретація на останній картинці описується таблицею, наведеною праворуч (крапка - відношення істинне). У даному випадку можливо $720$ нееквівалентних перестановок рядків і колонок цієї таблиці, а, отже, $720$ ізоморфних інтерпретацій.

Наведемо інтерпретації, що доводять незалежність аксіом $(\mathbf{A_1}-\mathbf{A_5})$ (рискою позначаємо хибну в даній інтерпретації аксіому):

Природно в останньому випадку прямі перетинаються тільки в "жирних точках", тобто в цій інтерпретації є п'ять точок і десять прямих. Зокрема, до прямої $\alpha$ паралельні дві прямі $\beta$ і $\gamma$.

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

Праворуч наведені інтерпретації, що доводять несуперечність і незалежність цих формул. Як ми бачили в попередньому розділі $\mathbf{A}_1~\vdash~\mathbf{T}_1$, а для доведення $\mathbf{T_2}$ необхідні $\mathbf{A_1},\,\mathbf{A_3}$.

Наведені вище аксіоми не утворюють повної теорії, хоча в цілому геометрія на площині повна. Для отримання повної теорії, необхідно додати ще два відношення і відповідні їм аксіоми. Неповнота аксіом $(\mathbf{A}_1-\mathbf{A}_5)$ зокрема випливає з існування скінченних неізоморфних моделей цієї теорії.

При побудові геометрії можна обирати інші сигнатури та аксіоми. Наприклад, в аксіоматиці Тарського існують тільки точки. Їхні властивості задають три базові предикати: рівності $x=y$, конгруентності $(x,y \cong u,v)$ і знаходження між $B(x,y,z)$. Пряма (точніше відрізок) визначається двома точками $\alpha=(x,y)$, а квантор належності це $z\in\alpha ~~\Leftrightarrow~~B(x,z,y)$. Семантично конгруентність $(x,y \cong u,v)$ означає рівність довжин відрізків $(x,y)$ і $(u,v)$. Аксіоми Тарського визначають властивості цих предикатів. Наприклад, для будь-яких точок конгруентність "рефлексивна" $(x,y \cong y,x)$, транзитивна $(x,y \cong u,v)\,\&\,(x,y \cong s,t)~\to~(u,v \cong s,t)$ і "ідентична" $(x,y \cong z,z)~\to~x=y$ (нульовий відрізок).

Трохи філософії

Теорія множин в певному сенсі особлива теорія. Раніше, розглядаючи формальні теорії, ми посилалися на множини предметів, якими "пробігалися" квантори $\forall_x$ і $\exists_x$. Очевидно, що при побудові аксіоматики теорії множин такий підхід не годиться.

Теорія множин повинна будуватися як гра в слова в чистому вигляді. Немає істинних чи хибних тверджень.
Немає причин сумніватися в існуванні будь-яких об'єктів, оскільки ці об'єкти визначені у вигляді слів. Промовлене слово вже існує. Можна вважати, що деякі слова (об'єкти) недопустимі (не існують). Але це буде вже інша (цілком можливо також допустима) гра в слова. Втім, якщо в процесі породження слів виникають протиріччя, правила гри або вихідні слова (аксіоми) необхідно, звичайно, змінювати.

Наприклад, нехай є сигнатура з відношенням $B(x,y)$, властивості якого визначає єдина аксіома: $\exists_b\,\forall_x\,\bigr[\,B(b,x)~\leftrightarrow~\neg B(x,x)\,\bigr]$. Вона стверджує існування деякого об'єкта $b$. Змістовно ця теорія відповідає історії про цирульника $b$, який голить усіх таких і тільки таких $x$ які не голяться самі. Неважко бачити, що ця теорія суперечлива (коли будь-який $x$ дорівнює $b$). Тому вона беззмістовна і такого цирульника не існує, хоч його визначення і написане. Зауважимо, що якщо прибрати зворот " і тільки таких" (замінивши $\leftrightarrow$ на $\to$), теорія одразу стане осмисленою, а цирульник існуючим і таким, що не голиться $~~\Rightarrow~\neg B(b,b)$. А при фразі "кожного, хто не голиться, голить цирульник": $\neg B(x,x)~\to~B(b,x)$, цирульник голиться $\Rightarrow~~ B(b,b)$.

Більшість математиків є платоністами і вірять в об'єктивне існування математичних конструкцій та апріорну істинність чи хибність математичних тверджень. Як і будь-яка філософія, вона виглядає підозрілою, однак той, хто сумнівається в існуванні написаного слова, стає ще більшим платоністом, ніж той, хто його написав. Тому будемо вважати, що "існують" актуально нескінченні множини і множини всіх їхніх підмножин, оскільки визначення цих об'єктів записані на папері. При цьому до неприємностей необхідно завжди бути готовим.

Множини

Будемо мати справу з об'єктами $x,y,z,...$, які в семантичному підході інтерпретуються як множини. Нічого крім множин не існує. Усі математичні конструкції (числа, точки тощо) визначаються як множини спеціального вигляду. Множини можуть збігатися $x=y$ і одна множина може належати іншій: $x\in y$, що б це не означало (в сигнатурі теорії є два відношення).

Частина наступних далі аксіом не є незалежними і це буде позначатися штрихом. Тим не менш твердження, що декларуються в них, є концептуально важливими. Незважаючи на те, що всі міркування про множини можна проводити суто синтаксично (гра в слова), ми будемо спрощувати собі життя, використовуючи семантику. У наших напівформальних міркуваннях будуть використані поняття істини і хиби, а також звичайна булева і кванторна алгебри.

$(\mathbf{ZF_=})$: $~~~~~~\forall_{x,y}\,\bigr[\,\forall_z\,(z\in x~\leftrightarrow~z\in y)~\to~x=y\,\bigr]$
Якщо дві множини $x,y$ містять одні й ті самі елементи, то вони рівні.

Ця аксіома об'ємності в "наївній теорії множин" означає, що сукупність $\{a,b,a,a,a\}$ те саме, що множина $\{a,b\}$. Іншими словами множина - це об'єднання попарно розрізнюваних елементів, кожен з яких перебуває в єдиному числі і порядок перерахування елементів у множині ролі не грає.

Оскільки $A\leftrightarrow B$ еквівалентно $(A\to B)\,\&\,(B\to A)$, за допомогою правила об'єднання, посилку аксіоми можна переписати таким чином: $\forall_z(z\in x~\to~z\in y)~~\&~~\forall_z(z\in y~\to~z\in x)$. Імплікація під квантором загальності з "усіх можливих" $z$ "відбирає" тільки ті, які належать $x$ (тоді вони належать і $y$) і навпаки. Це і означає, що $x,y$ "містять" однакові елементи. Використовуючи базовий символ сигнатури, визначимо відношення "$x$ підмножина $y$" і "$x$ строга підмножина $y$": $$ x \subseteq y~~~~~\Leftrightarrow~~~~~\forall_z\,(z\in x ~~\to~~z\in y),~~~~~~~~~~~~~~~~~~~~~~ x\subset y~~~~~\Leftrightarrow~~~~~x\subseteq y~\&~x\neq y. $$ Тепер першу аксіому можна переписати в такому вигляді: $x\subseteq y~\,\&\,~y\subseteq x~~\to~~x=y$. Очевидно, що $x\subseteq x$.

У "наївній теорії множин" наприклад $\{a,b\} \subset \{a,b,c\}$. При цьому $a\in \{a,b\}$, але $a\not\subset \{a,b\}$, а от $\{a\}\subset\{a,b\}$. Іншими словами всередині $\{...\}$ перераховуються елементи множини. Частина з них знову у фігурних дужках утворюють підмножину. При цьому важливо відрізняти $a$ і $\{a\}$ (множина з одного елемента $a$).

Строга підмножина володіє властивостями строгого порядку. Для будь-яких $x,y,z$ вона антирефлексивна, транзитивна і асиметрична (остання виводиться з перших двох властивостей): $$ \neg(x\subset y),~~~~~~~~~~~x\subset z~\to~(z \subset y ~\to~x\subset y),~~~~~~~~~~~~~x\subset y ~\to~\neg(y\subset x). $$

Аксіоми Цермело-Френкеля

Наступні аксіоми стверджують факт "існування" тих чи інших множин. При цьому важливо, що кожна нова множина отримується з уже побудованих (раніше визначених) множин. Це дозволяє уникнути ряду "парадоксів" наївної теорії множин.

$(\mathbf{ZF'_2})$: $~~~~~~\forall_{x,y}\,\exists_s\,\forall_z\,\bigr[\,(z=x\vee z=y) ~\leftrightarrow~z\in s\,\bigr]$
Будь-які дві множини $x,y$ і тільки вони можуть бути елементами множини $s$.

Існуюча за аксіомою пари множина з двох елементів позначається як $s=\{x,y\}$. Фігурні дужки в даному випадку відіграють роль предметних функцій з довільним числом аргументів. Зокрема, ця сама аксіома "дозволяє" існування й одноелементних множин $\{x\}$ (коли $x$ і $y$ збігаються).

Втім, існування хоча б однієї множини випливає з рефлексивності рівності: $\forall_x\,(x=x)$ і загальнозначущої формули $\forall_x P~\to~\exists_x\,P$, що дають $\exists_x\,(x=x)$.

Два елементи множини $\{x,y\}$ невпорядковані: $\{y,x\}$ це те саме, що і $\{x,y\}$. Однак за допомогою пари можна визначити впорядковану пару $(x,y)$ таким чином: $(x,y)~=~\{~\{x\},~\{x,y\}~\}.$ При цьому $(y,x)\neq (x,y)$.

$(\mathbf{ZF_P})$: $~~~~~~\forall_x\,\exists_s\,\forall_z\,\bigr[\,(z\in x~\,\&\,~P(z))~\leftrightarrow~z\in s \bigr]$
Для будь-якої множини $x$ існує її підмножина $s$, всі елементи якої володіють властивістю $P$.

Ключовим у цій аксіомі виділення є використання вже існуючої множини $x$ для побудови (виділення з $x$) множини $s$. У "наївній теорії множин" ця аксіома виглядала так: $\exists_s\,\forall_z\,\bigr[\,P(z) ~\leftrightarrow~z\in s\,\bigr]$. Якщо в ній замість $P(z)$ покласти $z\not\in z$, еквівалентне $\neg(z\in z)$ , то вийде $\exists_s\,\forall_z\,\bigr[\,z\not\in z ~\leftrightarrow~z\in s\,\bigr]$, або при $z=s$ (оскільки $z$ будь-яке) - протиріччя, яке називається парадоксом Рассела. У $\mathbf{ZF_P}$ такого протиріччя не виникає.

Підмножина елементів з даною властивістю позначається таким чином: $y=\{z\mid z\in x~\&~P(z)\}$. Природно, аксіома $\mathbf{ZF_P}$ є схемою аксіом, тобто нескінченним набором формул з різними $P(z)$.
Доведемо за допомогою $(\mathbf{ZF_P})$ таке важливе твердження:

$(\mathbf{ZF'_\varnothing})$: $~~~~~~\exists_s\,\forall_{z}\,(z\not\in s)$
Існує порожня множина $s$, що не містить інших множин.

Для цього покладемо замість $P(z)$ формулу $z\neq z$. Оскільки вона тотожно хибна, то за $\mathbf{ZF_P}$ хибним повинно бути і $z\in s$ або істинним $z\not\in s$.

Існуюча множина $s=\varnothing=\{\}=\{z\mid \F\}$ із властивістю $\forall_z\,(z\not\in\varnothing )$ єдина і її можна включити в сигнатуру. Єдиність безпосередньо випливає з аксіоми $\mathbf{ZF_=}$: дві $\varnothing$ і $\varnothing'$ складаються з однакових, хоч і відсутніх елементів, отже збігаються. Покажемо це трохи більш формально. Відношення $\varnothing \subseteq \varnothing'$, що дорівнює $\forall_z(z\in \varnothing~\to~z\in \varnothing')$, істинне (оскільки посилка хибна). Аналогічно істинне $\varnothing' \subseteq \varnothing$. Тому за $(\mathbf{ZF_=})$ ці множини збігаються: $\varnothing = \varnothing'$.

Нагадаємо, що $\varnothing=\{\}$ і $\{\varnothing\}=\{\{\}\}$ різні множини ("порожня коробка і коробка, в якій порожня коробка"). Порожня множина є підмножиною будь-якої множини: $\varnothing\subseteq y$ оскільки посилка в $\forall_z\,(z\in \varnothing ~\to~z\in y)$ хибна.

$(\mathbf{ZF_\cup})$: $~~~~~~\forall_x\,\exists_s\,\forall_z\,\bigr[\,\exists_w\,(z\in w ~\,\&\,w\in x~) ~\leftrightarrow~ z\in s\,\bigr]$
Існує множина $s$ рівна об'єднанню всіх множин, що містяться в даній множині $x$.

Семантично аксіома об'єднання означає, що якщо є, наприклад, двоелементна множина $\{\{a\},~\{b,c\}\}$, ми можемо побудувати триелементну множину: $\{a,~b,~c\}$ і т.д. Таку множину, отриману "витрушуванням" множин з елементів $x$, позначають як $\cup x = \{z\mid \exists_w\,(~z\in w\,\&\,~w\in x)\}$. З її допомогою можна визначити: $$ x\cup y ~~~~\Leftrightarrow~~~~\cup\{x,y\}~~~~\Leftrightarrow~~~~\{z\mid z\in x \vee z\in y\}. $$ Зокрема $\{a\}\cup \{b,c\} ~=~\{a,b,c\}$ і т.д.

$(\mathbf{ZF_\subseteq})$: $~~~~~~\forall_x\,\exists_s\,\forall_z\,\bigr[\,z\subseteq x ~\leftrightarrow~z\in s\,\bigr]$
Для будь-якої множини $x$ існує множина $s$, яка складається з усіх підмножин $x$ і тільки з них.

Ця аксіома степеня для даного $x$ дозволяє множину $s=\{z\mid z\subseteq x\}$. Таку множину позначають як $2^x$.

Звернемо увагу, що в усіх аксіомах "існування" множини $s$ стоїть символ еквівалентності $\leftrightarrow$ ("тоді і тільки тоді"), а не імплікації $\to$ ("якщо, то"). Пояснимо це на останній аксіомі. Формула $z\subseteq x ~\to~z\in s$ означає, що "будь-яка підмножина $z$ множини $x$ є елементом $s$". Але якщо $z$ не підмножина $x$, то $z\in s$ може бути як істинним, так і хибним. Іншими словами ця формула говорить, що множина $s$ складається з усіх підмножин $x$ і можливо ще з якихось інших елементів. Обернена імплікація $z\in s ~\to~z\subseteq x$ стверджує, що всі елементи $s$ є підмножинами $x$, але при цьому не обов'язково всіма підмножинами. Тільки об'єднання цих двох формул $(A \to B)\,\&\,(B\to A)$ в $A \leftrightarrow B$ приводить до "$s$ складається з усіх підмножин $x$ і тільки з них". У принципі, можна використовувати й ослаблену версію цієї аксіоми (без "і тільки з них").

Попередні шість тверджень декларували існування скінченних множин з будь-яким числом елементів. Наступна аксіома дозволяє існувати нескінченним множинам.

$(\mathbf{ZF_\infty})$: $~~~~~~\forall_x\,\exists_s\,\bigr[\,x\in s ~~\&~~\forall_z\,(z\in s\,\to\,\exists_w\,(z\in w~\,\&~\,w\in s)\,\bigr]$
Існує множина $s$ з нескінченним числом елементів.

Аксіома нескінченності індуктивно вводить актуальну нескінченність, як закінчену сукупність $s$.
Спочатку стверджується, що множині $s$ належить деякий довільний елемент $x$ (наприклад, $\varnothing$).
Потім, що будь-який елемент $z$ множини $s$ належить хоча б одному елементу $w$ тієї ж множини $s$.
Наприклад, якщо є $\varnothing$, то повинен бути і $\{\,\varnothing\,\}$, але тоді повинен бути і $\{\,\{\,\{\varnothing\}\,\}\,\}$ і т.д. скільки завгодно довго.

$(\mathbf{ZF_R})$: $~~~~~~\forall_x\,\bigr[\,x\neq\varnothing~\to ~\exists_z\,(z\in x~\,\&\,~\forall_w\,(w\in z~\to~w\not\in x)\,\bigr]$
Кожна непорожня множина $x$ містить елемент $z$, який не має спільних з $x$ елементів.

Аксіому регулярності (фундування) за допомогою функції перетину множин $x\cap y = \{\,z\mid z\in x~\&~z\in y\,\}$ можна записати у вигляді: $x\neq \varnothing ~\to~\exists_z\,(z\in x ~\&~z\cap x=\varnothing)$. Сенс її в тому, що в будь-якій непорожній множині $x$ знайдеться елемент $z$ "мінімальний" відносно відношення $\in$ (тобто немає $w$ з такою самою властивістю $w\in x$).
У множині $x=\{\{a,b\},~a\}$ такий $z=a$. При цьому $a$ не може залежати від себе ж (див. нижче). Вона також забороняє більш хитрі рекурсивні зв'язки. Якщо $x=\{a,\,b\}$, то $(a\not\in b~\vee~b\not\in a)$.

З аксіом регулярності і пари випливає що жодна множина не може бути своїм елементом: $z\not\in z$.
Від супротивного: нехай $z\in z$. За аксіомою пари є множина $x=\{z\}$. Вона не порожня і тому $z\cap x=\varnothing$.
Але це не так, оскільки $z\in z$ і $z\in x$, тобто $z$ належить перетину.

З цієї ж аксіоми випливає, що не існує нескінченного ланцюжка вкладених множин: $ ... \in x_2 \in x_1$, тобто число парних фігурних дужок завжди скінченне.

Нехай скінченна множина $x$, складається з $n$ непорожніх, непересічних множин $w$. "Очевидно", що взявши з кожної множини $w$ по елементу $z$, можна побудувати нову множину $s$ з $n$ елементами. Ця множина перетинатиме кожну вихідну множину рівно на одному елементі. Для нескінченного числа множин такий спосіб побудови нової множини не цілком "самоочевидний" і повинен регламентуватися аксіомою вибору.

Натуральні числа як множини

У платонівському світі математичних ідей немає нічого крім множин. Будь-які сутності, які в наївній теорії множин були елементами множин, але самі множинами не були, тепер повинні визначатися через множини. Таким чином вся математика далі будується за допомогою слів про множини. Визначимо, наприклад, множину натуральних чисел $\mathbb{N}=\{0,1,2,...\}$, використовуючи ідею фон Неймана.

Нехай множина $\varnothing$ еквівалентна числу $0$. Введемо множину з одного елемента: $\{0\}$ або $\{\, \varnothing \,\}$. Усі інші натуральні числа будемо будувати за схемою: якщо $x\in \mathbb{N}$, то $n(x)=x+1~=~x\cup \{x\}$ також належить $\mathbb{N}$: $$ 0:=\varnothing,~~~~~~~1:=\{0\}=\{\, \varnothing \,\},~~~~~~~~~2:=\{0,1\}=\{\, \varnothing,~ \{\, \varnothing \,\} \,\}, ~~~~~~~~ 3:=\{0,1,2\} = \{\, \varnothing,~ \{\, \varnothing \,\},~\{\, \varnothing,~ \{\, \varnothing \,\} \,\} \,\}. $$ Їхнє об'єднання утворює $\mathbb{N}$. Природно, необхідно далі показати, що введені подібним чином слова володіють звичними арифметичними властивостями. Наприклад, одразу видно, що вони лінійно впорядковані, де як відношення порядку виступає відношення строгої підмножини: $x\lt y~~\Leftrightarrow~~x\subset y$ (порожня множина є підмножиною будь-якої множини): $$ 0 ~\lt~1~~~\Leftrightarrow~~~ \varnothing \subset \{\,\varnothing\,\},~~~~~~~~~~~~ 1 ~\lt~2~~~\Leftrightarrow~~~ \{\varnothing\} \subset \{\varnothing,~\{\varnothing\}\},~~~~~~~~~~~~ 0 ~\lt~2~~~\Leftrightarrow~~~ \varnothing \subset \{\varnothing,~\{\varnothing\}\},... $$ Лінійний порядок означає, що для будь-яких $x,y$ справедливо $(x\lt y) \vee (y\lt x) \vee (x=y)$. Зауважимо, що для даної сукупності множин лінійний порядок задає і відношення $x\in y$ (хоча в загальному випадку для нього транзитивність $x\in y~\&~y\in z~\to x\in z$ не виконується).

Якби ми визначили числа як множини $0:=\varnothing,~~1:=\{\varnothing\},~~2:=\{\{\varnothing\} \},~~ ~~3:=\{\{\{\varnothing\}\}\}$, то лінійний порядок не можна було б ввести, ні за допомогою підмножин, ні за допомогою належності ($0\not\in 2$).
Інший спосіб $~~~0:=\varnothing,~~1:=\{\varnothing\},~~2:=\{\varnothing,~\{\varnothing\} \}, ~~3:=\{\varnothing,~\{\varnothing\},~\{\{\varnothing\}\}\}, ....$, лінійно впорядкований за $x\subset y$, але в ньому складно компактно виразити $n+1$ через $n$.

Впорядковані множини

Відношення in та on