Equivalencia de la teorías $\operatorname{Th}(\Bbb{R}, 0,1,+, \le)$ y $\operatorname{Th}(\Bbb{Q}, 0,1,+, \le) $

Question

Así que yo estaba trabajando en mostrar que

$$\operatorname{Th}(\Bbb{R}, 0,1,+, \le) = \operatorname{Th}(\Bbb{Q}, 0,1,+, \le) $$

Mi idea inicial para trabajar en este problema fue sistemáticamente a comenzar mostrando $$\operatorname{Th}(\Bbb{R}, 0,1,+) = \operatorname{Th}(\Bbb{Q}, 0,1,+) $$ y $$\operatorname{Th}(\Bbb{R}, 0,1,\le) = \operatorname{Th}(\Bbb{Q}, 0,1,\le).$$

Espero que para entonces tendría suficiente la intuición de que el problema a resolver el caso más grande. Pero se me ocurrió que no entiendo lo suficiente de estos casos. A partir de la primera. He notado que ya no existen relaciones reales aquí, y sólo los operadores, por lo tanto no hay manera de establecer una ecuación que sólo tiene una solución en uno pero no el otro. O, más en general, es imposible hacer afirmaciones que tienen algo de cierto o falso valor. Aparte de las declaraciones que implican la existencia. (Si usamos foralls, dada la no existencia de otra fórmula, que no se crea ninguna restricción)

Para la próxima, es claro que estos son equivalentes ya que no pueden utilizar operadores de modo que sólo las expresiones que implican la comparación de la $1$ $0$ (presente en ambos) puede ser fabricado y puesto que no podemos acceder a la estructura subyacente en cualquiera de colección de expresiones que no hay forma de diferenciar nuestro estructuras de aquí.

Por lo tanto, dado que en ambos casos son "obvias" cuando se mezclan y ahora considere el pleno:

$$\operatorname{Th}(\Bbb{R}, 0,1,+, \le) = \operatorname{Th}(\Bbb{Q}, 0,1,+, \le) $$

Se puede observar que a $+$ es cerrado en $\Bbb{Q}$ y que los racionales son densos sobre los reales. Pero eso no dice mucho ya que $\times$ también está cerrado en los racionales sin embargo, su trivial para mostrar:

$$\operatorname{Th}(\Bbb{R}, 0,1,+, \times, \le) \ne \operatorname{Th}(\Bbb{Q}, 0,1,+,\times \le) $$

Es decir, considerar

$$ \exists x \forall y |1 + 1 \le x*x \le 1 + 1 $$

Esta frase sólo es cierto para $\Bbb{R}$ $x$ en la pregunta que hace verdadera no existe en $\Bbb{Q}$.

Así que mi anterior intuición sobre el cierre y la densidad, no tienen un peso importante para ellos.

Pero entonces, ¿cómo debo proceder?

Answer 1

Recomiendo el uso de Ehrenfeucht-Fraisse juegos (esto es posiblemente porque simplemente me gustan :P).

Le da un par de relacional (ver a continuación) estructuras de $\mathcal{A}$ $\mathcal{B}$ natural y un número $n$, considere el siguiente juego de $EF_n(\mathcal{A},\mathcal{B})$ entre los dos jugadores, Mezclar y combinar:

• En el turn $k$, Mezcla primero juega un elemento de una estructura o la otra: o $a_k\in\mathcal{A}$ o $b_k\in\mathcal{B}$. A continuación, Coincide juega un elemento de la oposición de la estructura: o $b_k\in\mathcal{B}$ o $a_k\in\mathcal{A}$.

• El juego continúa para $n$ se convierte - al final de la cual, Mezclar y combinar han construido una secuencia $a_1, a_2, . . . , a_n$ de los elementos de $\mathcal{A}$ y una secuencia $b_1, b_2, . . . , b_n$ de los elementos de $\mathcal{B}$.

