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.