Konstrukcja von Neumanna liczb naturalnych

Liczby naturalne to jedna z najbardziej podstawowych idei matematycznych. Operacje dodawania i mnożenia liczb naturalnych są najczęściej uznawane za najprostsze operacje matematyczne. W aksjomatycznym podejściu do teorii mnogości wszystkie "oczywiste fakty" dotyczące liczb naturalnych należy wywieść z aksjomatów. W pierwszej części tego rozdziału wykażemy, że aksjomatyka ZF gwarantuje istnienie zbioru liczb naturalnych.

W teorii mnogości liczby naturalne, podobnie jak wszystkie inne byty, muszą być zbiorami. Konstrukcja liczb naturalnych przedstawiona w dalszej części została zaproponowana przez Johna von Neumanna jako specyficzny przypadek liczb porządkowych.

Liczby naturalne definiujemy w poniższy sposób: Liczbą naturalną [math]0[/math] jest zbiór pusty- [math]\emptyset[/math]. Jeśli [math]n[/math] jest liczba naturalną, to następna po niej liczbą naturalną jest [math]n'=n\cup\left\{ n\right\}.[/math]

A więc [math]1=0'=\emptyset \cup \left\{ \emptyset\right\}=\left\{ \emptyset\right\}.[/math]

Dalej [math]2=1'=\left\{ \emptyset\right\}'=\left\{ \emptyset\right\}\cup \left\{ \left\{ \emptyset\right\}\right\}=\left\{ \emptyset, \left\{ \emptyset\right\}\right\}.[/math]

I dalej [math]3=\left\{ \emptyset, \left\{ \emptyset\right\}\right\}'=\Bigl \{ \emptyset, \left\{ \emptyset\right\}, \ \left\{ \emptyset, \left\{ \emptyset\right\}\right\} \Bigr\}.[/math] itd. ,,,

Intuicyjnie, patrząc na nie widzimy, że liczba naturalna [math]n[/math] jest tutaj wzorcowym zbiorem dokładnie [math]n[/math]-elementowym. Dokładniej liczba naturalna [math]n[/math] jest tutaj zbiorem złożonym z dokładnie liczb naturalnych silnie mniejszych od [math]n[/math].

Aby się o tym przekonać, to tak (stosujemy naiwną wersję zasady indukcji): [math]0[/math] jest zbiorem pustym. A zbiór liczb naturalnych silnie mniejszych od [math]0[/math] oczywiście nie posiada elementów, a więc jest zbiorem pustym. A więc spełniona jest podstawa indukcji.

Krok indukcyjny: Jeśli [math]n[/math] jest zbiorem złożonym z dokładnie liczb naturalnych silnie mniejszych od [math]n[/math], to [math]n'[/math] jest zbiorem złożonym z dokładnie liczb naturalnych silnie mniejszych od [math]n'[/math]. Popatrzmy na [math]n'=n\cup\left\{ n\right\}.[/math] Jego elementami są wszystkie elementy [math]n[/math], oraz samo [math]n[/math]. A z założenia indukcyjnego, [math]n[/math] jest zbiorem złożonym z dokładnie liczb naturalnych silnie mniejszych od [math]n[/math]. Otrzymujemy zatem zbiór złożony z liczb naturalnych silnie mniejszych od [math]n[/math] oraz samo [math]n[/math] (jako element), czyli otrzymujemy zbiór liczb naturalnych mniejszych od [math]n'[/math],zbiór równy [math]n'[/math], co należało otrzymać dla kroku indukcyjnego.

A więc w naszej konstrukcji liczba naturalna [math]n[/math] jest zbiorem złożonym z dokładnie liczb naturalnych mniejszych od [math]n[/math].

Zauważmy, że każda liczba naturalna jest poprawnie określona, tzn. jako zbiór istnieje. Więcej istnieje również zbiór, który ma w sobie wszystkie liczby naturalne( jako zbiory, jak wyżej) i który, nie ma innych elementów. Musimy to wykazać. Aby to zrobić potrzebny jest aksjomat nieskończoności, wprowadzony w rozdziale drugim. Przypomnijmy jego treść.

Aksjomat nieskończoności:

Istnieje zbiór [math]\mathbb{X}[/math], taki że:

(1) [math]\emptyset\in \mathbb{X},[/math]

(2) [math]A\in \mathbb{X} \rightarrow A \cup \left\{ A\right\} \in \mathbb{X}.[/math]

