6

On page 101, A Mathematical Introduction to Logic, Herbert B. Enderton（2ed),

What subsets of the real line $\mathbb R$ are definable in $(\mathbb R; <)$? What subsets of the plane $\mathbb R × \mathbb R$ are definable in $(\mathbb R; <)$? Remarks: The nice thing about $(\mathbb R; <)$ is that its automorphisms are exactly the order-preserving maps from R onto itself. But stop after the binary relations. There are $2^{13}$ definable ternary relations, so you do not want to catalog all of them.

Here's how far I understand. Any strictly increasing function forms an automorphism, so no singleton is definable in this structure. Thus we can't distinguish a set and a translation of it. So no subset is definable.

The definable relation of $(\mathbb R, <)$ I can think of are $<$, $>$ ,$=$, $\leq$, $\geq$ and the trivial one which is the whole set $\mathbb R × \mathbb R$. I can't figure out a way to exhaust it and to make sure of it.

The most obscure problem to me is in the last line of the remark. How can we get that exact number $2^{13}$?

Metta World Peace
  • 6,403

2 Answers2

9

It is not true that no subsets of $\mathbb R$ are definable; both of $\varnothing$ and $\mathbb R$ are. But those two are the only ones.

In the $\mathbb R^3$ case, the $2^{13}$ comes about because a definable subset must decide whether it includes $(a,b,c)$ based on which of the following cases it falls in:

  • $a=b=c$
  • $a < b=c$ and $a > b=c$ and similar -- two cases for each choice of which of the three operands is the "unequal" one, totaling $6$ cases.
  • $a < b < c$ and similar -- when all three numbers are different there are $3!=6$ cases depending on the ordering between the numbers.

That are $1+6+6=13$ cases all in all, so there are $2^{13}$ ways to select some, all or none of these cases to be included in the subset. For each such choice it is easy to write down a formula that picks out exactly the triples that fall under one of the chosen cases.

Similarly, in $\mathbb R^2$, there are $3$ cases for how two numbers can be related, namely $a=b$, $a<b$, and $a>b$. So there should be $2^3=8$ definable subsets of $\mathbb R^2$. You have given six -- can you find the two ones you're missing?

What is the rule for the exponents? We have $2^1, 2^3, 2^{13},\ldots$. Working the next exponent out by hand gives $1+8+6+36+24=75$ cases for $\mathbb R^4$, and then we have enough terms to look up 1,3,13,75 in OEIS and find that the sequence is A000670.

hmakholm left over Monica
  • 286,031
3

You missed two definable subsets of $\Bbb R$: the formulas $x=x$ and $x\ne x$ define $\Bbb R$ and $\varnothing$, respectively. These are the only ones, however.

Here’s a hint for the subsets of $\Bbb R\times\Bbb R$, which after all are just relations on $\Bbb R$. Start by considering the sets $E=\{\langle x,y\rangle\in\Bbb R^2:x=y\}$, $L=\{\langle x,y\rangle\in\Bbb R^2:x<y\}$, and $G=\{\langle x,y\rangle\in\Bbb R^2:y<x\}$, which you already have, and combine them in various ways. You’ve got two of the combinations; there are three more.

You may want to try to show that each of these three sets is preserved by order-isomorphisms of $\Bbb R$. With $L$, for instance, show that if $a<b$ and $c<d$, then there is an order-isomorphism $\varphi$ of $\Bbb R$ such that $\varphi(a)=c$ and $\varphi(b)=d$.

Added: I was going to add an explanation of the $2^{13}$, but I see now that Henning already has a nice detailed explanation.

Brian M. Scott
  • 616,228