Uncountable Set

set-theory

Definition

Uncountable Set

An uncountable set is an infinite set that is too large to enumerate with the natural numbers, i.e. there is no bijection between and .

Equivalently, its elements cannot be enumerated as a single infinite sequence.

Examples:

Examples

Diagonalisation: Assume that is countable. Then, there exists a bijection , i.e. every natural number can be represented as a sequence of zeros and ones.

Define a new sequence that flips the -th bit of the -th listed sequence.

Trivially, . Thus but is not equal to any , contradicting that that is surjective. Therefore, the assumption that is countable is wrong and is uncountable.

Visually:

Diagonalisation: Assume that is countable. Then, there exists a bijection .

All real numbers is uniquely identified by its decimal digits and can be represented by:

Since is injective, . Therefore, every has its own selection of :

Visually, a 2D matrix appears which can be used to create a diagonal.

To show is that there is no . As said above, real numbers are uniquely identified by their digits, i.e. if one digit differs, they are considered distinct. Let be a helper sequence that ensures that the -th digit is always different from each sequence:

Further, let’s define as:

because . because , etc. Therefore:

which means a number is found that does not occur in , which is contradictory since is surjective. Hence, the initial assumption is wrong and is uncountable.