2
$\begingroup$

Let ψ be a first order formula. Wikipedia defines the spectrum of the formula ψ as follows: The spectrum of ψ is the set of natural numbers n such that there is a finite model for ψ with n elements.

In this wikipedia article, it says:

In full generality, it is not known if the set of spectra of a theory is closed by complementation, it is the so-called Asser's Problem.

So, there is talk of the spectrum of a theory, that is a set of formulas. Why is the spectrum previously only defined for a single formula instead of a whole set of formulas? Are the spectra of theories the same as the spectra of formulas? Is the spectrum problem for sets of formulas really open?


To improve this question, let me add some explanations:

Above I have given the definition of the spectrum of a first order sentence. One can also define the spectrum of a set $X$ of first order sentences: Let the spectrum of $X$ be the set of all cardinalities of finite structures that satisfy all the sentences in $S$.

Now I am wondering:

  • Given a set $X\subseteq \mathbb N_+$, is $X$ the spectrum of some first order sentence ψ if and only if $X$ is the spectrum of some set $S$ of first order formulas?

  • Let $S$ be a set of first order sentences. Is the spectrum of $S$ always decidable? (If we replace "set of first order formulas" by a single "first order formula" then the answer is yes, of course)

$\endgroup$
  • $\begingroup$ It seems like a logical extension to go to theories; the definition is the same. And why do you suppose it is not open? $\endgroup$ – Henno Brandsma May 1 '16 at 9:53
  • $\begingroup$ I don't know if it is open. That is why I ask. $\endgroup$ – ewuqify May 1 '16 at 10:08
  • $\begingroup$ I know that the spectrum problem for first order sentences is open. But one of my questions is, if the spectrum problem for sets of first order sentences is open. $\endgroup$ – ewuqify May 1 '16 at 10:26
1
$\begingroup$

The above definition of spectrum is not useful for theories. For given any subset $K$ of the natural numbers, there is a theory $T$ such that $T$ has a model of cardinality $n$ if and only if $n\in K$.

All we need to do it to produce, for every $n\not\in K$, a sentence that says "it is not the case that there are exactly $n$ objects." That can be done using just equality.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.