In this reading, we will discuss the countability of sets. At the heart of this topic is the question:

How do we count the elements of a set?

Our answers to this question will hold important implications for our understanding of the cardinality (size) of infinite sets, and the nature of infinity.

What is counting?

Let’s consider the following set

\[ S = \{a,b,c,d,e\}. \]

If we were to set out to count the elements of this set, we might proceed as follows: point to the \(a\) and speak “one,” point to the \(b\) and speak “two,” then at the \(c\) with a “three,” giving \(d\) a “four,” and finally arriving at a “five” for \(e\).

Counting is the process of assigning the natural numbers (the counting numbers) to the elements of a set.

When we create this assignment, we are defining a mapping between the two sets, which also defines a counting function \(f:S\to\mathbb{N}\). But our counting function must obey a couple important rules: (i) every element in the set must get counted, (ii) no element may be counted more than once, (iii) no natural number can be skipped, and (iv) no natural number can be used more than once. These rules together tell us that our function is injective and surjective (one-to-one and onto), and it is therefore a bijection between our set \(S\) and the natural numbers \(\mathbb{N}\). This gives us the basic definitions of countability, which details our ability to count the elements of a set.

We can also use this idea of counting to help us define the size of various sets, what we call the cardinality of the sets, as well as help us arrive at a condition for two sets to be considered the same size.

Countability of the Even Numbers

A classic example used to demonstrate the idea of countable sets is the set of all even natural numbers (aka the set of positive even integers): \(\mathbb{E}^+=\{2,4,6,8,10,12,\dots\}\). Let’s prove that this set is countable by defining a counting function \(f:\mathbb{E}^+\to\mathbb{N}\).

Recall that the even natural numbers can be generated using the function \(g(n) = 2n, n\in\mathbb{N}\). If we take the inverse of this function, we will get a function mapping each even number to the natural number that it doubled. So define \(f(n) = n/2\). This function is clearly a bijection, and we can see the counting in action by listing out a few values:

• \(f(2) = 1\)
• \(f(4) = 2\)
• \(f(6) = 3\)
• \(f(8) = 4\)
• etc

Element-wise Functions and Ordered Lists

We were able to easily find a closed form expression for \(f\) in the case of the even numbers due to how they are defined. We shouldn’t expect this task to always be this easy. To aid us in proving countability, it is important to remember our original idea of counting: directly listing the elements one at a time and assigning natural numbers to them. This process is defining the counting function \(f\) element-wise. If we return to our counting example of the set \(S = \{a,b,c,d,e\}\), the counting we performed would correspond to the element-wise defined function: \(f(a)=1, f(b)=2, f(c)=3, f(d)=4, f(e)=5\).

We can apply this idea to infinite sets as well: even though we can never actually write down all of the infinite terms, an element-wise definition of a counting function would still prove that an infinite set is countable.

One interesting note to make about this approach to counting is that this process of counting creates an ordered list of the elements of the set. In fact, the ordering of that ordered list defines the counting function (the first thing on the list, the second thing on the list, etc). To be a proper counting function, this list is subject to several rules: it must be complete and unique (every element appears exactly once on the list). If the listing is complete and unique, then the list itself is actually the definition of a bijection with the natural numbers!

So to prove that an infinite set is countable, we simply need to describe a method for counting them (a method for listing them in order).

Counting the Even Numbers

Let’s return to our example from before of the even natural numbers \(\mathbb{E}^+\). To prove that this set is countable, let’s define a method for listing the even numbers: “list the even numbers in order of increasing magnitude.” Clearly this list will contain all of the even numbers, and we have not allowed for repeats. So it is a complete and unique listing, making the set countable. We can write out the first few elements of the list:

1. \(2\)
2. \(4\)
3. \(6\)
4. \(8\)
5. etc

Pausing to Reflect

So far, this concept of counting infinite sets has fit very well with our own intuitive understanding of counting. But the Theorem that we have now proved twice, that the even natural numbers are countable, should give us pause. How were we able to find a bijection between the natural numbers and the even natural numbers? One of those sets is a proper subset of the other. To get to the even natural numbers, we had to remove all of the odd numbers, which means we removed every other element of the set. How do these sets have the same cardinality, the same number of elements? Shouldn’t the even numbers be half the size of the natural numbers?

The answer to this question lies in the fact that both sets are infinite. We never run out of either even numbers or natural number to pair up: for each new even number we go to add to our growing list, there is always another natural number available, there is always a next spot on the list.

There is a famous analogy called “Hilbert’s paradox of the Grand Hotel” that explores this idea by envisioning a hotel with a countably infinite number of rooms (each room is numbered, i.e., has been assigned a natural number). If the hotel wants to accommodate the even numbers as guests, it can assign them to rooms in increasing order (just like our listing). We will never run out of rooms, so we can fully fit all even numbers. We could do the same for the odd numbers. But what if we already have the even numbers staying at the hotel, can we fit both groups? Yes, by instructing each even number to move to the room that is double its current room number. That frees up every other room, leaving enough space for the odd numbers!

Remaining Questions

Now that we have taken all this time and effort to understand how we count sets, it should be natural for us to ask the question: Are all sets countable?

The answer to this question will have far-reaching consequences. What would it mean for a set to be uncountable? Countably infinite sets are sets that are the same cardinality as the natural numbers. A set that isn’t countable would then be… somehow larger than the infinite set of natural numbers? How would that be possible?

We will prove this in lecture.