Bijection from $[0,1]\times [0,1]$ to $[0,1]$ that preserve the product order

535 Views Asked by At

I'm trying to prove that there exists a bijection $f:[0,1]\times [0,1]\longrightarrow [0,1]$ such that $(a,b)\leq_p(c,d)$ implies that $f((a,b))\leq f((c,d))$, where $\leq_p$ is the product order in $[0,1]\times [0,1]$ and $\leq$ is the usual order in $[0,1]$. In fact, I suspect that this function indeed exists, but I can't prove. I was trying something using Zorn's Lemma.

Obs: $(a,b)\leq_p (c,d)$ means $(a\leq c)\wedge (b\leq d)$.

2

There are 2 best solutions below

5
On

Lemma: There is an order isomorphism from $\mathbb{N}^{\mathbb{N}}$ (under the lexicographic ordering) to $[0, 1)$.

Proof: Define $f : \mathbb{N}^\mathbb{N} \to [0, 1)$ by $$f(n_1, n_2, n_3, \dots) = 1 - 2^{-n_1} - 2^{-n_1-n_2} - 2^{-n_1-n_2-n_3} - \cdots = 1 - \sum_{k \geq 1} 2^{-(n_1 + \cdots + n_k)}.$$ Equivalently, $f(n_1, n_2, n_3, \dots)$ is the number in $[0, 1)$ with binary expansion $0.x_1x_2x_3\dots$, where $x_{n_1}, x_{n_1+n_2}, x_{n_1+n_2+n_3}, \dots = 0$, and all other $x_j = 1$. To show $f$ is surjective, let $x \in [0, 1)$ have binary expansion $0.x_1x_2x_3\dots$, where there are infinitely many $x_j$ with $x_j = 0$ since the expansion does not end in an infinite string of $1$'s. Letting $a_1 < a_2 < a_3 < \cdots$ be the indices of the zeroes in the expansion, so $a_1$ is the smallest number with $x_{a_1} = 0$, $a_2$ is the second smallest, and so on, it immediately follows that $x = f(a_1, a_2 - a_1, a_3 - a_2, \dots)$.

To show $f$ is order-preserving, suppose $(n_1, n_2, \dots) > (n_1', n_2', \dots)$, so there is some unique $j$ with $n_i = n_i'$ for $i < j$ and $n_j > n_j'$. Then we have \begin{align*} f(n_1, n_2, \dots) - f(n_1', n_2', \dots) &= \sum_{k \geq j} 2^{-(n_1' + \cdots + n_k')} - \sum_{k \geq j} 2^{-(n_1 + \cdots + n_k)} \\ &> 2^{-(n_1' + \cdots + n_j')} - \sum_{k \geq j} 2^{-(n_1 + \cdots + n_k)} \\ &\geq 2^{-(n_1' + \cdots + n_j')} - 2^{-(n_1 + \cdots + n_j - 1)} \\ &\geq 0 \end{align*} where the first inequality holds because we are simply removing the rest of the first sum after the first term, and the rest of the sum is positive, the second inequality holds because the $k$-th term of the second sum has $2^{-(n_1 + \cdots + n_k)} \leq 2^{-(n_1 + \cdots + n_j + (k-j))}$, and the final inequality holds because $n_1' + \cdots + n_j' \leq n_1 + \cdots + n_j - 1$. It follows that $f$ is order-preserving, hence also injective, and thus $f$ is an order isomorphism since both $\mathbb{N}^{\mathbb{N}}$ and $[0, 1)$ are linearly ordered. [end of lemma.]

Now we'll use this lemma to find an order-preserving bijection from $[0, 1) \times [0, 1)$ to $[0, 1)$. First, similar to @mathworker21's answer, note that the map $g : \mathbb{N}^{\mathbb{N}} \times \mathbb{N}^{\mathbb{N}} \to \mathbb{N}^{\mathbb{N}}$ given by $$((a_1, a_2, \dots), (b_1, b_2, \dots)) \to (a_1, b_1, a_2, b_2, \dots)$$ is an order-preserving bijection, where again each $\mathbb{N}^\mathbb{N}$ has the lexicographic ordering and $\mathbb{N}^{\mathbb{N}} \times \mathbb{N}^{\mathbb{N}}$ has the product ordering. Also, it follows from the lemma that $f^{-1} \times f^{-1}$ is an order isomorphism from $[0, 1) \times [0, 1)$ to $\mathbb{N}^{\mathbb{N}} \times \mathbb{N}^{\mathbb{N}}$ (both under the product ordering), and thus we conclude that map $h = f \circ g \circ (f^{-1} \times f^{-1})$ is an order-preserving bijection from $[0, 1) \times [0, 1)$ to $[0, 1)$.

Finally, using $h$ we can define $\tilde{h} : [0, 1] \times [0, 1] \to [0, 1]$ by $$\tilde{h}(x, y) = \begin{cases} \frac{1}{3}h(x, y) & x, y < 1 \\ \frac{1 + x}{3} & x < 1, y = 1 \\ \frac{2 + y}{3} & x = 1 \end{cases}$$ which you can check is an order-preserving bijection since $h$ is.

Note: For a more concrete description of $h$: if $x, y \in [0, 1)$ such that $x$ has zeroes in its binary expansion at indices $a_1, a_2, a_3, \dots$, and $y$ has zeroes at indices $b_1, b_2, b_3, \dots$, then $h(x, y)$ is the number in $[0, 1)$ with zeroes at the indices $a_1, a_1 + b_1, a_2 + b_1, a_2 + b_2, a_3 + b_2, a_3 + b_3, \dots$.

