Mostrando cualquier contables, denso, lineal pedido es isomorfo a un subconjunto de a $\mathbb{Q}$

Question

Estoy tratando de noquear a algunos de los posteriores ejercicios de Enderton Elementos de la Teoría de conjuntos. Este problema es el #17, que se encuentra en la página 227.

Un orden parcial $R$ se dice ser muy densa iff siempre $xRz$, $xRy$ $yRz$ algunos $y$. Suponga $(A,R)$ es un linealmente ordenado estructura con $A$ contables e $R$ denso. Mostrar que $(A,R)$ es isomorfo a $(B,<_Q)$ para algún subconjunto $B$$\mathbb{Q}$.

Yo tenía una idea, pero no estoy seguro de cómo comunicarlo formalmente, así que tengo la esperanza de conseguir un poco de ayuda en esto. En primer lugar, desde $A$ es contable, puedo enumerar como una secuencia, $A=\{a_0,a_1,a_2,\ldots\}$, incluso si este no es el real lineal de ordenación dictada por $R$. El texto sugiere que defina un poco de orden isomorfismo $f$ definiendo $f(a_i)$ por la recursividad en $i$.

Empecé por dejar a $f(a_0)=q_0$ para algunos arbitraria racional. Luego me mira a $a_1$ si $a_0Ra_1$, entonces yo les deje $q_0<f(a_1)$, y si $a_1Ra_0$, yo en lugar de elegir a $f(a_1)<q_0$. Esto continúa, así, por ejemplo, si $a_2Ra_1\land a_0Ra_2$, entonces yo les desea elegir a $f(a_2)$ tal que $q_0<f(a_2)<q_1$ y así sucesivamente.

Desde $\mathbb{Q}$ es densa, solo quiero elegir algunos racionales para conservar el orden como voy secuencialmente en $A$, y averiguar el orden de como me vaya. Esto es correcto? Si es así, ¿cuál es la manera rigurosa, esta idea? Estoy particularmente preocupado acerca de cómo $f$ puede responder donde el siguiente elemento $a_{i+1}$ podría estar en relación a la anterior $a_0,\ldots, a_i$, y cómo decidir qué elemento va a recoger. Gracias.

Answer 1

De hecho, no hay necesidad de suponer que $R$ es densa. El hecho es que cada contables de orden lineal incrusta en el racional de la línea. Otra forma de decir esto es que el racional de la línea (o cualquier contables densa orden lineal) es universal para contables lineal órdenes.

La prueba es tal y como lo describen. Dada una contables de fin de $\langle A,R\rangle$, enumerar $A=\{a_0,a_1,\ldots\}$ y construir el pleno del isomorfismo de $A$ a $\mathbb{Q}$ sucesivamente la definición de $f(a_n)$. En cualquier etapa de la construcción, tenemos un isomorfismo parcial la definición de las imágenes de $a_i$$i\lt n$, y queremos definir $f(a_n)$. Las imágenes $f(a_i)$ forma un subconjunto finito de $\mathbb{Q}$, el cual se divide $\mathbb{Q}$ en un número finito de intervalos. Así que nos fijamos en cómo $a_n$ se encuentra con respecto a la$a_i$$i\lt n$, es decir, en el que el intervalo de $A$ se encuentra entre aquellos que un número finito de puntos finales, y, a continuación, elija cualquier punto en $\mathbb{Q}$ que se encaja en el intervalo correspondiente en la imagen, y dejar que el punto de ser $f(a_n)$. Por lo tanto, hemos hecho un pedido en la preservación de mapa en cada etapa, y así el mapa completo es una orden-isomorfismo de $A$ con un subconjunto de a $\mathbb{Q}$ como se desee.

Cantor demostró también que, en el caso de $R$ es denso y la orden de $\langle A,R\rangle$ no tiene extremos, entonces, en el hecho de $\langle A,R\rangle$ es isomorfo a $\mathbb{Q}$, y se puede demostrar mediante el uso de la ida-y-técnica, utilizando la misma idea, pero ahora también se debe garantizar no sólo que el $n$-ésimo punto del dominio se le agrega el isomorfismo, pero también que el $n$-ésimo punto de la gama, se añade. Para demostrar la propiedad que usted solicitó, sin embargo, sólo se necesita la "otra" parte de la ida y vuelta de la construcción.

Answer 2

