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

Aksjomaty Zermela-Fraenkla

Aksjomat jednoznaczności

$\forall _{A,B}\ A=B\iff {\Big (}\forall _{x}\ x\in A\iff x\in B{\Big )}$

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:

$\forall _{A,B}\ A\subset B\iff {\Big (}\forall _{x}\ x\in A\Rightarrow x\in B{\Big )}$

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 $\subsetneq$ oznacza:

$A\subsetneq B\iff {\big (}A\subset B\wedge A\not =B{\big )}$.

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

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

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

Aksjomat zbioru pustego

$\exists _{\emptyset }\ \forall _{x}\ x\not \in \emptyset$

Aksjomat mówi, że istnieje zbiór, do którego nie należy żaden element - innymi słowy zbiór pusty. Znak $\emptyset$ 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 $\emptyset _{1},\emptyset _{2}$ - dwa zbiory puste. Na mocy aksjomatu zbioru pustego zachodzi:

$\forall _{x}\ x\not \in \emptyset _{1}$

$\forall _{x}\ x\not \in \emptyset _{2}$

A tym samym - $\forall _{x}\ x\in \emptyset _{1}\iff x\in \emptyset _{2}$.

Z kolei na mocy aksjomatu jednoznaczności ostatnia równoważność jest równoważna równości zbiorów. Stąd $\emptyset _{1}=\emptyset _{2}=\emptyset$.

Aksjomat pary

$\forall _{A,B}\exists _{C}\forall _{x}\ \left(x\in C\iff x=A\lor x=B\right)$

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: $\emptyset \not =\{\emptyset \}=\{\emptyset ,\emptyset \}$ - 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: $\emptyset$, $\{\emptyset \}$, $\{\{\emptyset \}\}$, ...

Aksjomat sumy

$\forall _{A}\exists _{\bigcup A}\forall _{y}\ {\Big (}\exists _{x\in A}\ y\in x\iff y\in \bigcup A{\Big )}$

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

$\forall _{A}\exists _{{\mathcal {P}}(A)}\forall _{x}\ {\Big (}x\subset A\iff x\in {\mathcal {P}}(A){\Big )}$

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}={\mathcal {P}}(A)$.

Uwaga 1: $\forall _{X}\ X\in {\mathcal {P}}(X)\wedge \emptyset \in {\mathcal {P}}(X)$

Aksjomat zastępowania

Niech P(X,Y) - dwuargumentowy predykat.

${\Big (}\forall _{x}\exists !_{y}\ P(x,y){\Big )}\Rightarrow {\bigg (}\forall _{A}\exists _{B}\forall _{b}\ {\Big (}b\in B\iff \exists _{a}\ a\in A\wedge P(a,b){\Big )}{\bigg )}$

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.

$\forall _{A}\exists _{B}\forall _{x}\ {\Big (}x\in B\iff x\in A\wedge P(x){\Big )}$

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)=\left\{{\begin{matrix}{\textrm {prawda}}&\Rightarrow P_{2}(x,x)\\{\textrm {falsz}}&\Rightarrow P_{2}(x,y)\\\end{matrix}}\right.$

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 - $\emptyset$.

Aksjomat regularności

$\forall _{A}\ A\not =\emptyset \Rightarrow \exists _{B\in A}\forall _{C}\ C\not \in A\vee C\not \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\not \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\not \in x$.

Aksjomat nieskończoności

$\exists _{\mathcal {N}}\ \emptyset \in {\mathcal {N}}\wedge \forall x\,{\bigg (}x\in {\mathcal {N}}\Rightarrow {\Big (}\bigcup \{x,\{x\}\}{\Big )}\in {\mathcal {N}}{\bigg )}$

Istnieje zbiór ${\mathcal {N}}$, do którego należy zbiór pusty a także dla dowolnego elementu x zbioru ${\mathcal {N}}$ 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.

$\forall _{X}\exists _{A}{\bigg (}\forall _{z\in A}\exists !_{x\in X}\exists !_{y\in x}\ z=y{\bigg )}\wedge {\bigg (}\forall _{x\in X}\exists !_{y\in x}\forall _{z\in A}\ {\Big (}{\big (}z\in x\Rightarrow z=y{\big )}\wedge (y\in A){\Big )}{\bigg )}$

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.