Logika i teoria mnogości/Wykład 7: Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje

Wstęp

John von Neumann (1903-1957)
Zobacz biografię

Liczby naturalne to jedna z najbardziej podstawowych idei matematycznych. Operacje dodawania i mnożenia liczb naturalnych są najczęściej uznawane za najprostsze operacje matematyczne. W aksjomatycznym podejściu do teorii mnogości wszystkie "oczywiste fakty" dotyczące liczb naturalnych należy wywieść z aksjomatów. W pierwszej części tego wykładu wykażemy, że aksjomatyka ZF gwarantuje istnienie zbioru liczb naturalnych. Druga część poświęcona jest dowodzeniu własności tych liczb.

W teorii mnogości liczby naturalne, podobnie jak wszystkie inne byty, muszą być zbiorami. Od aksjomatyki teorii mnogości niewątpliwie należy wymagać, aby gwarantowała ich istnienie. W aksjomatyce ZF opisanej w Wykładzie 4 jako liczby naturalne przyjmuje się zbiory, do których istnienia niezbędny jest aksjomat zbioru pustego, aksjomat pary i aksjomat sumy. Konstrukcja liczb naturalnych przedstawiona w dalszej części wykładu została zaproponowanych przez Johna von Neumanna jak specyficzny przypadek liczb porządkowych, które będą dokładniej przedstawione w Wykładzie 11.

Liczby naturalne definiujemy następująco. Liczbą naturalną zero jest zbiór pusty $\mathrm{\varnothing }$. Każdą następną liczbę naturalną otrzymujemy z poprzedniej w prosty sposób:

jeśli $n$ jest liczbą naturalną, to następną po niej liczbą jest $n^{\prime }\stackrel{\text{def}}{\equiv }\{n\}\cup n$

Początkowe liczby naturalne to:

$\begin{array}{ll}\text{liczba naturalna zero to zbiór }& \mathrm{\varnothing },\\ \text{liczba naturalna jeden to zbiór }& \{\mathrm{\varnothing }\},\\ \text{liczba naturalna dwa to zbiór }& \{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\},\\ \text{liczba naturalna trzy to zbiór }& \{\mathrm{\varnothing },\{\mathrm{\varnothing }\},\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}\},\\ \text{i tak dalej}\dots & \end{array}$

Liczby naturalne to zbiory, których istnienie jest zagwarantowane przez aksjomaty ZF. Intuicyjnie, patrząc na nie widzimy, że posiadają tyle elementów jaka jest "wartość" liczby. Zero, to zbiór pusty, jeden, to zbiór którego jedynym elementem jest $\mathrm{\varnothing }$ i tak dalej.

Zbiory induktywne

Aksjomaty ZF gwarantują więcej. Nie tylko każda z liczb naturalnych istnieje, ale również istnieje zbiór zawierający je wszystkie. Najmniejszy z takich zbiorów nazywamy zbiorem liczb naturalnych. Aby wykazać istnienie tego zbioru, niezbędny jest aksjomat nieskończoności. Przytoczymy jego brzmienie zgodnie z Wykładem 4.

Zakładamy, że następująca formuła, zwana aksjomatem nieskończoności, jest prawdą:

$\mathrm{\exists }x(\mathrm{\varnothing }\in x\wedge (\mathrm{\forall }yy\in x⟹y\cup \{y\}\in x))$

Każdy zbiór $x$ spełniający warunek występujący w aksjomacie nieskończoności nazywamy zbiorem induktywnym. Aksjomat nieskończoności nie nakłada żadnych ograniczeń górnych na zbiory induktywne -- mogą być one dowolnie wielkie. Zbiorem liczb naturalnych będziemy nazywać najmniejszy ze zbiorów induktywnych. Wcześniej jednak musimy udowodnić, że zbiór taki istnieje. Następujące fakty pozwolą nam go zdefiniować.

Lemat 2.1.

Jeśli $x$ jest niepustym zbiorem zbiorów induktywnych to $\bigcap x$ jest również zbiorem induktywnym.

Dowód

Aby wykazać, że $\bigcap x$ jest zbiorem induktywnym, musimy wykazać, że:

• $\mathrm{\varnothing }\in \bigcap x$

oraz że

• $\mathrm{\forall }yy\in \bigcap x⟹y\cup \{y\}\in \bigcap x$.

Ponieważ każdy z elementów $x$ jest zbiorem induktywnym, to $\mathrm{\forall }zz\in x⟹\mathrm{\varnothing }\in z$, czyli zbiór pusty jest w każdym z elementów $x$. Jeśli jakiś zbiór jest w każdym elemencie zbioru, to jest również w jego przecięciu, czyli $\mathrm{\varnothing }\in \bigcap x$. Pozostaje wykazać drugi fakt, weźmy dowolny $y\in \bigcap x$. Natychmiastową konsekwencją jest, że dla każdego $z$, elementu $x$ mamy $y\in z$. Skoro każdy element $x$ jest zbiorem induktywnym, to dla każdego $z$ w $x$ mamy $y\cup \{y\}\in z$ i, z definicji przecięcia, $y\cup \{y\}\in \bigcap x$. W ten sposób udowodniliśmy oba warunki i równocześnie lemat.

Przechodzimy do dowodu głównego twierdzenia. Mówi ono, że istnieje zbiór induktywny będący podzbiorem wszystkich zbiorów induktywnych.

Twierdzenie 2.2.

Istnieje najmniejszy, pod względem inkluzji, zbiór induktywny.

Dowód

Na mocy aksjomatu nieskończoności istnieje co najmniej jeden zbiór induktywny -- oznaczmy go przez $x$. Rozważmy wszystkie podzbiory ${𝒫}(x)$ tego zbioru i wybierzmy z nich, na mocy aksjomatu wyróżniania, zbiory induktywne -- powstały w ten sposób podzbiór ${𝒫}(x)$ nazwijmy $y$. Zbiór $y$ jest niepusty, ponieważ $x\in y$ jest zagwarantowane przez fakt, że $x\subset x$ i założenie mówiące, że $x$ jest zbiorem induktywnym. Wnioskujemy, że zbiór $y$ spełnia założenia Lematu 2.1 (patrz lemat 2.1.) i w związku z tym $\bigcap y$ jest zbiorem induktywnym.

