Formula for perfect squares spectrum.

Question

I have been working on exercises from "A first Course in Logic" by S. Hedman. Exercise 2.3 (d) asks to find a first-order sentence $\varphi$ having the set of perfect squares as a finite spectrum. But I am not sure whether or not my understanding of concepts of model and spectrum is correct.

My solution is:

$\varphi = (\exists x)((x^2 = b) \wedge (\forall y)(y\leq b))$, i.e., there is $x$ such that $x^2 = b$ and for all $y$, $y$ is less than or equal to a constant $b$. Hence, any set of positive integer numbers, with the maximal element that is a perfect square, models this sentence. For example, $\{1\}, \{1,2,3,4\}, \{1,\ldots, 9\}$ and so on.

Could someone confirm my solution (am I on the right track)? Or am I missing something?

Answer 1

Outline: We use a rather rich language based on the predicate calculus with equality, There are two unary predicate symbols, $P$, where $P(x)$ should be thought of as saying that $x$ is a point, and $E$, where $E(x)$ should be thought of as saying that $x$ is a (directed) edge. Then there is a ternary predicate symbol $S$, where $S(x,y,z)$ should be interpreted as meaning that $z$ is the edge going from $x$ to $y$. We now describe the axioms in informal language that should not be difficult, if one wishes, to turn into formal language.

$1.$ Everything is a point or an edge, and nothing can be both a point and an edge.

$2.$ $S(x,y,z)$ implies that $x$ and $y$ are points and $z$ is an edge.

$3.$ We can never have $S(x,x,z)$.

$4.$ For any $z$ there is a unique $x$ and $y$ such that $S(x,y,z)$.

$5.$ For any $x$ and $y$, with $x\ne y$, there is a unique $z$ such that $S(x,y,z)$.

Let $\varphi$ be the conjunction of the set of axioms described above.

Now let $M$ be a finite model of this set of axioms, and let $q$ be the cardinality of the set of elements of (the underlying set of) $M$ that satisfy (the interpretation of) the predicate symbol $P$. Then the number of elements of $M$ that satisfy $E$ is $q(q-1)$, so $M$ has cardinality $q+q(q-1)=q^2$. And it is clear that for every positive integer $q$ there is a model of cardinality $q^2$.

Answer 2

You can do this with the signature that has one unary relation $A(x)$ and one binary function $f(x,y)$. The sentence will say, essentially, that $f$ is a bijection between $A \times A$ and $M$.

It is much more difficult to do this sort of thing with the signature of arithmetic. You would need to include in $\phi$ several axioms about the addition and multiplication operations, the order relation, and how they are related. By comparison, the sentence obtained from the previous paragraph is relatively simple.

Remember that, for spectrum problems, you can choose any signature that you like. Choosing the right signature can make the problem much simpler.

Answer 3

The set of squares and its complement are spectra. Consider the language $\mathcal{L}$ (which contains only predicates and equality) and the $\mathcal{L}$-sentence $A'$ I define in this answer (you will also find how the predicates I use next are defined).

Now, let $B$ be the $\mathcal{L}$-sentence saying that a square is the largest element in our domain: $$\exists z\phantom{,}((\neg\exists\phantom{,} w Rzw)\wedge\exists x\phantom{,} Qxxz).$$

The set of squares is the spectrum of $A'\wedge B$, and its complement is the spectrum of $A'\wedge\neg B$.