La caratterizzazione $ (aa) ^ * $ in logica del primo ordine

Question

Nella mia classe di complessità descrittiva, c'è stato chiesto di trovare una formula che caratterizza la lingua $ (aa) ^ * $ (oltre l'alfabeto $ \ {a \} $) con una prima formula ordine sopra la lingua $ \ {<, P_A \} $.

Questa è stata la prima classe, così sarò ricordare ciò che abbiamo imparato ad essere sicuro che ho capito. Per un $ L $ -Formula $ \ phi $ associamo una lingua $ \ L mathcal (\ phi) $, che è la classe di tutti -Strutture $ L $ in cui $ \ phi $ è valida.

Nel mio caso, abbiamo poi cercando un $ \ {<, P_A \} $ - formula per la quale le parole di lunghezza sono anche modelli. Mi sa che devo dire in $ \ phi $ che $ <$ è un ordine totale, in modo che possa interpretare i modelli come parole, e che $ \ forall x, P_A (x) $ a dire che tutti i punti sono etichettati come 'un'. Ma come dire che ci deve essere un numero pari di punti del modello? La definizione di avere un numero pari di punti appare ricorsivo, così ho l'impressione che una formula per $ (aa) ^ * $ dovrebbero essere di lunghezza infinita in logica del primo ordine ..

Answer 1

Risposta breve . Non esiste una formula del primo ordine, è necessario un secondo formula ordine monadico.

Dettagli . Questo può essere dimostrato direttamente utilizzando un argomento giochi Ehrenfeucht-Fraisse se si vuole rimanere dentro la logica, ma la vera risposta alla tua domanda è la congiunzione di tre risultati.

[1] Büchi (1960):. Il linguaggio A è monadica secondo esprimibile ordine se e solo se è regolare
[2] McNaughton-Pappert (1971): il linguaggio A è di primo ordine esprimibile se e solo se è privo di stelle
. Automi Counter-libera. La ricerca Monografia 65. Con un'appendice di William Henneman. MIT Press. p. 48. ISBN 0-262-13076-9.
[3] Schützenberger (1965): un linguaggio regolare è se e senza stelle, solo se la sua sintattica monoid IS aperiodico. Su monoidi finiti aventi soli sottogruppi banali

[3] dà un algoritmo per decidere se un determinato linguaggio regolare è privo di stelle (e quindi, del primo ordine esprimibili, da [2]). Ora, il monoide sintattica di $ (aa) * ^ $ è il gruppo ciclico di ordine $ 2 $, il che non è aperiodica. Per ottenere una seconda formula ordine monadico, è necessario prima di avere prim'ordine "macro" per esprimere $ \ min $, $ \ $ max e $ + 1 $ e quindi la seguente formula secondo ordine farà il lavoro $$ \ Esiste X \ \ forall x \ (\ min \ in X \ wedge \ max \ notin X) \ cuneo (x \ in X \ leftrightarrow x + 1 \ notin X) $$