Caracterización de $ (aa)^*$ en la lógica de primer orden

Question

En mi clase de complejidad descriptiva, se nos ha pedido que encontremos una fórmula que caracterice el lenguaje $ (aa)^*$ (sobre el alfabeto $ {a } $) con una fórmula de primer orden sobre el lenguaje $ {<< , P_a } $.

Esta fue la primera clase, así que recordaré lo que hemos aprendido para asegurarme de que entendí. A $ L $ -Formula $ phi $ asociamos un idioma $ mathcal l ( phi) $, que es la clase de todas las estructuras $ l $ en las que $ phi $ es válido.

En mi caso, entonces estamos buscando una fórmula $ {<, p_a } $-para la cual las palabras de longitud uniforme son modelos. Supongo que tengo que decir en $ phi $ que $ <$ es un orden total, para que pueda interpretar los modelos como palabras, y que $ forall x, p_a (x) $ para decir que todos los puntos están etiquetados como 'a'. Pero, ¿cómo decir que tiene que haber un número par de puntos en el modelo? La definición de tener un número par de puntos parece recursivo, por lo que tengo la impresión de que una fórmula para $ (aa)^*$ debería ser de longitud infinita en la lógica de primer orden.

Answer 1

Respuesta corta. No existe tal fórmula de primer orden, necesita una fórmula monádica de segundo orden.

Detalles. Esto se puede probar directamente utilizando un argumento de los juegos Ehrenfeucht-Fraïssé si desea permanecer dentro de la lógica, pero la respuesta real a su pregunta es la conjunción de tres resultados.

1] Büchi (1960): un idioma es monádico de segundo orden expresable si es regular.
2] McNaughton-Pappert (1971): un idioma es expresable de primer orden IFF sin estrellas.
Autómatas sin contador. Monografía de investigación 65. Con un apéndice de William Henneman. MIT Press. pags. 48. ISBN 0-262-13076-9.
3] Schützenberger (1965): un idioma regular es libre de estrellas si y solo si es monoide sintáctico es aperiódico. En monoides finitos que tienen solo subgrupos triviales

3] da un algoritmo para decidir si un lenguaje regular dado es libre de estrellas (y por lo tanto, expresible de primer orden, por [2]). Ahora, el monoide sintáctico de $ (aa)^*$ es el grupo cíclico de orden $ 2 $, que no es aperiódico. Para obtener una fórmula monádica de segundo orden, primero debe tener "macros" de primer orden para expresar $ min $, $ max $ y $+1 $ y luego la siguiente fórmula de segundo orden hará el trabajo $$ existe x forall x ( min in x wedge max nonin x) wedge (x in x leftrightarrow x+1 noin x) $$