Widmo zdania

W logice matematycznej widmo zdania to zbiór liczb naturalnych występujących jako wielkość skończonego modelu , w którym dane zdanie jest prawdziwe.

Definicja

Niech ψ będzie zdaniem w logice pierwszego rzędu . Widmo ψ jest zbiorem liczb naturalnych n takich , że istnieje skończony model dla ψ z n elementami .

Jeśli słownik dla ψ składa się tylko z symboli relacyjnych, to ψ można traktować jako zdanie w egzystencjalnej logice drugiego rzędu (ESOL) kwantyfikowane na podstawie relacji, na podstawie pustego słownika. Uogólnione widmo to zbiór modeli ogólnego zdania ESOL.

Przykłady

• Widmo formuły pierwszego rzędu

${\ Displaystyle \ istnieje z, o ~ \ forall a, b, c ~ \ istnieje d, e$

$z = a = z + a ~ \ ziemia ~ a \ cdot z = z = z$

${\ Displaystyle \ ziemia ~ a + b = b + a ~ \ ziemia ~ a \ cdot (b + c) = a \ cdot b + a \cdot c~\land ~(a+b)+c=a+(b+c)}$

${\ Displaystyle \ ziemia ~ a \ cdot o = a = o \ cdot a ~ \ ziemia ~ a \ cdot e = o ~ \ ziemia ~ (a \ cdot b) \ cdot c = a \ cdot ( b\cdot c)}$

jest ${\ Displaystyle \ {p ^ {n} \ mid p {\ tekst { liczba pierwsza}}, n \ w \ mathbb {N} \}} , zbiór$ potęg liczba pierwsza . Rzeczywiście, $i$ for ${\ displaystyle 0}$ dla $displaystyle$ 1 $1}$ to zdanie opisuje zestaw pól ; kardynalność skończonego ciała _ jest potęgą liczby pierwszej.

• $Displaystyle \ istnieje S,T~\forall x~\left\{x\in S\iff x\not \in T\land ~f(f(x))=x\land ~x\in S\iff f(x) \in T\right\}}$ S to zbiór parzyste . $jest$ , bijekcją między i ${$ \ $displaystyle$$T$ } i i $wszechświata$ Stąd liczność wszechświata jest parzysta.
• Zbiór zbiorów skończonych i współskończonych to zbiór widm logiki pierwszego rzędu z relacją następnika.
• Zbiór ostatecznie okresowych zbiorów to zbiór widm monadycznej logiki drugiego rzędu z funkcją jednoargumentową. Jest to również zbiór widm monadycznej logiki drugiego rzędu z funkcją następcy.

Nieruchomości

Twierdzenie Fagina jest wynikiem teorii złożoności opisowej , która stwierdza, że ​​zbiorem wszystkich własności dających się wyrazić w logice egzystencjalnej drugiego rzędu jest właśnie klasa złożoności NP . Jest to niezwykłe, ponieważ jest to charakterystyka klasy NP, która nie odwołuje się do modelu obliczeniowego, takiego jak maszyna Turinga . Twierdzenie zostało udowodnione przez Ronalda Fagina w 1974 r. (ściśle w 1973 r. w jego pracy doktorskiej).

Równoważność maszyn Turinga

Jako wniosek, Jones i Selman wykazali, że zbiór jest widmem wtedy i tylko wtedy, gdy należy do klasy złożoności NEXP .

