×

zbMATH — the first resource for mathematics

Zum Reduktionstyp \(\exists ^{\infty}\forall \exists \forall (0,1)\) und zur spektralen Darstellung \(\rho\)-stelliger aufzählbarer und koaufzählbarer Prädikate durch Ausdrücke aus \(\exists ^{\infty}\forall \exists \forall (\rho,1)\). (German) Zbl 0718.03023
Let \({\mathcal M}\) be the least set such that \(\emptyset \in {\mathcal M}\) and \(\{\) \(x\}\in {\mathcal M}\), \(x\cup y\in {\mathcal M}\) for any sets x,y\(\in {\mathcal M}\), \(L_{\rho}\) be the first-order language with unique two-place predicate constant E and with one-place \(P_ 1,...,P_{\rho}\) if \(\rho\geq 1\). There are proved, in particular, the following results: 1) For any sentence \(\alpha\) from \(L_ 0\) there can be effectively constructed \(\beta\) from the fragment \(\exists^{\infty}\forall \exists \forall (0,1)\) of \(L_ 0\) such that \(\alpha\) is (finitely) satisfiable \(\Leftrightarrow\beta\) is (finitely) satisfiable \(\Leftrightarrow\) \(<U;\in >\vDash \beta\), where U is some (finite) transitive subset of \({\mathcal M}\). 2) Let P and \(\neg Q\) be \(\rho\)-place (\(\rho\geq 1)\) recursively enumerable predicates on N and \(Px_ 1,...,x_{\rho}\Rightarrow Qx_ 1...x_{\rho}\). Then there exists \(\beta\) from \(\exists^{\infty}\forall \exists \forall (\rho,1)\) such that a) \(Px_ 1...x_{\rho}\Leftrightarrow\) there exists a model \(I=<U;\in,P_ 1,...,P_{\rho}>\) of \(\beta\) such that U is a finite transitive subset of \({\mathcal M}\) and \(| I(P_ i)| =x_ i\) (1\(\leq i\leq \rho)\); b) \(Qx_ 1...x_{\rho}\Leftrightarrow\) there exists a model \(I=<U;\in,P_ 1,...,P_{\rho}>\) of \(\beta\) such that U is a transitive subset of \({\mathcal M}\) and \(| I(P_ i)| =x_ i\).

MSC:
03C30 Other model constructions
03D25 Recursively (computably) enumerable sets and degrees
03D05 Automata and formal grammars in connection with logical questions
PDF BibTeX XML Cite
Full Text: DOI