# Section 2.2: Problem 14 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

What subsets of the real line
are definable in
? What subsets of the plane
are definable in
?

*Remarks*: The nice thing about is that its automorphisms are exactly the order-preserving maps from onto itself. But stop after the binary relations. There are definable ternary relations, so you do not want to catalog all of them.

Intuitively,
defines the set of real numbers without specifying where either
or
is, i.e. we can neither say the origin nor the scale. Therefore, for a given set there is no way to say, for example, whether
belongs to it or not. Formally, we can use the corollary of the homomorphism theorem on page 98 to argue against some possibilities. Namely, suppose that
is a definable unary relation on
(a subset of
). If
then consider the automorphism
such that
. The corollary implies that if
is definable, then both
and
either belong to
or not. Since we have chosen
and
arbitrary, this implies that either all points of
are in
, or
is empty. Hence, the subsets of
that are definable in
are
and
(both subsets are indeed definable via, for example,
and
, correspondingly, and we have shown that there cannot be any other definable subsets). Note, that alternatively we could have said that there is one subset of
, namely,
, such that a)
is definable, and b) if any point of
is in
, then all points of
are in
, and to construct all possible definable subsets of
we either take this subset or we don’t, which gives as exactly
possibilities.

Intuitively, with
the situation is slightly different. We still cannot tell where
or any other point is, however, given a point
we at least can say whether
, or
, or
. Therefore, we at least can distinguish subsets having points
such that, say,
, and those that do not have such points. However, if we know that
and
, we still cannot say whether this point is, for example,
or any other point
satisfying
. Formally, we again use the corollary to argue against most of subsets. Consider two points
and
such that
. Then
is an automorphism as long as
and
have the same sign. Note that
and
. Therefore, according to the corollary, for any definable
, and
and
such that either
and
or
and
, either
or they both are not in
. Moreover, for two points
and
we can consider the automorphism
such that
, and as before argue that either both such points are in
or they both are not in
. Now we have three subsets
,
and
such that a) all these subsets are definable, and b) if any point of
is in
, so are all other points of
. This gives us exactly
definable subsets of
, namely, the empty set,
,
, their pairwise unions, and the whole plane
.

We can proceed this way further, even though the remark warns us against doing so. We can argue in a similar way, that if
is a definable
-ary relation on
, then for two points
and
such that for every
,
and
are either both zero or have the same sign, either both points are in
or they both are not in
. Therefore, we can distinguish several subsets
of
such that a)
is defined through specific relations among coordinates (such as
or
or
), b) if any point of
is in a definable relation
, so are all other points. Then, any definable
-ary relation on
is either empty or a union of some of these sets. And if there are
such sets, then we have
definable
-ary relations. The only question now is how we determine
. Let
be the number of possible combinations of relations among coordinates such that the coordinates form a set of
distinct values. For example,
as the only possibility here is when
,
as we have two cases
and
, and
as we can have
,
and 4 more possibilities, 2 when
, and 2 when
. Note that,
where
for all
(to produce
different values with
coordinates we can either take any combination of
coordinates with
distinct values and add the
th coordinate above all, below all, or between any two coordinates, or take any combination of
coordinates with
distinct values and add the
th coordinate by requiring it to be equal to one of those values). Now, the total number of possible combinations of relations among
coordinates is
. This recursive formula produces the following results.

Therefore, we have
definable unary relations,
definable binary relations,
definable ternary relations,
definable quaternary relations,
definable quinary relations etc.