7.9 Un poco de semantica

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.

7.9.1 Homomorfismos

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$, $A=(A,i)$, para cada $s\in C\cup F\cup R$, usaremos $s^A$ para denotar a $i\left(s\right)$.

Sean $A$ y $B$ modelos de tipo $\tau$. Una funcion $F:A\to B$ sera un homomorfismo de $A$ en $B$ si se cumplen las siguientes

1. (1) $F\left(c^A\right)=c^B$, para todo $c\in C$,

2. (2) $F\left(f^A\right(a_1,...,a_n\left)\right)=f^B\left(F\right(a_1),...,F(a_n\left)\right)$, para cada $f\in F_n$, $a_1,...,a_n\in A$.

3. (3) $(a_1,...,a_n)\in r^A$ implica $\left(F\right(a_1),...,F(a_n\left)\right)\in r^B$, para todo $r\in R_n$, $a_1,...,a_n\in A$.

Un isomorfismo de $A$ en $B$ sera un un homomorfismo de $A$ en $B$ el cual sea biyectivo y cuya inversa sea un homomorfismo de $B$ en $A$. Diremos que los modelos $A$ y $B$ son isomorfos (en simbolos: $A\cong B$), cuando haya un isomorfismo $F$ de $A$ en $B$. Diremos que $F:A\to B$ es un homomorfismo para expresar que $F$ es un homomorfismo de $A$ en $B$. Analogamente diremos que $F:A\to B$ es un isomorfismo para expresar que $F$ es un isomorfismo de $A$ en $B$.

Ejercicio: Pruebe que la relacion $\cong$ es reflexiva, transitiva y simetrica.

Proof. Por induccion. Sea

1. - Teo${}_k$: Si $F:A\to B$ es un homomorfismo, entonces $$F\left(t^A\right[(a_1,a_2,...)]=t^B[\left(F\right(a_1),F(a_2),...)]$$ para cada $t\in T_k^{\tau }$, $(a_1,a_2,...)\in A^N$.

Teo${}_0$ es trivial. Veamos que Teo${}_k$ implica Teo${}_{k+1}$. Supongamos que vale Teo${}_k$ y supongamos $F:A\to B$ es un homomorfismo, $t\in T_{k+1}^{\tau }-T_k^{\tau }$ y $\overrightarrow{a}=(a_1,a_2,...)\in A^N$. Denotemos $\left(F\right(a_1),F(a_2),...)$ con $F\left(\overrightarrow{a}\right)$. Por Lema 7.2, $t=f(t_1,...,t_n)$, con $n\ge 1$,$f\in F_n$ y $t_1,...,t_n\in T_k^{\tau }$. Tenemos entonces $$\begin{array}{ccc}F\left(t^A\right[\overrightarrow{a}\left]\right)& =& F\left(f\right(t_1,...,t_n{)}^A\left[\overrightarrow{a}\right])\\ & =& F\left(f^A\right(t_1^A\left[\overrightarrow{a}\right],...,t_n^A\left[\overrightarrow{a}\right]\left)\right)\\ & =& f^B\left(F\right(t_1^A\left[\overrightarrow{a}\right]),...,F(t_n^A\left[\overrightarrow{a}\right]\left)\right)\\ & =& f^B\left(t_1^B\right[F\left(\overrightarrow{a}\right)],...,t_n^B[F\left(\overrightarrow{a}\right)\left]\right))\\ & =& f(t_1,...,t_n{)}^B[F\left(\overrightarrow{a}\right)]\\ & =& t^B\left[F\right(\overrightarrow{a}\left)\right]\end{array}$$  

Proof. Para $\overrightarrow{a}=(a_1,a_2,...)\in A^N$, denotemos $\left(F\right(a_1),F(a_2),...)$ con $F\left(\overrightarrow{a}\right)$. Por induccion. Sea

