Abstract

The still unsettled decision problem for the restricted purely universal formulae 0-formulae) of the first order set-theoretic language based over =, ∈ is discussed in relation with the adoption or rejection of the axiom of foundation. Assuming the axiom of foundation, the related finite set-satisfiability problem for the very significant subclass of the 0-formulae consisting of the formulae involving only nested variables of level 1 is proved to be semidecidable on the ground of a reflection property over the hereditarily finite sets, and various extensions of this result are obtained. When variables are restricted to range only over sets, in universes with infinitely many urelements the set-satisfiability problem is shown to be solvable provided the axiom of foundation is assumed; if it is not, then the decidability of a related derivability problem still holds. That, in turn, suggests the alternative adoption of an antifoundation axiom under which the set-satisfiability problem is also solvable . Turning to set theory without urelements, assuming a form of Boffa's antifoundation axiom, the complement of the set-satisfiability problem for the full class of Δ0-formulae is shown to be semidecidable; a result that is known not to hold, for the set-satisfiability problem itself, even for a very restricted subclass of the Δ0-formulae