Is it possible to define countability without referring the natural numbers?

Solution 1:

Yes. You can. Depending on the available tools.

1. A set $A$ is countable if and only if whenever $B\subseteq A$ and $|B|<|A|$, then $B$ is finite. If you want countable to refer only to infinite sets, then you can also add that there is a proper subset of $A$ which is equipotent with $A$.

   Now, you might argue that finiteness depend on the natural numbers, but don't worry, Tarski got you covered: $X$ is finite if and only if the partial order $(\mathcal P(X),\subseteq)$ is well-founded.

2. A set $A$ is countable if and only if it can be linearly ordered such that every proper initial segment is finite. Again, if you are only interested in infinite sets, add the requirement that there is no maximal element.

Solution 2:

Two sets are equipotent iff there is a bijection between them.

A set is finite iff it admits a total ordering in which every nonempty subset has a least element and a greatest element; otherwise it is infinite.

(Alternatively, a set $A$ is infinite iff the set $\mathcal P(\mathcal P(A))$ is equipotent to a proper subset of itself.)

A set is countable (finite or countably infinite) iff all of its infinite subsets are equipotent.

Solution 3:

No that does not work. Even if you add a condition that there is an element (representing $0$) that is not the successor of anything), the definition would still claim that, for example $$ (\mathbb R \setminus \mathbb Z) \cup \mathbb N $$ is countable, just by defining "successor" as the usual $x\mapsto x+1$.

What modern (since the early 1900s) set theory actually does does not depend directly on the natural numbers:

1. A set $A$ is called inductive iff $\varnothing \in x$, and for every $x\in A$ it holds that $x\cup\{x\}\in A$ too.

2. There's an explicit axiom of set theory promising that at least one inductive set exists.

3. The intersection of all inductive sets is called $\omega$.

4. A set is called "countable" if it is in bijective correspondence with (some subset of) $\omega$.

It turns out that the elements of $\omega$ are good candidates for representing the natural numbers within set theory, so usually we end up defining $\mathbb N$ to be an alternative name for $\omega$ -- but countability does not actually depend of the number-ness of $\omega$'s elements. (It doesn't care about arithmetic, for example).

Solution 4:

A set $S$ is countable iff $S$ injects into every set $T$ that non-surjectively injects into $T$.

Basically, $S$ is countable iff $S$ is no larger than every infinite set.

A set is countable if there exists a successor function as characterised above.

Henning Makholm already explained why this is wrong, but I wish to point out that it is because you did not get an equivalence. If a set is countable then there exists a successor function like you said, but the converse does not hold.