论文标题
Specker-blatter定理的扩展和限制
Extensions and Limits of the Specker-Blatter Theorem
论文作者
论文摘要
原始Specker-blatter定理（1983）是针对结构类别的类别$ \ MATHCAL {C} $制定的，该类别的一个或几个二进制关系可在Monadic二阶逻辑MSOL中定义。它指出，集合$ [n] $上的此类结构的数量是模块化的C-Finite（MC-Finite）。在先前的工作中，我们将其扩展到CMSOL中可定义的结构，MSOL通过模块化计数量词扩展。第一作者还表明，Specker-blater定理不适合一个第四纪关系（2003）。 如果词汇允许恒定的符号$ c $，则$ n $在$ c $的$ [n] $上进行了可能的解释。我们说，如果$ c $始终由[n] $中的同一元素$ j \解释，则常数$ c $是{\ em hard-nired}。在本文中，我们显示： 1。当允许硬接线常数时，Specker-blater定理也适用于CMSOL。在这种情况下，Specker和Blatter的证明方法不起作用。 2。斑点 - 布拉特定理尚未适用于$ \ Mathcal {C} $，其中一个可以在一阶逻辑中定义的三元关系。自1983年以来，这是开放的。 使用硬连线常数使我们能够显示出各种限制分区功能的计数功能的MC限制，这些功能到目前为止还不是MC-Finite。其中，我们有限制的钟数$ b_ {r，a} $，第二种$ s_ {r，a} $的限制性stirl数字或限制的lah-numbers $ l_ {r，a} $。这里$ r $是一个非负整数，$ a $是最终定期的非负整数集。
The original Specker-Blatter Theorem (1983) was formulated for classes of structures $\mathcal{C}$ of one or several binary relations definable in Monadic Second Order Logic MSOL. It states that the number of such structures on the set $[n]$ is modularly C-finite (MC-finite). In previous work we extended this to structures definable in CMSOL, MSOL extended with modular counting quantifiers. The first author also showed that the Specker-Blatter Theorem does not hold for one quaternary relation (2003). If the vocabulary allows a constant symbol $c$, there are $n$ possible interpretations on $[n]$ for $c$. We say that a constant $c$ is {\em hard-wired} if $c$ is always interpreted by the same element $j \in [n]$. In this paper we show: 1. The Specker-Blatter Theorem also holds for CMSOL when hard-wired constants are allowed. The proof method of Specker and Blatter does not work in this case. 2. The Specker-Blatter Theorem does not hold already for $\mathcal{C}$ with one ternary relation definable in First Order Logic FOL. This was left open since 1983. Using hard-wired constants allows us to show MC-finiteness of counting functions of various restricted partition functions which were not known to be MC-finite till now. Among them we have the restricted Bell numbers $B_{r,A}$, restricted Stirling numbers of the second kind $S_{r,A}$ or restricted Lah-numbers $L_{r,A}$. Here $r$ is an non-negative integer and $A$ is an ultimately periodic set of non-negative integers.
