# The axiom of infinity for Zermelo–Fraenkel set theory

The axiom of infinity for Zermelo–Fraenkel set theory is stated as follows in the wikipedia page:

Let $S(w)$ abbreviate $w \cup \{w\}$, where $w$ is some set (We can see that $\{w\}$ is a valid set by applying the Axiom of Pairing with $x=y=w$ so that the set $z$ is $\{w\}$). Then there exists a set $X$ such that the empty set $\varnothing$ is a member of $X$ and, whenever a set $y$ is a member of $X$, then $S(y)$ is also a member of $X$.

I don't understand the intuition behind the set $w \cup \{w\}$. Why this causes the set $X$ to be infinite ? I think $\{w\}$ is enough.

-
Natural numbers may provide the intuition: $0:=\emptyset,1:=\{0\}=S(\emptyset), 2:=\{0,1\}=S(1), 3:=\{0,1,2\}=S(2)\cdots$. –  Shahab Apr 20 '13 at 11:18
Asaf vs B.M.S${}$ –  Git Gud Apr 20 '13 at 11:21
"I think $\{w\}$ is enough." The problem with defining $S(w)=\{w\}$ is that we cannot have an infinite set without violating the axiom of foundation. I.e. if $\alpha$ is infinite with respect to this definition of $S$, then $S(\alpha)=\{\alpha\}=\alpha$. So $\alpha\in\alpha$, a contradiction. –  Karl Kronenfeld Apr 20 '13 at 11:29
@user1: Your argument seems confused. Certainly, you are correct that having $\{a\}=a$ would violate the axiom of foundation. But there is nothing wrong in an axiom of infinity relying on $S(w)=\{w\}$. Naïvely, this establishes the existence of $\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\ldots\}$, which is a perfectly fine set. The customary definition is more convenient, that is all. –  Harald Hanche-Olsen Apr 20 '13 at 11:50
@HaraldHanche-Olsen Of course! I was imagining $A$ would be a singleton under this definition for some reason. Thank you for your patience. –  Karl Kronenfeld Apr 20 '13 at 15:37

Morally speaking[1] the Axiom of Foundation we can aid us in showing that for each positive natural number $m$ (existing in the meta-theory) and every set $x$ the set $$S^{(m)} ( x ) = \overbrace{S ( \cdots ( S}^{m\text{ times}} ( x ) ) \cdots )$$ is distinct from $x$. We first show by induction (I guess in the meta-theory) that $x \in S^{(m)}(x)$ for all $m \geq 1$, and then note that by Foundation $x \notin x$, and so each $S^{(m)}(x)$ must differ from $x$.

It then follows that the sets $\varnothing$, $S(\varnothing)$, $S ( S ( \varnothing ) )$, $\ldots$ are pairwise distinct. Since your inductive set $X$ must contain all of these, that set must be infinite (at least from the point-of-view of the meta-theory).

Added: An alternative approach, done through the exercises in Ch.1 of Jech's Set Theory, is to define a set $N$ to be the smallest inductive set (i.e., the intersection of all inductive subsets of some given inductive set), and then show that the elements of $N$ have certain properties that then imply the infiniteness (non-finiteness?) of $N$. It is somewhat tedious (since it avoids overtly mentioning ordinals, and in particular $\omega$), but is also clean and without circularity. Once ordinals are defined, it turns out that $N$ is actually $\omega$ (what a surprise!).

[1] By which I mean that there may be inaccuracies in what I am about to say, but the gist is pretty close to the actual truth. I thank Prof. Sy David Friedman for putting this phrasing into my mathematical vocabulary.

-
If you start with $0=\varnothing$ then you don't need foundations. –  Asaf Karagila Apr 20 '13 at 11:32
@Asaf: True, but then pickles won't arrive when you want them to. (I've got a few willing participants in the Great 2013 Massive Pickle Exchange.) –  Arthur Fischer Apr 20 '13 at 11:34
You mean the Young Spreewaldhof Transporters 2013 conference? :-) –  Asaf Karagila Apr 20 '13 at 11:36
I'm confused. How are you using induction before having the natural numbers? –  Git Gud Apr 20 '13 at 11:38
@GitGud: If you stop spinning in your chair you might see less circularity! It could help with the nausea and seasickness too! :-) –  Asaf Karagila Apr 20 '13 at 12:20

The intuition comes from the definition of the von Neumann ordinals. We define an ordinal as the set of its predecessors, which means that the successor ordinal of $\alpha$ is exactly $\alpha\cup\{\alpha\}$.

The finite ordinals corresponds to the natural numbers, so we can easily define $0=\varnothing$ and $n+1=n\cup\{n\}$. The axiom of infinity is equivalent to saying that there is a set whose members are exactly all the finite ordinals.

-

With Extensionality, Power Set, and Separation, a signleton exists. All {∅}, {{∅}}, {{{∅}}}, ..., are of cardinality 1. You cannot generate an infinite set/class this way.

Class A is ordinal (written as Ord A) iff A is transitive and is well-ordered by the epsilon relation. Define the class of all ordinal numbers On = { x | Ord x }.

With neither Infinity nor Regularity, \eqref{ordom} and \eqref{ordeleqon} are provable. $$\operatorname{Ord} \omega \tag{1} \label{ordom}$$ $$\operatorname{Ord} A \leftrightarrow \left( A \in \mathrm{On} \lor A = \mathrm{On} \right) \tag{2} \label{ordeleqon}$$

Consequently, ω ∈ On ∨ ω = On. If ω is not a member of On, ω = On, which does not exist. Converse this proposition. If ω exists, it is an ordinal number. $$\omega \in \mathrm V \to \omega \in \mathrm{On}$$

The Axiom of Infinity asserts the existence of ω. $$\omega \in \mathrm V$$

A finitist denies existence of ω. This leads to ω = On. A finitist can develop natural number, integer, and rational number arithmetic but be denied the real numbers (as well as much of the rest of mathematics).

-