Let $2^\alpha=\{f\mid f\colon\alpha\to2\}$.


1, Is it provable in ZFC that for all infinite ordinals $\alpha$, $2^{\alpha+1}$ cannot be embedded into $2^\alpha$, where $2^{\alpha+1}$ and $2^\alpha$ are equipped with the lexicographical ordering?


2, We can prove in ZFC that for all infinite cardinals $\kappa$ and all ordinals $\alpha<\kappa$, $\kappa$ cannot be embedded into $2^\alpha$, where $2^\alpha$ is equipped with the lexicographical ordering.


Is this proposition provable in ZF? Or is it provable in ZF that $\omega\_1$ cannot be embedded into $2^{\omega+\omega}$, where $2^{\omega+\omega}$ is equipped with the lexicographical ordering? (I have proved in ZF that $\omega\_1$ cannot be embedded into $2^\alpha$ for all $\alpha<\omega+\omega$.)



Two questions about the order type of $2^\alpha$ equipped with the lexicographical ordering
A friend of mine proves in ZF the proposition in Question 1 as follows.


Assume towards a contradiction that $H$ is an embedding of $2^{\alpha+1}$ into $2^\alpha$. For two different $f,g\in2^\alpha$, the branching point of $f$ and $g$, which will be denoted by $\mathrm{brp}(f,g)$, is defined to be the least ordinal $\beta<\alpha$ such that $f(\beta)\neq g(\beta)$. Let $<\_l$ be the lexicographical ordering. The following two facts are easily verifiable:


(i) If $e<\_lf<\_lg<\_lh$, then either $\mathrm{brp}(e,h)<\mathrm{brp}(e,f)$ or $\mathrm{brp}(e,h)<\mathrm{brp}(g,h)$.


(ii) If $e\leqslant\_lf<\_lg\leqslant\_lh$, then $\mathrm{brp}(e,h)\leqslant\mathrm{brp}(f,g)$.


Let $F$ be the function on $2^{\leqslant\alpha}$ into $\alpha$ such that for all $u\in2^{\leqslant\alpha}$,
$$F(u)=\mathrm{brp}(H(u\cup\langle0\mid\mathrm{Dom}(u)\leqslant\beta\leqslant\alpha\rangle),H(u\cup\langle1\mid\mathrm{Dom}(u)\leqslant\beta\leqslant\alpha\rangle)).$$


We define now by recursion a function $G$ on $\alpha$ into $\{0,1\}$ as follows. $G(\delta)=0$, if $F(G\upharpoonright\delta)<F((G\upharpoonright\delta)\cup\{(\delta,0)\})$, and $G(\delta)=1$, otherwise. By the fact (i) above, we have that if $G(\delta)=1$ then $F(G\upharpoonright\delta)<F((G\upharpoonright\delta)\cup\{(\delta,1)\})$.


Let $T$ be the function on $\alpha+1$ into $\alpha$ such that for all $\beta<\alpha+1$, $T(\beta)=F(G\upharpoonright\beta)$. By the definition of $G$, $\ T(\delta)<T(\delta+1)$ for all $\delta<\alpha$. By the fact (ii) above, we have that for all limit ordinals $\gamma<\alpha+1$ and all $\beta<\gamma$, $T(\beta)\leqslant T(\gamma)$. Hence $T$ is an increasing function from $\alpha+1$ into $\alpha$, which is a contradiction.


