Subject: set's cardinality

Name: Tania

Who is asking: Parent Level: Secondary

Question: My son come back to home with some questions about sets and its cardinality, but I couldn't solve any of the next three problems, these aren't to obvious for my... so I appreciate any comment.

Thanks in advance, Tania.

1. Show that the cardinality of P(X) (the power set of X) is equal to the cardinality of the set of all functions from X into {0,1}.
   
   
2. Show that (the cardinality of the natural numbers set) |N| = |NxNxN|.
   
   
3. Show that the cardinality of the set of prime numbers is the same as the cardinality of N+

These are all mental games with 'infinite sets'. A nice resource book would be 'stories about sets' which the authors explianed were things every student at Moscow University learned around the common room but not in any classes!

1. The key here is an 'image'. Consider a subset A of X (an element of the power set). Now consider the function f_A (usually called the characteristic function of A): If an element is in A, f_A maps it to 1. If an element is not in A, f_A maps it to 0.

   Can you see how this 'pairs the two set off'.

   One usually proves two sets have the same cardinality by such a pairing (fancy word - a bijection - a map which is both one-to-one and onto).
   
   

2. This requres a more complicated 'image'. You prove something has the cardinality of N (written |N|) by showing it can be put into a infinite list: first, second, third, ....

   Now you need to put all triples of natural numbers into some list of this type?

   The picture I learned for PAIRS, may suggest what to do from triples. For pairs, write them out as dots in a quadrant of the plane:
   
   

   (1,1) (1,2) (1,3) ...
   (2,1) (2,2) (2,3) ...
   (3,1) (3,2) (3,3) ...
   . . .
   . . .
   . . .
   

   Now zig zag out from the upper left corner: (1,1), (1,2), (2,1) (3,1), (2,2), (1,3) ....

   Catching the finite number of pairs with a given sum (2,3,4, .... ) in turn, and finally catching them all in a single list. Your son may have seen this in some proof that the rational numbers have cardinality |N| - all rational numbers appear as part of this list above (with some duplication) - by taking (a,b) as a/b.

   I suspect you can now image what to do for NxNxN .... Writing it down will still be a challenge.
   
   

3. the last one is hard. The proof involves something from Euclid - about the number of primes NOT being finite. Since the primes are PART of the natural numbers, we now that this set cannot be larger than |N|. If it was not equal to |N|, then it would be finite. It will leave looking up the fact from Euclid to your son.

All in all, a tough set of questions - tough because we have not practiced with infinite sets and because the 'logic' (reasoning) of some of these methods is also unfamiliar. Each of the three questions involved a different set of ideas or images.

Walter Whiteley
York University