lo que están haciendo construyendo $f$ paso-por-paso se llama la construcción de un parcial mapa. Habiendo ya elegido $b_{i}$ ($=f(a_{i})$) para $i<m$, usted escoge $b_{m}$, de modo que conserva las relaciones que $a_{m}$ con$a_{i}$$i<m$. Esto es posible debido a $\mathbb{Q}$ es densa y no tiene extremos. Así, en cada estado puede ampliar el isomorfismo parcial. Después de $\omega$-muchos pasos, el dominio del mapa serán todos los de $A$, y el $f$ que se han construido será un fin de preservar la inyección de $(A,R)$ a $\mathbb{Q}$.

A ver que siempre se puede ampliar el parcial mapa, tenga en cuenta que usted sólo tiene que encontrar un número finito de condiciones de cada momento. Por lo que su $a_{i}$ atmost estar entre alguno de los dos elementos anteriores, o más grande que todos ellos o mayor que todos ellos. Pero desde $\mathbb{Q}$ es densa y no tiene extremos, en cada caso, podemos elegir un correspondiente $b_{i}$.

También, observe que no he hecho suposiciones aquí acerca de $(A,R)$ aquí, salvo que es una contables de orden lineal. En el caso de $(A,R)$ es contable, denso y no tiene extremos, puede hacerlo aún mejor, es decir, usted puede de una manera similar a construir un isomorfismo entre el$(A,R)$$(\mathbb{Q},<)$. La forma de hacerlo es similar a la anterior, excepto que usted enumerar $A$ $\mathbb{Q}$ y, a continuación, construir un isomorfismo de elemento por elemento tal que se respete el orden y tiene rango de $\mathbb{Q}$ y el dominio $A$. Una manera de hacerlo es asignar un elemento de $A$ a un elemento de $\mathbb{Q}$ y, a continuación, asignar al menos no asignados elemento de $\mathbb{Q}$ en la enumeración a un elemento de $A$.

Palabras clave para lo que usted está buscando son: De ida y vuelta método de Ehrenfeucht-Fraïssé juego. Cualquier modelo de la teoría del libro de texto (Hodges, Marcador, Poizat, etc) debe tener una cuenta detallada de este método.

Answer 3

Su esquema es simplemente una inductivo (o recursiva) definición de una función. Para definir una función de $f : \mathbb N \to X$ (o cualquier contables establece como dominio) de acuerdo a este esquema necesita i) el suministro de la base de casos $f(1)$, y ii) para cada una de las $n > 1$ suministro de una regla de cómo calcular $f(n)$ de sus predecesores $f(n-1), \ldots, f(1)$.

En tu ejemplo, vamos a $A = \{a_1, a_2, a_3,\ldots \}$ ser un contable infinito lineary conjunto ordenado, definir $f(a_1) \in A$ arbitrarias (por ejemplo,$f(a_1) := 0$). Para la inducción de paso, supongamos $f(a_1), \ldots, f(a_{n-1})$ han sido definidos ($n > 1$), a continuación, defina $f(a_n)$ según los siguientes casos:

i) $a_n > a_k$ todos los $k = 1,\ldots, n-1$, a continuación, establezca $f(a_n) = n$.

ii) $a_n < a_k$ todos los $k = 1,\ldots, n-1$, a continuación, establezca $f(a_n) = -n$.

iii) $a_1 < \ldots < a_i < a_n < a_j < \ldots < a_n$, a continuación, establezca $$ f(a_n) = \frac{\phi(a_i) + \phi(a_j)}{2} $$ (o algún otro número racional entre ellos).

El rendimiento de este un fin de preservar la inyección en $\mathbb Q$ (y, por tanto, un fin de preservar bijection a un subconjunto $B \subseteq \mathbb Q$), tenga en cuenta que la existencia de un denso conjunto de $R$ no fue utilizado aquí. También tenga en cuenta que la inyección no es un surjection en general, y a veces no es posible dar uno, por ejemplo no es posible encontrar un fin de preservar bijection de$\mathbb Z$$\mathbb Q$.

Entonces, ¿qué es este denso conjunto de $R$ útil? Usted necesita esto si usted quiere encontrar una surjection en $\mathbb Q$, pero como esto no está claramente establecido, creo que este ejercicio no está bien formulada. De todos modos, voy a decir un resultado que podrían ser de interés para usted, porque hay algo así como su conjunto $R$ es realmente necesario:

Teorema: Vamos a $(A, \precsim)$ ser un lineary conjunto ordenado, entonces las siguientes condiciones son equivalentes:

(i) no Hay un número finito o contable de la orden-subconjunto denso de $A$,

(ii) No es una inyección de $(A, \precsim)$ a $(\mathbb R, \le)$.

Una prueba de esto puede encontrarse en:

Fundamentos de la Medición, Volumen I, de D. H. Krantz, R. D. Luce, P. Suppes, A. Tversky.