
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.
 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}.
 Show that (the cardinality of the natural numbers set) N = NxNxN.
 Show that the cardinality of the set of prime numbers is the same as the cardinality of N+
Hi Tania,
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!
 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
onetoone and onto).
 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.
 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
Go to Math Central

