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 ?

  • $\begingroup$ 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. $\endgroup$ – Martin Sleziak Sep 12 '13 at 12:34
  • $\begingroup$ But the powerset is not countable. Or it is ? $\endgroup$ – user94475 Sep 12 '13 at 14:21
  • $\begingroup$ 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. $\endgroup$ – Martin Sleziak Sep 12 '13 at 14:25
  • $\begingroup$ Yeah. I need more english class. Excuse me. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.