Logika i teoria mnogości/Aksjomaty teorii mnogości

Aksjomaty Zermela-Fraenkla

Aksjomat jednoznaczności

${\mathrm{\forall }}_{A,B}A=B⟺({\mathrm{\forall }}_{x}x\in A⟺x\in B)$

Aksjomat ten mówi, że jedynym kryterium, które rozstrzyga o tym, czy dane zbiory są takie same, jest to jakie elementy się w nim znajdują. Nie istnieje natomiast żadna inna cecha, która może wpływać na równość zbiorów. Z drugiej strony - jeżeli chcemy pokazać, że dane dwa zbiory są równe należy pokazać, że wszystkie elementy należące do jednego z nich, należą też do drugiego i odwrotnie. Żeby pokazać, że dwa zbiory są różne, należy znaleźć element, który należy tylko do jednego z nich.

Zawieranie zbioru A w zbiorze B jest własnością, którą przypisujemy, gdy zachodzi następujący warunek:

${\mathrm{\forall }}_{A,B}A\subset B⟺({\mathrm{\forall }}_{x}x\in A\Rightarrow x\in B)$

Mówimy czasami też, że A jest podzbiorem zbioru B.

Przy oznaczaniu nie panuje jednomyślność - czasami używa się też następującego, równoważnego symbolu: $A\subseteq B$, który dodatkowo podkreśla możliwość równości zbiorów - formalnie oznacza jednak to samo i dlatego, w dalszej części książki będzie stosowany $\subset$. Natomiast symbol $⊊$ oznacza:

$A⊊B⟺(A\subset B\wedge A=B)$.

Podzbiór spełniający powyższą właściwość nazywany jest podzbiorem właściwym.

Uwaga 1: $A\subset B⟺B\supset A$, $A\subseteq B⟺B\supseteq A$ itd.

Uwaga 2: ${\mathrm{\forall }}_{A,B}A=B⟺(A\subset B\wedge B\subset A)$.

Aksjomat zbioru pustego

${\mathrm{\exists }}_{\mathrm{\varnothing }}{\mathrm{\forall }}_{x}x\in ̸\mathrm{\varnothing }$

Aksjomat mówi, że istnieje zbiór, do którego nie należy żaden element - innymi słowy zbiór pusty. Znak $\mathrm{\varnothing }$ jest standardowym oznaczeniem zbioru pustego. Co więcej - na podstawie aksjomatu jednoznaczności możemy zauważyć, że istnieje tylko jeden taki zbiór.

Dowód:

Niech ${\mathrm{\varnothing }}_1,{\mathrm{\varnothing }}_2$ - dwa zbiory puste. Na mocy aksjomatu zbioru pustego zachodzi:

${\mathrm{\forall }}_{x}x\in ̸{\mathrm{\varnothing }}_1$

${\mathrm{\forall }}_{x}x\in ̸{\mathrm{\varnothing }}_2$

A tym samym - ${\mathrm{\forall }}_{x}x\in {\mathrm{\varnothing }}_1⟺x\in {\mathrm{\varnothing }}_2$.

Z kolei na mocy aksjomatu jednoznaczności ostatnia równoważność jest równoważna równości zbiorów. Stąd ${\mathrm{\varnothing }}_1={\mathrm{\varnothing }}_2=\mathrm{\varnothing }$.

Aksjomat pary

${\mathrm{\forall }}_{A,B}{\mathrm{\exists }}_C{\mathrm{\forall }}_x(x\in C⟺x=A\vee x=B)$

Aksjomat ten postuluje istnienie dla każdej pary zbiorów istnienie takiego zbioru, którego elementami są tylko i wyłącznie te dwa zbiory i nic więcej. Dla zbiorów A i B taki zbiór oznaczamy przez $\{A,B\}$. Warto zwrócić tutaj uwagę, że kolejność wypisywania elementów nie ma znaczenia, tzn. $\{A,B\}$=$\{B,A\}$.

Uwaga 1: $\mathrm{\varnothing }=\{\mathrm{\varnothing }\}=\{\mathrm{\varnothing },\mathrm{\varnothing }\}$ - zarówno równość jak i nierówność wynikają z aksjomatu jednoznaczności.

Uwaga 2: Dysponując wymienionymi aksjomatami możemy niejako wyprodukować nieskończenie wiele zbiorów. Zauważmy: $\mathrm{\varnothing }$, $\{\mathrm{\varnothing }\}$, $\{\{\mathrm{\varnothing }\}\}$, ...

Aksjomat sumy

${\mathrm{\forall }}_A{\mathrm{\exists }}_{\bigcup A}{\mathrm{\forall }}_y({\mathrm{\exists }}_{x\in A}y\in x⟺y\in \bigcup A)$

Dla każdego zbioru A istnieje zbiór którego elementami są elementy elementów zbioru A. Jest to pojęcie dużo ogólniejsze od zwyczajnej, "naturalnej" sumy, którą można teraz łatwo zdefiniować:

$A\cup B=\bigcup \{A,B\}$

Aksjomat zbioru potęgowego

${\mathrm{\forall }}_A{\mathrm{\exists }}_{𝒫(A)}{\mathrm{\forall }}_x(x\subset A⟺x\in 𝒫(A))$

Dla każdego zbioru A istnieje zbiór składający się tylko i wyłącznie z jego podzbiorów. Zbiory takie nazywamy zbiorami potęgowymi danego zbioru A. Czasami pojawia się też równoważne oznaczenie: $2^A=𝒫(A)$.

Uwaga 1: ${\mathrm{\forall }}_{X}X\in 𝒫(X)\wedge \mathrm{\varnothing }\in 𝒫(X)$

