Puede localmente finitos de estructuras realmente se definen como aquellas estructuras de la omisión de una determinada cuantificador libre tipo?

Question

Mi pregunta es 2.3.8(b) en Hodges' Un Corto Modelo de la Teoría, p.43. (También en su Modelo original de la Teoría de la p. 47). Voy a citar el problema, siga las definiciones de términos clave y, a continuación, explicar por qué la declaración de probar que se siente falso para mí.

L es de primer orden de la lengua, con un número finito de símbolos. Demostrar que no es un cuantificador libre de tipo tal que una estructura $A$ es localmente finito si se omite el tipo.

[Definiciones: un localmente finitos de la estructura es una estructura en donde cada subconjunto finito genera un número finito de la subestructura. Una $n$-el tipo es un conjunto de fórmulas en las variables de $x_1,\dots,x_n$. Un tipo es una $n$-tipo para algún entero positivo $n$. Un tipo se omite por una estructura si no hay manera de conectar las variables con los elementos de la estructura, de modo que todas las fórmulas son simultáneamente verdaderas.]

La razón por la que siente falso, es que puedo construir, para cualquier $n$, con una estructura de una lengua con un único binario símbolo de función tal que todos los $n$ elementos genera un número finito de la subestructura pero donde $n+1$ elementos puede generar un infinito de la subestructura. A mí me parece que un $n$-tipo no debería ser capaz de distinguir entre una estructura y una localmente finito. Lo he comprobado en la fe de erratas y no encontraron nada, así que tal vez mi intuición está justo al lado.

Answer 1

Este es un error en Hodges. Como usted dice, para cualquier $n>0$, es posible construir una estructura $B_n=<U,f>$ donde $f$ es una función binaria símbolo, de tal forma que cada $n$ elementos de $B_n$ generar un número finito de la subestructura, pero hay $n+1$ elementos de $B_n$ que generan un infinito de la subestructura. Por ejemplo, usted puede tomar $U={\mathbb Z_{\ge 0}}$ y $$f(a,b)=a+1,\ \ \ \ \ \hbox{if $b \equiv un+1 \ \ ({\rm mod}\ n+1)$},$$ $$f(a,b)=a, \ \ \ \ \hbox{otherwise.}$$ $f$ se ha definido de manera que se puede generar sin más elementos que la única función sucesor ($S(x)=x+1$), pero es posible que se genere menos, como en el fin de generar un elemento que es igual a $S(a)$, el residuo de la clase de $S(a)$ modulo $n+1$ debe de estar ya ocupados. Ahora, los elementos $\{0,1,2,\ldots,n\}$ generar todos los de $U$ bajo $S$ y ocupan todos los residuos de las clases modulo $n+1$, por lo que generar todos los de $U$ bajo $f$. Sin embargo, cualquier $n$-element set $V$ debe omitir algunos residuos de la clase modulo $n+1$. A continuación, comenzando con un poco de $a\in V$ como el primer argumento de $f$, sólo podemos generar algún subconjunto de $$T_a:=\{a, S(a), S^2(a), \ldots, S^n(a)\},$$ desde antes de que podamos generar todos los de $T_a$, llegaremos a la fallida, los residuos de la clase, que no se puede rellenar con $f$. Por lo tanto, cualquier $n$-element set $V$ puede generar sólo un número finito de la subestructura de $B_n$.

Ahora, tomando el lenguaje de $L$$\{f\}$, si hubo un cuantificador libre tipo de $T({\bf x})$ que $L$estructura $A$ fue localmente finito iff se omite $T({\bf x})$, $T({\bf x})$ tendría que ser un $m$-tipo de algunos $m$. Entonces a partir de la $B_m$ no es localmente finito, debe darse cuenta de $T({\bf x})$, es decir, hay elementos $a_1$, $\ldots$, $a_m$ en $B_m$ tal que $B_m \vDash T(a_1,\ldots,a_m)$. Pero desde $T({\bf x})$ es cuantificador libre, entonces también tenemos $C \vDash T(a_1,\ldots,a_m)$ donde $C$ es el finito subestructura de $B_m$ generado por $\{a_1,\ldots,a_m\}$. Por lo tanto, $C$ da cuenta de $T({\bf x})$. Desde $C$ es finito, es localmente finito, así que esto es una contradicción. Por lo tanto, la declaración no puede ser probado.

En Un corto modelo de la teoría, el ejercicio se lee:

Deje $L$ ser de primer orden lenguaje. Una $L$estructura $A$ se dice localmente finito si cada finitely generado subestructura de $A$ es finito. (a) Demostrar que existe un conjunto de $\Omega$ de cuantificador libre de tipos (es decir, tipos que consta de cuantificador libre de fórmulas) tal que para cada a $L$-estructura $A$, $A$ es localmente finito si y sólo si $A$ omite todo tipo en $\Omega$. (b) Mostrar que si $L$ ha finito de la firma, a continuación, podemos elegir el conjunto $\Omega$ (a) que constan de un solo tipo.

Para solucionarlo, cambiar la última frase:

(b) Mostrar que si $L$ ha finito de la firma, a continuación, podemos elegir el conjunto $\Omega$ (a) constan de una sola $n$-tipo para cada una de las $n$.

El ejercicio debe entonces ser factible.