Proving the Fibonacci numbers, the odd numbers and other sets are spectra

Question

The first order language is assumed to contain only the identity predicate $I$, and potentially other predicates, but no operations and no constants.

My question is how to show that the following sets are spectra:

1. The set of even numbers and its complement (odd numbers).
2. The set of Fibonacci numbers $\{1,2,3,5,8,13,21,34,\ldots\}$, and its complement. Recall that the Fibonacci numbers are defined by $F_{1}=1$, $F_{2}=2$, $F_{n}=F_{n-1}+F_{n-2}$ for $n\geq 3$.
3. The set $\{x^{y}:x,y\geq 2\}$ and its complement.

For 1. I take a binary relation symbol $R$ and sentences $A$, $B$, and $C$ expressing $R$ is reflexive, symmetric and transitive, respectively. Then, let $D$ be the sentence $$\forall x\exists y((\neg Ixy)\wedge\forall z(Rxz\Leftrightarrow(Ixz\vee Iyz))).$$ The sentence $A\wedge B\wedge C\wedge D$ has spectrum the even numbers. Now, the sentence $A\wedge B\wedge C\wedge \neg D$ does not work to show that the odd numbers are a spectrum, but I believe that if we let $E$ be the sentence expressing that each equivalent class consists of exactly two elements, except for one equivalence class, which consists of exactly one element, then $A\wedge B\wedge C\wedge E$ has spectrum the odd numbers. My candidate for $E$ is $$\exists x(\forall y (Ixy\Leftrightarrow Rxy)\wedge(\neg(Ixy)\Leftrightarrow\exists z(\neg(Iyz)\wedge\neg(Ixz)\wedge\forall t(Ryt\Leftrightarrow (Iyt\vee Izt))))).$$

However, I am lost as to how to find appropriate sentences for 2. and 3.

Answer 1

Here's a solution to a close relative of $3$, namely $$\{x+y+x^y: x,y\ge 2\}.$$

The idea is that $x^y$ counts the number of functions from a set with $y$ elements to a set with $x$ elements.

We start with the language consisting of three unary predicates $X,Y,F$ and a ternary relation $A$. Our axioms say:

• $X,Y,F$ partition the domain, and $X$ and $Y$ each have at least two elements.

• $A\subseteq F\times Y\times X$. Intuitively, elements of $F$ represent functions from $Y$ to $X$, and $A(f,x,y)$ means $f(x)=y$.

• For all $f,y,x_1,x_2$, we have $A(f,y,x_1)\wedge A(f,y,x_2)\rightarrow x_1=x_2$; and similarly, each element of $F$ describes a total function from $Y$ to $X$.

