Undefinable subset of $(\mathbb{N}, <)$

Question

Could you help me to solve the following task:

Find a subset $X \subseteq \mathbb{N}$ which is not definable in $(\mathbb{N}, <)$.

For example, in $(\mathbb{N}, +)$, set of even number is definable by formula $\varphi(x) \equiv \exists y (x = y + y)$. Negation of this formula define set of odd numbers.

How to be sure that set of even numbers is not definable subset od $\mathbb{N}$ in $(\mathbb{N},<)$? If I suppose that the set of even numbers is definable with formula $\varphi(x)$, than $\neg \varphi(x)$ define set of odd numbers. I should make contradiction with something. I dan't know with what?

How to proove that some set is not definable in $(\mathbb{N},<)$? I don't know that procedure.

Thank you!

Answer 1

In a now-deleted answer, user1047209 indicated an alternative approach, based on showing that $(\mathbb{N},<)$ is a minimal structure: Every definable set in one variable is finite or cofinite. Although the answer was flawed, the approach is valid. $(\mathbb{N},<)$ is indeed a minimal structure, and it follows that the set of even numbers, like any infinite and coinfinite set, fails to be definable in this structure.

For each $n>0$, let $P_n$ be a binary relation symbol. We interpret $P_n$ on $\mathbb{N}$ so that $P_n(x,y)$ holds if and only if $x < y$ and there are exactly $n-1$ elements between $x$ and $y$. Now it is a fact that the complete theory of the structure $(\mathbb{N},<,0,(P_n)_{n>0})$ eliminates quantifiers.

I will show that $(\mathbb{N},<,0,(P_n)_{n>0})$ is a minimal structure. It follows immediately that $(\mathbb{N},<)$ is also minimal.

Let's enumerate the atomic formulas with parameters and a single free variable $x$. For each, I will indicate whether it is finite or cofinite.

• $x = x$ (cofinite - all of $\mathbb{N}$)
• $x = a$ (finite - a singleton)
• $a = x$ (finite - a singleton)
• $x < x$ (finite - empty)
• $x < a$ (finite)
• $a < x$ (cofinite)
• $P_n(x,x)$ (finite - empty)
• $P_n(x,a)$ (finite - at most one element)
• $P_n(a,x)$ (finite - a singleton)

Now an arbitrary formula with parameters and one free variable $x$ is equivalent to a boolean combination of the atomic formulas above, by quantifier elimination. And a boolean combination of finite and cofinite sets is finite or cofinite. So we're done.

Note that the non-trivial part of this answer is proving quantifier elimination in the language with the relation symbols $P_n$. Similarly, the nontrivial part of Primo Petri's answer is proving that $N$ is an elementary extension of $\mathbb{N}$. To answer a question like this, you usually can't avoid doing some nontrivial work to understand the definable sets.

Answer 2

At the moment the answer of @user1047209 is not correct.

My answer uses a less elementary method (therefore it would be great if @user1047209 could correct their proof).

I will prove that the set of even elements is not definable.

Consider the model $N={\mathbb N} \cup \big({\mathbb Q}\times{\mathbb Z}\big)$ with the following order: the elements of ${\mathbb N}$ preceed the elements of ${\mathbb Q}\times{\mathbb Z}$. The set ${\mathbb Q}\times{\mathbb Z}$ is ordered with the lexicographic order.

$N$ is a saturated elementary extension of ${\mathbb N}$. (This is not proved here. BTW saturation is not necessary for the argument).

Suppose for a contradiction that $\varphi(x)$ define the even number. Then ${\mathbb N}\models \forall x\ \ \varphi(x)\not\leftrightarrow\varphi(x+1)$, where $x+1$ denotes the successor of $x$. Thoughnot in the language, this is a definable function.

But $\forall x\ \ \varphi(x)\not\leftrightarrow\varphi(x+1)$ is not true in $N$. In fact, the map that is the identity on ${\mathbb N}$ and maps $\langle q,n\rangle$ to $\langle q,n+1\rangle$ is an automorphism of $N$.