Każdy taki zbiór, spełniający te dwa warunki nazwiemy zbiorem induktywnym. Aksjomat nieskończoności mówi więc, że istnieje co najmniej jeden zbiór induktywny. Intuicyjnie to oznacza, że istnieje przynajmniej jeden zbiór, który ma w sobie wszystkie liczby naturalne (rozumiane jak wyżej, jako zbiory). Zbiór ten może mieć jeszcze inne elementy. Udowodnimy, że istnieje najmniejszy taki zbiór, który będzie nam służył jako [math]\mathbb{N}[/math].

W dowodzie bardzo pomocny będzie poniższy lemat:Lemat 0

Jeśli [math]\mathbb{B}[/math] jest niepustym zbiorem zbiorów induktywnych, to [math]\bigcap \mathbb{B}[/math] jest również zbiorem induktywnym.

Zauważmy, że założenia twierdzenia łatwo spełnić- skoro istnieje zbiór induktywny [math]\mathbb{X}[/math], to wtedy [math]\left\{ \mathbb{X}\right\}[/math] jest niepustym zbiorem( bo jednoelementowym) złożonym z tego zbioru induktywnego [math]\mathbb{X}.[/math]

Dowód:

Niech [math]\mathbb{B}[/math] będzie niepustym zbiorem zbiorów induktywnych. Pokażemy, że [math]\bigcap \mathbb{B}[/math] jest również zbiorem induktywnym.

Musimy pokazać dwa fakty:

(1) [math]\emptyset\in \bigcap \mathbb{B},[/math]

(2) [math]Y\in \bigcap \mathbb{B} \rightarrow Y \cup \left\{ Y\right\} \in \bigcap \mathbb{B}.[/math]

Aby udowodnić punkt pierwszy, należy pokazać, że zbiór pusty [math]\emptyset[/math] jest elementem każdego zbioru [math]A\in \mathbb{B}.[/math] Niech [math]A\in \mathbb{B}[/math]. Ponieważ [math]\mathbb{B}[/math] jest zbiorem zbiorów induktywnych, to [math]A[/math] jest zbiorem induktywnym, a skoro tak, to [math]\emptyset\in A.[/math] Pokazaliśmy, że zbiór pusty jest elementem każdego zbioru [math]A\in \mathbb{B}[/math], co należało pokazać w punkcie pierwszym.

Aby udowodnić punkt drugi, niech [math]Y\in \bigcap \mathbb{B}.[/math] Oznacza to dokładnie tyle, że [math]Y\in A[/math] dla każdego zbioru [math]A\in \mathbb{B}.[/math] Niech [math]A\in \mathbb{B}[/math], wnioskujemy, że [math]Y\in A.[/math] Ponieważ jednak [math]A\in \mathbb{B}[/math] jest zbiorem induktywnym, więc [math]Y \cup \left\{ Y\right\} \in A.[/math]Z dowolności wyboru zbioru [math]A\in \mathbb{B}[/math] otrzymujemy, że [math]Y \cup \left\{ Y\right\}[/math] jest elementem każdego zbioru [math]A\in \mathbb{B}[/math], a to oznacza, że [math]Y \cup \left\{ Y\right\} \in \bigcap \mathbb{B}.[/math] Dowód drugiego punktu został zakończony.

Zatem [math]\bigcap \mathbb{B}[/math] jest zbiorem induktywnym, co kończy dowód lematu.

Przechodzimy do głównego twierdzenia.

Twierdzenie 1 Istnieje najmniejszy, względem inkluzji, zbiór induktywny, czyli zbiór induktywny będący podzbiorem wszystkich zbiorów induktywnych.

Dowód:

Ustalmy zbiór induktywny [math]\mathbb{X},[/math] i rozważmy zbiór:

[math]\mathbb{Y}=\left\{ A\subset \mathbb{X}: \ A \hbox{ jest induktywny } \right\}.[/math]

Innymi słowy, rozważamy wszystkie podzbiory [math]\mathbb{X}[/math] induktywne.

