Effective model theory vs. recursive model theory.

*(English)*Zbl 0722.03030The 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.

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.

Reviewer: A.S.Morozov (Novosibirsk)

##### MSC:

03C57 | Computable structure theory, computable model theory |

03D45 | Theory of numerations, effectively presented structures |

03C25 | Model-theoretic forcing |

##### Keywords:

recursive model theory; effectiveness in model theory; effective model theory; algorithmic complexity; complexity of models; recursive stability; effective stability; recursive categoricity; effective categoricity
Full Text:
DOI

##### References:

[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.