How can I define $\mathbb{N}$ if I postulate existence of a Dedekind-infinite set rather than existence of an inductive set?

Suppose in the axioms of $\sf ZF$ we replaced the Axiom of infinity

There exists an inductive set.

with the Axiom of Dedekind-infinite set

There exists a set equipollent with its proper subset.

How can I define the set of natural numbers $\mathbb{N}$ in this setting, and prove that it is the unique minimal inductive set?

Solution 1:

Asaf's argument uses foundation, let me sketch an argument avoiding it:

Note that $\omega$ is a definable class --it is either an ordinal, and we are done, or the class of all ordinals. The issue is to show that it is a set. Let $D$ be Dedekind-infinite, and let $f:D\to D$ be injective but not surjective. This means that there is an $x\in D$ but not in the image of $f$. We can use recursion (since the natural numbers can be defined and their basic properties established) to show that $x,f(x),f^2(x),\dots$ are all different. The set $\{f^n(x)\mid n$ is a natural number$\}$ exists, by comprehension. By replacement, so does $\omega$.

By the way, you can adopt the even weaker axiom: There is an infinite set. The point is that if $X$ is infinite, then $\mathcal P(\mathcal P(X))$ is Dedekind infinite.

Solution 2:

Suppose that $A$ is a Dedekind-infinite set. First consider $T=\operatorname{TC}(A)$, the transitive closure of $A$. Now consider the function $f(x)=\operatorname{rank}(x)$, whose domain is $T$.

By the axiom of replacement the range of $f$ is a set, and it is not hard to prove that it has to be an ordinal.

Finally, prove by induction that if $n$ is a finite ordinal,¹ then there are no Dedekind-infinite sets of rank $n$ (we don't need an inductive set, if such set doesn't exist then this is just an induction on the class of ordinals). And therefore there is an infinite ordinal in the range of $f$. Take $\omega$ as the least such ordinal.

1. It is easy to define a finite ordinal if you already know what $\omega$ is, but in its absence you can define a finite ordinal to be a Dedekind-finite ordinal; or if you really like then you can use one of the many other formulations of finiteness. My favorite is due to Tarski:

   $A$ is finite if and only if for every $U\subseteq\mathcal P(A)$ which is non-empty, there is a $\subseteq$-maximal element in $U$.