# 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
Full Text: