Countable and Uncountable Sets

Introduction: Let's compare some candy!

In this first post, let’s discuss the important math concept of countable and uncountable sets. If you know what is a real number and what is an integer, then it will be enough to understand this intriguing math concept.

Before we are going to start discussing countable and uncountable sets, let’s do a small experiment that will allow us to introduce a really important concept of bijection that is a foundation to understand those topics. Imagine that we have two piles of candy in front of us.

One pile consists of red candy, and another pile has blue candy. Then, we can ask a simple question:

Which pile does have more candy?

There are at least two ways to answer that question. First one, if we know how to count, then we can take the first pile and count how many candies we have and do the same with the second one. In the end, we are going to have two numbers that we are going to compare.

This approach has two disadvantages: we need to know how to count, and we do twice as much work as we need to go through two piles. Is it possible to compare two piles without counting? Yes! We will use a bijection.

Take candy from the first pile and find a pair by choosing candy from the second pile. Put them aside, take the second candy, and repeat the process.

Since we have a finite number of candy in the first pile, then we have three options: we will have no candy in the first pile and some left in the second, no candies in both piles, and, finally, some candy in the first and no candies in the second. The second case means that we have the same amount of candies in both piles i.e. we have a bijection between two piles (sets).

As a summary:

A set is a collection of any elements that have a common feature or no feature at all.

A bijection between sets A and B is the correspondence that allows finding for any element a in A, a unique element b in B, and vice versa.

So, we can see that we can compare the number of elements in the finite sets by trying to establish a bijection between them.

Moving Towards Infinity

As a next step, what would we do if have a pile with an infinite number of candy? From our algebra class, we know that we have at least two infinite sets: integers and real numbers.

Surprisingly, those two infinities are not the same. We say that integers are countable and real numbers are uncountable.

A set A is countable if we can least all elements in set A by assigning them consecutive numbers 1, 2, 3, … etc.

For example, natural numbers 1, 2, 3, … are countable as we have one-to-one correspondence. Indeed, 1 goes to 1, 2 goes to 2, etc.

Let’s show that integers are also countable. If we write integers as a list

…, -2, -1, 0, 1, 2, …

then we don’t know what numbers should be first and how to list them. However, we can rewrite them as 0, 1, -1, 2, -2, …, so we can see that 1stnumber is 0, 2nd one is 1, etc.

Therefore, integers are countable. Using a more advanced language, we can see that we established a bijection between two sets A and B where A is the set of natural numbers and B is the set of integers.

Not All Infinities are The Same

We have discussed the definition of a countable set. But, what is an uncountable set R? It’s the set that has too many elements. In other words, we cannot enumerate elements in R, or strictly speaking, we cannot list them (there is no bijection between R and natural numbers).

For example, consider real numbers, and let’s show that they are uncountable. We are going to show that by contradiction. Assume that the set of real numbers is countable. Then, a subset (0,1) of real numbers is also countable.

Indeed, if we can list elements in the bigger set R, then we can list elements in the smaller set (0,1) by just remunerating them. We are going to obtain a contradiction by showing that (0,1) is uncountable.

So, if (0,1) is countable, then we can list all elements in (0,1) by writing them in decimal notation.

However, we can create an element that belongs to (0,1) but which we did not take in account in our list. Just take the elements whose first digit after zero is going to be different from alpha 11, the second digit is going to be different from alpha 22, etc. In other words, we will create the element beta of the following form:

First, we can see that beta belongs to (0,1) as it starts with zero. Also, it does not lie in our original list as every number in the list has at least one digit that is different from beta. Therefore, we obtained the desired contradiction that (0,1) is not countable i.e. the set of real numbers is not countable.

Finale

We can see that our concept of infinities can be misleading as who might think that we have different types of infinities in terms of their sizes. Yes, we can compare infinities. We will use a fancy word for that: cardinality. We will discover this together in my next blog posts. Finally, the cardinality of an uncountable set is bigger than a countable one as we literally cannot list elements of an uncountable set, but we can list elements for a countable one. Now, we know how to count uncountably many apples.