Prove Zorn's Lemma Problem: Cardinality of A and B

[Tom1992]

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.

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.

 

[StatusX]

we let T be the collection of all elements of P(X) that are comparable to each other by <=,

What exactly does this mean?

 

[StatusX]

What I'm saying is that, starting with a partially ordered set, you can't naturally define the "set of elements that are comparable to each other." For example, any set with the minimal reflexive relation is a poset, and each singleton subset, and only the singleton subsets, satisfy the property of having every element comparable to each other.

 

[matt grime]

That sounds like you're assuming the answer to me. You have written it as if there were only one possible such T. I.e. you stated: let T be THE set of all comparable elements. (emphasis added).The point is (I'm guessing), to say something like: take any chain of Ts with the property that they are totally ordered, now by Zorn there is a maximal one. Show that if the maximal one is not all of P(X) then you have a contradiction.

 

[matt grime]

If you read yout opening post, you'll notice that you've just found the maximal element M you were looking for. But it doesn't do anything for what you want to do.

 

[StatusX]

Let's make explicit what you're doing. The order is on elements in P(X). It is not the usual "is a subset of" order we put on P(X), but it is the weaker "has less or equal cardinality as" order. But this forces you to compare subsets that might be disjoint, which seems unnatural.

I would stick to A and B from the original post, and not worry about the power set of some other set X. Remember, |A|<=|B| means that there is an injective function from A to B. Assume this isn't true. Then can you construct an injective function from B to A?

 

[Tom1992]

Let's make explicit what you're doing. The order is on elements in P(X). It is not the usual "is a subset of" order we put on P(X), but it is the weaker "has less or equal cardinality as" order. But this forces you to compare subsets that might be disjoint, which seems unnatural.

I would stick to A and B from the original post, and not worry about the power set of some other set X. Remember, |A|<=|B| means that there is an injective function from A to B. Assume this isn't true. Then can you construct an injective function from B to A?

ok, i'll change my method altogether (and perhaps use the schroder-bernstein theorm). i was just following the hint of using zorn's lemma. so we throw zorn's lemma out the window?

 

[Tom1992]

using statusx's suggestion, this is what i have so far.

let A and B be two sets. If A<=B, we are done, so assume that A<=B is false. thus there is no injection from A to B . Let f:A->B be a surjective map (we will consider the case where there is no such surjective map later). then for any b in B , f^(-1)(b) is nonempty. by the axiom of choice, we choose one element of f^(-1)(b) for each b in B and so the resulting choice function c:B -> A is defined and injective. thus B<=A.

suppose there is no surjective map from A to B. then B-f(A) is nonempty for any map f:A->B. let S be the set of all "extra" elements in A that are mapped non-injectively to B (i'll define S rigorously later, using the axiom of choice). S is non-empty since f is not injective by assumption. we redefine f to a new map g:A->B such that, using the axiom of choice, every point in S is mapped to B-f(A) injectively (and g(a)=f(a) for all a not in S). after this process g is either injective or surjective (* I'm working on this detail now). if g is injective, then A<=B (a contradiction). but g can't be surjective either, since we've assumed that there is no surjective map from A to B. thus if A<=B is false, then we must have B<=A.

