# Why does at least two intervals overlap in an uncountable family of intervals?

1. Prove that there are uncountably many intervals $(a,b)$ in $\mathbb{R}, a\neq b$.
2. Assume $X$ be an uncountable family of intervals. Show that there exists at least two intervals in this family that overlap.

First was not difficult. I used the arguments similar to Cantor's Diagonal Argument (used to show $\mathbb{R}$ is uncountable.)

My attempt for 2: Assume $X$ be an uncountable family of pairwise disjoint intervals, i.e. $(a_i,b_i) \cap (a_j,b_j) = \emptyset, \quad \forall i\neq j\in I$. We know there exists a rational number in each of these intervals. This implies there are uncountably many rational numbers. Contradiction, since $\mathbb{Q}$ is countable. Thus, $X$ must have at least two intervals that overlap. $\blacksquare$

Is there any problem with this reasoning?

• First is a consequence of $(a,b)\mapsto b-a$ being a surjection. – Git Gud Sep 29 '13 at 11:33
• So would it be wrong to argue the way I did? – math Sep 29 '13 at 11:35
• Probably not, but it seems to me too complicated to prove what you want to prove. – Git Gud Sep 29 '13 at 11:36
• Looks fine to me. What about the argument made you feel uncertain? – Callus Sep 29 '13 at 11:38
• @Callus, are you asking me or Git Gud? – math Sep 29 '13 at 11:45

## 1 Answer

Nope, no problems.

For (1), you certainly could use a diagonal argument directly to prove that there is no surjection from $\mathbb{N}$ onto the set of intervals, or as Git Gud points out you could instead use the existence of a surjection from the set of intervals to $\mathbb{R}$ and then appeal to the nonexistence of a surjection $\mathbb{N} \to \mathbb{R}$. It is common to use Cantor's theorem on the uncountability of the reals as a "black box" in this way.

Your proof for (2) is perfectly fine. You could also get the contradiction by showing that $X$ is countable after all, rather than by showing that $\mathbb{Q}$ is uncountable, but this choice is just a matter of taste.

• For 1), why not just say that $(0,x)$ is an interval for any $x>0$, giving us directly an injection of $\mathbb R^+$ into the set of intervals? (Even simpler than the route with surjections.) – Andrés E. Caicedo Sep 29 '13 at 16:45
• @Andres Yes, I guess that would be simpler. However if we take countability to be defined in terms of the existence of surjections then Git Gud's method translates into a shorter formal proof, I think. – Trevor Wilson Sep 29 '13 at 16:52
• A third method would simply use the surjection from intervals to reals given by $(a,b) \mapsto a$. – Trevor Wilson Sep 29 '13 at 16:53
• Isn't the second proof is contrapositive instead, and the one by the OP is by contradiction? :-) – Asaf Karagila Sep 29 '13 at 17:14
• @Asaf I think that depends on whether or not it starts with "let $X$ be an uncountable family of pairwise disjoint intervals" like the OP's proof does. – Trevor Wilson Sep 29 '13 at 17:18