Définissabilité des ordinaux dans diverses signatures
Récemment, j'ai étudié à quoi "ressemblent" les sous-ensembles définissables des ordinaux dénombrables du point de vue de la logique du premier ordre simple (pas de la théorie des ensembles) équipée de diverses manières "d'accéder" à la structure des ordinaux.
Par exemple, nous pouvons avoir une signature constituée uniquement d'un symbole relationnel à 2 arités $S$ que nous interprétons dans une structure $\mathcal{A}$ avec ensemble sous-jacent $\omega_1$ comme l'ensemble de $(\alpha,\beta)$ tel que $\beta$ est le successeur de $\alpha$. Nous pouvons ensuite poser des questions sur les sous-ensembles de$\mathcal{A}$ sont définissables par des phrases logiques du premier ordre avec cette signature, où un sous-ensemble $S\subset\mathcal{A}$ est considéré comme définissable s'il existe une phrase logique du premier ordre $\phi(x)$ pour lequel l'ensemble des affectations satisfaisantes de $x$ est $S$. Dans notre exemple, nous pouvons définir l'ensemble de tous les ordinaux successeurs dénombrables via la formule$\exists y:S(y,x)$.
Nous pouvons également poser des questions comme "quel est le plus petit ordinal $\alpha$ tel que $\alpha$ est indéfinissable dans le sens où $\{\alpha\}$ est indéfinissable "et ainsi de suite. Dans l'exemple ci-dessus, il est clair de voir qu'en fait aucun ordinal n'est définissable, donc le plus petit ordinal indéfinissable est zéro. Je suis particulièrement intéressé par la façon dont le plus petit ordinal indéfinissable grandit à mesure que nous avons des signatures de plus en plus fortes. Par exemple, j'ai pu me convaincre qu'avec la signature $\{<\}$ avec l'interprétation évidente dans $\omega_1$ en tant que «relation inférieure à», le plus petit ordinal indéfinissable est $\omega^\omega$ (bien que je n'ai pas encore écrit mon argument formellement).
Ma question est la suivante: est-ce que quelqu'un a étudié des questions comme celles-ci? Sait-on quel est le plus petit ordinal définissable pour diverses autres signatures, comme$\{ADD(x,y,z)\}$ ce qui est vrai sur tout $x,y,z$ de sorte que $x+y=z$, ou même d'autres signatures avec multiplication, exponentiation, fonctions veblen, ou plus? Y a-t-il des généralisations connues de ces idées? Toute aide ou documentation connexe serait appréciée.
Réponses
Je n'ai pas assez de réputation pour ajouter un commentaire. Le document suivant peut vous être utile. Il contient des résultats étendant les travaux de Tarski, Mostowski et Doner, ainsi que de très beaux aperçus historiques et des références.
Buchi, Siefkes - Les extensions complètes de la théorie monadique du second ordre des ordinaux dénombrables.
La faible logique monadique du second ordre apparaît déjà dans l'œuvre originale d'Ehrenfeucht. Même si vous êtes exclusivement intéressé par les résultats du premier ordre, la logique monadique (faible) du second ordre peut jouer un rôle.
Par exemple, la théorie du premier ordre de l'addition ordinale coïncide avec la théorie du premier ordre de l'addition ordinale à l'intérieur $\omega^{\omega^{\omega}}$ (par Ehrenfeuct), tandis que $(\omega^{\omega^{\omega}},+)$ est une réduction d'une puissance généralisée de $(\omega,+)$ avec 'exposant' étant la version monadique faible de second ordre de $(\omega^{\omega},<)$(le théorème de Feferman-Vaught est le bon outil pour comprendre cela). Pour plus de détails, il y a Thomas - Ehrenfeucht, Vaught et la décidabilité de la théorie monadique faible du successeur , les détails ici sont tous corrects mais je pense que les conclusions ont quelques problèmes.
Il y a aussi des travaux plus récents du côté des automates tels que Cachat - Tree Automata Make Ordinal Theory Easy. Je n'en sais rien du contenu, mais si vous voulez un aperçu complet de la région, c'est peut-être un point de départ.