Effective model theory vs. recursive model theory. (English) Zbl 0722.03030

The author suggests a new approach in studying effectiveness in model theory that he calls “effective model theory”. This approach allows models of arbitrary algorithmic complexity but all notions should be relativized to the complexity of models. The author studies such series of notions as recursive stability, effective stability, recursive categoricity, effective categoricity etc., and studies their connections with effective definability by recursive formulas of \(L_{\omega_ 1\omega}\). The definitions of these notions are very long, so we give only one sample result:
Two definitions at first. A relation \(S\subseteq {\mathfrak A}^ n\) is said to be effectively \(\Sigma^ 0_{\alpha}\) iff for every model \({\mathfrak B}\) and isomorphism \({\mathfrak B\to {\mathfrak A}}\), \(f^{-1}(S)\) is a \(\Sigma^ 0_{\alpha}\)-set with respect to the atomic diagram of \({\mathfrak B}\). A relation \(S\subseteq {\mathfrak A}^ n\) is said to be formally \(\Sigma^ 0_{\alpha}\) iff it can be defined by a recursive \(\Sigma^ 0_{\alpha}\)-formula with a finite number of parameters. The sample result is the following: Let \(\alpha >0\). Fix a recursive model \({\mathfrak A}\) and a \(\Sigma^ 0_{\alpha}\)-set \(S\subseteq {\mathfrak A}^ n\). Then the following are equivalent: a) S is effectively \(\Sigma^ 0_{\alpha}\). b) S is formally \(\Sigma^ 0_{\alpha}.\)
Unexpectedly, all results are very natural and complete. Forcing plays an important role in the proofs.


03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
03C25 Model-theoretic forcing
Full Text: DOI


[1] Theory of recursive functions and effective computability (1967) · Zbl 0183.01401
[2] Degrees coded in jumps of orderings 51 pp 1034– (1986) · Zbl 0633.03038
[3] Aspects of recursive algebra pp 26– (1981)
[4] DOI: 10.1007/BF01669456 · Zbl 0407.03040
[5] DOI: 10.1016/0168-0072(86)90047-3
[6] Model theory for infinitary logic (1971)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.