Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $S$ be the set of all maximal chains in the poset $\langle$$\mathcal{P}$$($$\mathbb{N}$$),$$\subseteq$$\rangle$ partitioned into equivalence classes by their order types. How many different order types are there? Can you give me some insight into the structure of $S$ when quasi-ordered by embedding of order types? What is the supremum of ordinals that can be embedded into this quasi-order?

share|cite|improve this question
Adding the condition that the embedding have to be continuous (since the orders of the chains are complete) might make sense. – Thomas Andrews Jul 19 '12 at 18:11
@AsafKaragila Just to make sure we are on the same page: in the last question I meant an embedding of an ordinal into the quasi-order of order types rather than into an element of this quasi-order. – Vladimir Reshetnikov Jul 19 '12 at 18:18
@ThomasAndrews: Could you please give a definition of continuous embedding of order types? – Vladimir Reshetnikov Jul 19 '12 at 18:24
@AsafKaragila: Can every ordinal below $\mathfrak{c}$ be embedded? – Vladimir Reshetnikov Jul 19 '12 at 18:27
@Thomas, Vladimir: In light of the two answers, I've removed my comments. I think that you should also remove yours. – Asaf Karagila Jul 19 '12 at 22:52
up vote 4 down vote accepted

Somehow nobody dares to answer this question. (Edit: Thomas' answer didn't show up on my computer in time. We have the same result. I am talking about jumps, he talks about successors.)

Let $L$ be a linear order. Two points $x,y\in L$ form a jump if $x<y$ and the open interval $(x,y)$ is empty.

Let $M\subset\mathcal P(\mathbb N)$ be a maximal chain. Then $M$ is a infinite complete linear order with endpoints and at most countably many jumps.

By the maximality of $M$, $\emptyset$ and $\mathbb N$ have to be in $M$. Hence $M$ has endpoints. Similarly, if for all nonempty $S\subseteq M$, $\bigcup S\in M$. $\bigcup S$ is just the supremum of $S$ in $M$. Similarly, every nonempty subset $S$ of $M$ has an infimum in $M$, namely $\bigcap S$. It follows that $M$ is complete.

Now, if $x<y$ is a jump in $M$, then there is $n_{x,y}\in\mathbb N$ such that $n_{x,y}\in y$ and $n_{x,y}\not\in x$.
For two different jump $x,y$ and $x',y'$, $n_{x',y'}\not=n_{x,y}$. Since there are only countably many elements of $\mathbb N$, there are only countably many jumps.

Finally, why is $M$ separable? For each $n\in\mathbb N$ let $a_n=\bigcup\{a\in M:n\not\in a\}$. Then $a_n\in M$. Let $a,b\in M$ be such that $a\subsetneq b$. For some $n\in\mathbb N$, $n\in b$ but $n\not\in a$. Now $a\subseteq a_n\subsetneq b$.
This shows that every interval of the form $[a,b)$ with $a\subsetneq b$ has an element of the form $a_n$.
Now if $a<b$ and $a,b\in M$, then either $a,b$ form a jump in $M$ and the open interval $(a,b)$ is empty or there is $c\in M$ such that $a<c<b$. In this case there is $n$ such that $a_n\in[c,b)\subseteq(a,b)$. It follows that $\{a_n:n\in\mathbb N\}$ is actually dense in $M$.

This proof indicates another structure of $M$: For $n\in\mathbb N$ let $a^n=\bigcap\{a\in M:n\in M\}$. Clearly, $a_n<a^n$ and $a_n,a^n$ form a jump of $M$. So, by the previous argument, left partners of jumps are dense in $M$.

It follows that there is no maximal chain whose ordertype is that of $\mathbb R$! You do have chains of ordertype $\mathbb R$, but these are not maximal. Similarly, you have chains of every separable ordertype with at most countably many jumps.

If $L$ is an infinite complete linear order with countably many jumps and the jumps are dense in $L$, let $(d_n)_{n\in\mathbb N}$ be an enumeration of all left partners of jumps in $L$. Now the map $$e:L\to\mathcal P(\mathbb N);x\mapsto\{n:d_n<x\}$$ is order preserving, so $e[L]$ is a chain. The first element of $L$ gets mapped to $\emptyset$ and the last element of $L$ gets mapped to $\mathbb N$.

