Twierdzenie Gödla o przyspieszeniu
W matematyce twierdzenie Gödla o przyspieszeniu , udowodnione przez Gödla ( 1936 ), pokazuje, że istnieją twierdzenia, których dowody można drastycznie skrócić, pracując w mocniejszych systemach aksjomatycznych.
Kurt Gödel pokazał, jak znaleźć jednoznaczne przykłady zdań w systemach formalnych, które są w tym systemie dowodliwe, ale których najkrótszy dowód jest niewyobrażalnie długi. Na przykład stwierdzenie:
- „Tego stwierdzenia nie można udowodnić w arytmetyce Peano za pomocą mniej niż symboli googolplex ”
jest możliwy do udowodnienia w arytmetyce Peano (PA), ale najkrótszy dowód ma co najmniej symbole googolplex, za pomocą argumentu podobnego do dowodu pierwszego twierdzenia Gödla o niezupełności : jeśli PA jest niesprzeczny, to nie może udowodnić stwierdzenia za pomocą mniej niż symboli googolplex, ponieważ istnienie takiego dowodu samo w sobie byłoby twierdzeniem PA, sprzecznością. Ale zwykłe wyliczenie wszystkich ciągów o długości do googolplex i sprawdzenie, czy każdy taki ciąg nie jest dowodem (w PA) stwierdzenia, daje dowód stwierdzenia (który jest z konieczności dłuższy niż symbole googolplex).
Twierdzenie ma krótki dowód w potężniejszym systemie: w rzeczywistości dowód podany w poprzednim akapicie jest dowodem w systemie arytmetyki Peano plus stwierdzenie „Arytmetyka Peano jest niesprzeczna” (którego, zgodnie z twierdzeniem o niezupełności, nie można udowodnić w arytmetyce Peano).
W tym argumencie arytmetykę Peano można zastąpić dowolnym bardziej wydajnym spójnym systemem, a googolplex można zastąpić dowolną liczbą, którą można zwięźle opisać w systemie.
Harvey Friedman znalazł kilka wyraźnych naturalnych przykładów tego zjawiska, podając kilka wyraźnych zdań w arytmetyce Peano i innych systemach formalnych, których najkrótsze dowody są absurdalnie długie ( Smoryński 1982 ). Na przykład oświadczenie
- „istnieje taka liczba całkowita n , że jeśli istnieje ciąg zakorzenionych drzew T 1 , T 2 , ..., T n taki, że T k ma co najwyżej k +10 wierzchołków, to pewne drzewo może być homeomorficznie osadzone w późniejszym jeden"
jest dowodliwy w arytmetyce Peano, ale najkrótszy dowód ma długość co najmniej A (1000), gdzie A (0)=1 i A ( n +1) = 2 A ( n ) . Stwierdzenie to jest szczególnym przypadkiem twierdzenia Kruskala i ma krótki dowód w arytmetyce drugiego rzędu .
Jeśli weźmiemy arytmetykę Peano razem z negacją powyższego stwierdzenia, otrzymamy niespójną teorię, której najkrótsza znana sprzeczność jest równoważnie długa.
Zobacz też
- Buss, Samuel R. (1994), „O twierdzeniach Gödla o długościach dowodów. I. Liczba linii i przyspieszenie arytmetyki”, The Journal of Symbolic Logic , 59 (3): 737–756, doi : 10.2307/2275906 , ISSN 0022-4812 , JSTOR 2275906 , MR 1295967
- Buss, Samuel R. (1995), „O twierdzeniach Gödla o długości dowodów. II. Dolne granice rozpoznawania dowodliwości symbolu k”, w: Clote, Peter; Remmel, Jeffrey (red.), Matematyka wykonalna, II (Ithaca, NY, 1992) , Progr. Oblicz. nauka Aplikacja Logika, tom. 13, Boston, MA: Birkäuser Boston, s. 57–90, ISBN 978-0-8176-3675-3 , MR 1322274
- Gödel, Kurt (1936), „Über die Länge von Beweisen” , Ergebnisse eines Mathematischen Kolloquiums (w języku niemieckim), 7 : 23–24, ISBN 9780195039641 , Przedruk z tłumaczeniem na język angielski w tomie 1 jego dzieł zebranych.
- Smoryński, C. (1982), "Odmiany doświadczenia nadrzewnego", Math. Intelligencer , 4 (4): 182–189, doi : 10.1007/bf03023553 , MR 0685558