Paradoja aparente de tipo principal 1

Question

Paradoja aparente de tipo principal 1

lógica
Matemáticas
teoría de modelos

La apuesta de Pascal

Esta es una pregunta de seguimiento a Oración equivalente a $\bigwedge_{i=1}^ \infty \sigma_i$ sin usar infinitas conjunciones . tenemos un idioma $\mathcal{L}=\{R\}$ (con igualdad) donde $R$ es un símbolo de relación binaria. Dejar $\tau$ sea la oración diciendo $R$ es reflexiva, simétrica y transitiva. Para cada $k \geq 1$ , dejar $\sigma_k$ ser la oración que dice que hay exactamente una clase de equivalencia de tamaño $k$ .

Tengo algunas preguntas sobre esta configuración:

#1: Si $\mathcal{A}, \mathcal{B}$ son $\mathcal{L}$ -estructuras tales que $\{\tau, \sigma_1, \sigma_2, \dots\}$ es satisfecho por ambos, y si $\mathcal{A}, \mathcal{B}$ ambos no tienen clases de equivalencia infinita, entonces esto significa $Th(\mathcal{A})=Th(\mathcal{B})$ ? [Intuitivamente, supongo que esto es cierto, pero no entiendo cómo ver por qué formalmente.]

Asumiendo que la respuesta a la #1 es sí, (digamos $Th(\mathcal{A})=Th(\mathcal{B})=T$ ) entonces tengo otro dilema, o "paradoja" por así decirlo, que tengo problemas para resolver.

#2: ¿Cuántos tipos completos de 1 de $T$ ¿hay?

Uno quiere decir que hay $\aleph_0$ muchos, porque parece que para cada uno $n$ debería existir algún tipo 1 completo $\Sigma_n(v)$ tal que la fórmula $\theta_i(v)$ dicho " $v$ está en la clase de equivalencia de tamaño $i$ " pertenece a $\Sigma_n(v)$ si y solo si $n=i$ . Además, parece que un tipo 1 completo arbitrario $\Sigma(v)$ debe ser de la forma $\Sigma_n(v)$ para algunos $n$ , ya que no hay clases de equivalencia infinitas.

Por otra parte, parece que cada $\Sigma_n(v)$ es un tipo 1 completo principal, aislado por $\theta_i(u)$ . [Corrígeme si estoy equivocado. Una vez que sabemos qué clase de equivalencia $u$ está en sabemos todo lo que hay que saber sobre $u$ , por lo que en particular deberíamos tener $T \models \forall v(\theta_n(v) \to \phi(v))$ para cualquier $\phi \in \Sigma_n$ , ¿bien?]

Ahora hay un teorema que dice que una teoría completa $T$ tiene infinitos tipos 1 completos si y solo si existe al menos algún tipo 1 completo no principal. Así que los dos párrafos anteriores parecen contradecirse entre sí. Si hay $\aleph_0$ muchos tipos 1 completos, entonces debería haber al menos alguno no principal. Pero si todos son directores, entonces no puede haber $\aleph_0$ muchos. ¿Qué he hecho mal?

Respuestas (1)

Paradoja aparente de tipo principal 1

noah schweber · Answer 1

Re: 1, sí - de hecho, tenemos el hecho más fuerte $\mathcal{A}\cong\mathcal{B}$ en ese caso. (Más generalmente, dos $\{R\}$ -estructuras satisfactorias $\tau$ con el mismo número de clases de cada cardinalidad son isomorfos.)

Re: 2, ¡te estás perdiendo el hecho de que "no hay una clase infinita" no es expresable en primer orden! La teoría $T$ en cuestión tiene el no principal $1$ -tipo correspondiente a " $x$ es un elemento de una clase infinita", aunque esto no se realiza en $\mathcal{A}$ o $\mathcal{B}$ , y esto refleja el hecho de que una estructura sin clases infinitas aún puede ser elementalmente equivalente a una estructura con algunas clases infinitas. Así que no hay paradoja aquí.

(De hecho, es un buen ejercicio para mostrar que $T=Th(\mathcal{A})=Th(\mathcal{B})$ es simplemente el cierre deductivo de $\{\tau\}\cup\{\sigma_k:k\in\mathbb{N}\}$ .)

Aquí hay una prueba de que solo hay un tipo no aislado (= no principal) y que el $\Sigma_n$ s son los únicos tipos aislados sobre $T$ :

Suponer $p,q$ son dos tipos más $T$ que no están entre los $\Sigma_n$ s. Dejar $\mathcal{M}\models T$ ser un modelo dándose cuenta de ambos $p$ y $q$ a través de $a$ y $b$ respectivamente. WLOG (aplicar dLS si es necesario) $\mathcal{M}$ es contable, por lo que a fortiori cada clase en $\mathcal{M}$ es finito o contablemente infinito. Por suposición sobre $p$ y $q$ lo sabemos $[a]_\mathcal{M}$ y $[b]_\mathcal{M}$ debe ser infinito. Pero entonces debe haber un automorfismo. $\alpha\in Aut(\mathcal{M})$ con $\alpha(a)=b$ . (Más generalmente, siempre que $\mathcal{N}\models T$ entonces la relación de la órbita del automorfismo es simplemente $\{(u,v): \vert[u]_\mathcal{N}\vert=\vert[v]_\mathcal{N}\vert\}$ , y este es un buen ejercicio, esencialmente el mismo que en el primer párrafo de esta respuesta).

