scineram

> Can anyone give a proof of these statements
> about countable union and about infinite sets
> using CC?

The set N x N (where N is the natural numbers) is countably infinite (no choice needed, since it's easy to construct an explicit bijection with N). Suppose S_1, S_2, S_3, ... is a sequence of countable sets. For each n, let T_n = S_n \ ( S_1 union ... union S_{n-1} ). For each n there is an injection i_n: T_n -> {n} x N. (We are choosing infinitely many injections here, so this uses CC.) Combining these injections gives us an injection from the union of the T_n into N x N. So the union of the T_n (which is the same as the union of the S_n) is countable.

Now suppose that X is an infinite set. For each natural number n there is subset S_n of X of cardinality n. (We are choosing infinitely many subsets here, so this uses CC.) The union of the S_n is countable (by the previous paragraph) and is clearly infinite. So every infinite set has a countably infinite subset.