Cartesian Products of Countable Sets

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

(No.)

Cartesian Products and Countable Sets

Based on the book’s discussion of the countability of the set of rational numbers, and the discussion of Cartesian products of countable sets.

Rational Numbers

What would you say the main idea is behind how the book creates a bijection from the positive rational numbers to the natural numbers?

Assigning natural numbers to rationals along diagonals of a table:

In particular, this creates a bijection between natural numbers and positive rationals by “walking” through the  table along diagonals through the upper left corner; any time you reach a rational number in reduced form, assign it the next not-yet-used natural number.

Despite being described as an English procedure rather than as a mathematical formula, we can argue that this pairing between natural numbers and rationals is indeed a bijection:

• It’s an injection, because if two rationals, u and v, pair with the same natural number, it means that u and v appear at the same place in the “walk,” i.e., u = v.
• It’s a surjection, because every rational number, say q, lies somewhere in some diagonal; since all diagonals are finitely long, the “walk” will eventually reach q and assign it a natural number.

The General Claim

Theorem: If A and B are countably infinite sets, then A × B is countably infinite.

We wrote the proof formally with LaTeX. It’s the second proof in this source file and this PDF output.

The logic of the proof adapts the diagonals-in-a-table logic of the proof about positive rationals.

The proof also demonstrates a useful new LaTeX feature, namely including images or pictures in a LaTeX document. In this case I used PowerPoint (you can use any drawing program you like) to create a nice-looking picture of the table, and then saved that picture as a “.PNG” graphics file in the same folder as my LaTeX source. LaTeX’s \includegraphics command (made available by using package “graphicx,” i.e., by saying \usepackage{graphicx} in the document’s preamble) will then insert the graphics file in your document. The optional argument scale to \includegraphics (i.e., \includegraphics[scale=x]…) will scale the image by scale factor x. I usually center images by putting the \includegraphics command inside a center environment, as I did with this example.

Next

Show that there really are uncountable sets.

Please read “Beginning Activity 1 (The Game of Dodge Ball),” “Decimal Expressions for Real Numbers,” and “Uncountable Subsets of ℝ” in section 9.3 of the textbook.

Please also contribute to this discussion of the “dodge ball” game.

Next Lecture