How to show the relation $<$ is not definable in $(\Bbb N; 0, \operatorname {S})$ by quantifier elimination?

Question

Show that the ordering relation $\{(m, n)| m < n \in \Bbb N\}$ is not definable in $\mathfrak{N}_{s}$. Suggestion: It suffices to show there is no quantifier-free definition of ordering. Call a relation $R \subseteq \Bbb N × \Bbb N$ linear if it can be covered by a finite number of lines. Call $R$ colinear if it is the complement of a linear relation. Show that any relation definable in $\mathfrak{N}_{s}$ is either linear or colinear. And that the ordering relation is neither linear nor colinear.

This is an exercise on page 193, A Mathematical Introduction to Logic, Herbert B. Enderton（2ed). $\mathfrak{N}_{s} = (\Bbb N; 0, \operatorname {S})$, $\operatorname {S}$ is the successor function.

I can't understand what the suggestion really mean. It seems to be related to a previous exercise about showing that a definable subset of $\mathfrak{N}_{s}$ is either finite or cofinite in $\Bbb N$.

Added: Thank Asaf Karagila for pointing out Arthur Fischer's answer on exactly the same question which I'm not aware of beforehand. But the approach suggested in this exercise and Arthur's are not the same. I want to know how to show this according to the suggested approach, i.e. the quantifier elimination approach.

Answer 1

Note that the binary relations on $\mathbb{N}$ definable in $\mathfrak{N}_s$ without quantifiers are boolean combinations of relations of the form $$s = t; \quad s \neq t$$ where $s$ and $t$ are terms. Note, also, that such $s$ and $t$ can contain at most one variable, so there are essentially 4 basic positive forms:

1. $S^{(n)} 0 = S^{(m)} 0$ (which is empty if $n \neq m$, and full if $n = m$);
2. $S^{(n)} x = S^{(m)} 0$ (which is empty if $n > m$, and a the line $x = (m-n)$ otherwise);
3. $S^{(n)} x = S^{(m)} x$ (which is empty if $n \neq m$, and full if $n = m$);
4. $S^{(n)} x = S^{(m)} y$ (which is the line $x = y + (m-n)$ or $y = x + (n-m)$);

As the class $\mathcal{L}$ of binary relations on $\mathbb{N}$ which are either linear or co-linear is clearly closed under complements, to show that $\mathcal{L}$ is closed under boolean operations it suffices to show that if $R , S$ belong to $\mathcal{L}$, then so does $R \cup S$.

• If $R$ and $S$ are both linear, then clearly $R \cup S$ is linear (the finitely many linear that cover $R$ together with the finitely many lines that cover $S$ will cover $R \cup S$).
• If either $R$ or $S$ is co-linear, then $R \cup S$ is also co-linear ($\mathord{\sim} ( R \cup S ) = \mathord{\sim} R \cap\mathord{\sim} S$ is a sub-relation of a linear relation, and is thus linear).

Therefore $\mathcal{L}$ is closed under boolean operations. As each of the four basic (positive) forms above belongs to $\mathcal{L}$, it follows that every binary relation on $\mathbb{N}$ definable in $\mathfrak{N}_s$ (without quantifiers) belongs to $\mathcal{L}$.

---

Showing that $<$ is neither linear nor co-linear is a basic proof by contradiction. If it were linear, then take $n$ many lines $L_1 , \ldots , L_n$ which cover it. Find an $m > n+1$ such that no $L_i$ is the horizontal line $y = m$. Note that each $L_i$ can intersect the section $\{ ( \ell , m ) : \ell < m \}$ of $<$ in at most one place, so there must be a point of this section uncovered. Showing $<$ is not co-linear is similar.

Answer 2

Hint: a projection of a definable set is definable.