Loading [MathJax]/jax/output/CommonHTML/jax.js

7.9 Un poco de semantica

Dado que las estructuras de tipo τ constituyen los "mundos posibles" donde las formulas de tipo τ 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 τ, A=(A,i), para cada sCFR, usaremos sA para denotar a i(s).

Sean A y B modelos de tipo τ. Una funcion F:AB sera un homomorfismo de A en B si se cumplen las siguientes

  1. (1) F(cA)=cB, para todo cC,

  2. (2) F(fA(a1,...,an))=fB(F(a1),...,F(an)), para cada fFn, a1,...,anA.

  3. (3) (a1,...,an)rA implica (F(a1),...,F(an))rB, para todo rRn, a1,...,anA.

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: AB), cuando haya un isomorfismo F de A en B. Diremos que F:AB es un homomorfismo para expresar que F es un homomorfismo de A en B. Analogamente diremos que F:AB es un isomorfismo para expresar que F es un isomorfismo de A en B.

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

7.16. Sea F:AB un homomorfismo. Entonces F(tA[(a1,a2,...)]=tB[(F(a1),F(a2),...)] para cada tTτ, (a1,a2,...)AN.

Proof. Por induccion. Sea

  1. - Teok: Si F:AB es un homomorfismo, entonces F(tA[(a1,a2,...)]=tB[(F(a1),F(a2),...)] para cada tTτk, (a1,a2,...)AN.

Teo0 es trivial. Veamos que Teok implica Teok+1. Supongamos que vale Teok y supongamos F:AB es un homomorfismo, tTτk+1Tτk y a=(a1,a2,...)AN. Denotemos (F(a1),F(a2),...) con F(a). Por Lema 7.2, t=f(t1,...,tn), con n1,fFn y t1,...,tnTτk. Tenemos entonces F(tA[a])=F(f(t1,...,tn)A[a])=F(fA(tA1[a],...,tAn[a]))=fB(F(tA1[a]),...,F(tAn[a]))=fB(tB1[F(a)],...,tBn[F(a)]))=f(t1,...,tn)B[F(a)]=tB[F(a)]  


7.17. Supongamos que F:AB es un isomorfismo. Sea φFτ. Entonces Aφ[(a1,a2,...)] sii Bφ[(F(a1),F(a2),...)] para cada (a1,a2,...)AN. En particular A y B satisfacen las mismas sentencias de tipo τ.

Proof. Para a=(a1,a2,...)AN, denotemos (F(a1),F(a2),...) con F(a). Por induccion. Sea

Teok: Supongamos que F:AB es un isomorfismo. Sea φFτk. Entonces Aφ[a] sii Bφ[F(a)] para cada (a1,a2,...)AN

Prueba de Teo0. Hay dos casos. Caso φ=r(t1,...,tn), con n1,rRn y t1,...,tnTτ. Tenemos entonces Aφ[a]sii(tA1[a],...,tAm[a])rA (def de )sii(F(tA1[a]),...,F(tAn[a]))rB (F es iso)sii(tB1[F(a)]),...,tBn[F(a)])rB (Lema ???)siiBφ[F(a)] El caso φ=(ts) es dejado al lector. Ahora veamos que Teok implica Teok+1. Supongamos que vale Teok. Probaremos que vale entonces Teok+1. Si φFτk obviamente podemos directamente aplicar Teok. Supongamos entonces que φFτk+1Fτk. Por el lema de lectura única de fórmulas hay varios casos:

Caso φ=(φ1φ2), con φ1,φ2Fτk. Entonces

2Aφ[a] sii Aφ1[a] o Aφ2[a](def de \models) sii Bφ1[F(a)] o B[F(a)](Teok) sii Bφ[F(a)](def de \models)

Los casos φ=(φ1φ2), φ=(φ1φ2), φ=(φ1φ2) y φ=¬φ1 son analógos al caso anterior.

Caso φ=xjφ1, φ1Fτk. Veamos cada implicacion por separado. Supongamos Aφ[a]. Entonces por la def de se tiene que Aφ1[aj(a)], para todo aA. Por Teok tenemos que Bφ1[F(aj(a))], para todo aA. Pero ya que F(aj(a))=F(a)j(F(a)) tenemos que Bφ1[F(a)j(F(a))], para todo aA. Como F es suryectiva obtenemos que Bφ1[bj(F(a))], para todo bB. Ahora la def de nos dice que Bφ1[F(a)]. Supongamos ahora que Bφ1[F(a)]. La def de nos dice que Bφ1[bj(F(a))], para todo bB. Obviamente esto nos dice que Bφ1[F(a)j(F(a))], para todo aA. Pero como F(a)j(F(a))=F(aj(a)) , tenemos que Bφ1[F(aj(a))], para todo aA. Por Teok tenemos entonces que Aφ1[aj(a)], para todo aA, lo cual por la def de nos dice que Aφ[a].

El caso φ=xjφ1 es analógo al anterior.  


7.9.2 Algebras

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

7.18. Supongamos τ es algebraico. Si F:AB es un homomorfismo biyectivo, entonces F es un isomorfismo.

Proof. Solo falta probar que F1 es un homomorfismo. Supongamos que cC. Ya que F(cA)=cB, tenemos que F1(cB)=cA, por lo cual F1 cumple (1) de la definicion de homomorfismo. Supongamos ahora que fFn y sean b1,...,bnB. Sean a1,...,anA tales que F(ai)=bi, i=1,...,n. Tenemos que F1(fB(b1,...,bn))=F1(fB(F(a1),...,F(an)))=F1(F(fA(a1,...,an)))=fA(a1,...,an)=fA(F1(b1),...,F1(bn)) por lo cual F1 satisface (2) de la definicion de homomorfismo  


