Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can someone point me to a proof that the set of irrational numbers is uncountable? I know how to show that the set $\mathbb{Q}$ of rational numbers is countable, but how would you show that the irrationals are uncountable?

share|improve this question
    
See here for a proof. –  Hat Man Jun 8 at 6:47

5 Answers 5

up vote 51 down vote accepted

Given that the reals are uncountable (which can be shown via Cantor diagonalization) and the rationals are countable, the irrationals are the reals with the rationals removed, which is uncountable. (Or, since the reals are the union of the rationals and the irrationals, if the irrationals were countable, the reals would be the union of two countable sets and would have to be countable, so the irrationals must be uncountable.)

share|improve this answer

Let $b$ be an infinite binary sequence. Define $$ E(b) = \sum_{k=0}^\infty \left(\frac{1}{(2k)!} + \frac{b_k}{(2k+1)!}\right). $$ Wikipedia's proof of the irrationality of $e$ extends to show that $E(b)$ is irrational for every infinite binary sequence $b$. So if you believe that the set of all infinite binary sequences is uncountable, you must also believe that the set of irrational numbers is uncountable.

We could also define $$ E(b) = \sum_{k=0}^\infty \frac{b_k}{k!}, $$ but then $E(b)$ is irrational only if $b$ has infinitely many $1$s, or in other words, it doesn't end in an infinite sequence of zeroes.

share|improve this answer

Just for fun, we can prove this using way more machinery than necessary.

Assume for contradiction that the irrational numbers are countable. Now let $q_1,q_2,\ldots$ be an enumeration of the rationals, and let $r_1,r_2,\ldots$ be an enumeration of the irrationals. Now set $F_i=\mathbb R\setminus \{q_i,r_i\}$. Then the sets $F_i$ are open and dense in the usual topology on $\mathbb R$, and so by the Baire Category Theorem, $\bigcap_{i=1}^\infty F_i$ is dense in $\mathbb R$. However, $\bigcap_{i=1}^\infty F_i=\emptyset$ which is not dense, and hence the irrationals mustn't have been countable.

share|improve this answer

Assume that the set of irrational numbers is countable. This implies that we could show that every number in the set of irrational numbers has a one to one correspondance with the elements of N. Note that all irrational numbers are characterized by having an infinite number of decimal places. We can list these numbers as follows: N *R-Q* 1 .a_11 a_12 a_13 a_14… 2 .a_21 a_22 a_23 a_24... 3 .a_31 a_32 a_33 a_34... 4 .a_41 a_42 a_43 a_44... ... ... Choose some x that is an element of R-Q such that x = .b_1 b_2 b_3 b_4... where b = 1 if a_nn =/= 1 and 2 if a_nn = 2 for all n that is greater than or equal to 1.

QED


share|improve this answer

One can use a variant of the familiar Cantor diagonalization argument. Let us suppose that $x_1,x_2,x_3,\dots$ is an enumeration of the irrationals. Let $d_n$ be the $n$-th decimal digit of $x_n$ after the decimal point.

Let $w_n=5$ if $d_n$ is not equal to $3$ or $4$, and let $w_n=6$ if $d_n$ is equal to $3$ or $4$.

Now we give the decimal representation of an irrational $y$ not in the list $x_1,x_2,x_3,\dots$. Very roughly speaking, it is the number whose $n$-th digit after the decimal point is $w_n$. But some modification is made to ensure irrationality.

First we describe the $n$-th digit $e_n$ after the decimal point of $y$, where $w_n=5$. List these $n$ as $n_1,n_2,n_3,n_4,\dots$. Let $e_{n_1}=5$. Let $e_{n_2}=6$. Let $e_{n_3}=e_{n_4}=5$. Let $e_{n_6}=6$. Let $e_{n_7}=e_{n_8}=e^{n_9}=5$. Let $e_{n_{10}}=6$. Continue, leaving longer and longer strings of unchanged $5$'s.

The same procedure is used to produce the $n$-th digit $e_n$ after the decimal point of $y$, where $w_n=3$. Leave longer and longer strings of these unchanged, and switch the digit to $4$ occasionally.

The number $y$ we produce has decimal expansion which differs in the $n$-th place from the corresponding digit of $x_n$. The occasional switches from $5$ to $6$ or $3$ to $4$ ensure that the decimal expansion of $y$ is not ultimately periodic.

share|improve this answer

protected by Asaf Karagila Dec 9 '13 at 8:53

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.