Here are two false proofs of the fact that $\Bbb Q$ is uncountable. From Stephen Abbott's Understanding Analysis.

Proof 01

Lemma:(Nested Interval Property - NIP). For each $n ∈ N$, assume we are given a closed interval $I_n = [a_n, b_n]$. Assume also that each I_n contains I_{n+1}. Then, the resulting nested sequence of closed intervals $$I_1 ⊇ I_2 ⊇ I_3 ⊇ I_4 ⊇ · · ·$$ has a nonempty intersection.

Assume, for contradiction, that $\Bbb Q$ is countable. Thus we can write $\Bbb Q =\{r_1, r_2, r_3, . . .\}$ and, construct a nested sequence of closed intervals with $r_n \not \in I_n$. Our construction implies $\bigcap_{n=1}^{\infty} I_n = ∅$ while NIP implies $\bigcap_{n=1}^{\infty} I_n \neq ∅$ . This contradiction implies $\Bbb Q$ must therefore be uncountable.

Proof 02

Theorem : The open interval $(0,1)$ is uncountable.

Proof: Lets assume that $(0,1)$ is countable and thus let $f:\Bbb N\to (0,1)$ be a bijective function. Then let $f(m) = 0.a_{m1}a_{m2}a_{m3} . . . .$ (decimal representation). Let $x=0.b_1b_2...$ with $b_i=3$ if $a_{ii}=2$ else $b_i=2$. Its not difficult to see x is a different number from the counted set a contradiction.

Now the question is: Every rational number has a decimal expansion, so we could apply this same argument to show that the set of rational numbers between $0$ and $1$ is uncountable. However, because we know that any subset of $\Bbb Q$ must be countable, the proof of Theorem.

I can't figure out the flaws in these two arguments.

  • 1
    $\begingroup$ For proof 1, you want $\cap$, not $\cup$, in both places (not just the second). And the way out of the contradiction is that the mutual intersection contains a number that need not be in $\mathbb{Q}$. For proof 2, $f(m)$ yields an irrational number, hence not part of the bijection. $\endgroup$ – vadim123 Sep 5 '16 at 2:48
  • 1
    $\begingroup$ In proof $01$ I think you mean $\bigcap I_n$ $\endgroup$ – Jorge Fernández Hidalgo Sep 5 '16 at 2:48
  • $\begingroup$ @vadim123 Thanks a lot I got it. $\endgroup$ – gambler101 Sep 5 '16 at 2:55
  • 1
    $\begingroup$ In 02, if $f(n) = 1/9$ for all $n$, then $x = 1/9$. $\endgroup$ – AJY Sep 5 '16 at 2:55
  • $\begingroup$ Will it work now? $\endgroup$ – gambler101 Sep 5 '16 at 3:04

In proof $01$ you have not proved that $\bigcap\limits_{i=1}^n=\varnothing$, it could contain only one irrational number.

In proof $02$ you can't apply the same argument. Because the resulting number might be irrational.

  • 1
    $\begingroup$ No "could" or "might" about it :) $\endgroup$ – fleablood Sep 5 '16 at 4:49

The NIP doesn't hold in general metric spaces. For instance, let $a_1 = 3.1, a_2 = 3.14, a_3 = 3.141, \ldots$ (so $a_n$ is the first $n$ digits of the decimal expansion of $\pi$, and $b_n = a_n + 10^{-n}$. Then in $\mathbb{R}$, we have that $\bigcap_{n = 1}^{\infty} [a_n , b_n] = \{ \pi \}$. But if we limit ourselves to $\mathbb{Q}$, we have empty intersection. This relates to a property of $\mathbb{R}$ called completeness.

EDIT: Also, in 02 you are indeed constructing a number, but it needn't be rational (and if $f : \mathbb{N} \to \mathbb{Q}$ is a bijection, it necessarily won't be).

  • $\begingroup$ Is $\mathbb R$ the smallest complete set? $\endgroup$ – gambler101 Sep 5 '16 at 2:55
  • 3
    $\begingroup$ The smallest one containing $\mathbb{Q}$, yes. $\endgroup$ – AJY Sep 5 '16 at 3:19
  • 2
    $\begingroup$ @JonathanRichardLombardy More specifically, there are many ways to define $\mathbb{R}$, but one of the more common ones is to say it is the completion of $\mathbb{Q}$, that is to say the smallest complete metric space containing $\mathbb{Q}$. $\endgroup$ – AJY Sep 5 '16 at 4:56

