- #1

- 14

- 0

## Homework Statement

What subsets of the real line R are definable in (R,<)? What subsets of the plane RxR are definable in (R,<)?

## Homework Equations

A subset is definable if there is a formula in first order logic that is true only of the elements of that subset. For example, in the Natural numbers N, {0} is definable in (N,<), because the formula \forall n(v_{1}<n) is true only if v_{1}=0.

If a subset is definable, then it is preserved under automorphisms.

## The Attempt at a Solution

The only two subsets of R which are definable are R itself and the empty set. For R, the formula v_{1}=v_{1} is true no matter what v_{1} is. For the empty set, the formula \lnot(v_{1}=v_{1}) is true of no number in R. For any subset S of R which is not R or the empty set, there is an automorphism which takes elements of S to elements not in S. Indeed, there is an p in S and a q not in S, since S is neither R nor the empty set. Let f(x)=x+(q-p). f is an automorphism, it is easy to check. Then, f(p)=q, so that f takes an element of S to an element not in S. Thus, S is not a definable set.

Now, for RxR, I'm confused about what it means for a subset of RxR to be definable in (R,<).