| Autor: |
Cantone, Domenico, Omodeo, Eugenio G, Panettiere, Mattia |
| Předmět: |
|
| Zdroj: |
Journal of Logic & Computation; Jun2023, Vol. 33 Issue 4, p738-763, 26p |
| Abstrakt: |
In a first-order theory |$\varTheta $| , the decision problem for a class of formulae |$\varPhi $| is solvable if there is an algorithmic procedure that can assess whether or not the existential closure |$\varphi ^{\exists }$| of |$\varphi $| belongs to |$\varTheta $| , for any |$\varphi \in \varPhi $|. In 1988, Parlamento and Policriti already showed how to tailor arguments à la Gödel to a very weak axiomatic set theory, referring them to the class of |$\varSigma _{1}$| -formulae with |$(\forall \exists \forall)_{0}$| -matrix, i.e. existential closures of formulae that contain just restricted quantifiers of the forms |$(\forall x \in y)$| and |$(\exists x \in y)$| and are writable in prenex form with at most two alternations of restricted quantifiers (the outermost quantifier being a ' |$\forall $| '). While revisiting their work, we show slightly less weak theories under which incompleteness for recursively axiomatizable extensions holds with respect to existential closures of |$(\forall \exists)_{0}$| -matrices, namely formulae with at most one alternation of restricted quantifiers. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