7.9.2.1 Subalgebras

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

  1. (1) AB

  2. (2) cA=cB, para cada cC

  3. (3) fA=fB|An, para cada fFn, n1

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

  1. (1) AB

  2. (2) cBA, para cada cC

  3. (3) fB(a1,...,an)A, para cada (a1,...,an)An, fFn

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 τ 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 τ-algebra B podemos definir en forma natural una τ-algebra A de la siguiente manera:

  1. (1) Universo de A=A

  2. (2) cA=cB, para cada cC

  3. (3) fA=fB|An, para cada fFn.

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.

7.19. Supongamos τ es algebraico. Si F:AB es un homomorfismo, entonces IF es un subuniverso de B

Proof. Ya que A, tenemos que IF. Es claro que cB=F(cA)IF, para cada cC. Sea fFn y sean b1,...,bnIF Sean a1,...,an tales que F(ai)=bi, i=1,...,n. Tenemos que fB(b1,...,bn)=fB(F(a1),...,F(an))=F(fA(a1,...,an))IF por lo cual IF es cerrada bajo fB.  


7.9.2.2 Congruencias

Sea A una τ-algebra. Una congruencia sobre A es una relacion de equivalencia θ sobre A la cual cumple que a1θb1,...,anθbn implica fA(a1,...,an)θfA(b1,...,bn) cualesquiera sean a1,...,an,b1,...,bnA yfFn.

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

  1. (1) Universo de A/θ=A/θ={a/θ:aA}={clases de equivalencia de θ}

  2. (2) fA/θ(a1/θ,...,an/θ)=fA(a1,...,an)/θ, para cada fFn.

  3. (3) cA/θ=cA/θ, para cada cC

A/θ sera llamada el algebra cociente de A por θ.

7.20. Supongamos τ es algebraico. Si F:AB es un homomorfismo, entonces kerF es una congruencia sobre A

Proof. Sea fFn. Supongamos que a1,...,an,b1,...,bnA son tales que a1kerFb1,...,ankerFbn. Tenemos entonces que F(fA(a1,...,an))=fB(F(a1),...,F(an))=fB(F(b1),...,F(bn))=F(fA(b1,...,bn)) lo cual nos dice que fA(a1,...,an)kerFfA(b1,...,bn)  


Al mapeo AA/θaa/θ lo llamaremos la proyeccion canonica y lo denotaremos con πθ.

7.21. πθ:AA/θ es un homomorfismo cuyo nucleo es θ

Proof. Sea cC. Tenemos que πθ(cA)=cA/θ=cA/θ Sea fFn, con n1 y sean a1,...,anA. Tenemos que πθ(fA(a1,...,an))=fA(a1,...,an)/θ=fA/θ(a1/θ,...,an/θ)=fA/θ(πθ(a1),...,πθ(an)) con lo cual πθ es un homomorfismo. Es trivial que kerπθ=θ  


7.2. Para cada tTτ, aAN, se tiene que tA/θ[(a1/θ,a2/θ,...)]=tA[(a1,a2,...)]/θ.

Proof. Ya que πθ es un homomorfismo, se puede aplicar el Lema 7.16.  


7.3. Sea F:AB un homomorfismo suryectivo. Entonces A/kerFBa/kerFF(a) define sin ambiguedad una funcion ˉF la cual es un isomorfismo de A/kerF en B

Proof. Notese que la definicion de ˉF es inambigua ya que si a/kerF=a/kerF, entonces F(a)=F(a). Ya que F es sobre, tenemos que ˉF lo es. Supongamos que ˉF(a/kerF)=ˉF(a/kerF). Claramente entonces tenemos que F(a)=F(a), lo cual nos dice que a/kerF=a/kerF. Esto prueba que ˉF es inyectiva. Para ver que ˉF es un isomorfismo, por el Lema 7.18, basta con ver que ˉF es un homomorfismo. Sea cC. Tenemos que ˉF(cA/kerF)=ˉF(cA/kerF)=F(cA)=cB Sea fFn. Sean a1,...,anA. Tenemos que ˉF(fA/kerF(a1/kerF,...,an/kerF))=ˉF(fA(a1,...,an)/kerF)=F(fA(a1,...,an))=fB(F(a1),...,F(an))=fB(ˉF(a1/kerF),...,ˉF(an/kerF)) con lo cual ˉF cunple (2) de la definicion de homomorfismo  


7.9.2.3 Producto directo de algebras

Dadas τ-algebras A,B, definamos una nueva τ-algebra A×B, de la siguiente manera

  1. (1) Universo de A×B=A×B

  2. (2) cA×B=(cA,cB), para cada cC

  3. (3) fA×B((a1,b1),...,(an,bn))=(fA(a1,...,an),fB(b1,...,bn)), para cada fFn

Llamaremos a A×B el producto directo de A y B.

Los mapeos π1:A×BA(a,b)a                           π2:A×BB(a,b)b seran llamados las proyecciones canonicas asociadas al producto A×B

7.22. Los mapeos π1:A×BA y π2:A×BB son homomorfismos

Proof. Veamos que π1 es un homomorfismo. Primero notese que si cC, entonces π1(cA×B)=π1((cA,cB))=cA Sea fFn, con n1 y sean (a1,b1),...,(an,bn)A×B. Tenemos que π1(fA×B((a1,b1),...,(an,bn))=π1((fA(a1,...,an),fB(b1,...,bn))=fA(a1,...,an)=fA(π1(a1,b1),...,π1(an,bn)) con lo cual hemos probado que π1 cumple (2) de la definicion de homomorfismo  


7.23. Para cada tTτ, ((a1,b1),(a2,b2),...)(A×B)N, se tiene que tA×B[((a1,b1),(a2,b2),...)]=(tA[(a1,a2,...)],tB[(b1,b2,...)])