Úvod
Definice.
Pro každou množinu \(x\) definujeme tzv.
následovníka \(x^+\) jako množinu: \(x^+ = x ∪ \{x\}.\)
Definice.
- \(0 = ∅.\)
- \(1 = 0^+ = 0 ∪ \{0\} = \{0\}.\)
- \(2 = 1^+ = 1 ∪ \{1\} = \{0,1\}.\)
- \(3 = 2^+ = 2 ∪ \{2\} = \{0,1,2\}.\)
- \(4 = 3^+ = 3 ∪ \{3\} = \{0,1,2,3\}.\)
Důsledkem uvedených definic dostáváme:
- \(0 ∈ 1 ∈ 2 ∈ 3 ∈ 4 ∈ 5 ∈ ⋯\)
- \(0 ⊆ 1 ⊆ 2 ⊆ 3 ⊆ 4 ⊆ 5 ⊆ ⋯\)
Induktivní množiny
Připomeňme si Axiom nekonečna: Existuje množina \(A\)
taková, že \(∅ ∈ A\) a pro každé \(x ∈ A\) platí \(x^+ ∈ A.\)
Definice.
Množina \(I\) se nazývá
induktivní, pokud jsou splněny
podménky:
- \(∅ ∈ I.\)
- (\(\forall a ∈ I)(a^+ ∈ I\)).
Definice.
Množina \(n\) se nazývá přirozené číslo, pokud pro každou
induktivní množinu \(I\) platí: \(n ∈ I.\)
Poznámky.
-
Množina \(\emptyset\) je přirozeným číslem jak plyne z definice
induktivní množiny.
- Axiom nekonečna zaručuje existenci induktivní množiny.
-
Třída \(\{x: x \text{ náleží do každé induktivní množiny}\}\) je
množina v důsledku axiomu nekonečna.
Definice.
Množina všech přirozených čísel se označuje symbolem \(\omega\).
Poznámka.
Platí tedy \(n \in \omega \iff \forall I(I \text{ je induktivní}
\implies n \in I).\)
Věta.
Množina \(\omega\) je induktivní množinou a je podmnožinou každé
induktivní množiny. Tudíž lze říci, že \(\omega\) je nejmenší
induktivní množinou.
Důkaz.
- Zřejmě \(∅ ∈ \omega.\)
-
Ukažme, že platí: \((\forall a ∈ \omega)(a^+ ∈ \omega).\) Protože
pro každou induktivní množinu \(I\) platí \(\emptyset ∈ I\), plyne
odsud, že \(∅ ∈ \omega.\) Dále předpokládejme, že \(a ∈ \omega.\)
Potom z definice množiny \(\omega\) plyne, že \(a ∈ I\) pro každou
induktivní množinu \(I.\) Z toho vyplývá, že \(a^+ ∈ I\) pro
každou induktivní množinu \(I.\) Proto \(a^+ ∈ \omega.\) Dokázali
jsme tedy, že \(\omega\) je induktivní množinou. Zároveň, je-li
\(I\) induktivní množina a \(a ∈ \omega,\), pak \(a ∈ I.\) Proto
\(\omega ⊆ I.\)
\(\blacksquare\)
Důsledek.
Je-li \(I \subseteq \omega\) induktivní množina, pak \(I = \omega.\)
Věta (Princip matematické indukce).
Nechť \(P(n)\) je logická formule s jedním volným parametrem \(n\).
Pokud \(I = \{n\in \omega: P(n)\}\) a pokud platí:
- \(0 ∈ I.\)
- \((\forall n ∈ I)(n^+ ∈ I)\),
pak \(I = \omega.\)
Důkaz.
Věta plyne zřejmě z předchozího důsledku. \(\blacksquare\)
Věta.
Pro každé přirozené číslo \(n\) platí buď \(n = 0\) nebo existuje
přirozené číslo \(k\) takové, že \(n = k^+.\)
Důkaz.
Položme \(I = \{n ∈ \omega: n = 0 \lor (\exists k ∈ \omega)(n =
k^+)\}.\) Zřejmě \(0 ∈ I.\) Nechť nyní \(n ∈ I.\) Z definice množiny
\(I\) plyne, že \(n = 0\) nebo pro jisté \(k ∈ \omega\) platí \(n =
k^+.\) V prvním případě máme \(n^+ = 0^+ = 1 ∈ I.\) V druhém případě
máme \(n^+ = (k^+)^+\). V tomto případě protože \(k ∈ \omega,\) tak
\(k^+ ∈ \omega\) a tedy \(n^+ = (k^+)^+ ∈ I.\) Z principu matematické
indukce tedy plyne, že \(I = \omega.\) \(\blacksquare\)
Definice.
Množina \(A\) se nazývá tranzitivní, jestliže \[ (\forall a)(a
∈ A \implies a ⊆ A). \] Tj. každý prvek množiny \(A\) je podmnožinou
množiny \(A\).
Tranzitivnost množiny \(A\) lze formulovat také takto: \[ (\forall
x)(\forall y)(x ∈ y ∈ A \implies x ∈ A). \] Nebo jinak musí platit:
\(\bigcup A\subseteq A.\)
Příklad.
- Množina \(A = \emptyset\) je tranzitivní.
- Množina \(A = 1 = \{0\}\) je tranzitivní.
-
Množina \(A = \{1\}\) není tranzitivní, neboť \(1 ∈ A,\) ale \(0 ∉
A.\)
Lemma.
Jsou-li \(A\) a \(B\) množiny, potom platí: \[ \bigcup (A ∪ B) =
(\bigcup A) ∪ (\bigcup B). \]
Důkaz. Proveďte sami.\(\blacksquare\)
Věta.
Je-li \(a\) tranzitivní množina, pak \(\bigcup(a^+) = a.\)
Důkaz.
Předpokládejme, že \(a\) je tranzitivní množina. Potom \begin{align*}
\bigcup(a^+) &= \bigcup(a ∪ \{a\})\\ &= \bigcup a ∪ \bigcup \{a\}\ \ \
\text{(Lemma)}\\ &= \left(\bigcup a\right) ∪ a\ \ \ \text{(protože}
\bigcup \{a\} = a)\\ &= a \ \ \text{ protože je } \bigcup a \subseteq
a. \end{align*}
Věta.
Každé přirozené číslo je tranzitivní množina.
Důkaz.
Důkaz provedeme matematickou indukcí. Nechť \[ I = \{n ∈ \omega: n
\text{ je tranzitivní množina}\}. \] Zřejmě \(0 ∈ I,\) neboť \(0 =
∅\). Nechť nyní \(n ∈ I.\) Potom \(n\) je tranzitivní množina. Ukažme,
že i následovník \(n^+\) je tranzitivní množina. V důsledku předchozí
věty platí \(\bigcup(n^+) = n.\) Jelikož zřejmě \(n ⊆ n^+,\) tak
\(\bigcup(n^+) ⊆ n^+.\) Z toho plyne, že \(n^+\) je tranzitivní
množina. Z principu matematické indukce tedy plyne, že \(I = \omega.\)
\(\blacksquare\)
Cvičení.
Dokažte následující tvrzení: zobrazení \(\sigma: \omega → \omega\)
definované pro každé \(n ∈ \omega\) předpisem \(\sigma(n) = n^+\) je
prostá funkce.
Věta.
Množina všech přirozených čísel \(\omega\) je tranzitivní množina.
Důkaz podrobně dokazovat nebudeme. V podstatě stačí dokázat toto: \[
(\forall n ∈ \omega)(n ⊆ \omega). \] Položme \(I = \{n ∈ \omega: n ⊆
\omega\}.\) Dále postupujme matematickou indukcí. \(\blacksquare\)
Cvičení.
Dokažte, že platí následující tvrzení: \[ (\forall n ∈ \omega)(n \neq
n^+). \]
Princip rekurze
Věta (Princip rekurze).
Nechť \(A\) je množina a nechť \(a ∈ A\). Dále nechť \(f: A → A\) je
funkce. Potom existuje jediná funkce \(h: \omega → A\) taková, že
- \(h(0) = a,\)
-
\((h(n^+) = f(h(n)))\) pro každé \(n ∈ \omega.\)
Důkaz.
Nejdříve řekněme, že relace \(R ⊆ \omega × A\), která splňuje
podmínky:
- \((0,a) ∈ R,\)
- \((n,u) ∈ R \implies (n^+,f(u)) ∈ R.\)
se nazývá
přípustná relace. Dále definujme třídu
\(\mathcal{S}\) všech přípustných relací. Tato třída je zřejmě
množinou a je neprázdná, neboť \(\omega × A\) je přípustná relace.
Nyní položme: \[ h = \bigcap \{R: R ∈ \mathcal{S}\}. \]
Pomocné tvrzení 1.
\(h\) je přípustná relace.
Důkaz.
\(h\) je zřejmě relací mezi množinami \(\omega\) a \(A\). Ukažme, že
tato relace je přípustná, tj. vyhovuje podmínkám:
- \((0,a) ∈ h.\)
- \((n,u) ∈ h \implies (n^+,f(u)) ∈ h.\)
Zřejmě pro každé \(R ∈ \mathcal{S}\) platí: \((0,a) ∈ R.\) Proto
\((0,a) ∈ h.\) Abychom dokázali druhou podmínku, předpokládejme, že
\((n,u) ∈ h.\) Potom protože \(h = \bigcap \{R: R ∈ \mathcal{S}\},\)
tak pro každé \(R ∈ \mathcal{S}\) platí \((n,u) ∈ R.\) Proto
\((n^+,f(u)) ∈ R\) pro každé \(R ∈ \mathcal{S}.\) Z toho vyplývá, že
\((n^+,f(u)) ∈ h.\) \(\blacksquare\)
Pomocné tvrzení 2.
\(h\) je funkce zobrazující \(\omega\) do \(A\).
Důkaz.
Abychom dokázali, že \(h\) je funkce, ukažme, že pro každé \(n ∈
\omega\) existuje právě jedno \(y ∈ A\) takové, že \((n,y) ∈ h.\)
Důkaz provedeme matematickou indukcí. Položme \[ I = \{n ∈ \omega:
\text{existuje právě jedno } u ∈ A \text{ takové, že } (n,u) ∈ h\}.
\] Nyní ukažme, že \(I\) je induktivní množina a tedy \(I =
\omega.\)
(a) Ukažme, že \(0 ∈ I.\) Z definice \(h\) plyne, že \((0,a) ∈ h.\)
Proto zbývá dokázat, že neexistuje \(b \neq a\) takové, že \((0,b) ∈
h.\) Pokud potom položíme \[ R = h \setminus \{(0,b)\}, \] potom je
relace \(R\) přípustná a \(R ∈ \mathcal{S}.\) Odtud plyne, že \[ h
\subseteq R, \] což je spor s tím, že \((0,b) ∈ h.\) Tudíž element
\(a\) je jediný, který pro který platí, že \((0,a) ∈ h.\) Proto \(0
∈ I.\)
(b) Ukažme, že \(n ∈ I \implies n^+ ∈ I.\) Předpokládejme tedy, že
\(n ∈ I.\) To znamená, že existuje právě jedno \(u ∈ A\) takové, že
\((n,u) ∈ h.\) Z toho, že \(h\) je přípustná relace plyne:
\((n^+,f(u)) ∈ h.\) Tedy zbývá dokázat, že pokud \((n^+,b) ∈ h\),
pak \(b = f(u).\) Pokud by existovalo \(b \neq f(u)\) takové, že
\((n^+,b) ∈ h,\), potom položme \[ R = h \setminus \{(n^+,b)\}. \]
\(R\) je přípustná relace a tudíž \(R ∈ \mathcal{S}.\) Skutečně, z
definice \(R\) plyne, že \((0,a) ∈ R\) neboť \(0 \neq n^+.\) Je-li
nyní \(k \in \omega\) a \(v \in A\) libovolné tak, že \((k,v) ∈ R,\)
pak \((k,v) ∈ h.\) Dále z toho, že \(h\) je přípustná relace plyne,
že \((k^+,f(v)) ∈ h.\) Proto \((k^+,f(v)) ∈ R.\) Tudíž \(R ∈
\mathcal{S}\) a \(h ⊆ R,\) což implikuje, že \((n^+,b) ∉ h.\) To je
spor s předpokladem, že \((n^+,b) ∈ h.\) Proto \(b = f(u)\) a tedy
\(n^+ ∈ I.\) Jelikož jsme takto dokázali, že \(I\) je induktivní
množina, tak \(I = \omega.\) Platí tedy pomocné tvrzení 2., tj. \(h:
\omega → A\) je funkce. věty. \(\blacksquare\)
Zbývá dokázat, že \(h\) je jediná funkce, která splňuje podmínky
Pomocné tvrzení 3.
\(h\) je jediná funkce, která splňuje podmínky věty.
Důkaz.
Abychom dokázali, že \(h\) je jediná funkce, která splňuje podmínky
věty, předpokládejme, že \(g: \omega → A\) je funkce, která splňuje
podmínky 1. a 2. věty. Ukažme, že \(h = g.\) Jelikož funkce \(g\)
splňuje podmínky věty, tak to znamená, že je přípustná relace. Tj. \(g
∈ \mathcal{S}.\) Protože \(h = \bigcap \{R: R ∈ \mathcal{S}\},\) tak
\(h ⊆ g.\) Jelikož \(g\) i \(h\) jsou funkce, tak nutně platí \(h =
g.\) (Proč?)\(\blacksquare\)
Takto jsme dokázali tvrzení věty. \(\blacksquare\)
Příklad.
Uvažujme funkci \(f: \mathbb{R} → \mathbb{R}\) definovanou předpisem
\(f(x) = x + d,\) kde \(d ∈ \mathbb{R}\) je pevně zvolené reálné
číslo. Dále nechť \(a ∈ \mathbb{R}\) je též pevně zvolené reálné
číslo. Potom v důsledku principu rekurze existuje jediná funkce \(h:
\omega → \mathbb{R}\) taková, že \begin{align*} h(0) &= a,\\ h(n^+) &=
h(n+1) = f(h(n)) = h(n) + d. \end{align*} Funkce \(h\) se nazývá
aritmetická posloupnost s diferencí \(d\) a počátečním členem
\(a\).
Někdy můžeme potřebovat, aby rekurentně definovaná funkce \(h: \omega →
A\) byla prostá. V takovém případě můžeme použít následující modifikaci
principu rekurze:
Věta (Modifikace principu rekurze).
Nechť \(A\) je množina a nechť \(a ∈ A\). Dále nechť \(f: A → A\) je
prostá funkce taková, že \(a ∉ f(A)\). Potom existuje funkce \(h:
\omega → A\), která splňuje podmínky
- \(h(0) = a,\)
- \(h(n^+) = f(h(n))\) pro každé \(n ∈ \omega,\)
- \(h\) je prostá funkce.
Důkaz.
Nejdříve poznamenejme, že z předpokladů vyplývá podle "Principu
rekurze", že existuje jediná funkce \(h: \omega → A\) taková, že jsou
splňeny podmínky 1. a 2. věty. Zbývá tedy dokázat, že \(h\) je prostá
funkce. Dokažme, že pro všechna \(n ∈ \omega\) a pro všechna \(k ∈
\omega\) platí: \[ h(n) = h(k) \implies n = k. \] Nyní položme: \[ I =
\{n ∈ \omega: (\forall k ∈ \omega)(h(n) = h(k) \implies n = k)\}. \]
(a) Ukažme, že \(0 ∈ I\), tj. \[ (\forall k ∈ \omega)(h(0) = h(k)
\implies 0 = k). \tag{*} \] Nechť tedy \(k ∈ \omega\) je libovolné a
předpokládejme, že \(h(0) = h(k)\). Z vlastnosti 1. plyne, že \(h(0) =
a\). Tedy \(a = h(k)\). Nyní tvrdíme, že \(k = 0\). Pokud by platilo,
že \(k ≠ 0\), pak by existovalo \(j ∈ \omega\) takové, že \(k = j^+\).
Odtud by vyplývalo \(a = h(k) = h(j^+) = f(h(j))\). Tudíž \(a ∈
f(A)\), což je spor s předpokladem věty. Proto \(k = 0\) a tedy
\((*)\) platí. Tedy \(0 ∈ I\).
(b) Předpokládejme, že \(n \in I\). To znamená, že \[ (\forall k ∈
\omega)(h(n) = h(k) \implies n = k). \tag{**} \] Ukažme, že \(n^+ ∈
I\), tj. \[ (\forall k ∈ \omega)(h(n^+) = h(k) \implies n^+ = k).
\tag{***} \] Zvolme libovolné \(k ∈ \omega\) a předpokládejme, že
\(h(n^+) = h(k)\). Z toho, že platí \(n^+ \neq 0\) a z toho, že platí
vlastnost (*) plyne, \(k ≠ 0\). Proto existuje \(j ∈ \omega\) takové,
že \(k = j^+\). To znamená, \(f(h(n)) = h(n^+) = h(k) = h(j^+) =
f(h(j))\). Proto \(h(n) = h(j)\) jak plyne z předpokladu prostoty
funkce \(f\). Podle indukčního předpokladu (**) plyne, že \(n = j\).
Pak ale \(n^+ = j^+ = k\). Tedy \((***)\) platí, tj. \(n^+ ∈ I\).
Takto jsme de facto dokázali, že množina \(I\) je induktivní a podle
principu matematické indukce platí \(I = \omega\). Odtud plyne, že
\(h\) je prostá funkce. \(\blacksquare\)
Peanovy axiomy
Italský matematik
Giuseppe Peano
(1858 - 1932) ve své knize z roku 1889 publikoval systém axiomů
definujících množinu přirozených čísel na jejichž základě je možné
rozvinout teorii přirozených čísel a následně zavést další číselné
obory. Nejdříve předešleme následující definici:
Definice.
Nechť \(N\) je množina, \(S: N → N\) je funkce a nechť \(A ⊆ N\). Nyní
řekneme, že množina \(A\) je uzavřená vzhledem k funkci \(S\),
pokud platí: \[ (\forall n ∈ N)(n ∈ A \implies S(n) ∈ A). \]
Definice uspořádané trojice.
Mějme dány množiny \(x,y,z\). Pak uspořádanou trojicí rozumíme množinu
definovanou takto: \[ (x,y,z) = ((x,y),z). \]
Definice Peanova systému.
Uspořádanou trojicí \((N,S,e)\), kde \(N\) je množina, \(S: N → N\) je
funkce a \(e ∈ N\) je pevně zvolený prvek, nazveme
Peanovým systémem, pokud platí následující axiomy:
- \(e \notin S(N)\).
- \(S\) je prostá funkce.
-
Pro všechna \(A \subseteq N\) jestliže \(e ∈ A\) a \(A\) je
uzavřená vzhledem k funkci \(S\), pak \(N = A.\)
(Třetí axiom se nazývá
axiom indukce.)
Pokud budeme uvažovat funkci \(\sigma: \omega → \omega\) definovanou
předpisem \(\sigma(n) = n^+,\) pak uspořádanou trojicí
\((\omega,\sigma,0)\) je Peanovým systémem. Tento systém je základem pro
konstrukci teorie přirozených čísel.
Věta.
Uspořádaná trojice \((\omega,\sigma,0)\) je Peanovým systémem.
Důkaz.
Protože \(\omega\) je induktivní množina, tak \(0 ∈ \omega.\) A také
pro všechna \(n\in \omega\) platí \(\sigma(n) = n^+ ∈ \omega.\) Dále
pro všechna \(n ∈ \omega\) platí \(n^+ ≠ 0.\) Tudíž \(0 \notin
\sigma(\omega).\) Dále víme (viz cvičení výše), že funkce \(\sigma:
\omega → \omega\) je prostá. Zbývá dokázat, že pro každou množinu \(A
\subseteq \omega\) platí, že pokud \(0 ∈ A\) a \(A\) je uzavřená
vzhledem k funkci \(\sigma\), pak \(A = \omega.\) Důkaz tohoto tvrzení
provedeme pomocí principu matematické indukce. To nám implikuje, že
\(A\) je induktivní podmnožinou množiny \(\omega\) a tedy \(A =
\omega.\) \(\blacksquare\)
Definice.
Předpokládejme, že \((N,S,e)\) a \((N',S',e')\) jsou Peanovy systémy.
Potom řekneme, že \((N,S,e)\) je izomorfní s \((N',S',e')\),
pokud existuje bijekce \(\phi: N → N'\) taková, že
(1) \(\phi(e) = e',\)
(2) \((\forall x ∈ N)(\phi(S(x)) = S'(\phi(x))).\)
Funkci \(f\) nazveme izomorfismem \((N,S,e)\) na
\((N',S',e')\).
Věta.
Je-li trojice \((N,S,e)\) Peanovým systémem, pak je Peanův systém
\((\omega,\sigma,0)\) izomorfní s \((N,S,e)\).
Důkaz.
Nechť \((N,S,e)\) je Peanovým systémem. Pokud nyní budeme aplikovat
tzv. modifikovaný princip rekurze, kde položíme \(A = N\), \(a = e\) a
\(f = S\), tak bude platit, \(f\) je prostá funkce, \(a ∉ f(A)\).
Podle modifikovaného principu rekurze existuje jediná a prostá funkce
\(\phi: \omega → N\) taková, že \begin{align*} \phi(0) &= a = e,\\
\phi(n^+) &= \phi(\sigma(n)) = S(\phi(n)) \text{ pro každé } n ∈
\omega. \end{align*} Zbývá ještě dokázat, že \(\phi\) je surjektivní.
Tedy dokažme, že \(\mathrm{ran}(\phi) = N\). Víme, že \(\phi(0) = e\).
Předpokládejme nyní, že \(x \in \mathrm{ran}(\phi)\). To znamená, že
existuje \(n ∈ \omega\) takové, že \(\phi(n) = x\). Potom \(S(\phi(n))
= S(x)\). Proto \[ S(x) = S(\phi(n)) = \phi(n^+). \] Tudíž \(S(x) \in
\mathrm{ran}(\phi)\). Z toho plyne, že \(\mathrm{ran}(\phi)\) je
uzavřená vzhledem k funkci \(S\). Podle třetího axiomu Peanova systému
tedy platí \(\mathrm{ran}(\phi) = N\). Tedy \(\phi\) je surjektivní a
tedy bijekce. \(\blacksquare\)
Předchozí věta nám říká, že systém Peanových axiomů charakterizuje
množinu přirozených čísel až na izomorfismus. Tedy každý Peanův systém
je izomorfní s Peanovým systémem \((\omega,\sigma,0)\). Tímto způsobem
je možné definovat množinu přirozených čísel. V další části se budeme
zabývat aritmetikou na množině přirozených čísel.
Aritmetika na množině přirozených čísel
V této části se budeme zabývat možností jak zavést aritmetiku na množině
přirozených čísel. To znamená, že budeme chtít definovat binární operaci
sčítání, násobení a další operace na množině přirozených čísel.
Věta (BRP).
Nechť \(g: \omega → \omega\) a nechť \(f: \omega × \omega → \omega\)
jsou dané funkce. Potom existuje jediná funkce \(h: \omega \times
\omega → \omega\) taková, že pro každé \(m\in\omega\) platí:
- \(h(m,0) = g(m),\)
- \(h(m,n^+) = f(h(m,n),m)\) pro každé \(n ∈ \omega.\)
Důkaz.
Důkaz provedeme pomocí principu rekurze. Pokud zvolíme libovolné \(m ∈
\omega\), pak v důsledku principu rekurze existuje jediná funkce
\(p_m: \omega → \omega\) taková, že
\begin{align*}
p_m(0) &= g(m),\\
p_m(n^+) &= f(p_m(n),m),
\end{align*} pro každé \(n ∈ \omega.\)
Konečně definujeme funkci \(h: \omega × \omega → \omega\) předpisem:
\[ h(m,n) = p_m(n)\ \ \text{pro každé } m,n ∈ \omega. \] Funkce \(h\)
je jediná funkce, která splňuje podmínky věty. \(\blacksquare\)
Pokud nyní zvolíme \(g: \omega → \omega\) definovanou předpisem
\(g(m) = m\) a \(f: \omega × \omega → \omega\) definovanou předpisem
\(f(k,m) = k^+\), pak v důsledku předchozí věty existuje jediná funkce
\(A: \omega × \omega → \omega\) taková, že pro každé \(m,n ∈ \omega\)
platí:
\begin{align*}
A(m,0) &= m,\\
A(m,n^+) &= A(m,n)^+.
\end{align*}
Definice operace sčítání.
Nechť \(A:\omega × \omega → \omega\) je jednoznačně určená funkce z
předchozí věty splňující podmínky:
\begin{align*}
A(m,0) &= m, \tag{1}\\
A(m,n^+) &= A(m,n)^+ \text{ pro každé } m,n ∈ \omega. \tag{2}
\end{align*}
Funkci \(A\) nazveme
operací sčítání na množině přirozených čísel. Funkce \(A\) je
binární operace na množině přirozených čísel. Zavedeme označení:
\[
m + n = A(m,n), \text{ pro každé } m,n ∈ \omega.
\]
Jednoduchým důsledkem předchozí definice je následující věta:
Věta.
Pro každé \(m,n ∈ \omega\) platí:
- (A1) \(m + 0 = m,\)
- (A2) \(m + n^+ = (m + n)^+.\)
Důsledek.
Pro každé \(n \in \omega\) platí: \[ n + 1 = n^+. \]
Důkaz.
Pokus si uvědomíme, že pro každé \(m,n ∈ \omega\) platí: \[ m + n =
A(m,n), \] tak vlastnosti (A1) a (A2) jsou jednoduchým důsledkem
vlastností (1) a (2) z definice operace sčítání. \(\blacksquare\)
Následně si dokažne, že předchozí definice symbolu \(m+1\) je konzistentní
s právě zavedenou operací sčítání.
Tvrzení.
Pro každé \(m ∈ \omega\) platí: \[ m + 1 = m^+. \]
Důkaz.
Nechť \(m ∈ \omega\). Protože je \(1 = 0^+\), tak z definice operace
sčítání platí:
\begin{align*}
m + 1 &= m + 0^+\\
&= (m + 0)^+ \text{ (podle vlastnosti (A2))}\\
&= m^+. \text{ (podle vlastnosti (A1))}
\end{align*}
Tudíž, \(m + 1 = m^+.\) \(\blacksquare\)
Cvičení.
Dokažte s využitím definice přirozených čísel \(2\) a \(4\) následující
aritmetickou identitu: \[ 2 + 2 = 4. \]
Nyní máme zavedenu binární operaci sčítání na množině přirozených.
Opětovně použitím Věty (BRP) zavedeme
binární operaci násobení a to tak, že v uvedené větě zvolíme \(g: \omega →
\omega\) definovanou předpisem \(g(m) = 0\) a \(f: \omega × \omega →
\omega\) definovanou předpisem \(f(k,m) = k + m\).
Definice.
Nechť \(M: \omega × \omega → \omega\) je jednoznačně určená funkce splňující
podmínky:
\begin{align*}
M(m,0) &= 0, \tag{3}\\
M(m,n^+) &= M(m,n) + m \tag{4}
\end{align*}
pro každé \(m,n ∈ \omega\). Funkci \(M\) nazveme operací násobení
na množině přirozených čísel. Funkce \(M\) je binární operace na
množině přirozených čísel. Zavedeme označení:
\[
m \cdot n = M(m,n), \text{ pro každé } m,n ∈ \omega.
\]
Opět můžeme formulovat zjevný důsledek předchozí definice:
Věta.
Pro každé \(m,n ∈ \omega\) platí:
- (M1) \(m \cdot 0 = 0,\)
- (M2) \(m \cdot n^+ = m \cdot n + m.\)
Nyní můžeme dokázat některé ze základních vlastností sčítání a násobení,
jako jsou asociativita, komutativita a distributivita.
Věta (Asociativita sčítání).
Pro každé \(m,n,p ∈ \omega\) platí:
\[
(m + n) + p = m + (n + p). \tag{5}
\]
Důkaz.
Fixujme libovolné \(m\) a \(n\) z množiny \(\omega\). Dále položme
\[
I = \{p \in \omega: m + (n + p) = (m + n) + p\}.
\]
Snadno pak s využitím vlastnosti (A1) dostáváme:
\begin{align*}
m + (n + 0) &= m + n \text{ podle vlastnosti (A1),}\\
&= (m + n) + 0. \text{ opět podle vlastnosti (A1) }
\end{align*}
Tedy \(0 \in I\). Nyní předpokládejme, že \(p \in I\). Potom dostáváme:
\begin{align*}
m + (n + p^+) &= m + (n + p)^+\ \ \ \ \ \text{ (A2),}\\
&= (m + (n + p))^+\ \ \ \text{ (A2),}\\
&= ((m + n) + p)^+\ \ \ \text{ podle předpokladu,}\ p \in I,\\
&= (m + n) + p^+.\ \ \ \text{ (A2).}
\end{align*}
Tudíž platí \(m + (n + p^+) = (m + n) + p^+\) a tedy \(p^+ \in I\). Podle
principu matematické indukce tedy platí \(I = \omega\) a tedy platí věta.
\(\blacksquare\)
Nyní postupme dále a dokažme tzv. komutativní zákon pro sčítání.
Lemma (A2l).
Pro každé \(m,n ∈ \omega\) platí:
\[
m^+ + n = (m + n)^+.
\]
Důkaz.
Nechť \(m \in \omega\) je libovolné. Potom dokážeme tvrzení
\[
(\forall n ∈ \omega)(m^+ + n = (m + n)^+).
\]
Položme
\[
I = \{n ∈ \omega: m^+ + n = (m + n)^+\}.
\]
Nyní ukažme, že \(I\) je induktivní množina.
Nejdříve ověřme, že \(0 \in I\). S využitím vlastnosti (A1) dostáváme:
\[
m^+ + 0 = m^+ = (m + 0)^+.
\]
Tudíž \(0 \in I\). Nyní předpokládejme, že \(n \in I\). Potom s vyžitím
vlatsnosti (A2) dostáváme:
\begin{align*}
m^+ + n^+ &= (m^+ + n)^+\ \ \ \ \ \text{ (A2),}\\
&= ((m + n)^+)^+\ \ \ \text{ podle předpokladu,}\ n \in I,\\
&= (m + n^+)^+.\ \ \ \text{ (A2).}
\end{align*}
Tudíž platí \(m^+ + n^+ = (m + n^+)^+\) a tedy \(n^+ \in I\). Podle
principu matematické indukce tedy platí \(I = \omega\) a tedy platí věta.
\(\blacksquare\)
Věta (Komutativita sčítání).
Pro každé \(m,n ∈ \omega\) platí:
\[
m + n = n + m. \tag{6}
\]
Důkaz.
Zvolme libovolné \(n ∈ \omega\). Nyní matematickou indukcí dokážeme, že
pro každé \(m ∈ \omega\) platí:
\[
m + n = n + m.
\]
Za tím účelem položme \(I = \{m ∈ \omega: m + n = n + m\}\). Ukažme, že \(I\)
je induktivní množina. Použitím
Cvičení 1 dostáváme:
\(0 + n = n = n + 0\). Tudíž \(0 \in I\). Nyní předpokládejme, že \(m \in I\).
Nyní budeme chtít dokázat, že \(m^+ \in I\), tj. \(m^+ + n = n + m^+\).
Nyní platí:
\begin{align*}
m^+ + n &= (m + n)^+ \ \ \ \ \text{ Lemma (A2l),}\\
&= (n + m)^+\ \ \ \text{ podle předpokladu,}\ m \in I,\\
&= n + m^+.\ \ \ \text{ (A2).}
\end{align*}
Tudíž \(m^+ \in I\). Podle principu matematické indukce tedy platí \(I =
\omega\). \(\blacksquare\)
Věta (Distributivní zákon).
Pro každé \(m,n,p ∈ \omega\) platí:
\[
m \cdot (n + p) = m \cdot n + m \cdot p. \tag{7}
\]
Důkaz.
Fixujme libovolné \(m\) a \(n\) z množiny \(\omega\). Dále položme
\[
I = \{p \in \omega: m \cdot (n + p) = m \cdot n + m \cdot p\}.
\]
Ověřme, že \(0 \in I\).
\begin{align*}
m \cdot (n + 0) &= m \cdot n\ \ \ \ \ \text{ podle vlastnosti (A1),}\\
&= m \cdot n + 0.\ \ \ \text{ podle vlastnosti (A1)}
&= m \cdot n + m \cdot 0.\ \ \ \text{ podle vlastnosti (M1)}
\end{align*}
Tudíž \(0 \in I\). Nyní předpokládejme, že \(p \in I\). Potom dostáváme:
\begin{align*}
m \cdot (n + p^+) &= m \cdot (n + p)^+\ \ \ \ \ \text{ (A2),}\\
&= m \cdot (n + p) + m\ \ \ \text{ (M2),}\\
&= (m \cdot n + m \cdot p) + m\ \ \ \text{ podle předpokladu,}\ p \in I,\\
&= m \cdot n + (m \cdot p + m)\ \ \ \text{ podle asociativity sčítání,}\\
&= m \cdot n + m \cdot p^+.\ \ \ \text{ (M2).}
\end{align*}
Tudíž platí \(m \cdot (n + p^+) = m \cdot n + m \cdot p^+\) a tedy \(p^+ \in
I\).
Podle principu matematické indukce tedy platí \(I = \omega\) a tedy platí
věta.
\(\blacksquare\)
Věta (Asociativita násobení).
Pro každé \(m,n,p ∈ \omega\) platí:
\[
m\cdot(n\cdot p) = (m\cdot n)\cdot p. \tag{8}
\]
Důkaz.
Fixujme libovolné \(m\) a \(n\) z množiny \(\omega\). Dále položme
\[
I = \{p \in \omega: m \cdot (n \cdot p) = (m \cdot n) \cdot p\}.
\]
Ukažme, že \(I\) je induktivní množina. Ověřme, že \(0 \in I\).
\begin{align*}
m \cdot (n \cdot 0) &= m \cdot 0\ \ \ \ \ \text{ podle vlastnosti (M1),}\\
&= 0\ \ \ \text{ podle vlastnosti (M1),}\\
&= (m\cdot n) \cdot 0.\ \ \ \text{ podle vlastnosti (M1)}
\end{align*}
Tudíž \(m\cdot (n\cdot 0) = (m\cdot n)\cdot 0\). Tudíž \(0 \in I\). Nyní
předpoládejme, že \(p \in I\). Potom dostáváme:
\begin{align*}
m \cdot (n \cdot p^+) &= m \cdot (n \cdot p + n)\ \ \ \ \ \text{ (M2),}\\
&= m \cdot (n \cdot p) + m \cdot n\ \ \ \text{ podle distributivity,}\\
&= (m \cdot n) \cdot p + m \cdot n\ \ \ \text{ podle předpokladu,}\ p \in I,\\
&= (m \cdot n) \cdot p^+.\ \ \ \text{ (M2).}
\end{align*}
Tudíž platí \(m \cdot (n \cdot p^+) = (m \cdot n) \cdot p^+\) a tedy \(p^+ \in
I\). Podle principu matematické indukce tedy platí \(I = \omega\) a tedy platí
věta.
\(\blacksquare\)
Aplikujme nyní Větu (BRP) abychom zavedli
operaci umocňování na množině přirozených čísel. Zvolme \(g: \omega → \omega\)
definovanou předpisem \(g(m) = 1\) a \(f: \omega × \omega → \omega\)
definovanou
předpisem \(f(k,m) = k \cdot m\).
Definice.
Nechť \(E: \omega × \omega → \omega\) je jednoznačně určená funkce splňující
podmínky:
\begin{align*}
E(m,0) &= 1, \tag{9}\\
E(m,n^+) &= E(m,n) \cdot m \tag{10}
\end{align*}
pro každé \(m,n ∈ \omega\). Funkci \(E\) nazveme operací umocňování na
množině přirozených čísel. Funkce \(E\) je binární operace na množině
přirozených čísel. Zavedeme označení:
\[
m^n = E(m,n), \text{ pro každé } m,n ∈ \omega.
\]
Jednoduchým důsledkem předchozí definice je následující věta:
Věta.
Pro každé \(m,n ∈ \omega\) platí:
- (E1) \(m^0 = 1,\)
- (E2) \(m^{n^+} = m^n \cdot m.\)
Cvičení
Cvičení 1.
Dokažte, že pro každé \(n ∈ \omega\) platí: \[ 0 + n = n. \]
Cvičení 2.
Dokažte, že pro násobení platí tzv. komutativní zákon, tj. pro každé
\(m,n ∈ \omega\) platí: \[ m \cdot n = n \cdot m. \]
Cvičení 3.
Nechť \(m,n \in \omega\). Dále nechť \(m + n = 0\). Dokažte, že \(m = n = 0\).
Cvičení 4.
Nechť \(m,n \in \omega\). Dokažte, že je-li \(m \cdot n = 0\), pak
\(m = 0\) nebo \(n = 0\).