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, 2013 at 11:33
  • $\begingroup$ So would it be wrong to argue the way I did? $\endgroup$
    – math
    Sep 29, 2013 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, 2013 at 11:36
  • 2
    $\begingroup$ Looks fine to me. What about the argument made you feel uncertain? $\endgroup$ Sep 29, 2013 at 11:38
  • $\begingroup$ @Callus, are you asking me or Git Gud? $\endgroup$
    – math
    Sep 29, 2013 at 11:45

1 Answer 1

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$ Sep 29, 2013 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$ Sep 29, 2013 at 16:52
  • $\begingroup$ A third method would simply use the surjection from intervals to reals given by $(a,b) \mapsto a$. $\endgroup$ Sep 29, 2013 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, 2013 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$ Sep 29, 2013 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.