Existence of an injection from $\Bbb N$ without the axiom of choice

If you have a set $A$, and it satisfies that for some $x\in A$, there is a bijection between $A$ and $A\setminus\{x\}$.

Does that imply that there is an injection from $\Bbb N$ to $A$?
It is clearly true in ZFC, but I ask if it is true in ZF.

Solutions Collecting From Web of "Existence of an injection from $\Bbb N$ without the axiom of choice"

Yes. This is true in ZF. If $A$ has this property then we say that $A$ is Dedekind-infinite.

To see that it is true simply fix an injection $f\colon A\to A\setminus\{x\}$, and define $F\colon\Bbb N\to A$ as follows:

$$F(0)=x; F(n)=f(F(n-1))$$

Note that $F(1)=f(x)\neq f(f(x))=F(2)$, since $x\notin A$ we have that $f(x)\notin\operatorname{rng}(f\circ f)$; and so on we can see that $F$ is injective.

Similarly, if such injection from $\Bbb N$ into $A$ exists then we can find an injection from $A$ into $A\setminus\{x\}$, but I will leave this as an exercise for you.


It is trivial to see that assuming the axiom of choice every infinite set is Dedekind-infinite, but without the axiom of choice it is consistent that there are infinite sets which are not Dedekind-infinite. Those sets are called Dedekind-finite and they have the property that every self-injection is a bijection.

Interestingly enough, it is consistent that there are infinite Dedekind-finite sets that can be surjected onto themselves with an additional element.

So while it holds that if $X$ is finite then $f\colon X\to X$ is injective if and only if it is surjective if and only if it is bijective; this is not necessarily true for Dedekind-finite sets when the axiom of choice fails.

Yes. Let $\varphi:A\to A\setminus\{x\}$ be a bijection. Define $f:\Bbb N\to A$ recursively by $f(0)=x$, and $f(n+1)=\varphi\big(f(n)\big)$ for $n\in\Bbb N$. $\mathsf{ZF}$ is sufficient to justify this construction of $f$. (Sets with this property are said to be Dedekind infinite.)