论文标题
在FO和MSO中简洁地定义长话
Defining long words succinctly in FO and MSO
论文作者
论文摘要
我们考虑通过大小为n的公式在FO和MSO中定义的最长单词的长度。对于这两种逻辑，我们都将其作为该数字的上限，在n中的高度线性塔。我们通过计算固定量词等级的类型来证明这一点。作为FO和MSO的下限，我们以n的理性能力顺序获得了高度塔。我们通过提供具体公式来定义集合累积层次结构级别的单词表示形式来显示这些下限。此外，我们考虑了这些逻辑的Löwenheim-Skolem和HANF数字，并获得了这些逻辑的相似界限。
We consider the length of the longest word definable in FO and MSO via a formula of size n. For both logics we obtain as an upper bound for this number an exponential tower of height linear in n. We prove this by counting types with respect to a fixed quantifier rank. As lower bounds we obtain for both FO and MSO an exponential tower of height in the order of a rational power of n. We show these lower bounds by giving concrete formulas defining word representations of levels of the cumulative hierarchy of sets. In addition, we consider the Löwenheim-Skolem and Hanf numbers of these logics on words and obtain similar bounds for these as well.
