论文标题
自然井订单的单一二阶限制法律
Monadic second order limit laws for natural well orderings
论文作者
论文摘要
通过结合Büchi的经典结果，一些基本的Tauberian定理以及逻辑和组合学中的一些基本工具，我们表明，每个序数$α$与$ \ varepsilon_0 \geQα\geQα\ geqα\ geqα\ geqω^ω$切萨罗极限法。在这两种情况下，我们都像往常一样标识$ \ {β：β<α\} $的类别。 我们在附加设置中工作，在该设置中，Norm函数$ n $分配给每个列出的$α$以其cantor normal形式的符号$ω$的出现数量。该数字与树上的边缘数量相同，该数量与$α$相关。 对于给定的$α$，带有$ω\leqα\ leq \ varepsilon_0 $从线性订单的语言中的单一二阶公式$φ$的渐近概率为$ \ lim_ {n \ to \ in \ to \ infty}如果存在此限制，则φ\}}} {\＃\ {β<α：nβ= n \}} $。如果仅在塞萨罗（Cesaro）意义上存在此限制，我们会谈论$φ$的cesaro的不可分割概率。 此外，我们证明了低于$γ_0$（适当扩展规范函数）低于$γ_0$的序数段的二阶限制定律，我们指出了本文的结果如何扩展到较大的序数段，甚至可以扩展到某些具有无数序符的符号的障碍序列符号系统。我们还简要指出了如何证明相对于Matula编码为设置定义的相应乘法结果。 有关未超过$ \ varepsilon_0 $的列表的结果部分是在与Alan R. Woods的联合合作中获得的。
By combining classical results of Büchi, some elementary Tauberian theorems and some basic tools from logic and combinatorics we show that every ordinal $α$ with $\varepsilon_0\geq α\geq ω^ω$ satisfies a natural monadic second order limit law and that every ordinal $α$ with $ω^ω>α\geq ω$ satisfies a natural monadic second order Cesaro limit law. In both cases we identify as usual $α$ with the class of substructures $\{β:β<α\}$. We work in an additive setting where the norm function $N$ assigns to every ordinal $α$ the number of occurrrences of the symbol $ω$ in its Cantor normal form. This number is the same as the number of edges in the tree which is canonically associated with $α$. For a given $α$ with $ω\leq α\leq \varepsilon_0$ the asymptotic probability of a monadic second order formula $φ$ from the language of linear orders is $\lim_{n\to\infty} \frac{\#\{β<α: Nβ=n\wedge β\models Φ\}}{\#\{β<α: Nβ=n\}}$ if this limit exists. If this limit exists only in the Cesaro sense we speak of the Cesaro asympotic probability of $φ$. Moreover we prove monadic second order limit laws for the ordinal segments below below $Γ_0$ (where the norm function is extended appropriately) and we indicate how this paper's results can be extended to larger ordinal segments and even to certain impredicative ordinal notation systems having notations for uncountable ordinals. We also briefly indicate how to prove the corresponding multiplicative results for which the setting is defined relative to the Matula coding. The results of this paper concerning ordinals not exceeding $\varepsilon_0$ have been obtained partly in joint work with Alan R. Woods.
