« Section 2.2: Problem 13 Solution

Section 2.2: Problem 15 Solution »

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.