In the first case, you've ignored the possibility that your sequence of intervals is, say, $I_n = [\pi - 1/n, \pi + 1/n]$. Then $\bigcap_nI_n$ is nonempty, but the only element it includes is $\pi$, which is not rational. Importantly, the NIP holds only within the reals, not the rationals.

In the second proof, observe that the number you construct (0.3233222232333... or some such) is going to be nonterminating - and it would be very easy to concoct a listing of rational numbers so that the decimal was also nonrepeating. For example, say our list was 0.2, 0.03, 0.002, 0.0002, 0.00003, 0.000003, ...; repeating in increasing "patches". Then the "diagonal" number we construct is a nonrepeating decimal - which is necessarily irrational. Thus the diagonal argument only tells us that our list of rationals is missing an irrational - which we already knew, because that was what it was supposed to do.

  • $\begingroup$ Last I checked, $\pi-1/n\notin\mathbb Q$ for $n\in\mathbb N$. So those intervals are not valid for this problem. However one can indeed create a valid sequence of intervals for $\pi$, for example $[3,4], [3.1,3.2], [3.14,3.15], [3,141,3.142], \ldots$ Now all interval borders are rational, but the only real number contained in the intersection is $\pi$; in particular there's no rational number contained in it. $\endgroup$ – celtschk Sep 5 '16 at 7:14
  • 1
    $\begingroup$ @celtschk OP never stated that the closed intervals in question had endpoints in $\mathbb{Q}$. I'm not assuming that OP means to be working exclusively in $\mathbb{Q}$, because if they were the NIP would simply be false; I'm simply showing that the NIP does not entail that the intersection have a rational member. $\endgroup$ – Reese Sep 5 '16 at 7:19
  • $\begingroup$ If the closed intervals have no endpoints in $\mathbb Q$, the "proof" is already flawed before we even consider completeness. Indeed, by considering intervals outside the considered set I can also "prove" that the real numbers are incomplete, since the real numbers are included in the surreal numbers, but the surreal interval $[\omega^{-1},2\omega^{-1}]$ does not contain any real number (it consists only of infinitesimals). $\endgroup$ – celtschk Sep 5 '16 at 7:32
  • 1
    $\begingroup$ Yes? OP's proof is not about completeness of anything, it's trying to prove that $\mathbb{Q}$ is uncountable. My interpretation of the first proof was that it was trying to use the fact that NIP holds in $\mathbb{R}$ to show that a certain member of $\mathbb{Q}$ exists; that was the flawed argument that I addressed. My apologies if I wasn't clear enough in my interpretation of the question. $\endgroup$ – Reese Sep 5 '16 at 7:37
  • $\begingroup$ Ah, OK, I see your point now. sorry for the noise. $\endgroup$ – celtschk Sep 5 '16 at 7:49

I'd say both of these make the same error: that in only considering the rationals, we forget that the irrationals still exist.

In case 1 we conclude the non-empty intersection contains no rationals.

In case 2 we construct a number that is different from all rationals.

To which, if we remember that irrationals still exist, we should conclude the intersection contains only rationals (only one actually) and the constructed number is irrational.

  • $\begingroup$ Both of these prove that any countable set can't be complete and uncountable "something else" must exist if our system is to be complete. In other words it does prove irrational must exit and they must be uncountable. $\endgroup$ – fleablood Sep 5 '16 at 4:48
  • $\begingroup$ I'm pretty sure $\mathbb Z$ is both countable and complete. $\endgroup$ – celtschk Sep 5 '16 at 7:08
  • $\begingroup$ Depends on what you mean by complete. Z definitely does not have the nesting principal at all nor does it have multiplicative inverses. I meant informally complete ~ least upper bound property which Z has but I was also implicitely assuming a field. Which is being a lot more informal than is really acceptable, I suppose. $\endgroup$ – fleablood Sep 5 '16 at 18:08
  • $\begingroup$ Well, normally when using mathematical terms, the assumption is that the mathematical meaning is used. Especially when discussing a topic directly related to that mathematical concept. Anyway, you could also argue that informally the real numbers are incomplete, as they are not algebraically closed (for example, the equation $x^2=-1$ has no solution; note that this is not that different from the equation 2x=1 not having a solution in $\mathbb Z$, which you just gave as an example of "informal incompleteness" of the integers). $\endgroup$ – celtschk Sep 5 '16 at 18:36
  • $\begingroup$ To talk of NIP and infinite expansions is to talk of least upper bound properties and an archimedian property that a < x < b always exist. I sinned in lumping them together under the blanket term "complete". $\endgroup$ – fleablood Sep 5 '16 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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