Interpretando a teoria monádica dos reais na teoria monádica da ordem linear.

Aug 17 2020

Abaixo está um extrato de Gurevich, Shelah - Interpretando a lógica de segunda ordem na teoria monádica da ordem . Estou tentando entender como a teoria monádica da linha real pode ser interpretada na teoria monádica da ordem (eles não incluem nenhuma explicação ou prova adicional, apenas dizendo que isso pode ser feito facilmente).

Aqui estão algumas definições que podem ser úteis. E se$(\alpha,<)$ é uma ordem linear então pela 'teoria monádica de $\alpha$'significa a teoria de primeira ordem da estrutura $(\mathcal{P}(\alpha),\subseteq,<)$ Onde $<$ é a ordenação de $\alpha$fornecido em subconjuntos singleton. A 'teoria monádica da ordem' é a interseção de todas essas teorias de primeira ordem, conforme permitimos$\alpha$ para variar em todas as ordens lineares.

Existe talvez algum conjunto recursivo de axiomas $T_{\mathbb{R}}$ de modo que se tomarmos a união da teoria monádica da ordem com $T_{\mathbb{R}}$ nós temos a teoria completa da estrutura $(\mathcal{P}(\mathbb{R}),\subseteq,<)$? (Vale a pena notar, tanto a teoria monádica da ordem quanto a teoria monádica de$\mathbb{R}$ são indecidíveis).

Não consigo encontrar essa interpretação 'fácil', mas sinto que pode estar faltando algo óbvio.

Respostas

3 NoahSchweber Aug 17 2020 at 05:19

Não vejo como corrigir minha estratégia original - em particular, embora eu não tenha um contra-exemplo, suspeito que "é uma ordem linear completa de Dedekind sem pontos finais ou pontos isolados, todas cujas subordens têm cofinalidade e co-inicialidade $\le \omega$" não necessariamente fixa$\mathbb{R}$ até isomorfismo.

No entanto, ainda podemos obter a redução esperada (embora à primeira vista isso não produza uma interpretação per se - ainda pensando nisso). Digamos que uma ordem linear$A$ é $\mathbb{R}$ish se for Dedekind completo e não tiver endpoints ou pontos isolados. A observação principal é a seguinte:

(Lemma) Cada$\mathbb{R}$ordem ish tem uma subordem isomórfica a $\mathbb{R}$, e todo $\mathbb{R}$ish subordem de $\mathbb{R}$ é isomorfo a $\mathbb{R}$.

O ponto então é que $\mathbb{R}$fica na parte inferior de uma classe de pedidos definível por MSO em um sentido definível por MSO. Portanto, podemos realizar a seguinte tradução:

(Definição) Para uma frase MSO$\varphi$, deixei $\hat{\varphi}$ seja a frase MSO "Todos $\mathbb{R}$Essa ordem tem um $\mathbb{R}$ish subordem satisfatória $\varphi$. "

Pelo lema, temos isso $\hat{\varphi}$ faz parte da teoria MSO da ordem iff $\mathbb{R}\models\varphi$:

  • E se $\mathbb{R}\not\models\varphi$ então $\mathbb{R}\not\models\hat{\varphi}$, Já que todos $\mathbb{R}$subordinados ish de $\mathbb{R}$ são isomórficos a $\mathbb{R}$ pelo lema e, portanto, também não satisfaz $\varphi$.

  • Por outro lado, se $\mathbb{R}\models\varphi$ então todo $\mathbb{R}$Essa ordem linear tem um $\mathbb{R}$ish subordem satisfatória $\varphi$ - ou seja, qualquer subordem isomórfica a $\mathbb{R}$ em si, que é garantido que existe pelo lema

O mapa $\varphi\mapsto\hat{\varphi}$ é claramente computável, e assim obtemos uma redução de $Th_{MSO}(\mathbb{R})$ à teoria monádica da ordem, conforme desejado.