Postulujemy, że zbiór $\bigcap y$ jest najmniejszym zbiorem induktywnym. Aby to wykazać, pokażemy, że dla dowolnego zbioru induktywnego $z$ mamy $\bigcap y\subset z$. Ustalmy dowolny zbiór induktywny $z$, na mocy Lematu 2.1 (patrz lemat 2.1.), zastosowanego do zbioru $\{x,z\}$ otrzymujemy, że $x\cap z$ jest zbiorem induktywnym. W związku z tym $x\cap z\in y$ i dalej $\bigcap y\subset x\cap z\subset z$. To dowodzi, że zbiór $\bigcap y$ jest podzbiorem każdego zbioru induktywnego, czyli najmniejszym pod względem inkluzji zbiorem induktywnym.

Natychmiastowym wnioskiem jest, że zbiór taki jest jedyny.

Wniosek 2.3.

Istnieje unikalny, najmniejszy pod względem inkluzji, zbiór induktywny.

Dowód

Ustalmy dwa dowolne, najmniejsze pod względem inkluzji zbiory induktywne $x$ i $y$. Wtedy $x\subset y$ i $y\subset x$, skąd wnioskujemy, że $x=y$, co należało wykazać.

Tak skonstruowany zbiór nazywamy zbiorem liczb naturalnych.

Definicja 2.4.

Najmniejszy pod względem inkluzji zbiór induktywny nazywamy zbiorem liczb naturalnych i oznaczamy, przez $\mathbb{\mathbb{N}}$. Elementy tego zbioru nazywamy liczbami naturalnymi.

Skonstruowaliśmy, przy pomocy aksjomatów ZF zbiór posiadający pewne własności i nazwaliśmy go zbiorem liczb naturalnych. Zbiór ten niewątpliwie zawiera liczbę zero, zdefiniowaną wcześniej jako zbiór pusty. Zawiera również liczbę jeden $1=0^{\prime }=\{\mathrm{\varnothing }\}$, ponieważ zawiera $0$ i dla każdego elementu zawiera również jego następnik. Każda, z intuicyjnie oczywistych własności liczb naturalnych, musi być wykazana na gruncie aksjomatów ZF zanim uznamy ją za prawdziwą. Pozostała część tego wykładu poświęcona jest dowodzeniu podstawowych faktów dotyczących liczb naturalnych.

Indukcja matematyczna

Podstawową metodą dowodzenia twierdzeń o liczbach naturalnych jest zasada indukcji matematycznej. Używając aksjomatów, możemy wykazać, że indukcja matematyczna działa. Formalnie, dla dowolnej własności, którą chcemy dowodzić przez indukcję, definiujemy zbiór elementów, które ją spełniają. Jeśli zbiór ten spełnia wymagane własności, jest on równy zbiorowi liczb naturalnych, czyli własność jest prawdą dla wszystkich liczb naturalnych. W formalny sposób przedstawia to poniższe twierdzenie.

Twierdzenie 3.1. [o indukcji matematycznej]

Dla dowolnego zbioru $P$ jeśli $P\subset \mathbb{\mathbb{N}}$

• $\mathrm{\varnothing }\in P$

oraz

• $\mathrm{\forall }xx\in P⟹x^{\prime }=x\cup \{x\}\in P$,

to $P=\mathbb{\mathbb{N}}$.

Dowód

Ustalmy dowolny zbiór $P$ spełniający założenia twierdzenia. Zbiór $P$ jest zbiorem induktywnym, a więc, na mocy definicji zbioru liczb naturalnych, $\mathbb{\mathbb{N}}\subset P$. Równocześnie założyliśmy, że $P\subset \mathbb{\mathbb{N}}$ i w związku z tym $P=\mathbb{\mathbb{N}}$, co dowodzi twierdzenia.

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:

$\mathrm{\forall }xx\in \mathbb{\mathbb{N}}⟹\mathrm{\forall }y(y\in x⟹y\in \mathbb{\mathbb{N}})$

Dowód

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

