Espectro de una oración

En lógica matemática , el espectro de una oración es el conjunto de números naturales que ocurren como el tamaño de un modelo finito en el que una oración dada es verdadera.

Sea ψ una oración en lógica de primer orden . El espectro de ψ es el conjunto de números naturales n tales que existe un modelo finito para ψ con n elementos.

Si el vocabulario para ψ consiste solo en símbolos relacionales, entonces ψ puede considerarse como una oración en lógica existencial de segundo orden (ESOL) cuantificada sobre las relaciones, sobre el vocabulario vacío. Un espectro generalizado es el conjunto de modelos de una oración general de ESOL.

$\existe z,o~\forall a,b,c~\existe d,e$

es decir , el conjunto de potencias de un número primo . De hecho, con for y for , esta oración describe el conjunto de campos ; la cardinalidad de un campo finito es la potencia de un número primo. $\{p^{n}\mid p{\text{prime}},n\in \mathbb {N} \}$ ${\ estilo de visualización z}$ ${\ estilo de visualización 0}$ ${\ estilo de visualización o}$ ${\ estilo de visualización 1}$

El teorema de Fagin es un resultado de la teoría descriptiva de la complejidad que establece que el conjunto de todas las propiedades expresables en la lógica existencial de segundo orden es precisamente la clase de complejidad NP . Es notable ya que es una caracterización de la clase NP que no invoca un modelo de computación como una máquina de Turing . El teorema fue demostrado por Ronald Fagin en 1974 (estrictamente, en 1973 en su tesis doctoral).