so far so good? (no zorn's lemma unfortunately)

* call C=B-f(A). if C “becomes empty after this process” (i.e. g(S) contains C, after which g can map the left over points to anywhere in B), then g is surjective. Otherwise C contains g(S), in which case g is injective.

THIS METHOD WORKS, VERIFIED BY MATT GRIME

 

[matt grime]

zorn's lemma is equivalent to the axiom of chioce, so you have used it.

if you want to follow the original plan, just think about where you're trying to use zorn's lemma. What chain are you trying to take a maximal element of? It is probably a chain of collections of subsets for which the total ordering holds in each collection. your mistake was in saying 'the collection of sets'. You're trying to prove that there is a maximal one, and that it is all of P(X).

 

[matt grime]

let X be a set, and let A<=B mean that “A has less cardinality or the same cardinality as B”, where A and B are subsets of X. our goal is to show that P(X) is totally ordered by <=, where P(X) is the set of all subsets of X. we let T be the collection of all elements of P(X) that are comparable to each other by <=,

let T be *A* collection of sets that are totally ordered by <=

StatusX's point was that a priori you don't know there is such a set that we can call THE set of comparable elements. Indeed, there is no such thing as THE set of comparable elements. We do want to show that the maximal set of comparable elements is P(X).

and let T itself be partially ordered by set inclusion.

don't do this.

then we will (eventually) use zorn’s lemma to show that T has a maximal element M

T is a collection of sets. If it has a maximal element that element is just a set (a subset of X).

Try to show that for any chain of Ts, there is a maximal something or other, and that this maximal something or other is P(X).

I repeat, you don't want a maximal element of T, but a maximal element of things that have whatever property T has.

 

[Tom1992]

ok, i'll work on a second solution using zorn's lemma now.

 

[Tom1992]

but now I'm back to where i was stuck in the first place. how to show 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.

 

[StatusX]

X is just a set, it has no partial order itself. P(X) has a partial order given by |A|<|B| if the subset A has smaller cardinality than the subset B.

Then certain collections of subsets of X (ie, subsets of P(X), ie, elements in P(P(X)) ) either have the property that they are totally ordered or they don't. Let M denote the collection of subsets of P(X) that are totally ordered (note M is in P(P(P(X))) ).

Now you want to show that every subset of X can be compared, or in other words, the collection of all subsets of X, P(X), belongs to M. To do this you form chains not using the partial order by cardinality in P(X), but using the partial order by set inclusion in M (which is a subset of P(P(X)) ). In other words, given two totally ordered sets of subsets of X, A and B, we say A <= B if B contains A, ie, every subset in A is also in B.

Maybe this was already clear to you, but I thought it was sufficiently confusing that I'd mention it explicitly.

 

[Tom1992]

statusx, your M is my A, and my M is a maximal element of my A (which I've already established).

ok, I'm going to summarize my entire proof so far (i'm at the last step and stuck there):


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

 

[StatusX]

It seems like what you want to do is show that you can adjoin a subset S to M and still retain the total order property. In other words, you want to show that every element in M can be compared to S. But this is just what you want to show in the first place. And I don't see how M being maximal is going to help you.

Remember, ultimately the definition of this partial order is in terms of injective/surjective functions, so you'll need to construct some of these at some point. My guess is that Zorn's lemma will apply to this construction, and the proof using it is probably just a slight variation of your other proof.

 

[Tom1992]

still trying to prove M=P(X). suppose M not= P(X). take S from P(X)-M. we want to show that MU{S} is a collection of totally ordered subsets, contradicting the maximality of M.

Let R belong to M. if R<=S for all R belonging to M then MU{S} is a totally ordered set. define
K={R' in M|R'<=S is not true}.
then
K={R' in M| S<=R'}
(using the injective/surjective mapping technique in my other proof, we conclude that if R'<=S is not true, then S<=R'). KU{S} is totally ordered by <= since M is totally ordered by <= and K is a subset of M (and hence K itself is totally ordered by <=). Similarly, since
M-K={R' in M|R'<=S}
is totally ordered by <=, then (M-K)U{S} is totally ordered by <=. Thus MU{S}=((M-K)U{S})U(KU{S}) is totally ordered, contradicting the maximality of M. is this correct?

if not, how about this:
we now make use of the property that each element of P(X) partially ordered by set inclusion relation has a greatest lower bound and also a least upper bound (lub is the union, glb is the intersection). let R" be the greatest lower bound of K (in the partial order set inclusion). then R" is a subset of every element of K, which means that R"<=R' for every R' in K. since S<=R' for every R' in K, and R" is the greatest lower bound of K, then we must have S<=R". thus R'' belongs to K. consequently, since K is a subset of M and M is totally ordered, then KU{S} is totally ordered. similarly, M-K={R' in M|R'<=S} contains its least upper bound so that (M-K)U{S} is also totally ordered. thus
MU{S}=((M-K)U{S})U(KU{S})
is a collection of totally ordered subsets, contradicting the maximality of M. ?