Espectre d'una sentència

En llògica matemàtica, el espectre d'una oració és el conjunt de número natural que ocorren com el tamany d'un model finito en el que una sentència donada és verdadera.

Definició

Siga ψ una oració en la llògica de primer orde . El espectre de ψ és el conjunt d'número natural n tal que existix un model finito para ψ en n elements.

Si el vocabulari para ψ consistix solament en símbols relacionals, llavors ψ pot considerar-se com una oració en la llògica existencial de segon orde (ESOL) quantificada sobre les relacions, sobre el vocabulari buit. Un espectre generalisat és el conjunt de models d'una oració general de ESOL.

Eixemples

• L'espectre de la fòrmula de primer orde.

$\mathrm{\exists }z,o\mathrm{\forall }a,b,c\mathrm{\exists }d,e$

$a+z=a=z+a\wedge a\cdot z=z=z\cdot a\wedge a+d=z$

$\wedge a+b=b+a\wedge a\cdot (b+c)=a\cdot b+a\cdot c\wedge (a+b)+c=a+(b+c)$

$\wedge a\cdot o=a=o\cdot a\wedge a\cdot e=o\wedge (a\cdot b)\cdot c=a\cdot (b\cdot c)$

és $\{p^n\mid p\text{ prime},n\in \mathbb{N}\}$, el conjunt de potències d'un número primo. De fet, en $z$ per a $0$ i $o$ per a $1$, esta sentència descriu el conjunt de camps; La cardinalidad d'un camp finito és la potència d'un número primo.

• L'espectre de la fòrmula llògica monádica de segon orde $\mathrm{\exists }S,T\mathrm{\forall }x\{x\in S⟺x\in ̸T\wedge f(f(x))=x\wedge x\in S⟺f(x)\in T\}$ és el conjunt de números parells. En efecte, $f$ és una biyección entre $S$ i $T$ i $S$ i $T$ Són una partició de l'univers. Per lo tant, la cardinalidad de l'univers és parell.
• El conjunt de conjunts finitos i co-finitos és el conjunt d'espectres de llògica de primer orde en la relació successora.
• El conjunt de conjunts periòdics en última instància és el conjunt d'espectres de llògica monádica de segon orde en una funció unaria. També és el conjunt d'espectres de llògica monádica de segon orde en la funció successora.

Referències

• Fagin, Ronald (1974). «Generalized First-Order Spectra and Polynomial-Clave Recognisable Sets», Karp (ed.). Complexity of Computation, pp. 27–41.

• Grädel, Erich; Kolaitis, {{{nom2}}}; Libkin, Leonid; Maarten, {{{nom4}}} (2007). Finite model theory and its applications, Berlin: Springer-Verlag. doi:10.1007/3-540-68804-8. ISBN 978-3-540-00428-8. Grädel, Erich; Kolaitis, {{{nom2}}}; Libkin, Leonid; Maarten, {{{nom4}}} (2007). Finite model theory and its applications, Berlin: Springer-Verlag. doi:10.1007/3-540-68804-8. ISBN 978-3-540-00428-8. Grädel, Erich; Kolaitis, {{{nom2}}}; Libkin, Leonid; Maarten, {{{nom4}}} (2007). Finite model theory and its applications, Berlin: Springer-Verlag. doi:10.1007/3-540-68804-8. ISBN 978-3-540-00428-8.
• Immerman, Neil (1999). Descriptive Complexity, New York: Springer-Verlag, pp. 113–119. ISBN 0-387-98600-6. Immerman, Neil (1999). Descriptive Complexity, New York: Springer-Verlag, pp. 113–119. ISBN 0-387-98600-6. Immerman, Neil (1999). Descriptive Complexity, New York: Springer-Verlag, pp. 113–119. ISBN 0-387-98600-6.
• Bulletin of Symbolic Logic.18(4)

505–553.doi:10.2178/bsl.1804020.