7
$\begingroup$
  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?

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

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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.) $\endgroup$ – Andrés E. Caicedo Sep 29 '13 at 16:45
  • $\begingroup$ @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. $\endgroup$ – Trevor Wilson Sep 29 '13 at 16:52
  • $\begingroup$ A third method would simply use the surjection from intervals to reals given by $(a,b) \mapsto a$. $\endgroup$ – Trevor Wilson Sep 29 '13 at 16:53
  • $\begingroup$ Isn't the second proof is contrapositive instead, and the one by the OP is by contradiction? :-) $\endgroup$ – Asaf Karagila♦ Sep 29 '13 at 17:14
  • $\begingroup$ @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. $\endgroup$ – Trevor Wilson Sep 29 '13 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.