3 ms·
Yes. When working more formally it's actually easier just to show that for every set A the set 2^A is strictly bigger, where 2^A is a common representation for
by ColinWright 14y ago
Yes.
When working more formally it's actually easier just to show that for every set A the set 2^A is strictly bigger, where 2^A is a common representation for the power set of A, the collection of all subsets.
As an aside, if A and B are sets, the set A^B is
{f : f:B->A},
the set of all functions from B to A. You can quickly show that if A and B are finite, and |A|=n and |B|=m then |A^B|=n^m, thus matching our intuition. A function in 2^A says for each element of A, choose whether it's in or out. That gives a subset of A, so it makes sense to call the set of subsets 2^A, the power set.
In what follows you need to "read like math." This is not a novel - work through it, don't simply try to read. Draw pictures, use simple examples, try to fund counter-examples. Work on understanding.
So, given a set A, how do we show that |A| < |2^A|? Simple, we take any function from A to 2^A and show that some element of 2^A doesn't get hit. This shows that for every function from A->2^A it's not a matching. Hence no matching exists between A and 2^A, so 2^A is not the same size.
I'll leave it to the interested reader to show that 2^A is never smaller than A.
So how do we show that any function from A to 2^A leaves some element of 2^A unhit?
Let g:A->2^A be any function from A to 2^A. We construct h in 2^A such that h is not in the image of g.
h needs to be a function from A->{0,1}, so for every a in A, we need to say whether h(a)=0 or h(a)=1.
Remembering that g(a) is in 2^A, and hence is a function A->{0,1} we define h:A->{0,1} as:
h(a) = 0 if (g(a))(a) = 1
h(a) = 1 if (g(a))(a) = 0
Chase the definitions and you'll find that for every a in A, h != g(a).