Take the 2-minute tour ×
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.

Possible Duplicate:
A countale partially ordered set that has an uncountable number of maximal chains

Let $(P,\leq) $ partial ordered set. We say $I\subseteq P $ is a chain if for all $a,b \in I $, held $a\leq b$ or $b\leq a$.

$I\subseteq P $ is maximal chain if there is no $J\subseteq P$ that contains $I$ totally.

Question:

Find partial ordered set $(P,\leq) $, such that $\text{card P}=\aleph_0$, but the set of maximal chain cardinality is $\aleph$.

Can somebody explain me what I need to do?

Thank you!

share|improve this question

marked as duplicate by Asaf Karagila, martini, Cameron Buie, tomasz, Henry T. Horton Nov 29 '12 at 2:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3  
Is $\aleph$ the same as $\aleph_0$? If not, what is it? –  Brian M. Scott Nov 28 '12 at 21:06
    
$\text{card}\mathbb{R}=\aleph$ –  17SI.34SA Nov 28 '12 at 21:16
    
That’s a most unusual notation; normally one writes $2^{\aleph_0}$, $2^\omega$, or $\mathfrak c$ for $|\Bbb R|$. –  Brian M. Scott Nov 28 '12 at 21:23
1  
@Brian: That was Cantor's original notation, actually. It is also not uncommon in Israel (for some reason) to use $\aleph$. At least in introductory courses. –  Asaf Karagila Nov 28 '12 at 21:42
add comment

2 Answers 2

up vote 1 down vote accepted

I expect that you know what a chain in the partial order $\langle P,\le\rangle$ is: a subset of $P$ that is linearly ordered by $\le$. A maximal chain is simply a chain that is not a proper subset of any other chain. For example, if you partially order the positive integers by divisibility (i.e., $m\le n$ iff $m\mid n$), then $C=\{2^k:k\in\Bbb N\}$ is a maximal chain: if you add to $C$ any positive integer that is not a power of $2$, you’ll no longer have a chain. Thus, you’re being asked to find a countable partial order that has $|\Bbb R|$ distinct maximal chains.

It is perhaps a little surprising that it’s possible to find such a small partial order with so many different chains, so it’s not surprising that an example probably isn’t immediately obvious. I’ve given a couple of (very similar) examples below, leaving the verification that they work to you; if you want to try finding one on your own, you should stop reading here.


Let $P$ be the set of finite sequences of $0$’s and $1$’s, setting $\sigma\le\tau$ if and only if $\sigma$ is an initial segment of $\tau$. Show that there is a maximal chain for each infinite sequence of $0$’s and $1$’s.

Alternatively, let $\mathscr{F}$ be the family of finite subsets of $\Bbb N$, and define the partial order $\le$ as follows: for $F,G\in\mathscr{F}$, $F\le G$ if and only if $F\subseteq G$ and either $F=G$ or $\max F<\min(G\setminus F)$. In other words, if $F$ and $G$ are distinct members of $\mathscr{F}$, then $F<G$ if and only if $F\subseteq G$ and every element of $G\setminus F$ is larger than every element of $F$. Show that there is a maximal chain in $\langle\mathscr{F},\le\rangle$ for each infinite subset of $\Bbb N$. (This partial order is isomorphic to the subset of the first one consisting of those finite sequences whose last terms are $1$.)

share|improve this answer
    
Brian, read closely. The OP asked for an explanation what is the question asking, instead you wrote a solution to the question. :-) –  Asaf Karagila Nov 28 '12 at 21:46
    
@Asaf: Damn. I knew that, and then I got distracted before writing my answer. –  Brian M. Scott Nov 28 '12 at 21:50
add comment

You need to find a countable partial order $(P,\leq)$ such that the collection of $\{C\subseteq P\mid C\text{ is a maximal chain}\}$ has cardinality $2^{\aleph_0}$.

One example would be all finite binary strings ordered by end-extension. Show that any maximal chain would correspond to an infinite subset of $\mathbb N$, and that different subsets correspond to different maximal chains.


$C\subseteq P$ is a maximal chain, I'll remind you, if $(C,\leq\upharpoonright C)$ is a linear order, and whenever $C\subsetneqq D$ we have that there are $x,y\in D$ such that $x\nleq y$ and $y\nleq x$. Namely $C$ is a chain and it cannot be extended to a strictly larger chain.

share|improve this answer
add comment

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