Test GR4: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
 
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
 
(Nie pokazano 110 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 1: Linia 1:
{tw}{Twierdzenie}[section]
5555555555555555555555555555555555555555 Logika
{lem}[tw]{Lemmat}
{mtw}[tw]{Meta twierdzenie}
{fa}[tw]{Fakt}
{wn}[tw]{Wniosek}
{df}[tw]{Definicja}
{AZbioruPustego}{Aksjomat Zbioru Pustego}
{APary}{Aksjomat Pary}
{ASumy}{Aksjomat Sumy}
{ANieskonczonosci}{Aksjomat Nieskończoności}
{AWyrozniania}{Aksjomat Wyróżniania}
{AZbioruPotegowego}{Aksjomat Zbioru Potęgowego}
{AZastepowania}{Aksjomat Zastępowania}
{ARegularnosci}{Aksjomat Regularności}
{AWyboru}{Aksjomat Wyboru}


{}{0pt} {}{0pt}
{}{0in} {}{-0.5in} {}{6.3in}
{}{9in}


{cwicz}[section]
{obra}[section]
{hint}


==Wstęp==


Liczby naturalne to jedna z najbardziej podstawowych idei matematycznych. Operacje
10101010101010101010101010101010101010101010101010 Logika
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
<math>\emptyset</math>. Każdą następną liczbę naturalną otrzymujemy z poprzedniej w prosty
sposób
 
<center><math>\mbox{jeśli </math>n<math> jest liczbą naturalną, to następną po niej liczbą jest
</math>n'{def}{}n n<math>}.
</math></center>
 
Początkowe liczby naturalne to
 
<center><math>\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}
</math></center>
 
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
<math>\emptyset</math> 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ą
 
<center><math>\exists x\; \left(\emptyset\in x \land (\forall y\; y\in x\implies y\cup\{y\}\in x
)\right).
</math></center>
 
Każdy zbiór <math>x</math> 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 <math>x</math> jest niepustym zbiorem zbiorów induktywnych to <math>\bigcap x</math> jest również
zbiorem induktywnym.
}}
 
{{dowod|[Uzupelnij]||
 
Aby wykazać, że <math>\bigcap x</math> jest zbiorem induktywnym musimy wykazać, że
 
* <math>\emptyset \in \bigcap x</math> oraz, że
 
* <math>\forall y\; y\in \bigcap x \implies y\cup\{y\}\in \bigcap x</math>.
 
Ponieważ każdy z elementów <math>x</math> jest zbiorem induktywnym, to <math>\forall z\; z\in x
\implies \emptyset\in z</math>, czyli zbiór pusty jest w każdym z elementów <math>x</math>. Jeśli
jakiś zbiór jest w każdym elemencie zbioru to jest również w jego przecięciu, czyli
<math>\emptyset \in \bigcap x</math>. Pozostaje wykazać drugi fakt, weźmy dowolny <math>y\in\bigcap
x</math>. Natychmiastową konsekwencją jest, że dla każdego <math>z</math>, elementu <math>x</math>, mamy <math>y\in
z</math>. Skoro każdy element <math>x</math> jest zbiorem induktywnym, to dla każdego <math>z</math> w <math>x</math> mamy
<math>y\cup\{y\}\in z</math> i, z definicji przecięcia, <math>y\cup \{y\}\in\bigcap x</math>. 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.
}}
 