Teo${}_k$: Supongamos que $F:A\to B$ es un isomorfismo. Sea $\phi \in F_k^{\tau }$. Entonces $$A\models \phi \left[\overrightarrow{a}\right]\text{sii}B\models \phi \left[F\right(\overrightarrow{a}\left)\right]$$ para cada $(a_1,a_2,...)\in A^N$

Prueba de Teo${}_0$. Hay dos casos. Caso $\phi =r(t_1,...,t_n)$, con $n\ge 1$,$r\in R_n$ y $t_1,...,t_n\in T^{\tau }$. Tenemos entonces $$\begin{array}{ccc}A\models \phi \left[\overrightarrow{a}\right]& \text{sii}& \left(t_1^A\right[\overrightarrow{a}],...,t_m^A[\overrightarrow{a}\left]\right)\in r^A\text{(def de}\models \text{)}\\ & \text{sii}& \left(F\right(t_1^A\left[\overrightarrow{a}\right]),...,F(t_n^A\left[\overrightarrow{a}\right]\left)\right)\in r^B\text{(}F\text{es iso)}\\ & \text{sii}& \left(t_1^B\right[F\left(\overrightarrow{a}\right)\left]\right),...,t_n^B\left[F\right(\overrightarrow{a}\left)\right])\in r^B\text{(Lema}\text{???}\text{)}\\ & \text{sii}& B\models \phi \left[F\right(\overrightarrow{a}\left)\right]\end{array}$$ El caso $\phi =(t\equiv s)$ es dejado al lector. Ahora veamos que ${\text{Teo}}_k\text{implica}{\text{Teo}}_{k+1}$. Supongamos que vale ${\text{Teo}}_k$. Probaremos que vale entonces ${\text{Teo}}_{k+1}$. Si $\phi \in F_k^{\tau }$ obviamente podemos directamente aplicar ${\text{Teo}}_k$. Supongamos entonces que $\phi \in F_{k+1}^{\tau }-F_k^{\tau }$. Por el lema de lectura única de fórmulas hay varios casos:

Caso $\phi =({\phi }_1\vee {\phi }_2)$, con ${\phi }_1,{\phi }_2\in F_k^{\tau }$. Entonces

$$\begin{array}{ccc}2A\models \phi \left[\overrightarrow{a}\right]& \text{sii}A\models {\phi }_1\left[\overrightarrow{a}\right]\text{o}A\models {\phi }_2\left[\overrightarrow{a}\right]& \left(\text{def de models}\right)\\ & \text{sii}B\models {\phi }_1\left[F\right(\overrightarrow{a}\left)\right]\text{o}B\models \left[F\right(\overrightarrow{a}\left)\right]& \left({\text{Teo}}_k\right)\\ & \text{sii}B\models \phi \left[F\right(\overrightarrow{a}\left)\right]& \left(\text{def de models}\right)\end{array}$$

Los casos $\phi =({\phi }_1\wedge {\phi }_2)$, $\phi =({\phi }_1\to {\phi }_2)$, $\phi =({\phi }_1\leftrightarrow {\phi }_2)$ y $\phi =\neg {\phi }_1$ son analógos al caso anterior.

