Charakterisierung $ (aa)^*$ in Erster Ordnung Logik

Question

In meiner beschreibenden Komplexitätsklasse wurden wir gebeten, eine Formel zu finden, die die Sprache $ (aa)^*$ (über dem Alphabet $ {a } $) mit einer Formel erster Ordnung über die Sprache $ {<<<a } $) kennzeichnet. , P_a } $.

Dies war die erste Klasse, also werde ich mich erinnern, was wir gelernt haben, um sicher zu sein, dass ich verstanden habe. Zu A $ l $ -Formula $ phi $ wir verknüpfen eine Sprache $ mathcal l ( phi) $, was die Klasse aller $ l $ -strukturen ist, in denen $ phi $ gültig ist.

In meinem Fall suchen wir dann nach einer $ {<, p_a } $-Formel, für die Wörter mit gleichmäßiger Länge Modelle sind. Ich denke, ich muss in $ phi $ sagen, dass $ <$ eine Gesamtbestellung ist, damit ich die Modelle als Wörter interpretieren kann und dass $ forall x, p_a (x) $ zu sagen, dass alle Punkte als als als bezeichneten Punkte bezeichnet werden 'a'. Aber wie muss man sagen, dass es eine gleiche Anzahl von Punkten im Modell geben muss? Die Definition einer geraden Anzahl von Punkten scheint rekursiv zu sein. Ich habe daher den Eindruck, dass eine Formel für $ (aa)^*$ in logik erster Ordnung von unendlicher Länge sein sollte.

Answer 1

Kurze Antwort. Es gibt keine solche Formel erster Ordnung, Sie benötigen eine monadische Formel zweiter Ordnung.

Einzelheiten. Dies kann direkt mit einem Ehrenfeucht-Fraïssé-Spielargument nachgewiesen werden, wenn Sie in der Logik bleiben möchten. Die eigentliche Antwort auf Ihre Frage ist jedoch die Konjunktion von drei Ergebnissen.

1] Hüchi (1960): Eine Sprache ist ein monadisches Ausdrucksfähiger zweiter Ordnung, wenn es regelmäßig ist.
2] McNaughton-Pappert (1971): Eine Sprache ist exprimierbar erster Ordnung, wenn sie sternfrei ist.
Gegenfreie Automaten. Forschungsmonograph 65. mit einem Anhang von William Henneman. MIT Press. p. 48. ISBN 0-262-13076-9.
3] Schützenberger (1965): Eine reguläre Sprache ist sternfrei, wenn es nur dann ist, wenn es ist syntaktisches Monoid ist aperiodisch. Auf endlichen Monoiden mit nur trivialen Untergruppen

3] gibt einen Algorithmus an, um zu entscheiden, ob eine bestimmte reguläre Sprache sternfrei ist (und daher exprimierbar erster Ordnung durch [2]). Jetzt ist das syntaktische Monoid von $ (aa)^*$ die zyklische Gruppe von Bestell -$ 2 $, was nicht aperiodisch ist. Um eine monadische Formel zweiter Bestellung zu erhalten, müssen Sie zunächst "Makros" erster Bestellung haben, um $ min $, $ max $ und $+1 $ auszudrücken, und dann wird die folgende Formel zweiter Bestellung den Job erledigen $$ exists x forall x ( min in X Wedge max notin x) kege (x in x leftrightarrow x+1 notin x) $$