# How to show a collection of sets is countable

In the proof for "Every open subset $\mathcal O$ of $\mathbb R$ can be written uniquely as a countable union of disjoint open intervals" Stein and Shakarchi (2005 p6) argue that (after having defined a collection of disjoint open intervals $\mathcal I=\{I_x\}_{x\in\mathcal O}$) "since every open interval $I_x$ contains a $\bf rational$ number, since different intervals are disjoint, they must contain distinct $\bf rationals$, and therefore $\mathcal I$ is $\bf countable$."

I do not understand this argument. If it is true, then why can't I say "since every open interval $I_x$ contains an $\bf irrational$ number, since different intervals are disjoint, they must contain distinct $\bf irrationals$, and therefore $\mathcal I$ is $\bf uncountable$."? Could anyone explain this to me, please? Thank you!

• Consider the collection of disjoint open sets $\{(n,n+1)\}$ and let $n$ vary from $1$ to some fixed $N\in \mathbb{N}$...can you apply your argument here ? – wanderer Mar 19 '14 at 8:20

Well, simply because you could have an irrational number in each set but still not uncountably many. The argument with irrationals tells us only that we have at most uncountably many, i.e. gives us an upper bound. But the argument with rationals gives us an even better upper bound:

If we have a unique rational number in each set, and there are only countably many rational numbers, then we must have at most countably many sets, which is less than uncountably many.

That argument basically comes down to the following:

We have a set $X$, and we can set up an injective (or one-to-one) function $f : X \to Y$. By definition of cardinality (or, rather the $\leq$ relation between cardinal numbers) it follows that $|X| \leq |Y|$.

In your specific instance, your set $X$ is the collection $\mathcal{I}$, your set $Y$ is $\mathbb{Q}$, and the function is a choice function which assigns to each open interval in $\mathcal{I}$ a rational number in it. So our conclusion is $|\mathcal{I}| \leq | \mathbb{Q} | = | \mathbb{N} |$, which means that $\mathcal{I}$ is countable.

Were you to use $\mathbb{R} \setminus \mathbb{Q}$ instead, your conclusion would be that $|\mathcal{I}| \leq | \mathbb{R} \setminus \mathbb{Q}|$, but from this you cannot conclude that $\mathcal{I}$ is uncountable.

The idea is to choose for every interval $I_x, x \in \mathcal{O}$ some rational number $r_x \in I_x$. Since the intervals are disjoint $r_x$ will determine $I_x$ uniquely (among the intervals in $\{I_x|x\}$). Now there are only countably many rationals and for every rational number there is at most one interval in your collection. Hence there are at most countably many intervals in your collection.

Edit: The same argument does in fact work with the set of irrational numbers instead of the rational numbers to show that there are at most as many intervals as there are irrational numbers. This is just not what you want to prove since the set of irrational numbers is uncountable.

• the question is that why can't you use the same argument by replacing the rationals with irrationals and conclude that the number of intervals are uncountable. i think the arguments by Arthur and naslundx gives the answer. – wanderer Mar 19 '14 at 8:24
• You are indeed correct. I edited my post to better answer the question. – Sebastian Schoennenbeck Mar 19 '14 at 8:42