Countable Sets

Return to Course Outline

Previous Lecture

End-of-Semester Announcements

Class schedule for next week:

• Monday (May 10) is an “honorary Tuesday,” i.e., classes meet according to the Tuesday schedule. We don’t have class.
• Tuesday (May 11) is an honorary Wednesday. We do have class, at the usual time and place (12:30, Welles 140).
• Wednesday (May 12) is an honorary Thursday. We don’t have class.

SOFIs are currently under way. I do read and consider what you have to say; it has been valuable in the past in affecting what I do (e.g., individual meetings for grading) or don’t (e.g., daily use of a “random names” list) do in classes. So please fill out a SOFI for this class, it might have on impact on future classes you or friends take from me.

Anything You Want to Talk About?

(No.)

Unions of Countable Sets

Based on the first part of section 9.2 in the textbook and this discussion of countably infinite sets.

The Countably Infinite Motel

(From the discussion.)

The first question that came up about the countably infinite motel is what does it even mean to say that the motel is “full” after accommodating every passenger on a countably infinite bus? Since infinity is more of an idea than an actual number, how can you say that there’s a person in “every” room? It turns out that our notion of equivalent cardinality has an answer: there is a bijection between people from the bus and rooms in the motel; since a bijection is a surjection (i.e., “onto,” i.e., something maps to every element of the codomain), every room in the motel has a person mapped to it.

The motel’s first problem from the discussion is how to fit 4 more people in after filling every room from the countably infinite bus. They can do this by moving people to new rooms according to a scheme that is an injection (i.e., one-to-one, i.e., everyone gets their own room), but not a surjection (i.e., it leaves 4 rooms empty). One way to do this is move everyone 4 rooms down the hall, leaving rooms 1, 2, 3, and 4 vacant:

Now what happens when another countably infinite bus shows up? Is there another way to reassign the existing guests that leaves a countably infinite number of rooms free? It turns out that there is, namely move everyone to a room whose number is twice their current room number. This means the even numbered rooms are all occupied, but all the odd numbered ones are free. And conveniently, the set of odd natural numbers is countably infinite (see Beginning Activity 1 in section 9.1 of the textbook).

Generalization

The countably infinite motel fitting in two countably infinite busloads of guests is an instance of the following theorem:

The union of two disjoint countably infinite sets is countably infinite

or, stated in a way that gives names to the sets,

If A and B are countably infinite, then A ∪ B is countably infinite.

Or, less formally, “infinity plus infinity is still infinity.”

How would you prove this theorem?

As with many proofs that a set is countably infinite, find a bijection between the union and the natural numbers.

You know there are bijections between A and the naturals, and between B and the naturals. Call those bijections f and g, respectively.

Now imagine a new function h : A ∪ B → ℕ defined as

• h(x) = 2 f(x) if x ∈ A
• h(x) = 2 g(x) - 1 if x ∈ B

The idea is similar to fitting two buses into the motel, namely to map one set to even numbers and the other to odd ones.

We had to adjust the mapping to odd naturals to make sure it is a surjection from B to the odd naturals, i.e., it maps something to each odd natural numbers. Our first version used 2 g(x) + 1, which couldn’t map anything to 1. To check that the new version does, we want to find x such that h(x) = 1

Since 1 is odd, this means we need 2 g(x) - 1 = 1

Or g(x) = 1, which is a natural number, and so is the image of some element of B (since g is itself a bijection and thus a surjection).

This problem with getting a new function that maps something to 1 shows that it’s not necessarily true that a function we construct to map between some set and the natural numbers is a bijection just because we want it to be. We have to prove that it is. We haven’t done that proof completely yet, we just checked one case within it.

What we did in class is an outline of the proof that the union of two disjoint countably infinite sets is countably infinite. I wrote the proof out in full after class; you can download its LaTeX source and PDF output from Canvas. It’s the first proof in both files.

Next

What about “infinity times infinity”? Or, more accurately, the cardinalities of sets of pairs made from countably infinite sets.

Please read “The Set of Positive Rational Numbers” and “Countably Infinite Sets” in section 9.2 of the textbook.

Please also contribute to this discussion of Cartesian products of countably infinite sets.

Next Lecture