proof equivalence of formulation of foundation

We show that each of the three formulations of the axiom of foundationMathworldPlanetmath given are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath.


Let X be a set and consider any function f:ωtc(X). Consider Y={f(n)n<ω}. By assumptionPlanetmathPlanetmath, there is some f(n)Y such that f(n)Y=, hence f(n+1)f(n).


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


Let X be a nonempty set and define ϕ(x)xX. Then ϕ is true for some X, and by assumption, there is some y such that ϕ(y) but there is no zy such that ϕ(z). Hence yX but yX=.

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