Order-automorphisms of $\mathbb{Q}$

382 Views Asked by At

This is the exercise 7.22 of Classic set theory by Derek Goldrei. First I have to show that the set of order-automorphism of $\mathbb{Q}$ is infinite. After I have to find whether this set is equinumerous to $\mathbb{N}, 2^\mathbb{N}$ or $2^{2^\mathbb{N}}$.

For the first question I found that we just need to take an order-automorphism, say $f$, and multiply it by $\lambda \in \mathbb{Q}$. Knowing that $\mathbb{Q}$ is infinite thus $\{\lambda f | \lambda \in \mathbb{Q} \}$ is infinite and so is the set of order-automorphism.

For the second question I don't know how to proceed. The answer to the first one may help but I don't see how. Any help ?

2

There are 2 best solutions below

1
On BEST ANSWER

Let me start by saying that the following is almost assuredly not what Goldrei had in mind and that there's surely a simpler argument that someone else will come along and answer.


First, we show that $\text{Aut}(\mathbb Q,<)$ is uncountable, by a "forcing" argument (i.e. a repackaging of the back-and-forth method):

Let $P$ be the set of finite partial order preserving functions from $\mathbb Q$ to $\mathbb Q$. Order $P$ by reverse inclusion: $p\le q\iff p\supseteq q$.

Let $\{f_n:n\in\mathbb N\}\subset \text{Aut}(\mathbb Q,<)$. Define $$ D_n:=\{p\in P: p\not\subset f_n\} $$ Note that each $D_n$ is dense in $P$ (this means $\forall p\in P\exists q \in D_n (q\le p))$. To see this, fix $n$ and take $p\in P$. Pick a rational $x$ greater than every member of the domain of $p$ and another rational $y$ greater than every member of the domain of $p$ with $y\neq f_n(x)$. Then $q:=p\cup \{(x,y)\}$ is a partial order preserving function, $q\le p$, and $q\in D_n$ because $q(x)=y\neq f_n(x)$.

Also, let

$$ E_x:=\{p\in P: x\in \text{dom}(p)\} $$ and $$ E'_y:=\{p\in P: y\in \text{ran}(p)\} $$ for $x,y\in\mathbb Q$. Each $E_x$ and $E_y'$ is dense in $P$.

Let $$ \mathscr D:=\{D_n:n\in\mathbb N\}\cup\{E_x: x\in\mathbb Q\}\cup\{E_y':y\in\mathbb Q\} $$ Clearly, $\mathscr D$ is countable. By the Rasiowa-Sikorski Lemma, there is a filter $G\subset P$ which intersects every member of $\mathscr D$. Put $g:=\bigcup G$. Note that $g:\mathbb Q\to \mathbb Q$ (i.e. it is a total function), $g$ is order preserving, and $g$ is surjective. So, $g$ is an order automorphism of $\mathbb Q$. Additionally, $g\neq f_n$ for every $n\in\mathbb N$ by the choice of the $D_n$.

This shows that $\text{Aut}(\mathbb Q,<)$ is uncountable.

To argue that $\text{Aut}(\mathbb Q,<)$ has size continuum, fix a non-repeating enumeration $\{r_n:n\in\mathbb N\}$ of $\mathbb Q$. Consider the following subset of $\mathbb N^\mathbb N$:

$$ B:=\{f\in\mathbb N^\mathbb N:\forall n,m\in\mathbb N(r_n<r_m \to r_{f(n)}<r_{f(m)}\}\cap \{f\in\mathbb N^\mathbb N: \forall n\in\mathbb N\exists m\in\mathbb N (f(m)=n)\} $$

Note that $B$ is Borel with respect to the product topology $\mathbb N^\mathbb N$. Moreover, $B$ is equinumerous with $\text{Aut}(\mathbb Q,<)$, as witnessed by the map that sends $f\in B$ to the function $r_n\mapsto r_{f(n)}$.

By what we did above, $B$ is uncountable. Since $\mathbb N^\mathbb N$ is a Polish space and $B$ is Borel, $B$ must have size $2^{\aleph_0}$. Hence $|\text{Aut}(\mathbb Q,<)|=2^{\aleph_0}$.


Note that the $2^{2^\mathbb N}$ option can be excluded from the get go via some cardinal arithmetic: $|\mathbb Q|=\aleph_0$ and $\text{Aut}(\mathbb Q,<)\subset \mathbb Q^\mathbb Q$, so that $$ |\text{Aut}(\mathbb Q,<)|\le \aleph_0^{\aleph_0}\le\left(2^{\aleph_0}\right)^{\aleph_0}=2^{\aleph_0\aleph_0}=2^{\aleph_0}<2^{2^{\aleph_0}}. $$


Simpler argument: this is just a more detailed explanation of the very insightful comment left by Andreas Blass. We first need the following result:

Theorem (Cantor): Let $(D,<_D)$ be a linear order which is countable, dense, and has no end-points. Then $(D,<_D)\cong (\mathbb Q,<)$.

Using this theorem, we can argue as follows: fix $x\in\mathbb R\setminus\mathbb Q$. Define the "cuts"

$$L_x:=(-\infty,x)\cap \mathbb Q \\ R_x:=(x,\infty)\cap \mathbb Q$$

Note that both $R_x$ and $L_x$ are countable, linearly ordered, dense, and have no end-points. By Cantor's Theorem, $(L_x,<)$ is isomorphic to $(\mathbb Q,<)$ (so is $R_x$, but we don't need that). Pick a map $f_x: L_x\to L_x$ such that $f_x(r)\neq r$ for every $r\in L_x$. One way of seeing this is to appeal to the theorem: the property "There is an automorphism that fixes no point" is true of $(\mathbb Q,<)$ ($r\mapsto r+1$ being an example), hence it must be true of $L_x$ because the two structures are isomorphic.

Let $g_x:\mathbb Q\to\mathbb Q$ be defined by $$ g_x(r):=\begin{cases} f_x(r) & \text{if } r<x\\ r & \text{if } r>x \end{cases} $$

It is clear that $g_x$ is an order automorphism of $\mathbb Q$. Now, suppose $x,y$ are irrational and $x<y$. Fix $r\in\mathbb Q$ with $x<r<y$. Then $g_x(r)=r\neq g_y(r)$, so that $g_x \neq g_y$. Therefore, the map $$ \mathbb{R}\setminus \mathbb{Q}\to \text{Aut}(\mathbb Q,<)\\ x\mapsto g_x $$ is injective. But then

$$ 2^{\aleph_0}=|\mathbb R\setminus \mathbb Q|\le |\text{Aut}(\mathbb Q,<)|\le 2^{\aleph_0} $$ By the Cantor-Bernstein Theorem, $\text{Aut}(\mathbb Q,<)$ has size $2^{\aleph_0}$.

1
On

There is a more concrete way to show $|\operatorname{Aut}(\mathbb{Q},<)|\ge2^{\aleph_0}$, without relying on a back-and-forth argument: First, we claim that there are $2^{\aleph_0}$ many strictly increasing functions from $\mathbb{Z}$ to $\mathbb{Z}$. This is simple: for each real number $r\ge 1$, consider $f_r(n)=\lfloor rn\rfloor$.

Now extend $f_r$ to an increasing function from $\mathbb{Q}$ to $\mathbb{Q}$, by joining each $(n,f_r(n))$ to $(n+1,f_r(n+1))$ by line segment. The resulting function is piecewise linear and strictly increasing. It remains to show that the extended $f_r$ is onto, but it follows from that $\bigcup_{n\in\mathbb{Z}} [f_r(n),f_r(n+1)]=\mathbb{R}$.