Gödelsova věta o zrychlení - Gödels speed-up theorem - Wikipedia

V matematice Gödelova věta o zrychlení, prokázáno Gödel  (1936 ), ukazuje, že existují věty, jejichž důkazy lze drasticky zkrátit prací ve výkonnějších axiomatických systémech.

Kurt Gödel ukázal, jak najít explicitní příklady prohlášení ve formálních systémech, které jsou v tomto systému prokazatelné, ale jejichž nejkratší důkaz je nepředstavitelně dlouhý. Například prohlášení:

„Toto tvrzení nelze prokázat v Peano aritmetika za méně než a googolplex symboly "

je prokazatelný v aritmetice Peano (PA), ale nejkratší důkaz má alespoň googolplexové symboly, argumentem podobným důkazu Gödelova první věta o neúplnosti: Pokud je PA konzistentní, pak nemůže dokázat tvrzení méně než googolplexovými symboly, protože existence takového důkazu by sama o sobě byla teorémem PA, rozporem. Ale jednoduše výčet všech řetězců délky až po googolplex a kontrola, že každý takový řetězec není důkazem (v PA) příkazu, poskytuje důkaz prohlášení (který je nutně delší než symboly googolplex).

Výrok má krátký důkaz v silnějším systému: důkaz uvedený v předchozím odstavci je ve skutečnosti důkazem v systému Peanoovy aritmetiky plus tvrzení „Peanoova aritmetika je konzistentní“ (což podle věty o neúplnosti nelze dokázat v aritmetice Peano).

V tomto argumentu může být Peanoova aritmetika nahrazena jakýmkoli výkonnějším konzistentním systémem a googolplex může být nahrazen libovolným číslem, které lze v systému stručně popsat.

Harvey Friedman našel některé explicitní přirozené příklady tohoto jevu, poskytl některé explicitní výroky v aritmetických a jiných formálních systémech Peano, jejichž nejkratší důkazy jsou směšně dlouhé (Smoryński 1982 ). Například prohlášení

"existuje celé číslo n takové, že pokud existuje sled kořenových stromů T1, T2, ..., Tn takhle Tk má nanejvýš k+10 vrcholů, pak může být nějaký strom homeomorfně vložený v pozdějším "

je prokazatelný v aritmetice Peano, ale nejkratší důkaz má alespoň délku A(1000), kde A(0) = 1 a A(n+1)=2A(n). Toto prohlášení je zvláštním případem Kruskalova věta a má krátký důkaz v aritmetika druhého řádu.

Pokud vezmeme Peanovu aritmetiku spolu s negací výše uvedeného tvrzení, získáme nekonzistentní teorii, jejíž nejkratší rozpor je nepředstavitelně dlouhý.

Viz také

Reference

  • Buss, Samuel R. (1994), „K Gödelovým větám o délkách důkazů. I. Počet řádků a zrychlení pro aritmetiku“, The Journal of Symbolic Logic, 59 (3): 737–756, doi:10.2307/2275906, ISSN  0022-4812, JSTOR  2275906, PAN  1295967
  • Buss, Samuel R. (1995), „K Gödelovým větám o délkách důkazů. II. Dolní hranice pro uznání prokazatelnosti symbolu k“, Clote, Peter; Remmel, Jeffrey (eds.), Realizovatelná matematika, II (Ithaca, NY, 1992), Progr. Comput. Sci. Appl. Logika, 13, Boston, MA: Birkhäuser Boston, str. 57–90, ISBN  978-0-8176-3675-3, PAN  1322274
  • Gödel, Kurt (1936), „Über die Länge von Beweisen“, Ergebinisse Eines Mathematischen Kolloquiums (v němčině), 7: 23–24, ISBN  9780195039641 „Přetištěno do anglického překladu v 1. dílu svých sebraných děl.
  • Smoryński, C. (1982), „Odrůdy stromové zkušenosti“, Matematika. Vyzvědač, 4 (4): 182–189, doi:10.1007 / bf03023553, PAN  0685558