# 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 |