Jednym z kierunków dowodu jest pokazanie, że dla każdej formuły pierwszego rzędu problem ustalenia, czy istnieje model wzoru na liczność n , jest równoważny problemowi spełnienia wzoru $\ displaystyle \ varphi}$ wielkości φ { wielomian w n , który jest w NP(n), a więc w NEXP wejścia do problemu (liczby n w postaci binarnej, która jest łańcuchem o rozmiarze log( n )).

Odbywa się to poprzez zastąpienie każdego kwantyfikatora egzystencjalnego w dysjunkcji na wszystkich $.$ modelu i zastąpienie każdego kwantyfikatora uniwersalnego koniunkcją na wszystkich elementach modelu Teraz każdy predykat dotyczy elementów w modelu, a ostatecznie każde pojawienie się predykatu na określonych elementach jest zastępowane nową zmienną zdaniową. Równości są zastępowane ich wartościami logicznymi zgodnie z ich przypisaniami.

Na przykład:

${\ Displaystyle \ forall {x} \ forall {y} \ lewo (P (x) \ klin P (y) \ prawo) \rightarrow (x=y)}$

Dla modelu o liczności 2 (tj. n = 2) zastępuje się przez

${\ Displaystyle {\ duży (} \ lewo (P (a_ {1}) \ klin P (a_ {1}) \ prawo) \ strzałka w prawo (a_ {1} = a_ {1}) {\ duży)} \ klin {\big (}\left(P(a_{1})\klin P(a_{2})\right)\rightarrow (a_{1}=a_{2}){\big )}\klin {\big (}\left(P(a_{2})\klin P(a_{1})\right)\rightarrow (a_{2}=a_{1}){\big )}\klin {\big (}\ left(P(a_{2})\klin P(a_{2})\right)\rightarrow (a_{2}=a_{2}){\big )}}$

Które jest następnie zastępowane przez ${\ Displaystyle {\ duży (} \ lewo (p_ {1} \ klin p_ {1} \ prawo) \ strzałka w prawo \ top {\ duży)} \ klin {\ duży (} \ lewo (p_ {1} \ klin p_ {2}\right)\rightarrow \bot {\big )}\wedge {\big (}\left(p_{2}\wedge p_{1}\right)\rightarrow \bot {\big )}\klin { \big (}\left(p_{2}\klin p_{2}\right)\rightarrow \top {\big )}}$

gdzie ${\ displaystyle \ top}$$\ displaystyle$$prawdą$ , $\ bot}$ jest fałszem i zmiennymi zdaniowymi $przypadku$ ostatnia formuła zadowalające

Innym kierunkiem dowodu jest pokazanie, że dla każdego zestawu ciągów binarnych akceptowanych przez niedeterministyczną maszynę Turinga działającą w czasie wykładniczym ( dla długości wejściowej x) istnieje 2 do x { $^ {cx}}$$taka$ pierwszego rzędu , że ​​​​zbiór liczb reprezentowanych przez te ciągi binarne to widmo ${\ displaystyle \ varphi}$ .

Jones i Selman wspominają, że widmo formuł pierwszego rzędu bez równości jest po prostu zbiorem wszystkich liczb naturalnych nie mniejszych niż pewna minimalna liczność.

Inne właściwości

Zbiór widm teorii jest zamknięty na sumę , przecięcie , dodawanie i mnożenie. W pełnej ogólności nie wiadomo, czy zbiór widm teorii jest domknięty przez dopełnienie; jest to tak zwany problem Assera.

Zobacz też

• Spektrum teorii

•   Fagin, Ronald (1974). „Uogólnione widma pierwszego rzędu i zestawy rozpoznawalne w czasie wielomianu” (PDF) . W Karp, Richard M. (red.). Złożoność obliczeń . proc. Syp. Aplikacja. Matematyka Postępowanie SIAM-AMS. Tom. 7. s. 27–41. Zbl 0303.68035 .
•    Gradel, Erich; Kolaitis, Phokion G.; Libkin, Leonid ; Maarten, Marks; Spencer, Joel ; Vardi, Mosze Y .; Venema, Yde; Weinstein, Scott (2007). Teoria modeli skończonych i jej zastosowania . Teksty z informatyki teoretycznej . Seria EATCS. Berlin: Springer-Verlag . doi : 10.1007/3-540-68804-8 . ISBN 978-3-540-00428-8 . Zbl 1133.03001 .
•    Immerman, Neil (1999). Złożoność opisowa . Absolwent Teksty z informatyki. Nowy Jork: Springer-Verlag. s. 113 –119. ISBN 0-387-98600-6 . Zbl 0918.68031 .
• Durand, Arnaud; Jones, Neil; Markowski, Johann; Więcej, Malika (2012). „Pięćdziesiąt lat problemu widma: ankieta i nowe wyniki”. Biuletyn logiki symbolicznej . 18 (4): 505–553. ar Xiv : 0907.5495 . Bibcode : 2009arXiv0907.5495D . doi : 10.2178/bsl.1804020 .