In Zermelo-Frankel set theory, the Axiom of Infinity is often stated as

"There exists a set $X$ such that $\emptyset \in X$ and such that if $y\in X$ then $S^{+}_1(y)\in X$",

where we take the successor function as $S^{+}_1(y) = y\cup \{y\}$. I believe the original formulation for the Axiom of Infinity by Zermelo had a different form, where the successor function was instead $S^{+}_2(y) = \{y\}$.

Let's call the form of the Axiom of Infinity with $S^{+}_1$ "Infinity 1" and the form with $S^{+}_2$ "Infinity 2". Changing from "Infinity 2" to "Infinity 1" made the axiom easier to work with, but the two formulations should be equivalent.

How can we prove that "Infinity 1" and "Infinity 2" are equivalent under the remaining ZF axioms?

  • 1
    $\begingroup$ As @Nishant notes, we can recursively define maps from the finite von Neumann ordinals ($0$, $n +1 = n \cup \{n\}$) and the finite Zermelo ordinals ($0$, $n+ 1 = \{ n\}$). Replacement then implies that the set of the former exist iff the set of the latter do. But it's worth noting that in the absence of Replacement this can fail in both directions. See jstor.org/stable/… $\endgroup$ – GME May 6 '15 at 16:12
  • $\begingroup$ Did Zermelo even had an axiom of infinity? $\endgroup$ – Asaf Karagila May 6 '15 at 17:15
  • $\begingroup$ @AsafKaragila If the wikipedia page for Zermelo set theory is to be believed, then yep; and it was Infinity 2. $\endgroup$ – GME May 6 '15 at 18:23
  • $\begingroup$ @GME: Interesting, I somehow recalled that there wasn't something like that; but maybe I was thinking about the very early axiomatizations, and maybe I was just thinking about how the Zermelo encoding of $\Bbb N$ cannot be extended transfinitely. $\endgroup$ – Asaf Karagila May 6 '15 at 18:25
  • $\begingroup$ @AsafKaragila What do you think goes wrong in the transfinite case? (Assuming we take unions at limits.) $\endgroup$ – GME May 6 '15 at 18:50

If you're allowed to use Replacement, you can recursively define a map from an inductive set of the second kind to an inductive set of the first kind by just setting $f(\varnothing)=\varnothing, f(S_2^+(y))=S_1^+(f(y))$, and then the image, which is a set by Replacement, will be an inductive set of the first kind.


Really what we have here is the statement that there is a function $S(x)$, which is injective (as a consequence of regularity, of course), and there is a set $X$ such that $\varnothing\in X$, and $X$ is closed under $S$. Let us call such set $X$, "$S$-inductive".

Assuming the $S_1(x)=x\cup\{x\}$ definition, note that $V_\omega=\bigcup_{n\in\omega}\mathcal P^n(\varnothing)$ is inductive for $S_1$, but it is also inductive for $S_2(x)=\{x\}$. So $\sf ZF$ proves the axiom $\sf Inf_{\it S_2}$.

On the other hand, $\sf ZF-Inf$ proves there is a rank function from sets to the ordinals, since any inductive set is necessarily infinite, it cannot have a finite rank, so if $X$ is $S_2$-inductive its rank is infinite, so there are infinite ordinals. Take the least infinite ordinal, and it is indeed an $S_1$-inductive set.


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.