Test GR4

Wstęp

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ład 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 John von Neumann jak specyficzny przypadek liczb porządkowych, które będą dokładniej przedstawione w Wykład 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 }defnn$}. </math>

Początkowe liczby naturalne to

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array} {ll} \text{liczba naturalna zero to zbiór }&\emptyset \\ \text{liczba naturalna jeden to zbiór }&\{\emptyset\} \\ \text{liczba naturalna dwa to zbiór }&\{\emptyset,\{\emptyset\}\} \\ \text{liczba naturalna trzy to zbiór }&\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\} \\ \text{i tak dalej\dots}&\text{ } \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 aksjomat nieskończoności. Przytoczymy jego brzmienie zgodnie z Wykład 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 [Uzupelnij]

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

Dowód [Uzupelnij]

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 [Uzupelnij]

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

Dowód [Uzupelnij]

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 Uzupelnic lem:przeciecieinduktywnych| 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 Uzupelnic lem:przeciecieinduktywnych|, 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 [Uzupelnij]

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

Dowód [Uzupelnij]

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.

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 [Uzupelnij]

[o indukcji matematycznej] Dla dowolnego zbioru $P$ jeśli $P\subset \mathbb{\mathbb{N}}$ oraz

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

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

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

Dowód [Uzupelnij]

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 [Uzupelnij]

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 [Uzupelnij]

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 Uzupelnic tw:ind| 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 Uzupelnic tw:ind| 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. Jasne jest, ż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 [Uzupelnij]

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 [Uzupelnij]

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 [Uzupelnij]

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

Dowód [Uzupelnij]

Dowód przeprowadzimy indukcyjnie, czyli w oparciu o Twierdzenie Uzupelnic tw:ind|. 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.

Parę podobnych własności liczb naturalnych podajemy jako ćwiczenie {cwicz}{1}{Ćwiczenie {section}.{cwicz}} Jeśli $m$ i $n$ są liczbami naturalnymi, to:

1. jeżeli $m^{\prime }=n^{\prime }$ to $m=n$,

1. jeżeli $m\subset n$ i $m\ne n$ to $m\in n$,

1. $m\subset n$ lub $n\subset m$ -- czyli wszystkie liczby naturalne są

porównywalne przez inkluzję

1. $m\in n$ albo $m=n$ albo $m\ni n$ -- czyli dla

dowolnych dwóch różnych liczb naturalnych, jedna jest elementem drugiej.

{hint}{0}

Rozwiązanie.

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

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 Uzupelnic fa:minmsubn|

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

1. 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)\}$

1. • 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 Uzupelnic fa:minmsubn| 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ść.

1. 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)\}.$

1. • Bardzo łatwo zauważyć, że $0=\mathrm{\varnothing }\in P$, ponieważ $\mathrm{\varnothing }\subset m$

jest prawdą dla każdego $m$.

1. • 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.

1. 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 Uzupelnic fa:minmsubn| 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.

{Koniec ćwiczenia {section}.{cwicz}}

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{<mrow data-mjx-texclass="ORD">def</mrow>}}{\equiv }m\subset n$

oraz

$m<n\stackrel{\text{<mrow data-mjx-texclass="ORD">def</mrow>}}{\equiv }m\in n.$

Przy takim zdefiniowaniu relacji Fakt Uzupelnic fa:minmsubn| 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: {cwicz}{1}{Ćwiczenie {section}.{cwicz}} 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)$,

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

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

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

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

1. $(k<m\wedge m<n)⟹k<n$.

{hint}{0}

Rozwiązanie.

Ustalmy dowolne liczby naturalne $k,m$ i $n$

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

1. Jak wykazaliśmy w

Wykład4 aksjomat regularności gwarantuje, że żaden zbiór nie jest swoim własnym elementem. Czyli $n\notin n$, co należało pokazać.

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

1. Jeśli $k<m\wedge m\le n$ to $k\in m\subset n$, czyli $k\in n$,

co należało wykazać.

1. 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ść.

1. Jeśli $k<m\wedge m<n$ to $k<m\wedge m\le n$

i na podstawie poprzednich punktów $k<n$.

{Koniec ćwiczenia {section}.{cwicz}} 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 [Uzupelnij]

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 [Uzupelnij]

Dla dowolnego ustalonego $n$ i $z$ implikacja w lewą stronę jest oczywista (z definicji $<$). Implikacja w prawą stronę jest natychmiastową konsekwencją Twierdzenia Uzupelnic tw:zinnnat| i definicji

