Example that proves "not every infinite subset of a non-countable set is non-countable" I need an example to prove this statement:

Not every infinite subset of a non-countable set is non-countable.

As far as I know, every infinite subset of a countable set is countable, but I cant work my way into proving the above statement.
I am trying to think of a subset of $R$, but nothing comes to my mind.
Thanks in advance.
 A: Well, take the set of real numbers $\mathbb{R}$. Then, consider the set of rational numbers $\mathbb{Q} \subset \mathbb{R}$. We know that the former is uncountable and we know that the latter is countable. Does that make sense?
I mean, yea, you could choose, for instance, the integers or the natural numbers too. Those work as well.
A: Well, if we can't think of one... we make one.
Let's start by picking $0$ from $\mathbb R$. (If we know we are picking from $\mathbb R$ and we know $0 \in \mathbb R$ so we aren't assuming any axiom of choice if anyone wants to nitpick).  Then we can pick $1$ from $\mathbb R$.
Then by induction we figure once we pick $n$ we can then pick $n+1$ and our set will contain $\{0,1,2,3,.....\}$ for all natural numbers and as we did nothing else our set will be only the natural numbers. And our set is ....  then we give ourselves a giant dope slap as our set is just $\mathbb N$ and $\mathbb N \subseteq \mathbb R$.
That's the perfect and obvious counter example $\mathbb N \subseteq \mathbb R$ and $\mathbb N$ is infinite and countable.
======
A harder thing would be to prove every uncountable set has an infinite countable subset.  But we can do that.
And uncountable set, $X$, is non empty so we can pick $a_1 \in X$.  Then if we can assure ourselves that $X_1 = X\setminus\{a_1\}$ is uncountable we can continue.
If $X_1$ were countable then $X_1 \cup \{a_1\} = X$ would be countable which it is not.
We can define $A_1 =\{a_1\}$ and we can pick $a_2\in X_1$ and define $X_2=X_1\setminus \{a_2\}$ and define $A_2=\{a_1, a_2\}$.
And by induction for every $A_k=\{a_1,...., a_k\}; X_k = X\setminus A_k$ we  can pick $a_{k+1}\in X_k$ and define $A_{k+1} = A_k\cup \{a_{k+1}\}$ and define $X_{k+1} = X\setminus A_{k+1}$.
And by induction we can have a set $\{a_1,.......\}\subset X$ that is infinite and countable.
A: Here I consider a "non-countable" ("uncountable") set the one which is not finite OR countable (and countable $\ne$ finite).
Let $X$ be a non-countable set. $X$ is nonempty, so, assuming AC (Axiom of Choice), we can make the "choice function" $\mathcal{C}:\mathcal{P}(X)\to X$, which "picks" an element of every subset: $\mathcal{C}(Y)\in Y$ for all $Y\subseteq X$.
Now, define recursively:
$$x_1=\mathcal{C}(X)$$
$$x_{n+1}=\mathcal{C}(X\setminus\{x_1,x_2,\ldots,x_n\})$$
By construction, $x_1, x_2, x_3$ etc. are all mutually different, so the set $\{x_1, x_2, x_3\ldots\}\subseteq X$ is the required countable subset of $X$.
