T.Forster at dpmms.cam.ac.uk T.Forster at dpmms.cam.ac.uk
Mon Sep 19 17:47:15 EDT 2011

While we are on the subject of wellfoundedness and paradox, perhaps i might
mention an open problem that has been bothering me for some time. It is
easy to prove by $\in$-induction that every set has nonempty complement.
The proof is even constructive. (I know of no constructive proof by
$\in$-induction that every set has inhabited complement). The assertion
that $x$ has nonempty complement is parameter-free, and is stratified in
Quine's sense, and we can prove by $\in$-induction that every set has this
property. My question is this: is there any other formula $\phi(x)$ -
stratified and without parameters - for which we can prove $\forall x phi(x)$ by $\in$-induction? Put it another way: is there any parameter-free
stratified $\phi$ s.t we have an elementary proof that (\forall x)[(\forall
y)(y \in x \to \phi(y)) \to \phi(x)]
My expectation is that the answer is no', but i can't prove it - nor
can i find a counterexample!

`