TREE(3)

TREE(3) je extrémně velké přirozené číslo definované americkým logikem Harveym Friedmanem v oblasti kombinatoriky, matematické logiky a teorie důkazu. Jde o konečné číslo vzniklé jako řešení jednoduše formulovaného kombinatorického problému, jehož velikost však přesahuje veškerou běžnou matematickou intuici i formální zápis.

Tento článek nemusí být čtenáři dostatečně srozumitelný, protože obsahuje příliš mnoho odborných nebo naopak slangových výrazů.

Tento článek není dostatečně ozdrojován, a může tedy obsahovat informace, které je třeba ověřit.

Kontext

TREE(3) je součástí posloupnosti čísel TREE(n), kde každé následující číslo je definováno pomocí stále složitějších kombinatorických a logických pravidel. Tato čísla slouží k ilustraci hranic formálních axiomatických systémů, jako je Peanova aritmetika, a ukazují, že i jednoduché otázky mohou vést k extrémně složitým odpovědím.

Číslo TREE(3) vzniká jako minimální počet potřebný pro zajištění pravdivosti specifického tvrzení o značení stromových struktur konečným počtem barev. Přestože lze podmínky problému popsat stručně, výpočet výsledného čísla je mimořádně náročný.

Pravidla hry

Základem definice TREE(3) je jednoduchá kombinatorická hra:

1. Uvažujeme všechny možné konečné posloupnosti zakořeněných stromů (tj jejichž jeden uzel je zvolen jako kořenový).
2. Každý vrchol v každém stromě musí být označen jednou ze tří barev.
3. n-tý strom může obsahovat nejvýše n vrcholů.
4. Strom je považován za inf-vnořený do jiného stromu, pokud je izomorfní s nějakou jeho částí a mají stejný barevný vzor.
5. Strom v posloupnost nesmí obsahovat žádný předchozí strom jako inf-vnořený.
6. Cílem je najít nejvyšší možný počet vrcholů, pro který lze tyto podmínky splnit

Číslo TREE(3) je tedy nejvyšší možný počet vrcholů (a pro jakýkoliv vyšší počet již nelze uvedené podmínky splnit).

TREE(3)_sequence

Velikost

TREE(3) je konečné a přesně definované číslo, jehož velikost však nelze vyjádřit pomocí běžné aritmetiky, exponenciální notace ani pokročilých zápisů jako je Knuthova šipková notace. Jeho hodnota dalece převyšuje známá velká čísla jako googol, googolplex nebo Grahamovo číslo.

Číslo	Přibližná velikost
Googol	10^100
Googolplex	10^(10^100)
Grahamovo číslo	Extrémně velké, ale stále menší než TREE(3)
TREE(3)	Mnohonásobně větší než všechna výše uvedená čísla

Význam

TREE(3) má význam především v teoretické logice a teorii důkazu. Poukazuje na hranice, které nelze překročit v rámci běžně používaných axiomatických systémů, a slouží jako příklad konečně formulovatelného problému s řešením mimo rozsah běžné matematiky. Ilustruje také rychlost růstu některých matematických funkcí a komplexitu jednoduchých kombinatorických tvrzení.

Odkazy

Literatura

• Friedman, Harvey. Finite Functions and the Necessary Use of Large Cardinals.
• Raatikainen, Panu. Gödel's Incompleteness Theorems. In: Stanford Encyclopedia of Philosophy

Externí odkazy

• TREE(3) na Googology Wiki