7
$\begingroup$

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?

  • 0
    @Thomas, Vladimir: In light of the two answers, I've removed my comments. I think that you should also remove yours.2012-07-19

2 Answers 2

4

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 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 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 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. 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 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 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.

3

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 in $L$ and $\forall z\in L:z.

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.

  • 0
    @AsafKaragila I've tried to fix it with the issues I fou$n$d.2012-07-19