6
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Natural numbers may provide the intuition: $0:=\emptyset,1:=\{0\}=S(\emptyset), 2:=\{0,1\}=S(1), 3:=\{0,1,2\}=S(2)\cdots$. $\endgroup$
    – user10575
    Commented Apr 20, 2013 at 11:18
  • $\begingroup$ Asaf vs B.M.S${}$ $\endgroup$
    – Git Gud
    Commented Apr 20, 2013 at 11:21
  • $\begingroup$ "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. $\endgroup$ Commented Apr 20, 2013 at 11:29
  • 2
    $\begingroup$ @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. $\endgroup$ Commented Apr 20, 2013 at 11:50
  • $\begingroup$ @HaraldHanche-Olsen Of course! I was imagining $A$ would be a singleton under this definition for some reason. Thank you for your patience. $\endgroup$ Commented Apr 20, 2013 at 15:37

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ If you start with $0=\varnothing$ then you don't need foundations. $\endgroup$
    – Asaf Karagila
    Commented Apr 20, 2013 at 11:32
  • $\begingroup$ @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.) $\endgroup$
    – user642796
    Commented Apr 20, 2013 at 11:34
  • 1
    $\begingroup$ You mean the Young Spreewaldhof Transporters 2013 conference? :-) $\endgroup$
    – Asaf Karagila
    Commented Apr 20, 2013 at 11:36
  • $\begingroup$ I'm confused. How are you using induction before having the natural numbers? $\endgroup$
    – Git Gud
    Commented Apr 20, 2013 at 11:38
  • 1
    $\begingroup$ @GitGud: If you stop spinning in your chair you might see less circularity! It could help with the nausea and seasickness too! :-) $\endgroup$
    – Asaf Karagila
    Commented Apr 20, 2013 at 12:20
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.