List out all the definable set in given model

Question

The problem says:

List all the definable subsets of $\mathbb R^2$ in ($\mathbb R$,<) with formulas.

And I found $x<y$, $y<x$ and $x=y$ are desired one. But, I want to say that any subset which could made up by them is also definable. For example, less than or equal to is also desired one, but I want to say that not just it is definable but it is definable since it is made by $x<y$, $y<x$ and $x=y$. I intuitively think that there're many definable sets like $\leq $ above. So, my question is that:

How can I express all of such definable sets by $x<y$, $y<x$ and $x=y$?

Answer 1

One way to do this is to note that the only thing that matters to whether some sequence of elements satisfies a formula over $(\mathbb R,<)$ is how the elements stand to each other with respect to $<$ and $=$. A little more precisely,

• if $(\mathbb R, <)\models \phi (a_1,\ldots,a_k)$ and if $((b_1,\ldots,b_k),<)$ is isomorphic to $((a_1,\ldots,a_k),<)$, then $(\mathbb R,<)\models \phi(b_1,\ldots,b_k)$.

This is routine to show by induction on formulas.

It follows that the relations definable over $(\mathbb R,<)$ are just those $R$ such that...

1. if $(a,a)\in R$ then $(b,b)\in R$ for all $b\in \mathbb R$
2. if $(a,b)\in R$ with $a<b$ then $(c,d)\in R$ for all $c,d\in \mathbb R$ such that $c<d$
3. if $(a,b)\in R$ with $a>b$ then $(c,d)\in R$ for all $c,d\in \mathbb R$ such that $c>d$.

There are eight such relations: $=$, $\neq$, $<$, $>$, $\leq$, $\geq$, $\mathbb R\times \mathbb R$, and $\emptyset$.