Własności liczb naturalnych

Pierwszym twierdzeniem, które udowodnimy przy użyciu indukcji matematycznej jest twierdzenie mówiące, że każdy element liczby naturalnej jest również liczbą naturalną.

Twierdzenie 4.1.

Każdy element liczby naturalnej jest również liczbą naturalną. Formalnie:
\( \forall x\; x\in\mathbb{N} \Longrightarrow \forall y\;( y\in x \Longrightarrow y\in\mathbb{N}). \)

Dowód

Dowiedziemy tego faktu przez indukcję. Oznaczmy przez \( P \) zbiór tych wszystkich elementów \( \mathbb{N} \) które spełniają naszą własność:

\( P = \{n\in\mathbb{N}\,:\, \forall y\; y\in n \Longrightarrow y\in\mathbb{N}\} \)

Innymi słowy, jest to zbiór liczb naturalnych, dla których dowodzony fakt jest prawdą. Aby móc zastosować Twierdzenie 3.1., musimy wykazać trzy własności zbioru \( P \). Niewątpliwie \( P\subset\mathbb{N} \), skoro \( P \) jest zbiorem niektórych liczb naturalnych. Przechodzimy teraz do pierwszego kroku indukcyjnego.

Po pierwsze musimy wykazać, że \( \emptyset\in P \). Aby to sprawdzić, musimy stwierdzić, czy każdy element zbioru \( \emptyset \) jest liczbą naturalną. Ponieważ \( \emptyset \) nie posiada żadnych elementów nie trzeba niczego dowodzić.
Załóżmy teraz, że \( n\in P \). To oznacza, że każdy element \( n \) jest liczbą naturalną. Rozważmy \( n'=n\cup \{n\} \). Każdy element \( n \) jest liczbą naturalną, na mocy założenia indukcyjnego, również jedyny element \( \{n\} \) równy \( n \) jest liczbą naturalną, ponieważ \( n\in P\subset \mathbb{N} \). W związku z tym każdy z elementów unii \( n\cup\{n\} \) jest również liczbą naturalną. To implikuje, że \( n' \) należy do \( P \).

Udowodniliśmy wszystkie przesłanki Twierdzenia 3.1. i w związku z tym twierdzenie to gwarantuje, że \( P=\mathbb{N} \), czyli że każdy z elementów dowolnej liczby naturalnej jest również liczbą naturalną.

