Shrinking games and local formulas
Shrinking games and local formulas
复制标题
缩小游戏和本地公式
DOI：
10.1016/j.apal.2004.01.004
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
W. Lotfallah
中科院分区：
文献类型：
--
作者：
H. Keisler;W. Lotfallah
盖夫曼范式定理证明了量词秩为n的每个一阶句等价于“散乱局部句”的布尔组合，其中局部邻域的半径至多为7n−1.这一界被Lifsches和−改进为3×4nı̈1.我们利用具有“收缩水平”的Ehrenfeucht-Fra-Fra Sesé型对策得到了一系列依赖于收缩速度的Gaifman型范式定理.这个谱包含了Lifsches和Shelah的结果，具有更容易理解的证明，并且半径上的界改进到4N−1。我们还得到了Schwentik和Barthelmann的一个规范型定理的界。
Gaifman's normal form theorem showed that every first-order sentence of quantifier rank n is equivalent to a Boolean combination of “scattered local sentences”, where the local neighborhoods have radius at most 7n−1. This bound was improved by Lifsches and Shelah to 3×4n−1. We use Ehrenfeucht–Fraı̈ssé type games with a “shrinking horizon” to get a spectrum of normal form theorems of the Gaifman type, depending on the rate of shrinking. This spectrum includes the result of Lifsches and Shelah, with a more easily understood proof and with the bound on the radius improved to 4n−1. We also obtain bounds for a normal form theorem of Schwentick and Barthelmann.