Mostrar un homomorphism existe iff existen homomorphisms de cada finitely generado subestructura

Question

Deje $L$ ser una firma (o la lengua), y deje $\mathcal{A}$ ser finito $L$-modelo (o $L$-estructura). Demostrar que existe un homomorphism de una $L$modelo $\mathcal{B}$ a $\mathcal{A}$ si y sólo si hay homomorphisms de cada finitely generado subestructura de $\mathcal{B}$ a $\mathcal{A}$.

He aquí lo que tengo hasta ahora: creo que el "$\Rightarrow$" la dirección es simple, como usted puede simplemente tomar el dado homomorphism restringido a la subestructura; este debe ser un homomorphism.

Inicialmente se pensó que el "$\Leftarrow$" era trivial, ya que se puede tomar $\mathcal{B}$ como uno de los finitely generado subestructuras. Pero luego me di cuenta de que $\mathcal{B}$ no puede ser finitely generado a partir de una subestructura (es posible?). Me siento como que podría tener el uso de compacidad o ultraproducts (dada la frase "finitely generado subsuelo"), pero no estoy realmente seguro de cómo.

Le pido disculpas si lo que estoy diciendo no tiene sentido, todavía estoy tratando de conseguir una comprensión de los modelos de la teoría. Cualquier ayuda se agradece!

Answer 1

Supongo que las operaciones y las relaciones de $L$ son finitary. Deje $A$ $B$ ser el subyacente conjuntos de $\mathcal A$ $\mathcal B.$ Deje $[B]^{\lt\omega}$ ser el conjunto de todos los subconjuntos finitos de $B.$ Deje $\mathcal U$ ser un ultrafilter en $[B]^{\lt\omega}$ tal que $\{X\in[B]^{\lt\omega}:b\in X\}\in\mathcal U$ por cada $b\in B.$

Para cada una de las $X\in[B]^{\lt\omega}$ elegir un homomorphism $f_X:\langle X\rangle\to\mathcal A,$ donde $\langle X\rangle$ es la subestructura de la $\mathcal B$ generado por $X.$ Por cada $b\in B,$ definir $f(b)$ como el único elemento $a\in A$ tal que $f_X(b)=a$ $\mathcal U$- casi todos los $X\in[B]^{\lt\omega},$, $\{X\in[B]^{\lt\omega}:f_X(b)=a\}\in\mathcal U.$ (un elemento $a$ existe porque $A$ es finito, y debido a la especial propiedad de la ultrafilter $\mathcal U$, lo que garantiza que $f_X(b)$ está definido por $\mathcal U$-casi todos los $X.$) Esta función $f:\mathcal B\to\mathcal A$ es un homomorphism.

A ver que $f$ es un homomorphism, se observa que, si $k\lt\omega$ $b_1,\dots,b_k\in B,$ $f|\{b_1,\dots,b_k\}=f_X|\{b_1,\dots,b_k\}$ para algunos (de hecho, para casi todos) $X\in[B]^{\lt\omega}.$

Ejemplo: Si $\mathcal B$ es un (simple, sin dirección, no necesariamente finita) gráfico, y si $\mathcal A=K_n$ (el grafo completo de orden $n$) para algunos naturales $n,$, a continuación, un homomorphism de la gráfica de $\mathcal B$ a $\mathcal A$ es sólo una adecuada $n$-coloración de los vértices de $\mathcal B.$ En este caso tenemos el De Bruijn–Erdős teorema que dice que un grafo es $n$-engañosa iff cada finito subgrafo es $n$-engañosa.