Aksjomat zastępowania

Niech P(X,Y) - dwuargumentowy predykat.

$({\mathrm{\forall }}_x\mathrm{\exists }{!}_{y}P(x,y))\Rightarrow \left({\mathrm{\forall }}_A{\mathrm{\exists }}_B{\mathrm{\forall }}_b\right(b\in B⟺{\mathrm{\exists }}_{a}a\in A\wedge P(a,b)\left)\right)$

Niech istnieje warunek dwuargumentowy P taki, że jeżeli P(q,p) i P(q,r) jest prawdą, to zachodzi p=r.

Wówczas dla każdego zbioru A istnieje taki zbiór, który składa się tylko z tych elementów, które odpowiadają elementom zbioru A względem predykatu P.

Predykat tego typu bywa nazywany predykatem funkcyjnym, ponieważ można go zastąpić funkcją (pojęcie i definicja funkcji pojawi się w dalszej części książki). Poprzednik implikacji jest właśnie warunkiem predykatu funkcyjnego.

Intuicyjnie powyższy aksjomat możemy rozumieć następująco: jeżeli mamy jakieś elementy, spośród których możemy wskazać zbiór A, a każdy element możemy jednoznacznie połączyć w parę z innym elementem, to możemy też wskazać zbiór elementów sparowanych z elementami zbioru A.

Aksjomat wycinania

Czasami podając aksjomatykę teorii mnogości zamiast aksjomatu zastępowania podaje się słabszy aksjomat wycinania. Aksjomat ten można wyprowadzić z powyższych aksjomatów (dlatego nie jest potrzebny, jeżeli przyjmujemy aksjomat zastępowania), mimo to warto go tutaj zaprezentować:

Niech P - jednoargumentowy predykat.

${\mathrm{\forall }}_A{\mathrm{\exists }}_B{\mathrm{\forall }}_x(x\in B⟺x\in A\wedge P(x))$

Czyli dla każdego zbioru A istnieje taki jego podzbiór B, który składa się tylko z tych elementów zbioru A, które spełniają predykat P.

Dowód aksjomatu wycinania na gruncie aksjomatu zastępowania i aksjomatu zbioru pustego przebiega następująco: niech P₁ - predykat jednoargumentowy, taki jak w aksjomacie wycinania, niech P₂ - predykat dwuargumentowy, taki jak w aksjomacie zastępowania. Dla każdego predykatu P₁ definiujemy predykat P₂ następująco:

$P_1(x)=\{\begin{array}{cc}\text{prawda}& \Rightarrow P_2(x,x)\\ \text{falsz}& \Rightarrow P_2(x,y)\end{array}$

przy czym P₁(y) jest prawdą i $y\in A$. Jeżeli taki element y nie istnieje, to zbiór B wymieniony w aksjomacie jest zbiorem pustym - $\mathrm{\varnothing }$.

Aksjomat regularności

${\mathrm{\forall }}_{A}A=\mathrm{\varnothing }\Rightarrow {\mathrm{\exists }}_{B\in A}{\mathrm{\forall }}_{C}C\in ̸A\vee C\in ̸B$

Aksjomat ten mówi tyle, że dla każdego zbioru A musi istnieć jakiś jego element a rozłączny z A tzn. nie posiadający elementów wspólnych.

Czasami rozważa się układ aksjomatów z pominięciem aksjomatu regularności - rozważane są wówczas tzw. hiperzbiory.

Uwaga 1: Z powyższego aksjomatu wynika, że $x\in ̸x$. Rozważmy zbiór {x}. W myśl aksjomatu regularności każdy element albo należy do zbioru x albo należy do zbioru {x}. Z tego wynika, że jedyny element zbioru {x} nie może należeć do zbioru x, czyli, że $x\in ̸x$.

Aksjomat nieskończoności

${\mathrm{\exists }}_{𝒩}\mathrm{\varnothing }\in 𝒩\wedge \mathrm{\forall }x(x\in 𝒩\Rightarrow (\bigcup \{x,\{x\}\})\in 𝒩)$

Istnieje zbiór $𝒩$, do którego należy zbiór pusty a także dla dowolnego elementu x zbioru $𝒩$ należy do niego również suma teoriomnogościowa tego elementu i singletonu tego zbioru: $x\cup \{x\}=\bigcup \{x,\{x\}\}$.

Uwaga 1: Szczególnym przykładem zbioru induktywnego jest zbiór liczb naturalnych, o czym można będzie przeczytać dalej.

Aksjomat wyboru

Niech X - rodzina zbiorów (czyli zbiór zbiorów) niepustych i parami rozłącznych.

${\mathrm{\forall }}_X{\mathrm{\exists }}_A({\mathrm{\forall }}_{z\in A}\mathrm{\exists }{!}_{x\in X}\mathrm{\exists }{!}_{y\in x}z=y)\wedge \left({\mathrm{\forall }}_{x\in X}\mathrm{\exists }{!}_{y\in x}{\mathrm{\forall }}_{z\in A}\right((z\in x\Rightarrow z=y)\wedge (y\in A)\left)\right)$

Zbiór A bywa nazywany selektorem.

Hipoteza continuum

Hipoteza continuum pojawi się w dalszej części książki, gdzie będzie zrozumiałe skąd się wzięła i co się z nią wiąże. Tymczasem i dla porządku jej postać w formie słownej:

Nie istnieje zbiór mocy mniejszej od mocy zbioru liczb rzeczywistych i jednocześnie mocy większej niż zbiór liczb naturalnych.

Warto zaznaczyć, że rozważa się zarówno teorie przyjmujące hipotezę continuum, jak i te przyjmujące jej zaprzeczenie.