0

I know that rationals are countable, but I'm not seeing the flaw in this reasoning showing that rationals are uncountable:

We start by defining $f:\Bbb N \to \Bbb Q$ such that $$ 1 \mapsto \frac{p_1}{q_1}\\ 2 \mapsto \frac{p_2}{q_2}\\ 3 \mapsto \frac{p_3}{q_3}\\ .\\ .\\ .\\ $$

Then, we construct a new rational number, $c$, such that

$$c=\frac{2^{p_1}5^{p_2}11^{p_3}...}{3^{q_1}7^{q_2}13^{q_3}...}$$

where we choose the bases of the exponents to be prime numbers, alternating between numerator and denominator. We know $c$ is in simplest form, and both the numerator and denominator are unique. Therefore, $c$ is not in our list which contradicts our assumption that we can construct an all-inclusive listing.

Obviously the conclusion is absurd, but why? Secondly, why can this reasoning be used to prove $\Bbb R$ is uncountable but can't be used to prove $\Bbb Q$ is uncountable?

Badr B
  • 631
  • 5
  • 13
  • 5
    $c$ does not appear to be a rational number. – lulu Oct 16 '20 at 17:13
  • 5
    It looks like the numerator/denominator of $c$ both have an infinite number of terms, so the conclusion that $c$ is rational is dubious. Moreover, even if it is rational, it's not obvious why $c$ wouldn't appear in the list of rationals used to construct it. – Alex R. Oct 16 '20 at 17:16
  • The product defining $c$ is probably not convergent. And if it is, it can be any real number. Including one of the rationals. – N. S. Oct 16 '20 at 17:18
  • @Alex R. Thanks! Can't believe I missed that. And my reasoning for $c$ not being in the list is that the numerator and denominator are both greater than any numerator and denominator preceding it since it's being constructed using exponents of a positive integer base. – Badr B Oct 16 '20 at 17:19

1 Answers1

3

First of all, as mentioned in the comments the "object" $c$ you've described is rather problematic: it's not at all clear that that infinite product is well-defined (that is, that the appropriate limit actually exists and is finite).

More subtly, your argument that $c$ is not on the list breaks down since things aren't "stable" as we take the limit: it's a good exercise to show that there is a sequence of naturals $(a_i)_{i\in\mathbb{N}}$ such that $$\lim_{n\rightarrow\infty}\prod_{i=1}^n{(p_{2i-1})^{a_{2i-1}}\over (p_{2i})^{a_{2i}}}={17\over 42}$$ (for example).

That said, this is in some sense superficial: we can replace the OP's construction with a "digit-by-digit" construction, a la Cantor's diagonal argument, and produce a totally well-defined real number guaranteed to not be on the starting list. So why doesn't that show that the rationals are uncountable?

Well, the point is that there are actually two things we have to show about the "antidiagonal" object $\alpha$ we've constructed from a list $L$ in order to move forward with the diagonal argument:

  • We must show that $\alpha$ is not in fact in $L$.

  • We also must show that $\alpha$ is the "right sort of thing:" if the goal is to show that $L$ does not exhaust some set $S$, we have to argue that $\alpha\in S$.

When we're looking at the usual diagonal argument, this second step is basically trivial: any infinite string of digits is the expansion of a real number in $[0,1]$.

  • More precisely, and in base $2$ for convenience: for any infinite binary sequence $(c_i)_{i\in\mathbb{N}}$, the limit $\lim_{n\rightarrow\infty}\sum_{i=1}^n2^{-i}c_i$ exists and is in $[0,1]$.

For this reason it's often unstated. However, in general this may not be obvious, or indeed may be false. The OP is a case of the latter: when we apply the diagonal argument to a list of rationals, we get a real number (so far so good) which is not rational (oops).

Noah Schweber
  • 245,398