Spektrum věty - Spectrum of a sentence - Wikipedia

v matematická logika, spektrum věty je soubor z přirozená čísla vyskytující se jako velikost a konečný model ve kterém daný věta je pravda.

Definice

Nechat ψ být větou v logika prvního řádu. The spektrum z ψ je množina přirozených čísel n tak, že existuje konečný model pro ψ s n elementy.

Pokud je slovník pro ψ skládá se tedy pouze z relačních symbolů ψ lze považovat za větu v existenciální logika druhého řádu (ESOL) vyčísleno nad vztahy, nad prázdnou slovní zásobou. A zobecněné spektrum je sada modelů obecné věty ESOL.

Příklady

• Spektrum vzorce prvního řádu

${ displaystyle existuje z, o ~ forall a, b, c ~ existuje d, e}$

${ Displaystyle a + z = a = z + a ~ land ~ a cdot z = z = z cdot a ~ land ~ a + d = z}$

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

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

je ${ displaystyle {p ^ {n} mid p { text {prime}}, n in mathbb {N} }}$, soubor pravomocí a prvočíslo. Opravdu, s ${ displaystyle z}$ pro ${ displaystyle 0}$ a ${ displaystyle o}$ pro ${ displaystyle 1}$, tato věta popisuje množinu pole; the mohutnost a konečné pole je síla prvočísla.

• Spektrum monadické logické formule druhého řádu ${ displaystyle existuje S, T ~ forall x ~ left {x in S iff x not in T land ~ f (f (x)) = x land ~ x v S iff f (x) v T vpravo }}$ je sada dokonce čísla. Vskutku, ${ displaystyle f}$ je bijekce mezi ${ displaystyle S}$ a ${ displaystyle T}$, a ${ displaystyle S}$ a ${ displaystyle T}$ jsou částí vesmíru. Proto je mohutnost vesmíru rovnoměrná.
• Sada konečné a co-konečné sady je množina spekter logiky prvního řádu s relací nástupce.
• Sada nakonec periodických množin je množina spekter monadické logiky druhého řádu s unární funkcí. Je to také soubor spekter monadické logiky druhého řádu s následnickou funkcí.

Vlastnosti

Faginova věta je výsledkem v teorie popisné složitosti který uvádí, že množina všech vlastností vyjádřitelných v existenciálním logika druhého řádu je přesně to třída složitosti NP. Je pozoruhodné, protože jde o charakterizaci třídy NP, která nevyvolává model výpočtu, jako je a Turingův stroj. Věta byla prokázána Ronald Fagin v roce 1974 (přísně v roce 1973 ve své disertační práci).

Rovnocennost s Turingovými stroji

Jako důsledek Jones a Selman ukázali, že množina je spektrum právě tehdy, pokud je ve třídě složitosti NEXP.^[1]

Jedním ze směrů důkazu je ukázat, že pro každý vzorec prvního řádu ${ displaystyle varphi}$, problém určení, zda existuje model vzorce mohutnost n je ekvivalentní s problém splnění vzorce polynomu velikosti v n, který je v NP (n) a tedy v NEXP vstupu problému (číslo n v binární formě, což je řetězec velikosti log (n)).

To se provádí nahrazením každého existenční kvantifikátor v ${ displaystyle varphi}$ s disjunkce přes všechny prvky v modelu a nahradí všechny univerzální kvantifikátor s spojení přes všechny prvky v modelu. Nyní je každý predikát na prvcích v modelu a nakonec je každý vzhled predikátu na konkrétních prvcích nahrazen novou výrokovou proměnnou. Rovnosti jsou nahrazeny jejich pravdivostními hodnotami podle jejich přiřazení.

Například:

${ displaystyle forall {x} forall {y} left (P (x) wedge P (y) right) rightarrow (x = y)}$

Pro model mohutnosti 2 (tj. n= 2) se nahrazuje

${ displaystyle { big (} left (P (a_ {1}) klín P (a_ {1}) right) rightarrow (a_ {1} = a_ {1}) { big)} klín { big (} left (P (a_ {1}) wedge P (a_ {2}) right) rightarrow (a_ {1} = a_ {2}) { big)} wedge { big (} left (P (a_ {2}) wedge P (a_ {1}) right) rightarrow (a_ {2} = a_ {1}) { big)} wedge { big (} left (P (a_ {2}) wedge P (a_ {2}) right) rightarrow (a_ {2} = a_ {2}) { big)}}$

Který je poté nahrazen${ displaystyle { big (} left (p_ {1} wedge p_ {1} right) rightarrow top { big)} wedge { big (} left (p_ {1} wedge p_ {2} right) rightarrow bot { big)} wedge { big (} left (p_ {2} wedge p_ {1} right) rightarrow bot { big)} wedge { big (} left (p_ {2} wedge p_ {2} right) rightarrow top { big)}}$

kde ${ displaystyle top}$ je pravda, ${ displaystyle bot}$ je faleš a ${ displaystyle p_ {1}}$, ${ displaystyle p_ {2}}$ jsou výrokové proměnné. V tomto konkrétním případě je poslední vzorec ekvivalentní ${ displaystyle neg (p_ {1} klín p_ {2})}$, což je uspokojivé.

Druhým směrem důkazu je ukázat, že pro každou sadu binárních řetězců přijatých nedeterministickým Turingovým strojem běžícím v exponenciálním čase (${ displaystyle 2 ^ {cx}}$ pro vstupní délku x) existuje vzorec prvního řádu ${ displaystyle varphi}$ taková, že množina čísel představovaná těmito binárními řetězci je spektrum ${ displaystyle varphi}$.

Jones a Selman zmiňují, že spektrum vzorců prvního řádu bez rovnosti je jen množina všech přirozených čísel, která není menší než nějaká minimální mohutnost.

Další vlastnosti

Soubor spekter teorie je uzavřen pod svaz, průsečík, sčítání a násobení. Zcela obecně není známo, zda je soubor spekter teorie uzavřen komplementací; toto je takzvaný Asserův problém.

Viz také

• Spektrum teorie

Reference

• Fagin, Ronald (1974). „Zobecněná spektra prvního řádu a rozpoznatelné polynomiální časy“ (PDF). v Karp, Richard M. (vyd.). Složitost výpočtu. Proc. Syp. Aplikace. Matematika. Řízení SIAM-AMS. 7. 27–41. Zbl  0303.68035.
• Grädel, Erich; Kolaitis, Phokion G .; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Teorie konečných modelů a její aplikace. Texty v teoretické informatice. Řada EATCS. Berlín: Springer-Verlag. doi:10.1007/3-540-68804-8. ISBN  978-3-540-00428-8. Zbl  1133.03001.
• Immerman, Neil (1999). Popisná složitost. Postgraduální texty v informatice. New York: Springer-Verlag. str.113 –119. ISBN  0-387-98600-6. Zbl  0918.68031.
• Durand, Arnaud; Jones, Neil; Markowsky, Johann; More, Malika (2012). „Padesát let problému spektra: průzkum a nové výsledky“. Bulletin of Symbolic Logic. 18 (4): 505–553. arXiv:0907.5495. Bibcode:2009arXiv0907.5495D. doi:10,2178 / bsl.1804020.

Charakteristický