proof equivalence of formulation of foundation

We show that each of the three formulations of the axiom of foundation given are equivalent.

$1\Rightarrow 2$

Let $X$ be a set and consider any function $f:\omega \to \mathrm{tc}(X)$. Consider . By assumption, there is some $f(n)\in Y$ such that $f(n)\cap Y=\mathrm{\varnothing }$, hence $f(n+1)\notin f(n)$.

$2\Rightarrow 3$

Let $\varphi$ be some formula such that $\varphi (x)$ is true and for every $X$ such that $\varphi (X)$, there is some $y\in X$ such that $\varphi (y)$. Then define $f(0)=x$ and $f(n+1)$ is some $y\in f(n)$ such that $\varphi (y)$. This would construct a function violating the assumption, so there is no such $\varphi$.

$3\Rightarrow 1$

Let $X$ be a nonempty set and define $\varphi (x)\equiv x\in X$. Then $\varphi$ is true for some $X$, and by assumption, there is some $y$ such that $\varphi (y)$ but there is no $z\in y$ such that $\varphi (z)$. Hence $y\in X$ but $y\cap X=\mathrm{\varnothing }$.

Title	proof equivalence of formulation of foundation
Canonical name	ProofEquivalenceOfFormulationOfFoundation
Date of creation	2013-03-22 13:04:37
Last modified on	2013-03-22 13:04:37
Owner	Henry (455)
Last modified by	Henry (455)
Numerical id	6
Author	Henry (455)
Entry type	Proof
Classification	msc 03C99