# 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?

• Does Hagen's answer to a different-but-related question at math.stackexchange.com/a/763561/785 answer yours? (Essentially, choose such a set, show that there's a smallest ordinal which can't be injected into your Dedekind-infinite set, show that ordinal isn't finite, use well-ordering to find a smallest such non-finite ordinal)? That feels like it might use induction in disguise for some of the well-ordering properties, though... Commented May 30, 2014 at 17:07

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.

• "infinite set" meaning that for every natural number $n$ it contains a subset of $n$ elements? How do you define natural numbers before you constructed $\omega$? Or do you mean "Tarski-infinite"? Commented May 30, 2014 at 18:10
• Either version is fine (they are equivalent). You can define natural numbers as those ordinals all of whose non-empty elements are succesor ordinals. Commented May 30, 2014 at 18:38
• @Vladimir: The term "Tarski-finite" can have several meanings. In either case, there are more than a handful of definitions of "finite", all of which the finite ordinals satisfy, so you are free to choose whichever you'd like, and use that. Commented May 30, 2014 at 20:19
• In your comment, do you mean:define the natural number as those ordinals whose non empty elements are successor ordinals and that there is a maximal element of the ordinal? Commented Feb 10, 2022 at 16:16
• @Logic As for the definition of natural number: Yes, sorry for the typo. Regarding replacement, on the other hand, I expect its use is essential, but haven't really thought about it to know for sure. Commented Feb 11, 2022 at 0:05

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,1 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$$.

• I know this is an old answer, but how would you go about proving that $\operatorname{TC}(A)$ exists without already having $\omega$?
– Anon
Commented Jul 10 at 23:37
• @Anon: That's a great question. Because we have Foundation and Replacement we have the von Neumann hierarchy. So every set lives inside a transitive set (that is, some $V_\alpha$), so we can take the intersection of all such transitive sets, which is the transitive closure. Commented Jul 11 at 7:24

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.

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)$$

• That doesn't answer the question. Commented Jun 14, 2020 at 7:42
• @AsafKaragila I made some changes. Please downvote if there is no remedy (precision) that can applied to fix any minor 'loose ends'. You are welcome to edit the answer if you think it is salvageable. Commented Jun 14, 2020 at 9:37
• Now you've answered the question, but your answer is practically that of Andrés. Of course there's no issue with duplicated answers, but it is a bit annoying when this duplication comes six years too late. At the very least, you might want to clarify that the argument is the same. Commented Jun 14, 2020 at 10:26