Twierdzenie Chaitina o niekompletności mówi, że żadna wystarczająco silna teoria arytmetyki nie może udowodnić, że gdzie K ( s ) to złożoność Kołmogorowa ciągów s, a L jest wystarczająco dużą stałą. L jest wystarczająco duży, jeśli jest większy niż rozmiar w bitach maszyny sprawdzającej proof (PCM). PCM dla teorii T wykonuje ciąg zakodowany jako całkowitą jako dane wejściowe i wyprowadza wartość 1, jeśli ciąg jest ważny dowód w języku T .
Załóżmy, że dla teorii T jest górną granicą dla złożoności T . Rozważ następującą hierarchię teorii: Niech podstawową teorią będzie arytmetyka Robinsona ( Q ). Augment P z coraz silniejszych axioms wielomianu ograniczonym indukcji. Niech Q ∗ będzie teorią twierdzeń, które można udowodnić za pomocą Q i dowolnego z tych ograniczonych aksjomatów indukcyjnych. Załóżmy, że możemy zdefiniować L ( Q ) i L ( Q ∗ poprzez zdefiniowanie PCM dla każdej teorii.
Chcę rozważyć ulepszoną maszynę do sprawdzania proofów (EPCM) dla . Ten EPCM przyjmuje ciąg znaków jako dane wejściowe podobnie jak ECM i ma drugie wejście, które określa stopień i poziom pod-teorii Q ∗ . Jeżeli ciąg wejściowy jest ważny dowód w Q * EPCM następnie przechodzi przez kolejne etapy dowodu w celu ustalenia najwyższego poziomu indukcji rangę i używane. Ten EPCM zapisuje następnie 1, jeśli zdanie wejściowe jest ważnym dowodem w określonej pod-teorii Q ∗ .
Czy opisany przeze mnie sprawdzony dowód jest wykonalny? Jeśli tak, to czy wielkość tego EPCM byłaby górną granicą nie tylko dla złożoności , ale także górną granicą złożoności jakiejkolwiek sub-teorii Q ∗ ?
Czy rozsądne jest stwierdzenie, że istnieje stała górna granica złożoności i wszystkich jej pod-teorii?
Pytanie to zostało zainspirowane przez nieudany dowód Nelsona na niespójność arytmetyki. Nie wspomniałem o tym wcześniej, ponieważ niektórzy uważają ten dowód za niepokojący. Moją motywacją jest zadanie interesującego pytania. Wydaje się, że CSTheory jest właściwym forum dla tego pytania. Złożoność i wszystkich jej pod-teorii jest albo stała, albo nieograniczona. Każda odpowiedź prowadzi do większej liczby pytań.
Jeśli złożoność pod-teorii jest nieograniczona, możemy zadawać pytania, jak najsłabsza pod-teoria bardziej złożona niż Q ∗ ? Lub bardziej złożony niż PA i ZFC? Myślenie o tym pytaniu pokazało mi już, że istnieje poważna granica tego, jak wiele teorii może udowodnić złożoność łańcuchów Kołmogorowa. Jeśli Q ∗ jest spójne, to żadna z jego pod-teorii nie może udowodnić K ( s ) > L ( Q ∗ ) dla dowolnego łańcucha. Oznacza to, że nawet bardzo silne pod-teorie nie mogą udowodnić, że istnieją bardziej złożone ciągi niż niektóre znacznie słabsze pod-teorie, w których słabsza teoria jest bardziej złożona niż Q .
źródło
Odpowiedzi:
Spróbuję udzielić odpowiedzi na to pytanie i postaram się wyjaśnić pewne zamieszanie co do dokładnej formy pytania.
Pierwszym punktem chcę zrobić: the w zestawieniu stałej Chaitin jest rzeczywiście funkcją T . W sensie absolutnym jest wyrazem monotonicznym w wyrazistości T : jeśli L ( T ) jest najmniejszą liczbą naturalną, dla której T ⊬ K ( s ) ≥ L ( T ) dla dowolnego ciągu s , to jeśli T ' jest spójną teorią silniejszy niż T ( T ⊢ φ implikuje T ′L T T L(T)
Jest to jednak prawdą tylko wtedy, gdy jest absolutną stałą Chaitin. W szczególności, gdy T ' dowodzi C O N ( T ) , a T " ⊢ ∃ L ∀ s ⌈ T ⊬ K ( Ż a ) ≥ Ż L ⌉L(T) T′ Con(T)
internalizując argument Chaitina. Jednakże , A betonu , dla któregol
na ogół nie będzie równyL(T) . W szczególności może być większe, na ogół proporcjonalne do wielkości dowodu w T "Con(T) T′ . Można to łatwo zauważyć w dowodzie twierdzenia samego, który w zasadniczy sposób polega na konsystencji .T
Tak więc, chociaż może udowodnić spójność układu z ograniczoną indukcją, długość tych dowodów jest tym większa, im bardziej zbliżasz się do Q ∗ w ekspresyjności (jednym ze sposobów zrozumienia twierdzeń o niekompletności jest to, że długość staje się nieskończona, gdy osiągniesz Q ∗ , dlatego nie ma skończonego dowodu zgodności w samym Q ∗ ). To samo dotyczy różnych górnych granic wewnętrznych L ( T ) s Q ∗, które można opisać dla każdej pod-teorii.Q∗ Q∗ Q∗ Q∗ L(T) Q∗
źródło