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 ?
 A: 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.
A: 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.
