Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
复制标题
（广义）后继二（一）阶理论扩展的可判定性和不可判定性
DOI：
10.2307/2269808
复制
发表时间：
1966
影响因子：
0.6
通讯作者：
M. Rabin
中科院分区：
文献类型：
--
作者：
C. C. Elgot;M. Rabin
我们研究了某些一阶和二阶理论，它们在语义上被定义为在某些给定结构中所有句子的集合。设A是非空集，λ是序数，Pα是A上的n(α)元关系或函数4，我们把一种语言L联系起来，它可能是一阶或更高阶的演算。L对每个α<；α都有一个n(λ)位谓词或函数常数P。我们将学习三种类型的语言：(1)一阶等式演算；(2)包含A的子集上的一元谓词(集)变量的二阶一元演算；(3)包含A的有限子集上的一元谓词变量的受限(弱)二阶演算。
We study certain first and second order theories which are semantically defined as the sets of all sentences true in certain given structures. Let be a structure where A is a non-empty set, λ is an ordinal, and Pα is an n(α)-ary relation or function4 on A. With we associate a language L appropriate for which may be a first or higher order calculus. L has an n(α)-place predicate or function constant P for each α < λ. We shall study three types of languages: (1) first-order calculi with equality; (2) second-order monadic calculi which contain monadic predicate (set) variables ranging over subsets of A; (3) restricted (weak) second-order calculi which contain monadic predicate variables ranging over finite subsets of A.