Характеристика $ (aa)^*$ в логике первого порядка

Question

В моем классе описательной сложности нас попросили найти формулу, которая характеризует язык $ (aa)^*$ (над алфавитом $ {a } $) с формулой первого порядка над языком $ {<<< , P_a } $.

Это был первый класс, поэтому я вспомню, что мы научились, чтобы быть уверенным, что я понял. Для $ l $ -formula $ phi $ мы связываем язык $ mathcal l ( phi) $, который является классом всех $ l $-структуры, в которых $ phi $ действителен.

В моем случае мы затем ищем $ {<, p_a } $-формула, для которой слова даже длины являются моделями. Я думаю, я должен сказать в $ phi $, что $ <$ - это общий заказ, чтобы я мог интерпретировать модели как слова, и что $ forall x, p_a (x) $ сказать, что все точки помечены как 'A'. Но как сказать, что в модели должно быть равномерное количество очков? Определение наличия равномерного количества очков кажется рекурсивным, поэтому у меня сложилось впечатление, что формула для $ (aa)^*$ должна иметь бесконечную длину в логике первого порядка.

Answer 1

Короткий ответ. Анкет Там нет такой формулы первого порядка, вам нужна монадическая формула второго порядка.

Подробности. Анкет Это может быть доказано непосредственно с использованием аргумента Ehrenfeucht-Fraïsse Games, если вы хотите остаться в логике, но реальный ответ на ваш вопрос-это соединение трех результатов.

1] Бючи (1960): Язык - это монадический второй порядок, если он регулярно.
2] McNaughton-Pappert (1971): Язык является выражением первого порядка, если он не является звездой.
Бесплатные автоматы. Исследовательская монография 65. С приложением Уильяма Хеннеммана. MIT Press. п. 48. ISBN 0-262-13076-9.
3] Schützenberger (1965): обычный язык не является звездой, если и только тогда, когда его синтаксический моноид является апериодическим. На конечных моноидах, имеющих только тривиальные подгруппы

3] дает алгоритм, чтобы решить, не является ли данный регулярный язык без звезд (и, следовательно, выражается первым порядком [2]). Теперь синтаксический моноид $ (aa)^*$ является циклической группой порядка $ 2 $, которая не является апериодической. Чтобы получить формулу второго порядка в Монадике, вам нужно сначала иметь первый заказ «макросы», чтобы выразить $ min $, $ max $ и $+1 $, а затем следующая формула второго порядка выполнит задание $$ fastist x forall x ( min in x wedge max notin x) wedge (x in x leftrightarrow x+1 notin x) $$