Caso $\phi =\forall x_j{\phi }_1$, ${\phi }_1\in F_k^{\tau }$. Veamos cada implicacion por separado. Supongamos $A\models \phi \left[\overrightarrow{a}\right]$. Entonces por la def de $\models$ se tiene que $A\models {\phi }_1\left[{\downarrow }_j^a\right(\overrightarrow{a}\left)\right]$, para todo $a\in A$. Por ${\text{Teo}}_k$ tenemos que $B\models {\phi }_1\left[F\right({\downarrow }_j^a\left(\overrightarrow{a}\right)\left)\right]$, para todo $a\in A$. Pero ya que $F\left({\downarrow }_j^a\right(\overrightarrow{a}\left)\right)={\downarrow }_j^{F\left(a\right)}\left(F\right(\overrightarrow{a}\left)\right)$ tenemos que $B\models {\phi }_1\left[{\downarrow }_j^{F\left(a\right)}\right(F\left(\overrightarrow{a}\right)\left)\right]$, para todo $a\in A$. Como $F$ es suryectiva obtenemos que $B\models {\phi }_1\left[{\downarrow }_j^b\right(F\left(\overrightarrow{a}\right)\left)\right]$, para todo $b\in B$. Ahora la def de $\models$ nos dice que $B\models {\phi }_1\left[F\right(\overrightarrow{a}\left)\right]$. Supongamos ahora que $B\models {\phi }_1\left[F\right(\overrightarrow{a}\left)\right]$. La def de $\models$ nos dice que $B\models {\phi }_1\left[{\downarrow }_j^b\right(F\left(\overrightarrow{a}\right)\left)\right]$, para todo $b\in B$. Obviamente esto nos dice que $B\models {\phi }_1\left[{\downarrow }_j^{F\left(a\right)}\right(F\left(\overrightarrow{a}\right)\left)\right]$, para todo $a\in A$. Pero como ${\downarrow }_j^{F\left(a\right)}\left(F\right(\overrightarrow{a}\left)\right)=F\left({\downarrow }_j^a\right(\overrightarrow{a}\left)\right)$ , tenemos que $B\models {\phi }_1\left[F\right({\downarrow }_j^a\left(\overrightarrow{a}\right)\left)\right]$, para todo $a\in A$. Por ${\text{Teo}}_k$ tenemos entonces que $A\models {\phi }_1\left[{\downarrow }_j^a\right(\overrightarrow{a}\left)\right]$, para todo $a\in A$, lo cual por la def de $\models$ nos dice que $A\models \phi \left[\overrightarrow{a}\right]$.

El caso $\phi =\exists x_j{\phi }_1$ es analógo al anterior.  

7.9.2 Algebras

