|
|
| (Nie pokazano 109 pośrednich wersji utworzonych przez tego samego użytkownika) |
| Linia 1: |
Linia 1: |
| ==Wstęp==
| | 5555555555555555555555555555555555555555 Logika |
|
| |
|
| 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
| |
| <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
| | 10101010101010101010101010101010101010101010101010 Logika |
| </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 [[##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 [[##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 [[##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 [[##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 [[##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> (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 [[##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 [[##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> (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 [[##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 [[##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 (z definicji
| |
| <math><</math>). Implikacja w prawą stronę jest natychmiastową
| |
| konsekwencją Twierdzenia [[##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 [[##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> (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> (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 (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 (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 [[##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> (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 [[##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 [[##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> (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> (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> (przy dowolnych <math>m</math> i <math>n</math>) to dla <math>k'</math> (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 [[##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 [[##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> (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> (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 [[##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 [[##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}}
| |
