Definable subsets of the natural numbers using only the successor function

Question

Consider the first-order language whose only nonlogical symbol is the unary function symbol $S$, and the structure $\mathfrak{N} = ( \mathbb{N} , S )$, where $S$ denotes the successor function. Why must a definable subset of $\mathbb{N}$ (in this language) be either finite or have finite complement?

Answer 1

You can use quantifier elimination: By induction on the quantifier depth, you can show that every first-order formula over the language $\{0,S\}$ is equivalent in $\mathbb N$ to a quantifier-free formula whose atoms all have one of the forms

• $x<\bar n$ for some numeral $\bar n$
• $x<y+\bar n$ for two different variables $x$ and $y$, and a numeral $\bar n$.

If you have a formula $\varphi(x)$ with only one free variable, this is consequently equivalent to some propositional combination of atoms of the first form (because the second one requires two different variables).

Now, every value for $x$ which is larger than the highest numeral in those atoms will give the same truth value for those atoms, and therefore for $\varphi(x)$ itself. Therefore either $\phi(x)$ is false for all sufficiently large $x$ (in which case the set is finite) or it is true for all sufficiently large $x$ (in which case it is cofinite).

---

If you add $+$ to your language, to get the language of Presburger arithmetic, all sets whose indicator functions are eventually periodic become definable.

If you add both $+$ and $\times$ you get the language of basic arithmetic, with a lifetime supply of definable sets, including every decidable (or recursively enumerable) set and the entire arithmetical hierarchy