Proving cardinality of a set differs from cardinality of its power set

[Ed Quanta]

Can someone help me prove that the cardA does not equal cardP?

where A is the set {a,b} and P is its power set{empty set,(a),(b),(a,b)}

I know that by showing A ->P is not a surjection, I will be showing that no bijection exists and thus unequal cardinalities between sets A and P. But I am unclear on how to do this. I heard it is a tough proof, and just want some insight of helpful hints.

 

[matt grime]

Do you want a general proof that there is no bijection from a set to its power set? Seeing as you don't need that here it seems a lot like over kill, not that the proof is hard.

Let S and T be two finite sets. How many injections are there from S to T? If card(s) > card(T) then there can be no injections.

In fact you can now show that there are bijections between finite sets iff they contain the same number of elements in the obvious sense.

 

[Ed Quanta]

Do you want a general proof that there is no bijection from a set to its power set? Seeing as you don't need that here it seems a lot like over kill, not that the proof is hard.

Yeah, if it isn't too hard I wouldn't mind seeing it.

 

[matt grime]

Let X be any set, and f any injection from X to P(X). define T to be the set of x in X such that x is not in f(x). T cannot lie in the image of f (think cantor's usual argument). It would be good for you to figure out why for yourself. But in conclusion f is not a surjection, hence there are no bijections.

 

[Ed Quanta]

If f were to be a bijection, then it would also be a surjection which would imply that for all elements of T there would have to be an x such that f(x)=T.
This contradicts the fact that in order to be an element of T, x cannot be in
f(x). And thus there is no surjection from X to P(X), and no bijection, and the cardinal numbers must be equal.

I think that is right. The only thing that confuses me is how we originally know to define T in the way that you did.

 

[matt grime]

"imply that for all elements of T there would have to be an x such that f(x)=T"

the start of that is quantified by for all t in T (for no reason I can see), and has nothing to do with the conclusion you reach.

This idea is exactly the argument in the proof that the set of all sequences of 0s and 1s is uncountable that we often use to show that the reals are uncountable.

 

[Ed Quanta]

Rather than create a new thread, I would just like to ask two questions here

1) Some dude was telling me that he objected strongly to the axiom of choice and thought it was a bull**** axiom. He didn't really explain it that well to me so I was curious if you could tell me about it. Also, he said that the axiom of choice makes it possible to divide a sphere into parts, and put them together to form a greater volume, or something like that?

2) Is this sufficient in showing that a subset of a countably infinite set must also be countable?

Set A is countably infinite if and only if if there is a bijection from the set of natural numbers to A. If subset Z of A is finite, then there must be a bijection for some n is an element of Natural numbers, and therefore be countable . If subset Z is empty, it also must be countable. If subset Z of A is infinite, it must be countably infinite because it cannot be a greater infinity and thus there will also exist a bijection to the set of Natural Numbers, and be countable.

 

[matt grime]

Your second proof is right.

The axiom of choice is something that most mathematicians take to be true. Cohen showed it to be independent of the other axioms of ZF (assuming they are consistent which we haven't porved yet and don't look like disproving either).

Pretty much we want it to be true (not in the sense that we believe it *really* is true, but that we want it as an axiom) because it is the only way to find a basis of any vector space. However it does create these problems such as the Banach -Tarski paradox up there. What goes "wrong" is that by allowing us to pick bases we also then create issues where we pick other pathological sets.

Let me give at least one example: you've heard of measure theory perhaps. Here we attempt to define a consistent idea of length of subsets of, say, R, the real numbers. We let [a,b] have length b-a, and write down some other rules (a subset of one set must have smaller total length, and so on) and get a measure, what we find is we have to restrict to a certain kind of set, namely all those that can be written as repeated intersections, unions and complements of sets of the form (a,b]. The question is then are there sets that aren't measurable? It turns out that there are, but in order to write one down one needs to use the axiom of choice.

And what happens in the Banach Tarski paradox involves unmeasurable sets (I think, it's been a while).

Pretty much the problem can be summed up as assuming the axiom of choice let's us make constructions involving an infinite number of unspecified operations, which leads to some distinctly odd ideas, as well as some nice ones.

Without the axiom of choice your proof above doesn't hold as you're assuming the cardinals are well ordered, which is a consequence of the axiom of choice.

There are other things that crop up from assuming apparently reasonable axioms (such as constructibility, google for a devlin article about that one). In all honesty no serious mathematician is all that worried about it too much as long as we state that we are using it explicitly, and accept that there may be some philosophical issues there.

One may do set theory of infinite sets without it. The Bernstein-Schroeder argument is one that states that if U and V are sets with injections between each other then there is a bijection. You do this directly, no axiom of choice. The corresponding proof using surjections requires the axiom of choice.

Hope that's a start.