proof that reals are uncountable I found this proof in Goldberg's Methods of Real Analysis:
Assume the $\mathbb{R} = \{x_1, x_2, ... \}$ are countable. Let $I_1$ be the interval $(x_1-1/4, x_1+1/4)$, $I_2$ be the interval $(x_2-1/8,x_2+1/8)$, $I_n$ be the interval $(x_n-1/2^{n+1},x_n+1/2^{n+1})$. Then $\mathbb{R} \subset \cup^{\infty}_{n=1} I_n$. Then the whole real line whose length is infinite would be contained in a union of intervals whose lengths sum to 1. This seems to be a contradiction. Is it?
Is this a valid proof? The Cantor set has a length of $0$ yet is equivalent to $[0,1]$, so how can length of an interval be used in such a proof for "countability"?
 A: It doesn't look convincing. As long as there's not any relevant knowledge about measures on $\mathbb R$ to build on, the argument looks like it would apply just as well (or ill) to show that $\mathbb Q$ is uncountable. But $\mathbb Q$ is countable, so there has to be a gap somewhere in the proof that needs to be filled out with something that is specific to $\mathbb R$.
A: This is a tantalizing example of a seemingly intuitive proof that's subtly flawed. Let's explore the details.
The Flaw
This answer correctly points out that there is something missing in this proof, as the argument equally applies to the rationals. I'll drill into specifically what's wrong. It's the conclusion:

Then the whole real line whose length is infinite would be contained
in a union of intervals whose lengths sum to 1.

Without further assumptions, this in and of itself isn't a contradiction. To see why, as suggested in the linked answer, let's examine the rationals. Consider the set $A = [0, 1] \cap \mathbb{Q}$. This is just the set of rational numbers between $0$ and $1$. Now consider any two rational numbers $p < q \in A$. We can define a new set, a subset of $A$, which is the rational interval $I_{p, q} = [p, q) \cap \mathbb{Q}$.
Now, let's define the "length" $\mu$ of $I_{p, q}$ as $\mu(I_{p, q}) = q - p$. This seems like the standard notion of length that we know from every day. At first, the length function that we defined seems to behave as we'd expect. If we have a finite number of disjoint intervals whose union is another interval, then the sum of the lengths of the smaller intervals equals the length of the larger. That is, we can "cut" the larger interval into a finite number of smaller intervals and total length is preserved. Mathematically, if $I_{p, q} = \cup_{k=1}^{n} I_{p_k, q_k}$ and $k \neq j \implies I_{p_k, q_k} \cap I_{p_j, q_j} = \emptyset$ then it can be shown that:
$$\mu(I_{p, q}) = \Sigma_{k=1}^{n} \mu(I_{p_k, q_k})$$
This is called finite additivity. I'll prove this now by induction. The case of $n = 1$ is straightforward because we just have an identity. So let's just do the inductive case, where there are $n+1$ intervals. Since there are only a finite number of intervals, and since they are all disjoint, we can order them. WLOG then we have $p_1 < q_1 \leq p_2 < q_2 \dots \leq p_{n+1} < q_{n+1}$. Since all points must lie in some interval, we have then that $q_k = p_{k+1}$ and $q = q_{n+1}$. Now, by assumption we have:
$I_{p, q} = \cup_{k=1}^{n+1} I_{p_k, q_k} = \cup_{k=1}^{n} I_{p_k, q_k} \cup I_{p_{n+1}, q_{n+1}}$
Since intervals are ordered, we know that $\cup_{k=1}^{n} I_{p_k, q_k} = I_{p_1, q_n}$ and so the induction hypothesis applies, allowing us to conclude that:
$\mu(I_{p, q}) = q - p = q_{n+1} - p_{n+1} + p_{n+1} - p = \mu(I_{p_{n+1}, q_{n+1}}) + \Sigma_{k=1}^{n} \mu(I_{p_k, q_k}) = \Sigma_{k=1}^{n+1} \mu(I_{p_k, q_k})$
Great, so our notion of "length" is looking good, on intervals containing only rational numbers. Chopping an interval into finite pieces preserves length. But what about if we "chop" the interval into a countably infinite number of pieces? Well, we should depart from the word "chop" here really and use "cover". If we can cover an interval with a countably infinite number of disjoint intervals, then surely the lengths of those intervals would add up to the original? Right? Wrong. The property is called countable additivity. It's the countable analogue of the finite additivity property we just proved. Countable additivity states that if $I_{p, q} = \cup_{k=1}^{\infty} I_{p_k, q_k}$ and $k \neq j \implies I_{p_k, q_k} \cap I_{p_j, q_j} = \emptyset$ then:
$$\mu(I_{p, q}) = \Sigma_{k=1}^{\infty} \mu(I_{p_k, q_k})$$
Let's see why this doesn't hold for the set $A$. The construction is much like that in your proof. Since the entire set of rationals is countable, then so is the set $A$. So we can enumerate its members as $a_1, a_2, \dots, a_k, \dots$ so that $A = \{a_i | i \in \mathbb{N} \}$. Now, we can proceed to cover the entire set as follows. Start with $d = \frac14$ and with $k = 1$ and then follow this algorithm, which has a countably infinite number of steps:

*

*If $a_k \notin U_k = \cup_{i=1}^{k} I_j$, then define $F_k = [a_k, a_k + d) \setminus U_k$. It can be shown that $F_k$ is the union of a finite set of disjoint intervals. Define $I_k \subseteq F_k$ as the interval in the union that contains $a_k$. Else define $I_k = \emptyset$.

*Update $d$ by dividing the old value by $2$.

*Increment $k$ and return to the first step.

Clearly the set of all $I_k$ covers every rational number in $A$. And with a bit of thought, you can see they are disjoint. But the infinite sum of the lengths $I_k$ converges to a number less than $\frac12$, not $1$, which is the "length" of $A$. This is indeed a strange behaviour. We can even see that at all points in the algorithm, the remaining uncovered points in the set form a finite set of intervals whose total length sums up to an amount greater than $\frac12$ but then... in the infinite limit... there is nothing left. Every point is covered.
So the notion of length we defined over rational intervals is not countably additive. There is no contradiction here- this is just how the rationals behave. So to assume that the non-satisfaction of countable additivity of a "length" function on intervals implies a contradiction is wrong- we've just seen a set that does so without contradiction. A dense set at that.
Fixing the Proof: Enter Measure Theory
Of course, if we start with the knowledge that there exists a measure on some sigma algebra over subsets of $\mathbb{R}$ which gives us $b - a$ for any interval $[a, b)$, then a proof like the above will work: sub-additivity of the measure means that $A \subset B \implies \mu(A) \leq \mu(B)$ which would indeed be a contradiction since $\mu(\mathbb{R}) = \infty \nleq 1 = \mu(\cup_{n > 0}I_n)$. However, if we've already gone to the trouble of using measure theory then why not just use a simpler proof e.g. https://math.stackexchange.com/a/1092947/252983.
Now, although logically the uncountability of $\mathbb{R}$ follows from the existence of the Lebesgue measure, we need to be careful to call this a proof. In the construction of the Lebesgue measure, if there is reliance upon the uncountability of $\mathbb{R}$, then the argument would be circular and we haven't really proved the uncountability: rather we have just shown that the existence of such a measure implies uncountability. I'm not sure if the Lebesgue measure construction does indeed rely on the uncountability of the reals at its core, so I can't comment further on that for now. But perhaps others will add to this post with further knowledge in this area.
A: If you know that a closed interval is compact, then you could choose a finite number of intervals that would cover $[0,2]$, and arrive at a contraction. What facts about Real numbers are know at this point in your study.
