Definability of eventually periodic

Let $$\Bbb{N}$$ the set of natural numbers including 0. A set $$X\subset \Bbb{N}$$ is called eventually periodic if there is a $$p\geq 1$$ and an $$n_0 \in \Bbb{N}$$ such that for all $$n \geq n_0$$ we have $$n \in X \leftrightarrow n + p \in X$$

Let $$\mathcal{L}=\{0,+,S\}$$ be a language where $$0$$ is a constant symbol, $$+$$ is a binary function symbol and $$S$$ is a unary function symbol. Consider the $$\mathcal{L}$$-structure $$(\Bbb{N},0,+,S)$$ where $$0$$ is the natural $$0$$, $$+$$ is addition and $$S$$ is the succesor function.

Prove that every eventually periodic set is definable in $$(\Bbb{N},0,+,S)$$.

I am having issues finding a formula that describes the eventually periodic sets, I have tried to define a recursive one but it makes no sense. Possible ideas would be appreciated.

• @AdamRubinson No, a formula in first order logic can only have variables, symbols of the language (in this case $0$, $+$ and $S$), logic simbols ($\land$, $\lor$, $\neg$ and $\rightarrow$) and quantifiers ($\forall$ and $\exists$). So, $\in$ and words can not be part of a formula. Jun 9 at 11:13
• @AdamRubinson The $x$ was wrong, it was a $n$, I edited it. Jun 9 at 11:16

For a fixed $$n \in \mathbb{N}$$ let $$[n]$$ denote $$S^n(0)$$, so that e.g. $$[2]$$ denotes $$S(S(0))$$. Let $$n \cdot x$$ denote $$x + x + \dots + x$$ where $$x$$ occurs $$n$$ times, so that e.g. $$3 \cdot x$$ denotes the term $$x + x + x$$.

Take an eventually periodic set $$X\subseteq \mathbb{N}$$ with corresponding fixed constants $$n_0$$ and $$p$$ so that for all $$n \geq n_0$$, $$n \in X \leftrightarrow n + p \in X$$.

We can write the set $$X$$ as a union of three sets:

1. $$X_i = \{n \in \mathbb{N} \:|\: n \in X \wedge n < n_0 \}$$
2. $$X_b = \{n \in \mathbb{N} \:|\: n \in X \wedge n < n_0 + p\}$$
3. $$X_p = \{n \in \mathbb{N} \:|\: n \in X \wedge n_0 + p \leq n\}$$.

We will show that each of these sets is definable.

First notice that the sets $$X_i$$ and $$X_b$$ are finite (they have no more than $$n_0 + p$$ elements), so one can define $$X_i$$ using the finite disjunction $$\varphi_i(x) \leftrightarrow \bigvee_{j < n_0,\\ j \in X_i} x = [j],$$ and one can define membership in $$X_b$$ using the finite disjunction $$\varphi_b(x) \leftrightarrow \bigvee_{j < n_0 + p,\\ j \in X_b} x = [j].$$

Finally, notice that by the eventual periodicity of $$X$$, $$n \in X_p$$ holds when one can find some $$n' \in X_b$$ and $$k \in \mathbb{N}$$ so that $$n' + p\cdot k = n$$. This means that we can define

$$\varphi_p(x) \leftrightarrow \exists n. \exists k. \varphi_b(n) \wedge x = n + p \cdot k$$

Since $$X = X_i \cup X_b \cup X_p$$, we can define $$X$$ using the formula

$$\varphi(x) \leftrightarrow \varphi_i(x) \vee \varphi_b(x) \vee \varphi_p(x).$$

This definition has some redundancy (for example $$\varphi_b(x) \rightarrow \varphi_p(x)$$ always holds by taking $$k = 0$$), but it gets the job done.