$<$.

{cwicz}{1}{Ćwiczenie {section}.{cwicz}} Ile jest funkcji $f:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$ takich, że $\overrightarrow{f}(n)=f(n)$ dla każdej liczby naturalnej $n$. {hint}{0} {hint}{1}

Wskazówka .

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 Uzupelnic wn:nissmallerset| 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. {Koniec ćwiczenia {section}.{cwicz}}

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 [Uzupelnij]

[{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 [Uzupelnij]

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 [Uzupelnij]

[{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 [Uzupelnij]

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 [Uzupelnij]

[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

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array} {lcll} h(0,a) &=& f(a) &\text{dla każdego } a AParser nie mógł rozpoznać (błąd składni): {\displaystyle } \\ h(n',a) &=& g(h(n,a),n,a) &\text{dla każdego } a A$i$n{N}Parser nie mógł rozpoznać (błąd składni): {\displaystyle } \end{array} }

Dowód [Uzupelnij]

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle H = \{e\,:\, \exists m\; m\in\mathbb{N} \land e:m'\times A \rightarrow B \land \textrm{([[##eq:forinddef|Uzupelnic eq:forinddef|]])}\} }

gdzie

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array} {lcll} e(0,a) &=& f(a) &\text{dla każdego } a AParser nie mógł rozpoznać (błąd składni): {\displaystyle } \\ e(n',a) &=& g(e(n,a),n,a) &\text{dla każdego } a A$i$n mParser nie mógł rozpoznać (błąd składni): {\displaystyle }. \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 (Uzupelnic eq:forinddef|). Funkcja $e^{\prime }$ zdefiniowana jako:

Parser nie mógł rozpoznać (nieznana funkcja „\begincases”): {\displaystyle e'(n,a)=\begincases e(n,a) & \textrm{ jeśli } n m'Parser nie mógł rozpoznać (błąd składni): {\displaystyle } \\ g(e(n,a),n,a) & \textrm{ jeśli } n=m'Parser nie mógł rozpoznać (nieznana funkcja „\endcases”): {\displaystyle } \endcases }

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 Uzupelnic tw:elmin| 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 Uzupelnic fa:zeroorsucc| $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 [Uzupelnij]

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

Dowód [Uzupelnij]

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 Uzupelnic fa:zeroorsucc| 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 [Uzupelnij]

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 [Uzupelnij]

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. {cwicz}{1}{Ćwiczenie {section}.{cwicz}} Dla dowolnych liczb naturalnych $k,m$ i $n$ udowodnij:

1. $n+0=n$,

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

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

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

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

{hint}{0}

Rozwiązanie.

Dowody

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

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

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

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

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

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

{Koniec ćwiczenia {section}.{cwicz}} {cwicz}{1}{Ćwiczenie {section}.{cwicz}} Wykaż, że dla dowolnych liczb naturalnych $k$ i $n$.

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

1. $k+n\ge k$,

{hint}{0}

Rozwiązanie.

Dowody:

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

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

{Koniec ćwiczenia {section}.{cwicz}}

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 [Uzupelnij]

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

Dowód [Uzupelnij]

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ń. {cwicz}{1}{Ćwiczenie {section}.{cwicz}} 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,

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

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

1. $k\cdot 0=0$

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

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

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

{hint}{0}

Rozwiązanie.

Dowody

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

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

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

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

1. 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 Uzupelnic fa:zeroorsucc| mamy $k=p^{\prime }$ dla pewnego $p$. Wtedy $k\cdot m=p^{\prime }\cdot m=p\cdot m+m=0$. Na podstawie Faktu Uzupelnic fa:zeropluszeroiszero| otrzymujemy $m=0$, co dowodzi implikacji w prawą stronę.

1. 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ść.

1. 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 Uzupelnic fa:zeroorsucc|. 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ć.

{Koniec ćwiczenia {section}.{cwicz}} {cwicz}{1}{Ćwiczenie {section}.{cwicz}} Wykaż, że dla dowolnych liczb naturalnych $k$ i $n$.

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

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

{hint}{0}

Rozwiązanie.

Rozwiązania:

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

1. 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 Uzupelnic fa:timesoneissame| mamy $k\cdot 1=k$, czyli teza jest prawdą również w tym przypadku.

{Koniec ćwiczenia {section}.{cwicz}}