A4.8 B4.10

Logic, Computation and Set Theory
Part II, 2001

What is a wellfounded relation, and how does wellfoundedness underpin wellfounded induction?

A formula ϕ(x,y)\phi(x, y) with two free variables defines an \in-automorphism if for all xx there is a unique yy, the function ff, defined by y=f(x)y=f(x) if and only if ϕ(x,y)\phi(x, y), is a permutation of the universe, and we have (xy)(xyf(x)f(y))(\forall x y)(x \in y \leftrightarrow f(x) \in f(y)).

Use wellfounded induction over \in to prove that all formulæ defining \in-automorphisms are equivalent to x=yx=y.