Can We Prove the Irrationals Are Uncountable Without Cantor’s Diagonal Argument?

The irrational numbers are uncountable, and you can prove this without using Cantor’s familiar decimal diagonal argument. The cleanest route is to use the nested-interval property of the real numbers.

The proof has two parts. First, show that if the irrationals were countable, then all real numbers would be countable. Second, prove directly that the real numbers cannot be listed by constructing a real number that is missing from any proposed list.

Countable sets involved

The rational numbers $\mathbb{Q}$ are countable. One way to see this is to write each rational number as $p/q$, where $p\in\mathbb{Z}$ and $q\in\mathbb{N}$, and arrange the pairs $(p,q)$ in a grid. Reading the grid by diagonals gives a list, with repetitions removed.

Suppose, for contradiction, that the irrational numbers were also countable. Then there would be lists

$$\mathbb{Q}=\{q_1,q_2,q_3,\ldots\}$$

and

$$\mathbb{R}\setminus\mathbb{Q}=\{i_1,i_2,i_3,\ldots\}.$$

Every real number is either rational or irrational. Interleaving these two lists would therefore produce a list of all real numbers:

$$q_1,i_1,q_2,i_2,q_3,i_3,\ldots$$

Thus, the assumption that the irrationals are countable would imply that $\mathbb{R}$ is countable.

It remains to show that $\mathbb{R}$ cannot be listed.

A nested-interval proof that the reals are uncountable

Assume that all real numbers have been listed:

$$\mathbb{R}=\{x_1,x_2,x_3,\ldots\}.$$

We will construct a real number that is different from every $x_n$.

Start with the closed interval

$$J_0=[0,1].$$

Now divide $J_0$ into three closed subintervals of equal length. At least one of those subintervals does not contain $x_1$. Choose such a subinterval and call it $J_1$.

Next, divide $J_1$ into three equal closed subintervals. At least one does not contain $x_2$. Choose one and call it $J_2$.

Continue this process. At stage $n$, divide $J_{n-1}$ into three equal closed subintervals and choose one that does not contain $x_n$. The intervals satisfy

$$J_0\supseteq J_1\supseteq J_2\supseteq\cdots$$

and their lengths satisfy

$$\operatorname{length}(J_n)=\frac{1}{3^n}.$$

For example, the first few choices might look schematically like this:

$$J_0=[0,1],\qquad J_1\subseteq J_0,\qquad J_2\subseteq J_1,\qquad J_3\subseteq J_2.$$

The exact intervals depend on the proposed list, but every choice is possible because one point cannot belong to all three separated thirds.

Why the intervals have a common point

The nested-interval property of the real numbers says that a nested sequence of nonempty closed intervals whose lengths approach zero has exactly one common point. Therefore, there is a real number $x$ such that

$$x\in J_n\quad\text{for every }n.$$

But $J_n$ was chosen not to contain $x_n$. Since $x$ belongs to $J_n$, it follows that

$$x\neq x_n\quad\text{for every }n.$$

So $x$ is a real number that does not occur anywhere in the alleged list

$$x_1,x_2,x_3,\ldots.$$

This contradicts the claim that the list contains every real number. Hence $\mathbb{R}$ is uncountable.

Finish the argument for the irrationals

If the irrational numbers were countable, then the rationals and irrationals together would make $\mathbb{R}$ countable. But the nested-interval argument proves that $\mathbb{R}$ is uncountable. Therefore, the irrational numbers must be uncountable.

Symbolically, if $I=\mathbb{R}\setminus\mathbb{Q}$ were countable, then

$$\mathbb{R}=\mathbb{Q}\cup I$$

would be a union of two countable sets and hence countable. This is impossible, so $I$ is uncountable.

What “without Cantor” means here

This proof does not use Cantor’s decimal diagonal construction. It does, however, use a theorem about the real numbers that is closely related in spirit: the nested-interval property, which depends on the completeness of $\mathbb{R}$.

If “without Cantor” means avoiding every theorem associated with Cantor, then the request needs clarification. Standard proofs of the uncountability of the reals rely on some equivalent foundational fact, such as the nested-interval theorem, the least-upper-bound property, or the Baire category theorem. What can be avoided is the particular diagonalization with decimal expansions.

Common mistakes

Showing only that the rationals are countable

The fact that $\mathbb{Q}$ is countable does not by itself prove that the irrationals are uncountable. You also need an argument showing that $\mathbb{R}$ is uncountable.

Assuming the complement of a countable set is automatically uncountable

That statement is true when the ambient set is known to be uncountable. The fact that $\mathbb{R}$ is uncountable must therefore be established first.

Constructing a number outside only the irrational list

If you directly avoid each listed irrational, the resulting number might be rational. The safer argument combines the rational and irrational lists into a list of all real numbers, then constructs a real number outside that complete list.

Forgetting completeness

The claim that the nested closed intervals share a point is not true in every ordered number system. It relies on the completeness of the real numbers; for example, analogous intervals can have no common rational point when considered inside $\mathbb{Q}$.