Thursday 10 November class

• Activity: "Dodge Ball" from The Heart of Mathematics

Topics: How to count/measure infinite sets!

First we have to examine closely what we do when we count a finite set. Essentially we are making what is called a one-to-one correspondence between the first however-many counting numbers (the natural numbers) and the items that we are counting.

The idea of one-to-one correspondence is what will carry over into infinite sets.

• David Hilbert's Hotel, and some theorems about the sizes of some infinite sets: See the Science4All article. (Warning: it contains math notation that may not display correctly on a phone. Here is another article which uses less math notation but has fewer details)

If an infinite set of numbers (or anything else) can be put into a one-to-one correspondence with the st of natural numbers (that is, it can be put into the form of an infinite list), we say it is a countable set. In the Science4All article, countable sets are called listable, which is a good name for them but is not standard.

First we discussed Hilbert's infinite hotel. Even if every room is occupied, we can accommodate an additional guest, or even a countably infinite number of guests! So you can say "infinity plus 1 is infinity" or "infinity plus infinity is infinity" - but wait! That second statement needs some care, because it turns out there are different sizes of infinity.

We showed the following in class:
 • The whole numbers are countable (listable)
 •  The even numbers are countable (listable)
 •  The integers are countable (listable) - this is also proved in some of the videos linked below
 •  The rational numbers are countable (listable) - this is also proved in some of the videos linked below
 • The real numbers are not countable. In other words, the set of real numbers is larger than the set of natural numbers (or even the set of rational numbers)!
The implication of this is that the set of irrational numbers is uncountable, which means that it is reasonable to say that there are more irrational numbers than rational numbers. (More on this next time.)

Look for the proofs of the following theorems in the article or in this video and this video (for the Cantor proof) , and here is another video as well. (all three of them are worth watching.)

    • Theorem: The integers are countable (listable)
    • Theorem: all countable (listable) sets have the same size (same number of elements)
    • Theorem: The rational numbers are countable (listable)
   And then the big one:
    • Theorem: The real numbers are uncountable (they are not listable).
The last one is Cantor's diagonal proof, and it relies on the strategy that Player 2 can use for "Dodge Ball" to make sure they always win.


Homework:
• Journal assignment: write the proofs of the Theorems listed above in your own words.
• Prove that the odd numbers are countable (listable) by pairing them up with the natural numbers. (Make a one-to-one correspondence with the natural numbers. Watch the videos linked above if you have doubt about what this means.)

• Next time: Power sets and the Continuum Hypothesis. (The continuum is another name for the real number line.)
  See Math is Fun on sets for some set notation that we will be using.