Cantor defined countable sets as
A set is countable if there exists an injective function from the set to the set of natural numbers.
Still today countability is almost always defined in Cantor's words. Are the natural numbers really necessary to define countability. Most mathematicians admit that set theory is still a rich subject to study without getting into the conception of numbers. And I believe that the notion of countability is more fundamental than the set of natural numbers itself. Hence I wonder is it possible to define countability without referring the natural numbers?
Let $A$ be a set and let $S:A\rightarrow A$ be a successor function which is characterised by the following properties.
-
Two different elements in $A$ can not have same successor.
-
The successor of an element should not be its ancestor.
Shall I define countable sets as below?
A set is countable if there exists a successor function as characterised above.
Best Answer
Yes. You can. Depending on the available tools.
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.
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.