Důkaz vyčerpáním - Proof by exhaustion

Důkaz vyčerpáním , známý také jako důkaz případy , důkaz případovou analýzou , úplná indukce nebo metoda hrubou silou , je metoda matematického důkazu, ve které je tvrzení, které má být prokázáno, rozděleno na konečný počet případů nebo sady ekvivalentních případů a kde se kontroluje každý typ případu, aby se zjistilo, zda dotyčná věta platí. Toto je metoda přímého důkazu . Důkaz vyčerpáním obvykle obsahuje dvě fáze:

  1. Důkaz, že soubor případů je vyčerpávající; tj. že každá instance prohlášení, která má být prokázána, odpovídá podmínkám (alespoň) jednoho z případů.
  2. Důkaz každého z případů.

Prevalence digitálních počítačů značně zvýšila pohodlí používání metody vyčerpání (např. První počítačově podporovaný důkaz čtyřbarevné věty v roce 1976), ačkoli tyto přístupy lze zpochybnit také na základě matematické elegance . K zodpovězení mnoha otázek, které jsou jim kladeny, lze využít expertní systémy . Teoreticky lze důkaz metodou vyčerpání použít vždy, když je počet případů konečný. Protože je však většina matematických množin nekonečná, používá se tato metoda k odvození obecných matematických výsledků zřídka.

V izomorfismu Curry – Howard souvisí důkaz vyčerpáním a analýza případů s párováním vzorů ve stylu ML .

Příklad

Důkaz vyčerpáním lze prokázat, že v případě, že číslo je ideální krychle , pak musí být buď násobkem 9, 1 větší než je násobek 9, nebo o 1 méně než násobek 9.

Důkaz :
Každá dokonalá krychle je krychlí nějakého celého čísla n , kde n je buď násobek 3, 1 více než násobek 3, nebo 1 méně než násobek 3. Takže tyto tři případy jsou vyčerpávající:

  • Případ 1: Pokud n = 3 p , pak n 3 = 27 p 3 , což je násobek 9.
  • Případ 2: Pokud n = 3 p  + 1, pak n 3 = 27 p 3  + 27 p 2  + 9 p  + 1, což je o 1 více než násobek 9. Například, pokud n  = 4, pak n 3 = 64 = 9 × 7 + 1.
  • Případ 3: Pokud n = 3 p  - 1, pak n 3 = 27 p 3  - 27 p 2  + 9 p  - 1, což je o 1 méně než násobek 9. Například, pokud n = 5, pak n 3 = 125 = 9 × 14 - 1. QED

Elegance

Matematici se raději vyhýbají důkazům vyčerpáním u velkého počtu případů, které jsou považovány za nedovolené . Názorným příkladem toho, jak takové důkazy mohou být ilegální, je podívat se na následující důkazy, že všechny moderní letní olympijské hry se konají v letech dělitelných 4:

Důkaz : První moderní letní olympijské hry se konaly v roce 1896 a poté každé 4 roky (opomíjely se výjimky, jako když se hry nekonaly kvůli první světové válce a druhé světové válce spolu s tím, že olympijské hry v Tokiu v roce 2020 byly odloženy na rok 2021 kvůli COVID-19 pandemie .). Protože 1896 = 474 × 4 je dělitelné čtyřmi, příští olympiáda by byla v roce 474 × 4 + 4 = (474 ​​+ 1) × 4, což je také dělitelné čtyřmi atd. (To je důkaz matematickou indukcí ). Proto je tvrzení prokázáno.

Tvrzení lze prokázat také vyčerpáním tím, že každý rok, na kterém se konaly letní olympijské hry, bude uveden výčet a zkontrolováno, že každou z nich lze dělit čtyřmi. S celkovým počtem 28 letních olympijských her od roku 2016 je to důkaz vyčerpání u 28 případů.

Důkaz vyčerpání bude kromě toho, že bude méně elegantní, vyžadovat také případ navíc při každé nové letní olympiádě. To musí být v kontrastu s důkazem matematickou indukcí, která dokazuje tvrzení na neurčito do budoucnosti.

Počet případů

Neexistuje žádná horní hranice počtu případů povolených v důkazu vyčerpáním. Někdy existují pouze dva nebo tři případy. Někdy to mohou být tisíce nebo dokonce miliony. Například důsledné vyřešení šachové hádanky může zahrnovat zvážení velmi velkého počtu možných pozic ve stromu hry daného problému.

Prvním důkazem čtyřbarevné věty byl důkaz vyčerpáním u 1834 případů. Tento důkaz byl kontroverzní, protože většina případů byla kontrolována počítačovým programem, nikoli ručně. Nejkratší známý důkaz čtyřbarevné věty dnes má stále přes 600 případů.

Obecně se pravděpodobnost chyby v celém důkazu zvyšuje s počtem případů. Důkaz s velkým počtem případů zanechává dojem, že věta je pravdivá pouze náhodou, a ne kvůli nějakému základnímu principu nebo spojení. Jiné typy důkazů - například důkaz indukcí ( matematická indukce ) - jsou považovány za elegantnější . Existují však některé důležité věty, u nichž nebyla nalezena žádná jiná metoda dokazování, například

Viz také

Poznámky