Porządek na liczbach naturalnych
Wśród naiwnie interpretowanych liczb naturalnych mamy zdefiniowany porządek mniejszości. Aby zdefiniować taki porządek w aksjomatycznie skonstruowanym zbiorze liczb naturalnych musimy go wyrazić za pomocą symboli predykatowych. Dla dowolnych dwóch liczb naturalnych \( m \) i \( n \) piszemy:
\( m\leq n \stackrel{\textrm{def}}{\equiv} m\subset n \)
oraz
\( m < n \stackrel{\textrm{def}}{\equiv} m\in n. \)
Przy takim zdefiniowaniu relacji Fakt 4.3. i poprzednie ćwiczenie natychmiast gwarantują, że dla dowolnych liczb naturalnych \( m \) i \( n \):
- \( m < n \Longrightarrow m\leq n \),
- \( (m\leq n \land m\neq n) \Longrightarrow m < n \),
- \( m \leq n \lor n\leq m \),
- \( m < n \lor m=n \lor n < m \) - gdzie dokładnie jeden z warunków jest prawdziwy.
Kolejne własności dotyczące porządku na liczbach naturalnych podajemy w formie ćwiczenia:
Ćwiczenie 5.1
Dla dowolnych liczb naturalnych \( k,m \) i \( n \) następujące warunki są spełnione:
- 1. \( m=n\iff (m\leq n \land n\leq m) \),
- 2. \( \lnot (n < n) \),
- 3. \( (k\leq m \land m\leq n) \Longrightarrow k\leq n \),
- 4. \( (k < m \land m\leq n) \Longrightarrow k < n \),
- 5. \( (k\leq m \land m < n) \Longrightarrow k < n \),
- 6. \( (k < m \land m < n) \Longrightarrow k < n \).
Ustalmy dowolne liczby naturalne \( k,m \) i \( n \)
Często używać będziemy zbioru wszystkich liczb naturalnych mniejszych niż dana liczba. Okazuje się, że zdefiniowaliśmy już takie zbiory - każda liczba naturalna to zbiór liczb silnie mniejszych od niej.
Wniosek 5.1.
Każda liczba naturalna \( n \) to zbiór liczb istotnie mniejszych od \( n \). Formalnie:
\( \forall n\; n\in\mathbb{N}\Longrightarrow ( \forall z\; z\in n \iff (z\in\mathbb{N} \land z < n)). \)
Dowód
Dla dowolnego ustalonego \( n \) i \( z \) implikacja w lewą stronę jest oczywista (z definicji \( < \)). Implikacja w prawą stronę jest natychmiastową konsekwencją Twierdzenia 4.1. i definicji \( < \).
Ćwiczenie 5.2
Ile jest funkcji \( f:\mathbb{N}arrow\mathbb{N} \) takich, że \( \vec{f}(n) = f(n) \), dla każdej liczby naturalnej \( n \).
Następujące twierdzenie mówi, że każdy zbiór liczb naturalnych zawiera liczbę najmniejszą w porządku \( \leq \). Pozwala ono dowody przez indukcję zamieniać na dowody niewprost. Zamiast przeprowadzać dowód indukcyjny dla zbioru \( P \), rozważyć możemy zbiór \( \mathbb{N}\setminus P \). Na mocy poniższego twierdzenia zbiór taki posiada element minimalny, który jest albo zerem, albo następnikiem pewnej liczby naturalnej, co pozwala na uzyskanie sprzeczności.
Twierdzenie 5.2. [Zasada minimum]
Każdy niepusty zbiór liczb naturalnych zawiera element najmniejszy, to znaczy taki, że wszystkie elementy w tym zbiorze są od niego większe lub równe.
Dowód
Faktu tego dowodzimy indukcyjnie. Na początku ustalmy zbiór \( P \):
\( P=\{n\in\mathbb{N}\,:\, \forall x (x\subset\mathbb{N} \land x\cap n \neq \emptyset) \Longrightarrow \bigcap x\in x\}. \)
Zbiór \( P \) zawiera takie liczby naturalne, że dla dowolnego zbioru liczb naturalnych \( x \) jeśli \( x\cap n\neq \emptyset \) (czyli w zbiór \( x \) zawiera liczbę naturalną silnie mniejszą od \( n \)), to zbiór \( \bigcap x \) jest elementem \( x \). Wykażmy, indukcyjnie, że \( P=\mathbb{N} \).
- Niewątpliwie \( 0\in P \), ponieważ, dla dowolnego, \( x \) fałszem jest \( x\cap\emptyset\neq\emptyset \).
- Załóżmy, że \( n\in P \) i ustalmy zbiór \( x \) taki, że \( x\subset \mathbb{N} \) i \( x\cap n'\neq \emptyset \). Ponieważ \( n'=n\cup\{n\} \) naturalnie jest rozważyć dwa przypadki. Jeśli \( x\cap n\neq \emptyset \), otrzymujemy \( \bigcap x\in x \) na mocy założenia indukcyjnego. W przeciwnym przypadku \( x\cap n = \emptyset \), czyli \( x\cap n'=\{n\} \). Otrzymujemy wtedy \( n\in x \). Równocześnie, dla każdego \( z\in x \) mamy \( n\in z \) lub \( n=z \) (na mocy identyczności pokazanych wcześniej) ponieważ \( z\in n \) -trzecia możliwość jest zabroniona na mocy \( x\cap n = \emptyset \). To wykazuje, że dla każdego \( z\in\mathbb{N} \) mamy, na mocy własności liczb naturalnych, \( n\subset z \). Używając własności przecięcia dostajemy \( n\subset \bigcap x \), a ponieważ \( n\in x \) otrzymujemy \( \bigcap x\subset n \) - to daje \( \bigcap x = n\in x \) - co należało wykazać.
Aby dowieść twierdzenie, ustalmy niepusty zbiór \( x \subset \mathbb {N} \). Niewątpliwie istnieje \( n\in\mathbb{N} \) takie, że \( n\in x \). Wtedy \( n'\cap x\neq\emptyset \), ponieważ \( n\in n'\cap x \). Na mocy dowiedzionego chwilę wcześniej faktu wnioskujemy, że \( \bigcap x\in x\subset\mathbb{N} \). Czyli że \( \bigcap x \) jest najmniejszą liczbą naturalną występującą w \( x \).
Oczywistym faktem jest, że nie istnieje największa liczba naturalna. Aksjomatyczny dowód tego faktu przebiega niewprost. Jeśli \( n \) jest liczbą naturalną, to \( n' \) jest również liczbą naturalną i \( n'> n \), więc \( n \) nie mogła być większa od wszystkich liczb. Niemniej jednak, jeśli pewien podzbiór liczb naturalnych jest ograniczony z góry, to posiada element największy.
Twierdzenie 5.3. [Zasada maksimum]
Jeśli \( x \) jest niepustym zbiorem liczb naturalnych ograniczonym z góry, tzn.:
\( \exists y\; y\in\mathbb{N} \land \forall z\; z\in x \Longrightarrow z \leq y, \)
to \( x \) posiada element największy, tzn.:
\( \exists y\; y\in x \land \forall z\; z\in x \Longrightarrow z\leq y. \)
Dowód
Faktu tego dowodzimy przez indukcję. Zdefiniujmy zbiór \( P \) jako zbiór tych ograniczeń górnych dla których zachodzi nasza teza:
\( P = \{n\in\mathbb{N}\,:\, \forall x\; ( x\neq \emptyset \land x\subset n ) \Longrightarrow \bigcup x \in x\}. \)
Zbiór \( P \) jest zdefiniowany jako zbiór tych liczb naturalnych \( n \), że dla każdego zbioru \( x \) składającego się z liczb silnie mniejszych od \( n \) zbiór ten posiada największy element (którym jest \( \bigcup x \)). Przechodzimy do indukcyjnego dowodu tego faktu.
- Niewątpliwie \( 0=\emptyset\in P \), ponieważ \( \emptyset \) nie posiada żadnych niepustych podzbiorów.
- Załóżmy, że \( n\in P \) i ustalmy dowolne, niepuste \( x\subset n' \). Jeśli \( n\in x \), to, ponieważ pozostałe elementy \( n' \) są podzbiorami \( n \), otrzymujemy \( \bigcup x = \bigcup n' = n\in x \). Jeśli \( n\notin x \), to \( x\subset n \) i, na mocy założenia indukcyjnego otrzymujemy \( \bigcup x\in x \).
Ustalmy teraz dowolny niepusty zbiór liczb naturalnych \( x \) ograniczony z góry przez liczbę naturalną \( y \). Natychmiast otrzymujemy, że \( x\subset y' \) i na mocy dowiedzionej wcześniej własności \( \bigcup x\in x\subset \mathbb{N} \), czyli \( \bigcup x \) jest liczbą naturalną i elementem \( x \). Niewątpliwie \( \bigcup x \) jest nadzbiorem każdego z elementów \( x \), co dowodzi, że \( \bigcup x \) jest elementem maksymalnym zbioru \( x \).