Co si přečíst před tímto článkem – článek o Peanových axiomech, článek o indukci a článek o relacích.
Na přirozených číslech platí několik věcí, na které jsme zvyklí. Např. že \(5+7 = 7+5\), \(3+(4+7) = (3+4)+7\) atd. Ale žádnou z těchto vlastností nemáme v Peanových axiomech – popisují snad Peanovy axiomy jiná přirozená čísla, než na jaká jsme zvyklí? Ne, všechny tyto vlastnosti můžeme odvodit z Peanových axiomů.
0+a = a (V1)
Z definice sčítání máme, že \(a+0 = a\). Nyní bychom chtěli ukázat, že \(0+a = a\). Udělejme to indukcí (to můžeme díky existenci pátého axiomu).
Dokažme to pro první prvek, tedy pro \(a=0\).
$$ 0+0 = 0,$$
což platí z definice sčítání, neboť podle této definice pro všechna \(a \in \mathbb{N}\) máme, že \(a+0 = 0\).
Nyní se pokusíme dokázat, že platí-li to pro nějaký \(k\)-tý prvek, pak to platí i pro \(succ(k)\)-tý prvek (v principu bychom mohli psát i pro \(k+1\)-tý, neboť jsme dokázali, že \(succ(k) = k+1\)) – jinými slovy pokusíme se najít rovnost \(0+succ(a) = succ(a)\) a máme k tomu indukční předpoklad, totiž, že \(0+a = a\).
\( 0+succ(a) = succ(0+a) \) z definice sčítání a symetrie ekvivalence,
\(succ(0+a) = succ(a) \) z indukčního předpokladu.
Dostáváme tedy, že \(0+succ(a) = succ(a)\), čímž je důkaz hotov.
WAIT A MINUTE! Takhle ale axiom o indukci nezněl, zněl \(P5: \) Pokud existuje množina \(X \subseteq \mathbb {N}\) taková, že \(0 \in X \land n \in X \Rightarrow succ(n) \in X\), tak \(X = \mathbb {N} \).
Správně bychom tedy měli na začátku našeho důkazu psát, nechť existuje \(A = \{n \in \mathbb N: 0+a = a\}\) a pak ukážeme, že do \(A\) patří všechna přirozená čísla, tedy \(A = \mathbb N\) – což uděláme přesně tak, jak jsme udělali v našem důkazu. Tento krok se sestrojením nějaké množiny \(A\) na začátku důkazu indukcí budeme přeskakovat.
Sčítání je asociativní (V2)
To znamená, že nezáleží na pořadí, v kterém budu sčítat tři prvky neboli
$$ \forall a,b,c \in \mathbb{N}: (a+b)+c = a+(b+c). $$
Stejně jako (téměř) vše v tomto článku, i toto dokážeme indukcí. V prvním kroce to dokážeme pro \(c=0\).
\( a+b = (a+b)+0 \) z definice sčítání,
\( b+0 = b \Rightarrow a+b=a+(b+0) \) z definice sčítání,
\( (a+b)+0 = a+b = a+(b+0) \) ze symetrie a tranzitivity ekvivalence.
Nyní provedeme indukci na \(c\). Hledáme tedy následující rovnost \( (a+b)+succ(c) = a+(b+succ(c)) \) a pomůže nám k tomu indukční předpoklad, tedy \( (a+b)+c = a+(b+c) \).
\( (a+b)+succ(c) = succ( (a+b)+c) \) z definice sčítání,
\( succ( (a+b)+c) = succ(a+(b+c)) \) z indukčního předpokladu,
\( succ(a+(b+c) )= a+succ(b+c) \) z definice sčítání,
\( a+succ(b+c) = a+(b+succ(c)) \) z definice sčítání.
Máme tedy \( (a+b)+succ(c) = a+(b+succ(c)) \), čímž je důkaz hotov.
Sčítání je komutativní (V3)
To znamená, že
$$ \forall a,b \in \mathbb{N}: a+b = b+a. $$
Když chceme ukázat, že toto platí, můžeme použít jen Peanovy axiomy, operace na nich definované a tvrzení, která jsme již dokázali.
Komutativitu dokážeme opět indukcí. Jako první ukážeme, že dané tvrzení platí pro \(b=0\).
\( a+0 = 0+a \) podle V1.
a+1 = 1+a (V3.2)
Nyní ukážeme, že obecně platí \(a+1 = 1+a\). A ukážeme to indukcí – takže v důkazu indukcí máme další indukci! Jako první krok je ukázat, že \(0+1 = 1+0\), ale to již víme, že platí podle V1.
Nyní musíme ukázat, že platí-li to pro nějaký \(a\)-tý prvek, platí to i pro \(succ(a) \)-tý, jinými slovy, chceme dojít k následující rovnosti \(succ(a)+1 = 1+succ(a)\).
\( succ(a)+1 = succ(a)+succ(0) \) z definice succ,
\( succ(a)+succ(0) = succ(succ(a)+0) \) z definice sčítání,
\( succ(succ(a)+0) = succ(succ(a)) \) z definice sčítání,
\( succ(succ(a)) = succ(a+1) \) podle V0,
\( succ(a+1) = succ(1+a) \) z indukčního předpokladu,
\( succ(1+a) = 1+succ(a) \) z definice sčítání.
Dostáváme tedy, že \(succ(a)+1 = 1+succ(a) \), čímž je (pod)důkaz hotov, nyní víme, že ať přičítáme jedničku zleva či zprava, výsledek bude stejný. My bychom to ale chtěli dokázat i pro dvojku, trojku, …
Ukážeme konečně, že \(a+b = b+a\), kterou máme ukázanou již pro \(b=0\) a \(b=1\). Chceme tedy nalézt tuto rovnost \(a+succ(b) = succ(b)+a\) a použijeme indukční předpoklad, tedy \(a+b = b+a\) .
\( a+succ(b) = a+(b+1) \) podle V0,
\( a+(b+1) = (a+b)+1 \) podle V2,
\( (a+b)+1 = (b+a)+1 \) z indukčního předpokladu,
\( (b+a)+1 = b+(a+1) \) podle V2,
\( b+(a+1) = b+(1+a) \) podle V3.2,
\( b+ (1+a) = (b+1)+a \) podle V2,
\( (b+1)+a = succ(b)+a \) podle V0.
Dostali jsme tedy, že \(a+succ(b) = succ(b)+a\), čímž je důkaz hotov.
Distributivita (V4)
Zkombinujme sčítání a násobení. Ukážeme, že
$$ \forall x,y,z \in \mathbb{N}, (x+y) \cdot z = x \cdot z+y \cdot z. $$
Této vlastnosti říkáme distributivita. Důkaz opět provedeme indukcí, tentokrát na \(z\). První dokážeme, že to platí pro \(z = 0\).
\( (x+y) \cdot 0 = 0 \) z definice násobení,
\( 0 = 0+0 \) z definice sčítání,
\( 0+0 = x \cdot 0+y \cdot 0\) z definice násobení.
V druhém kroku indukce odvodíme tuto rovnost \( (x+y) \cdot succ(z) = x \cdot succ(z)+y \cdot succ(z) \).
\( (x+y) \cdot succ(z) = x+y+(x+y) \cdot z \) z definice násobení,
\( x+y+(x+y) \cdot z = x+y+x \cdot z+y \cdot z \) z indukčního předpokladu,
\( x+y+x \cdot z+y \cdot z = (x+x \cdot z)+(y+y \cdot z)\) podle V2 a V3,
\( (x+x \cdot z)+(y+y \cdot z) = x \cdot succ(z)+y \cdot succ(z) \) z definice násobení.
Čímž je důkaz hotov.
0 \cdot a = 0 (v5)
Že \(a \cdot 0 = 0\) plyne z definice násobení. Zde opět provedeme důkaz indukcí, teď už ale rychleji.
a = 0
\( 0 \cdot 0 = 0\) z definice násobení.
\( \underline {k \Rightarrow k+1} \)
\(0 \cdot succ(k) = 0 \cdot (k+1) \) podle V0,
\(0 \cdot (k+1) = 0 \cdot k+0 \cdot 1 \) podle V4,
\(0 \cdot k+0 \cdot 1 = 0 \cdot k+0\) podle V0.1,
\(0 \cdot k+0 = 0 \cdot k\) z definice sčítání,
\(0 \cdot k = 0\) podle indukčního předpokladu.
Máme tedy, že \(0 \cdot succ(k) = 0\), čímž je důkaz hotov.
Násobení je komutativní (V6)
To znamená, že:
$$ \forall a,b \in \mathbb{N}, a \cdot b = b \cdot a. $$
Opět uděláme důkaz indukcí.
b = 0
\(a \cdot 0 = 0\) z definice násobení,
\( 0 \cdot a = 0\) podle V5,
\(a \cdot 0 = 0 = 0 \cdot a \) z tranzitivity ekvivalence.
\( \underline {b \Rightarrow b+1} \)
\(a \cdot succ(b) = a+a \cdot b \) z definice násobení,
\(a+a \cdot b = a+b \cdot a\) podle indukční hypotézy,
\(a+b \cdot a = b \cdot a+a\) podle V3,
\(b \cdot a+a = (b+1) \cdot a \) podle V4,
\( (b+1) \cdot a = succ(b) \cdot a\) podle V0.
Dostali jsme \(a \cdot succ(b) = succ(b) \cdot a \), čímž je důkaz hotov.
Násobení je asociativní (v7)
To znamená, že:
$$ \forall a,b,c \in \mathbb{N}: (a \cdot b) \cdot c = a \cdot (b \cdot c). $$
Provedeme důkaz indukcí.
c = 0
\( (a \cdot b) \cdot 0 = 0 \) z definice násobení,
\(0 = a \cdot 0 \) z definice násobení,
\(a \cdot 0 = a \cdot (b \cdot 0) \) z definice násobení.
\( \underline {c \Rightarrow c+1} \)
\( (x \cdot y) \cdot succ(c) = x \cdot y+(x \cdot y) \cdot c \) z definice násobení,
\( x \cdot y+(x \cdot y) \cdot c = x \cdot y+x \cdot (y \cdot c) \) podle indukční hypotézy,
\( x \cdot y+x \cdot (y \cdot c) = x \cdot (y+(y \cdot c)) \) podle V4,
\( x \cdot (y+(y \cdot c)) = x \cdot (y \cdot succ(c)) \) z definice násobení.
Máme tedy, že \( (x \cdot y) \cdot succ(c) = x \cdot (y \cdot succ(c)) \), čímž je důkaz hotov.
„Zkrácení“ na sčítání (V8)
Kdybychom měli rovnici typu
$$ a+c = b+c, $$
bylo by lákavé říct, že z toho jasně plyne, že \(a=b\). A ono to z toho opravdu plyne, jen to musíme dokázat. Budeme dokazovat toto tvrzení:
$$ \forall a,b,c \in \mathbb {N}: a+c = b+c \Rightarrow a = b. $$
c = 0
\(a+0 = b+0 \Rightarrow a = b \) z definice sčítání,
\( \underline {c \Rightarrow c+1} \)
\(a+succ(c) = b+succ(c) \)
\(succ(a+c) = succ(b+c) \) z definice sčítání,
\(a+c = b+c\) podle Peanova čtvrtého axiomu,
\(a = b\) podle indukčního předpokladu,
čímž je důkaz hotov.
Všimněme si, že tato věta funguje i naopak:
$$ \forall a,b,c \in \mathbb{N}, a = b \Rightarrow a+c=b+c \ (V8.2), $$
neboť určitě platí, že \(a+c = a+c\), kde můžu na pravou stranu dosadit za \(a\) a dostáváme, že \(a+c=b+c\).
Menší než
Než se posuneme dále, definujme si další relaci na přirozených číslech a to následujícím způsobem: Řekneme, že \(a\) je menší než \(b\), pokud existuje \(p \in \mathbb {N}\), které je různé od \(0\) a platí, že \(a+p=b\).
Toto celé píšeme zkráceně takto:
$$ a < b. $$
Trichotomie (V9)
Tato vlastnost nám říká, že ať máme dva libovolné prvky v přirozených číslech, pak vždy platí právě jedna z následujících možností:
$$ 1. \ a = b , $$
$$2. \ b < a ,$$
$$ 3. \ a < b, $$
kde (např.) \(b<a \) můžeme zapsat také jako \(a>b\).
Dokažme to opět indukcí, ale tentokrát se nám náš důkaz rozpadne na hodně podpřípadů.
Přepišme si ještě větu, kterou chceme dokázat, podle definice relace \(<\).
\( \forall a,b \in \mathbb{N}\) platí právě jedna z následujících možností:
$$ 1. \ a = b ,$$
$$ 2. \ \exists n \in \mathbb{N_{>0}} : b+n = a, $$
$$ 3. \ \exists n \in \mathbb{N_{>0}} : a+n = b, $$
kde symbolem \(\mathbb{N_{>0}}\) myslíme všechna přirozená čísla větší než \(0\). První dokažme toto tvrzení pro \(a = 0\) jako základ pro naší indukci. Jinými slovy musíme ukázat, že pokud \(a=0\), potom platí jen jedna z možných možností.
Případ 1: b = 0.
A) Platí ta možnost, že \(a = b\), neboť \(0 = 0\). Tím jsme ale nedokázali, že platí právě jedna z oněch tří možností, musíme tedy ještě ukázat, že neplatí ani druhá, ani třetí možnost.
B) Aby platila druhá možnost, muselo by existovat takové nenulové \(n\), že \(b+n = a\). Řešíme to pro případ, že \(a = 0\) a \(b =0\), takže dosaďme a dostáváme, že \(0+n = 0\). To podle V1 znamená, že \(n = 0\), což je v rozporu s naším předpokladem.
C) Aby platila třetí možnost, muselo by existovat takové nenulové \(n\), že \(a+n = b\), opěť dosaďme a opět dostáváme, že \(0+n = 0\). To podle V1 znamená, že \(n = 0\), což je v rozporu s naším předpokladem.
Případ 2: \(b \neq 0 \).
A) Naše \(a\) se rovná nule a \(b \neq 0\), tedy \(a\) se zjevně nerovná \(b\) (vizte úvahu ve článku o Peanových axiomech, kde je ukázáno, že všechny prvky jsou různé).
B) Ukažme, že ani druhá možnost nemůže platit. Aby platila, muselo by platit, že \(b+n = a\) pro nějaké nenulové \(n\). Dosaďme za \(a\) a dostáváme, že \(b+n = 0\). Ale jestli je naše \(n\) nenulové, pak musí být následovníkem nějakého \(c \in \mathbb {N}\), pišme tedy, že \(n = succ(c) \).
Dostáváme, že \(b+succ(c) = 0\), což podle definice sčítání znamená, že \(succ(b+c) = 0\), což je ale v rozporu se třetím Peanovým axiomem.
C) Abychom ukázali, že tato možnost platí, musíme najít nějaký prvek \(n\) z \(\mathbb{N}\), pro který bude platit tato rovnost \(a+n = b\). Takovýmto prvkem je \(n = b \), neboť (nezapomínejme, že naše \(a\) je stále rovno nule) po dosazení dostáváme, že \(0+b = b\), což platí podle V1.
_________________________________________
Nyní máme náš základ pro indukci. Předpokládejme, že naše věta platí pro nějaké \(k\), tedy \(a = k\), náš indukční předpoklad tedy je, že pro všechna přirozená \(b\) platí právě jedno z následujících:
$$1. \ k = b, $$
$$2. \ k > b, $$
$$3. \ k < b. $$
Nyní chceme ukázat, že pokud tento indukční předpoklad platí, potom to platí i pro nějakého následovníka \(k\), neboli chceme ukázat, že platí právě jedno z následujících:
$$1′. \ succ(k) = b, $$
$$2′. \ succ(k) > b, $$
$$3′. \ succ(k) < b. $$
Opět si to rozdělme na případy.
Případ 1: k = b.
1′. Ukažme, že pokud \(k = b\), pak neplatí, že \(succ(k) = b\). Dokažme to sporem, předpokládejme, že platí \(k = b\) a zároveň, že \(succ(k) = b\).
Dosaďme \(b\) do \(succ(k)\) a dostáváme, že \(succ(b) = b\), což je ale v rozporu s Peanovými axiomy.
2′. Ukažme, že pokud \(k = b\), pak platí, že \(succ(k) > b\) neboli \(k+1 > b\) neboli (protože \(k=b\)) \(k+1 > k\). To můžeme přepsat na \(k < k+1\) – aby byla tato nerovnost splněna, musel by existovat nějaký prvek \(n\), pro který by platilo, že \(k+n = k+1\). Zjevně je takovým prvkem \(n = 1\), neboť \(k+1 = k+1\) neboli \(succ(k) = succ(k) \) a odtud ze čtvrtého Peanova axiomu plyne, že \(k=k\), což platí podle symetrie relace ekvivalence.
3′. Ukažme, že pokud \(k = b\), pak neplatí, že \(succ(k) < b\), a to sporem. Předpokládejme, že platí \(k = b\) a zároveň, že \(succ(k) < b\).
Dostáváme, že \(succ(b) < b\) neboli (podle V0) \(b+1 < b\), tedy že existuje \(n\) takové, že \( (b+1)+n = b\). Podle V3 máme \(n+(b+1)=b\) a opět podle V3 máme, \(n+(1+b) = b\) a podle V2 dostáváme, že \( (n+1)+b = b\). Podle V8 dostáváme, že \(n+1 = 0\) a podle V0 máme, že \(succ(n) = 0\), což je v rozporu s Peanovým třetím axiomem.
Případ 2: \(k<b \land succ(k) = b\).
1′. platí, neboť \(k<b \land succ(k) = b \Rightarrow succ(k) = b\).
2′. neplatí. Dokažme to sporem, tj. předpokládejme, že \(k<b \land succ(k) = b \land succ(k) > b\).
Z předpokladu máme, že pro nějaké nenulové \(n\) platí \(succ(k) = b+n\). Dosaďme za \(succ(k)\) a dostáváme, že \(b= n+b\). Podle V8 dostáváme, že \(0 = n \), což je spor.
3′. opět neplatí a opět to ukážeme sporem. Předpokládejme, že \(k<b \land succ(k) = b \land succ(k) < b\).
Z předpokladu máme, že pro nějaké nenulové \(n\) platí \(succ(k)+n = b\). Dosaďme za \(succ(k)\) a dostáváme, že \(b+n = b\). Podle V8 dostáváme, že \(n = 0\), což je spor.
Případ 3: \(k<b \land succ(k) \neq b\).
1′ neplatí. Vzhledem k tomu, že předpokládám, že \(succ(k) \neq b\), tak z toho těžko odvodíme, že \(succ(k) = b\).
2′ také neplatí a opět to dokážeme sporem. Předpokládejme, že platí \(k<b \land succ(k) \neq b \land succ(k) >b \). Mějme nějaké nenulové \(c\) takové, že \(succ(k) = b+c\).
Uvědomme si ještě pár věcí – to, že \(k < b\) znamená, že existuje nějaké nenulové \(m\) takové, že \(k+m = b\). Ale vzhledem k tomu, že \(m\) je nenulové, existuje nějaké \(p\), pro které platí, že \(succ(p) = m\). Neboli \(b = k+succ(p)\).
Stejně tak, protože \(c\) je nenulové, existuje nějaké \(d\), pro které platí \(succ(d) = c\).
Z předpokladu máme, že \(succ(k) = b+c\). Dosaďme za \(b\) a \(c\) a dostáváme, že
\( succ(k) = k+succ(p)+succ(d)\),
\( succ(k) = k+succ(d)+succ(p) \) podle V2,
\( succ(k) = k+succ(succ(d)+p) \) podle definice sčítání,
\(succ(k) = succ(k+succ(d)+p\) podle definice sčítání,
\(succ(k) = succ(k+p+succ(d)) \) podle V2,
\(succ(k) = succ(k+succ(p+d) \) podle definice sčítání,
\(k = k+succ(p+d)\), podle Peanova čtvrtého axiomu,
\(0 = succ(p+d)\) podle V8.
Dospěli jsme tedy k tomu, že \(0 = succ(p+d)\), což je ale v rozporu s Peanovým třetím axiomem.
3′. platí, neboli \(k<b \land succ(k) \neq b \Rightarrow succ(k) < b \).
Máme \(b = k+succ(p)\), neboli že \(b = succ(k+p) \) z definice sčítání. Podle V3 máme, že \(b = succ(p+k) \). Opět podle definice sčítání dostáváme, že \(b = p+succ(k)\) a odtud podle V3, že \(b = succ(k)+p\). To ale podle definice relace \(<\) znamená, že \(succ(k) < b\), což jsme chtěli dokázat.
Případ 4: \(k > b\).
První si uvědomme, že \(k>b\) znamená, že existuje nějaké nenulové \(m\) takové, že \(k = b+m\). Ale protože je \(m\) nenulové, pak existuje takové \(p\), že \(succ(p) = m \). Čili \(k = b+succ(p)\). K oběma dvěma stranám můžeme přičíst podle V8.2 jedničku a dostáváme podle definice funkce \(succ\), že \(succ(k) = succ(b+succ(p))\). Označme tuto vlastnost \(X\).
1′. neplatí. Předpokládejme, že platí \(k > b \land succ(k) = b\). Potom pro nějaké nenulové \(n\) platí, že \(b+n = k\) a zároveň, že \(succ(b+n) = b\). Odtud ale máme, že \(b+succ(n) = b\) a podle V8 dostáváme, že \(succ(n) = 0\), což je ale v rozporu s Peanovým třetím axiomem.
2′. platí, neboť již víme, že \(succ(k) = succ(b+succ(p))\), což podle definice sčítání můžeme přepsat na \(succ(k) = b+succ(succ(p))\). To ale znamená, že \(succ(k) > b\).
3′. neplatí. Pro spor předpokládejme, že \(k > b \land succ(k) < b\). Tedy pro nějaké nenulové \(c\) máme, že
\( b = succ(k)+c \), což plyne z \(succ(k) < b\),
\(b = succ(b+succ(p)) +c\), což plyne z \(X\),
\(b = b+succ(succ(p))+c\), což plyne z definice sčítání,
\(b = b+c+succ(succ(p))\) podle V2 a V3,
\(0 =c+succ(succ(p))\) podle V8,
\(0 = succ(c+succ(p) )\),
což je ale v rozporu s Peanovým třetím axiomem. Tím je celý důkaz V9 hotov.
V10
$$ \forall a,b,c \in \mathbb{N}: a = b \Rightarrow a \cdot c = b \cdot c. $$
Víme, že určitě platí, že \(a \cdot c=a \cdot c\). Na pravou stranu můžeme za \(a\) dosadit a dostáváme, že \(a \cdot c=b \cdot c\), čímž je důkaz hotov.
V11
$$ \forall a,b \in \mathbb{N}: a>0, b>0 \Rightarrow a \cdot b \neq 0. $$
Dokažme toto tvrzení sporem. Předpokládejme, že \(a>0\) a \(b>0\) a zároveň, že \(a \cdot b = 0\). Pokud je \(a >0\), pak existuje \(x \in \mathbb{N} \) takové, že \(a = x+1=succ(x)\) (tato rovnost platí podle V0). Pokud je \(b >0\), pak existuje \(y \in \mathbb{N} \) takové, že \(b = y+1\). Vynásobme spolu \(a\) a \(b\), dostáváme
\( 0 = a \cdot b\) z předpokladu a symetrie relace ekvivalence,
\(a \cdot b = succ(x) \cdot (y+1)\) dosazení za \(a\) a \(b\),
\( succ(x) \cdot (y+1) = succ(x) \cdot y+succ(x) \cdot 1\), podle V4,
\(succ(x) \cdot y+succ(x) \cdot 1 = succ(x) \cdot y+succ(x)\) podle V0.1,
\( succ(x) \cdot y+succ(x) = succ( succ(x) \cdot y+x) \) z definice sčítání.
Dostáváme, tedy, že \(0 = succ(succ(x) \cdot y+x)\) neboli podle symetrie ekvivalence \(succ(succ(x) \cdot y+x) = 0\), což je v rozporu s třetím Peanovým axiomem.
V12
$$ \forall x, y, z \in \mathbb{N}, z \neq 0: x<y \Rightarrow x \cdot z<y \cdot z.$$
Pokud je \(x<y\), potom existuje nějaké nenulové \(k\) takové, že \(x+k = y\). Vynásobme obě dvě strany této rovnice (podle V11) nějakým nenulovým \(z\).
Dostáváme, že \(z \cdot (x+k) = z \cdot y\). To podle V4 můžeme přepsat na \(z \cdot x+z \cdot k = z \cdot y\). Podle V6 to přepišme na \(x \cdot z+z \cdot k = y \cdot z\). Ale \(z \cdot k\) je nějaké přirozené a (podle V11) nenulové číslo, čili můžeme psát, že \(z \cdot k = l\), kde \(l\) je různé od nuly.
Máme tedy, že \(x \cdot z+l = y \cdot z\), což podle definice relace „menší než“ znamená, že \(x \cdot z < y \cdot z\).
„Zkrácení“ na násobení (V13)
Také platí, že
$$ \forall a,b,c \in \mathbb {N}, c \neq 0: a \cdot c = b \cdot c \Rightarrow a = b. $$
Je zde důležitý rozdíl oproti \(V8\), a to ten, že \(c\) se nesmí rovnat nule. Např. z toho, že \(2 \cdot 0 = 5 \cdot 0\) jistě neplyne, že \(2=5\).
Předpokládejme pro spor, že \(a \cdot c=b \cdot c \land a<b\). Podle V12 platí, že \(a<b \Rightarrow a \cdot c<b \cdot c\), což je ale spor s tím, že \(a \cdot c=b \cdot c\).
Předpokládejme pro spor, že \(a \cdot c=b \cdot c \land b<a\). Podle V12 platí, že \(b<a \Rightarrow b \cdot c<a \cdot c\), což je ale spor s tím, že \(a \cdot c=b \cdot c\).
Podle V9 ale musí platit právě jedno z následujících: \(a=b \lor a<b \lor a>b \). Vzhledem k tomu, že neplatí ani druhá, ani třetí možnost, musí platit ta první.