How to construct natural numbers by set theory?

Question

Definition 1: For any set $a$ , its successor $a^+=a\cup \{a\}$.

Informally , we want to construct natural numbers such that :
$0=\emptyset,1=\emptyset^+,2=\emptyset^{++},3=\emptyset^{+++}$,...

Definition 2: A natural number is a set that belongs to every inductive set.

Then we can construct a set $\omega$ whose members are exactly the natrual numbers . $\{x | x \text{ belongs to every inductive set } \}$
The discussion above was in Herbert B.Enderton's book . However , I did not see how to make a connection between $\{0,1,2,3,... \}$ and the natural number we define above .

My attempt :
$(1)$ $\omega$ is inductive , and is a subset of every other inductive set .
$(2)$ $\omega$ is the smallest inductive set . Every inductive subset of $\omega$ is concides with $\omega$ .
$(3)$ If we can prove $N=\{\emptyset,\emptyset^+,\emptyset^{++},\emptyset^{+++}, ... , ... \}$ is actually a set , then $N=\omega$ since $N$ is inductive and every member $x \in N$ also belongs to $\omega$ .

My question :
I want to define $N$ as $$\{x\in \omega | x \text{ is finite times successor of }\emptyset \}$$ However , the question happens when we want to define "finite times" . Although we can define finite by members belong to $\omega$ , how can we define finite times while we did not define even one number in our usual sense ?

Answer 1

You cannot prove $N=\{0,0^+, 0^{++}, \ldots\}$ is a set because the right hand side is not even a definition, merely suggestive notation. Your attempt of defining a natural number as something that takes the form of a finite number of successors applied to $0$ fails for the reasons you are beginning to suspect: you haven't defined what it means to be a finite number yet, let alone what it means to have said form, and such a thing seems rather hopeless without first having a definition of what it means to be a natural number.

What we might be tempted to do is "write down" an infinite disjunction: $$ \mathbb N = \{x: x =0\lor x=0^+\lor x=0^{++}\lor\ldots\}.$$ This would be a more logic-oriented approach to the intuitive "definition". However, infinite formulas are not allowed in the first order logic that underlies set theory. There are good reasons why we stick to first order logic, but I won't argue it here... I'll just note that making this definition requires we reason about completed infinities, which might be uncomfortably circular to a person approaching with a foundationalist mindset.

So we need to be somewhat less direct in our definition, and Enderton gives the most common approach. We define the notion of an inductive set as one that contains $0$ and is closed under the successor function, and then, crucially, we assume that an inductive set exists (this is the axiom of infinity, which, as its name suggests, is required for there to be any infinite sets at all). Then we define a natural number as a set belonging to every inductive set, and hence the set of natural numbers is the intersection of all the inductive sets.

