Na tym wykładzie zapoznamy się z podstawami aksjomatycznej konstrukcji liczb naturalnych
Aksjomatyczną konstrukcji liczb naturalnych zawdzięczamy między innymi Ernestowi Zermelo, Abrahamowi Fraenklowi, Albertowi Skolemowi, Johnowi von Neumannowi i Guiseppe Peano. Ernst Zermelo sformułował aksjomat wyboru i z jego pomocą udowodnił twierdzenie o dobrym uporządkowaniu. W 1908 przedstawił system aksjomatów Teorii Mnogości, następnie zmodyfikowany przez Fraenkla i Skolema1. John von Neuman2 zaproponował konstrukcję liczb naturalnych a Giuseppe Peano3 opracował aksjomatykę arytmetyki liczb naturalnych.
Zapoznamy się też z twierdzeniami o definiowaniu i dowodzeniu przez indukcję. Wykład ma częściowo charakter informacyjny, nie wszystkich faktów będziemy dowodzić.
Oprócz wspomnianych wcześniej aksjomatów (zobacz Wykład II.2) potrzebny nam będzie aksjomat zwany Aksjomatem Nieskończoności.
\(\bullet \) Aksjomat Nieskończoności: Istnieje rodzina zbiorów \(\cal A\) o następujących własnościach:
1. \(\emptyset \in {\cal A}\)
2. \(X\in {\cal A}\lra \exists Y\in {\cal A} : Y=X\cup \{X\}.\)
Definicja 226. Rodzinę zbiorów spełniających warunki Aksjomatu Nieskończoności nazywamy rodziną induktywną, albo też: zbiorem induktywnym.
Definicja 227. Jeśli \(X\) jest zbiorem to zbiór \(X\cup \{X\}\) nazywamy następnikiem zbioru \(X\) i oznaczamy przez \(X'\).
Konstrukcja Von Neumanna liczb naturalnych opiera się przede wszystkim na następującym twierdzeniu.
Dowód. Dowód zaczniemy od następującego lematu.
Dowód Lematu 229. Musimy sprawdzić warunki 1. i 2. Aksjomatu Nieskończoności. Skoro każdy zbiór \(R\) jest zbiorem induktywnym, to dla każdego \(R\) mamy \(\emptyset \in R\), a zatem \(\emptyset \in \bigcap _{R\in {\cal R}} R\), zatem warunek 1. jest spełniony. Aby sprawdzić warunek 2. musimy sprawdzić, czy jeśli \(X\in \bigcap _{R\in {\cal R}} R\) to \(X'\in \bigcap _{R\in {\cal R}} R\). Jeśli \(X\in \bigcap _{R\in {\cal R}} R\) to \(X\in R \ \forall _{R\in {\cal R}}\) a zatem (skoro \(R\) są induktywne) \(X'\in R \ \forall _{R\in {\cal R}}\), czyli \(X'\in \bigcap _{R\in {\cal R}} R\), więc spełniony jest też warunek 2. □
Z Aksjomatu Nieskończoności wynika, że istnieje co najmniej jeden zbiór induktywny, nazwijmy go \(\cal A\). Weźmy podzbiory tego zbioru, \(\cal P(A)\) (istnienie zbioru podzbiorów też wynika z przyjętych aksjomatów). Z \(\cal P(A)\) wybieramy podzbiory induktywne, tę rodzinę podzbiorów nazwiemy \(\cal R\). Rodzina \(\cal R\) jest niepusta, bo \({\cal A}\in {\cal R}\). Z Lematu 229 wynika, że \(\N := \bigcap _{R\in {\cal R}} R\) jest zbiorem induktywnym. Jeśli \(K\) jest innym zbiorem induktywnym to dla dowolnego zbioru \(R\) z \(\cal R\) zbiór \(R\cap K\) jest (z powyższego Lematu) zbiorem induktywnym, zatem także elementem \(\cal R\). Stąd \(\N =\bigcap _{R\in {\cal R}} R\subset R\cap K\subset K\). \(\N \) jest więc najmniejszym zbiorem induktywnym. □
Uwaga 231. Von Neumann zaproponował następującą konstrukcję zbioru liczb naturalnych:
\(0\) to \(\emptyset \)
\(1\) to \(\{\emptyset \}\)
\(2\) to \(\{ \emptyset , \{\emptyset \}\}\)
\(3\) to \(\{\emptyset , \{\emptyset \}, \{ \emptyset , \{\emptyset \}\}\}\)
…
Zauważmy, że tak skonstruowany zbiór liczb naturalnych ma elementy, które są zbiorami, zatem każdą liczbę naturalną możemy traktować jako zbiór, co więcej, poprzednia liczba, czyli poprzedni zbiór (o ile taki jest) jest elementem następnego zbioru. Szczegółowiej zajmiemy się tymi własnościami w dalszej części wykładu.
Przejdźmy teraz do zasady indukcji matematycznej. W „szkolnej wersji” ta zasada jest następująca: jeśli \(T_{n}\) jest stwierdzeniem zawierającym liczbę naturalną \(n\) i jeśli twierdzenie \(T_1\) jest prawdziwe, oraz dla wszystkich \(k\in \mathbb {N}\) spełnione jest wynikanie: jeśli \(T_k \) jest prawdziwe, to \(T_{k+1}\) jest prawdziwe, to wtedy stwierdzenie \(T_n\) jest prawdziwe dla wszystkich \(n\in \N \). W ten sposób można wykazać na przykład, że \(1+2+\dots +n=\frac {n(n+1)}{2}\). W szkole średniej nie dowodzi się Zasady Indukcji, przyjmując ją jako aksjomat. Teraz wykażemy formalnie ten fakt. Dla uproszczenia notacji elementy \(\N \), choć traktujemy je jako zbiory, będziemy oznaczać małymi literami \(m, n, x,y\).
Dowód. Jeśli zbiór \(P\) spełnia założenia twierdzenia, to jest zbiorem induktywnym. W takim razie \(\N \subset P\), bo \(\N \) jest najmniejszym zbiorem induktywnym. Z założenia jednak \(P\subset \N \). W takim razie \(P=\N \). □
Zajmiemy się teraz wykazaniem pewnych wybranych własności liczb naturalnych; głównym narzędziem będzie Zasada Indukcji.
Dowód. Wykorzystamy Zasadę Indukcji. Niech
\[P=\{n\in \N : \forall _{y} \ y\in n\lra y\in \N \},\]
czyli \(P\) jest zbiorem liczb naturalnych spełniających tezę naszego twierdzenia. Wystarczy wykazać, że \(P=\N \). Sprawdźmy:
0. Warunek \(P\subset \N \) jest spełniony.
1. Zachodzi \(\emptyset \in P\), bo \(\emptyset \) nie ma żadnych elementów, zatem warunek z tezy jest dla niego (pusto)spełniony.
2. Musimy sprawdzić, czy jeśli \(n\in P\) to \(n'\in P\). Zbiór \(n'=n\cup \{n\}\), zatem jeśli \(y\in n'\) to albo \(y\in n\) albo \(y=n\). Jeśli zachodzi \(y=n\in P\) to oczywiście \(y\in \N \). Jeśli \(y\in n\) a \(n\in P\), to z definicji \(P\) mamy \(y\in \N \). Stąd, każdy element \(n'\) należy do \(\N \), zatem \(n'\in P\).
Sprawdziliśmy, że \(P\) jest zawartym w \(\N \) zbiorem induktywnym, w takim razie, z Zasady Indukcji \(P=\N \), co kończy dowód stwierdzenia. □
Dowód. Znowu wykorzystamy Zasadę Indukcji. Niech
\[P=\{n\in \N : (n=\emptyset \vee (\exists _{m} \ m\in \N \wedge m'=n) \},\]
czyli \(P\) jest zbiorem liczb naturalnych spełniających tezę naszego twierdzenia. Wystarczy wykazać, że \(P=\N \). Sprawdzamy podobnie jak poprzednio:
0. \(P\subset \N \).
1. Warunek \(\emptyset \in P\) zachodzi z definicji \(P\).
2. Musimy sprawdzić, czy jeśli \(n\in P\) to \(n'\in P\). Żeby \(n'\in P\) wystarczy, by \(n' \) był następnikiem jakiejś liczby naturalnej, co oczywiście zachodzi, bo \(n'\) jest następnikiem \(n\).
Z Zasady Indukcji \(P=\N \), co kończy dowód stwierdzenia. □
Teraz sformułujemy i wykażemy nieco dziwnie brzmiące stwierdzenie, które będzie nam potrzebne w dalszej części wykładu, gdzie zajmiemy się porządkiem w zbiorze liczb naturalnych.
Dowód. Niech \(P\) będzie zbiorem liczb naturalnych spełniających tezę stwierdzenia,
\[P=\{n\in \N : y\in n \lra y\subset n \}.\]
Sprawdzamy:
0. \(P\subset \N \).
1. Warunek \(\emptyset \in P\) zachodzi, bo poprzednik implikacji (\(y\in \emptyset \)) jest fałszywy, skąd implikacja jest prawdziwa.
2. Sprawdzamy, czy jeśli \(n\in P\) to \(n'\in P\). Jeśli \(y\in n'\) to \(y\in n\) albo \(y=n\). Jeśli \(y\in n\), a \(n\in P\) to \(y\subset n\subset n'\). Jeśli \(y=n\) to skoro \(n\subset n'\) to także \(y\subset n'\).
W takim razie \(P\) jest zbiorem induktywnym, a więc \(P=\N \). □
Kolejne stwierdzenie, które zostawimy bez dowodu, także wykorzystamy przy omawianiu własności porządku w liczbach naturalnych.
Powiemy teraz parę słów o porządku w liczbach naturalnych. Zdefiniujemy relację \(\leq \) na zbiorze \(\N \) i, wykorzystując poprzednie Stwierdzenia, wykażemy własności tej relacji.
Relacja \(\leq \) ma następujące własności:
Dowód. Dowód jest natychmiastowym wnioskiem ze Stwierdzenia 236. □
Dowód. Zwrotność, słaba antysymetryczność i przechodniość wynika od razu z własności relacji \(\subset \), przykładowo \(m\leq n\) i \(n\leq m\) oznacza, że \(m\subset n\) i \(n\subset m\), skąd wynika \(m=n\), zatem \(\leq \) jest relacją słabo antysymetryczną.
□
Wniosek 240. Każda liczba naturalna to zbiór liczb (naturalnych) istotnie od niej mniejszych.
Dowód. Warto spojrzeć teraz na konstrukcję Von Neumanna (Uwaga 231).
Tezę wniosku możemy zapisać następująco:
\[\forall _{n\in \N } \ (\forall _m \ m\in n)\iff (m\in \N \wedge m<n).\]
Wykażmy wynikanie \((\lra )\). Jeśli \(m\in n\) to \(m\in \N \) ze Stwierdzenia 234, oraz \(m<n\) wprost z definicji \(<\).
Wynikanie \((\Longleftarrow )\) jest natychmiastowe z definicji \(<\). □
Kolejne stwierdzenie mówi, że pomiędzy liczbą naturalną a jej następnikiem nie ma innych liczb naturalnych (co w zasadzie wiemy od dawna :))
Dowód. Niech \(n\leq m\), załóżmy, że \(m\neq n\). Będziemy chcieli wykazać, że \(m=n'\). Z założenia mamy, że \(m\leq n'\), co oznacza, że \(m\subset n\cup \{n\}\), co oznacza, że \(m\in n\cup \{n\}\) lub \(m= n\cup \{n\}=n'.\) Gdyby ta ostatnia równość nie zachodziła, to mielibyśmy \(m\in n\cup \{n\}\). Są zatem dwie możliwości: \(m\in n\) lub \(m\in \{n\}\). Jeśli \(m\in \{n\}\) to \(m=n\), co jest sprzeczne z naszym założeniem na początku dowodu. Zatem \(m\in n\). Równocześnie, z założenia, \(n\leq m\), co z definicji \(\leq \) zachodzi gdy \(n\in m \vee n=m\). Możliwość \(n=m\) została wykluczona, zatem zostaje \(n\in m\), ale jednocześnie ciągle \(m\in n\), co daje sprzeczność (zbiór nie może być swoim elementem). Stąd \(m=n'\). □
Kolejne twierdzenie, zwane Zasadą Minimum, pozwoli nam stwierdzić, że porządek na \(\N \) jest dobry. Zauważmy, że ze Stwierdzenia 238 (4) wynika, że porządek \(\leq \) jest liniowy.
Dowód. W tym dowodzie zrezygnujemy trochę z formalności na korzyść przejrzystości. Weźmy niepusty zbiór \(X\subset \N \). Zdefiniujmy
\[Z=\{n\in \N :\{0,1,\dots ,n\}\cap X=\emptyset \}.\]
Wykorzystamy Zasadę Indukcji. Gdyby w \(X\) nie było elementu najmniejszego, to \(0\notin X\), zatem \(0\in Z\). Jeśli \(n\in Z\) to \(\{0,\dots ,n \}\cap X=\emptyset \), gdyby zatem zachodziło \(n'\in X\), to \(n'\) byłby najmniejszym elementem \(X\) (a miało takiego nie być). W takim razie \(n'\in Z\), zatem oba warunki Zasady Indukcji są spełnione, a więc wynika z niej, że \(Z=\N \), to jednak oznacza, że \(X=\emptyset \), sprzeczność. W takim razie w \(X\) istnieje element najmniejszy. □
Ostatnie wykazane na tym wykładzie twierdzenie, to twierdzenie o definiowaniu przez indukcję.
Dowód. Wykorzystamy Zasadę Indukcji. Niech
\[P=\{ n\in \N : f(n)\text { jest jednoznacznie zdefiniowane} \}.\]
Sprawdzamy warunki Zasady Indukcji. Oczywiście \(P\subset \N \) i \(0\in P\). Jeśli \(n\in P\) to znaczy, że \(f(n)\) jest jednoznacznie zdefiniowane, ale w takim razie \(f(n')=h(f(n))\) też jest zdefiniowane, czyli \(n'\in P\). Zatem, z Zasady Indukcji, \(P=\N \), czyli funkcja \(f\) jest jednoznacznie zdefiniowana dla wszystkich liczb naturalnych. □
Podobnie można wykazać następujące twierdzenie:
Przykład 245 (Ciąg Fibonacciego). Przykładowo, niech \(A=\N \), \(a=b=1\) i \(h(m,n)=m+n\). Z powyższego twierdzenia wiemy, że istnieje dokładnie jedna funkcja \(f:\N \to \N \) taka, że \(f(0)=f(1)=1\) oraz \(f(n+2)=h(f(n+1),f(n))=f(n+1)+f(n)\). Ta funkcja, zwana wzorem Bineta, pozwala w sposób jawny zapisać rekurencyjnie zadany ciąg Fibonacciego. Czytelnik na ćwiczeniach z algebry liniowej wykaże być może, że
\[f(n)=\frac {1}{\sqrt {5}}\left ( \left (\frac {1+\sqrt {5}}{2}\right )^{n+1} +\left (\frac {1-\sqrt {5}}{2}\right )^{n+1} \right ).\]
Uwaga 246. O rozszerzeniu zasady indukcji na zbiory dobrze uporządkowane, czyli o zasadzie indukcji pozaskończonej, zainteresowany czytelnik może poczytać na przykład w [3].
1 Albert Skolem (1887–1963), norweski matematyk.
2 John von Neuman (1903–1957), węgierski matematyk pochodzenia żydowskiego.
3 Giuseppe Peano (1858–1932), włoski matematyk i logik.
[1] Dubois, D., Prade, H.: Fundamentals of Fuzzy Sets, Springer New York 2000
[2] Gelfond, A.: Transcendental and Algebraic Numbers, Courier Dover Publications, 2015
[3] Guzicki W., Zakrzewski, P.: Wykłady ze wstępu do matematyki, PWN Warszawa 2005
[4] Kraszewski, J.: Wstęp do matematyki, WNT PWN 2020
[5] Kuratowski, K.: Wstęp do teorii mnogości i topologii, PWN Warszawa 1980
[6] Marek, W., Onyszkiewicz, J.: Elementy logiki i teorii mnogości w zadaniach, PWN Warszawa 1978
[7] Sierpiński, W.: Cardinal and ordinal numbers, PWN Warszawa 1965
[8] Tarski, A.: Sur les ensembles finis, Fundamenta Mathematicae 6 (1924), 45–95.
[9] Wójtowicz, K.: artykuł
http://www.obi.opoka.org.pl/zfn/022/zfn02203Wojtowicz.pdf, dostęp 2020.05.03