Fixed-point extensions of first-order logic
Fixed-point extensions of first-order logic
复制标题
一阶逻辑的定点扩展
DOI：
10.1109/sfcs.1985.27
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
S. Shelah
中科院分区：
文献类型：
--
作者：
Y. Gurevich;S. Shelah
我们分别用正归纳、单调归纳和所谓的非单调（在我们的术语中称为膨胀）归纳证明了一阶逻辑的三种扩展在有限结构下都具有相同的表达能力。作为一个副产品，可以推导出相应的定点层次的崩溃。
We prove that the three extensions of first-order logic by means of positive inductions, monotone inductions, and so-called non-monotone (in our terminology, inflationary) inductions respectively, all have the same expressive power in the case of finite structures. As a by-product, the collapse of the corresponding fixed-point hierarchies can be deduced.