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 \)

Rozwiązanie 1

\( m=n \) jest równoważne \( m\subset n \) i \( n\subset m \), a to z kolei jest równoważne \( m\leq n \land n\leq m \) - co należało pokazać.

Rozwiązanie 2

Jak wykazaliśmy w wykładzie "Teoria mnogości ZFC. Operacje na zbiorach" aksjomat regularności gwarantuje, że żaden zbiór nie jest swoim własnym elementem. Czyli \( n\notin n \), co należało pokazać.

Rozwiązanie 3

Jeśli \( k\leq m \) i \( m\leq n \), to \( k\subset m \subset n \), czyli \( k\subset n \) i dowód jest zakończony.

Rozwiązanie 4

Jeśli \( k < m \land m\leq n \), to \( k\in m\subset n \), czyli \( k\in n \), co należało wykazać.

Rozwiązanie 5

Jeśli \( k\leq m \land m < n \), to niewątpliwie \( k\leq n \). Wystarczy wykazać, że \( k\neq n \). Jeśli, dla dowodu niewprost, założymy \( k=n \), to z punktu pierwszego tego ćwiczenia wynika, że \( m= n \), co, w połączeniu z założeniami implikuje \( n\in n \) - sprzeczność.

Rozwiązanie 6

Jeśli \( k < m \land m < n \) to \( k < m\land m\leq n \) i na podstawie poprzednich punktów \( k < 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 \).

Podpowiedź

Rozważ \( f(0) \).

Rozwiązanie

Niewątpliwie istnieje przynajmniej jedna taka funkcja \( f \), zdefiniowana jako \( f(n)=n \), dla każdego \( n \). Dla każdej liczby \( n \), na podstawie Wniosku 5.1. mamy:

\( f(n) = n = \{m\in\mathbb{N}\,:\, m < n\} = \vec{f}(\{m\in\mathbb{N}\,:\, m < n\}) = \vec{f}(n). \)

Tak więc funkcja \( f \) spełnia wymagania naszego ćwiczenia. Wykażemy teraz, że dla każdej funkcji \( f':\mathbb{N}arrow\mathbb{N} \) mamy \( f'(n)=f(n) \), dla wszystkich \( n \). Zdefiniujmy zbiór \( P \), do którego będziemy stosować twierdzenie o indukcji.

\( P = \{n\in\mathbb{N}\,:\, f(n) = f'(n)\}. \)

Wykażemy fakty gwarantujące założenia twierdzenia o indukcji:

Liczna \( 0 \) jest elementem \( P \), ponieważ dla dowolnej funkcji mamy \( \vec{f}(\emptyset) = \emptyset \), a więc \( f(0)=\vec{f}(\emptyset) = \emptyset = \vec{f'}(\emptyset) = f'(0) \).
Załóżmy teraz, że twierdzenie jest prawdziwe, dla \( n\in\mathbb{N} \). Wtedy:

\( f(n') = \vec{f}(n') = \vec{f}(n\cup\{n\}) = \vec{f}(n)\cup \vec{f}(\{n\}). \)

Na podstawie założenia indukcyjnego wiemy, że \( f(n) = f'(n) \), czyli że \( \vec{f}(\{n\})=\vec{f'}(\{n\}) \). To samo założenie gwarantuje również, że \( \vec{f}(n)=\vec{f'}(n) \), czyli:

\( f(n') = \vec{f}(n)\cup \vec{f}(\{n\}) = \vec{f'}(n)\cup \vec{f'}(\{n\}) = f'(n'), \)

co dowodzi kroku indukcyjnego.

Na mocy twierdzenia o indukcji \( P=\mathbb{N} \), co dowodzi, że każda funkcja spełniająca nasze założenia musi być identycznością. Udowodniliśmy, że istnieje dokładnie jedna funkcja spełniająca założenia ćwiczenia.

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 \).