表征$（aa）^*$在一阶逻辑中

Question

在我的描述性复杂性类中，我们被要求找到一个表征语言$（aa）^*$的公式（在Alphabet $ {a } $上，带有第一阶公式在语言上$ {<< ，p_a } $。

这是第一堂课，所以我会回想起我们学会的确保我理解的东西。对于$ l $ -formula $ phi $，我们将语言$ mathcal l（ phi）$关联，这是所有$ l $ structures的类别，其中$ phi $有效。

就我而言，然后我们正在寻找$ {<，p_a } $ - 公式，该公式均匀的单词是模型。我想我必须在$ phi $中说$ <$是总订单，这样我就可以将这些模型解释为单词，而$ forall x，p_a（x）$都可以说所有点都标记为'一个'。但是如何说模型中必须有偶数点呢？具有均匀数量的定义似乎是递归的，因此我给人的印象是，$（aa）^*$的公式在一阶逻辑中应为无限长度。

Answer 1

简短的答案. 。没有这样的一阶公式，您需要一个单一的二阶公式。

细节. 。如果您想留在逻辑中，可以使用Ehrenfeucht-Fraïssé游戏参数直接证明这一点，但是您问题的真正答案是三个结果的结合。

1]Büchi（1960）：语言是单一的二阶阶，如果是规则的。
2] McNaughton-Pappert（1971）：语言是一阶表达，如果是无星。
无柜台自动机。研究专着65.威廉·汉尼曼（William Henneman）的附录。麻省理工学院出版社。 p。 48. ISBN 0-262-13076-9。
3]Schützenberger（1965）：只有且仅当它 句法单体 是至上的。 在有限的单体上，只有琐碎的亚组

3]给出了一种算法来决定给定的常规语言是否不含星（因此，由[2]）提供了一阶表达）。现在，$（aa）^*$的句法单体是订单$ 2 $的循环群，这不是至关重要的。要获取Monadic二阶公式，您需要首先要有一阶“宏”来表达$ min $，$ max $和$+1 $，然后以下第二订单公式将完成工作$ forall x （ min in x wedge max notin x） wedge（x in x leftrightarrow x+1 notin x）$$