# Section 3.1: Problem 5 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

Show that the ordering relation
is not definable in
.

*Suggestion*: It suffices to show there is no quantifier-free definition of ordering. Call a relation*linear*if it can be covered by a finite number of lines. Call*colinear*if it is the complement of a linear relation. Show that any relation definable in is either linear or colinear. And that the ordering relation is neither linear nor colinear.
As suggested and noted on page 192, we use the fact that if a relation
is definable in
, then there is a quantifier-free formula
that defines it. In fact,
can be further assumed to be in its disjunctive normal form. Each atomic formula is of the form
, where
and
are either
,
or
. If
, then, if
, the atomic formula is always satisfied, otherwise, using axioms S2 and S4, the atomic formula is never satisfied. Thus, if
, the atomic formula defines either
or
. If
, then, suppose first, it contains
:
. If
, then, using axioms S2 and S1, we conclude that the atomic formula is never satisfied. If
, then, using axiom S2,
. 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
. Now, assume that the atomic formula does not contain
:
. Again, using S2, we conclude that under
the formula is equivalent to
or
or
. In
, all three equations define the line
(the equation is chosen depending on whether
). Overall, a proper subset of
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
(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
minus a finite union of lines. Now,
, 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
minus a finite union of lines, then the complement of the subset defined by
can be covered by these lines, otherwise, the subset defined by
is a finite union of subsets each covered by a finite number of lines. Overall, we have that every formula free in
and
defines a subset of
that is linear or colinear.

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