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

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.

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.

• (to add to your comment at the bottom, I'd also argue that this fact makes the "complement" halves of OP's questions rather harder, since it's not immediately clear what the "combinatorial story" to not being of form $x^y$ or not being a fibonacci number is) Jul 3 at 2:55
• @AtticusStonestrom I posted an answer with a possible solution for both halves of my original question, as well as for both halves of the set in Noah Schweber's answer.
– John
Jul 10 at 19:54
• @John right on, that's a really nice construction! (+1) Jul 11 at 1:56
• @AtticusStonestrom Thank you! For the Fibonacci part, did I define the predicate $F$ correctly by recursion? Something seems off, and I am double checking it.
– John
Jul 11 at 2:25
• @AtticusStonestrom Thank you, yes. That is exactly what I am trying to say. I think I have tunnel vision. It was a challenging question for me, and I have been at this all weekend.
– John
Jul 11 at 2:31

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 and there does not exist $$z$$ such that $$x.

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 iff $$y 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.]
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, whence $$|X_{i+2}|=|X_i|+|X_{i+1}|$$. Hence $$|X_i|=F_i$$ for each $$0, and so, by the observations in the first paragraph, we are done.

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
• $$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.

1. $$\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$$.

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

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

1. $$\forall u\,(Ou\Rightarrow\forall x\,\forall z\,(Puxz\Leftrightarrow Sxz))$$
2. $$\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$$.

1. $$\forall u\,(Ou\Rightarrow\forall x\,\forall z\,(Quxz\Leftrightarrow x=z))$$
2. $$\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
• $$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$$.