Countable Sets

Let’s explore if two sets have the same number of elements. If both sets are finite, we can determine this easily by simply counting the elements in both sets. If the count of both sets matches, they contain the same number of elements. Otherwise, they do not. However, this strategy fails if the sets are infinite. We have to devise another method in which we do not count. Georg Cantor (1845-1918) was the first to suggest such a technique. Surprisingly, it turns out that all infinite sets don’t have the same size. We can arrive at interesting conclusions based on the relative sizes of the set of positive integers and the size of other infinite sets.

What is a countable set?

A set is countable if it is finite or has the same number of elements as the set of positive integers. This means that any finite set is also a countable set. The difficult task is to determine if an infinite set is countable. This can also be done if we can determine if the infinite set has the same size as the set of positive integers.

Note: A countable infinite set is also called a denumerable set.

For example, let’s think of a classroom where every student has a chair and no empty chairs. Without counting the students or the chairs, we can say that there are as many chairs in the classroom as the number of students. What are we doing in this case? We are checking if students and chairs can be perfectly paired up; if yes, their count is the same; otherwise, it is not. Elements of two sets can be paired up if and only if there is a one-to-one correspondence or a bijection between the two sets. This was exactly the idea given by Cantor—to find a bijection between the two sets instead of counting their elements. Let’s look at a few examples of countable sets.

Even positive integers

To see why a set of even positive integers is countable, we present a bijection from the set of positive integers to the set of even positive integers. The set of even positive integers is defined as follows: