Bellè, Dorella; Parlamento, Franco The decidability of the \(\forall ^*\exists\) class and the axiom of foundation. (English) Zbl 1023.03007 Notre Dame J. Formal Logic 42, No. 1, 41-53 (2001). Summary: We show that the Axiom of Foundation, as well as the Antifoundation Axiom AFA, play 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, \dots, x_n\exists yF^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. Cited in 1 Document MSC: 03B25 Decidability of theories and sets of sentences 03E65 Other set-theoretic hypotheses and axioms 03C62 Models of arithmetic and set theory Keywords:extensionality axiom; antifoundation axiom; axiom of foundation; decidability; first-order theory × Cite Format Result Cite Review PDF Full Text: DOI References: [1] Aczel, P., Non-well-founded Sets , CSLI Lecture Notes, CSLI, Stanford, 1988. · Zbl 0668.04001 [2] Bellè, D., and F. Parlamento, ”Decidability and completeness for open formulas of membership theories”, Notre Dame Journal of Formal Logic , vol. 36 (1995), pp. 304–18. · Zbl 0837.03007 · doi:10.1305/ndjfl/1040248461 [3] Bellè, D., and F. Parlamento, ”Undecidability in weak membership theories”, pp. 327–37 in Logic and Algebra , Lecture Notes in Pure and Applied Mathematics, edited by A. Ursini and P. Aglianò, Dekker, New York, 1996. · Zbl 0858.03014 [4] Lewis, H. R., Unsolvable Classes of Quantificational Formulas , Addison-Wesley, 1979. · Zbl 0423.03003 [5] Omodeo, E. G., F. Parlamento, and A. Policriti, ”Decidability of \(\exists^ *\forall\)”-sentences in membership theories, Mathematical Logic Quarterly , vol. 42 (1996), pp. 41–58. · Zbl 0836.03011 · doi:10.1002/malq.19960420105 [6] Parlamento, F., A. Policriti, and K. P. S. B. Rao, ”Witnessing differences without redundancies”, Proceedings of the American Mathematical Society , vol. 125 (1997), pp. 587–94. · Zbl 0857.03027 · doi:10.1090/S0002-9939-97-03630-7 [7] Parlamento, F., and A. Policriti, ”Note on: ‘The logically simplest form of the infinity axiom”’, Proceedings of the American Mathematical Society , vol. 108 (1990), pp. 285–86. · Zbl 0694.03031 · doi:10.2307/2047726 [8] Parlamento, F., and A. Policriti, ”Expressing infinity without foundation”, The Journal of Symbolic Logic , vol. 56 (1991), pp. 1230–35. JSTOR: · Zbl 0744.03051 · doi:10.2307/2275470 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.