Cardinality of the irrational numbers vs the rationals

Question

I am trying to explain why this proof is false. The easy way is to just assert that we have a valid proof that tells us that the cardinality of the irrational numbers is greater than the set of rationals and be done with it, but I want to be able to explain exactly where this proof is wrong.

1. Let $I$ be the set of irrational numbers, where the elements are $\{i_n: n \in R \land 0 < i_n < 1.0 \} $

2. Let $T_{i_n}$ be the set of all rational prefixes of $i_n$

3. For example if $i_{1.3721\dots} = 0.314159\dots$ then set $T_{i_{1.3721\dots}} = \{ 0.3, 0.31, 0.314, 0.3145, 0.314159, \dots\}$

4. Let $T = \bigcup T_{i_n}: n \in R$

5. Then $T$ will be a set of rational numbers

6. If $\exists q : q \in T_{i_k} \land q\notin \bigcup T_{i_n}: n \in (R \setminus k)$

7. Then $|I| \le |T|$ We are done

8. Else $|I| \not \le |T|\rightarrow \exists i_x \exists i_y: i_x \ne i_y \land T_{i_x} = T_{i_y}$ Contradiction

9. Two different irrational numbers can't have the same prefix set.

The proof is trying to say that every prefix set contributes at least one rational number to the union, and if that one prefix set were removed, then there would be some rational number missing from the union.

I would argue that in the prefix set given as an example, there are an infinite number of prefix sets that contribute 0.3 to the union, and there are an infinite number of sets that contributes 0.31, and the same for 0.314, and the same for all the elements in that prefix set. So you can remove any prefix set from the union and the union will not be any less. You can even remove an infinite number of irrationals and still have the same union. The only way to reduce the rational elements in the union, is by removing a segment from the union. For example if you remove an interval, like all the irrational numbers between 0.005 and 0.006 then the rational numbers from 0.005 to 0.006 will not be in the union.

Would this be one reason for why the proof fails and are there others?

Answer 1

You got the idea right -- it's not true that every prefix set contributes at least one rational number to the union; in fact, for every rational number contributed by prefix set $T_{i_x}$, there are infinite other prefix sets which contribute the same rational number to the union.

As for the formal proof, I am completely mystified where (8) comes from. As far as I can tell, all we can conclude from the negation of the assumption in (6) (which is I think how (8) is trying to argue?) is that every rational number is contained within the intersection of some two prefix sets -- but this is far from implying that some two prefix sets are equal.

Answer 2

Your condition in step (6) with all the quantifiers explicit, looks like it should be $$ \text{If }\forall k\in\mathbb R:\exists q\in T_{i_k} : q\notin \bigcup_{n\in \mathbb R\setminus\{k\}} T_{i_n} $$ which is the same as saying $$ \text{If }\forall k\in\mathbb R:\exists q\in T_{i_k} : \neg\exists n\neq k: q\in T_{i_n}$$ In step (8) we're assuming the negation of this -- that is, $$ \text{If }\exists k\in\mathbb R:\forall q\in T_{i_k} : \exists n\neq k: q\in T_{i_n}$$ However to conclude that there are two of the prefix sets that are the same you would need something of the form $$ \text{If }\exists k\in\mathbb R: \exists n\neq k: \cdots$$ and you don't get that from the negation above, because the $n$ that comes out of that may depend on $q$.

---

What went wrong? One hypothesis is that you have accidentally swapped the quantifiers in your mind, giving $$ \tag{wrong!} \text{If }\exists k\in\mathbb R: \exists n\neq k:\forall q \in T_{i_k}: q\in T_{i_n}$$ or in other words that there are two prefix sets where one is a subset of the other. But even that would not be quite the contradiction you're looking for -- though we could still derive a contradiction from it by considering that the only limit point of $T_x$ ought to be $x$.

Another hypothesis would be that because $(6)$ implies $|I|\nleq|T|$ you think that $\neg (6)$ would imply $|I|\leq|T|$. But that is not valid reasoning -- just because one particular argument for $|I|\nleq|T|$ happens not to be available doesn't mean that $|I|\nleq|T|$ has to be false.