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.

I have this prob and still haven't figured about

Let (A, $\leq$) be a partially ordered set. A subset B of A is called an antichain if and only if for any two distinct elements x and y in B, neither x $\leq$ y or y $\leq$ x. Prove that every antichain is contained in an antichain which is maximal with respect to inclusion $\subseteq$

I tried to make a set of subsets of A which are antichains. However I don't know what to do next. The text book says use Hausdorff maximal principle, but I can't use it from the set I made cause elements are not totally ordered sets. What should I do?

share|improve this question
    
I removed the elementary set theory tag since the Hausdorff Maximal Principle is equivalent to the Axiom of Choice. –  Willie Wong Jan 11 '13 at 13:40
add comment

1 Answer

up vote 2 down vote accepted

Let $L$ be the set of all antichains of $A$. $L$ is evidently non-empty, since every singleton subset $\{x\}\subset A$ is an antichain.

Since $L \subset \mathcal{P}A$ we have that $L$ is partially ordered by set inclusion.

For an antichain $B$, $\{B\}\subseteq L$ is totally ordered by set inclusion trivially. Hence applying Hausdorff Maximal principle it is contained in a maximal totally order chain which we call $\mathcal{C}\subseteq L$.

Let $\bar{B} = \cup \mathcal{C}$.

Verify $\bar{B}$ is maximal: if not, there would be $C$ an antichain such that $C\supsetneq \bar{B}$. But then $\mathcal{C} \cup \{C\} \supsetneq \mathcal{C}$ contradicts maximality of $\mathcal{C}$.

Next we verify $\bar{B}$ is an antichain. If $x,y\in \bar{B}$ we know that $\exists B_x,B_y\in \mathcal{C}$ such that $x\in B_x, y\in B_y$. But since $\mathcal{C}$ is totally ordered we have that $\exists B' \in \mathcal{C}$ such that $B' \supset B_x \cup B_y$ and so $x,y\in B'$. Since $B'\in L$ we have that $x,y$ are not comparable. Hence $\bar{B}$ is an antichain.

share|improve this answer
    
Thank you. By the way, why the existence of such B' implies x,y are in B'? –  mingyu Jan 11 '13 at 13:57
    
$x\in B_x \subseteq B'$ and $y\in B_y \subseteq B'$. .. Ah, I made a typo in the original answer. Sorry. –  Willie Wong Jan 11 '13 at 14:00
    
Now I got it! Thank you again:) –  mingyu Jan 11 '13 at 14:02
add comment

Your Answer

 
discard

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.