# Section 2.2: Problem 16 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

Give a sentence having models of size
for every positive integer
, but no finite models of odd size. (Here the language should include equality and will have whatever parameters you choose.)

*Suggestion*: One method is to make a sentence that says, “Everything is either red or blue, and is a color-reversing permutation.”*Remark*: Given a sentence , it might have some finite models (i.e., models with finite universes). Define the

*spectrum*of to be the set of positive integers such that has a model of size . This exercise shows that the set of even numbers is a spectrum.

For example if
is the conjunction of the field axioms (there are only finitely many, so we can take their conjunction), then its spectrum is the set of powers of primes. This fact is proved in any course on finite fields. The spectrum of
, by contrast, is the set of all positive integers (non-fields come in all sizes). Günter Asser in 1955 raised the question: Is the complement of every spectrum a spectrum? Once you realize that simply taking a negation does not work (cf. the preceding paragraph), you see that this is a nontrivial question. In fact the problem, known as the spectrum problem, is still open. But modern work has tied it to another open problem, whether or not co-NP = NP.

Consider the following language:
where
and
are
-place functions. Then the following sentence has a model of every even positive integer size but no finite models of any odd size.

We first ensure that there are two distinct points
and
, and
assigns either
or
to every point. Essentially, whatever is
, we partition
into two disjoint subsets
and
of those points that are assigned
and
, respectively. Then, we say that
maps every point
in
to a point in
, and vice versa. Finally, we say that
is injective. For finite sets
and
this implies that
and
, or, equivalently,
and
have the same number of elements.