As suggested and noted on page 192, we use the fact that if a relation $R$ is definable in $\mathfrak{N}_{S}$ , then there is a quantifier-free formula $\phi$ that defines it. In fact, $\phi$ can be further assumed to be in its disjunctive normal form. Each atomic formula is of the form $\mathbb{S}^{m}t=\mathbb{S}^{n}u$ , where $t$ and $u$ are either $v_{1}$ , $v_{2}$ or $0$ . If $t=u$ , then, if $m=n$ , the atomic formula is always satisfied, otherwise, using axioms S2 and S4, the atomic formula is never satisfied. Thus, if $t=u$ , the atomic formula defines either $\emptyset$ or $\mathbb{N}\times\mathbb{N}$ . If $t\neq u$ , then, suppose first, it contains $0$ : $\mathbb{S}^{m}v_{i}=\mathbb{S}^{n}0$ . If $m>n$ , then, using axioms S2 and S1, we conclude that the atomic formula is never satisfied. If $m\le n$ , then, using axiom S2, $A_{S}\vDash\mathbb{S}^{m}v_{i}=\mathbb{S}^{n}0\leftrightarrow v_{i}=\mathbb{S}^{n-m}0$ . In the first case, the atomic formula defines the empty set, and in the second case, the atomic formula defines a vertical or horizontal line in $\mathbb{N}\times\mathbb{N}$ . Now, assume that the atomic formula does not contain $0$ : $\mathbb{S}^{m}v_{1}=\mathbb{S}^{n}v_{2}$ . Again, using S2, we conclude that under $A_{S}$ the formula is equivalent to $\mathbb{S}^{m-n}v_{1}=v_{2}$ or $v_{1}=v_{2}$ or $v_{1}=\mathbb{S}^{n-m}v_{2}$ . In $\mathbb{N}\times\mathbb{N}$ , all three equations define the line $v_{2}=v_{1}+m-n$ (the equation is chosen depending on whether $m\gtreqqless n$ ). Overall, a proper subset of $\mathbb{N}\times\mathbb{N}$ that can be defined by an atomic formula is a vertical, horizontal or diagonal line. Therefore, the negation of an atomic formula can define the complement of such a line. Each component of $\phi$ (the conjunction of atomic formulas or their negations) defines the intersection of the subsets defined by the atomic formulas or their negations. If the intersection is not empty, and there is at least one atomic formula defining a line, then the set defined by the component can be covered by this line, otherwise it is $\mathbb{N}\times\mathbb{N}$ minus a finite union of lines. Now, $\phi$ , as the disjunction of its components, defines a subset that is the union of the subsets defined by the components. If at least one component defines a subset that is $\mathbb{N}\times\mathbb{N}$ minus a finite union of lines, then the complement of the subset defined by $\phi$ can be covered by these lines, otherwise, the subset defined by $\phi$ is a finite union of subsets each covered by a finite number of lines. Overall, we have that every formula free in $v_{1}$ and $v_{2}$ defines a subset of $\mathbb{N}\times\mathbb{N}$ that is linear or colinear.

At the same time, the ordering relation $R$ is neither linear, nor colinear. Indeed, assume it is linear, and consider the first $n$ such that $v_{1}=n$ is not covered by a vertical line. But then there are infinitely many points $<v_{1},v_{2}>$ in $R$ such that $v_{1}=n$ , and only finitely many of them can be covered by a finite number of non-vertical lines. Similarly, if we assume that $R$ is colinear, then its complement is linear, but its complement defines the relation $m\ge n$ , and we can use the same argument to show that it cannot be covered by a finite number of lines.