Definibilidad de ordinales en varias firmas
Recientemente, he estado estudiando cómo "se ven" los subconjuntos definibles de los ordinales contables desde la perspectiva de la lógica básica de primer orden (no la teoría de conjuntos) equipada con varias formas de "acceder" a la estructura de los ordinales.
Por ejemplo, podemos tener una firma que consiste solo en un símbolo relacional de 2 aridades $S$ que interpretamos en una estructura $\mathcal{A}$ con conjunto subyacente $\omega_1$ como el conjunto de $(\alpha,\beta)$ tal que $\beta$ es el sucesor de $\alpha$. Luego podemos hacer preguntas sobre qué subconjuntos de$\mathcal{A}$ son definibles por oraciones lógicas de primer orden con esta firma, donde un subconjunto $S\subset\mathcal{A}$ se considera definible si hay una oración lógica de primer orden $\phi(x)$ para el cual el conjunto de asignaciones satisfactorias de $x$ es $S$. En nuestro ejemplo, podemos definir el conjunto de todos los ordinales sucesores contables mediante la fórmula$\exists y:S(y,x)$.
También podemos hacer preguntas como "¿cuál es el ordinal más pequeño $\alpha$ tal que $\alpha$ es indefinible en el sentido de que $\{\alpha\}$ es indefinible "y tal. En el ejemplo anterior, está claro ver que, de hecho, ningún ordinal es definible, por lo que el ordinal indefinible más pequeño es cero. Estoy particularmente interesado en cómo crece el ordinal indefinible más pequeño a medida que tenemos firmas cada vez más fuertes. Por ejemplo, me he podido convencer de que con la firma $\{<\}$ con la interpretación obvia en $\omega_1$ como la "relación menor que", el ordinal indefinible más pequeño es $\omega^\omega$ (aunque todavía no he escrito formalmente mi argumento).
Mi pregunta es: ¿alguien ha estudiado preguntas como estas? ¿Se sabe cuál es el ordinal definible más pequeño para varias otras firmas, como$\{ADD(x,y,z)\}$ que es cierto en todos $x,y,z$ así que eso $x+y=z$, o incluso otras firmas con multiplicación, exponenciación, funciones veblen o más? ¿Existen generalizaciones conocidas de estas ideas? Se agradecería cualquier ayuda o literatura relacionada.
Respuestas
No tengo suficiente reputación para agregar un comentario. El siguiente documento puede resultarle útil. Contiene resultados que amplían el trabajo de Tarski, Mostowski y Doner, así como una descripción histórica y referencias muy interesantes.
Buchi, Siefkes: las extensiones completas de la teoría monádica de segundo orden de los ordinales contables.
La débil lógica monádica de segundo orden aparece ya en la obra original de Ehrenfeucht. Incluso si está exclusivamente interesado en resultados de primer orden, la lógica monádica (débil) de segundo orden puede desempeñar un papel.
Por ejemplo, la teoría de la suma ordinal de primer orden coincide con la teoría de la suma ordinal de primer orden dentro $\omega^{\omega^{\omega}}$ (por Ehrenfeuct), mientras $(\omega^{\omega^{\omega}},+)$ es una reducción de un poder generalizado de $(\omega,+)$ siendo 'exponente' la versión monádica débil de segundo orden de $(\omega^{\omega},<)$(el teorema de Feferman-Vaught es la herramienta correcta para entender esto). Para obtener más detalles, están Thomas - Ehrenfeucht, Vaught y la decidibilidad de la teoría monádica débil del sucesor , los detalles aquí son todos correctos, pero creo que las conclusiones tienen algunos problemas.
También hay trabajos más recientes en el lado de los autómatas como Cachat - Tree Automata Make Ordinal Theory Easy. No sé nada sobre el contenido de esto, pero si desea una descripción general completa del área, este es quizás un punto de partida.