{{dowod|[Uzupelnij]||
 
Na mocy aksjomatu nieskończoności istnieje co najmniej jeden zbiór induktywny --
oznaczmy go przez <math>x</math>. Rozważmy wszystkie podzbiory <math>\mathcal{P}(x)</math> tego zbioru i
wybierzmy z nich, na mocy aksjomatu wyróżniania, zbiory induktywne -- powstały w ten
sposób podzbiór <math>\mathcal{P}(x)</math> nazwijmy <math>y</math>. Zbiór <math>y</math> jest niepusty, ponieważ <math>x\in y</math>
jest zagwarantowane przez fakt, że <math>x\subset x</math> i założenie mówiące, że <math>x</math> jest
zbiorem induktywnym. Wnioskujemy, że zbiór <math>y</math> spełnia założenia
Lematu&nbsp;[[##lem:przeciecieinduktywnych|Uzupelnic lem:przeciecieinduktywnych|]] i w związku z tym <math>\bigcap y</math> jest zbiorem
induktywnym.
 
Postulujemy, że zbiór <math>\bigcap y</math> jest najmniejszym zbiorem induktywnym. Aby to
wykazać pokażemy, że dla dowolnego zbioru induktywnego <math>z</math>, mamy <math>\bigcap y\subset
z</math>.  Ustalmy dowolny zbiór induktywny <math>z</math>, na mocy
Lematu&nbsp;[[##lem:przeciecieinduktywnych|Uzupelnic lem:przeciecieinduktywnych|]], zastosowanego do zbioru <math>\{x,z\}</math>
otrzymujemy, że <math>x\cap z</math> jest zbiorem induktywnym. W związku z tym <math>x\cap z \in y</math> i
dalej  <math>\bigcap y\subset x\cap z \subset z</math>. To dowodzi, że zbiór <math>\bigcap y</math>
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.
}}
 
{{dowod|[Uzupelnij]||
 
Ustalmy dwa dowolne, najmniejsze pod względem inkluzji zbiory induktywne <math>x</math> i <math>y</math>.
Wtedy <math>x\subset y</math> i <math>y\subset x</math> skąd wnioskujemy, że <math>x=y</math> 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 <math>\mathbb{N}</math>. 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
<math>1=0'=\{\emptyset\}</math> ponieważ zawiera <math>0</math> 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 <math>P</math> jeśli <math>P\subset\mathbb{N}</math> oraz
 
* <math>\emptyset\in P</math>
 
* <math>\forall x\; x\in P \implies x'=x\cup\{x\}\in P</math>
 
to <math>P=\mathbb{N}</math>.
}}
 
{{dowod|[Uzupelnij]||
 
Ustalmy dowolny zbiór <math>P</math> spełniający założenia  twierdzenia. Zbiór <math>P</math> jest zbiorem
induktywnym, a więc, na mocy definicji zbioru liczb naturalnych, <math>\mathbb{N}\subset P</math>.
Równocześnie założyliśmy, że <math>P\subset\mathbb{N}</math> i w związku z tym <math>P=\mathbb{N}</math> 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
 
<center><math>\forall x\; x\in\mathbb{N} \implies \forall y\;\left( y\in x  \implies y\in\mathbb{N}\right).
</math></center>
 
}}
 
{{dowod|[Uzupelnij]||
 
Dowiedziemy tego faktu przez indukcję. Oznaczmy przez <math>P</math> zbiór tych wszystkich
elementów <math>\mathbb{N}</math> które spełniają naszą własność.
 
<center><math>P = \{n\in\mathbb{N}\,:\, \forall y\; y\in n\implies y\in\mathbb{N}\}
</math></center>
 
Innymi słowy jest to zbiór liczb naturalnych dla których dowodzony fakt jest prawdą.
Aby móc zastosować Twierdzenie&nbsp;[[##tw:ind|Uzupelnic tw:ind|]] musimy wykazać trzy własności zbioru <math>P</math>.
Niewątpliwie <math>P\subset\mathbb{N}</math>, skoro <math>P</math> jest zbiorem niektórych liczb naturalnych.
Przechodzimy teraz do pierwszego kroku indukcyjnego.
 
* Po pierwsze musimy wykazać, że <math>\emptyset\in P</math>. Aby to sprawdzić musimy
stwierdzić, czy każdy element zbioru <math>\emptyset</math> jest liczbą naturalną. Ponieważ
<math>\emptyset</math> nie posiada żadnych elementów nie trzeba niczego dowodzić.
* Załóżmy
teraz, że <math>n\in P</math>. To oznacza, że każdy element <math>n</math> jest liczbą naturalną. Rozważmy
<math>n'=n\cup \{n\}</math>. Każdy element <math>n</math> jest liczbą naturalną na mocy założenia
indukcyjnego, również jedyny element <math>\{n\}</math> równy <math>n</math> jest liczbą naturalną,
ponieważ <math>n\in P\subset \mathbb{N}</math>. W związku z tym każdy z elementów unii <math>n\cup\{n\}</math>
jest również liczbą naturalną. To implikuje, że <math>n'</math> należy do <math>P</math>.
 
Udowodniliśmy wszystkie przesłanki Twierdzenia&nbsp;[[##tw:ind|Uzupelnic tw:ind|]] i w związku z tym
twierdzenie to gwarantuje, że <math>P=\mathbb{N}</math> 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ą <math>0=\emptyset</math> oraz następniki liczb naturalnych.
Niewątpliwie <math>0</math> nie jest następnikiem żadnej liczby naturalnej, ponieważ następnik
dowolnego zbioru posiada przynajmniej jeden element -- dla <math>n</math> mamy <math>n\in n'</math>.
Poniższy fakt pokazuje własność przeciwną.
 
{{fakt|[Uzupelnij]||
 
Każda liczba naturalna jest albo zbiorem pustym, albo następnikiem liczby naturalnej.
Formalnie
 
<center><math>\forall x\; x\in\mathbb{N} \implies (x = \emptyset \lor \exists y\; (y\in\mathbb{N} \land x=y'))
</math></center>
 
}}
 
{{dowod|[Uzupelnij]||
 
Aby dowieść tego faktu skorzystamy z twierdzenia  o indukcji matematycznej.
Zdefiniujemy zbiór <math>P</math> jako zbiór elementów spełniających nasze założenia:
 
<center><math>P = \{n\in\mathbb{N}\,:\, n=\emptyset \lor \exists m\; (m\in\mathbb{N} \land n=m')\}.
</math></center>
 
Aby skorzystać z twierdzenia o indukcji wykażemy, że
 
* Zbiór pusty jest elementem <math>P</math> -- jest to oczywista konsekwencja definicji <math>P</math>.
 
* Jeśli <math>n\in P</math> to również <math>n'\in P</math>. Aby to wykazać załóżmy, że <math>n\in
P\subset \mathbb{N}</math>. Oczywiście <math>n'</math> jest następnikiem pewnej liczby naturalnej -- <math>n</math>.
 
Na podstawie twierdzenia o indukcji <math>P=\mathbb{N}</math>, czyli fakt jest prawdziwy.
}}
 
Kolejny fakt mówi o zależnościach pomiędzy różnymi liczbami naturalnymi.
 
{{fakt|[Uzupelnij]||
 
Dla dowolnej liczby naturalnej <math>n</math> i dowolnego zbioru <math>y</math>, jeśli <math>y\in n</math> to
<math>y\subset n</math>.
}}
 
{{dowod|[Uzupelnij]||
 
Dowód przeprowadzimy indukcyjnie, czyli w oparciu o Twierdzenie&nbsp;[[##tw:ind|Uzupelnic tw:ind|]].
Zdefiniujmy zbiór <math>P</math> jako zbiór tych wszystkich <math>n</math>, elementów <math>\mathbb{N}</math> które
spełniają nasze założenie -- formalnie
 
<center><math>P=\{n\in\mathbb{N}\,:\, \forall y\; y\in n\implies y\subset n\}.
</math></center>
 
Aby skorzystać z indukcji należy wykazać dwa fakty
 
* Oczywiście <math>0=\emptyset\in P</math>, ponieważ <math>\emptyset\in\mathbb{N}</math> i warunek <math>y \in
\emptyset</math> jest fałszem dla wszystkich <math>y</math>.
* Załóżmy teraz że <math>n\in P</math> i
dowiedźmy, że <math>n'</math> jest również elementem <math>P</math>. W tym celu ustalmy dowolny <math>y</math> taki,
że <math>y\in n' = n\cup\{n\}</math>. Rozważamy dwa przypadki -- albo <math>y\in n</math> albo
<math>y\in\{n\}</math>&nbsp;(równoważnie <math>y=n</math>). Jeśli <math>y\in n</math>, to, na mocy założenia indukcyjnego,
<math>y\subset n</math> a ponieważ <math>n\subset n\cup\{n\}</math> wnioskujemy, że <math>y\subset n'</math> co
należało wykazać. W drugim przypadku <math>y=n</math>, ale, ponieważ <math>n'=n\cup\{n\}</math> otrzymujemy
natychmiast, że <math>y=n\subset n'</math> co należało wykazać.
 
No mocy twierdzenia o indukcji matematycznej <math>P=\mathbb{N}</math>  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 <math>m</math> i <math>n</math> są liczbami naturalnymi, to:
 
# jeżeli <math>m'=n'</math> to <math>m=n</math>,
 
# jeżeli <math>m\subset n</math> i <math>m\neq n</math> to <math>m\in n</math>,
 
# <math>m\subset n</math> lub <math>n\subset m</math> -- czyli wszystkie liczby naturalne są
porównywalne przez inkluzję
# <math>m\in n</math> albo <math>m=n</math> albo <math>m\ni n</math> -- 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:
 
:# Załóżmy, niewprost, że <math>m'=n'</math> i <math>m\neq n</math>. Skoro <math>m'=n'</math> i <math>m\in m'</math>, to <math>m\in
n\cup\{n\}</math>. Skoro <math>m\neq n</math> otrzymujemy <math>m\in n</math> i, na mocy Faktu&nbsp;[[##fa:minmsubn|Uzupelnic fa:minmsubn|]]
<math>m\subset n</math>. Ponieważ mamy dokładną symetrię pomiędzy <math>m</math> i <math>n</math>, rozumując
podobnie otrzymujemy <math>n\subset m</math> co w sumie implikuje <math>m=n</math> -- sprzeczność z
założeniem.
:# Drugiego faktu dowiedziemy przez indukcję ze względu na <math>n</math>.
Oznaczmy przez <math>P</math> zbiór
 
<center><math>P=\{n\in\mathbb{N}\,:\, \forall m\; m\in\mathbb{N}\implies (m\subset n \land m\neq n\implies m
\in n)\}
</math></center>
 
:#* Niewątpliwie <math>\emptyset \in P</math>, ponieważ <math>m\subset \emptyset \land
m\neq\emptyset</math> jest fałszem dla wszystkich <math>m</math>.
:#* Pozostaje wykazać, że jeżeli
<math>n\in P</math> to również <math>n'\in P</math>. W tym celu ustalmy dowolne <math>m\in\mathbb{N}</math> takie, że
<math>m\subset n' \land m\neq n'</math>. Nasze założenie mówi, że <math>m\subset n\cup\{n\}</math>.
Jeśli <math>m\subset n</math>, to albo <math>m=n</math> i pokazaliśmy krok indukcyjny ponieważ <math>m=n\in
n'</math>, albo <math>m\neq n</math> i wtedy, na mocy założenia indukcyjnego, <math>m\in n</math> i co za tym
idzie <math>m\in n'</math> ponieważ <math>n\subset n'</math>. Pozostaje rozważyć przypadek, kiedy
<math>m\not\subset n</math>, czyli kiedy <math>n\in m</math>. Wtedy Fakt&nbsp;[[##fa:minmsubn|Uzupelnic fa:minmsubn|]] gwarantuje, że
<math>n\subset m\subset n\cup\{n\}=n'</math>, ale w tym przypadku, <math>m\neq n'</math> i <math>m\neq n</math> co
daje sprzeczność gwarantując, że przypadek <math>m\not\subset n</math> nigdy nie zajdzie.
 
Korzystając z twierdzenia o indukcji matematycznej wykazaliśmy, że <math>P=\mathbb{N}</math>, czyli,
że wszystkie liczby naturalne mają żądaną własność.
 
:# Kolejnego faktu dowodzimy również przez indukcję. Zdefiniujmy <math>P</math> jako
 
<center><math>P = \{n\in\mathbb{N}\,:\, \forall m\; m\in\mathbb{N} \implies (n\subset m \lor m\subset n)
\}.
</math></center>
 
:#* Bardzo łatwo zauważyć, że <math>0=\emptyset\in P</math>, ponieważ <math>\emptyset \subset m</math>
jest prawdą dla każdego <math>m</math>.
:#* Zakładamy, że <math>n\in P</math> i dowodzimy, że <math>n'</math> jest
również elementem <math>P</math>. W tym celu ustalmy dowolne <math>m\in\mathbb{N}</math>. Na mocy założenia
indukcyjnego <math>n \subset m \lor m\subset n</math>. W tym drugim przypadku wnioskujemy,
że <math>m\subset n\subset n'</math> i pokazaliśmy, że <math>n'\in P</math>. Jeśli <math>n\subset m</math> to
albo <math>n=m</math>&nbsp;(i <math>n'\in P</math> ponieważ dla każdej liczby naturalnej <math>n\subset n'</math>), albo
<math>n\neq m</math> i, na mocy poprzedniego punktu <math>n\in m</math>. Wtedy jednak <math>n\cup\{n\}\subset
m</math> co należało dowieść.
 
Twierdzenie o indukcji gwarantuje, że własność jest prawdziwa dla wszystkich liczb
naturalnych.
 
:# Rozważmy dwie liczby naturalne <math>n</math> i <math>m</math>. Na mocy poprzedniego punktu
<math>n\subset m</math> lub <math>m\subset n</math>. Jeśli <math>n\neq m</math> to w pierwszym przypadku mamy, na
mocy poprzednich ćwiczeń, <math>n\in m</math> a w drugim <math>m\in n</math>. Na mocy aksjomatu
regularności wiemy że żaden zbiór nie jest swoim własnym elementem, więc <math>n=m</math> nie
może być prawdziwe równocześnie z jakimkolwiek innym warunkiem. Pozostaje rozważyć
sytuację kiedy <math>m\in n</math> i <math>n\in m</math>. Na mocy Faktu&nbsp;[[##fa:minmsubn|Uzupelnic fa:minmsubn|]] dostajemy <math>m\in
n\subset m</math> i w końcu <math>m\in m</math> 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 <math>m</math> i <math>n</math> piszemy
 
<center><math>m\leq n \stackrel{\textrm{def}}{\equiv} m\subset n
</math></center>
 
oraz
 
<center><math>m< n \stackrel{\textrm{def}}{\equiv} m\in n.
</math></center>
 
Przy takim zdefiniowaniu relacji Fakt&nbsp;[[##fa:minmsubn|Uzupelnic fa:minmsubn|]] i poprzednie ćwiczenie
natychmiast gwarantują, że dla dowolnych liczb naturalnych <math>m</math> i <math>n</math>
 
* <math>m < n \implies m\leq n</math>,
 
* <math>(m\leq n \land m\neq n) \implies m < n</math>,
 
* <math>m \leq n \lor n\leq m</math>,
 
* <math>m < n \lor m=n \lor n< m</math> -- 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 <math>k,m</math> i <math>n</math> następujące warunki są spełnione
 
# <math>m=n\iff (m\leq n \land n\leq m)</math>,
 
# <math>\lnot (n < n)</math>,
 
# <math>(k\leq m \land m\leq n)\implies k\leq n</math>,
 
# <math>(k < m \land m\leq n)\implies k< n</math>,
 
# <math>(k\leq m \land m< n)\implies k< n</math>,
 
# <math>(k < m \land m < n)\implies k <n</math>.
 
{hint}{0} 
; Rozwiązanie.
: Ustalmy dowolne liczby naturalne <math>k,m</math> i <math>n</math>
 
:# <math>m=n</math> jest równoważne <math>m\subset n</math> i <math>n\subset m</math>, a to z kolei jest
równoważne <math>m\leq n \land n\leq m</math> -- co należało pokazać.
:# Jak wykazaliśmy w
Wykład4 aksjomat regularności gwarantuje, że żaden zbiór nie jest swoim
własnym elementem. Czyli <math>n\notin n</math>, co należało pokazać.
:# Jeśli <math>k\leq m</math> i
<math>m\leq n</math> to <math>k\subset m \subset n</math>, czyli <math>k\subset n</math> i dowód jest
zakończony.
:# Jeśli <math>k<m \land m\leq n</math> to <math>k\in m\subset n</math>, czyli <math>k\in n</math>,
co należało wykazać.
:# Jeśli <math>k\leq m \land m< n</math> to niewątpliwie <math>k\leq n</math>.
Wystarczy wykazać, że <math>k\neq n</math>. Jeśli, dla dowodu niewprost, założymy <math>k=n</math>, to z
punktu pierwszego tego ćwiczenia wynika, że  <math>m= n</math>, co, w połączeniu z założeniami
implikuje <math>n\in n</math> -- sprzeczność.
:# Jeśli <math>k<m \land m<n</math> to <math>k<m\land m\leq n</math>
i na podstawie poprzednich punktów <math>k< n</math>.
 
{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 <math>n</math> to zbiór liczb istotnie mniejszych od <math>n</math>. Formalnie
 
<center><math>\forall n\; n\in\mathbb{N} \implies\left( \forall z\; z\in n \iff (z\in\mathbb{N} \land z<
n)\right).
</math></center>
 
}}
 
{{dowod|[Uzupelnij]||
Dla dowolnego ustalonego <math>n</math> i <math>z</math>
implikacja w lewą stronę jest oczywista&nbsp;(z definicji
<math><</math>). Implikacja w prawą stronę jest natychmiastową
konsekwencją Twierdzenia&nbsp;[[##tw:zinnnat|Uzupelnic tw:zinnnat|]] i definicji
<math><</math>. }}
 
{cwicz}{1}{Ćwiczenie {section}.{cwicz}}  Ile jest funkcji
<math>f:\mathbb{N}\rightarrow\mathbb{N}</math> takich, że <math>\vec{f}(n) = f(n)</math> dla
każdej liczby naturalnej <math>n</math>. {hint}{0}  {hint}{1}
; Wskazówka .
: Rozważ
<math>f(0)</math>.
; Rozwiązanie.
: Niewątpliwie istnieje przynajmniej jedna
taka funkcja <math>f</math> zdefiniowana jako <math>f(n)=n</math> dla
każdego <math>n</math>. Dla każdej liczby <math>n</math>, na podstawie
Wniosku&nbsp;[[##wn:nissmallerset|Uzupelnic wn:nissmallerset|]] mamy
 
<center><math>f(n) = n = \{m\in\mathbb{N}\,:\, m< n\} = \vec{f}(\{m\in\mathbb{N}\,:\, m< n\}) = \vec{f}(n).
</math></center>
 
Tak więc funkcja <math>f</math> spełnia wymagania naszego ćwiczenia. Wykażemy teraz, że dla
każdej funkcji <math>f':\mathbb{N}\rightarrow\mathbb{N}</math> mamy <math>f'(n)=f(n)</math> dla wszystkich <math>n</math>. Zdefiniujmy
zbiór <math>P</math> do którego będziemy stosować twierdzenie o indukcji.
 
<center><math>P = \{n\in\mathbb{N}\,:\, f(n) = f'(n)\}.
</math></center>
 
Wykażemy fakty gwarantujące założenia twierdzenia o indukcji
 
:* Liczna <math>0</math> jest elementem <math>P</math> ponieważ dla dowolnej funkcji mamy
<math>\vec{f}(\emptyset) = \emptyset</math>, a więc <math>f(0)=\vec{f}(\emptyset) = \emptyset =
\vec{f'}(\emptyset) = f'(0)</math>.
:* Załóżmy teraz, że twierdzenie jest prawdziwe dla
<math>n\in\mathbb{N}</math>. Wtedy
 
<center><math>f(n') = \vec{f}(n') = \vec{f}(n\cup\{n\}) = \vec{f}(n)\cup \vec{f}(\{n\})
</math></center>
 
Na podstawie założenia indukcyjnego wiemy, że <math>f(n) = f'(n)</math>, czyli, że
<math>\vec{f}(\{n\})=\vec{f'}(\{n\})</math>. To samo założenie gwarantuje również, że
<math>\vec{f}(n)=\vec{f'}(n)</math>, czyli
 
<center><math>f(n') = \vec{f}(n)\cup \vec{f}(\{n\}) = \vec{f'}(n)\cup \vec{f'}(\{n\}) = f'(n'),
</math></center>
 
co dowodzi kroku indukcyjnego.
 
Na mocy twierdzenia o indukcji <math>P=\mathbb{N}</math> 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 <math>\leq</math>. Pozwala ono dowody przez indukcję zamieniać na
dowody niewprost. Zamiast przeprowadzać dowód indukcyjny dla zbioru <math>P</math> rozważyć
możemy zbiór <math>\mathbb{N}\setminus P</math>. 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.
}}
 
{{dowod|[Uzupelnij]||
 
Faktu tego dowodzimy indukcyjnie. Na początku ustalmy zbiór <math>P</math>
 
<center><math>P=\{n\in\mathbb{N}\,:\, \forall x (x\subset\mathbb{N} \land x\cap n \neq \emptyset)\implies
\bigcap x\in x\}.
</math></center>
 
Zbiór <math>P</math> zawiera takie liczby naturalne, że dla dowolnego zbioru liczb naturalnych
<math>x</math> jeśli <math>x\cap n\neq \emptyset</math>&nbsp;(czyli w zbiór <math>x</math> zawiera liczbę naturalną silnie
mniejszą od <math>n</math>) to zbiór <math>\bigcap x</math> jest elementem <math>x</math>. Wykażmy, indukcyjnie, że
<math>P=\mathbb{N}</math>.
 
* Niewątpliwie <math>0\in P</math>, ponieważ dla dowolnego <math>x</math> fałszem jest
<math>x\cap\emptyset\neq\emptyset</math>.
* Załóżmy, że <math>n\in P</math> i ustalmy zbiór <math>x</math> taki,
że <math>x\subset \mathbb{N} </math> i <math>x\cap n'\neq \emptyset</math>. Ponieważ <math>n'=n\cup\{n\}</math> naturalnie
jest rozważyć dwa przypadki. Jeśli <math>x\cap n\neq \emptyset</math> otrzymujemy <math>\bigcap x\in
x</math> na mocy założenia indukcyjnego. W przeciwnym przypadku <math>x\cap n = \emptyset</math> czyli
<math>x\cap n'=\{n\}</math>. Otrzymujemy wtedy <math>n\in x</math>. Równocześnie, dla każdego <math>z\in x</math> mamy
<math>n\in z</math> lub <math>n=z</math>&nbsp;(na mocy identyczności pokazanych wcześniej) ponieważ <math>z\in n</math> --
trzecia możliwość jest zabroniona na mocy <math>x\cap n = \emptyset</math>. To wykazuje, że dla
każdego <math>z\in\mathbb{N}</math> mamy, na mocy własności liczb naturalnych, <math>n\subset z</math>.
Używając własności przecięcia dostajemy <math>n\subset \bigcap x</math>, a ponieważ <math>n\in x</math>
otrzymujemy <math>\bigcap x\subset n</math> -- to daje <math>\bigcap x = n\in x</math> -- co należało
wykazać.
 
Aby dowieść twierdzenie ustalmy niepusty zbiór <math>x\subset\mathbb{N}</math>. Niewątpliwie
istnieje <math>n\in\mathbb{N}</math> takie, że <math>n\in x</math>. Wtedy <math>n'\cap x\neq\emptyset</math> ponieważ <math>n\in
n'\cap x</math>. Na mocy dowiedzionego chwilę wcześniej faktu  wnioskujemy, że <math>\bigcap
x\in x\subset\mathbb{N}</math>. Czyli, że <math>\bigcap x</math> jest najmniejszą liczbą naturalną
występującą w <math>x</math>.
}}
 
Oczywistym faktem jest, że nie istnieje największa liczba naturalna. Aksjomatyczny
dowód tego faktu przebiega niewprost. Jeśli <math>n</math> jest liczbą naturalną, to <math>n'</math> jest
również liczbą naturalną i <math>n'> n</math>, więc <math>n</math> 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 <math>x</math> jest niepustym zbiorem liczb naturalnych ograniczonym z góry tzn.
 
<center><math>\exists y\; y\in\mathbb{N} \land \forall z\; z\in x \implies z \leq y
</math></center>
 
to <math>x</math> posiada element największy tzn.
 
<center><math>\exists y\; y\in x \land \forall z\; z\in x \implies z\leq y.
</math></center>
 
}}
 
{{dowod|[Uzupelnij]||
 
Faktu tego dowodzimy przez indukcję. Zdefiniujmy zbiór <math>P</math> jako zbiór tych ograniczeń
górnych dla których zachodzi nasza teza
 
<center><math>P = \{n\in\mathbb{N}\,:\, \forall x\; ( x\neq \emptyset \land x\subset n )\implies
\bigcup x \in x\}.
</math></center>
 
Zbiór <math>P</math> jest zdefiniowany jako zbiór tych liczb naturalnych <math>n</math>, że dla każdego
zbioru <math>x</math> składającego się z liczb silnie mniejszych od <math>n</math> zbiór ten posiada
największy element&nbsp;(którym jest <math>\bigcup x</math>).  Przechodzimy do indukcyjnego dowodu
tego faktu.
 
* Niewątpliwie <math>0=\emptyset\in P</math> ponieważ <math>\emptyset</math> nie posiada żadnych
niepustych podzbiorów.
* Załóżmy, że <math>n\in P</math> i ustalmy dowolne, niepuste
<math>x\subset n'</math>. Jeśli <math>n\in x</math> to, ponieważ pozostałe elementy <math>n'</math> są podzbiorami
<math>n</math> otrzymujemy <math>\bigcup x = \bigcup n' = n\in x</math>. Jeśli <math>n\notin x</math>, to <math>x\subset
n</math> i, na mocy założenia indukcyjnego otrzymujemy <math>\bigcup x\in x</math>.
 
Ustalmy teraz dowolny niepusty zbiór liczb naturalnych <math>x</math> ograniczony z góry przez
liczbę naturalną <math>y</math>. Natychmiast otrzymujemy, że <math>x\subset y'</math> i na mocy
dowiedzionej wcześniej własności <math>\bigcup x\in x\subset \mathbb{N}</math>, czyli <math>\bigcup x</math>
jest liczbą naturalną i elementem <math>x</math>. Niewątpliwie <math>\bigcup x</math> jest nadzbiorem
każdego z elementów <math>x</math> co dowodzi, że <math>\bigcup x</math> jest elementem maksymalnym zbioru
<math>x</math>.
}}
 
==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 <math>A</math> i <math>B</math> będą zbiorami, a <math>f: A \rightarrow B</math> i <math> g:B\times \mathbb{N}\times A\rightarrow B</math>
funkcjami. Istnieje unikalna funkcja <math>h:\mathbb{N}\times A\rightarrow B</math> taka, że
 
<center><math>\begin{array} {lcll}
h(0,a) &=& f(a) &\text{dla każdego </math>a A<math>} \\
h(n',a) &=& g(h(n,a),n,a) &\text{dla każdego </math>a A<math> i </math>n{N}<math>}
\end{array}
</math></center>
 
}}
 
{{dowod|[Uzupelnij]||
 
Dowód istnienia funkcji <math>h</math> będzie się opierał na analizie elementów następującego
zbioru:
 
<center><math>H = \{e\,:\, \exists m\; m\in\mathbb{N} \land e:m'\times A \rightarrow B \land
\textrm{([[##eq:forinddef|Uzupelnic eq:forinddef|]])}\}
</math></center>
 
gdzie
 
<center><math>
\begin{array} {lcll}
e(0,a) &=& f(a) &\text{dla każdego </math>a A<math>} \\
e(n',a) &=& g(e(n,a),n,a) &\text{dla każdego </math>a A<math> i </math>n m<math>}.
\end{array}
</math></center>
 
Zbiór <math>H</math> jest to zbiór funkcji, które częściowo rozwiązują nasz problem -- funkcje
ze zbioru <math>H</math> działają dla liczb naturalnych mniejszych niż pewne, ustalone <math>m</math>.
Funkcja <math>h</math>, której istnienia dowodzimy, powinna działać dla wszystkich liczb
naturalnych.
 
W pierwszej części dowiedziemy, że zbiór <math>H</math> jest niepusty i, co więcej, zawiera
przynajmniej jedną funkcję <math>e:m'\times A \rightarrow B</math> dla każdej liczby naturalnej <math>m</math>.
Dowód jest indukcyjny -- zdefiniujmy zbiór <math>P</math> jako zbiór tych liczb dla których
istnieją odpowiednie funkcje w <math>H</math>
 
<center><math>P = \{m\in\mathbb{N}\,:\, \exists e\; e:m'\times A\rightarrow B \land e\in H\}.
</math></center>
 
Dowiedziemy indukcyjnie, że <math>P=\mathbb{N}</math>:
 
* Niewątpliwie <math>0\in P</math> ponieważ funkcja <math>e:\{0\}\times A\rightarrow B</math> zdefiniowana
jako <math>e(0,a)=f(a)</math> jest elementem <math>H</math>.
* Załóżmy, że <math>m\in P</math>. To oznacza, że
istnieje funkcja <math>e:m'\times A\rightarrow B</math> spełniająca ([[##eq:forinddef|Uzupelnic eq:forinddef|]]). Funkcja <math>e'</math>
zdefiniowana jako:
 
<center><math>e'(n,a)=\begincases
e(n,a) & \textrm{ jeśli </math>n m'<math>} \\
g(e(n,a),n,a) & \textrm{ jeśli </math>n<nowiki>=</nowiki>m'<math>}
\endcases
</math></center>
 
przeprowadza <math>m''\times A</math> w <math>B</math> i należy do <math>H</math> gwarantując, że <math>m'\in P</math>.
 
Na podstawie twierdzenia o indukcji istnieje funkcja <math>e:m'\times A\rightarrow B</math> należąca
do <math>H</math> dla każdego <math>m\in\mathbb{N}</math>.
 
Kolejną rzeczą jako wykażemy jest to, że dowolne funkcje <math>e\in H</math> i <math>e'\in H</math> dla
tych samych argumentów zwracają takie same wyniki&nbsp;(oczywiście zakładając że argumenty
należą do przecięcia dziedzin tych funkcji). Nasz dowód przebiega niewprost. Załóżmy
że funkcje <math>e,e'\in H</math> są takie, że istnieje <math>n\in\mathbb{N}</math> i <math>a\in A</math> spełniające
<math>e(n,a)\neq e'(n,a)</math>. Zastosujmy Twierdzenie&nbsp;[[##tw:elmin|Uzupelnic tw:elmin|]] do zbioru tych wszystkich
<math>n</math> dla których istnieje <math>a\in A</math> spełniające <math>e(n,a)\neq e'(n,a)</math>&nbsp;(na mocy naszego
założenia zbiór ten jest niepusty). Otrzymujemy najmniejszą liczbę naturalną <math>n</math>
taką, że <math>e(n,a)\neq e'(n,a)</math>. Liczba <math>n</math> nie może być równa <math>0</math>, bo wtedy <math>e(0,a) =
f(a) = e'(0,a)</math>, więc, na mocy Faktu&nbsp;[[##fa:zeroorsucc|Uzupelnic fa:zeroorsucc|]] <math>n=k'</math> dla pewnego <math>k</math>.
Ponieważ  <math>k< n</math>, więc <math>e(k,a)=e'(k,a)</math> i otrzymujemy sprzeczność dzięki
 
<center><math>e(n,a) = e(k',a)=g(e(k,a),k,a) = g(e'(k,a),k,a) = e'(k',a) = e'(n,a).
</math></center>
 
Dowód twierdzenia kończymy definiując <math>h = \bigcup H</math>. Na mocy wcześniejszego faktu
<math>h</math> jest funkcją, a na mocy faktu, który dowodziliśmy indukcyjnie dziedziną <math>h</math> jest
zbiór liczb naturalnych. Warunki stawiane <math>h</math> są spełnione w sposób oczywisty dzięki
definicji zbioru <math>H</math>.
 
Aby wykazać unikalność funkcji <math>h</math> załóżmy że istnieje funkcja <math>h'\neq h</math> spełniająca
tezę twierdzenia. Wnioskujemy, że istnieje <math>n\in\mathbb{N}</math> i <math>a\in A</math> takie, że
<math>h(n,a)\neq h'(n,a)</math>. Wtedy jednak <math>h'</math> zawężone do <math>n'</math> jest elementem zbioru <math>H</math> co
stoi w sprzeczności z faktem wykazanym o <math>H</math>.
}}
 
==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ą <math>\mathbb{N} \times \mathbb{N} </math> w <math>\mathbb{N}</math>.
Aby wykazać istnienie dodawania korzystamy z twierdzenia  o indukcji kładąc za <math>A</math> i
<math>B</math> zbiór liczb naturalnych <math>\mathbb{N}</math> i definiując <math>f(n)=n</math>, oraz <math>g(m,n,p) = m'</math>. Na
mocy twierdzenia o definiowaniu przez indukcję istnieje funkcja <math>h:\mathbb{N}^2\rightarrow\mathbb{N}</math>
taka, że <math>h(0,m) = m</math> i <math>h(n',m)= h(n,m)'</math>. Funkcja ta to dodawanie liczb naturalnych
i będziemy używać zwyczajnej notacji <math>h(n,m) = n+m</math>. Zgodnie z intuicją, dla dowolnej
liczby naturalnej <math>n</math> mamy <math>n' = n+1</math>.
 
Jedyną udowodnioną w tej chwili własnością funkcji zapisywanej przez <math>+</math> są
wynikające wprost z definicji własności. Wiemy, że
 
<center><math>0+n = n
</math></center>
 
dla każdego liczby naturalnej <math>n</math> oraz, że
 
<center><math>n'+m = (n+m)'
</math></center>
 
dla dowolnych liczb <math>n</math> i <math>m</math>. Poniżej przedstawiamy parę podstawowych faktów
dotyczących dodawania liczb naturalnych.
 
{{fakt|[Uzupelnij]||
 
Jeśli suma dwóch liczb jest równa <math>0</math>, to obie liczby muszą być równe <math>0</math>.
}}
 
{{dowod|[Uzupelnij]||
 
Załóżmy, że dla dwu liczb naturalnych <math>n</math> i <math>m</math> zachodzi <math>n+m=0</math>. Jeśli liczba <math>n</math>
jest następnikiem jakiejś liczby naturalnej to również <math>n+m</math> jest następnikiem
jakiejś liczby i w związku z tym <math>n+m\neq 0</math>. Na podstawie Faktu&nbsp;[[##fa:zeroorsucc|Uzupelnic fa:zeroorsucc|]]
wnioskujemy, że <math>n=0</math>. Wtedy <math>0+m=m</math> i otrzymujemy <math>m=0</math>, co należało wykazać.
}}
 
Kolejny fakt mówi o łączności dodawania liczb naturalnych
 
{{fakt|[Uzupelnij]||
 
Dodawanie liczb naturalnych jest łączne. Formalnie
 
<center><math>\forall k \forall m \forall n\; (k\in\mathbb{N} \land m\in \mathbb{N} \land n\in \mathbb{N})\implies
k+(m+n)=(k+m)+n.
</math></center>
 
}}
 
{{dowod|[Uzupelnij]||
 
Dowód jest indukcją ze względu na <math>k</math>.
 
* Jeśli <math>k=0</math>, to <math>0+(m+n) = m+n</math>, oraz <math>0+m=m</math>  i w związku z tym <math>(0+m)+n =
m+n</math> co należało pokazać.
* Zakładamy, że równość jest prawdziwa dla <math>k</math>&nbsp;(dla
dowolnych <math>m</math> i <math>n</math>). Ustalmy dowolne liczby naturalne <math>m</math> i <math>n</math>, wtedy
 
<center><math>k'+(m+n) = (k+(m+n))' = ((k+m) + n)' = (k+m)' +n = (k'+m) +n
</math></center>
 
gdzie druga równość wynika z założenia indukcyjnego, a wszystkie pozostałe równości z
definicji funkcji <math>+</math>.
 
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 <math>k,m</math> i <math>n</math> udowodnij:
 
# <math>n+0=n</math>,
 
# <math>k'+m=k+m'</math>,
 
# <math>k+m = m+k</math>, czyli dodawanie jest przemienne,
 
# jeśli <math>k+n = m+n</math> to <math>k=m</math>, czyli dodawanie jest skracalne,
 
# jeśli <math>k>m</math> to istnieje <math>n>0</math> takie, że <math>k=m+n</math>.
 
{hint}{0} 
; Rozwiązanie.
: Dowody
 
:# Dowodzimy przez indukcję na <math>n</math>. Niewątpliwie <math>0+0= 0</math>. Jeśli <math>n+0 =n</math>, to
<math>n'+0=(n+0)' = n'</math>, gdzie druga równość wywodzi się z założenia indukcyjnego. Na mocy
twierdzenia  o indukcji <math>n+0= n</math> dla każdej liczby naturalne <math>n</math>.
:# Dowodzimy ten
fakt przez indukcję na <math>k</math>. Niewątpliwie, dla <math>k=0</math> i dla dowolnego <math>m</math> mamy
<math>0'+m=(0+m)'=m'= 0+m'</math>. Pozostaje założyć, że fakt jest prawdą dla <math>k</math> i wykazać go
dla <math>k'</math>. Dla dowolnego <math>m</math>
 
<center><math>k''+m = (k'+m)'=(k+m')=k'+m'
</math></center>
 
co dowodzi kroku indukcyjnego i całego faktu.
 
:# Przemienności dodawania dowodzimy przez indukcję na <math>k</math>. Niewątpliwie, dla
<math>k=0</math> i dla dowolnego <math>m</math> mamy <math>0+m=m=m+0</math>. Załóżmy teraz, że teza jest prawdziwa dla
<math>k</math> i dla dowolnych <math>m</math>. Ustalmy dowolne <math>m</math> i
 
<center><math>k'+m = (k+m)' = (m+k)'= m'+k
</math></center>
 
gdzie druga równość jest konsekwencją założenia indukcyjnego. Korzystając z
poprzedniego ćwiczenia dostajemy <math>m'+k=m+k'</math> co dowodzi, że dla dowolnego <math>m</math> mamy
<math>k'+m=m+k'</math>. Używając twierdzenia o indukcji konkludujemy, że dodawanie w liczbach
naturalnych jest przemienne.
 
:# Tę własność dowodzimy indukcją na <math>n</math>. Jeśli <math>n=0</math>, to <math>k+0=m+0</math> niewątpliwie implikuje, że <math>k=m</math>.
Załóżmy, że własność skracania zachodzi dla <math>n</math>&nbsp;(dla dowolnych <math>k</math> i <math>m</math>), wtedy
 
<center><math>k+n' = n'+k = (n+k)' = (k+n)'
</math></center>
 
i podobne rozumowanie jest prawdziwe dla <math>m+n'</math> dając
 
<center><math>(k+n)' = (m+n)'.
</math></center>
 
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
 
<center><math>k+n = m+n.
</math></center>
 
Co, po zastosowaniu założenia indukcyjnego gwarantuje, że <math>k=m</math>. Twierdzenie o
indukcji powoduje, że dodawanie jest skracalne.
 
:# Dowodzimy tego faktu przez indukcję na <math>k</math>. Jeśli <math>k</math> jest równe <math>0</math> to nie istnieje <math>m<k</math>,
czyli teza jest prawdziwa. Załóżmy teraz, że teza jest prawdziwa dla <math>k</math> i dla wszystkich <math>m<k</math>.
Ustalmy <math>k'</math> i dowolne <math>m<k'</math>. Jeśli <math>m=k</math> to bierzemy <math>n=1</math> i <math>k' = m +1</math> dowodzi kroku indukcyjnego.
Jeśli <math>m<k</math> to, na podstawie założenia indukcyjnego istnieje <math>n</math> takie, że
 
<center><math>k = m+n.
</math></center>
 
Wtedy <math>k' = (m+n)' = m+n'</math> 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 <math>k</math> i <math>n</math>.
 
# jeśli <math>n \neq 0</math> to <math>k+ n > k</math>.
 
# <math>k +  n \geq k</math>,
 
{hint}{0} 
; Rozwiązanie.
: Dowody:
 
:# Pierwszego punktu dowodzimy przez indukcję względem <math>k</math>. Jeśli <math>k=0</math> , to <math>n = 0 + n > 0</math> dla dowolnego
<math>n\neq 0</math>. Dla dowodu kroku indukcyjnego załóżmy, że dla każdego <math>n\neq 0</math> mamy <math>k+n > k</math>.
Ustalmy dowolne <math>n\neq 0</math>, wtedy
<math> k'+n = (k+n)'</math> korzystając z faktu, że <math>k+n> k</math> dostajemy
 
<center><math>k'+n > k'
</math></center>
 
co należało wykazać.
 
:# Aby wykazać nierówność rozpatrujemy przypadki ze względu na <math>n</math>. Jeśli <math>n\neq 0</math> z poprzedniego
podpunktu otrzymujemy, że <math>k+n>k</math>, czyli <math>k+n\geq k</math>. Jeśli <math>n=0</math>, to <math>k+0 = k \geq k</math>, 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 <math>A=B=\mathbb{N}</math> oraz <math>f(n) = 0</math> i <math>g(m,n,p) = m + p</math>.
Twierdzenie o definiowaniu przez indukcję gwarantuje istnienie funkcji <math>h:\mathbb{N}^2\rightarrow
\mathbb{N}</math> takiej, że:
 
<center><math>h(0,m) = 0,
</math></center>
 
oraz
 
<center><math>h(n',m) = h(n,m) + m.
</math></center>
 
Funkcję <math>h</math> definiującą mnożenie oznaczamy w notacji infiksowej symbolem <math>\cdot</math> tak,
że <math>n\cdot m = h(n,m)</math>. 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 <math>k</math> mamy <math>k\cdot 1 = k</math>.
}}
 
{{dowod|[Uzupelnij]||
 
Dowód tego faktu jest indukcją ze względu na <math>k</math>. Jeśli <math>k=0</math> to <math>0\cdot 1 = 0</math>.
Jeśli równość jest prawdą dla <math>k</math>, to <math>k'\cdot 1 = k\cdot 1 + 1</math>, co, na mocy
założenia indukcyjnego jest równe <math>k+1=k'</math>. 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 <math>k,m</math> i <math>n</math> zachodzi
 
# <math>k\cdot (m+n) = k\cdot m +k\cdot n</math> -- dodawanie jest rozdzielne względem mnożenia z prawej strony,
 
# <math>(k+m)\cdot n = k\cdot n + m\cdot n</math> -- dodawanie jest rozdzielne względem mnożenia z lewej strony,
 
# <math>k\cdot(m\cdot n) = (k\cdot m)\cdot n</math> -- mnożenie jest łączne,
 
# <math>k\cdot 0 = 0</math>
 
# <math>k\cdot m = 0</math> wtedy i tylko wtedy, kiedy <math>k=0\lor m=0</math>
 
# <math>k\cdot m = m\cdot k</math> -- mnożenie jest przemienne,
 
# jeśli <math>k\cdot n = m\cdot n</math> i <math>n\neq 0</math> to <math>k=m</math>.
 
{hint}{0} 
; Rozwiązanie.
: Dowody
 
:# Pierwszego faktu dowodzimy przez indukcję na <math>k</math>. Jeżeli <math>k=0</math>, to zarówno <math>0\cdot (m+n)</math> jak i
<math>0\cdot m</math> oraz <math>0\cdot n</math> są równe zero i równość jest prawdziwa. Jeśli równość jest prawdziwa dla
<math>k</math> i dla dowolnych <math>m</math> i <math>n</math>, to dla <math>k'</math>
 
<center><math>k'\cdot(m+n) =k\cdot(m+n) + (m + n) = (k\cdot m +k\cdot n) + (m +n) =
</math></center>
 
na mocy założenia indukcyjnego i dalej
 
<center><math>= (k\cdot m +m) + (k\cdot n +n) =
</math></center>
 
używając przemienności i łączności dodawania. W końcu
 
<center><math>= k'\cdot m + k'\cdot n
</math></center>
 
co należało pokazać dla kroku indukcyjnego. Twierdzenie o indukcji gwarantuje, że
równość jest prawdą dla wszystkich <math>k</math>.
 
:# Przedstawiamy dowód przez indukcję na <math>k</math>. Jeśli <math>k=0</math> to lewa strona równości jest równa
<math>(0+m)\cdot n= m\cdot n</math> a prawa <math>0\cdot n + m\cdot n = 0 +m\cdot n = m\cdot n</math>, czyli równość jest prawdą.
Jeśli równość jest prawdziwa dla <math>k</math>&nbsp;(przy dowolnych <math>m</math> i <math>n</math>) to dla <math>k'</math>&nbsp;(i dowolnych <math>m</math> i <math>n</math>)
 
<center><math>(k'+m)\cdot n = (k+m)'\cdot n = (k+m)\cdot n + n=(k\cdot n + m\cdot n) + n =
</math></center>
 
korzystając z założenia indukcyjnego. Dalej, używając przemienności i łączności
dodawania dostajemy
 
<center><math>=(k\cdot n + n) + m\cdot n = k'\cdot n + m\cdot n
</math></center>
 
co dowodzi kroku indukcyjnego i, co za tym idzie, prawdziwości tezy.
 
:# Dowód przez indukcję na <math>k</math>. Jeśli <math>k=0</math> to <math>0\cdot (m\cdot n) = 0 </math>, również <math>0\cdot m=0</math> i
<math>(0\cdot m)\cdot n=0</math>, co dowodzi podstawy indukcji. Załóżmy teraz że równość jest prawdą dla <math>k</math>
i dla dowolnych <math>m</math> i <math>n</math>. Ustalmy dowolne <math>m</math> i <math>n</math> i
 
<center><math>k'\cdot (m\cdot n) = k\cdot(m\cdot n) + (m\cdot n) = (k\cdot m)\cdot n  + (m\cdot n)=
</math></center>
 
na mocy założenia indukcyjnego. Dalej
 
<center><math>= ((k\cdot m) +m)\cdot n =
</math></center>
 
na podstawie rozdzielności i
 
<center><math>= (k'\cdot m) \cdot n.
</math></center>
 
Co dowodzi kroku indukcyjnego i całej identyczności.
 
:# Dowód przez indukcję na <math>k</math>. Jeśli <math>k=0</math> to, oczywiście, <math>0\cdot 0 = 0</math> i teza
jest spełniona. Załóżmy teraz, że <math>k\cdot 0 = 0</math>, mamy wtedy <math>k'\cdot 0 = k\cdot 0 +
0 = 0 + 0 = 0</math> na podstawie założenia indukcyjnego i identyczności dotyczących
dodawania.
:# Implikacja z prawej strony w lewą wynika z poprzedniego punktu i z
definicji mnożenia. Dowodzimy implikacji w prawą stronę. Załóżmy, że <math>k\cdot m = 0</math>.
Jeśli <math>k=0</math> to implikacja jest prawdziwa. Jeśli <math>k\neq 0</math> to, na podstawie
Faktu&nbsp;[[##fa:zeroorsucc|Uzupelnic fa:zeroorsucc|]] mamy <math>k=p'</math> dla pewnego <math>p</math>. Wtedy <math>k\cdot m = p'\cdot m =
p\cdot m + m = 0</math>. Na podstawie Faktu&nbsp;[[##fa:zeropluszeroiszero|Uzupelnic fa:zeropluszeroiszero|]] otrzymujemy <math>m=0</math>,
co dowodzi implikacji w prawą stronę.
:# Aby dowieść przemienności mnożenia
stosujemy indukcję względem <math>k</math>. Jeśli <math>k=0</math> to <math>0\cdot m= 0 = m\cdot 0</math>&nbsp;(dla
dowolnego <math>m</math>) na podstawie poprzedniego punktu. Załóżmy teraz, że teza jest prawdą
dla <math>k</math> i dla dowolnych <math>m</math>. Wtedy dla dowolnego <math>m</math> mamy
 
<center><math>k'\cdot m = k \cdot m + m = m \cdot k + m =
</math></center>
 
na podstawie założenia indukcyjnego. Dalej używamy rozdzielności i poprzednich
punktów
 
<center><math>m\cdot k + m\cdot 1 = m \cdot (k +1) = m\cdot k'
</math></center>
 
co należało wykazać. Krok indukcyjny jest dowiedziony, a co za tym idzie również cała
identyczność.
 
:# Dowód jest indukcją ze względu na <math>k</math>. Jeśli <math>k=0</math>, to <math>0\cdot n = m\cdot n</math> implikuje,
że <math>m\cdot n =0</math>. Ponieważ wiemy, że <math>n\neq 0</math> to, używając poprzednich ćwiczeń, otrzymujemy <math>m=0</math>
co dowodzi podstawy indukcji. Załóżmy teraz, że dowodzony fakt jest prawdą dla <math>k</math>&nbsp;(dla dowolnych <math>m</math>
i <math>n\neq 0</math>). Ustalmy dowolne <math>m</math> i <math>n\neq 0</math> i załóżmy, że
 
<center><math>k'\cdot n = m \cdot n.
</math></center>
 
Liczba <math>m</math> nie może być równa zero, ponieważ <math>k'\neq 0</math> i <math>n\neq 0</math> i, co za tym
idzie <math>k'\cdot n\neq 0</math>. W związku z tym <math>m=p'</math> na podstawie
Faktu&nbsp;[[##fa:zeroorsucc|Uzupelnic fa:zeroorsucc|]]. W związku z tym, przekształcając powyższe równanie
dostajemy
 
<center><math>k\cdot n + n = p \cdot n+n.
</math></center>
 
Używając, wcześniej wykazanej, skracalności dla dodawania liczb naturalnych
otrzymujemy
 
<center><math>k\cdot n= p \cdot n
</math></center>
 
co, na mocy założenia indukcyjnego, implikuje <math>k=p</math>, a więc <math>k' = p'=m</math> co należało
wykazać.
 
{Koniec ćwiczenia {section}.{cwicz}} 
{cwicz}{1}{Ćwiczenie {section}.{cwicz}} 
Wykaż, że dla dowolnych liczb naturalnych <math>k</math> i <math>n</math>.
 
# jeśli <math>n > 1</math>  i <math>k\neq 0</math> to <math>k\cdot n > k</math>.
 
# jeśli <math>n\neq 0</math> to <math>k\cdot n \geq k</math>,
 
{hint}{0} 
; Rozwiązanie.
: Rozwiązania:
 
:# Jeśli <math>n>1</math>, to <math>n= p'</math> dla pewnego <math>p\neq 0</math> wtedy <math>k\cdot n = n\cdot k =
p'\cdot k = p\cdot k + k</math>, gdzie <math>p\neq 0</math> i <math>k\neq 0</math>. Na podstawie wcześniejszych
ćwiczeń dostajemy <math>p\cdot k\neq 0</math> i w związku z tym <math>p\cdot k + k> k</math>. Otrzymaliśmy
<math>k\cdot n > k</math>.
:# Jeśli <math>k=0</math>, to <math>k\cdot n = 0\cdot n = 0 \geq 0 = k</math>. Jeśli
<math>k\neq 0</math>, to jedynym przypadkiem, w którym nie możemy zastosować poprzedniego
twierdzenia jest <math>n=1</math>. Jeśli <math>n=1</math> to, na podstawie Faktu&nbsp;[[##fa:timesoneissame|Uzupelnic fa:timesoneissame|]]
mamy <math>k\cdot 1 = k</math>, czyli teza jest prawdą również w tym przypadku.
 
{Koniec ćwiczenia {section}.{cwicz}}

Aktualna wersja na dzień 20:09, 29 wrz 2006

5555555555555555555555555555555555555555 Logika



10101010101010101010101010101010101010101010101010 Logika

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_GR4&oldid=60021”