Definibilidade de ordinais em várias assinaturas
Recentemente, estive estudando como os subconjuntos definíveis dos ordinais contáveis "se parecem" da perspectiva da lógica básica de primeira ordem (não a teoria dos conjuntos) equipada com várias maneiras de "acessar" a estrutura dos ordinais.
Por exemplo, podemos ter uma assinatura que consiste apenas em um símbolo relacional 2-aridade $S$ que interpretamos em uma estrutura $\mathcal{A}$ com conjunto subjacente $\omega_1$ como o conjunto de $(\alpha,\beta)$ de tal modo que $\beta$ é o sucessor de $\alpha$. Podemos então fazer perguntas sobre quais subconjuntos de$\mathcal{A}$ são definíveis por sentenças lógicas de primeira ordem com esta assinatura, onde um subconjunto $S\subset\mathcal{A}$ é considerado definível se houver uma sentença lógica de primeira ordem $\phi(x)$ para o qual o conjunto de atribuições satisfatórias de $x$ é $S$. Em nosso exemplo, podemos definir o conjunto de todos os ordinais sucessores contáveis por meio da fórmula$\exists y:S(y,x)$.
Também podemos fazer perguntas como "qual é o menor ordinal $\alpha$ de tal modo que $\alpha$ é indefinível no sentido de que $\{\alpha\}$ é indefinível "e tal. No exemplo acima, é claro ver que, na verdade, nenhum ordinal é definível, portanto, o menor ordinal indefinível é zero. Estou particularmente interessado em como o menor ordinal indefinível cresce, pois temos assinaturas cada vez mais fortes. Por exemplo, fui capaz de me convencer de que com a assinatura $\{<\}$ com a interpretação óbvia em $\omega_1$ como o "menos que relação", o menor ordinal indefinível é $\omega^\omega$ (embora eu não tenha escrito meu argumento formalmente ainda).
Minha pergunta é: alguém estudou questões como essas? É conhecido o que é o menor ordinal definível para várias outras assinaturas, como$\{ADD(x,y,z)\}$ o que é verdade em todos $x,y,z$ de modo a $x+y=z$, ou mesmo outras assinaturas com multiplicação, exponenciação, funções veblen ou mais? Existem generalizações conhecidas dessas idéias? Qualquer ajuda ou literatura relacionada seria apreciada.
Respostas
Não tenho reputação suficiente para adicionar um comentário. O seguinte artigo pode ser útil para você. Ele contém resultados que estendem o trabalho de Tarski, Mostowski e Doner, bem como uma visão geral histórica muito boa e referências.
Buchi, Siefkes - As Extensões Completas da Teoria Monádica da Segunda Ordem dos Ordinais Contáveis.
Lógica monádica fraca de segunda ordem já aparece na obra original de Ehrenfeucht. Mesmo que você esteja exclusivamente interessado nos resultados de primeira ordem, a lógica monádica (fraca) de segunda ordem pode desempenhar um papel.
Por exemplo, a teoria de primeira ordem da adição ordinal coincide com a teoria de primeira ordem da adição ordinal dentro $\omega^{\omega^{\omega}}$ (por Ehrenfeuct), enquanto $(\omega^{\omega^{\omega}},+)$ é uma redução de um poder generalizado de $(\omega,+)$ com 'expoente' sendo a versão monádica fraca de segunda ordem de $(\omega^{\omega},<)$(o teorema de Feferman-Vaught é a ferramenta correta para entender isso). Para mais detalhes, há Thomas - Ehrenfeucht, Vaught, e a decidibilidade da teoria monádica fraca do sucessor , os detalhes aqui estão todos corretos, mas acho que as conclusões têm alguns problemas.
Há também trabalhos mais recentes no lado dos autômatos, como Cachat - Tree Automata Make Ordinal Theory Easy. Não sei nada sobre o conteúdo disso, mas se você quiser uma visão geral abrangente da área, este é talvez um ponto de partida.