Důkaz indukcí

Technology

12 hours ago

Author

Důkaz indukcí je obecná metoda dokazování matematických vět. Spočívá v prokázání nějakého tvrzení typu „pro všechny objekty jisté třídy platí…“ způsobem, při němž se objekty dané třídy rozdělí do několika (většinou nekonečně mnoha) podtříd, které se uspořádají do posloupnosti a ukáže se o nich: # (první krok) Pro všechny objekty z první podtřídy platí … # (indukční krok) Jestliže platí … pro všechny objekty z předcházejících podtříd, pak platí … i pro všechny objekty z podtřídy bezprostředně za nimi následující.

Důkaz indukcí se typicky používá k důkazům takových univerzálních tvrzení (tj. tvrzení tvaru „Pro každé x platí…“), pro které existuje nějaký snadno dokazatelný speciální případ (tj. +more takové x, že o x platí…) a zároveň každý další složitější případ je v konečně mnoha krocích převeditelný na platnost pro speciální případ s tím, že počet kroků v tomto převedení se s rostoucí složitostí případu zvyšuje.

Souvislost s principem minimality

Princip indukce úzce souvisí s vlastnostmi uspořádání a relací vztahujících se k existenci minimálních prvků, jakými jsou dobrost nebo fundovanost. Princip indukce totiž může být také přeříkán následujícím způsobem nazývaným princip minimality: „Pokud dané tvrzení platí pro nějaký objekt, pak existuje podtřída obsahující objekt, pro nějž tvrzení platí, taková, že pro všechny objekty předchozích podtříd tvrzení neplatí. +more“.

Důkazy, že tyto dva principy vyjadřují tutéž skutečnost, se liší pro různé druhy indukcí. Podstata však zůstává vždy stejná: * Platí-li princip minimality, pak platí princip indukce: *: Nechť nějaké tvrzení splňuje jak první tak indukční krok principu indukce, ale neplatí pro něj závěr tohoto principu, tj. +more existuje objekt, pro nějž toto tvrzení neplatí. Pak tento objekt je takový, že pro něj platí negace tvrzení. Tedy podle principu minimality existuje podtřída obsahující objekt, pro nějž platí negace tvrzení, taková, že pro všechny objekty předcházejících podtříd neplatí negace tvrzení. Tedy existuje objekt, který je prvkem nějaké podtřídy takové, že pro všechny objekty předchozích podtříd tvrzení platí. Pak podle indukčního kroku platí i pro tento objekt, což je spor. * Platí-li princip indukce, pak platí princip minimality: *: Nechť existuje nějaký objekt, pro nějž dané tvrzení platí, ale neexistuje takový, pro nějž tvrzení platí a pro všechny objekty předcházejících podtříd neplatí. Pak jistě tvrzení neplatí pro žádný objekt z první podtřídy, neboť pro něj žádné předcházející podtřídy neexistují, a tedy by protiřečil výše zmíněnému. Tedy pro objekty z první podtřídy platí negace tvrzení. Nechť dále tvrzení neplatí pro žádné objekty podtříd předcházejících nějaké podtřídě zvolené. Pak také neplatí pro žádné objekty zvolené podtřídy, neboť jinak by to opět odporovalo výše zmíněnému. Ukázali jsme tedy, že pokud platí negace tvrzení pro všechny objekty z předcházejících podtříd, platí i pro všechny objekty podtřídy bezprostředně za nimi následující. Podle principu indukce pak platí negace tvrzení pro všechny objekty, tedy neexistuje objekt, pro nějž tvrzení platí, což je spor.

Druhy důkazů indukcí

Existuje mnoho druhů důkazů indukcí: * matematická indukce (všechny podtřídy jsou jednoprvkové a posloupnost spočetná) * transfinitní indukce (všechny podtřídy jsou jednoprvkové a posloupnost může být libovolné kardinality) * fundovaná indukce * indukce dle složitosti * sestupná indukce