Definibilità degli ordinali in varie firme
Recentemente, ho studiato come "appaiono" i sottoinsiemi definibili degli ordinali numerabili dalla prospettiva della semplice logica del primo ordine (non teoria degli insiemi) dotata di vari modi per "accedere" alla struttura degli ordinali.
Ad esempio, potremmo avere una firma composta solo da un simbolo relazionale di 2 arità $S$ che interpretiamo in una struttura $\mathcal{A}$ con set sottostante $\omega_1$ come l'insieme di $(\alpha,\beta)$ tale che $\beta$ è il successore di $\alpha$. Possiamo quindi porre domande su quali sottoinsiemi di$\mathcal{A}$ sono definibili da frasi logiche del primo ordine con questa firma, dove un sottoinsieme $S\subset\mathcal{A}$ è considerato definibile se esiste una frase logica del primo ordine $\phi(x)$ per cui l'insieme degli incarichi soddisfacenti di $x$ è $S$. Nel nostro esempio, possiamo definire l'insieme di tutti gli ordinali successori numerabili tramite la formula$\exists y:S(y,x)$.
Possiamo anche porre domande come "qual è il più piccolo ordinale $\alpha$ tale che $\alpha$ è indefinibile nel senso che $\{\alpha\}$ è indefinibile "e simili. Nell'esempio sopra, è chiaro che in realtà nessun ordinale è definibile, quindi il più piccolo ordinale indefinibile è zero. Sono particolarmente interessato al modo in cui il più piccolo indefinibile ordinale cresce man mano che abbiamo firme sempre più forti. Ad esempio, sono stato in grado di convincermi che con la firma $\{<\}$ con l'ovvia interpretazione in $\omega_1$ come "minore di relazione", il più piccolo ordinale indefinibile è $\omega^\omega$ (anche se non ho ancora formalmente scritto la mia argomentazione).
La mia domanda è: qualcuno ha studiato domande come queste? È noto quale sia il più piccolo ordinale definibile per varie altre firme, come$\{ADD(x,y,z)\}$ il che è vero per tutti $x,y,z$ così che $x+y=z$, o anche altre firme con moltiplicazione, esponenziazione, funzioni di veblen o altro? Esistono generalizzazioni note di queste idee? Qualsiasi aiuto o letteratura correlata sarebbe apprezzata.
Risposte
Non ho abbastanza reputazione per aggiungere un commento. Il seguente documento potrebbe esserti utile. Contiene risultati che estendono il lavoro di Tarski, Mostowski e Doner, oltre a una panoramica e riferimenti storici molto belli.
Buchi, Siefkes - The Complete Extensions of the Monadic Second Order Theory of Countable Ordinals.
La debole logica monadica del secondo ordine appare già nell'opera originale di Ehrenfeucht. Anche se sei interessato esclusivamente ai risultati del primo ordine, la logica monadica del secondo ordine (debole) può giocare un ruolo.
Ad esempio, la teoria dell'addizione ordinale del primo ordine coincide con la teoria dell'addizione ordinale del primo ordine all'interno $\omega^{\omega^{\omega}}$ (di Ehrenfeuct), mentre $(\omega^{\omega^{\omega}},+)$ è una riduzione di un potere generalizzato di $(\omega,+)$ con "esponente" la versione debole del secondo ordine monadico di $(\omega^{\omega},<)$(il teorema di Feferman-Vaught è lo strumento corretto per capirlo). Per maggiori dettagli c'è Thomas-Ehrenfeucht, Vaught e la decidibilità della debole teoria monadica del successore , i dettagli qui sono tutti corretti ma penso che le conclusioni abbiano alcuni problemi.
C'è anche un lavoro più recente sul lato degli automi come Cachat - Tree Automata Make Ordinal Theory Easy. Non so nulla del contenuto di questo ma se vuoi una panoramica completa della zona, questo è forse un punto di partenza.