Pero esto significa que $a$ y $b$ realizar los mismos tipos en $\mathcal{M}$ , eso es, $p=q$ . Entonces hay exactamente uno $(1-)$ escribe encima $T$ junto al $\Sigma_n$ s. Y ya sabemos que este tipo debe ser entonces no aislado.

Entonces, si entiendo correctamente, mi error fue donde dije "Además, parece que un tipo 1 completo arbitrario $\Sigma(v)$ debe ser de la forma $\Sigma_n(v)$ para algunos $n$ , ya que no hay clases de equivalencia infinitas". ¿Todo lo demás es correcto?
@ Pascal'sWager Sí, así es. Más ampliamente, "tipo realizado en $\mathcal{X}$ " y "tipo consistente con $Th(\mathcal{X})$ " en general no son la misma noción, y eso es lo que estamos viendo aquí.
Bueno, gracias. Todavía estoy tratando de averiguar cuántos tipos completos de cada tipo (sin juego de palabras) hay. son los $\Sigma_n$ ( $n \in \mathbb{Z}^+$ ) los únicos principales, o hay más? ¿Y hay varios que no son principales o solo el único que mencionó en su respuesta?
El $\Sigma_n$ s son los únicos principales, y solo existe el único tipo no principal. Creo que Lowenheim-Skolem es la forma más fácil de probar esto (demostrar que si $\mathcal{M}\models T$ con $a,b\in\mathcal{M}$ no satisfaciendo ninguno de los $\Sigma_n$ s, entonces hay una subestructura elemental $\{a,b\}\subseteq\mathcal{N}\preccurlyeq\mathcal{M}$ con $a$ y $b$ en la misma órbita de automorfismo de $\mathcal{N}$ ). El $n$ -tipos para $n>1$ no son mucho más complicados.
Esta es probablemente una pregunta muy ingenua, pero ¿cómo sabemos el $\Sigma_n$ son de hecho principal? [Sé que dije antes que $\Sigma_n$ está aislado por $\theta_n$ , pero solo confiaba en mi intuición. ¿Cómo lo vería uno formalmente? Estaba pensando en tal vez probar algún argumento sobre la complejidad de $\phi$ pero eso es probablemente una exageración.]
@Pascal'sWager Una vez más, piense en los automorfismos: demuestre que si $a,b\in\mathcal{M}\models T$ y $\vert[a]_\mathcal{M}\vert=\vert[b]_\mathcal{M}\vert<\aleph_0$ (lo que sucede si cada uno satisface el mismo $\Sigma_n$ ), entonces hay un automorfismo $\alpha\in Aut(\mathcal{M})$ con $\alpha(a)=b$ . Tenga en cuenta que este es realmente solo un caso especial del segundo ejercicio mencionado en mi respuesta, que a su vez es básicamente el mismo que el primero. En general, los automorfismos (esp. + submodelo elemental/argumentos de extensión) proporcionan una herramienta muy poderosa para analizar tipos.
Ahora es cierto que hay indefinibilidad/equivalencia/etc. resultados en los que los auto/isomorfismos son insuficientes (a menudo porque un argumento basado en auto/isomorfismos es tosco y se aplica a todas las lógicas "razonables" y, por lo tanto, no puede ayudarnos en los resultados que, por ejemplo, se cumplen para la lógica de primer orden pero no para la lógica de segundo orden). lógica de orden). Para un ejemplo relativamente elemental de las limitaciones de este método, mientras que "dLS+isomorfismos" es suficiente para establecer la completitud de la teoría de los órdenes lineales densos sin puntos finales, la completitud de Presburger tiene más cuidado .
Pero siempre es una buena idea ver primero si un argumento basado en auto/isomorfismo puede abordar el problema en cuestión, y en este caso tales argumentos son suficientes.
Gracias, volveré a esto más tarde y le daré una oportunidad. En este momento estoy tratando de verificar el $p=q$ parte y ya casi termino, pero lo que no entiendo es por qué $\alpha(a)=b$ implica que ambos tipos son iguales. Quiero decir, $\alpha: \mathcal{M} \to \mathcal{M}$ es un isomorfismo, por lo que para cualquier fórmula sin cuantificador $\phi(u)$ tenemos $\mathcal{M} \models \phi[a]$ si y si $\mathcal{M} \models \phi[b]$ . Pero que si $\phi(u)$ ¿No está libre de cuantificadores? (Cuando dices "automorfismo", ¿estás asumiendo que es elemental?)
@Pascal'sWager ¡Todos los automorfismos conservan propiedades de complejidad arbitraria! Este es uno de los ejercicios más fundamentales sobre lógica de primer orden (inducción sobre la complejidad).

Paradoja aparente de tipo principal 1

La apuesta de Pascal

Respuestas (1)

noah schweber

La apuesta de Pascal

noah schweber

La apuesta de Pascal

noah schweber

La apuesta de Pascal

noah schweber

noah schweber

noah schweber

La apuesta de Pascal

noah schweber

¿Es la teoría de los lenguajes formales regulares finitamente axiomatizable?

Encontrar un universo adecuado para una estructura dada

¿Cómo se especifica la semántica completa de SOL y HOL?

Un número finito de modelos contables implica decidibilidad

Cada modelo de ZFC tiene un elemento que es un modelo de ZFC

Modelos de aritmética sucesora

Un modelo que tiene solo un elemento indefinible sobre un lenguaje con solo un número finito de símbolos

Brecha en el lema: la teoría satisfacible implica una teoría libre de contradicciones

¿Por qué los modelos de ZF que no son ωω\omega-modelos tienen fórmulas no estándar cuya longitud es "números naturales infinitamente grandes"?

No axiomatizabilidad y ultraproductos