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

Question

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?

Answer 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.

Answer 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$.

Answer 3

I was informed by an expert that this answer is is 'practically that of Andrés' (see comment). Here we deploy less sophistication so it should be of interest to the student just starting to explore mathematical concepts.

---

We begin by defining, up to isomorphism, the algebraic structure $(\Bbb N,+,*)$.

Let $f: A \to A$ be an injective mapping that is not surjective.

Let $a_0 \in A \setminus f(A)$.

Consider the statement

$\quad {\mathbf {S}: \displaystyle \exists \mathbf {I} \,\bigr(\,a_0 \in \mathbf {I} \,\land \,\forall x\in \mathbf {I} \,(x \in \text{Domain of } f \land f(x) \in \mathbf {I})\,\bigr)}$

(c.f. axiom of infinity)

Since

$\quad {\displaystyle a_0 \in A \,\land \,\forall x\in A \,\bigr(x \in \text{Domain of } f \land f(x) \in A\bigr)}$

statement $\mathbf {S}$ is true.

The intersection of all sets $J$ satisfying

$\quad {\displaystyle a_0 \in J \,\land \,\forall x\in J \,\bigr(x \in \text{Domain of } f \land f(x) \in J\bigr)}$

is our definition of the natural numbers $\Bbb N$ (here a subset of $A$). In essence, we're applying Peano's method in this axiomatic context. The object of interest is the function $f$ restricted to $\Bbb N$ giving us the abstract Peano successor function,

$\quad f = \sigma: \Bbb N \to \Bbb N$

The Peano construction can be found in Appendix I of Serge Lang's Undergraduate Algebra.

For the next step, use recursion to define a mapping $g$ defined on $\Bbb N$.

Set

$\quad g(0) = \emptyset$

With $g(n)$ defined, set

$\quad g(n+1) = g(n) \cup \{g(n)\}$

We can now construct the OP's minimal inductive set,

$\quad \displaystyle \omega = \bigcup_{n \in\Bbb N} g(n)$

Answer 4

The answers given above mention natural numbers, but there is no need: read Dedekind's "Wass sind und wass sollen die Zahlen?". In there he does what CopyPasteIt describes and very carefully proves that all desirable properties of $\mathbb{N}$ hold in the smallest set $N$ that contains $a_0$ and is closed under $f$. Unlike Andres he refrains from writing $N=\{f^n(a_0):n$ is a natural number$\}$ because there is no need (and it would be self-referential as $n=f^n(a_0)$ in hindsight).

The map $g$ can be defined by recursion on $N$ by $g(a_0)=\emptyset$ and $g(f(x))=g(x)\cup\{g(x)\}$; here Replacement comes into play to show that $g$ and hence its range is a set. Or you can deduce from Dedekind's work that $N$ is an infinite well-ordered set and observe that its order-type is an inductive set.