Un tipo $\tau$ sera llamado algebraico si no contiene nombres de relacion (i.e. $R=\varnothing$). Un modelo de un tipo algebraico $\tau$ sera llamado una $\tau$-algebra. Ejemplos clasicos de $\tau$-algebras son los grupos ($\tau =\left(\right\{e\},\{{.}^2\},\varnothing ,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 $R=\varnothing$, la nocion de isomorfismo se simplifica.

Proof. Solo falta probar que $F^{-1}$ es un homomorfismo. Supongamos que $c\in C$. Ya que $F\left(c^A\right)=c^B$, tenemos que $F^{-1}\left(c^B\right)=c^A$, por lo cual $F^{-1}$ cumple (1) de la definicion de homomorfismo. Supongamos ahora que $f\in F_n$ y sean $b_1,...,b_n\in B$. Sean $a_1,...,a_n\in A$ tales que $F\left(a_i\right)=b_i$, $i=1,...,n$. Tenemos que $$\begin{array}{ccc}{F}^{-1}\left(f^B\right(b_1,...,b_n\left)\right)& =& F^{-1}\left(f^B\right(F\left(a_1\right),...,F\left(a_n\right)\left)\right)\\ & =& F^{-1}\left(F\right(f^A(a_1,...,a_n)\left)\right)\\ & =& f^A(a_1,...,a_n)\\ & =& f^A\left(F^{-1}\right(b_1),...,F^{-1}(b_n\left)\right)\end{array}$$ por lo cual $F^{-1}$ satisface (2) de la definicion de homomorfismo  

7.9.2.1 Subalgebras

Dadas $\tau$-algebras $A$ y $B$, diremos que $A$ es una subalgebra de $B$ cuando se den las siguientes condiciones

1. (1) $A\subseteq B$

2. (2) $c^A=c^B$, para cada $c\in C$

3. (3) $f^A=f^B{|}_{A^n}$, para cada $f\in F_n$, $n\ge 1$

Si $B$ es una $\tau$-algebra, entonces un subuniverso de $B$ es un conjunto $A$ el cual cumple las siguientes condiciones:

1. (1) $\varnothing \ne A\subseteq B$

2. (2) $c^B\in A,$ para cada $c\in C$

3. (3) $f^B(a_1,...,a_n)\in A$, para cada $(a_1,...,a_n)\in A^n,$ $f\in 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 $B$ podemos definir en forma natural una $\tau$-algebra $A$ de la siguiente manera:

1. (1) Universo de $A=A$

2. (2) $c^A=c^B,$ para cada $c\in C$

3. (3) $f^A=f^B{|}_{A^n},$ para cada $f\in F_n$.

Es facil chequear que el algebra $A$ asi definida es una subalgebra de $B$. Lo anterior nos muestra que los subuniversos de un algebra dada son precisamente los universos de las distintas subalgebras de dicha algebra.

Proof. Ya que $A\ne \varnothing ,$ tenemos que $I_F\ne \varnothing .$ Es claro que $c^B=F\left(c^A\right)\in I_F,$ para cada $c\in C$. Sea $f\in F_n$ y sean $b_1,...,b_n\in I_F$ Sean $a_1,...,a_n$ tales que $F\left(a_i\right)=b_i,$ $i=1,...,n$. Tenemos que $$f^B(b_1,...,b_n)=f^B\left(F\right(a_1),...,F(a_n\left)\right)=F\left(f^A\right(a_1,...,a_n\left)\right)\in I_F$$ por lo cual $I_F$ es cerrada bajo $f^B$.  

7.9.2.2 Congruencias

Sea $A$ una $\tau$-algebra. Una congruencia sobre $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}^A(a_1,...,a_n)\theta f^A(b_1,...,b_n)$$ cualesquiera sean $a_1,...,a_n,b_1,...,b_n\in A$ y$f\in F_n$.

Dada una congruencia $\theta$ sobre $A$ se puede formar una nueva algebra $A/\theta$ de la siguiente manera:

1. (1) Universo de $A/\theta =A/\theta =\{a/\theta :a\in A\}=\{$clases de equivalencia de $\theta \}$

2. (2) $f^{A/\theta }(a_1/\theta ,...,a_n/\theta )=f^A(a_1,...,a_n)/\theta ,$ para cada $f\in F_n.$

3. (3) $c^{A/\theta }=c^A/\theta ,$ para cada $c\in C$

$A/\theta$ sera llamada el algebra cociente de $A$ por $\theta$.

Proof. Sea $f\in F_n$. Supongamos que $a_1,...,a_n,b_1,...,b_n\in A$ son tales que $a_1\ker F{b}_1,...,a_n\ker F{b}_n$. Tenemos entonces que $$\begin{array}{ccc}F\left(f^A\right(a_1,...,a_n\left)\right)& =& f^B\left(F\right(a_1),...,F(a_n\left)\right)\\ & =& f^B\left(F\right(b_1),...,F(b_n\left)\right)\\ & =& F\left(f^A\right(b_1,...,b_n\left)\right)\end{array}$$ lo cual nos dice que $f^A(a_1,...,a_n)\ker F{f}^A(b_1,...,b_n)$  

Al mapeo $$\begin{array}{ccc}A& \to & A/\theta \\ a& \to & a/\theta \end{array}$$ lo llamaremos la proyeccion canonica y lo denotaremos con ${\pi }_{\theta }$.

Proof. Sea $c\in C$. Tenemos que $${\pi }_{\theta }\left(c^A\right)=c^A/\theta =c^{A/\theta }$$ Sea $f\in F_n$, con $n\ge 1$ y sean $a_1,...,a_n\in A$. Tenemos que $$\begin{array}{ccc}{\pi }_{\theta }\left(f^A\right(a_1,...,a_n\left)\right)& =& f^A(a_1,...,a_n)/\theta \\ & =& f^{A/\theta }(a_1/\theta ,...,a_n/\theta )\\ & =& f^{A/\theta }\left({\pi }_{\theta }\right(a_1),...,{\pi }_{\theta }(a_n\left)\right)\end{array}$$ con lo cual ${\pi }_{\theta }$ es un homomorfismo. Es trivial que $\ker {\pi }_{\theta }=\theta$  

Proof. Ya que ${\pi }_{\theta }$ es un homomorfismo, se puede aplicar el Lema 7.16.  

Proof. Notese que la definicion de $\overline{F}$ es inambigua ya que si $a/\ker F=a^{\prime }/\ker F$, entonces $F\left(a\right)=F\left(a^{\prime }\right).$ Ya que $F$ es sobre, tenemos que $\overline{F}$ lo es. Supongamos que $\overline{F}\left(a/\ker F\right)=\overline{F}\left(a^{\prime }/\ker F\right).$ Claramente entonces tenemos que $F\left(a\right)=F\left(a^{\prime }\right)$, lo cual nos dice que $a/\ker F=a^{\prime }/\ker F$. Esto prueba que $\overline{F}$ es inyectiva. Para ver que $\overline{F}$ es un isomorfismo, por el Lema 7.18, basta con ver que $\overline{F}$ es un homomorfismo. Sea $c\in C$. Tenemos que $$\overline{F}\left(c^{A/\ker F}\right)=\overline{F}\left(c^A/\ker F\right)=F\left(c^A\right)=c^B$$ Sea $f\in F_n$. Sean $a_1,...,a_n\in A$. Tenemos que $$\begin{array}{ccc}\overline{F}\left(f^{A/\ker F}\right(a_1/\ker F,...,a_n/\ker F\left)\right)& =& \overline{F}\left(f^A\right(a_1,...,a_n\left)/\ker F\right)\\ & =& F\left(f^A\right(a_1,...,a_n\left)\right)\\ & =& f^B\left(F\right(a_1),...,F(a_n\left)\right)\\ & =& f^B\left(\overline{F}\right(a_1/\ker F),...,\overline{F}(a_n/\ker F\left)\right)\end{array}$$ con lo cual $\overline{F}$ cunple (2) de la definicion de homomorfismo  

7.9.2.3 Producto directo de algebras

Dadas $\tau$-algebras $A,B,$ definamos una nueva $\tau$-algebra $A\times B,$ de la siguiente manera

1. (1) Universo de $A\times B=A\times B$

2. (2) $c^{A\times B}=(c^A,c^B)$, para cada $c\in C$

3. (3) $f^{A\times B}\left(\right(a_1,b_1),...,(a_n,b_n\left)\right)=\left(f^A\right(a_1,...,a_n),f^B(b_1,...,b_n\left)\right)$, para cada $f\in F_n$

Llamaremos a $A\times B$ el producto directo de $A$ y $B.$

Los mapeos $$\begin{array}{ccc}{\pi }_1:A\times B& \to & A\\ (a,b)& \to & a\end{array}\begin{array}{ccc}{\pi }_2:A\times B& \to & B\\ (a,b)& \to & b\end{array}$$ seran llamados las proyecciones canonicas asociadas al producto $A\times B$

Proof. Veamos que ${\pi }_1$ es un homomorfismo. Primero notese que si $c\in C$, entonces $${\pi }_1\left(c^{A\times B}\right)={\pi }_1\left(\right(c^A,c^B\left)\right)=c^A$$ Sea $f\in F_n$, con $n\ge 1$ y sean $(a_1,b_1),...,(a_n,b_n)\in A\times B$. Tenemos que $$\begin{array}{ccc}{\pi }_1\left(f^{A\times B}\right((a_1,b_1),...,(a_n,b_n))& =& {\pi }_1\left(\right(f^A(a_1,...,a_n),f^B(b_1,...,b_n))\\ & =& f^A(a_1,...,a_n)\\ & =& f^A\left({\pi }_1\right(a_1,b_1),...,{\pi }_1(a_n,b_n\left)\right)\end{array}$$ con lo cual hemos probado que ${\pi }_1$ cumple (2) de la definicion de homomorfismo