Dowiedziemy teraz paru własności dotyczących liczb naturalnych. Wiemy, że liczbami naturalnymi są \( 0=\emptyset \) oraz następniki liczb naturalnych. Niewątpliwie \( 0 \) nie jest następnikiem żadnej liczby naturalnej, ponieważ następnik dowolnego zbioru posiada przynajmniej jeden element - dla \( n \) mamy \( n\in n' \). Poniższy fakt pokazuje własność przeciwną.

Fakt 4.2.

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

\( \forall x\; x\in\mathbb{N} \Longrightarrow (x = \emptyset \lor \exists y\; (y\in\mathbb{N} \land x=y')) \)

Dowód

Aby dowieść tego faktu skorzystamy z twierdzenia o indukcji matematycznej. Zdefiniujemy zbiór \( P \) jako zbiór elementów spełniających nasze założenia:

\( P = \{n\in\mathbb{N}\,:\, n=\emptyset \lor \exists m\; (m\in\mathbb{N} \land n=m')\}. \)

Aby skorzystać z twierdzenia o indukcji wykażemy, że:

Zbiór pusty jest elementem \( P \) -- jest to oczywista konsekwencja definicji \( P \).

Jeśli \( n\in P \) to również \( n'\in P \). Aby to wykazać, załóżmy, że \( n\in P\subset \mathbb{N} \). Oczywiście \( n' \) jest następnikiem pewnej liczby naturalnej - \( n \).

Na podstawie twierdzenia o indukcji \( P=\mathbb{N} \), czyli fakt jest prawdziwy.

Kolejny fakt mówi o zależnościach pomiędzy różnymi liczbami naturalnymi.

Fakt 4.3.

Dla dowolnej liczby naturalnej \( n \) i dowolnego zbioru \( y \), jeśli \( y\in n \), to \( y\subset n \).

Dowód

Dowód przeprowadzimy indukcyjnie, czyli w oparciu o Twierdzenie 3.1.. Zdefiniujmy zbiór \( P \) jako zbiór tych wszystkich \( n \), elementów \( \mathbb{N} \), które spełniają nasze założenie -- formalnie:

\( P=\{n\in\mathbb{N}\,:\, \forall y\; y\in n \Longrightarrow y\subset n\}. \)

Aby skorzystać z indukcji, należy wykazać dwa fakty:

Oczywiście \( 0=\emptyset\in P \), ponieważ \( \emptyset\in\mathbb{N} \) i warunek \( y \in \emptyset \) jest fałszem, dla wszystkich \( y \).
Załóżmy teraz że \( n\in P \) i dowiedźmy, że \( n' \) jest również elementem \( P \). W tym celu ustalmy dowolny \( y \) taki, że \( y\in n' = n\cup\{n\} \). Rozważamy dwa przypadki - albo \( y\in n \), albo \( y\in\{n\} \) (równoważnie \( y=n \)). Jeśli \( y\in n \), to, na mocy założenia indukcyjnego, \( y\subset n \), a ponieważ \( n\subset n\cup\{n\} \), wnioskujemy, że \( y\subset n' \), co należało wykazać. W drugim przypadku \( y=n \), ale, ponieważ \( n'=n\cup\{n\} \), otrzymujemy natychmiast, że \( y=n\subset n' \), co należało wykazać.

No mocy twierdzenia o indukcji matematycznej \( P=\mathbb{N} \) i fakt jest dowiedziony dla wszystkich liczb naturalnych.

Kilka podobnych własności liczb naturalnych podajemy jako ćwiczenie:

Ćwiczenie 4.1

Jeśli \( m \) i \( n \) są liczbami naturalnymi, to:

1. jeżeli \( m'=n' \), to \( m=n \),

2. jeżeli \( m\subset n \) i \( m\neq n \), to \( m\in n \),

3. \( m\subset n \) lub \( n\subset m \) - czyli wszystkie liczby naturalne są porównywalne przez inkluzję

4. \( m\in n \) albo \( m=n \) albo \( m\ni n \) - czyli dla dowolnych dwóch różnych liczb naturalnych jedna jest elementem drugiej.

Przedstawimy kolejno rozwiązania do powyższych podpunktów:

Rozwiązanie 1

1. Załóżmy, niewprost, że \( m'=n' \) i \( m\neq n \). Skoro \( m'=n' \) i \( m\in m' \), to \( m\in n\cup\{n\} \). Skoro \( m\neq n \) otrzymujemy \( m\in n \) i, na mocy Faktu 4.3., \( m\subset n \). Ponieważ mamy dokładną symetrię pomiędzy \( m \) i \( n \), rozumując podobnie, otrzymujemy: \( n\subset m \), co w sumie implikuje \( m=n \) - sprzeczność z założeniem.

Rozwiązanie 2

2. Drugiego faktu dowiedziemy przez indukcję ze względu na \( n \).

Oznaczmy przez \( P \) zbiór:
\( P=\{n\in\mathbb{N}\,:\, \forall m\; m\in\mathbb{N} \Longrightarrow (m\subset n \land m\neq n \Longrightarrow m \in n)\}. \)

Niewątpliwie \( \emptyset \in P \), ponieważ \( m\subset \emptyset \land m\neq\emptyset \) jest fałszem dla wszystkich \( m \).
Pozostaje wykazać, że jeżeli \( n\in P \), to również \( n'\in P \). W tym celu ustalmy dowolne \( m\in\mathbb{N} \) takie, że \( m\subset n' \land m\neq n' \). Nasze założenie mówi, że \( m\subset n\cup\{n\} \). Jeśli \( m\subset n \) to albo \( m=n \) i pokazaliśmy krok indukcyjny, ponieważ \( m=n\in n' \), albo \( m\neq n \) i wtedy, na mocy założenia indukcyjnego, \( m\in n \) i co za tym idzie \( m\in n' \), ponieważ \( n\subset n' \). Pozostaje rozważyć przypadek, kiedy \( m\not\subset n \), czyli kiedy \( n\in m \). Wtedy Fakt 4.3. gwarantuje, że \( n\subset m\subset n\cup\{n\}=n' \), ale w tym przypadku, \( m\neq n' \) i \( m\neq n \), co daje sprzeczność, gwarantując, że przypadek \( m\not\subset n \) nigdy nie zajdzie.

Korzystając z twierdzenia o indukcji matematycznej, wykazaliśmy, że \( P=\mathbb{N} \), czyli że wszystkie liczby naturalne mają żądaną własność.

Rozwiązanie 3

3. Kolejnego faktu dowodzimy również przez indukcję. Zdefiniujmy \( P \) jako:

\( P = \{n\in\mathbb{N}\,:\, \forall m\; m\in\mathbb{N} \Longrightarrow (n\subset m \lor m\subset n) \}. \)

Bardzo łatwo zauważyć, że \( 0=\emptyset\in P \), ponieważ \( \emptyset \subset m \) jest prawdą, dla każdego \( m \).
Zakładamy, że \( n\in P \) i dowodzimy, że \( n' \) jest również elementem \( P \). W tym celu ustalmy dowolne \( m\in\mathbb{N} \). Na mocy założenia indukcyjnego \( n \subset m \lor m\subset n \). W tym drugim przypadku wnioskujemy, że \( m\subset n\subset n' \) i pokazaliśmy, że \( n'\in P \). Jeśli \( n\subset m \) to albo \( n=m \) (i \( n'\in P \) ponieważ dla każdej liczby naturalnej \( n\subset n' \)), albo \( n\neq m \) i, na mocy poprzedniego punktu \( n\in m \). Wtedy jednak \( n\cup\{n\}\subset m \), co należało dowieść.

Twierdzenie o indukcji gwarantuje, że własność jest prawdziwa dla wszystkich liczb naturalnych.

Rozwiązanie 4

4. Rozważmy dwie liczby naturalne \( n \) i \( m \). Na mocy poprzedniego punktu \( n\subset m \) lub \( m\subset n \). Jeśli \( n\neq m \) to w pierwszym przypadku mamy, na mocy poprzednich ćwiczeń, \( n\in m \), a w drugim \( m\in n \). Na mocy aksjomatu regularności wiemy, że żaden zbiór nie jest swoim własnym elementem, więc \( n=m \) nie może być prawdziwe równocześnie z jakimkolwiek innym warunkiem. Pozostaje rozważyć sytuację kiedy \( m\in n \) i \( n\in m \). Na mocy Faktu 4.3. dostajemy \( m\in n\subset m \) i w końcu \( m\in m \), co daje sprzeczność. W ten sposób pokazaliśmy, że zawsze jest spełniony dokładnie jeden z trzech powyższych warunków.