For $A\neq B\in {\cal P}(\omega)$ we set $$\mu(A,B) = \min\big((A\setminus B)\cup (B\setminus A)\big).$$ We define $A < B$ if and only if $A \neq B$, and


* $A = B\cap \mu(A,B)$ (that is $A$ is an initial segment of $B$), **or**
* $\mu(A, B)\in A$ and there is $b\in B$ with $b > \mu(A,B)$.


For example we have $\{0,1\} < \{0,1,2\} < \{0,2\}$. Note that the ordering given by $<$ is total; I don't know whether it is really called a "lexicographic" ordering, perhaps there is a proper name in the literature. (Also I would be delighted to see a definition of $<$ that is more elegant than my definition above.)


**Questions**: If $\alpha$ is a countable ordinal, can $\alpha$ be embedded into ${\cal P}(\omega)$ with the lexicographic ordering? Can even $\aleph\_1$ (or ${\frak c} = 2^\omega$ for that matter) be embedded into ${\cal P}(\omega)$?



"Lexicographic" ordering on ${\cal P}(\omega)$
**Update.** My original post had some wrong statements, which I
have now corrected.


As Emil had noted in the comments, the order is dense on the
infinite subsets. Suppose $A<B$ and both are infinite. In this
case, the least difference element is in $A$. Let $A^+$ agree with
$A$ up to and including that least difference element, and then
skip over the next element of $A$, before continuing arbitrarily.
It follows that $A<A^+<B$.


It follows that there is a dense linear suborder of your order,
and any such order is universal for all countable linear orders.


(The order is not dense on the finite sets, since for example
$\{\}<\{0\}$, and there is no set in between. More generally, if
$A$ is any finite set, then $A<A\cup\{\sup(A)+1\}$ is an immediate
successor.)


Meanwhile, $\omega\_1$ cannot embed in the order, by the following argument. Suppose that we have an $\omega\_1$-increasing chain $A\_0<A\_1<\dots<A\_\alpha$ for $\alpha<\omega\_1$. I claim that eventually, the sets must stabilize on whether $0\in A\_\alpha$, since once it falls out, then it will have to stay out. Above that bound, the sets must eventually agree on whether $1\in A\_\alpha$ or not, for the same reason. And so on. By taking a supremum of these countably many stabilizing points, it follows that there will be a countable stage after which the sets agree on all elements, which contradicts that it is increasing. 


Finally, let me say that your definition is not what is usually called the lexical order, although it has a similar spirit. Usually, the lexical order is defined as follows: regards sets $A\subset\omega$ as binary sequences via their characteristic functions, and say $A<\_{\rm Lex} B$, if at the first digit of difference, $A$ has a $0$ and $B$ has a $1$. This is the usual dictionary order, since we look at the first letter, and then the next letter, and so on.


