# Countable subset of a uncountable set

Is it true that for any uncountable subset T of $\mathbb R$, one can find a subset S of T such that S is countable. If yes, how can we prove it?

Thanks!

Edit: Is there a countable subset S of T such that for every element $t\in T$, there exists $s\in S$ such that $s\geq t$?

-
Just take $S$ to be one element of $T$? – Jean-Sébastien Sep 23 '12 at 19:56
My question was really stupid. It's not exactly what I wanted to say. Thank you! – alabama78 Sep 23 '12 at 19:59
There is no such thing has a stupid question. Sometimes you stumble on a question that is really easy just because you are trying to hard prove something where there isn't really something to prove – Jean-Sébastien Sep 23 '12 at 20:00
Yes I guess you are right. Thank you! – alabama78 Sep 23 '12 at 20:01
@alabama78 What exactly did you want to say? – Fly by Night Sep 23 '12 at 20:27

Yes, every infinite set has a countably infinite subset.

However this countable subset need not be constructive (we don't have to have a nice formula defining it), because its existence requires a fragment of the axiom of choice (which allows us to make infinitely many arbitrary choices at once). Indeed it is consistent in the absence of the axiom of choice that there is an infinite set of real numbers which has no countably infinite subset (this implies that this set is uncountable).

In common, and especially introductory real analysis, the axiom of choice is assumed through and through, so you may disregard the above ramble if you wish.

-

Here is a more formal proof:

Let $T$ be an uncountable set. Choose $S_n$ to be a finite subset of $T$ with $n$ elements. It's always possible to pick such a set because $T$ is uncountable. Now let: $$S = \bigcup_{n=1}^\infty S_n$$

This set is a countable union of finite sets. Thus, it's at most countable. $S$ must be infinite because for all $n \in \mathbb{N}$, there is $S_n \subset S$. In other words, there is no $n$ for which $|S| < n$.

-

Any uncountable set has a countable proper subset. Pick any point $x_1$. Having picked finitely many distinct points, $x_1,\ldots,x_n$, one can always pick $x_{n+1}$ distinct from the previous ones. In this way one ends up with a sequence of points $x_1,x_2,x_3,\ldots$ which is the countable subset needed.

-

I take it that your edit is the question you wanted to ask, i.e.

Is there a countable subset S of T such that for every element $t\in T$, there exists $s\in S$ such that $s\geq t$?

So let $T$ be uncountable.

If $T$ is bounded above then it has a supremum $\eta$. If $\eta \in T$ then let $S = \{ \eta \}$. Otherwise, let $S = \{ \eta_n\, :\, n \in \mathbb{N} \}$ where $(\eta_n)_{n=1}^{\infty}$ is some strictly increasing sequence in $T$ converging to $\eta$.

If $T$ is unbounded then let $S = \{ \eta_n\, :\, n \in \mathbb{N} \}$, where $(\eta_n)_{n=1}^{\infty}$ is some strictly increasing sequence in $T$ which tends to $\infty$.

In any case, by construction, for each $t \in T$ there exists $s \in S$ such that $s \ge t$, as you should verify; and $S$ is clearly countable.

If you require $S$ to be countably infinite then, in the case $T$ bounded and $\sup T = \eta \in T$ given above, let $S'$ be any countably infinite subset of $T$ (e.g. constructed as in Ayman Hourieh's answer) and then let $S = S' \cup \{ \eta \}$.

-

Let $\sim$ be the relation of equinumerosity. Then, define the relation $\prec$ on the class of sets modulo $\sim$ by: $A \prec B$ if there exists an injection $A \to B$.

According to Cantor-Bernstein-Schroeder Theorem, $\prec$ is an order relation. Moreover, Zermelo's Theorem states that $\prec$ is linear.

Therefore, if $A$ is an uncountable set, then $\mathbb{N} \prec A$ and there exists an injection $\phi : \mathbb{N} \to A$; $\phi(\mathbb{N})$ is a countable subset of $A$.

-