文のスペクトル

数理論理学では、文のスペクトルは、与えられた文が真となる有限モデルのサイズとして発生する自然数の集合である。記述的複雑さの結果として、自然数の集合がスペクトルとなるのは、非決定論的指数時間で認識できる場合のみである。

ψ を一階述語論理の文とする。ψのスペクトルは、n個の要素を持つψの有限モデルが存在するような自然数nの集合である。

ψの語彙が関係記号のみで構成されている場合、ψ は、関係と空の語彙に対して量化された存在第二階論理(ESOL)の文と見なすことができます。一般化スペクトルは、一般的な ESOL 文のモデルのセットです。

• この文は「多くても 個のものが存在する」ということを表しています。つまり、。${\displaystyle \psi _{n}\equiv \exists x_{1}\ldots \exists x_{n}\forall y(y=x_{1}\lor \ldots \lor y=x_{n})}$${\displaystyle n}$${\displaystyle {\text{Spec}}(\psi _{n})=\mathbb {N} _{\leq n}}$
• ${\displaystyle \neg \psi _{n}}$「物がたくさんある」ことを表します。つまり、。${\displaystyle n}$${\displaystyle {\text{Spec}}(\neg \psi _{n})=\mathbb {N} _{>n}}$
• ${\displaystyle \psi _{n}\land \neg \psi _{n-1}}$「まさに物事がある」と表現します。つまり、。${\displaystyle n}$${\displaystyle {\text{Spec}}(\psi _{n}\land \neg \psi _{n-1})=\{n\}}$
• 一次式のスペクトル

${\displaystyle \exists z,o~\forall a,b,c~\exists 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)}$

は、素数のべき乗の集合です。実際、に対して、 に対してを用いると、この文は体の集合を記述します。有限体の濃度は素数のべき乗です。 ${\displaystyle \{p^{n}\mid p{\text{ prime}},n\in \mathbb {N} \}}$${\displaystyle z}$${\displaystyle 0}$${\displaystyle o}$${\displaystyle 1}$

• モナドの 2 階論理式のスペクトルは、偶数の集合です。実際、は と の間の一対一であり、と は宇宙の分割です。したがって、宇宙の濃度は偶数です。${\displaystyle \exists 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\}}$${\displaystyle f}$${\displaystyle S}$${\displaystyle T}$${\displaystyle S}$${\displaystyle T}$
• 有限集合と余有限集合の集合は、後続関係を持つ一階述語論理のスペクトルの集合です。
• 究極的に周期的な集合の集合は、単項関数を持つモナド的二階論理のスペクトルの集合である。また、後続関数を持つモナド的二階論理のスペクトルの集合でもある。

フェイギンの定理は、記述的複雑性理論の結果であり、存在二階述語論理で表現可能なすべてのプロパティの集合は、まさに複雑性クラス NPであると述べています。これは、チューリングマシンなどの計算モデルを呼び出さないクラス NP の特徴付けであるため注目に値します。この定理は、1974 年にロナルド フェイギンによって証明されました(厳密には、1973 年の博士論文で)。

帰結として、ジョーンズとセルマンは、集合がスペクトルとなるのは、それが複雑性クラスNEXPに属する場合のみであることを示した。^[1]

証明の1つの方向は、すべての1階論理式に対して、濃度nの論理式のモデルが存在するかどうかを判断する問題が、 n内のサイズ多項式の論理式を満たす問題と同等であることを示すことです。n内のサイズ多項式はNP(n)に属し、したがって問題への入力（サイズlog( n ) の文字列であるバイナリ形式の数n）のNEXPに属します。${\displaystyle \varphi}$

これは、モデル内のすべての要素にわたる論理和にすべての存在量指定子を置き換え、モデル内のすべての要素にわたる論理積にすべての全称量指定子を置き換えることによって行われます。これで、すべての述語がモデル内の要素に存在し、最終的に、特定の要素に対する述語のすべての出現が新しい命題変数に置き換えられます。等式は、割り当てに従って真理値に置き換えられます。 ${\displaystyle \varphi}$

例えば：

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

濃度2（つまりn = 2）のモデルは次のように置き換えられます。

${\displaystyle {\big (}\left(P(a_{1})\wedge P(a_{1})\right)\rightarrow (a_{1}=a_{1}){\big )}\wedge {\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 )}}$

これを次のように置き換える。 ${\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 )}}$

ここで、は真、は偽、 は命題変数です。この特定のケースでは、最後の式は と同等であり、これは満たされます。 ${\displaystyle \top }$${\displaystyle \bot }$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle \neg (p_{1}\wedge p_{2})}$

証明のもう1つの方向は、指数時間（入力長xに対して）で実行される非決定性チューリングマシンによって受け入れられるバイナリ文字列のすべてのセットに対して、これらのバイナリ文字列によって表される数値の集合が のスペクトルとなるような一次式が存在することを示すことです。 ${\displaystyle 2^{cx}}$${\displaystyle \varphi }$${\displaystyle \varphi }$

ジョーンズとセルマンは、等式のない一階公式のスペクトルは、ある最小の基数よりも小さくないすべての自然数の集合にすぎないと述べています。

理論のスペクトルの集合は、和、積、加法、乗法の下で閉じている。一般に、理論のスペクトルの集合が相補性の下で閉じているかどうかは不明である。これはいわゆるアッサーの問題である。ジョーンズとセルマンの結果によれば、これは NEXPTIME = co-NEXPTIME であるかどうか、つまり NEXPTIME が相補性の下で閉じているかどうかという問題と同等である。^[2]

• 理論のスペクトル
• 計量定量化

• Fagin, Ronald (1974)。「一般化された 1 次スペクトルと多項式時間認識可能セット」(PDF)。Karp , Richard M. (編)。計算の複雑性。Proc. Syp. App. Math. SIAM-AMS Proceedings。第 7 巻。pp. 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).有限モデル理論とその応用。理論計算機科学テキスト。EATCS シリーズ。ベルリン: Springer-Verlag。doi : 10.1007 /3-540-68804-8。ISBN 978-3-540-00428-8.ZBL1133.03001  。​
• イマーマン、ニール（1999）。記述的複雑性。コンピュータサイエンスの大学院テキスト。ニューヨーク：シュプリンガー出版社。pp. 113–119。ISBN 0-387-98600-6.ZBL 0918.68031  .
• Durand, Arnaud; Jones, Neil; Markowsky, Johann; More, Malika (2012). 「スペクトル問題の 50 年: 概観と新しい結果」. Bulletin of Symbolic Logic . 18 (4): 505–553. arXiv : 0907.5495 . Bibcode :2009arXiv0907.5495D. doi :10.2178/bsl.1804020. S2CID  9507429.