Derpityderpiderp
2018-10-07 01:20:26
What will you do if you wanna show that one set has a larger cardinality than the other?
The most straight forward thing to do is to find something from the former set that can't be mapped by the latter set, thus showing that the former set "has more element".
This is precisely what the proof is doing.
When we say 2 sets have the same cardinality, what we are talking about is that there exists a bijective function between the 2 sets. Now what is a bijective function? A function being 1-to-1 and onto. We wanna show otherwise, so what do? Well show that given a function f, one of the condition doesn't hold. Now which do you think is more likely to take you to your destination, 1-to-1 or onto? Well, since you wanna show that there are stuff that can't be mapped, intuitively you will think onto is the more likely way to go. So let's go with onto.
The point is, we want to construct a subset of X such that this subset has no corresponding argument in X. If you ever find yourself stranded in a remote small island, perhaps it's best to first look around, see anything useful, and if you can, try whatever you might. After all if you're gonna die anyway, then you might as well die trying. So when you don't know what to do, let's assume that f is indeed onto, and see where it takes us. If f is onto, then for all x in X, there should be a corresponding f(x), which is a subset of X (very important, you have to know what you are dealing with), and this f(x) will exhaustively represent all the possible member of your power set P(X).
Now comes the fun part: can you think of a subset X that obviously lies out of f's range? If you wanna think about it a little, don't read on. If you're so tired of getting stuck with the proof and just wanna get on, then you should now realize where this A kicks in.
Why not define a set A with the following rule: A set of all x in X such that x doesn't belong to f(x).
Recall that f(x) is a member of P(X), and thus is a set. So it makes sense to say x doesn't belong to f(x). Is A an empty set? Well obviously not: take p in X and define f(p) to be the set of all x save p. p belongs to A. So now we've just taken out the trivial possibility that it's empty. But how do we know that this set can't be mapped by any x in X? This is where our previous assumption kicks in.
You see, we have assumed that f is in fact onto. That means there must be some p in X such that f(p) = A. But then comes the question, can p be in A? Well if it does, then A's condition implies that f(p) =/= A, a contradiction. But if p isn't in A, then p is in fact in f(p) = A, again a contradiction! So there can't actually be a p that maps to A. That's how you show that f is not onto at all, and thus P(X) has a greater cardinality than X.
Maths is a lot more intuitive and creative than most people like to think. Not to say there aren't any black magics out there, but I'll say that if you are willing to learn, most importantly look in to the mindset and actually do maths (instead of merely reading it), you will eventually get there.