I don't know how to prove the following:


$K:=\lbrace G : G$ is a union of finitely many intervals with rational endpoints$\rbrace$.

Prove that $K$ is countably infinite.

Here is my approach:

The set of intervals with rational endpoints is countably infinite as there is a bijection between this set and $\mathbb{Q}\times \mathbb{Q}$. However, I don't know how to continue.

I really appreciate any help you can provide.

  • $\begingroup$ How about the set $K_n$ that consists of unions of $n$ disjoint intervals with rational endpoints? And how about $\bigcup_n K_n$? $\endgroup$ – gniourf_gniourf Feb 14 '16 at 18:25
  • $\begingroup$ Why disjoint intervals? $\endgroup$ – J.-E. Pin Feb 14 '16 at 18:26
  • $\begingroup$ @J.-E.Pin maybe because it's easier to construct an explicit bijection (at least the one I have in mind) $\endgroup$ – gniourf_gniourf Feb 14 '16 at 18:27
  • 1
    $\begingroup$ Imagine we have enumerated the intervals (we probably need to include the four kinds of interval). Let $I_1,I_2,\dots$ be an enumeration. Then we can enumerate the set of finite sequences of intervals. For any finite sequence of natural numbers $a_1,a_2,\dots,a_k$ can be mapped to $p_1^{a_1}\cdots p_k^{a_k}$, where the $p_i$ are the primes in increasing order. $\endgroup$ – André Nicolas Feb 14 '16 at 18:30

Hint. Let $E$ be the set of intervals with rational endpoints. You already proved it is a countably infinite set. You need now to prove that the set $U$ of finite unions of elements of $E$ is also countably infinite. Clearly $U = \bigcup_{n \geq 0} U_n$, where $U_n$ is the set of union of $n$ elements of $E$. Since a countable union of countable sets is countable, it remains to show that each set $U_n$ is countable. Can you prove that last part?

  • $\begingroup$ Can I use this with a fixed $n$ and use the fact that there is an injection between $U_n$ and the set of the link (whit $n$ fixed)? $\endgroup$ – Who knows Feb 14 '16 at 19:30
  • $\begingroup$ This is a possibility. Your link also redirects to this question and this question which also solve your question directly. You can choose between the several answers to these questions and/or use the suggestion given by André Nicolas in his comment. $\endgroup$ – J.-E. Pin Feb 14 '16 at 21: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.