Definability of eventually periodic

Question

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.

Answer 1

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.