# 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\rightarrow\operatorname{tc}(X)$. Consider $Y=\{f(n)\mid n<\omega\}$. By assumption, there is some $f(n)\in Y$ such that $f(n)\cap Y=\emptyset$, hence $f(n+1)\notin f(n)$.

## $2\Rightarrow 3$

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

## $3\Rightarrow 1$

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

Title proof equivalence of formulation of foundation ProofEquivalenceOfFormulationOfFoundation 2013-03-22 13:04:37 2013-03-22 13:04:37 Henry (455) Henry (455) 6 Henry (455) Proof msc 03C99