Tento príspevok slúži ako zbierka úloh na precvičenie induktívnych definíc a dôkazu indukciou. V cvičeniach si zadefinujeme prirodzené čísla, induktívne princípy na nich a postupne vybudujeme elemntárnu aritmetiku. Primárna motivácia pre voľbu týchto cvičení je jednoduchosť dokazovaných tvrdení a praktický nulové predpoklady na znalosť konkrétnych oblastí matematiky. Každý dôkaz by teda mať byť detailný a odkazovať buď na lokálne predpoklady alebo už dokázané lemmy a tvrdenia. Cvičenia sú okrem indukcie zamerané na schopnosť pracovať s lokálnym kontextom (správne chápanie toho čo vieme a čo chceme).
Prirodzené čísla
Uvážme, že máme prirodzené čísla induktívne definované následovne:
\[\begin{aligned} 0 &\in \mathbb{N}, \\ n &\in \mathbb{N} \implies \text{s}(n) \in \mathbb{N}. \end{aligned}\]Potom každé prirodzené číslo \(n\) má jednoznačné odvodenie v predošlých pravidlách a vyzerá následovne:
\[ n = \underbrace{\text{s}(\text{s}(\text{s}(...(\text{s}}_{\text{$n$-krát}}(0))...))). \]
Táto definícia je trocha naivná a neformálna, no pre potreby tohto cvičenia stačí. Konštanty definujeme prirodzene, no pamätajme, že je to len “skratka”. Čísla ako 1, 2 alebo 3 sú teda len mená, ktoré reprezentujú postupne \(\text{s}(0), \text{s}(\text{s}(0))\) a \(\text{s}(\text{s}(\text{s}(0)))\).
Na takto definovaných prirodzených číslach vieme induktívne definovať funkcie a to popisom výslednej hodnoty v \(0\) (bázovom prvku) a hodnoty v \(\text{s}(n)\) s prístupom k hodnote v \(n\). Takto definovaná funkcia \(f : \mathbb{N}\to \mathbb{N}\) teda bude vyzerať následovne:
\[\begin{aligned} f(0) &= \text{popis hodnoty v $0$} \\ f(\text{s}(n)) &= \text{popis hodnoty v $\text{s}(n)$ s prístupom k $f(n)$} \end{aligned}\]napríklad pre
Definícia 0.1. Nech funkcia \(\text{double}: \mathbb{N}\to \mathbb{N}\) je funkcia definovaná následovným induktívnym popisom: \[\begin{aligned} \text{double}(0) &= 0 \\ \text{double}(\text{s}(n)) &= \text{s}(\text{s}(\text{double}(n))) \end{aligned}\]Definícia 0.2. Nech funkcia \(\text{quadruple}: \mathbb{N}\to \mathbb{N}\) je funkcia definovaná následovným induktívnym popisom:
\[\begin{aligned} \text{quadruple}(0) &= 0 \\ \text{quadruple}(\text{s}(n)) &= \text{s}(\text{s}(\text{s}(\text{s}(\text{quadruple}(n))))) \end{aligned}\]Kontrola 0.1 Ako sa vyhodnotí \(\text{double}(2)\)? Ako sa vyhodnotí \(\text{quadruple}(2)\)?
Tvrdenia o takýchto funkciách potom dokazujeme zväčša indukciou. V našom prípade (a aj obecne v induktívne definovaných štruktúrach) v takomto dôkaze dokazujeme tvrdenie pre všetky možné “hodnotové konštruktory”–v našom prípade konštanta \(0\) a unárne \(\text{s}\)–s tým, že o vnútorných hodnotách prijímame indukčný predpoklad. V našom prípade sa teda dá indukcia vyjadriť ako:
\[ \Big[ \underbrace{\varphi(0)}_{\text{báza}}\land \underbrace{\forall k . \big( \varphi( k ) \implies \varphi( s( k ) ) \big)}_{\text{indukčný krok}} \Big] \iff \Big( \forall n . \varphi( n ) \Big) \]
Všimnime si podobnosť so samotnou induktívnou definíciou prirodzených čísel. Ilustrujme takýto dôkaz na nasledujúcom tvrdení.
Tvrdenie 0.1 Pre všetky \(n \in \mathbb{N}\) platí \(\text{double}(\text{double}(n)) = \text{quadruple}(n)\).
Dôkaz: Indukciou voči \(n\):
- Báza: Nech teda \(n = 0\). Z definíce funkcie \(\text{double}\) a \(\text{quadruple}\) dostávame nasledujúce rovnosti
\[\text{double}(\text{double}(0)) \doteq \text{double}(0) \doteq 0 \doteq \text{quadruple}(0).\]
- Indukčný krok: Nech \(k \in \mathbb{N}\) je ľubovoľné také, že \(\text{double}(\text{double}(k)) = \text{quadruple}(k)\). Treba ukázať, že \(\text{double}(\text{double}(s(k))) = \text{quadruple}(s(k))\). Potom ale \[\begin{aligned} \text{double}(\text{double}(s(k))) &\doteq \text{double}(\text{s}(\text{s}(\text{double}(k)))) \\ &\doteq \text{s}(\text{s}(\text{double}(\text{s}(\text{double}(k))))) \\ &\doteq \text{s}(\text{s}(\text{s}(\text{s}(\text{double}(\text{double}(k)))))) \\ &\overset{\small IP}{=}\text{s}(\text{s}(\text{s}(\text{s}(\text{quadruple}(k))))) \\ &\doteq \text{quadruple}(s(k)). \end{aligned}\]
Z indukcie teda plynie originálne tvrdenie. \(\square\)
V našom dôkaze sme rovnosti označovali \(\doteq\) v prípade, že plynú z definície, \(\overset{\small IP}{=}\) v prípade, že plynú z induktívneho predpokladu. Posledný typ rovností, ktoré v tomto dokumente môžeme (a budeme) potrebovať, je odvolávanie na už dokázané tvrdenia a rôzne predpoklady. V každom dôkaze by ste pri každej rovnosti mali byť schopní ukázať na definíciu, lemmu, tvrdenie alebo predpoklad, z ktorého táto rovnosť priamo plynie.
Napríklad v predošlom dôkaze
rovnosť vyplýva z definície \(\text{double}\) aplikovaného na \(\text{s}(k)\), teda \(\text{double}(\text{s}(k)) = \text{s}(\text{s}(\text{double}(k)))\),
rovnosť vyplýva z definície \(\text{double}\) aplikovaného na \(\text{s}(\text{s}(\text{double}(k)))\), teda \(\text{double}(\text{s}(\text{s}(\text{double}(k)))) = \text{s}(\text{s}(\text{double}(\text{s}(\text{double}(k)))))\),
rovnosť vyplýva z definície \(\text{double}\) aplikovaného na \(\text{s}(\text{double}(k))\), teda \(\text{double}(\text{s}(\text{double}(k))) = \text{s}(\text{s}(\text{double}(\text{double}(k))))\),
rovnosť vyplýva z indučného predpokladu, podľa ktorého \(\text{double}(\text{double}(k)) = \text{quadruple}(k)\),
rovnosť vyplýva z definície \(\text{quadruple}\) aplikovaného na \(\text{s}(k)\), teda \(\text{quadruple}(\text{s}(k)) = \text{s}(\text{s}(\text{s}(\text{s}(\text{quadruple}(k)))))\).
V niektorých tvrdeniach však netreba indukciu.
Tvrdenie 0.2 Pre všetky \(n \in \mathbb{N}\) platí \(\text{double}(\text{double}(\text{double}(\text{double}(n))))\) = \(\text{quadruple}(\text{quadruple}(n))\).
Dôkaz. Nech \(n \in \mathbb{N}\) je ľubovoľné, naďalej pevné. Potom z Tvrdenia 0.1 aplikovaného na \(n\) vieme, že \(\text{double}(\text{double}(n)) = \text{quadruple}(n)\) a teda
\[\begin{equation} \text{double}(\text{double}(\text{double}(\text{double}(n)))) = \text{double}(\text{double}(\text{quadruple}(n))) \end{equation}\]
Potom ale z Tvrdenia 0.1 aplikovaného na \(\text{quadruple}(n)\) vieme, že \(\text{double}(\text{double}(\text{quadruple}(n))) = \text{quadruple}(\text{quadruple}(n))\).
\(\square\)
Sčítanie
Na úvod začneme definíciou sčítania a dokázaním jeho vlastností.
Definícia 1. Pre pevné \(a \in \mathbb{N}\) definujte induktívne funkciu \(\text{add}_a : \mathbb{N}\to \mathbb{N}\), ktorá sa bude chovať ako pričítanie \(a\); \(\text{add}_a(n)\) by teda malo byť číslo reprezentujúce súčet \(n\) a \(a\).\(^{★}\)
Notácia 1. Definujeme operátor \(+\) následovne: \((b + a) := \text{add}_a(b)\).
Pri notácii nemusíte nič robiť. Treba si len vždy rozmyslieť, na ktorej strane je ktoré číslo. Uvedomte si, že podobne ako pri konštantách, by sme sa bez nich zaobišli.
Uvedomte si, že sme si asociativitu operátoru \(+\) nedefinovali, teda nemôžeme mať výraz, kde by boli zátvorky implicitné; napr. \(1 + 2 + 3\). Štandardne by sme všade mali písať okolo \(+\) zátvorky. V záujme čitateľnosti budeme ale najvonkajší pár zátvoriek vynechávať, teda \(1 + 2\) chápeme ako \((1 + 2)\). Pri \(1 + 2 + 3\) ale musíme určiť zátvorky, napr. \((1 + 2) + 3\) alebo \(1 + (2 + 3)\). V tento moment nevieme, že v obecnosti sú tieto dve možnosti ekvivalentné. Zároveň nevieme, že je tento operátor komutatívny, teda že v obecnosti platí \(a + b = b + a\). Aj napriek tomu, že používame štandardný symbol +, nevieme aké ma chovanie. Tento operátor totiž vznikol dva paragrafy vyššie a vnútri sa odvoláva na vašu (potencionálne nesprávnu) definíciu (napr. takú, ktorá v skutočnosti ráta odčítanie). O týchto vlastnostiach sa ale presvedčíme vo zvyšku tejto sekcie. V procese dokazovania budete musieť pracovať so svojou definíciou podobne ako sme v Tvrdení 0.1 pracovali s definíciou funkcií \(\text{double}\) a \(\text{quadruple}\).
Dobrý nápad je urobiť si nasledujúcu kontrolu.
Kontrola 1. Vyhodnoťte nasledujúce výrazy: \(0 + 3\), \(3 + 0\), \(2 + 2\). Chová sa vaša definícia správne? (výraz \(0 + 3\) je “len skratka”, je teda definične rovný \(\text{add}_{\text{s}(\text{s}(\text{s}(0)))}(0)\), no nie \(\text{add}_0(\text{s}(\text{s}(\text{s}(0))))\); na poradí záleží).
V tento moment sme si definovali sčítanie prirodzených čísel. Je ale zjavné¸ že definícia tohto sčítania je nesymetrická (viď proces vyhodnocovania \(0 + 3\) a \(3 + 0\)). Tento fakt budú demonštrovať aj rozdiely v obtiažnosti dôkazov nasledujúcich, zdanlivo podobných, tvrdení. Hint: Potrebujem pri všetkých použiť indukciu? Nie sú niektoré rovnosti len definície? Rozpíšte si výraz \(b + a\) do podoby \(\text{add}_a(b)\). V prípade, že neviete ako začať, inšpirujte sa dôkazom Tvrdenia 0.1.
Úlohy majú hodnotenie obtiažnosti značené: \(^{★}\), \(^{★★}\) alebo \(^{★★★}\). Táto obtiažnosť je ale orientačná. Môže sa vám kľudne stať, že \(^{★★★}\) bude jednoduchšie ako \(^{★}\).
Lemma 1. Pre všetky \(n \in \mathbb{N}\) platí, že \(0 + n = n\). \(^{★}\)
Lemma 2. Pre všetky \(n \in \mathbb{N}\) platí, že \(n + 0 = n\). \(^{★}\)
Lemma 3. Pre všetky \(n \in \mathbb{N}\) platí, že \(1 + n = s(n)\). \(^{★}\)
Lemma 4. Pre všetky \(n \in \mathbb{N}\) platí, že \(n + 1 = s(n)\). \(^{★}\)
V nasledujúcich dvoch tvrdeniach si môžete zvoliť parameter, voči ktorému budete robiť indukciu. Indukcia sa dá “vrstviť”, teda môžete napríklad robiť indukciu voči \(m\) v indukčnom kroku indukcie voči \(n\). V týchto príkladoch to ale netreba. Veďte teda indukciu buď voči \(m\), alebo \(n\). Hint: v tomto bode sa môže oplatiť použiť predošlé lemmy.
Lemma 5. Pre všetky \(n, m \in \mathbb{N}\) platí, že \(s(m + n) = s(m) + n\). \(^{★}\)
Lemma 6. Pre všetky \(n, m \in \mathbb{N}\) platí, že \(s(m + n) = m + s(n)\). \(^{★★}\)
Lemma 7. Pre všetky \(n \in \mathbb{N}\) platí, že \(n + n = \text{double}(n)\). \(^{★★}\)
Teraz sa presunieme k známym vlastnostiam komitativity a asociativity. Hint: hore uvedené tvrdenia sa v nasledujúcich dôkazoch môžu hodiť. Ak sa teda zaseknete, pozrite sa čo už viete.
Tvrdenie 1. Pre všetky \(m, n \in \mathbb{N}\) platí, že \(m + n = n + m\). \(^{★★}\)
Tvrdenie 2. Pre všetky \(m, n, l \in \mathbb{N}\) platí, že \(m + ( n + l ) = ( m + n ) + l\). \(^{★★★}\)
Dávajte si pozor, že ste v dôkaze predošlého cvičenia neurobili chybu \(\text{s}(a + b) + c = \text{s}( a + b + c)\), na ľavú stranu totiž ide celý výraz v zátvorke a teda \(\text{s}(a + b) + c = \text{s}((a + b) + c)\). Spomeňte si na komentár ohľadom zátvorkovania.
Násobenie
Definícia 2. Pre pevné \(a \in \mathbb{N}\) definujte induktívne funkciu \(\text{mul}_a : \mathbb{N}\to \mathbb{N}\), ktorá sa bude chovať ako vynásobenie číslom \(a\); \(\text{mul}_a(n)\) by teda malo byť číslo reprezentujúce súčin čísel \(n\) a \(a\). \(^{★★}\)
Notácia 2. Definujeme operátor \(\cdot\) následovne: \((b \cdot a) := \text{mul}_a(b)\).
Situácia s zátvorkami, asociativitou a komutativitou je podobná ako pri \(+\).
Kontrola 2. Vyhodnoťte nasledujúce výrazy: \(0 \cdot 3\), \(3 \cdot 1\), \(2 \cdot 2\). Chová sa vaša definícia správne?
Podobne ako v prípade sčítania je táto definícia silne nesymetrická. Hint: aspoň v pár prikládoch si rozpíšte \(b \cdot a\) ako \(\text{mul}_a(b)\).
Lemma 8. Pre všetky \(n \in \mathbb{N}\) platí, že \(0 \cdot n = 0\). \(^{★}\)
Lemma 9. Pre všetky \(n \in \mathbb{N}\) platí, že \(n \cdot 0 = 0\). \(^{★★}\)
Lemma 10. Pre všetky \(n \in \mathbb{N}\) platí, že \(1 \cdot n = n\). \(^{★★}\)
Lemma 11. Pre všetky \(n \in \mathbb{N}\) platí, že \(n \cdot 1 = n\). \(^{★★}\)
Lemma 12. Pre všetky \(n \in \mathbb{N}\) platí, že \(s(m) \cdot n = ( m \cdot n ) + n\). \(^{★}\)
Nasledujúce cvičenia sú koncepčne jednoduché, no treba si dať pozor na korektnosť úprav. Pri každej rovnosti si rozmyslite, z ktorého tvrdenia plynie.
Lemma 13. Pre všetky \(n \in \mathbb{N}\) platí, že \(m \cdot s(n) = m + ( m \cdot n )\). \(^{★★★}\)
Lemma 14. Pre všetky \(n \in \mathbb{N}\) platí, že \(2 \cdot n = n + n\). \(^{★★}\)
Lemma 15. Pre všetky \(n \in \mathbb{N}\) platí, že \(n \cdot 2 = n + n\). \(^{★★★}\)
Hint: Pre nasledujúcu lemmu existuje veľmi krátky argument.
Lemma 16. Pre všetky \(n \in \mathbb{N}\) platí, že \(2 \cdot n = \text{double}(n)\). \(^{★★}\)
A teraz už známe tvrdenia distributivity, asociativity a komutativity.
Tvrdenie 3. Pre všetky \(m, n, l \in \mathbb{N}\) platí, že \(l\cdot( m + n ) = l \cdot m + l \cdot n\). \(^{★★}\)
Tvrdenie 4. Pre všetky \(m, n, l \in \mathbb{N}\) platí, že \(( m + n )\cdot l = m \cdot l + n \cdot l\). \(^{★★}\)
Tvrdenie 5. Pre všetky \(m, n \in \mathbb{N}\) platí, že \(m \cdot n = n \cdot m\). \(^{★★★}\)
Tvrdenie 6. Pre všetky \(m, n, l \in \mathbb{N}\) platí, že \(m \cdot ( n \cdot l ) = ( m \cdot n ) \cdot l\). \(^{★★★}\)
Fin.
Tento príspevok je inšpirovaný The Natural Number Game, v ktorom sa tieto tvrdenia dokazujú v Lean. Alternatíva, ktorá avšak presahuje tento príspevok je napríklad Logical Foundations, ktorá približuje dokazovanie v nástroji Coq.