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.

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ý.

Základem definice TREE(3) je jednoduchá kombinatorická hra se značkováním struktur zvaných full trinary trees (úplné trojvětvené stromy):

1. Uvažujeme všechny možné konečné stromové struktury, kde každý vrchol má buď 0, nebo 3 potomky. Takové struktury se nazývají full trinary trees.
2. Každý vrchol v každém stromu je možné označit jednou ze tří barev.
3. Dvě podstruktury jsou považovány za stejné, pokud jsou izomorfní a mají stejný barevný vzor.
4. Pokud v nějakém značení vznikne taková shodná dvojice podstromů, nazýváme to bad pattern (špatný vzor).
5. Cílem je najít nejmenší počet vrcholů, pro který je zaručeno, že každé možné značení bude obsahovat alespoň jeden bad pattern.

Číslo TREE(3) je tedy ten nejmenší počet vrcholů, od kterého nelze vyrobit žádné "dobré" značení bez výskytu bad pattern.

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.

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í.

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

• TREE(3) na Googology Wiki

Zdroj