Dado que las estructuras de tipo \(\tau\) constituyen los "mundos posibles" donde las formulas de tipo \(\tau\) se "interpretan" se suele llamar semantica al estudio general de las estructuras y su vinculacion con el lenguaje. Aqui daremos algunas nociones basicas de semantica.
La nocion de homomorfismo estaba restringida a unos pocos casos particulares de estructuras estudiadas pero ahora con nuestra definicion general de estructura podemos generalizarla en forma natural. Antes una notacion muy util. Dado un modelo de tipo \(\tau\), \(\mathbf{A}=(A,i)\), para cada \(s\in\mathcal{C}\cup\mathcal{F}\cup\mathcal{R}\), usaremos \(s^{\mathbf{A}}\) para denotar a \(i(s)\).
Sean \(\mathbf{A}\) y \(\mathbf{B}\) modelos de tipo \(\tau\). Una funcion \(F:A\rightarrow B\) sera un homomorfismo de \(\mathbf{A}\) en \(\mathbf{B}\) si se cumplen las siguientes
adhocprefix(1)adhocsufix \(F(c^{\mathbf{A}})=c^{\mathbf{B}}\), para todo \(c\in\mathcal{C}\),
adhocprefix(2)adhocsufix \(F(f^{\mathbf{A}}(a_{1},...,a_{n}))=f^{\mathbf{B}}(F(a_{1}),...,F(a_{n}))\), para cada \(f\in\mathcal{F}_{n}\), \(a_{1},...,a_{n}\in A\).
adhocprefix(3)adhocsufix \((a_{1},...,a_{n})\in r^{\mathbf{A}}\) implica \((F(a_{1}),...,F(a_{n}))\in r^{\mathbf{B}}\), para todo \(r\in\mathcal{R}_{n}\), \(a_{1},...,a_{n}\in A\).
Un isomorfismo de \(\mathbf{A}\) en \(\mathbf{B}\) sera un un homomorfismo de \(\mathbf{A}\) en \(\mathbf{B}\) el cual sea biyectivo y cuya inversa sea un homomorfismo de \(\mathbf{B}\) en \(\mathbf{A}\). Diremos que los modelos \(\mathbf{A}\) y \(\mathbf{B}\) son isomorfos (en simbolos: \(\mathbf{A}\cong\mathbf{B}\)), cuando haya un isomorfismo \(F\) de \(\mathbf{A}\) en \(\mathbf{B}\). Diremos que \(F:\mathbf{A}\rightarrow\mathbf{B}\) es un homomorfismo para expresar que \(F\) es un homomorfismo de \(\mathbf{A}\) en \(\mathbf{B}\). Analogamente diremos que \(F:\mathbf{A}\rightarrow\mathbf{B}\) es un isomorfismo para expresar que \(F\) es un isomorfismo de \(\mathbf{A}\) en \(\mathbf{B}\).
Ejercicio: Pruebe que la relacion \(\cong\) es reflexiva, transitiva y simetrica.
7.16. Sea \(F:\mathbf{A}\rightarrow\mathbf{B}\) un homomorfismo. Entonces \[F(t^{\mathbf{A}}[(a_{1},a_{2},...)]=t^{\mathbf{B}}[(F(a_{1}),F(a_{2}),...)]\] para cada \(t\in T^{\tau}\), \((a_{1},a_{2},...)\in A^{\mathbf{N}}\).
Proof. Por induccion. Sea
adhocprefix-adhocsufix Teo\(_{k}\): Si \(F:\mathbf{A}\rightarrow\mathbf{B}\) es un homomorfismo, entonces \[F(t^{\mathbf{A}}[(a_{1},a_{2},...)]=t^{\mathbf{B}}[(F(a_{1}),F(a_{2}),...)]\] para cada \(t\in T_{k}^{\tau}\), \((a_{1},a_{2},...)\in A^{\mathbf{N}}\).
Teo\(_{0}\) es trivial. Veamos que Teo\(_{k}\) implica Teo\(_{k+1}\). Supongamos que vale Teo\(_{k}\) y supongamos \(F:\mathbf{A}\rightarrow\mathbf{B}\) es un homomorfismo, \(t\in T_{k+1}^{\tau}-T_{k}^{\tau}\) y \(\vec{a}=(a_{1},a_{2},...)\in A^{\mathbf{N}}\). Denotemos \((F(a_{1}),F(a_{2}),...)\) con \(F(\vec{a})\). Por Lema 7.2, \(t=f(t_{1},...,t_{n})\), con \(n\geq1\),\(\;f\in\mathcal{F}_{n}\) y \(t_{1},...,t_{n}\in T_{k}^{\tau}\). Tenemos entonces \[\begin{array}{ccl} F(t^{\mathbf{A}}[\vec{a}]) & = & F(f(t_{1},...,t_{n})^{\mathbf{A}}[\vec{a}])\\ & = & F(f^{\mathbf{A}}(t_{1}^{\mathbf{A}}[\vec{a}],...,t_{n}^{\mathbf{A}}[\vec{a}]))\\ & = & f^{\mathbf{B}}(F(t_{1}^{\mathbf{A}}[\vec{a}]),...,F(t_{n}^{\mathbf{A}}[\vec{a}]))\\ & = & f^{\mathbf{B}}(t_{1}^{\mathbf{B}}[F(\vec{a})],...,t_{n}^{\mathbf{B}}[F(\vec{a})]))\\ & = & f(t_{1},...,t_{n})^{\mathbf{B}}[F(\vec{a})]\\ & = & t^{\mathbf{B}}[F(\vec{a})] \end{array}\]
7.17. Supongamos que \(F:\mathbf{A}\rightarrow\mathbf{B}\) es un isomorfismo. Sea \(\varphi\in F^{\tau}\). Entonces \[\mathbf{A}\models\varphi[(a_{1},a_{2},...)]\text{ sii }\mathbf{B}\models\varphi[(F(a_{1}),F(a_{2}),...)]\] para cada \((a_{1},a_{2},...)\in A^{\mathbf{N}}\). En particular \(\mathbf{A}\) y \(\mathbf{B}\) satisfacen las mismas sentencias de tipo \(\tau\).
Proof. Por induccion. Sea
adhocprefix-adhocsufix Teo\(_{k}\): Supongamos que \(F:\mathbf{A}\rightarrow\mathbf{B}\) es un isomorfismo. Sea \(\varphi\in F_{k}^{\tau}\). Entonces \[\mathbf{A}\models\varphi[(a_{1},a_{2},...)]\text{ sii }\mathbf{B}\models\varphi[(F(a_{1}),F(a_{2}),...)]\] para cada \((a_{1},a_{2},...)\in A^{\mathbf{N}}\)
Prueba de Teo\(_{0}\). Supongamos que \(F:\mathbf{A}\rightarrow\mathbf{B}\) es un isomorfismo, \(\varphi\in F_{0}^{\tau}\) y \((a_{1},a_{2},...)\in A^{\mathbf{N}}\). Probaremos que \[\mathbf{A}\models\varphi[(a_{1},a_{2},...)]\text{ sii }\mathbf{B}\models\varphi[(F(a_{1}),F(a_{2}),...)]\] Hay dos casos. Caso \(\varphi=r(t_{1},...,t_{n})\), con \(n\geq1\),\(\;r\in\mathcal{R}_{n}\) y \(t_{1},...,t_{n}\in T^{\tau}\). Denotemos con \(\vec{a}\) a \((a_{1},a_{2},...)\) y con \(F(\vec{a})\) a \((F(a_{1}),F(a_{2}),...)\). Tenemos entonces \[\begin{array}{ccl} \mathbf{A}\models\varphi[\vec{a}] & \text{sii} & (t_{1}^{\mathbf{A}}[\vec{a}],...,t_{m}^{\mathbf{A}}[\vec{a}])\in r^{\mathbf{A}}\text{ (def de }\models\text{)}\\ & \text{sii} & (F(t_{1}^{\mathbf{A}}[\vec{a}]),...,F(t_{n}^{\mathbf{A}}[\vec{a}]))\in r^{\mathbf{B}}\text{ (}F\text{ es iso)}\\ & \text{sii} & (t_{1}^{\mathbf{B}}[F(\vec{a})]),...,t_{n}^{\mathbf{B}}[F(\vec{a})])\in r^{\mathbf{B}}\text{ (Lema \ref{F-respeta-term})}\\ & \text{sii} & \mathbf{B}\models\varphi[F(\vec{a})] \end{array}\] Dejamos al lector completar la prueba de que Teo\(_{k}\) implica Teo\(_{k+1}\)
Un tipo \(\tau\) sera llamado algebraico si no contiene nombres de relacion (i.e. \(\mathcal{R}=\emptyset\)). Un modelo de un tipo algebraico \(\tau\) sera llamado una \(\tau\)-algebra. Ejemplos clasicos de \(\tau\)-algebras son los grupos (\(\tau=(\{e\},\{.^{2}\},\emptyset,a)\)), los reticulados terna, los reticulados acotados, las algebras de Boole, etc. Muchos de los resultados y definiciones dados en la Seccion [capitulo estructuras algebraicas ordenadas] para reticulados terna, reticulados acotados y reticulados complementados pueden ahora ser generalizados naturalmente para \(\tau\)-algebras. Desarrollaremos un poco esta linea de "algebra general" la cual ha tenido un fuerte impacto en el area de las especificaciones algebraicas de tipos de datos.
Tal como sucedia para las distintas estructuras reticuladas estudiadas, tenemos que cuando \(\mathcal{R}=\emptyset\), la nocion de isomorfismo se simplifica.
7.18. Supongamos \(\tau\) es algebraico. Si \(F:\mathbf{A}\rightarrow\mathbf{B}\) es un homomorfismo biyectivo, entonces \(F\) es un isomorfismo.
Proof. Solo falta probar que \(F^{-1}\) es un homomorfismo. Supongamos que \(c\in\mathcal{C}\). Ya que \(F(c^{\mathbf{A}})=c^{\mathbf{B}}\), tenemos que \(F^{-1}(c^{\mathbf{B}})=c^{\mathbf{A}}\), por lo cual \(F^{-1}\) cumple (1) de la definicion de homomorfismo. Supongamos ahora que \(f\in\mathcal{F}_{n}\) y sean \(b_{1},...,b_{n}\in B\). Sean \(a_{1},...,a_{n}\in A\) tales que \(F(a_{i})=b_{i}\), \(i=1,...,n\). Tenemos que \[\begin{array}{ccl} F^{-1}(f^{\mathbf{B}}(b_{1},...,b_{n})) & = & F^{-1}(f^{\mathbf{B}}(F(a_{1}),...,F(a_{n})))\\ & = & F^{-1}(F(f^{\mathbf{A}}(a_{1},...,a_{n})))\\ & = & f^{\mathbf{A}}(a_{1},...,a_{n})\\ & = & f^{\mathbf{A}}(F^{-1}(b_{1}),...,F^{-1}(b_{n})) \end{array}\] por lo cual \(F^{-1}\) satisface (2) de la definicion de homomorfismo
Dadas \(\tau\)-algebras \(\mathbf{A}\) y \(\mathbf{B}\), diremos que \(\mathbf{A}\) es una subalgebra de \(\mathbf{B}\) cuando se den las siguientes condiciones
adhocprefix(1)adhocsufix \(A\subseteq B\)
adhocprefix(2)adhocsufix \(c^{\mathbf{A}}=c^{\mathbf{B}}\), para cada \(c\in\mathcal{C}\)
adhocprefix(3)adhocsufix \(f^{\mathbf{A}}=f^{\mathbf{B}}|_{A^{n}}\), para cada \(f\in\mathcal{F}_{n}\), \(n\geq1\)
Si \(\mathbf{B}\) es una \(\tau\)-algebra, entonces un subuniverso de \(\mathbf{B}\) es un conjunto \(A\) el cual cumple las siguientes condiciones:
adhocprefix(1)adhocsufix \(\emptyset\neq A\subseteq B\)
adhocprefix(2)adhocsufix \(c^{\mathbf{B}}\in A,\) para cada \(c\in\mathcal{C}\)
adhocprefix(3)adhocsufix \(f^{\mathbf{B}}(a_{1},...,a_{n})\in A\), para cada \((a_{1},...,a_{n})\in A^{n},\) \(f\in\mathcal{F}_{n}\)
Es importante notar que si bien los conceptos de subalgebra y subuniverso estan muy relacionados, se trata de objetos diferentes ya que las subalgebras de un algebra dada son estructuras de tipo \(\tau\) y por lo tanto son pares ordenados y los subuniversos de un algebra dada son ciertos subconjuntos por lo cual no son pares ordenados. A continuacion presisaremos la relacion que hay entre estos dos conceptos. Notese que dado un subuniverso \(A\) de una \(\tau\)-algebra \(\mathbf{B}\) podemos definir en forma natural una \(\tau\)-algebra \(\mathbf{A}\) de la siguiente manera:
adhocprefix(1)adhocsufix Universo de \(\mathbf{A}=A\)
adhocprefix(2)adhocsufix \(c^{\mathbf{A}}=c^{\mathbf{B}},\) para cada \(c\in\mathcal{C}\)
adhocprefix(3)adhocsufix \(f^{\mathbf{A}}=f^{\mathbf{B}}|_{A^{n}},\) para cada \(f\in\mathcal{F}_{n}\).
Es facil chequear que el algebra \(\mathbf{A}\) asi definida es una subalgebra de \(\mathbf{B}\). Lo anterior nos muestra que los subuniversos de un algebra dada son precisamente los universos de las distintas subalgebras de dicha algebra.
7.19. Supongamos \(\tau\) es algebraico. Si \(F:\mathbf{A}\rightarrow\mathbf{B}\) es un homomorfismo, entonces \(I_{F}\) es un subuniverso de \(\mathbf{B}\)
Proof. Ya que \(A\neq\emptyset,\) tenemos que \(I_{F}\neq\emptyset.\) Es claro que \(c^{\mathbf{B}}=F(c^{\mathbf{A}})\in I_{F},\) para cada \(c\in\mathcal{C}\). Sea \(f\in\mathcal{F}_{n}\) y sean \(b_{1},...,b_{n}\in I_{F}\) Sean \(a_{1},...,a_{n}\) tales que \(F(a_{i})=b_{i},\) \(i=1,...,n\). Tenemos que \[f^{\mathbf{B}}(b_{1},...,b_{n})=f^{\mathbf{B}}(F(a_{1}),...,F(a_{n}))=F(f^{\mathbf{A}}(a_{1},...,a_{n}))\in I_{F}\] por lo cual \(I_{F}\) es cerrada bajo \(f^{\mathbf{B}}\).
Sea \(\mathbf{A}\) una \(\tau\)-algebra. Una congruencia sobre \(\mathbf{A}\) es una relacion de equivalencia \(\theta\) sobre \(A\) la cual cumple que \[a_{1}\theta b_{1},...,a_{n}\theta b_{n}\text{ implica }f^{\mathbf{A}}(a_{1},...,a_{n})\theta f^{\mathbf{A}}(b_{1},...,b_{n})\] cualesquiera sean \(a_{1},...,a_{n},b_{1},...,b_{n}\in A\) y\(\;f\in\mathcal{F}_{n}\).
Dada una congruencia \(\theta\) sobre \(\mathbf{A}\) se puede formar una nueva algebra \(\mathbf{A}/\theta\) de la siguiente manera:
adhocprefix(1)adhocsufix Universo de \(\mathbf{A}/\theta=A/\theta=\{a/\theta:a\in A\}=\{\)clases de equivalencia de \(\theta\}\)
adhocprefix(2)adhocsufix \(f^{\mathbf{A}/\theta}(a_{1}/\theta,...,a_{n}/\theta)=f^{\mathbf{A}}(a_{1},...,a_{n})/\theta,\) para cada \(f\in\mathcal{F}_{n}.\)
adhocprefix(3)adhocsufix \(c^{\mathbf{A}/\theta}=c^{\mathbf{A}}/\theta,\) para cada \(c\in\mathcal{C}\)
\(\mathbf{A}/\theta\) sera llamada el algebra cociente de \(\mathbf{A}\) por \(\theta\).
7.20. Supongamos \(\tau\) es algebraico. Si \(F:\mathbf{A}\rightarrow\mathbf{B}\) es un homomorfismo, entonces \(\ker F\) es una congruencia sobre \(\mathbf{A}\)
Proof. Sea \(f\in\mathcal{F}_{n}\). Supongamos que \(a_{1},...,a_{n},b_{1},...,b_{n}\in A\) son tales que \(a_{1}\ker Fb_{1},...,a_{n}\ker Fb_{n}\). Tenemos entonces que \[\begin{array}{ccl} F(f^{\mathbf{A}}(a_{1},...,a_{n})) & = & f^{\mathbf{B}}(F(a_{1}),...,F(a_{n}))\\ & = & f^{\mathbf{B}}(F(b_{1}),...,F(b_{n}))\\ & = & F(f^{\mathbf{A}}(b_{1},...,b_{n})) \end{array}\] lo cual nos dice que \(f^{\mathbf{A}}(a_{1},...,a_{n})\ker Ff^{\mathbf{A}}(b_{1},...,b_{n})\)
Al mapeo \[\begin{array}{lll} A & \rightarrow & A/\theta\\ a & \rightarrow & a/\theta \end{array}\] lo llamaremos la proyeccion canonica y lo denotaremos con \(\pi_{\theta}\).
7.21. \(\pi_{\theta}:\mathbf{A}\rightarrow\mathbf{A}/\theta\) es un homomorfismo cuyo nucleo es \(\theta\)
Proof. Sea \(c\in\mathcal{C}\). Tenemos que \[\pi_{\theta}(c^{\mathbf{A}})=c^{\mathbf{A}}/\theta=c^{\mathbf{A}/\theta}\] Sea \(f\in\mathcal{F}_{n}\), con \(n\geq1\) y sean \(a_{1},...,a_{n}\in A\). Tenemos que \[\begin{array}{ccl} \pi_{\theta}(f^{\mathbf{A}}(a_{1},...,a_{n})) & = & f^{\mathbf{A}}(a_{1},...,a_{n})/\theta\\ & = & f^{\mathbf{A}/\theta}(a_{1}/\theta,...,a_{n}/\theta)\\ & = & f^{\mathbf{A}/\theta}(\pi_{\theta}(a_{1}),...,\pi_{\theta}(a_{n})) \end{array}\] con lo cual \(\pi_{\theta}\) es un homomorfismo. Es trivial que \(\ker\pi_{\theta}=\theta\)
7.2. Para cada \(t\in T^{\tau}\), \(\vec{a}\in A^{\mathbf{N}},\) se tiene que \(t^{\mathbf{A}/\theta}[(a_{1}/\theta,a_{2}/\theta,...)]=t^{\mathbf{A}}[(a_{1},a_{2},...)]/\theta.\)
Proof. Ya que \(\pi_{\theta}\) es un homomorfismo, se puede aplicar el Lema 7.16.
7.3. Sea \(F:\mathbf{A}\rightarrow\mathbf{B}\) un homomorfismo suryectivo. Entonces \[\begin{array}{lll} A/\ker F & \rightarrow & B\\ a/\ker F & \rightarrow & F(a) \end{array}\] define sin ambiguedad una funcion \(\bar{F}\) la cual es un isomorfismo de \(\mathbf{A}/\ker F\) en \(\mathbf{B}\)
Proof. Notese que la definicion de \(\bar{F}\) es inambigua ya que si \(a/\ker F=a^{\prime}/\ker F\), entonces \(F(a)=F(a^{\prime}).\) Ya que \(F\) es sobre, tenemos que \(\bar{F}\) lo es. Supongamos que \(\bar{F}(a/\ker F)=\bar{F}(a^{\prime}/\ker F).\) Claramente entonces tenemos que \(F(a)=F(a^{\prime})\), lo cual nos dice que \(a/\ker F=a^{\prime}/\ker F\). Esto prueba que \(\bar{F}\) es inyectiva. Para ver que \(\bar{F}\) es un isomorfismo, por el Lema 7.18, basta con ver que \(\bar{F}\) es un homomorfismo. Sea \(c\in\mathcal{C}\). Tenemos que \[\bar{F}(c^{\mathbf{A}/\ker F})=\bar{F}(c^{\mathbf{A}}/\ker F)=F(c^{\mathbf{A}})=c^{\mathbf{B}}\] Sea \(f\in\mathcal{F}_{n}\). Sean \(a_{1},...,a_{n}\in A\). Tenemos que \[\begin{array}{ccl} \bar{F}(f^{\mathbf{A}/\ker F}(a_{1}/\ker F,...,a_{n}/\ker F)) & = & \bar{F}(f^{\mathbf{A}}(a_{1},...,a_{n})/\ker F)\\ & = & F(f^{\mathbf{A}}(a_{1},...,a_{n}))\\ & = & f^{\mathbf{B}}(F(a_{1}),...,F(a_{n}))\\ & = & f^{\mathbf{B}}(\bar{F}(a_{1}/\ker F),...,\bar{F}(a_{n}/\ker F)) \end{array}\] con lo cual \(\bar{F}\) cunple (2) de la definicion de homomorfismo
Dadas \(\tau\)-algebras \(\mathbf{A},\mathbf{B},\) definamos una nueva \(\tau\)-algebra \(\mathbf{A}\times\mathbf{B},\) de la siguiente manera
adhocprefix(1)adhocsufix Universo de \(\mathbf{A}\times\mathbf{B}=A\times B\)
adhocprefix(2)adhocsufix \(c^{\mathbf{A}\times\mathbf{B}}=(c^{\mathbf{A}},c^{\mathbf{B}})\), para cada \(c\in\mathcal{C}\)
adhocprefix(3)adhocsufix \(f^{\mathbf{A}\times\mathbf{B}}((a_{1},b_{1}),...,(a_{n},b_{n}))=(f^{\mathbf{A}}(a_{1},...,a_{n}),f^{\mathbf{B}}(b_{1},...,b_{n}))\), para cada \(f\in\mathcal{F}_{n}\)
Llamaremos a \(\mathbf{A}\times\mathbf{B}\) el producto directo de \(\mathbf{A}\) y \(\mathbf{B}.\)
Los mapeos \[\begin{array}{lll} \pi_{1}:A\times B & \rightarrow & A\\ \;\;\;\;\;(a,b) & \rightarrow & a \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{lll} \pi_{2}:A\times B & \rightarrow & B\\ \;\;\;\;\;(a,b) & \rightarrow & b \end{array}\] seran llamados las proyecciones canonicas asociadas al producto \(A\times B\)
7.22. Los mapeos \(\pi_{1}:\mathbf{A}\times\mathbf{B}\rightarrow\mathbf{A}\) y \(\pi_{2}:\mathbf{A}\times\mathbf{B}\rightarrow\mathbf{B}\) son homomorfismos
Proof. Veamos que \(\pi_{1}\) es un homomorfismo. Primero notese que si \(c\in\mathcal{C}\), entonces \[\pi_{1}(c^{\mathbf{A}\times\mathbf{B}})=\pi_{1}((c^{\mathbf{A}},c^{\mathbf{B}}))=c^{\mathbf{A}}\] Sea \(f\in\mathcal{F}_{n}\), con \(n\geq1\) y sean \((a_{1},b_{1}),...,(a_{n},b_{n})\in A\times B\). Tenemos que \[\begin{array}{ccl} \pi_{1}(f^{\mathbf{A}\times\mathbf{B}}((a_{1},b_{1}),...,(a_{n},b_{n})) & = & \pi_{1}((f^{\mathbf{A}}(a_{1},...,a_{n}),f^{\mathbf{B}}(b_{1},...,b_{n}))\\ & = & f^{\mathbf{A}}(a_{1},...,a_{n})\\ & = & f^{\mathbf{A}}(\pi_{1}(a_{1},b_{1}),...,\pi_{1}(a_{n},b_{n})) \end{array}\] con lo cual hemos probado que \(\pi_{1}\) cumple (2) de la definicion de homomorfismo
7.23. Para cada \(t\in T^{\tau},\) \(((a_{1},b_{1}),(a_{2},b_{2}),...)\in(A\times B)^{\mathbf{N}},\) se tiene que \(t^{\mathbf{A}\times\mathbf{B}}[((a_{1},b_{1}),(a_{2},b_{2}),...)]=(t^{\mathbf{A}}[(a_{1},a_{2},...)],t^{\mathbf{B}}[(b_{1},b_{2},...)])\)