Now a model of the theory so far amounts to a pair of sets $X,Y$ and some family of functions between them. We have to ensure that every function "appears in the $F$-part" - at least, as long as $X$ and $Y$ are finite (note that Lowenheim-Skolem implies that we can't do this for infinite $X$ and $Y$). We can do this via a cute trick:

Ensure that each constant function is "represented" in $F$, and then say that if $f$ is "represented" in $F$ and $g$ differs from $f$ in a single value then $g$ is "represented" in $F$ too.

Putting everything we have so far together we get a single sentence whose spectrum is the desired set. Now, do you see how to shift from "$x+y+x^y$" to the desired "$x^y$"? (HINT: let some elements of the structure "do double-duty.")

---

EDIT: note that the general strategy in the above was, "figure out a 'combinatorial story' that the set of numbers has, then tell it possibly with auxiliary sets, then if necessary 'fold in' those auxiliary sets appropriately." The same strategy, at least as I construe it, also describes Atticus' answer addressing your other question.

Answer 2

Edit: I've just seen that you're asking for the language to not contain function symbols. This actually does not change which sets are spectra; any $n$-ary function symbol $f(x_1,\dots,x_n)$ in a first-order language can be replaced by an $(n+1)$-ary relation symbol $F(x_1,\dots,x_n,y)$ by adding an axiom stating that, for every $x_1,\dots,x_n$, there is a unique $y$ such that $F(x_1,\dots,x_n,y)$ holds. Then in any model of that axiom $F$ will induce the desired $n$-ary function, and in any other axiom, you can replace instances of $f$ by suitable instance of $F$. This makes the notation a bit tedious however, so I will refrain from doing it below. Let me know if it is unclear to you how to turn my example below into one without function symbols.

---

Noah has given a nice solution for the first half of number $3$ (+1); let me give a solution for the first half of number $2$. First I'll make two observations. First, letting $F_i$ be the $i$-th Fibonacci number, then we have $F_{n+2}=2+\sum_{i=1}^nF_i$ for each $n>0$. (You can prove this by induction, for example.) Second, it suffices to show that the set $\{F_i:i\geqslant 4\}$ is a spectrum (can you see why?), which is what we'll do below. Finally, one other piece of terminology: given a partial order $<$ on a set $X$, I will say that an element $y\in X$ is a "$<$-successor" of an element $x\in X$ if $x<y$ and there does not exist $z$ such that $x<z<y$.

Alright, with these preliminaries out of the way, let's get started. We're going to work in a first-order language $L=\{<,f,g\}$, where $<$ is a binary relation symbol and $f,g$ are unary function symbols. Our first-order sentence will express the following:

1. $<$ is a strict partial order, and incomparability under $<$ gives an equivalence relation; from hereonout call this equivalence relation $E$.
2. $<$ respects $E$; in other words, if $E(x,y)$ holds, then for every $z$ we have $x<z$ iff $y<z$ and $x>z$ iff $y>z$. [Note that, by definition of $E$, this means that $<$ yields a well-defined strict total order on the equivalence classes of $E$, wherein the $E$-equivalence class of $x$ is smaller than the $E$-equivalence class of $y$ if and only if $x<y$.]
3. The first three classes of $E$ under $<$ have sizes $2$, $1$, and $2$, respectively, and every other class of $E$ has size greater than $2$.
4. $f,g$ act as the identity on the first equivalence class of size $2$, and $f$ acts as the identity on the equivalence class of size $1$.
5. $f,g$ are injections.
6. For every $x$ not in the first equivalence class of size $2$ or the equivalence class of size $1$, $f(x)$ is a $<$-successor of $x$. For every $x$ not in the first equivalence class of size $2$, $g(x)$ is a $<$-successor of a $<$-successor of $x$.
7. For every $y$, if the equivalence class of $y$ has size greater than $2$, then exactly one of the following holds: (i) $y$ lies in the image of $f$ and (ii) $y$ lies in the image of $g$.

Now, fix a finite model of the axioms above, and enumerate the $E$-equivalence classes in this model under the ordering $<$ as $X_0,X_1,\dots,X_k$. Then the axioms first tell us that$|X_0|=2$, $|X_1|=1$, and $|X_2|=2$. They then tell us that acting as $g$ on $X_i$ and acting as $f$ on $X_{i+1}$ gives a bijection $X_i\cup X_{i+1}\to X_{i+2}$ for each $0<i<k-2$, whence $|X_{i+2}|=|X_i|+|X_{i+1}|$. Hence $|X_i|=F_i$ for each $0<i\leqslant k$, and so, by the observations in the first paragraph, we are done.

Answer 3

For each given set $X$ in 2 and 3 we will give a sentence of the form $A\wedge B$ having spectrum precisely $X$, and so that the sentence $A\wedge\neg B$ has spectrum precisely the complement of $X$.

The idea is to consider the axioms for finite sets with addition, multiplication, a strict linear order, a smallest element with respect to the strict linear order, and with successors (e.g. think of positive integers modulo some $n$, in essence).

Consider the language $\mathcal{L}$ containing the following predicates (intuitive meaning to the right):

• $Ox: x=1$
• $Pxyz: x+y=z$
• $Qxyz: x\cdot y=z$
• $Rxy: x<y$
• $Sxy: x+1=y$
• $=$ (identity predicate)

Let $A'$ denote the conjunction of the following:

1. $\forall x\,\forall y\,(Rxy\vee Ryx\vee x=y)$
2. $\forall x\,\forall y\,(Rxy\Rightarrow\neg Ryx)$
3. $\forall x\,\forall y\,((Rxy\wedge Ryz)\Rightarrow Rxz)$

These three sentences say $R$ is a strict linear ordering.

4. $\forall x\,\forall z\,(Sxz\Leftrightarrow(Rxz\wedge\neg\exists y\,(Rxy\wedge Ryz)))$

This sentence says $S$ is the immediate successor predicate with respect to $R$.

5. $\forall u\,(Ou\Leftrightarrow\neg\exists x\,Rxu)$

This sentence says there is a smallest element with respect to $R$.

6. $\forall u\,(Ou\Rightarrow\forall x\,\forall z\,(Puxz\Leftrightarrow Sxz))$
7. $\forall v\,\forall w\,(Svw\Rightarrow\forall x\,\forall z\,(Pwxz\Leftrightarrow\exists y\,(Syz\wedge Pvxy)))$

These two sentences define the addition predicate $P$ in terms of $S$ by induction along $R$.

8. $\forall u\,(Ou\Rightarrow\forall x\,\forall z\,(Quxz\Leftrightarrow x=z))$
9. $\forall v\,\forall w\,(Svw\Rightarrow\forall x\,\forall z\,(Qwxz\Leftrightarrow\exists y\,(Qvxy\wedge Pxyz)))$

These two sentences define the multiplication predicate $Q$ in terms of $S$ and $P$ by induction along $R$.

A key feature of the $\mathcal{L}$-sentence $A'$ is that for any finite $\mathcal{L}$-structure $M$, then $M\vDash A'$ if and only if $M$ is isomorphic to $M_{n}$ for some $n$, where $M_{n}$ denotes the $\mathcal{L}$-structure $$M_{n}=(U_{n},O_{n},P_{n},Q_{n},R_{n},S_{n},I_{n}),$$ where

• $U_{n}=\{1,\ldots,n\}$
• $O_{n}=\{1\}$
• $P_{n}=\{(i,j,k)\in U_{n}^{3}:i+j=k\}$
• $Q_{n}=\{(i,j,k)\in U_{n}^{3}:i\cdot j=k\}$
• $R_{n}=\{(i,j)\in U_{n}^{2}:i<j\}$
• $S_{n}=\{(i,j)\in U_{n}^{2}:i+1=j\}$
• $I_{n}=\{(i,j)\in U_{n}^{2}:i=j\}$

Now, let us consider the set of Fibonacci numbers and its complement: Add a new unary predicate $F$ to the language $\mathcal{L}$, with $Fx$ intuitively meaning `$x$ is a Fibonacci number'. Then consider a sentence $A$ which is the conjunction of $A'$ with the following:

1. $\forall u\,(Ou\Rightarrow Fu)$
2. $\forall u\,\forall v\,(Ou\wedge Suv\Rightarrow Fv)$
3. $\forall v\,(((\neg Ov)\wedge(\neg\exists u\,Ou\wedge Suv))\Rightarrow(Fv\Leftrightarrow(\exists x\,\exists y\,(Fx\wedge Fy\wedge Rxy\wedge Pxyv\wedge\forall z\,((Rxz\wedge Rzy)\Rightarrow\neg Fz)))))$

These sentences define $F$ recursively.

Next, consider the sentence stating that the largest number in our domain is a Fibonacci number, i.e. $$B=\exists z\,((\neg\exists w\,Rzw)\wedge Fz).$$

The spectrum of $A\wedge B$ is precisely the set of Fibonacci numbers, and the spectrum of $A\wedge\neg B$ is precisely the complement of the set of Fibonacci numbers.

Finally, we consider the set $X=\{x^{y}:x,y\geq 2\}$ and its complement. We add a new ternary predicate $H$ to the original language $\mathcal{L}$, intuitively meaning $Hxyz: x^{y}=z$. We now define $A$ to be the conjunction of $A'$ with the following:

1. $\forall u\,(Ou\Rightarrow\forall x\,\forall z\,((Huxz\Leftrightarrow Oz)\wedge(Hxuz\Leftrightarrow x=z)))$
2. $\forall v\,\forall w\,(Svw\Rightarrow \forall x\,\forall z\,((Hxwz\Leftrightarrow\exists y\,(Hxvy\wedge Qyxz))\wedge(Hwxz\Leftrightarrow\exists y\,(Syz\wedge\exists t\,Qvty))))$

These sentences define exponentiation in terms of $S$ and $Q$ by induction along $R$.

Next, consider the sentence stating that the largest number in our domain is of the form $x^{y}$, with $x,y\geq 2$. $$B=\exists z\,((\neg\exists w\,Rzw)\wedge \exists x\,\exists y\,((\neg Ox)\wedge(\neg Oy)\wedge Hxyz)).$$

The spectrum of $A\wedge B$ is precisely the set $X$, and the spectrum of $A\wedge\neg B$ is precisely the complement of $X$.

---

For the set $Y=\{x+y+x^{y}:x,y\geq 2\}$ provided by Noah Schweber in his answer, the language $\mathcal{L}$ and the $\mathcal{L}$-sentence $A$ are the same as for the set $X$ above, and $B$ is the $\mathcal{L}$-sentence $$\exists z\,((\neg\exists w\,Rzw)\wedge \exists x\,\exists y\,\exists t\,\exists v((\neg Ox)\wedge(\neg Oy)\wedge Pxyt\wedge Hxyv\wedge Ptvz)).$$ The spectrum of $A\wedge B$ is $Y$ and the spectrum of $A\wedge\neg B$ is the complement of $Y$.