论文标题
可数序的一阶分离
First-order separation over countable ordinals
论文作者
论文摘要
我们表明，在可数序单词上分开两个单一的二阶公式的一阶公式的存在是可以决定的。这扩展了Henckell和Almeida在有限的单词上的工作，以及$ω$ - 词的位置和Zeitoun的工作。为此，我们开发了具有上膜合并的单体（分别$ω$ -Semigroup，ordinal monoid）的代数概念，它的扩展（分别是$ω$ -semigroup，seps。Monoid）明确的，其中包括一种新操作，其中包括捕获的新操作，该操作捕获了由第一顺序造成的精确效果。我们还展示了FO-Pointlike集的计算性，以及在可数序单词上的一阶逻辑的覆盖问题的可决定性。
We show that the existence of a first-order formula separating two monadic second order formulas over countable ordinal words is decidable. This extends the work of Henckell and Almeida on finite words, and of Place and Zeitoun on $ω$-words. For this, we develop the algebraic concept of monoid (resp. $ω$-semigroup, resp. ordinal monoid) with aperiodic merge, an extension of monoids (resp. $ω$-semigroup, resp. ordinal monoid) that explicitly includes a new operation capturing the loss of precision induced by first-order indistinguishability. We also show the computability of FO-pointlike sets, and the decidability of the covering problem for first-order logic on countable ordinal words.
