Definable subsets of $\mathbb{Q}^2$ in $\langle \mathbb{Q} , < \rangle$?

Question

The question seems quite simple; what are the definable subsets of $\mathbb{Q}^2$ over the structure $\langle \mathbb{Q} , < \rangle$.

Part of me wants to say there are none, given any definable subset $S \subseteq \mathbb{Q}^2$ must be closed under automorphisms i.e if $(a,b) \in S$, $\pi$ an automorphism, then $\pi(a,b) = (\pi(a),\pi(b)) \in S$. However I can't find a way to compute such a map without also ruling out that $\mathbb{Q}^2$ is definable there.

Answer 1

Hint: to be asked this question, you must have met the fact that $(\mathbb{Q}, <)$ admits quantifier-elimination: i.e., every formula is equivalent to a quantifier-free formula. So every definable subset of $\mathbb{Q}^2$ belongs to the Boolean algebra generated by the sets defined by $x = y$, $x < y$ and $y < x$.

Answer 2

I'm going to say a bit about the parameter-free case; working with parameters is trickier, and it's good to try to figure out how to get there from here. Also, I'm going to avoid quantifier elimination because working with automorphisms is more fun. :P

---

Your argument about automorphisms is in the right direction, althought the argument itself doesn't work. As Carl points out, $\emptyset$ and $\mathbb{Q}^2$ are certainly definable. And there are two more trivial examples: the diagonal, $\Delta=\{(q, q): q\in\mathbb{Q}\}$, and the complement of the diagonal, $\overline{\Delta}$. But it doesn't even stop here: there are nontrivial definable subsets, like $\{(a, b): a<b\}$. So it's not going to be so easy!

But let's try to see how much we can rule out with automorphisms.

First, suppose $q\in\mathbb{Q}$; then the map $\pi_q: p\mapsto p+q$ is an automorphism of $\mathcal{Q}=(\mathbb{Q}, <)$, so if $D$ is a definable subset of $\mathcal{Q}^2$ we must have $\pi(D)=\{(\pi(p), \pi(q)): (p, q)\in D\}=D$.

Geometrically, this means that $D$ is a union of lines of slope 1. (Think about why.)

So we've ruled out a bunch of sets, but there's still a lot left; and certainly (since there are uncountable many unions of lines with slope 1) we haven't gotten rid of all the undefinable sets. So let's look for another class of automorphisms which will help kill off some bad sets.

In order to kill off more bad sets, our new automorphisms had better be quite different from the $\pi_q$s already considered. The obvious maps to look at are the multiplicative ones, in contrast with the additive nature of the $\pi_q$s: $$\rho_q: p\mapsto qp \quad \mbox{($q$ positive)}.$$

Now let's think about what these maps can do to a set $D\subseteq\mathbb{Q}^2$ which is a union of lines of slope 1. By applying an appropriate $\rho_q$ we can move the lines with slope 1 above the origin around however we like; and similarly with the lines of slope 1 below the origin.

I claim we're done!

• Figure out what sets this rules out;

• now show that all those sets are definable. (This will be much easier than it sounds.)