# What makes a infinity set countable?

I know that all infinity and countable set can be put in correspondence with $\mathbb{N}$.

But what proofs the correspondence itself ? Is it a well-ordering of the set ?

For example, Cantor has demonstrated that the set $\mathbb{Q}$ is infinity countable, by considering a well-ordered version of this particular set, and then, indexing the first element with the Natural 1, the second with the Natural 2, and so forth.

Is the well-ordering the only necessary condition to realize that a infinity set is also countable ?

If the set has a "first element" and a clear "sucessor rule", is it countable ?

• You wrote: I know that all infinity and countable set can be put in correspondence with $\mathbb{N}$. It is not true that every infinite countable set is equinumerous to $\mathbb N$. For example, there is no bijection between $\mathbb N$ and the powerset $\mathcal P(\mathbb N)$; according to Cantor's theorem. – Martin Sleziak Sep 12 '13 at 12:34
• But the powerset is not countable. Or it is ? – user94475 Sep 12 '13 at 14:21
• You're right, it isn't countable. It seems that I misunderstood your post. (I should have read it more carefully.) I thought that you mean: Every infinite set can be put into correspondence with $\mathbb N$ and every countable set can be put into... BTW standard name seems to be countably infinite set. – Martin Sleziak Sep 12 '13 at 14:25
• Yeah. I need more english class. Excuse me. – user94475 Sep 12 '13 at 15:13

The object that shows that a set $S$ is countable is the bijection between $S$ and $\mathbb N$. A well-ordering is not required to prove that a set is countable.

For example, to prove that $\mathbb Q$ is countable, one may construct a function $f: \mathbb Q \to \mathbb N$ (e.g., the function that Cantor constructs) and then prove that $f$ is bijective. Note that this proof does not require well-orderings or choice at any point, since one may give explicit formulas both for $f$ and its inverse.

Of course, the fact that a set is countable implies that it is well-ordered: If $S$ is countable, and $f: S \to \mathbb N$ is a bijection proving that, one may define an order $a \sqsubseteq b :\iff f^{-1}(a) \le f^{-1}(b)$, and it is easy to prove that this is a well-order. But this is a result of countability, and not required in the proof in any form whatsoever.

• I knew that a bijection is needed. But in the Cantor's book i have, he doesn't define a function as we are familiar with. He defines rules of precedence. Michael Greinecker makes all clear to me. Thanks. – user94475 Sep 12 '13 at 14:46

Every set has a wellorder defined on it, this is an equivalent version of the Axiom of Choice.

What is sufficient for a set $S$to be countable is that it has a "first element", a clear "successor rule $s$" and "every element but the first is a successor". Then if $x$ is the first element, we can recursively define a surjective map $f:\mathbb{N}\to S$ by letting $f(0)=x$ and $f(s(y))=f(y)+1$. If $s$ is injective, this gives actually a bijection and $S$ is countably infinite.

One can define a lot of well-orders that do not look like the usual well-order on the natural numbers though.

• Oh ! I got the point. Not all well-order satisfies the "every element but the first, is a sucessor" condition. Is it ? – user94475 Sep 12 '13 at 11:11
• @user94475 Exactly. – Michael Greinecker Sep 12 '13 at 11:29
• I need better drinking buddies. Where are you? – Asaf Karagila Sep 12 '13 at 12:11