Taki zbiór [math]\mathbb{Y}[/math] jest niepusty, bo [math]\mathbb{X} \in \mathbb{Y}[/math], bo [math]\mathbb{X}[/math] z założenia jest induktywny. [math]\mathbb{Y}[/math] jest niepustym zbiorem zbiorów induktywnych, zatem na mocy lematu [math]\bigcap \mathbb{Y}[/math] jest również zbiorem induktywnym. Ponieważ [math]\bigcap \mathbb{Y}[/math] jest podzbiorem każdego zbioru rodziny [math]\mathbb{Y}[/math], więc [math]\bigcap \mathbb{Y}[/math] zawiera się w każdym podzbiorze [math]\mathbb{X}[/math] induktywnym. Pokażemy, że jest podzbiorem również każdego zbioru induktywnego. Początkowy zbiór induktywny [math]\mathbb{X},[/math] ponieważ jest induktywny, to ma w sobie wszystkie liczby naturalne(jako zbiory), ale może mieć jeszcze inne elementy. Jeśli rozważymy jego podzbiory(podzbiory mogą być dowolnie małe, do zbioru pustego włącznie), ale jeśli rozważymy podzbiory induktywne, to ponieważ są induktywne, to one również będą mieć w sobie wszystkie liczby naturalne, stąd łatwo przypuścić, że przekrój (część wspólna) takich zbiorów, to poszukiwany [math]\mathbb{N}[/math] zbiór złożony z dokładnie liczb naturalnych( i tylko nich). Niemniej musimy to udowodnić.

W tym celu ustalmy dowolny zbiór induktywny [math]\mathbb{Z}[/math]. [math]\mathbb{Z}[/math] jest induktywny, i [math]\mathbb{X}[/math] jest induktywny, zatem znowu stosując lemat [math]\mathbb{Z} \cap \mathbb{X}[/math] jest induktywny. Niewątpliwie [math]\mathbb{Z} \cap \mathbb{X} \subset \mathbb{Z}.[/math] Oczywiście, również [math]\mathbb{Z} \cap \mathbb{X} \subset \mathbb{X}[/math], i [math]\mathbb{Z} \cap \mathbb{X}[/math] jest induktywny, a skoro zaznaczyłem, że [math]\bigcap \mathbb{Y}[/math] zawiera się w każdym podzbiorze [math]\mathbb{X}[/math] induktywnym, więc [math]\bigcap \mathbb{Y} \subset \mathbb{Z} \cap \mathbb{X} \subset \mathbb{Z}.[/math] Pokazaliśmy, że [math]\bigcap \mathbb{Y}\subset \mathbb{Z}[/math]. Z dowolności wyboru zbioru induktywnego [math]\mathbb{Z}[/math], [math]\bigcap \mathbb{Y}[/math] jest podzbiorem każdego zbioru induktywnego. [math]\square[/math]

Taki zbiór jest tylko jeden. Gdyby istniały dwa najmniejsze zbiory induktywne ( względem inkluzji), to by się wzajemnie zawierały, zatem muszą być równe.

Tak skonstruowany zbiór nazywamy zbiorem liczb naturalnych.

Zbiór induktywny będący podzbiorem wszystkich zbiorów induktywnych nazywamy zbiorem liczb naturalnych, i oznaczamy przez [math]\mathbb{N}[/math]. Elementy tego zbioru nazywamy liczbami naturalnymi.

Zbiór ten ma liczbę [math]0[/math], zdefiniowaną wcześniej jako zbiór pusty. Ma również [math]1=\emptyset'=\left\{ \emptyset\right\}[/math], bo ma liczbę [math]0=\emptyset[/math], i z każdym elementem ma również jego następnik, więc ma również następnik zbioru pustego. [math]\emptyset'=\left\{ \emptyset\right\}=1[/math]. Itd. Taki zbiór ma w sobie tylko liczby naturalne( w sensie, wprowadzone we wstępie zbiory), gdyż moglibyśmy utworzyć podzbiór [math]X[/math] (to nie jest formalne uzasadnienie) zbioru [math]\mathbb{N}[/math] złożony z dokładnie takich omawianych zbiorów, jest to najbardziej naturalny przykład zbioru induktywnego, ponieważ [math]\mathbb{N}[/math] jest podzbiorem każdego zbioru induktywnego, to jest podzbiorem [math]X[/math], i [math]X=\mathbb{N}[/math], czyli [math]\mathbb{N}[/math] składa się z dokładnie ze zbiorów wprowadzonych we wstępie.

ZASADA INDUKCJI MATEMATYCZNEJ

Podstawową metodą dowodzenia twierdzeń o liczbach naturalnych jest zasada indukcji matematycznej. Chcemy pokazać,że dana rozpatrywana własność odnośnie liczb naturalnych, jest prawdziwa dla wszystkich liczb naturalnych. Definiujemy więc zbiór liczb naturalnych, które ją spełniają. Jeśli zbiór ten spełnia wymagane własności poniższej zasady indukcji, to jest on równy zbiorowi liczb naturalnych, czyli własność jest prawdą dla wszystkich liczb naturalnych. Mówi o tym poniższe twierdzenie.