To see that $e[L]$ is maximal, let $a\subseteq\mathbb N$ be such that $e[L]$ is a chain. If $\{d_n:n\in a\}$ has a largest element, it is of the form $d_n$ and hence the left partner of a jump with right partner $x$. Now $e(x)=a$.

If $\{d_n:n\in a\}$ has no last element, then let $x=\sup\{d_n:n\in a\}$. Now also $e(x)=a$. This shows that $a\in e[L]$. Hence $e[L]$ is indeed a maximal chain.

share|cite|improve this answer

In a linear order, $(L,<)$ we say that $x\in L$ is a successor if there exists a (necessarily unique) $y\in L$ such that $y<x$ in $L$ and $\forall z\in L:z<x\implies z\leq y$.

A linear order, $(L,<)$, can be represented by a maximal chain in $(P(\mathbb N),\subset)$ if and only if:

  1. $(L,<)$ is complete, infinite, and has maximal and minimal elements

  2. The set of successors in $(L,<)$ is countable and dense in $(L,<)$

These conditions mean that such a linear order is entirely determined by the order on the set of successors, and hence there is a $1-1$ correspondence between $S$ and the isomorphism classes of countably infinite linear orders.

Given a linear order $(\mathbb N,\prec)$, we define a chain as $$C=\{X\subset \mathbb N:\forall x,y: x\in X \land y\prec x \implies y\in X\}$$ That this is a chain is clear. That this is maximal only requires a little work.

On other other hand, if $(L,<)$ satisfies our condition above, and $\phi:\mathbb N\to L$ is a $1-1$ map onto the successors of $L$, then we can define $(\mathbb N,\prec)$ by $n\prec m$ if and only if $\phi(n)<\phi(m)$. Then we can show that the chain that we get from $$(\mathbb N,\prec)$ must be isomorphic to $(L,<)$.

The elements of $C$ of the form: $$X_n = \{y:y\prec_{=} n\}$$ are successors of $$Y_n=\{y:y\prec n\}$$ and they are dense in the order of $C$, because if $a\subset b$ are elements of $C$ and $n\in b-a$, then $a\subset X_n \subseteq b$.

A little fussing will show that this gives all maximal chains.

In response to your question in comments about uncountable ordinals.

Given an ordinal, $m$, the set of successors is always dense, but, if the ordinal is infinite, the set of successors has the same cardinality as the entire ordinal, so $m$ must be countable.

As Asaf said in comments above, the quasi-order under embeddings is going to be very messy. Even with my suggested restriction to continuous embeddings, I still think this is a big mess.

Contrary to comments above, there is no such $C$ isomorphic to $\mathbb R$ or $[0,1]$, because there are no successors in these orders. There are uncountable examples, however, such as the Cantor set. The closest we can come to the reals is the reals with addition of "successor rationals" - two items per rational number, with one the successor of the other.

share|cite|improve this answer
+1 Very nice! ${}$ – Asaf Karagila Jul 19 '12 at 19:50
Wait, correct me if I am wrong, but isn't there really just two kinds of complete separable linear orders? $[0,1]$ and successor ordinals? If that is the case then $S$ is actually quite simple, it's $\omega_1+1$. – Asaf Karagila Jul 19 '12 at 20:03
No, you can get inverse ordinals - no lower bound. @AsafKaragila – Thomas Andrews Jul 19 '12 at 20:06
Also, you don't get exactly $[0,1]$ by taking the ideals of the rational numbers order, since the order ideals of $\mathbb Q$ include two instances of each rational. Dedekind cuts exclude the set $\{r:r\leq q\}$. So I might be missing something here. – Thomas Andrews Jul 19 '12 at 20:07
You might have to add the ccondition that the dense subset has to be a set of elements with distinct maximal sub-element - that is, they are all successors. – Thomas Andrews Jul 19 '12 at 20:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.