4 ms·

That would rock, yes. (But why aren't there 2^oo columns? In order to fill up all possible ...<snap> I think I got it... You're not trying to use every possi

That would rock, yes. (But why aren't there 2^oo columns? In order to fill up all possible ...<snap> I think I got it... You're not trying to use every possible oo-length binary string, you're just mapping each natural number to an arbitrary (unique) oo-length binary string, so the grid in a square in the end.

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

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