As is well-known, the Bernays-Schönfinkel-Ramsey class of all prenex ∃*∀* -sentences which are valid in classical first-order logic is decidable. This paper paves the way to an analogous result which the authors deem to hold when the only available predicate symbols are ∈ and =, no constants or function symbols are present, and one moves inside a (rather generic) Set Theory whose axioms yield the well-foundedness of membership and the existence of infinite sets. Here semi-decidability of the satisfiability problem for (...) the BSR class is proved by following a purely semantic approach, the remaining part of the decidability result being postponed to a forthcoming paper. (shrink)

We show that the Axiom of Foundation, as well as the Antifoundation Axiom AFA, plays a crucial role in determining the decidability of the following problem. Given a first-order theory T over the language $ =,\in$, and a sentence F of the form $ \forall x_1, \ldots, x_n \exists y F^M$ with $ F^M$ quantifier-free in the same language, are there models of T in which F is true? Furthermore we show that the Extensionality Axiom is quite irrelevant in that (...) respect. (shrink)

Let V be the cumulative set theoretic hierarchy, generated from the empty set by taking powers at successor stages and unions at limit stages and, following [2], let the primitive language of set theory be the first order language which contains binary symbols for equality and membership only. Despite the existence of ∀∀-formulae in the primitive language, with two free variables, which are satisfiable in V but not by finite sets ([5]), and therefore of ƎƎ∀∀ sentences of the same language, (...) which are undecidable in ZFC without the Axiom of Infinity, truth in V for Ǝ*∀∀-sentences of the primitive language, is decidable ([1]). Completeness of ZF with respect to such sentences follows. (shrink)