Twierdzenie 1.1 [ ZASADA INDUKCJI MATEMATYCZNEJ]

Dla dowolnego zbioru [math]X[/math], jeśli [math]X\subset\mathbb{N}[/math], oraz

[math]\emptyset\in X,[/math]

oraz

[math]x\in X \implies x'=x\cup\{x\}\in X,[/math]

to wtedy [math]X=\mathbb{N}.[/math]

DOWÓD:

Ustalmy dowolny zbiór [math]X[/math] spełniający założenia twierdzenia. Te założenia oznaczają, że zbiór [math]X[/math] jest zbiorem induktywnym, a więc, na mocy definicji zbioru liczb naturalnych, ponieważ [math]\mathbb{N}[/math] jest podzbiorem każdego zbioru induktywnego, więc [math]\mathbb{N}\subset X[/math]. Równocześnie założyliśmy, że [math]X\subset\mathbb{N}[/math] i w związku z tym [math]X=\mathbb{N}[/math], co kończy dowód.[math]\square [/math]

Udowodnimy parę twierdzeń przy pomocy zasady indukcji matematycznej. Najpierw:

Twierdzenie 1.2 Każdy element liczby naturalnej jest liczbą naturalną.

Rozważmy zbiór [math]X[/math]:

[math]X=\left\{ n\in\mathbb{N}\Bigl| \ \ \bigwedge\limits_{a\in n} a\in\mathbb{N}\right\}. [/math]

Jest to zbiór tych liczb naturalnych [math]n[/math], że każdy element [math]n[/math] jest liczbą naturalną, jest to zbiór tych liczb naturalnych dla których twierdzenie zachodzi. Wykażemy indukcyjnie, że [math]X=\mathbb{N}.[/math]

Po pierwsze musimy wykazać, że [math]\emptyset\in X.[/math] Aby to sprawdzić musimy stwierdzić, czy każdy element zbioru pustego jest liczbą naturalną- oczywiście jest to prawda (formalna). A więc [math]\emptyset\in X.[/math]

(Krok indukcyjny):Załóżmy, że [math]n\in X[/math], i dowiedźmy że [math]n'\in X.[/math] Założenie oznacza, że każdy element [math]n[/math]jest liczbą naturalną. Rozważmy [math]n'=n\cup\left\{ n\right\}[/math], każdy element [math]n[/math] jest liczbą naturalną, również jedyny element [math]\left\{ n \right\}[/math] równy [math]n[/math] jest liczbą naturalną, bo [math]n\in X\subset\mathbb{N}[/math], zatem [math]n\in\mathbb{N}.[/math] Wobec czego każdy element sumy [math]n\cup\left\{ n\right\}[/math] jest liczbą naturalną, a zatem [math]n\cup\left\{ n\right\}=n'\in X.[/math]

Na mocy zasady indukcji [math]X=\mathbb{N}[/math], czyli każda liczba naturalna należy do [math]X[/math], więc dla dowolnej ustalonej liczby naturalnej (z definicji tego zbioru [math]X[/math]) każdy jej element jest liczbą naturalną. [math]\square[/math]

Wiemy, że liczbami naturalnymi są [math]0=\emptyset[/math] oraz następniki liczb naturalnych. Niewątpliwie [math]0[/math] nie jest następnikiem żadnej liczby naturalnej, ponieważ następnik dowolnej liczby naturalnej posiada przynajmniej jeden element - dla [math]n[/math] mamy [math]n\in n'=n\cup\left\{ n\right\}[/math], a więc [math]n'\neq \emptyset=0.[/math] Poniższy fakt pokazuje własność przeciwną.

Fakt 1.3 Każda liczba naturalna jest albo zbiorem pustym, albo następnikiem liczby naturalnej. Formalnie:

[math]n\in\mathbb{N}\Longrightarrow n=\emptyset\vee \bigvee\limits_{m\in\mathbb{N}} n=m'. [/math]

DOWÓD:

Rozważmy zbiór [math]X[/math]:

