- 112

- 0

**1. Homework Statement**

prove that given any pair of sets A and B, either A< B, A~B , or B<A, where < means “has cardinality less than” and ~ means “has the same cardinality as”. the hint is to use zorn's lemma.

**3. The Attempt at a Solution**

i've done several zorn's lemma problems successfully, so i know zorn's lemma well. but this question got me stuck.

i'm going to summarize my entire proof so far (i'm at the last step and stuck there). Note: i've editted my opening post and placed my latest solution here:

let X be a set. we give P(X) a partial order relation: we write Y<=Z if Y has less cardinality than or the same cardinality as Z, where Y and Z are subsets of X.

let A be the collection of all collections of subsets of X that are totally ordered by <=. let A be partially ordered by set inclusion. let B={B_i} be a totally ordered subcollection of A. let C=Union B_i. C is an upper bound of B since each B_i is a subset of C. before using zorn’s lemma, however, we must show that C is in A, i.e. C is collection of subsets that are totally ordered by <=. let R,S be in C. then there exists B_i, B_j from B such that R belongs to B_i and S belongs to B_j. since B is totally ordered by set inclusion, then either B_i is a subset of B_j or B_j is a subset of B_i. without loss of generality, we assume that B_i is a subset of B_j. then R,S belong to B_j. since B_j is totally ordered by <=, then we have either R<=S, or S<=R. thus C is a collection of subsets that are totally ordered by <=, and hence C belongs to A.

we have thus shown that every totally ordered subcollection of A has an upper bound in A and thus by zorn’s lemma, A has a maximal element M. we claim that M=P(X). suppose M not= P(X). take S from P(X)-M. we want to show that M+{S} is a collection of totally ordered subsets, contradicting the maximality of M. take L from M+{S}. we need to show that either L<=S or S<=L.

**<<STUCK>>**the problem is that if K<=S (say K is a subset of S), and K<=J, i can't say anything about J and S (or can i?). clearly X and the empty set are in M. then

{emptyset ,...,..., S,....,.., X} is a chain not contained in M, but that doesn't give a contradiction.

Last edited: