3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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 ^_^

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I should have stated that I'm taking the ZF axioms here as given. This includes the Axiom of Infinity. . $\endgroup$ – Idle Math Guy Jul 18 at 22:44
2
$\begingroup$

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?).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rob Arthan Jul 18 at 22:10
  • 1
    $\begingroup$ ... 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". $\endgroup$ – Rob Arthan Jul 18 at 22:17
  • $\begingroup$ I should have stated that I'm taking the ZF axioms here as given. This includes the Axiom of Infinity. $\endgroup$ – Idle Math Guy Jul 18 at 22:44
  • $\begingroup$ @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. $\endgroup$ – Idle Math Guy Jul 18 at 23:04
  • $\begingroup$ @IdleMathGuy: I think you have been a bit too idle about finishing off your last comment $\ddot{\smile}$. $\endgroup$ – Rob Arthan Jul 18 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.