• Ahora, nos fijamos en la atómica de los diagramas de las tuplas $(a_i)$$(b_i)$: si hay un cuantificador fórmula libre de $\varphi(x_1, . . . , x_n)$ tal que $$\mathcal{A}\models\varphi(a_1, . . . , a_n)\quad\mbox{ but }\quad\mathcal{B}\not\models\varphi(b_1, . . . , b_n),$$ a continuación, Mezclar la gana; de lo contrario (es decir, si las tuplas "el mismo aspecto") Partido gana.

He aquí el hecho notable:

$\mathcal{A}\equiv\mathcal{B}$ fib partida de jugador tiene una estrategia ganadora en cada juego de $EF_n(\mathcal{A}, \mathcal{B})$.

Así que usted puede probar en la escuela elemental de la equivalencia de dos estructuras mediante la descripción de una estrategia ganadora para el Partido (y, por supuesto, lo que demuestra que en realidad es una estrategia ganadora).

EF-juegos son sin duda un a veces técnica: otros métodos son a menudo mucho más rápido. Sin embargo, personalmente creo que la EF de los juegos de los más intuitivamente satisfactoria enfoque, y realmente no entiendo por qué dos estructuras son elementarily equivalente hasta que sepa cómo ganar el EF-juego entre ellos.

---

OK, ¿qué es eso del "relacional" de negocios? Bien, una relacional de la estructura es sólo una estructura que sólo tiene constantes y relaciones - no hay funciones. Malas noticias: usted tiene funciones! Buenas noticias: usted puede deshacerse de ellos! Podemos "relationalize" una estructura $\mathcal{A}$ mediante la sustitución de cada una de las $n$-ary símbolo de función $f$ $(n+1)$- ary relación símbolo $G_f$, el gráfico de $f$: $$G_f^\mathcal{A}=\{(a_1, . . . , a_n, a_{n+1}): f^{\mathcal{A}}(a_1, . . . , a_n)=a_{n+1}\}.$$

A ver por qué relationalization es necesario, imagine que hemos jugado, la longitud-1 EF-juego con el funcional de las estructuras de $\mathcal{A}=(\mathbb{R}, +, 1)$$\mathcal{B}=(\mathbb{Q}, +, 1)$. Como Mezcla, me gustaría jugar al $a_1=\pi\in\mathcal{A}$; Partido tendría que jugar algunos racional $b_1\in \mathcal{B}$. Supongamos $b_1={p\over q}$; a continuación, $b_1$ satisfaría la fórmula atómica $b_1+. . . .+b_1=1+. . . .+1$ ($q$-muchos "$+$"s a la izquierda, $p$-muchos en la derecha) en $\mathcal{A}$. Pero, por supuesto, $\pi$ no satisface la correspondiente fórmula en $\mathcal{A}$. Así que, Mix, iba a ganar!

En el relationalization, por el contrario, yo no sería capaz de tirar de ese truco - me llevaría $\max\{q, p\}$-muchos movimientos para ser capaz de "mostrar" que $b_1$ $\pi$ eran diferentes. Así que para que coincida $\pi$ en el juego de la longitud de la $n$, solo hay que escoger una $b_1$ que está "cerca de $\pi$ y no demasiado racional" - por ejemplo, el más cercano racional con denominador $n+1$. Si intenta jugar, digamos, $EF_2$ de las dos estructuras, usted comenzará a ver lo que una estrategia ganadora para el Partido parece . . .

Una idea similar - que nos podemos encontrar en "definible" elementos que "parezca" indefinible elementos durante el tiempo suficiente para ganar específicos EF-juegos - funciona para mostrar que la lineal órdenes de $\mathbb{Z}$ $\mathbb{Z}\oplus\mathbb{Z}$ son elementarily equivalente; véase el capítulo 6 de Rosenstein el maravilloso libro de "Lineal Órdenes" (https://books.google.com/books?id=y3YpdW-sbFsC&pg=PA93&lpg=PA93&dq=ehrenfeucht-fraisse+game+Z+linear+order&source=bl&ots=eREBRBKTDL&sig=9aBq9q7YLHzB6ujtpeW92IPoFK4&hl=en&sa=X&ved=0CCAQ6AEwATgKahUKEwj6zq3ewpTJAhUd02mkhrtwanq#v=onepage&q=ehrenfeucht-fraisse%20game%20Z%20linear%20order&f=false).