(If there are no inductive sets, this definition does not work as intended since every set is vacuously a member of every inductive set. The set of natural numbers cannot be defined. However, the property of being a natural number can still be defined, but one needs to use a different definition that can be most succinctly phrased in terms of ordinals: a natural number is an ordinal that is not greater than or equal to any limit ordinal. CopyPasteIt's link has something similar that will work as well.)

The fact that we take the smallest possible inductive set is what corresponds to the idea that the set only contains zero and its successors, i.e. the only things that we need to be there in order to have an inductive set. However, we cannot hope to prove something of the form $\forall x\in\mathbb N(x=0\lor x=1\lor\ldots)$... as I remarked above, we cannot even express this notion in our language... if we could have we would have probably defined it this way.

So there's a reason Enderton defines the set of natural numbers as the intersection of all inductive sets rather than as $"\{0,1,2,\ldots\}"$ or as the set of all sets that can be obtained from $0$ by a finite number of applications of the successor function: this definition works in the desired framework and the latter two don't.

An earlier version of this answer made some remarks about non-standard models that may have misled you into thinking that somehow these naturals we define in set theory are not the "real" natural numbers. Make no mistake: what Enderton is doing here is giving a rigorous definition of the natural numbers within the framework of set theory. (And we can also define all the usual structure, arithmetic, etc.) The intention is to make precise the intuitive notion and also to unify with any number of other mathematical concepts that can also be encoded in ZF. So this set is intended to be the natural numbers for all intents and purposes.

(This is not the only way of looking at this: nobody says we have to use set theoretical foundations. Moreover, the concept of the natural numbers also has its own effective axiom system (PA or second order variants thereof) that we can use to study arithmetic and analysis in isolation. What is the 'real' natural numbers isn't really a sharp or in my opinion meaningful question.)

Answer 2

You can't define the set $\{\emptyset, \emptyset^+, \emptyset^{++}, \ldots\}$. If we can construct a set $X$ with the property $$\emptyset^{(n)}\in X \text{ for every natural number(external) } n,$$ then the compactness theorem provides that there might exist an element of $X$, which is not $\emptyset^{(n)}$ for every $n$.

Answer 3

There is a way to define the natural numbers directly. Unlike the standard definition, it is not self-referential in nature. Before getting to that, I will review the standard definition. The most well-known construction of the natural numbers, found in texts such as those by Enderton or Hrbacek and Jech, begins as follows:

An inductive set is any set $X$ such that $\emptyset \in X$, and for all sets $a$, if $a \in X$ then $S(a) \in X$.

Here, $S(a) = a \cup \{a\}$ denotes the successor of a. Then the Axiom of Infinity states:

There exists an inductive set.

This definition is self-referential in the sense that the property "if $a \in X$ then $S(a) \in X$" references $X$ itself. Therefore, rather than defining the extension (members) of $X$ explicitly, as the Axiom Schema of Specification does for example, this property defines the extension implicitly, making it less clear what $X$ actually is.

The final step is to define the natural numbers $\mathbb N$ as the intersection of all inductive sets. This does result in a unique set, but it does not fully resolve the self-referential nature of the definition, in the sense that it still doesn't immediately describe the members of $\mathbb N$ and their properties.

There is nothing necessarily wrong with this, nor is there any formal circularity or logical contradiction here. Rather the issue is more of a meta-circularity, and has more to do with bringing the self-evidence of the Axiom of Infinity into question. None of the other axioms of ZFC use these kind of self-referential definitions.

One could argue that rigorous (e.g. ZFC) set theory should attempt to model the intuition of naive set theory, at least as far as it can while avoiding contradictions like Russell's Paradox. In naive set theory, sets are thought of as obtained by collecting together objects using some criterion. This is formalized in the Axiom Schema of Unrestricted Comprehension. While this axiom schema leads to paradoxes, these can be avoided using its restricted form, the Axiom Schema of Specification. The idea is to specify exactly what elements are in the defined set.

This is a unifying and intuitively appealing conceptual approach, which the standard definition of $\mathbb N$ does not follow. On the other hand, defining $\mathbb N$ as the smallest inductive set does immediately indicate that proof by induction is applicable. So that is perhaps one motivation for that definition.

But in the case of your question, it is precisely this self-referential aspect of the the Axiom of Infinity which I believe is the issue. Your attempt to define $\mathbb N$ as

$\mathbb N = \{x \mid x = S^n(\emptyset) \, \text{for some finite} \, n\}$.

will not work, because we cannot write $S^n$, the $n$-fold composition of the successor function $S$, in our first-order language, only in the meta-language. In fact, we can't write $f^n$ in our language for any function $f$ (set or class). We can only express it indirectly as an element of a set guaranteed to exist by the Axiom of Infinity and the Axiom Schema of Replacement. But then, this already requires a definition of $\mathbb N$.

However, we can define what it means to be finite directly. As I mentioned above, there is a direct (i.e. comprehension-like) way to define the natural numbers. We do this using ordinals.

If we take the common von Neumann definition of ordinals, then an ordinal is a transitive set that is well-ordered by set membership ($\in$). Furthermore, we define an ordinal $\alpha$ to be finite if every non-empty subset of $\alpha$ has a maximal element (with respect to the order defined by $\in$). Note the similarity of this definition to the well-founded property of a well-ordering, namely that every non-empty subset has a minimal element. From these definitions, it follows that the first few finite ordinals are $\emptyset$, $\{\emptyset\} = S(\emptyset)$, $\{\emptyset, \{\emptyset\}\} = S^2(\emptyset)$, etc.

Then we can define the natural numbers $\omega$ to be

$\omega = \{\alpha \mid \alpha \, \text{is a finite ordinal}\}$.

Of course, without an axiom asserting that such a set exists, this is just a class. We could just replace the Axiom of Infinity with the assertion that the above class is a set. But we may as well just use the Axiom of Infinity, because as it turns out, using the definitions above, $\omega = \mathbb N$. In the remainder of this answer, I will prove this.

Proof. First we prove $\mathbb N \subseteq \omega$. We will show that $\omega$ is an inductive set. First note that $\emptyset \in \omega$. Now let $\alpha \in \omega$. Then $\alpha$ is a transitive set, and $\alpha \subseteq \alpha \cup \{\alpha\} = S(\alpha)$, so $S(\alpha)$ is a transitive set as well. Furthermore, since $\alpha$ is an ordinal, the set membership relation $\in$ defines a trichotomous, transitive, well-founded order on $\alpha$. Since for all $\beta \in S(\alpha)$, we have either $\beta \in \alpha$ or $\beta = \alpha$ by the definition of $S(\alpha)$, this order extends to a trichotomous, transitive order on $S(\alpha)$. To see that this order is also well-founded on $S(\alpha)$, let $A \subseteq S(\alpha)$ be non-empty. If $\alpha \notin A$ then $A \subseteq \alpha$, hence $A$ has a minimal element because $\alpha$ is an ordinal. Otherwise, by trichotomy of the order, the minimal element of $A$ is either $\alpha$ or the minimal element of $A \cap \alpha$, the latter of which exists because $A \cap \alpha \subseteq \alpha$. Finally, note that $\alpha$ is a maximal element of $S(\alpha) = \alpha \cup \{\alpha\}$, since $\alpha \not \in \alpha$, and for all $\beta \in \alpha$, $\alpha \notin \beta$ by trichotomy of the order. Therefore, every subset $A \subseteq S(\alpha)$ has a maximal element, which is either guaranteed to exist by the finiteness of $\alpha$ if $A \subseteq \alpha$, or is equal to $\alpha$ otherwise. Thus $S(\alpha)$ is a finite ordinal, so $S(\alpha) \in \omega$. This shows that $\omega$ is indeed an inductive set. Since $\mathbb N$ is the intersection of all inductive sets, $\mathbb N \subseteq \omega$.

Now we prove that $\omega \subseteq \mathbb N$. Suppose, for a contradiction, that there is an $\alpha \in \omega$ for which $\alpha \notin \mathbb N$. Since $\emptyset \in \mathbb N$ by definition, we may assume $\alpha \neq \emptyset$. Since $\alpha$ is a non-empty finite ordinal, it has a maximal element, call it $\gamma_0$. Then by the trichotomy of the set membership order on $\alpha$, for all $\beta \in \alpha$ either $\beta = \gamma_0$ or $\beta \in \gamma_0$. Therefore $\alpha = S(\gamma_0)$. Since $\alpha \notin \mathbb N$ and $\mathbb N$ is inductive, we must have $\gamma_0 \notin \mathbb N$. So the set $B = \{\beta \in \alpha \mid \beta \notin \mathbb N\}$ is non-empty. Since $B \subseteq \alpha$ and $\alpha$ is an ordinal, $B$ has a minimal element, call it $\beta_0$. Then $\beta_0$ must be non-empty, for otherwise $\beta_0 = \emptyset \in \mathbb N$ by definition of $\mathbb N$, contradicting the definition of $B$. Since $\beta_0 \in \alpha$ and $\alpha$ is a transitive set, $\beta_0 \subseteq \alpha$. Therefore, being a non-empty subset of the finite ordinal $\alpha$, $\beta_0$ has a maximal element, call it $\gamma_1$. By the same reasoning as above, $\beta_0 = S(\gamma_1)$. But then, because $\beta_0 \notin \mathbb N$ and $\mathbb N$ is inductive, we must also have $\gamma_1 \notin \mathbb N$. Note that $\gamma_1 \in \beta_0 \in \alpha$, so by transitivity $\gamma_1 \in \alpha$. This, together with the fact that $\gamma_1 \notin \mathbb N$, means that $\gamma_1 \in B$, contradicting the minimality of $\beta_0$. Therefore $\alpha$ must be an element of $\mathbb N$, and thus $\omega \subseteq \mathbb N$.

We conclude that $\omega = \mathbb N$. $\blacksquare$