# Do I need Axiom of Choice for ZF construction of the Natural Numbers?

Using ZF axioms I have constructed the natural numbers like so:

0 = ∅
1 = {0} = {∅}
2 = {0,1} = {∅,{∅}}
3 = {0,1,2} = {∅,{∅},{∅,{∅}}}
4 = {0,1,2,3} = {∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}}}
etc.

I am trying to determine if I used the axiom of choice for the representation. For the number $$0$$ I obviously did not since there is only one set with no elements. However, for the other sets, say for $$2$$, there is an infinite number of choices. i.e. $$\{ \; \{\emptyset\}, \{\{\{\emptyset\}\}\} \; \}$$ is another set with two elements in it.

However if we define the way we choose our sets through a successor property: $$S(X) = X \cup \{X\}$$ then we get the representative sets above. Because we used a property to pick our representation I don't think the Axiom of Choice is needed here. That is, we could use this property as a choice function.

Is this reasoning correct?

I am not sure what you mean by "we could use this property as a choice function", but ignoring that point you are correct.

Since you have explicitly defined $$S(X) = X \cup \{X\}$$ there is no choice involved here. You can very easily define any natural number $$n$$ as $$S^n(\emptyset)$$, which is an expression that you can expand and write down.

If you are taking a set theory class, though, it is worth noting that you have only constructed each individual number $$n$$ in this way. You have not constructed the set $$\omega$$ of all natural numbers. In order to build $$\omega$$ you need the axiom of infinity, and indeed $$\omega$$ itself (in the metatheory) provides a model of "most of ZF", with the axiom of infinity conspicuously absent. For more details see Kunen's (new) "Set Theory".

I hope this helps ^_^

• I should have stated that I'm taking the ZF axioms here as given. This includes the Axiom of Infinity. . – Idle Math Guy Jul 18 at 22:44

You don't need choice to construct the Von Neumann ordinals. FOr the finite ones, you can proceed as follows: as you noted, the empty set exists by "Empty Set Axiom" (or "Infinity" + "Comprehension"). Once you have $$\emptyset$$, use "Pairing" to get $$\{ \emptyset, \emptyset \}$$ which, by "Extensionality", is just $$\{ \emptyset \}$$; this is what we identify as $$1$$. Now suppose you have constructed $$n$$. Then by "Pairing", $$\{ n,n \} = \{ n \}$$ exists, and so does $$\{ n , \{ n \} \}$$. Finally, by "Union", $$\bigcup \{ n, \{ n \} \} = n \cup \{ n \}$$ exists, which we identify as $$n+1$$.

In general, ordinals are not just pairs of elements you've already constructed. They are, in particular, well-ordered by $$\in$$ and transitive. This would fail for $$\{ \emptyset, \{\{ \emptyset \}\} \}$$ (can you see why?).

• Your argument is using a weak form of the axiom of choice (called DC - the axiom of dependent choice). You need the axiom of infinity in some form to construct the set $\omega$ of all finite ordinals. – Rob Arthan Jul 18 at 22:10
• ... and note also that the OP is asking about a construction of the natural numbers: we aren't compelled to use transitive sets that are well-ordered by $\in$ to represent the natural numbers: see Benecerraf's famous paper "What numbers could not be". – Rob Arthan Jul 18 at 22:17
• I should have stated that I'm taking the ZF axioms here as given. This includes the Axiom of Infinity. – Idle Math Guy Jul 18 at 22:44
• @RobArthan I don't think I'm using the Axiom of Dependent Choice here. This would imply that available choices for $x_{n+1}$ depend on the choice of $x_n$ made at the previous stage. Since the empty set is the only available choice for the representation of $0$ I have no choice as to what sets to represent each number at each state. – Idle Math Guy Jul 18 at 23:04
• @IdleMathGuy: I think you have been a bit too idle about finishing off your last comment $\ddot{\smile}$. – Rob Arthan Jul 18 at 23:06