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 }\stackrel{\text{<mrow data-mjx-texclass="ORD">def</mrow>}}{\equiv }n\cup n$.

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 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}}$ oraz

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

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

Parę 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{<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 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ład4 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 Uzupelnic tw:zinnnat| i definicji

$<$.

Ćwiczenie 5.2

{{{3}}}

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}}