Axiom talk:Axiom of Foundation

Seems too long

I haven't closely examined the content of the axiom statement, but it seems much too lengthy for what I am familiar with. Takeuti / Zaring's "Introduction to Axiomatic Set Theory" introduces the axiom of regularity as:

$a \not = \varnothing \implies \exists x \in a: x \cap a = \varnothing$ (page 19).

Even if expanded into primitive membership relations, it is not this long. --asalmon 25 November 2011

I have tentatively added a shorter version that is still expanded into primitives. --asalmon 25 November 2011

You might want to add the Takeuti / Zaring work that you cite above in the "Books" section and then it can be referred to in the "sources" section. See examples of what's there already for what is usually done. --prime mover 04:33, 26 November 2011 (CST)

No infinite descending chain?

My lecture notes simply state that this forbids that $x\in x$ (which it obviously does), but I'm not sure why constructions like this are not allowed:

Let $E_0 = \varnothing$, and for $n\in\N$, $E_n = \{E_{n-1}\}$.

For $n\in\N$, let $S_n$ satisfy $S_n = \{S_{n+1}, E_n\}$.

Note that there is no problem with recursion as I might just have a set (or sequence of sets if you wish) satisfying this (assume it is given). It is not obvious why the $S_n$ cannot be sets (although the axiom page states that this is forbidden by the axiom). I am a little confused. Clarification will be appreciated. --Lord_Farin 03:52, 26 November 2011 (CST)

Proof sketch that there is no $S_n$ that satisfies that for all $n \in \N$: Let $F(n)$ be the same thing as $S _n$, such that the domain of $F$ is $\N$. By the axiom of infinity, the domain is a set, not a class. By the axiom of replacement, the range must also be a set, since $F$ is a function that maps $\N$ (a set) into its range. Thus, $F$ must be a set, because since both its domain and range are sets, $F$ is contained within the cross product of both its domain and range (which is itself a set).

The range of $F$ is a nonempty set. Therefore, by (weak) Regularity, $\exists x \in \operatorname{Ran} F: \forall y \in \operatorname{Ran} F: \neg y \in x$. Since $F$ is a function on $\N$, $\exists z \in \N: F(z) = x$ (by existential elimination), so $\exists z \in \N: \forall y \in \operatorname{Ran} F: \neg y \in F(z)$. However, by your construction, $\forall x \in \N: F(x+1) \in F(x)$. This is a contradiction, because $F(x+1) \in \operatorname{Ran} F$. --asalmon

Source - Takeuti/Zaring "Introduction to Axiomatic Set Theory" Theorem 7.34 (the presentation is different here, but this shows that theorem actually appears in literature).

Okay, I accept that this form doesn't work. However your proof seems to take ad hoc advantage of the form of the $S_n$ (I looked up the proof in Takeuti/Zaring). What about the different definition

For $n\in\N$, let $S_n$ satisfy $S_n = \{\{S_{n+1}\}, E_n\}$.

or, for all I care, some finite number of curly bracket pairs around that $S_{n+1}$. It doesn't satisfy $S_n \in S_{n+1}$ so the argument doesn't hold. --Lord_Farin 14:11, 26 November 2011 (CST)

This should not work either. Since $S_n$ is a set, $\{ S_n \}$ is a nonempty set. Now notice that $S_{n+1} \in \{ S_{n+1} \} \in S_{n}$. We can define a piece-wise function $F(n)$ such that

$F(n) = \left\{

   \begin{array}{lr}
      S_{n/2} & : n/2 \in \N \\
      \{ S_{(n-1)/2} \} & : n/2 \not \in \N
   \end{array}
  \right\}$

And $\forall n \in \N: F(n+1) \in F(n)$ --asalmon

Thanks again; I take it that the general form will also work; given my confusion and the fact that this is in fact a theorem in some books, we might add it as a separate page on PW if you're up to it (for of course the general proof that $\in$ is well-founded from this is harder, but interesting nonetheless). Thinking of it, well-founded might be intuitively called 'finitely nesting' (and loop-free); I am thinking out loud here, best just keep with well-founded. --Lord_Farin 17:58, 26 November 2011 (CST)