Why Doesn't My Proof, That Rational Numbers Are Uncountable, Work? (Using Cantors Argument)

Question

First I'd like to recognize the shear number of these "anti-proofs" for Cantor's Diagonalization Argument, which to me just goes to show how unsatisfying and unintuitive it is to learn at first. It really gives off a "I couldn't figure it out, so it must not have a mapping" kind of vibe. I have read these posts [ 1, 2, 3,] and do recognize many of the mistakes though potentially not all so I apologize if I end up repeating some of them. That said here is my attempted proof which I know must be wrong but don't understand why.

Proof by Contradiction:
Since all subsets of a countable set are countable, if rational numbers are countable then the subset $(0,1)\in \mathbb{Q}$ is therefore countable.
Where $i \in \mathbb{N}$ and $n,d\in \mathbb{N}$ let: $$ q_i=\frac{2^{n_{i1}}\cdot 3^{n_{i2}} \cdot 5^{n_{i3}} \cdot 7^{n_{i4}} \cdot ... }{2^{d_{i1}}\cdot 3^{d_{i2}} \cdot 5^{d_{i3}} \cdot 7^{d_{i4}} \cdot ... }, \text{where} \,n_{ij}\ne0\to d_{ij}=0 \, \text{and} \,d_{ij}\ne0\to n_{ij}=0 $$ By using the fundamental theorem of arithmetic we know that we can represent all integers in both the numerator and denominator of $q_i$ and that $q_i\ne q_k$ unless for all index values of $\mathbf{n}_i$ and $\mathbf{d}_i$ are equal to those of $\mathbf{n}_k$ and $\mathbf{d}_k$.
With this we can represent the set $(0,1)\in\mathbb{Q}$ as $\{q_1, q_2, q_3,...\}$.
However, using Cantor's Diagonalization Argument we can create: $$ q=\dfrac{2^{n_{11}}\cdot 3^{n_{22}} \cdot 5^{n_{33}} \cdot 7^{n_{44}} \cdot ...}{2^{d_{11}\,+1}\cdot 3^{d_{22}\,+1} \cdot 5^{d_{33}\,+1} \cdot 7^{d_{44}\,+1} \cdot ...} $$ The new value $q$ will not be equal to any elements in $\{q_1, q_2, q_3, ...\}$ and it also isn't necessarily a larger number or smaller number (so I'm not just counting up or down by one). The value $q$ will also need to exist in the subset.

Any help pointing out my mistakes will help me finally seal my unease with Cantor's Diagonalization Argument, as I get how it works for real numbers but I can't seem to wrap my mind around it not also being applied to other sets which are countable.

Answer 1

I believe the mistake is that you are forgetting a condition that the numbers $n_{i,j}$ and $d_{i,j}$ must satisfy: At most a finite number of them can be non-zero. This changes everything.

Cantor's argument shows there is no surjective function from $X$ to $2^X$, but what we have (instead of $2^X)$ is more akin to the the set of finite subsets of $X$. See this answer here for more information on the cardinality of this set.

Answer 2

The mistake you're making is basically that an infinite product of rationals need not be rational (any more than an infinite sum of rationals need be rational - consider e.g. $3+0.1+0.04+0.001+0.0005+...$). The Wallis formula is a concrete example of how this can break down. In fact, it's not hard to show the following:

Every real number can be written as an infinite product of rationals; that is, for every real number $a$ there is some sequence of rationals $(q_i)_{i\in\mathbb{N}}$ such that $a=\prod_{i\in\mathbb{N}}q_i$.

(HINT: think about how every real is the limit of a sequence of rationals ...)

Note that there's a crucial point about limits here: limits are not approximations, even though the intuitive way we think about them (initially at least) is in terms of approximation. For example, the infinite product in the Wallis formula literally is $\pi\over 2$, in the same way that $\lim_{n\rightarrow\infty}(1-2^{-n})$ literally is $1$. A general consequence of this, which is often surprising at first, is that a limit of numbers with a certain property need not have that property. Here of course the relevant property is rationality.