14
On

An answer to the question from the comments to my other answer (apologies if it gets too tedious):

We define $K[0, 1] = \{(x, y) : 0 \leq x \leq y \leq 1\}$ and $K[0, 1) = \{(x, y) : 0 \leq x \leq y < 1\}$ (I'm not sure if this notation is correct, just using this for convenience). In order to find an order-preserving bijection from $K[0, 1]$ to $[0, 1]$, we'll find an order-preserving bijection from $K[0, 1)$ to $[0, 1)$.

Some preliminaries: as you can check, the map $t : \mathbb{N}^{\mathbb{N}} \times \mathbb{N}^{\mathbb{N}} \to (\mathbb{N} \times \mathbb{N})^{\mathbb{N}}$ given by $$t : ((a_1, a_2, \dots), (b_1, b_2, \dots)) \mapsto ((a_1, b_1), (a_2, b_2), \dots)$$ is an order-preserving bijection, where $\mathbb{N}^{\mathbb{N}} \times \mathbb{N}^{\mathbb{N}}$ is under the product ordering (with each $\mathbb{N}^{\mathbb{N}}$ under the lexicographic ordering), and $(\mathbb{N} \times \mathbb{N})^{\mathbb{N}}$ is under the lexicographic ordering (with $\mathbb{N} \times \mathbb{N}$ under the product ordering).

Letting $f : \mathbb{N}^{\mathbb{N}} \to [0, 1)$ be the function from the other answer, we define the subset $$L := (t \circ (f^{-1} \times f^{-1}))(K[0, 1)) \subset (\mathbb{N} \times \mathbb{N})^{\mathbb{N}}$$ so that $t \circ (f^{-1} \times f^{-1})$ is an order-preserving bijection from $K[0, 1)$ to $L$. Note that $L$ is the set of all sequences $((a_n, b_n))_{n \in \mathbb{N}}$ for which either $a_i = b_i$ for all $i$, or there is a unique $j$ with $a_i = b_i$ for $i < j$ and $a_j < b_j$. Letting $D, E \subset \mathbb{N} \times \mathbb{N}$ so that $D$ is the diagonal consisting of all elements $(a, a)$ and $E$ consists of all $(a, b)$ with $a \leq b$, we see that $L$ consists of those $(x_1, x_2, \dots) \in (\mathbb{N} \times \mathbb{N})^{\mathbb{N}}$ for which either $x_i \in D$ for all $i$, or there is a unique $j$ with $x_i \in D$ for $i < j$ and $x_j \in E - D$.

We'll now define an order-preserving bijection $s : L \to \mathbb{N}^{\mathbb{N}}$, but first, we need order-preserving bijections $u : E \to \mathbb{N}$ and $v : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$. These are fairly standard constructions: we can take $u(a, b) = \binom{b}{2} + a$ and $v(a, b) = \binom{a+b-1}{2} + a$. Then we define $s$ on $x = (x_1, x_2, \dots)$, where $x_i = (a_i, b_i)$, by $$s(x) = (u(x_1), u(x_2), \dots)$$ if $x_i \in D$ for all $i$, and otherwise as $$s(x) = (u(x_1), \dots, u(x_j), v(x_{j+1}), v(x_{j+2}), \dots)$$ where $j$ is the minimal index with $x_j \not \in D$.

It remains to show that $s$ has the desired properties. For a given $y = (y_1, y_2, \dots) \in \mathbb{N}^{\mathbb{N}}$, either $y_i \in u(D)$ for all $i$, in which case setting $x = (u^{-1}(y_1), u^{-1}(y_2), \dots)$ we have $s(x) = y$, or there is some minimal $j$ with $y_j \not \in u(D)$, in which case we have $s(x) = y$ for $$x = (u^{-1}(y_1), \dots, u^{-1}(y_j), v^{-1}(y_{j+1}), v^{-1}(y_{j+2}), \dots)$$ so it follows that $s$ is surjective.

To show $s$ is order-preserving, suppose $x, x' \in L$ with $x < x'$, and let $k$ be the index such that $x_i = x_i'$ for $i < k$ and $x_k < x_k'$. There are two cases: in the first case, $x_1, \dots, x_{k-1} \in D$, hence the first $k$ coordinates of $s(x)$ are $u(x_1), u(x_2), \dots, u(x_k)$ and similarly those of $s(x')$ are $u(x_1'), u(x_2'), \dots, u(x_k')$, from which it follows that $s(x) < s(x')$ since $u(x_k) < u(x_k')$. In the second case, there is some (minimal) $j < k$ with $x_j \not \in D$, hence the first $k$ coorinates of $s(x)$ are $u(x_1), \dots, u(x_j), v(x_{j+1}), \dots, v(x_k)$, and similarly those of $s(x')$ are $u(x_1'), \dots, u(x_j'), v(x_{j+1}'), \dots, v(x_k')$, again giving $s(x) < s(x')$ since $v(x_k) < v(x_k')$. Thus $s$ is order-preserving, hence injective, so $s$ is an order-preserving bijection as desired.

Putting things together, we have that $r = f \circ s \circ t \circ (f^{-1} \times f^{-1})$ defines an order-preserving bijection from $K[0, 1)$ to $[0, 1)$. We can now define the order-preserving bijection $\tilde{r} : K[0, 1] \to [0, 1]$, by $$r(x, y) = \begin{cases} \frac{1}{2}r(x, y) & y < 1 \\ \frac{1 + x}{2} & y = 1\end{cases}$$