MathFundamentalsSets

Countable and uncountable sets

Provided by: Edvancium

9 minutes read

You already know about basic set operations. Let's dive deeper into set theory. Here you'll learn about equinumerous, countable and uncountable sets. These concepts are essential for the mathematical logic and proving of different theorems.

As you progress in mathematics, more and more complicated sets begin to appear. If you are able to determine whether they are countable or uncountable, it will be easier to study them.

For example, when a set is countable, you can think of its elements as an ordered sequence. This can make it easier to handle or give a clearer idea of its structure. On the other hand, when a set is uncountable, it has a very large size, and you must develop specific techniques to deal with its elements.

Equinumerous sets

Imagine that you have $2$ sets: $A$ and $B$ , and want to compare their sizes. If these sets have finite amounts of elements, it's obvious how to do it: just count the elements of these sets and compare the results. But what should you do if sets have infinite amounts of elements? The answer is to build a one-to-one correspondence. A one-to-one correspondence is a matching between the elements of these two sets which connects every element $a$ of the set $A$ with only one element $b$ of the set $B$ and every element $b$ of the set $B$ with only one element $a$ of the set $A$ .

One-to-one correspondence

So, sets $A$ and $B$ are equinumerous sets if a one-to-one correspondence between these two sets exists.

Let's take a look at some examples to understand this term better.

Imagine that you have two sets $A = \{1,2,3\}$ and $B = \{a, b,c\}$ . You can easily build a one-to-one correspondence between these sets: $1 \rightarrow a \\ 2 \rightarrow b\\ 3 \rightarrow c$
Imagine that you have two sets $A = \{1,2,3\}$ and $B = \{a,b,c, d\}$ . It's impossible to build a one-to-one correspondence between these two sets because they have different amounts of elements. So, these sets are not equinumerous.
Imagine a house and a parking lot near it. If the amount of flats in this house is equal to the number of places at the parking lot, it's possible to build a one-to-one correspondence between the set of flats and the set of places at the parking lot. These sets then are equinumerous. But if there is an extra parking place (e.g., for guests), it is impossible to match one and only one with one and only one lot.

Finite and infinite sets

At first, you should focus on the definition of finite and infinite sets.

A set $A$ is called a finite set if it consists of a finite number of elements. Formally, it means that there is a one-to-one correspondence: $A \rightarrow \{1,2,...,n\}$ for some non-negative integer number $n$ . Informally, this means that you can find a way to count all the elements of the set and find the exact number of elements in the set.

Here are some examples of finite sets.

You can represent all letters of the English alphabet as a set $A$ :

$A = \{A, B,C,D, ...Z\}$

There are 26 elements in this set, so you can build a one-to-one correspondence between this set $A$ and the set of first $26$ natural numbers $\{1,2,3,4,...,26\}$ :

$A \rightarrow 1 \\ B \rightarrow 2 \\ C \rightarrow 3 \\ D \rightarrow4 \\ ...\\ Z \rightarrow 26$

You know that any number in the decimal numerical system can be represented using $10$ digits $\{0,1,2,3,4,5,6,7,8,9\}$ . You can also build a one-to-one correspondence between this set of digits and the set of the first $10$ natural numbers $\{1,2,...,10\}$ :

$0 \rightarrow 1 \\ 1 \rightarrow 2 \\ ...\\ 9 \rightarrow 10$

Surnames of children in a class can also be represented as a set. You can order their surnames alphabetically. If some students have exactly the same surnames, let's order them by their names. If they are namesakes, let's order them by the date of birth. So, by ordering the surnames of children you've just built a one-to-one correspondence between the set of surnames and the set of numbers $\{1,2,3,\dots, n\}$ , $n$ is equal to the number of children in the class. It's clear that every surname is connected with only one number, and every number is connected with only one surname.

So, this set is also finite.

You may have noticed that, in fact, you have just counted the elements in these sets. By definition, you can do that for every finite set. This means that all finite sets are countable sets.

Here's a real-life example of a finite countable set. Names of people who bought tickets to a train can be represented as a set. Every person who buys a ticket, reserves a seat number. So, you have two sets — names of passengers and seat numbers. Let's assume that every person can buy only one ticket. Then the one-to-one correspondence between these sets is built while selling the tickets because there's only one seat for every person and there's only one person for every seat. So, the set of names is a countable finite set.

A set $B$ is called infinite if it is not finite. It means that the number of elements in this set is greater than any non-negative number $n$ . But can the infinite set be countable? Can you find the rule on how to count the elements in this set? To answer this question, you need to formally define what a countable set is.

Countably infinite sets

The set of natural numbers $\mathbb{N}$ is the set of numbers used for counting: $\{1,2,3,...\}$ . Some mathematicians include 0 in the set of natural numbers, and some don't. Let's not include 0 in this set.

Since we've introduced the set of natural numbers, we can expand the definition of countable sets. A set $C$ is called countable if it is finite or if there is a one-to-one correspondence between this set and the set of natural numbers $f:C \rightarrow \mathbb{N}$ . This paragraph will focus on countably infinite sets. These are countable sets that are infinite.

If you include $0$ in the set of natural numbers, you'll get the set of whole numbers $\mathbb{N}_{0}$ : $\{0,1,2,3,...\}$ .

Why is the set of whole numbers countable?

$\mathbb{N}$ and $\mathbb{N}_{0}$ are equinumerous, because you can build a one-to-one correspondence using the following method:

