Informatyka MIMUW

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