Uncountable

Uncountable
Uncountably Infinite

Describes a set which contains more elements than the set of integers. Formally, an uncountably infinite set is an infinite set that cannot have its elements put into one-to-one correspondence with the set of integers.

For example, the set of real numbers is uncountably infinite.

Example

Problem: Show that the set of all real numbers between 0 and 1 is uncountable using Cantor's diagonal argument.

Step 1: Assume, for contradiction, that the real numbers between 0 and 1 are countable. This means we could list every such number in a sequence:

r_1 = 0.d_{11}d_{12}d_{13}\ldots \quad r_2 = 0.d_{21}d_{22}d_{23}\ldots \quad r_3 = 0.d_{31}d_{32}d_{33}\ldots

Step 2: Suppose the first few entries on our list are as follows. Each number is written in its full decimal expansion:

r_1 = 0.\mathbf{5}1749\ldots \quad r_2 = 0.3\mathbf{2}394\ldots \quad r_3 = 0.81\mathbf{6}05\ldots \quad r_4 = 0.240\mathbf{7}8\ldots

Step 3: Construct a new number by looking at the diagonal digits (the bold digits: 5, 2, 6, 7, …) and changing each one. A simple rule: if the digit is not 1, replace it with 1; if it is 1, replace it with 2. The new number starts:

s = 0.1112\ldots

Step 4: The number s differs from r_1 in its 1st decimal place, from r_2 in its 2nd decimal place, from r_3 in its 3rd place, and so on. Therefore s is not equal to any number on the list.

s \neq r_n \text{ for every } n

Step 5: But s is a real number between 0 and 1, so it should have been on our supposedly complete list. This is a contradiction. Our initial assumption was wrong.

Answer: No complete list of all real numbers between 0 and 1 can exist, so the interval (0, 1) is uncountable.

Frequently Asked Questions

Why are the real numbers uncountable but the rationals are countable?

The rational numbers, despite being dense on the number line, can be systematically listed (for instance, by arranging them in a grid of numerator and denominator and sweeping diagonally). The real numbers include all irrational numbers as well, and Cantor's diagonal argument proves that no such listing is possible for them. In a precise sense, the 'extra' irrational numbers make the reals a strictly larger infinity than the rationals.

Are there different sizes of uncountable sets?

Yes. The set of real numbers has cardinality denoted by c (the cardinality of the continuum). The power set of the reals — the set of all subsets of the reals — is strictly larger still. In general, for any set A, its power set has a greater cardinality than A itself (Cantor's theorem), so there is no largest infinity.

Countably Infinite vs. Uncountable

A countably infinite set (like the integers or rationals) can be listed in a sequence — you can assign a unique natural number to each element. An uncountable set is too large for this: no sequence, however cleverly arranged, will cover every element. Both are infinite, but uncountable is a strictly larger type of infinity. The natural numbers are countably infinite with cardinality ℵ₀, while the real numbers are uncountable with cardinality c > ℵ₀.

Why It Matters

The distinction between countable and uncountable is foundational in modern mathematics. It shows that not all infinities are the same size — a surprising result first proved by Georg Cantor in 1874. This idea underpins measure theory, probability, and real analysis, where many key theorems depend on whether a set is countable or uncountable.

Common Mistakes

Mistake: Thinking that 'uncountable' simply means 'very large' or 'larger than any finite number.'

Correction: Many infinite sets, such as the integers, are still countable. Uncountable specifically means there is no one-to-one correspondence with the natural numbers. Size alone does not determine uncountability — structure matters.

Mistake: Believing the rational numbers must be uncountable because they are densely packed between every two real numbers.

Correction: Density does not imply uncountability. The rationals are dense on the number line yet countable, because they can be listed systematically. Cantor's diagonal argument fails for the rationals precisely because their decimal expansions are eventually repeating, and the constructed diagonal number is typically irrational.

Related Terms

Countably Infinite — An infinite set that can be listed sequentially
Set — A collection of distinct objects
Real Numbers — The standard example of an uncountable set
Cardinal Numbers — Numbers that measure the size of sets
Infinite — A set that is not finite; includes both types
One-to-One Function — Key concept in defining countability
Integers — A countably infinite reference set
Element of a Set — An individual member belonging to a set