$0 \rightarrow 1 \\ 1 \rightarrow 2 \\ ...\\ n \rightarrow n+1 \\ ...$ Now you can use the $\mathbb{N}_{0}$ instead of $\mathbb{N}$ to prove that a set is countable, because you've shown that $\mathbb{N}$ and $\mathbb{N}_{0}$ are equinumerous.

There are also two other countably infinite sets of numbers.

The set of integers $\mathbb{Z}$ is the set of all natural numbers, their opposites, and zero $\{...,-3,-2,-2,0, 1,2,3,...\}$ .

The set of rational numbers $\mathbb{Q}$ is the set of numbers that can be represented as a fraction $\frac{p}{q}$ , where $p,q$ are integers and $q\neq 0$ .

Why are the sets of integers and rational numbers countable?

Let's show that $\mathbb{Z}$ and $\mathbb{N}$ are equinumerous. You should build a one-to-one correspondence using the following method.

You can write $\mathbb{Z}$ as $...,- n,...,-2,-1,0,1,2,...,n,...$ and change positions of its elements to get $0,1,-1,2,-2,...,n,-n,...$ .

Now you can build a one-to-one correspondence using the following formula: $n \rightarrow 2\cdot n, n \geq 0 \\ n \rightarrow -2\cdot n-1, n \lt 0$

The sets Z and N are equinumerous

So, we've built a one-to-one correspondence and shown that $\mathbb{Z}$ is countably infinite.

Let's also show that $\mathbb{Q}$ and $\mathbb{N}$ are equinumerous. You should build a one-to-one correspondence using the following method.

You can write $\mathbb{Q}$ as the following table and enumerate all the numbers using the way shown on the picture. We'll skip all the reducible fractions we've already enumerated like $\frac{2}{2} = 1$ and enumerate only irreducible fractions.

$\begin{matrix} 0 &\to& 1 && -1&\to& 2 && -2&\to &3 & \dots\\ &&\downarrow &\nearrow&&\swarrow && \nearrow && \swarrow \\ &&\frac{1}{2} && - \frac{1}{2} && \frac{2}{2} &&- \frac{2}{2} && \frac{3}{2} & \dots \\ && &\swarrow&&\nearrow && \swarrow && \\ &&\frac{1}{3} && - \frac{1}{3} && \frac{2}{3} &&- \frac{2}{3} && \frac{3}{3} & \dots \\ &&\downarrow &\nearrow&&\swarrow \\ &&\frac{1}{4} && - \frac{1}{4} && \frac{2}{4} &&- \frac{2}{4} && \frac{3}{4} & \dots \\ &&&\swarrow \\ &&\frac{1}{5} && - \frac{1}{5} && \frac{2}{5} &&- \frac{2}{5} && \frac{3}{5} & \dots \\ &&&&&&\dots \end{matrix} \\ \begin{matrix} \mathbb{Q}: & 0 & 1 &\frac{1}{2} & -1 & 2 &-\frac{1}{2} &\frac{1}{3} &\frac{1}{4} &-\frac{1}{3} & -2 & 3 & \frac{2}{3} & -\frac{1}{4} & \frac{1}{5} & \dots \\ & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \dots\\ \mathbb{N}:& 1 &2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & \dots \end{matrix}$

So, we've built a one-to-one correspondence and shown that $\mathbb{Q}$ is countably infinite.

Here's a real-life example of a countably infinite set. Imagine a river in a jungle full of crocodiles. The river is quite narrow, so the crocodiles can only swim one by one. This river is a paradise for crocodiles, they always come there and swim, so the flow of crocodiles will never end. You're standing at the bank of this river, so you can count every crocodile which swims by and assign a number to it. But since more crocodiles are coming to this river, even if you spend your whole life counting them, there'll be no end. So, the set of these crocodiles is a countably infinite set.

Uncountable sets

A set is called uncountable if it is not countable.

First, let's take a look at the straight-line segment $[0, 1]$ . There are many points in this segment — both rational and irrational.

You already know, that irrational numbers are numbers that are not rational. It means that they can't be expressed as a fraction $\frac{p}{q}$ , where $p,q$ are integers and $q\neq 0$ . Here are examples of irrational numbers: $\pi, e, \sqrt{2}$ .

Line segment is an infinite uncountable set

Is the amount of dots finite or infinite? Let's take the midpoint of this segment. You'll get two new segments, and you can take their midpoints. Now you have 3 points. You can split these segments again and get 7 midpoints. You can do an infinite number of splits, since the segment $[0, 1]$ has no holes and you're not limited in the size of the segments you get — they can be really small. So, this line segment is an infinite uncountable set.

The set of real numbers $\mathbb{R}$ is the union of the set of rational numbers and the set of irrational numbers. It's also an uncountable set.

The set of real numbers

Conclusion

A one-to-one correspondence is a matching between the elements of two sets $A$ and $B$ which connects every element $a$ of the set $A$ with only one element $b$ of the set $B$ and every element $b$ of the set $B$ with only one element $a$ of the set $A$ .
Two sets are equinumerous if a one-to-one correspondence between them exists.
A set $A$ is called finite if there is a one-to-one correspondence: $A \rightarrow \{1,2,...,n\}$ for natural number $n$ .
A set $C$ is called countable if it is finite or there is a one-to-one correspondence between this set and the set of natural numbers $f:C \rightarrow \mathbb{N}$ .
The set of integers $\mathbb{Z}$ and the set of rational numbers $\mathbb{Q}$ are countably infinite sets.
The set of real numbers $\mathbb{R}$ is an uncountable set.

20 learners liked this piece of theory. 1 didn't like it. What about you?

Report a typo