Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
@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

3 Answers 3

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.

share|improve this answer
    
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
1  
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
1  
@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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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