Are there interestingly non-equivalent definitions of countability over ZF?

Over ZF, there are many definitions of infinite (and therefore of finite) that are non-equivalent, but become equivalent under presence of (a weak version of) the axiom of choice. See "Other notions of finiteness" on Wikipedia for examples.

I wonder if the same thing happens for countably infinite sets. Some obvious ones certainly appear to be equivalent: admitting a bijection to $\omega$, an unbounded injection into $\omega$, or a surjection from $\omega$ (but not from a natural number). Are there different characterizations of countably infinite sets that are equivalent over ZFC but not over ZF, and that give rise to some interesting differences?

(By 'interesting' I mean that I am not interested in characterizations such as "$A$ is countably infinite if there is a bijection $\omega \to A$ and furthermore every set is well-orderable".)

Solution 1:

Countability is kind of etched in stone. So the only differences I can think of would come from taking a definition of finiteness which is not equivalent to the usual finiteness without some choice, some $X$-finite sets, and define countable as follows:

$A$ is $X(1)$-countable if for every $B$ such that any $X$-finite injects into $B$, then $A$ injects into $B$ as well.

Or,

$A$ is $X(2)$-countable if it is not $X$-finite, but every strictly smaller cardinality is $X$-finite.

Note that the first definition is peculiar since without choice it is possible that $\omega$ is not $X(1)$-countable if $X$ is not equivalent to finiteness and there are no Dedekind-finite sets. Indeed, it is possible that there are no countable sets under this odd definition.

In the second case it is always the case that $\omega$ is $X(2)$-countable, since any definition of finite which the natural numbers do not satisfy or that $\omega$ does satisfy is a bad definition of finite. But it might be there are two different countable sets. For example, if $D$ is an amorphous set, then $D\cup\omega$ is such that any smaller subset is either amorphous or equivalent to $D\cup\omega$. So by taking $X$ to be Dedekind-finite, or "finite or amorphous", both $\omega$ and $D\cup\omega$ are $X(2)$-countable.

You will notice, however, that these are somewhat contrived, as opposed to the various definition of finiteness, since countability is very inherently about the natural numbers. So it is kind of hard to get around that.