Aaron Toponce aaron.toponce at
Wed Jun 1 14:27:30 MDT 2011

On Sat, May 28, 2011 at 01:41:07PM -0600, Andrew McNabb wrote:
> On Sat, May 28, 2011 at 12:37:40PM -0600, Nicholas Leippe wrote:
> > What about subsets of the natural numbers such as all even numbers,
> > fibonacci series, or prime numbers?
> > How does the "infiteness" of these kinds of sets get classified?
> They all have the same cardinality as the natural numbers in general.
> You can make a list of the first prime number, the second prime number,
> etc.  This infinite list is a one-to-one and onto function from the
> natural numbers to the prime numbers (proof not included in this email),
> so the two sets have the same cardinality.

Ah, the argument about the size of sets. I really want to chime in here.

Which set is "bigger"? The set of all integers from negative infinity to
positive infinity, or the set of even integers from negative infinity to
positive infinity? Intuition would tell us that the full set of integers is
twice as large, as it's subset containing only the evens. But, our
intuition is wrong. Both sets have the same cardinality. Both sets are the
same size. In fact, the full set of integers has the same cardinality as
the set of every integer divisible by one million. Or one million million.

Let's cover some theorems and proofs to illustrate the point:

Theorem: The cardinality of the set of integers has a 1:1 correspondence
with the set of naturals.

Proof: By definition, the set of integers Z={..., -2, -1, 0, 1, 2,...} and
the set of naturals N={1, 2, 3, ...}. Let us rearrange the set of integers
in this fashion: {0, -1, 1, -2, 2, -3, 3, ...}. From here, we can create a
function that has a 1:1 correspondence from the integers to the naturals, by
letting all the nonnegative numbers in Z map to the odd numbers in N, and
all the negative numbers in Z map to the even numbers in N. Thus, we can
see that the cardinality of N and Z are the same: i.e.: |Z| = |N|. QED

Theorem: The cardinality of the set of rationals has a 1:1 correspondence
with the set of naturals.

Proof: We use a similar argument that we used showing |Z| = |N|. Let Q be
the set of rational numbers. Let us rearrange the elements of Q in the
following matrix (let each number be both positive and negative):

    0/1 1/1 1/2 1/3 1/4 1/5 ...
    2/1 2/2 2/3 2/4 2/5 2/6 ...
    3/1 3/2 3/3 3/4 3/5 3/6 ...
    4/1 4/2 4/3 4/4 4/5 4/6 ...
    5/1 5/2 5/3 5/4 5/5 5/6 ...
    6/1 6/2 6/3 6/4 6/5 6/6 ...

Starting in the upper left corner of our matrix, move one element right,
then move down diagonal left to the left edge. Then, move one element down,
and move up diagonal right to the top edge. Continue in a like manner,
arranging the elements like so:

    Q={0/1, -1/1, 1/1, -2/1, 2/1, -3/1, 3/1, -2/2, 2/2, -1/2, 1/2, -1/3,...}

Reduce every rational to simplest form, and remove any duplicates. Redefine
Q to be this new set.

As in the previous proof, let all the nonnegative numbers in Q map to the
odd numbers in N, and let all the negative numbers in Q map to the even
numbers in N. Thus, the cardinality of N and Q are the same: i.e.: |Q| =
|N|. QED

These two proofs show that the set of integers and rationals are countable
by mapping each element to the naturals. Mathematics notation would be
something like this:


"Let f be a function that maps all the elements in the set of rationals to
the set of naturals."

Similar proofs can be constructed for any countable set: the set of prime
numbers, the set of numbers divisible by Pi, etc.). It gets interesting when
you get into uncountable sets, such as the irrationals or the Cantor Set.
Let us chalk up an idea illustrating that there is a 1:1 function that maps
every element in an uncounable set to every element in a different
uncountable set. For example:

Theorem: The cardinality of the entire real line is bijective to the unit
interval (0,1).

I won't outline the proof here (it's quite involved), but the idea is to
show that there are two functions that are both injective (say f(x) and
g(x)) in our sets. Then, you show that both functions are surjective with
the same. It involves carefully crafting the functions, and intermediate
sets to pull off the proof, but it's doable. Here is a full sketch of the
proof if you're interested:

The result of the proof states that the cardinality of the unit interval
[0,1] is the same as the cardinality of the entire real line R. In other
words, both sets are the same "size", which is entirely counterintuitive.

But this is very boring talking only about dense sets. It gets even more
fun talking about Borel sets, nowhere dense sets, first category sets and
residual sets. All topics for an undergraduate coure in Real Analysis.

Further in that course, you get to discuss the measure of sets, such as the
Lebesgue measure. For example, consider the following function:

    Let f(x) = 1, if x is rational
             = 0, otherwise
    be defined over the unit interval [0,1].

Elementary mathematicians will immediately recognize this function as being
discontinuous. Further, Calculus students may recognize that the Riemann
integral of f(x) is undefined. However, this isn't a problem with Lebesgue
integration. Although the set of rationals is dense, the measure of that
set is 0. Further, although the set of irrationals is also dense, it has a
measure of 1 (there are infinitely many more irrationals than rationals (a
fun probability thought: if you were to grab a number a random from the
unit interval, the probability of picking a rational is zero)).

So, because the measure of the rationals is 0 and the measure of the
irrationals is 1 in our function f(x), the Lebesgue integral tells us that
the value of the integral of f(x) is 1.

One last example to illustrate the point of the "size of sets". Suppose you
want to stay at a hotel. It has a finite number of rooms. There is a
vacancy, so you occupy the vacancy. Anyone else wishing to stay at the
hotel is out of luck, until someone leaves. Nothing new here.

Imagine now that you wish to stay at a hotel with an infinite number of
rooms. Further, suppose all the rooms are full- there are no vacancies. Can
you still find a room to spend the night? Sure. Just honk your horn in the
parking lot to wake everyone up, have them move to a room number that is
n+1 their original room number. After everyone makes the switch, room #1
just became available, and you can spend the night. Without anyone losing a
room. (This hotel is the Hilbert Hotel, after the famous mathematician
David Hilbert).

A good rule of thumb when dealing with infinities: your intuition about the
size of an infinite set is usually wrong. If you are familiar with the
Cantor Set, then you are doing pretty good. If you don't, and this is
blowing your mind, you are in good company. Infinities have plagued
mathematicians for centuries, and continue to do so today.

Anyway, I had to add my 2 cents on the matter. Math is a fun subject,
especially when talking about infinity.

. o .   o . o   . . o   o . .   . o .
. . o   . o o   o . o   . o o   . . o
o o o   . o .   . o o   o o .   o o o
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 527 bytes
Desc: Digital signature
Url : 

More information about the PLUG mailing list