[math] X=\left\{ n\in\mathbb{N}\Bigl| \ \ n=\emptyset\vee \bigvee\limits_{m\in\mathbb{N}} n=m'\right\}.[/math]

Jest to zbiór tych liczb naturalnych, które maja wymaganą własność z twierdzenia. Wykażemy indukcyjnie, że [math]X=\mathbb{N}.[/math]

Oczywiście [math]\emptyset\in X[/math], spełniony jest pierwszy człon alternatywy, a więc i cała alternatywa.

(Krok indukcyjny): Załóżmy, że liczba naturalna [math]n\in X[/math], i dowiedźmy, że [math]n'\in X.[/math] Oczywiście [math]n'[/math] jest następnikiem [math]n[/math], wobec czego [math]n'[/math] jest następnikiem pewnej liczby naturalnej, w związku z czym [math]n'\in X.[/math]

Na mocy zasady indukcji [math]X=\mathbb{N}[/math], czyli każda liczba naturalna należy do [math]X[/math], czyli (z definicji zbioru [math]X[/math]) każda liczba naturalna ma rozpatrywaną własność- każda liczba naturalna jest zbiorem pustym lub następnikiem pewnej liczby naturalnej. [math]\square[/math]

Fakt 1.4 Dla dowolnej liczby naturalnej [math]n[/math] i dowolnego zbioru [math]x[/math], jeśli [math]x\in n[/math], to [math]x\subset n[/math].

Czyli jeśli zbiór [math]x[/math] jest elementem liczby naturalnej, to jest również jej podzbiorem. Możemy powiedzieć jeszcze prościej, że każdy element liczby naturalnej jest jej podzbiorem. Ma to sens, przypominamy bowiem, że jedynymi rozważanymi przez nas obiektami są zbiory, więc elementy zbiorów są również zbiorami( i chyba nie muszę mówić, że liczba naturalna w naszym ujęciu jest zbiorem). Było to wyjaśniane we wstępie do rozdziału Aksjomaty teorii mnogości.

DOWÓD:

Rozważmy zbiór [math]A[/math]:

[math] A=\left\{ n\in\mathbb{N}\Bigl| \ \ \bigwedge\limits_{x\in n} x\subset n\right\}.[/math]

Jest to zbiór tych liczb naturalnych [math]n[/math], że każdy element [math]n[/math] jest jej podzbiorem, czyli zbiór tych liczb naturalnych, dla których twierdzenie zachodzi. Wykażemy indukcyjnie, że [math]A=\mathbb{N}.[/math]

Oczywiście [math]0=\emptyset\in A[/math], bo każdy element zbioru pustego (będzie spełniał to co chcemy) czyli jest jego podzbiorem( formalna prawda).

Załóżmy, że [math]n\in A[/math], i dowiedźmy, że [math]n'\in A.[/math] Nasze założenie oznacza, że każdy element [math]n[/math] jest jej podzbiorem. Wykażemy, że każdy element [math]n'[/math] jest jej podzbiorem. Ustalmy dowolne [math]x\in n'=n\cup\left\{n\right\}.[/math] Mamy dwa przypadki: [math]x\in n[/math] lub [math]x\in\left\{ n\right\}[/math]( równoważnie [math]x=n[/math]). Jeśli [math]x\in n[/math], to na mocy założenia indukcyjnego każdy element [math]n[/math] jest jej podzbiorem, wobec czego [math]x\subset n\subset n\cup\left\{n\right\}=n'[/math], czyli [math]x\subset n'[/math], co należało pokazać. Jeśli [math]x=n[/math], ponieważ [math]n\subset n\cup\left\{n\right\}=n'[/math], wnioskujemy, że [math]x\subset n'[/math]. Zatem w każdym przypadku, każdy element [math]n'[/math] jest jej podzbiorem, a zatem [math]n'\in A.[/math]

Na mocy zasady indukcji [math]A=\mathbb{N}[/math], czyli każda liczba naturalna [math]n[/math] jest elementem [math]A[/math], więc z definicji tego zbioru każdy element zbioru [math]n[/math] jest jego podzbiorem.[math]\square[/math]

Na koniec:

Fakt 1.5 Jeżeli [math]m'=n'[/math] to [math]m=n.[/math]

Czyli jeśli dwie liczby naturalne mają równe następniki, to są równe.

Dowód:

Załóżmy, nie wprost, że [math]m'=n'[/math] i [math]m\neq n.[/math] Skoro [math]m'=n'[/math] i [math]m\in m'=m\cup\left\{m\right\}[/math], to [math]m\in n'=n\cup\{n\}.[/math] Skoro [math]m\neq n.[/math] otrzymujemy [math]m\in n[/math] i, na mocy Faktu 1.4, [math]m\subset n.[/math] Ponieważ mamy dokładną symetrię pomiędzy [math]m[/math] i [math]n[/math], rozumując podobnie, otrzymujemy: [math]n\subset m[/math], co w sumie daje [math]n=m[/math] - sprzeczność z założeniem.