- Jak możemy wyrazić „ ” jako formułę pierwszego rzędu?
- Który poziom hierarchii arytmetycznej zawiera tę formułę (i jaki jest obecnie znany minimalny poziom hierarchii, która ją zawiera)?
W celach informacyjnych zobacz ten post na blogu autorstwa Lipton .
Odpowiedzi:
Po pierwsze, chcę skierować komentarze do pytania, w którym zasugerowano, że wyraża się „fałsz”P.= PS.P.A C.mi ponieważ stwierdzenie jest fałszywe. Chociaż może to być dobry żart, myślenie w ten sposób jest bardzo szkodliwe. Kiedy pytamy, jak wyrazić określone zdanie w określonym systemie formalnym, nie mówimy o wartościach prawdy. Gdyby tak było, to kiedy ktoś zapytał „Jak zapisać fakt, że istnieje nieskończenie wiele liczb pierwszych?” moglibyśmy odpowiedzieć „3 + 3 = 6”, ale to na pewno nie zadziała. Z tego samego powodu „fałsz” nie jest prawidłową odpowiedzią na „jak zapisać”P.= PS.P.A C.mi ? ". Myślę, że Frege i Russell starali się nas nauczyć tej lekcji. Ok, teraz odpowiedź.
Pokażę, jak wyrazićP.S.P.A C.mi⊆ P. , drugi kierunek jest podobny, a następnie można je połączyć w spójkę, aby uzyskać P.S.P.A C.mi= P . W każdym razie do celów może być wystarczające wyrażenieP.S.P.A C.mi⊆ P. , w zależności od tego, co robisz.
Wykorzystanie technik podobnych do tych w konstrukcji predykatu KleeneT. , możemy skonstruować ograniczoną formułę kwantyfikatora a c c e pts p a c e(k,m,n) (który w ten sposób rezyduje w Σ00=Π00 ) mówiąc „kiedy uruchomimy maszynę zakodowaną przez k i ograniczył wykorzystanie miejsca do |n|m , urządzenie akceptuje dane wejściowe n „Tutaj | n | jest długością n . Nieformalny sposób dostrzeżenia istnienia takich formuł jest następujący: danyk , m , i n możemy obliczyć prymitywną rekurencyjną zależną od tego, ile czasu i przestrzeni będziemy potrzebować (tj. co najwyżej | n|m przestrzeń i co najwyżej 2)| n|m czas). Następnie po prostu przeszukujemy wszystkie możliwe ślady wykonania, które mieszczą się w obliczonych granicach - takie wyszukiwanie jest raczej nieefektywne, ale jest prymitywne rekurencyjne i dlatego możemy wyrazić je jako formułę ograniczoną.
Istnieje podobna formułaa c c e ptt i m e( k , m , n ) w którym obowiązuje czas wykonywania | n|m .
Rozważmy teraz wzór:
Możemy to poprawić, jeśli zamiast tego chcemy wyrazić zdanie „TQBF is in polytime ”, co powinno wystarczyć dla większości aplikacji, ponieważ TQBF jest ukończony PSPACE, a więc bycie w czasie polytime jest równoważne zPSPACE⊆P . Pozwolićk0 być (kod) maszyną, która rozpoznaje TQBF w przestrzeni |n|m0 . Następnie "TQBF∈P „można wyrazić jako
źródło
Andrej już to wyjaśniłP=PSPACE można zapisać jako Σ02 -zdanie. Pozwól mi wspomnieć, że ta klasyfikacja jest optymalna w tym sensie, że jeśli instrukcja jest równoważna doΠ02 - to fakt ten nie relatywizuje. Dokładniej, zestaw wyroczniA takie, że PA=PSPACEA jest definiowany przez Σ02 -formula z bezpłatną zmienną drugiego rzędu A , ale nie jest to możliwe do zdefiniowania Π02 -formuła. Argument jest przedstawiony (dlaP=NP , ale działa tak samo dla PSPACE ) w komentarzach na stronie /mathpro/57348 . (W rzeczywistości można wykazać, opracowując ideę, że zestaw jestΣ02 -kompletne w odpowiednim znaczeniu).
EDYCJA: Dowód topologiczny podany w powiązanym komentarzu jest krótki, ale może wydawać się trudny. Oto argument wymuszania bezpośredniego.
Odϕ(B) , tam istnieje y0 takie, że θ(B,0,y0) . Jednak,θ jest ograniczoną formułą, stąd ocena wartości prawdy θ(B,0,y0) używa tylko skończonej części wyroczni. Zatem istnieje część skończonab0 z B takie, że θ(A,0,y0) za każdą wyrocznię A rozsuwalny b0 .
PozwolićC[b0] oznacz wyrocznię, która się rozciąga b0 i zgadza się z C gdzie b0 jest niezdefiniowany. OdPA i PSPACEA nie ma na nas wpływu skończona zmiana wyroczni, którą mamy ψ(C[b0]) . Istnieje ten sam argument, co powyżejz0 i część skończona c0 z C[b0] takie, że η(A,0,z0) dla każdego A rozsuwalny c0 . Możemy to założyćc0 rozszerza się b0 .
Kontynuując w ten sam sposób, konstruujemy nieskończone sekwencje liczby0,y1,y2,… , z0,z1,z2,… i skończone częściowe wyrocznie b0⊆c0⊆b1⊆c1⊆b2⊆⋯ takie, że
Teraz pozwólA bądź wyrocznią, która rozciąga wszystko bn i cn . Zatem 1 i 2 implikują toϕ(A) i ψ(A) jednocześnie utrzymują, co jest sprzeczne z założeniem, że są one wzajemnie uzupełnieniem.
źródło