Interprétation de la théorie monadique des réels dans la théorie monadique de l'ordre linéaire.

Aug 17 2020

Ci-dessous, un extrait de Gurevich, Shelah - Interpréter la logique du second ordre dans la théorie monadique de l'ordre . J'essaie de comprendre comment la théorie monadique de la ligne réelle est interprétable dans la théorie monadique de l'ordre (ils n'incluent aucune autre explication ou preuve, disant seulement que cela peut être fait facilement).

Voici quelques définitions qui pourraient être utiles. Si$(\alpha,<)$ est donc un ordre linéaire par `` la théorie monadique de $\alpha$'signifie la théorie du premier ordre de la structure $(\mathcal{P}(\alpha),\subseteq,<)$$<$ est l'ordre de $\alpha$donné sur des sous-ensembles singleton. La `` théorie monadique de l'ordre '' est l'intersection de toutes ces théories du premier ordre comme nous le permettons$\alpha$ pour varier sur tous les ordres linéaires.

Y a-t-il peut-être un ensemble récursif d'axiomes $T_{\mathbb{R}}$ tel que si l'on prend l'union de la théorie monadique de l'ordre avec $T_{\mathbb{R}}$ nous obtenons la théorie complète de la structure $(\mathcal{P}(\mathbb{R}),\subseteq,<)$? (À noter, tant la théorie monadique de l'ordre que la théorie monadique de$\mathbb{R}$ sont indécidables).

Je ne peux pas trouver cette interprétation «facile», mais j'ai le sentiment de manquer quelque chose d'évident.

Réponses

3 NoahSchweber Aug 17 2020 at 05:19

Je ne vois pas comment corriger ma stratégie d'origine - en particulier, bien que je n'ai pas de contre-exemple, je soupçonne que "est un ordre linéaire Dedekind-complet sans points d'extrémité ou points isolés, dont tous les sous-ordres ont la cofinalité et la coinitialité $\le \omega$"ne définit pas nécessairement$\mathbb{R}$ jusqu'à l'isomorphisme.

Cependant, nous pouvons toujours obtenir la réduction attendue (bien qu'à un coup d'œil, cela ne donne pas d' interprétation en soi - y réfléchissant toujours). Dites qu'un ordre linéaire$A$ est $\mathbb{R}$ish s'il est Dedekind-complete et n'a pas de points de terminaison ou de points isolés. La principale observation est la suivante:

(Lemme) Chaque$\mathbb{R}$l'ordre ish a un sous-ordre isomorphe à $\mathbb{R}$et chaque $\mathbb{R}$ish sous-ordre de $\mathbb{R}$ est isomorphe à $\mathbb{R}$.

Le point est alors que $\mathbb{R}$se trouve au bas d'une classe d'ordonnances définissables par MSO dans un sens définissable par MSO. Nous pouvons donc effectuer la traduction suivante:

(Définition) Pour une phrase MSO$\varphi$, laisser $\hat{\varphi}$ soit la phrase MSO "Chaque $\mathbb{R}$l'ordre ish a un $\mathbb{R}$sous-ordre satisfaisant $\varphi$. "

Par le lemme nous avons ça $\hat{\varphi}$ fait partie de la théorie MSO de l'ordre ssi $\mathbb{R}\models\varphi$:

  • Si $\mathbb{R}\not\models\varphi$ puis $\mathbb{R}\not\models\hat{\varphi}$, puisque toutes $\mathbb{R}$ish sous-ordres de $\mathbb{R}$ sont isomorphes à $\mathbb{R}$ par le lemme et donc ne satisfont pas non plus $\varphi$.

  • Inversement, si $\mathbb{R}\models\varphi$ puis chaque $\mathbb{R}$L'ordre linéaire ish a un $\mathbb{R}$sous-ordre satisfaisant $\varphi$ - à savoir, tout sous-ordre isomorphe à $\mathbb{R}$ lui-même, qui est garanti d'exister selon le lemme.

La carte $\varphi\mapsto\hat{\varphi}$ est clairement calculable, et nous obtenons donc une réduction de $Th_{MSO}(\mathbb{R})$ à la théorie monadique de l'ordre comme souhaité.