Effective model theory vs. recursive model theory
Effective model theory vs. recursive model theory
复制标题
有效模型理论与递归模型理论
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
John Chisholm
中科院分区：
文献类型：
--
作者：
John Chisholm
递归模型论是研究模型论中构造和定理的有效性的理论。这通常涉及到获得各种经典模型论概念的"有效"版本。传统的方法是将注意力限制在递归模型以及它们之间的递归同构等上。因此，例如，以下定义出现在文献中（在[3]和[1]中）。定义.给定一个递归模型A和一个n <$ω，一个子集R <$An称为固有r. e。假设对每个递归模型B ∈ A，R在B中的同构像是一个r. e. Bn的子集。很明显，如果R可由一个（递归的，无穷的）10公式（具有来自A的10个参数）定义，则R本质上是r.e.。反过来说似乎也是很自然的。事实上，如果（A，R）在Ash和Nerode的定理（见[3]）中精确的意义上是充分"正则的"，则相反的情况也成立。然而，如果我们放弃（相当强的）正则性条件，则存在固有r.e.的"病态"例子。不能用公式定义的关系（见[7]）。在本文中，我们提出了一个相当不同的方法来研究模型理论的有效性，我们称之为“有效模型理论”的方法。其基本思想是允许任意的非递归模型，但要求所有的概念都相对于所涉及的模型的复杂性。(Much同样的概念在[2]中以"相对递归模型理论"的名义使用。因此，例如，我们有下面的有效模型理论版本的性质是内在的r.e.
Recursive model theory is supposed to be the study of the effectiveness of constructions and theorems in model theory. This often involves getting “effective” versions of various classical model-theoretic notions. The traditional way of doing this is to restrict attention to recursive models, and recursive isomorphisms between them, etc. Thus for example the following definition appears in the literature (in [3] and [1]). Definition. Given a recursive model A and an n Є ω, a subset R ⊆ An is called intrinsically r.e. provided that for every recursive model B ≈ A, the isomorphic image in B of R is an r.e. subset of Bn. It is clear that if R is definable by a (recursive, infinitary) Σ10 formula (with finitely many parameters from A), then R is intrinsically r.e. It seems natural for the converse to be true. Indeed, provided that (A, R) is sufficiently “regular” in a sense made precise in a theorem of Ash and Nerode (see [3]), the converse is true. However, if we drop the (rather strong) regularity conditions, there exist “pathological” examples of intrinsically r.e. relations which are not definable by a Σ10 formula (see [7]). In this paper, we suggest a rather different approach to studying the effectiveness of model theory, an approach we have dubbed “effective model theory”. The basic idea is to allow arbitrary nonrecursive models, but to require all notions to be relativized to the complexity of the models involved. (Much the same notion has been used in [2] under the name “relatively recursive model theory”.) Thus for example we have the following effective model theory version of the property of being intrinsically r.e.