Proof that intersection of two spectra is a spectrum.

239 Views Asked by At

Let $A$ be a sentence of the predicate calculus with identity. The spectrum of $A$ is the set of positive integers $n$ such that $A$ has a model of cardinality $n$. We shall call a spectrum a set $X$ of positive integers, such that $X = spectrum(A)$ for some $A$.

I want to show that if $X$ and $Y$ are spectra, then $X \cup Y$ and $X\cap Y$ are spectra.

Here http://www.math.psu.edu/simpson/ I have found the following proof:

Assume that $X$ is the spectrum of $A$ and $Y$ is the spectrum of $B$. Then $X \cup Y$ is the spectrum of $A \lor B$. Also, $X\cap Y$ is the spectrum of $A \land B$, provided A and B have no predicates in common except the identity predicate $^{(*)}$. To arrange for this, replace B by an analogous sentence in a different language.

My question is: why do we need the hypothesis $^{(*)}$?

1

There are 1 best solutions below

1
On BEST ANSWER

The point is that when they have no overlapping predicates, the way we put an $A$-satisfying structure on a set doesn't affect the way we can put a $B$-satisfying structure on the same set. If they overlap, though, you could get into a problem where $A$ and $B$ demand contradicting things.

For example, let the language for both $A$ and $B$ consist of a unary relation symbol $U$. Let $A$ be the sentence "$\forall x(U(x))$" and $B$ be the sentence "$\exists x(\neg U(x))$." Then:

  • $Spec(A)=\mathbb{N}$,

  • $Spec(B)=\mathbb{N}$, but

  • $Spec(A\wedge B)=\emptyset$.

More interesting examples are of course possible, but this one illustrates the point.