$P=\{n\in \mathbb{\mathbb{N}}:\mathrm{\forall }yy\in n⟹y\in \mathbb{\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. (patrz twierdzenie 3.1.), musimy wykazać trzy własności zbioru $P$. Niewątpliwie $P\subset \mathbb{\mathbb{N}}$, skoro $P$ jest zbiorem niektórych liczb naturalnych. Przechodzimy teraz do pierwszego kroku indukcyjnego.

• Po pierwsze musimy wykazać, że $\mathrm{\varnothing }\in P$. Aby to sprawdzić, musimy stwierdzić, czy każdy element zbioru $\mathrm{\varnothing }$ jest liczbą naturalną. Ponieważ $\mathrm{\varnothing }$ 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^{\prime }=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{\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^{\prime }$ należy do $P$.

Udowodniliśmy wszystkie przesłanki Twierdzenia 3.1. (patrz twierdzenie 3.1.) i w związku z tym twierdzenie to gwarantuje, że $P=\mathbb{\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=\mathrm{\varnothing }$ 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^{\prime }$. Poniższy fakt pokazuje własność przeciwną.

Fakt 4.2.

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

$\mathrm{\forall }xx\in \mathbb{\mathbb{N}}⟹(x=\mathrm{\varnothing }\vee \mathrm{\exists }y(y\in \mathbb{\mathbb{N}}\wedge x=y^{\prime }))$

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{\mathbb{N}}:n=\mathrm{\varnothing }\vee \mathrm{\exists }m(m\in \mathbb{\mathbb{N}}\wedge n=m^{\prime })\}$

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^{\prime }\in P$. Aby to wykazać, załóżmy, że $n\in P\subset \mathbb{\mathbb{N}}$. Oczywiście $n^{\prime }$ jest następnikiem pewnej liczby naturalnej - $n$.

Na podstawie twierdzenia o indukcji $P=\mathbb{\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. (patrz twierdzenie 3.1.). Zdefiniujmy zbiór $P$ jako zbiór tych wszystkich $n$, elementów $\mathbb{\mathbb{N}}$, które spełniają nasze założenie -- formalnie:

$P=\{n\in \mathbb{\mathbb{N}}:\mathrm{\forall }yy\in n⟹y\subset n\}$

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

• Oczywiście $0=\mathrm{\varnothing }\in P$, ponieważ $\mathrm{\varnothing }\in \mathbb{\mathbb{N}}$ i warunek $y\in \mathrm{\varnothing }$ jest fałszem, dla wszystkich $y$.
• Załóżmy teraz że $n\in P$ i dowiedźmy, że $n^{\prime }$ jest również elementem $P$. W tym celu ustalmy dowolny $y$ taki, że $y\in n^{\prime }=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^{\prime }$, co należało wykazać. W drugim przypadku $y=n$, ale, ponieważ $n^{\prime }=n\cup \{n\}$, otrzymujemy natychmiast, że $y=n\subset n^{\prime }$, co należało wykazać.

No mocy twierdzenia o indukcji matematycznej $P=\mathbb{\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^{\prime }=n^{\prime }$, to $m=n$,

2. jeżeli $m\subset n$ i $m\ne 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^{\prime }=n^{\prime }$ i $m\ne n$. Skoro $m^{\prime }=n^{\prime }$ i $m\in m^{\prime }$, to $m\in n\cup \{n\}$. Skoro $m\ne n$ otrzymujemy $m\in n$ i, na mocy Faktu 4.3. (patrz fakt 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{\mathbb{N}}:\mathrm{\forall }mm\in \mathbb{\mathbb{N}}⟹(m\subset n\wedge m\ne n⟹m\in n)\}$

• Niewątpliwie $\mathrm{\varnothing }\in P$, ponieważ $m\subset \mathrm{\varnothing }\wedge m\ne \mathrm{\varnothing }$ jest fałszem dla wszystkich $m$.
• Pozostaje wykazać, że jeżeli $n\in P$, to również $n^{\prime }\in P$. W tym celu ustalmy dowolne $m\in \mathbb{\mathbb{N}}$ takie, że $m\subset n^{\prime }\wedge m\ne n^{\prime }$. 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^{\prime }$, albo $m\ne n$ i wtedy, na mocy założenia indukcyjnego, $m\in n$ i co za tym idzie $m\in n^{\prime }$, ponieważ $n\subset n^{\prime }$. Pozostaje rozważyć przypadek, kiedy $m\subset ̸n$, czyli kiedy $n\in m$. Wtedy Fakt 4.3. (patrz fakt 4.3.) gwarantuje, że $n\subset m\subset n\cup \{n\}=n^{\prime }$, ale w tym przypadku, $m\ne n^{\prime }$ i $m\ne n$, co daje sprzeczność, gwarantując, że przypadek $m\subset ̸n$ nigdy nie zajdzie.

Korzystając z twierdzenia o indukcji matematycznej, wykazaliśmy, że $P=\mathbb{\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{\mathbb{N}}:\mathrm{\forall }mm\in \mathbb{\mathbb{N}}⟹(n\subset m\vee m\subset n)\}$

• Bardzo łatwo zauważyć, że $0=\mathrm{\varnothing }\in P$, ponieważ $\mathrm{\varnothing }\subset m$ jest prawdą, dla każdego $m$.
• Zakładamy, że $n\in P$ i dowodzimy, że $n^{\prime }$ jest również elementem $P$. W tym celu ustalmy dowolne $m\in \mathbb{\mathbb{N}}$. Na mocy założenia indukcyjnego $n\subset m\vee m\subset n$. W tym drugim przypadku wnioskujemy, że $m\subset n\subset n^{\prime }$ i pokazaliśmy, że $n^{\prime }\in P$. Jeśli $n\subset m$ to albo $n=m$ (i $n^{\prime }\in P$ ponieważ dla każdej liczby naturalnej $n\subset n^{\prime }$), albo $n\ne 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\ne 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. (patrz fakt 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.

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\le n\stackrel{\text{def}}{\equiv }m\subset n$

oraz

$m<n\stackrel{\text{def}}{\equiv }m\in n$

Przy takim zdefiniowaniu relacji Fakt 4.3. (patrz fakt 4.3.) i poprzednie ćwiczenie natychmiast gwarantują, że dla dowolnych liczb naturalnych $m$ i $n$:

• $m<n⟹m\le n$,

• $(m\le n\wedge m\ne n)⟹m<n$,

• $m\le n\vee n\le m$,

• $m<n\vee m=n\vee 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⟺(m\le n\wedge n\le m)$,

2. $\mathrm{\neg }(n<n)$,

3. $(k\le m\wedge m\le n)⟹k\le n$,

4. $(k<m\wedge m\le n)⟹k<n$,

5. $(k\le m\wedge m<n)⟹k<n$,

6. $(k<m\wedge m<n)⟹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\le n\wedge n\le m$ - co należało pokazać.

Rozwiązanie 2

Jak wykazaliśmy w Wykładzie 4 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\le m$ i $m\le n$, to $k\subset m\subset n$, czyli $k\subset n$ i dowód jest zakończony.

Rozwiązanie 4

Jeśli $k<m\wedge m\le n$, to $k\in m\subset n$, czyli $k\in n$, co należało wykazać.

Rozwiązanie 5

Jeśli $k\le m\wedge m<n$, to niewątpliwie $k\le n$. Wystarczy wykazać, że $k\ne 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\wedge m<n$ to $k<m\wedge m\le 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:

$\mathrm{\forall }nn\in \mathbb{\mathbb{N}}⟹(\mathrm{\forall }zz\in n⟺(z\in \mathbb{\mathbb{N}}\wedge 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. (patrz twierdzenie 4.1.) i definicji $<$.

Ćwiczenie 5.2

Ile jest funkcji $f:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$ takich, że $\overrightarrow{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. (patrz wniosek 5.1.) mamy:

$f(n)=n=\{m\in \mathbb{\mathbb{N}}:m<n\}=\overrightarrow{f}(\{m\in \mathbb{\mathbb{N}}:m<n\})=\overrightarrow{f}(n)$

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

$P=\{n\in \mathbb{\mathbb{N}}:f(n)=f^{\prime }(n)\}$

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

• Liczna $0$ jest elementem $P$, ponieważ dla dowolnej funkcji mamy $\overrightarrow{f}(\mathrm{\varnothing })=\mathrm{\varnothing }$, a więc $f(0)=\overrightarrow{f}(\mathrm{\varnothing })=\mathrm{\varnothing }=\overrightarrow{f^{\prime }}(\mathrm{\varnothing })=f^{\prime }(0)$.
• Załóżmy teraz, że twierdzenie jest prawdziwe, dla $n\in \mathbb{\mathbb{N}}$. Wtedy:

$f(n^{\prime })=\overrightarrow{f}(n^{\prime })=\overrightarrow{f}(n\cup \{n\})=\overrightarrow{f}(n)\cup \overrightarrow{f}(\{n\})$

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

$f(n^{\prime })=\overrightarrow{f}(n)\cup \overrightarrow{f}(\{n\})=\overrightarrow{f^{\prime }}(n)\cup \overrightarrow{f^{\prime }}(\{n\})=f^{\prime }(n^{\prime })$,

co dowodzi kroku indukcyjnego.

Na mocy twierdzenia o indukcji $P=\mathbb{\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 $\le$. Pozwala ono dowody przez indukcję zamieniać na dowody niewprost. Zamiast przeprowadzać dowód indukcyjny dla zbioru $P$, rozważyć możemy zbiór $\mathbb{\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{\mathbb{N}}:\mathrm{\forall }x(x\subset \mathbb{\mathbb{N}}\wedge x\cap n\ne \mathrm{\varnothing })⟹\bigcap x\in x\}$

Zbiór $P$ zawiera takie liczby naturalne, że dla dowolnego zbioru liczb naturalnych $x$ jeśli $x\cap n\ne \mathrm{\varnothing }$ (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{\mathbb{N}}$.

• Niewątpliwie $0\in P$, ponieważ, dla dowolnego, $x$ fałszem jest $x\cap \mathrm{\varnothing }\ne \mathrm{\varnothing }$.
• Załóżmy, że $n\in P$ i ustalmy zbiór $x$ taki, że $x\subset \mathbb{\mathbb{N}}$ i $x\cap n^{\prime }\ne \mathrm{\varnothing }$. Ponieważ $n^{\prime }=n\cup \{n\}$ naturalnie jest rozważyć dwa przypadki. Jeśli $x\cap n\ne \mathrm{\varnothing }$, otrzymujemy $\bigcap x\in x$ na mocy założenia indukcyjnego. W przeciwnym przypadku $x\cap n=\mathrm{\varnothing }$, czyli $x\cap n^{\prime }=\{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=\mathrm{\varnothing }$. To wykazuje, że dla każdego $z\in \mathbb{\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{\mathbb{N}}$. Niewątpliwie istnieje $n\in \mathbb{\mathbb{N}}$ takie, że $n\in x$. Wtedy $n^{\prime }\cap x\ne \mathrm{\varnothing }$, ponieważ $n\in n^{\prime }\cap x$. Na mocy dowiedzionego chwilę wcześniej faktu wnioskujemy, że $\bigcap x\in x\subset \mathbb{\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^{\prime }$ jest również liczbą naturalną i $n^{\prime }>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.:

$\mathrm{\exists }yy\in \mathbb{\mathbb{N}}\wedge \mathrm{\forall }zz\in x⟹z\le y$,

to $x$ posiada element największy, tzn.:

$\mathrm{\exists }yy\in x\wedge \mathrm{\forall }zz\in x⟹z\le 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{\mathbb{N}}:\mathrm{\forall }x(x\ne \mathrm{\varnothing }\wedge x\subset n)⟹\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=\mathrm{\varnothing }\in P$, ponieważ $\mathrm{\varnothing }$ nie posiada żadnych niepustych podzbiorów.
• Załóżmy, że $n\in P$ i ustalmy dowolne, niepuste $x\subset n^{\prime }$. Jeśli $n\in x$, to, ponieważ pozostałe elementy $n^{\prime }$ są podzbiorami $n$, otrzymujemy $\bigcup x=\bigcup n^{\prime }=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^{\prime }$ i na mocy dowiedzionej wcześniej własności $\bigcup x\in x\subset \mathbb{\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$.

Definiowanie przez indukcję

Następujące twierdzenie pozwala nam zdefiniować dodawanie, mnożenie i wiele ważnych operacji na liczbach naturalnych. Twierdzenie to mówi, że jeśli wiemy, jak zdefiniować pewną operację dla zera oraz jak zdefiniować ją dla następnika danej liczby, to możemy zdefiniować ją równocześnie dla wszystkich liczb.

Twierdzenie 6.1. [o definiowaniu przez indukcję]

Niech $A$ i $B$ będą zbiorami, a $f:A\to B$ i $g:B\times \mathbb{\mathbb{N}}\times A\to B$ funkcjami. Istnieje unikalna funkcja $h:\mathbb{\mathbb{N}}\times A\to B$ taka, że:

$\begin{array}{rl}& h(0,a)=f(a),\text{ dla każdego }a\in A,\\ & h(n^{\prime },a)=g(h(n,a),n,a),\text{ dla każdego }a\in A\text{ i }n\in \mathbb{\mathbb{N}}.\end{array}$

Dowód

Dowód istnienia funkcji $h$ będzie się opierał na analizie elementów następującego zbioru:

$H=\{e:\mathrm{\exists }mm\in \mathbb{\mathbb{N}}\wedge e:m^{\prime }\times A\to B\wedge \text{(*)}\}$,

gdzie

$\begin{array}{rl}& e(0,a)=f(a),\text{ dla każdego }a\in A,\\ & e(g(n,a),n,a),\text{ dla każdego }a\in A\text{ i }n\in m\text{(*)}\end{array}$

Zbiór $H$ jest to zbiór funkcji, które częściowo rozwiązują nasz problem -- funkcje ze zbioru $H$ działają dla liczb naturalnych mniejszych niż pewne, ustalone $m$. Funkcja $h$, której istnienia dowodzimy, powinna działać dla wszystkich liczb naturalnych.

W pierwszej części dowiedziemy, że zbiór $H$ jest niepusty i, co więcej, zawiera przynajmniej jedną funkcję $e:m^{\prime }\times A\to B$ dla każdej liczby naturalnej $m$. Dowód jest indukcyjny -- zdefiniujmy zbiór $P$ jako zbiór tych liczb, dla których istnieją odpowiednie funkcje w $H$:

$P=\{m\in \mathbb{\mathbb{N}}:\mathrm{\exists }ee:m^{\prime }\times A\to B\wedge e\in H\}$

Dowiedziemy indukcyjnie, że $P=\mathbb{\mathbb{N}}$:

• Niewątpliwie $0\in P$ ponieważ funkcja $e:\{0\}\times A\to B$ zdefiniowana jako $e(0,a)=f(a)$ jest elementem $H$.
• Załóżmy, że $m\in P$. To oznacza, że istnieje funkcja $e:m^{\prime }\times A\to B$ spełniająca (*). Funkcja $e^{\prime }$

zdefiniowana jako:

$e^{\prime }(n,a)=\{\begin{array}{ll}e(n,a),& \text{jeśli }n\in m^{\prime },\\ g(e(n,a),n,a),& \text{jeśli}n=m^{\prime },\end{array}$

przeprowadza $m^{″}\times A$ w $B$ i należy do $H$, gwarantując, że $m^{\prime }\in P$.

Na podstawie twierdzenia o indukcji istnieje funkcja $e:m^{\prime }\times A\to B$ należąca do $H$, dla każdego $m\in \mathbb{\mathbb{N}}$.

Kolejną rzeczą jako wykażemy jest to, że dowolne funkcje $e\in H$ i $e^{\prime }\in H$ dla tych samych argumentów zwracają takie same wyniki (oczywiście zakładając, że argumenty należą do przecięcia dziedzin tych funkcji). Nasz dowód przebiega niewprost. Załóżmy że funkcje $e,e^{\prime }\in H$ są takie, że istnieje $n\in \mathbb{\mathbb{N}}$ i $a\in A$ spełniające $e(n,a)\ne e^{\prime }(n,a)$. Zastosujmy Twierdzenie 5.2. (patrz twierdzenie 5.2.) do zbioru tych wszystkich $n$, dla których istnieje $a\in A$ spełniające $e(n,a)\ne e^{\prime }(n,a)$ (na mocy naszego założenia zbiór ten jest niepusty). Otrzymujemy najmniejszą liczbę naturalną $n$ taką, że $e(n,a)\ne e^{\prime }(n,a)$. Liczba $n$ nie może być równa $0$, bo wtedy $e(0,a)=f(a)=e^{\prime }(0,a)$, więc, na mocy Faktu 4.2. (patrz fakt 4.2.) $n=k^{\prime }$, dla pewnego $k$. Ponieważ $k<n$, więc $e(k,a)=e^{\prime }(k,a)$ i otrzymujemy sprzeczność dzięki:

$e(n,a)=e(k^{\prime },a)=g(e(k,a),k,a)=g(e^{\prime }(k,a),k,a)=e^{\prime }(k^{\prime },a)=e^{\prime }(n,a)$

Dowód twierdzenia kończymy, definiując $h=\bigcup H$. Na mocy wcześniejszego faktu $h$ jest funkcją, a na mocy faktu, który dowodziliśmy indukcyjnie dziedziną $h$ jest zbiór liczb naturalnych. Warunki stawiane $h$ są spełnione w sposób oczywisty dzięki definicji zbioru $H$.

Aby wykazać unikalność funkcji $h$ załóżmy, że istnieje funkcja $h^{\prime }\ne h$ spełniająca tezę twierdzenia. Wnioskujemy, że istnieje $n\in \mathbb{\mathbb{N}}$ i $a\in A$ takie, że $h(n,a)\ne h^{\prime }(n,a)$. Wtedy jednak $h^{\prime }$ zawężone do $n^{\prime }$ jest elementem zbioru $H$, co stoi w sprzeczności z faktem wykazanym o $H$.

Operacje na liczbach naturalnych

Definiowanie przez indukcję pozwala nam na wprowadzenie podstawowych operacji arytmetycznych na liczbach naturalnych. Jako pierwszą z tych operacji wprowadzimy dodawanie.

Dodawanie liczb naturalnych

Dodawanie jest funkcją dwuargumentową przekształcającą $\mathbb{\mathbb{N}}\times \mathbb{\mathbb{N}}$ w $\mathbb{\mathbb{N}}$. Aby wykazać istnienie dodawania, korzystamy z twierdzenia o indukcji, kładąc za $A$ i $B$ zbiór liczb naturalnych $\mathbb{\mathbb{N}}$ i definiując $f(n)=n$ oraz $g(m,n,p)=m^{\prime }$. Na mocy twierdzenia o definiowaniu przez indukcję istnieje funkcja $h:{\mathbb{\mathbb{N}}}^2\to \mathbb{\mathbb{N}}$ taka, że $h(0,m)=m$ i $h(n^{\prime },m)=h(n,m{)}^{\prime }$. Funkcja ta to dodawanie liczb naturalnych i będziemy używać zwyczajnej notacji $h(n,m)=n+m$. Zgodnie z intuicją, dla dowolnej liczby naturalnej $n$ mamy $n^{\prime }=n+1$.

Jedyną udowodnioną w tej chwili własnością funkcji zapisywanej przez $+$ są wynikające wprost z definicji własności. Wiemy, że,

$0+n=n$,

dla każdego liczby naturalnej $n$ oraz że,

$n^{\prime }+m=(n+m{)}^{\prime }$,

dla dowolnych liczb $n$ i $m$. Poniżej przedstawiamy parę podstawowych faktów dotyczących dodawania liczb naturalnych.

Fakt 7.1.

Jeśli suma dwóch liczb jest równa $0$, to obie liczby muszą być równe $0$.

Dowód

Załóżmy, że dla dwu liczb naturalnych $n$ i $m$ zachodzi $n+m=0$. Jeśli liczba $n$ jest następnikiem jakiejś liczby naturalnej, to również $n+m$ jest następnikiem jakiejś liczby i w związku z tym $n+m\ne 0$. Na podstawie Faktu 4.2. (patrz fakt 4.2.) wnioskujemy, że $n=0$. Wtedy $0+m=m$ i otrzymujemy $m=0$, co należało wykazać.

Kolejny fakt mówi o łączności dodawania liczb naturalnych.

Fakt 7.2.

Dodawanie liczb naturalnych jest łączne. Formalnie:

$\mathrm{\forall }k\mathrm{\forall }m\mathrm{\forall }n(k\in \mathbb{\mathbb{N}}\wedge m\in \mathbb{\mathbb{N}}\wedge n\in \mathbb{\mathbb{N}})⟹k+(m+n)=(k+m)+n$

Dowód

Dowód jest indukcją ze względu na $k$.

• Jeśli $k=0$, to $0+(m+n)=m+n$ oraz $0+m=m$ i w związku z tym $(0+m)+n=m+n$, co należało pokazać.
• Zakładamy, że równość jest prawdziwa dla $k$ (dla

dowolnych $m$ i $n$). Ustalmy dowolne liczby naturalne $m$ i $n$, wtedy:

$k^{\prime }+(m+n)=(k+(m+n){)}^{\prime }=((k+m)+n{)}^{\prime }=(k+m{)}^{\prime }+n=(k^{\prime }+m)+n$

gdzie druga równość wynika z założenia indukcyjnego, a wszystkie pozostałe równości z definicji funkcji $+$.

Dzięki twierdzenie o indukcji matematycznej dodawanie jest łączne dla wszystkich liczb naturalnych.

Dalsze własności dodawania liczb naturalnych prezentujemy jako ćwiczenie.

Ćwiczenie 7.1

Dla dowolnych liczb naturalnych $k,m$ i $n$ udowodnij:

1. $n+0=n$,

2. $k^{\prime }+m=k+m^{\prime }$,

3. $k+m=m+k$, czyli dodawanie jest przemienne,

4. jeśli $k+n=m+n$, to $k=m$, czyli dodawanie jest skracalne,

5. jeśli $k>m$, to istnieje $n>0$ takie, że $k=m+n$.

Rozwiązanie 1

Dowód 1

Dowodzimy przez indukcję na $n$. Niewątpliwie $0+0=0$. Jeśli $n+0=n$, to $n^{\prime }+0=(n+0{)}^{\prime }=n^{\prime }$, gdzie druga równość wywodzi się z założenia indukcyjnego. Na mocy twierdzenia o indukcji $n+0=n$, dla każdej liczby naturalnej $n$.

Rozwiązanie 2

Dowód 2

Dowodzimy ten fakt przez indukcję na $k$. Niewątpliwie, dla $k=0$ i dla dowolnego $m$, mamy: $0^{\prime }+m=(0+m{)}^{\prime }=m^{\prime }=0+m^{\prime }$. Pozostaje założyć, że fakt jest prawdą dla $k$ i wykazać go dla $k^{\prime }$. Dla dowolnego $m$:

$k^{″}+m=(k^{\prime }+m{)}^{\prime }=(k+m^{\prime })=k^{\prime }+m^{\prime }$,

co dowodzi kroku indukcyjnego i całego faktu.

Rozwiązanie 3

Dowód 3

Przemienności dodawania dowodzimy przez indukcję na $k$. Niewątpliwie, dla $k=0$ i dla dowolnego $m$, mamy $0+m=m=m+0$. Załóżmy teraz, że teza jest prawdziwa dla $k$ i dla dowolnych $m$. Ustalmy dowolne $m$, wtedy:

$k^{\prime }+m=(k+m{)}^{\prime }=(m+k{)}^{\prime }=m^{\prime }+k$,

gdzie druga równość jest konsekwencją założenia indukcyjnego. Korzystając z poprzedniego ćwiczenia, dostajemy: $m^{\prime }+k=m+k^{\prime }$, co dowodzi, że dla dowolnego $m$ mamy $k^{\prime }+m=m+k^{\prime }$. Używając twierdzenia o indukcji konkludujemy, że dodawanie w liczbach naturalnych jest przemienne.

Rozwiązanie 4

Dowód 4

Tę własność dowodzimy indukcją na $n$. Jeśli $n=0$, to $k+0=m+0$ niewątpliwie implikuje, że $k=m$. Załóżmy, że własność skracania zachodzi dla $n$ (dla dowolnych $k$ i $m$), wtedy:

$k+n^{\prime }=n^{\prime }+k=(n+k{)}^{\prime }=(k+n{)}^{\prime }$

i podobne rozumowanie jest prawdziwe dla $m+n^{\prime }$, dając,

$(k+n{)}^{\prime }=(m+n{)}^{\prime }$

Na podstawie wcześniejszych ćwiczeń wiemy, że jeżeli następniki liczb są sobie równe, to liczby też muszą być równe, więc:

$k+n=m+n$

Co, po zastosowaniu założenia indukcyjnego gwarantuje, że $k=m$. Twierdzenie o indukcji powoduje, że dodawanie jest skracalne.

Rozwiązanie 5

Dowód 5

Dowodzimy tego faktu przez indukcję na $k$. Jeśli $k$ jest równe $0$, to nie istnieje $m<k$, czyli teza jest prawdziwa. Załóżmy teraz, że teza jest prawdziwa dla $k$ i dla wszystkich $m<k$. Ustalmy $k^{\prime }$ i dowolne $m<k^{\prime }$. Jeśli $m=k$, to bierzemy $n=1$ i $k^{\prime }=m+1$ dowodzi kroku indukcyjnego. Jeśli $m<k$, to, na podstawie założenia indukcyjnego, istnieje $n$ takie, że:

$k=m+n$

Wtedy $k^{\prime }=(m+n{)}^{\prime }=m+n^{\prime }$, co otrzymujemy, korzystając z poprzednich identyczności. Krok indukcyjny został dowiedziony i, na podstawie twierdzenia o indukcji, fakt jest prawdą dla wszystkich liczb naturalnych.

Ćwiczenie 7.2

Wykaż, że dla dowolnych liczb naturalnych $k$ i $n$:

1. jeśli $n\ne 0$, to $k+n>k$,

2. $k+n\ge k$.

Rozwiązanie 1

Dowód 1

Pierwszego punktu dowodzimy przez indukcję względem $k$. Jeśli $k=0$ , to $n=0+n>0$, dla dowolnego $n\ne 0$. Dla dowodu kroku indukcyjnego załóżmy, że dla każdego $n\ne 0$ mamy $k+n>k$. Ustalmy dowolne $n\ne 0$, wtedy $k^{\prime }+n=(k+n{)}^{\prime }$, korzystając z faktu, że $k+n>k$ dostajemy:

$k^{\prime }+n>k^{\prime }$,

co należało wykazać.

Rozwiązanie 2

Dowód 2

Aby wykazać nierówność rozpatrujemy przypadki ze względu na $n$. Jeśli $n\ne 0$ z poprzedniego podpunktu otrzymujemy, że $k+n>k$, czyli $k+n\ge k$. Jeśli $n=0$, to $k+0=k\ge k$, co kończy dowód.

Mnożenie liczb naturalnych

Podobnie do dodawania możemy zdefiniować mnożenie. Stosujemy twierdzenie o definiowaniu przez indukcję do $A=B=\mathbb{\mathbb{N}}$ oraz $f(n)=0$ i $g(m,n,p)=m+p$. Twierdzenie o definiowaniu przez indukcję gwarantuje istnienie funkcji $h:{\mathbb{\mathbb{N}}}^2\to \mathbb{\mathbb{N}}$ takiej, że:

$h(0,m)=0$

oraz:

$h(n^{\prime },m)=h(n,m)+m$

Funkcję $h$ definiującą mnożenie oznaczamy w notacji infiksowej symbolem $\cdot$ tak, że $n\cdot m=h(n,m)$. Podobnie jak dla dodawania musimy wykazać własności dotyczące mnożenia liczb naturalnych, posługując się wyłącznie powyższą definicją.

Fakt 7.3.

Dla dowolnej liczby naturalnej $k$ mamy $k\cdot 1=k$.

Dowód

Dowód tego faktu jest indukcją ze względu na $k$. Jeśli $k=0$, to $0\cdot 1=0$. Jeśli równość jest prawdą dla $k$, to $k^{\prime }\cdot 1=k\cdot 1+1$, co, na mocy założenia indukcyjnego, jest równe $k+1=k^{\prime }$. Dowiedliśmy kroku indukcyjnego, a co za tym idzie całej identyczności.

Kolejne własności przedstawiamy w formie ćwiczeń.

Ćwiczenie 7.3

Wykaż, że dla dowolnych liczb naturalnych $k,m$ i $n$ zachodzi:

1. $k\cdot (m+n)=k\cdot m+k\cdot n$ - dodawanie jest rozdzielne względem mnożenia z prawej strony,

2. $(k+m)\cdot n=k\cdot n+m\cdot n$ - dodawanie jest rozdzielne względem mnożenia z lewej strony,

3. $k\cdot (m\cdot n)=(k\cdot m)\cdot n$ - mnożenie jest łączne,

4. $k\cdot 0=0$,

5. $k\cdot m=0$ wtedy i tylko wtedy, kiedy $k=0\vee m=0$,

6. $k\cdot m=m\cdot k$ - mnożenie jest przemienne,

7. jeśli $k\cdot n=m\cdot n$ i $n\ne 0$ to $k=m$.

Rozwiązanie 1

Dowód 1

Pierwszego faktu dowodzimy przez indukcję na $k$. Jeżeli $k=0$, to zarówno $0\cdot (m+n)$ jak i $0\cdot m$ oraz $0\cdot n$ są równe zero i równość jest prawdziwa. Jeśli równość jest prawdziwa dla $k$ i dla dowolnych $m$ i $n$, to dla $k^{\prime }$:

$k^{\prime }\cdot (m+n)=k\cdot (m+n)+(m+n)=(k\cdot m+k\cdot n)+(m+n)=$

na mocy założenia indukcyjnego i dalej:

$=(k\cdot m+m)+(k\cdot n+n)=$

używając przemienności i łączności dodawania. W końcu:

$=k^{\prime }\cdot m+k^{\prime }\cdot n$,

co należało pokazać dla kroku indukcyjnego. Twierdzenie o indukcji gwarantuje, że równość jest prawdą dla wszystkich $k$.

Rozwiązanie 2

Dowód 2

Przedstawiamy dowód przez indukcję na $k$. Jeśli $k=0$, to lewa strona równości jest równa $(0+m)\cdot n=m\cdot n$, a prawa $0\cdot n+m\cdot n=0+m\cdot n=m\cdot n$, czyli równość jest prawdą. Jeśli równość jest prawdziwa dla $k$ (przy dowolnych $m$ i $n$) to dla $k^{\prime }$, (i dowolnych $m$ i $n$):

$(k^{\prime }+m)\cdot n=(k+m{)}^{\prime }\cdot n=(k+m)\cdot n+n=(k\cdot n+m\cdot n)+n=$

korzystając z założenia indukcyjnego. Dalej, używając przemienności i łączności dodawania, dostajemy:

$=(k\cdot n+n)+m\cdot n=k^{\prime }\cdot n+m\cdot n$,

co dowodzi kroku indukcyjnego i, co za tym idzie, prawdziwości tezy.

Rozwiązanie 3

Dowód 3

Dowód przez indukcję na $k$. Jeśli $k=0$, to $0\cdot (m\cdot n)=0$, również $0\cdot m=0$ i $(0\cdot m)\cdot n=0$, co dowodzi podstawy indukcji. Załóżmy teraz, że równość jest prawdą dla $k$ i dla dowolnych $m$ i $n$. Ustalmy dowolne $m$ i $n$ i:

$k^{\prime }\cdot (m\cdot n)=k\cdot (m\cdot n)+(m\cdot n)=(k\cdot m)\cdot n+(m\cdot n)=$

na mocy założenia indukcyjnego. Dalej:

$=((k\cdot m)+m)\cdot n=$

na podstawie rozdzielności i:

$=(k^{\prime }\cdot m)\cdot n$

Co dowodzi kroku indukcyjnego i całej identyczności.

Rozwiązanie 4

Dowód 4

Dowód przez indukcję na $k$. Jeśli $k=0$, to, oczywiście, $0\cdot 0=0$ i teza jest spełniona. Załóżmy teraz, że $k\cdot 0=0$, mamy wtedy $k^{\prime }\cdot 0=k\cdot 0+0=0+0=0$ na podstawie założenia indukcyjnego i identyczności dotyczących dodawania.

Rozwiązanie 5

Dowód 5

Implikacja z prawej strony w lewą wynika z poprzedniego punktu i z definicji mnożenia. Dowodzimy implikacji w prawą stronę. Załóżmy, że $k\cdot m=0$. Jeśli $k=0$, to implikacja jest prawdziwa. Jeśli $k\ne 0$, to, na podstawie Faktu 4.2. (patrz fakt 4.2.), mamy: $k=p^{\prime }$, dla pewnego $p$. Wtedy $k\cdot m=p^{\prime }\cdot m=p\cdot m+m=0$. Na podstawie Faktu 7.1. (patrz fakt 7.1.) otrzymujemy $m=0$, co dowodzi implikacji w prawą stronę.

Rozwiązanie 6

Dowód 6

Aby dowieść przemienności mnożenia, stosujemy indukcję względem $k$. Jeśli $k=0$, to $0\cdot m=0=m\cdot 0$ (dla dowolnego $m$) na podstawie poprzedniego punktu. Załóżmy teraz, że teza jest prawdą dla $k$ i dla dowolnych $m$. Wtedy dla dowolnego $m$ mamy:

$k^{\prime }\cdot m=k\cdot m+m=m\cdot k+m=$

na podstawie założenia indukcyjnego. Dalej używamy rozdzielności i poprzednich punktów:

$m\cdot k+m\cdot 1=m\cdot (k+1)=m\cdot k^{\prime }$,

co należało wykazać. Krok indukcyjny jest dowiedziony, a co za tym idzie również cała identyczność.

Rozwiązanie 7

Dowód 7

Dowód jest indukcją ze względu na $k$. Jeśli $k=0$, to $0\cdot n=m\cdot n$ implikuje, że $m\cdot n=0$. Ponieważ wiemy, że $n\ne 0$, to, używając poprzednich ćwiczeń, otrzymujemy: $m=0$, co dowodzi podstawy indukcji. Załóżmy teraz, że dowodzony fakt jest prawdą dla $k$ (dla dowolnych $m$ i $n\ne 0$). Ustalmy dowolne $m$ i $n\ne 0$ i załóżmy, że:

$k^{\prime }\cdot n=m\cdot n$

Liczba $m$ nie może być równa zero, ponieważ $k^{\prime }\ne 0$ i $n\ne 0$ i, co za tym idzie, $k^{\prime }\cdot n\ne 0$. W związku z tym $m=p^{\prime }$, na podstawie Faktu 4.2. (patrz fakt 4.2.). W związku z tym, przekształcając powyższe równanie, dostajemy:

$k\cdot n+n=p\cdot n+n$

Używając, wcześniej wykazanej, skracalności dla dodawania liczb naturalnych otrzymujemy:

$k\cdot n=p\cdot n$,

co, na mocy założenia indukcyjnego, implikuje $k=p$, a więc $k^{\prime }=p^{\prime }=m$, co należało wykazać.

Ćwiczenie 7.4

Wykaż, że dla dowolnych liczb naturalnych $k$ i $n$.

1. jeśli $n>1$ i $k\ne 0$, to $k\cdot n>k$,

2. jeśli $n\ne 0$, to $k\cdot n\ge k$.

Rozwiązanie 1

Jeśli $n>1$, to $n=p^{\prime }$, dla pewnego $p\ne 0$, wtedy $k\cdot n=n\cdot k=p^{\prime }\cdot k=p\cdot k+k$, gdzie $p\ne 0$ i $k\ne 0$. Na podstawie wcześniejszych ćwiczeń dostajemy $p\cdot k\ne 0$ i w związku z tym $p\cdot k+k>k$. Otrzymaliśmy $k\cdot n>k$.

Rozwiązanie 2

Jeśli $k=0$, to $k\cdot n=0\cdot n=0\ge 0=k$. Jeśli $k\ne 0$, to jedynym przypadkiem, w którym nie możemy zastosować poprzedniego twierdzenia jest $n=1$. Jeśli $n=1$, to, na podstawie Faktu 7.3. (patrz fakt 7.3.) mamy, $k\cdot 1=k$, czyli teza jest prawdą również w tym przypadku.