×

The decidability of the \(\forall ^*\exists\) class and the axiom of foundation. (English) Zbl 1023.03007

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.

MSC:

03B25 Decidability of theories and sets of sentences
03E65 Other set-theoretic hypotheses and axioms
03C62 Models of arithmetic and set theory
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.