Are Spectrums Recursive?

Logic Level 4

Given a first order vocabulary σ\sigma and a sentence φ\varphi over σ\sigma, a subset MNM \subseteq \mathbb{N} of natural numbers is called the spectrum φ\varphi if for each nMn \in M, there is a model satisfying φ\varphi containing exactly nn elements.

For example, the spectrum of the following sentence is the set of even numbers.

x [S(x)    ¬T(x) f(f(x))=x S(x)    T(f(x))] \forall x ~ \left [S(x) \iff \neg T(x) \\ \land~ f(f(x))=x \\ \land~ S(x) \iff T(f(x))\right ]

A set MNM \subseteq \mathbb{N} is said to be recursive if given a natural nn, a Turing Machine can determine whether nMn \in M or n∉Mn \not \in M.

Which of the following are true?

×

Problem Loading...

Note Loading...

Set Loading...