4
$\begingroup$

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)$?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ The restriction of this order to infinite sets is a dense order, hence it contains a copy of Q, hence it contains a copy of any countable linear order. $\endgroup$
    – Emil Jeřábek
    Commented Apr 13, 2016 at 13:47
  • $\begingroup$ Emil, it isn't dense on the infinite sets, since $\mathbb{N}<\mathbb{N}-\{0\}$, but there is nothing in between. But it is dense on the finite sets. $\endgroup$
    – Joel David Hamkins
    Commented Apr 13, 2016 at 14:14
  • $\begingroup$ If I'm not mistaken, you can embed your order into Baire space $\mathbb{Z}^\omega$, with its lexicographic order, by listing the elements of a set in increasing order and padding out finite sets with -1. And I'm pretty sure you can't embed $\omega_1$ into Baire space. According to this, you can embed the lex order on Baire space into the reals with their usual order (specifically the irrationals) and you definitely can't embed $\omega_1$ in the reals. $\endgroup$
    – Nate Eldredge
    Commented Apr 13, 2016 at 14:19
  • $\begingroup$ @Joel: I may misunderstand the definition, but it seems to me that N < N-{1} < N-{0}. You even claim yourself in another comment that the order is dense on cofinite sets, which these two sets are. $\endgroup$
    – Emil Jeřábek
    Commented Apr 13, 2016 at 16:54
  • $\begingroup$ You are right, and my argument is wrong. I'll edit later. {}<{0} and there is nothing between. $\endgroup$
    – Joel David Hamkins
    Commented Apr 13, 2016 at 18:55

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the clarification! Can you show two sets $A, B\in{\cal P}(\omega)$ that have reversed order in "my" ordering vs $<_{\text{Lex}}$? And your answer would be the same if the question were about $<_{\text{Lex}}$? $\endgroup$
    – Dominic van der Zypen
    Commented Apr 13, 2016 at 14:31
  • 2
    $\begingroup$ Of course for the usual lexical order there is a direct proof that every countable ordinal embeds of where we choose a bijection between the ordinals and $\omega$ and send each ordinal to the image of the set of ordinals below it under the bijection. $\endgroup$
    – Will Sawin
    Commented Apr 13, 2016 at 14:32
  • $\begingroup$ Dominic, in your definition, you say $A<B$ when $A$ has the first-difference element, this does not agree with the usual lexical order, since the binary sequence would have a $1$ for $A$ and a $0$ for $B$ in this case, but you haven't just reversed the order, since you say initial segments are lower. $\endgroup$
    – Joel David Hamkins
    Commented Apr 13, 2016 at 14:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .