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 s∈C∪F∪R, usaremos sA para denotar a i(s).

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

1. (1) F(cA)=cB, para todo c∈C,

2. (2) F(fA(a1,...,an))=fB(F(a1),...,F(an)), para cada f∈Fn, a1,...,an∈A.

3. (3) (a1,...,an)∈rA implica (F(a1),...,F(an))∈rB, para todo r∈Rn, a1,...,an∈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≅B), cuando haya un isomorfismo F de A en B. Diremos que F:A→B es un homomorfismo para expresar que F es un homomorfismo de A en B. Analogamente diremos que F:A→B es un isomorfismo para expresar que F es un isomorfismo de A en B.

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

Proof. Por induccion. Sea

1. - Teok: Si F:A→B es un homomorfismo, entonces F(tA[(a1,a2,...)]=tB[(F(a1),F(a2),...)] para cada t∈Tτk, (a1,a2,...)∈AN.

Teo0 es trivial. Veamos que Teok implica Teok+1. Supongamos que vale Teok y supongamos F:A→B es un homomorfismo, t∈Tτk+1−Tτk y →a=(a1,a2,...)∈AN. Denotemos (F(a1),F(a2),...) con F(→a). Por Lema 7.2, t=f(t1,...,tn), con n≥1,f∈Fn y t1,...,tn∈Tτ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)]  

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

Teok: Supongamos que F:A→B 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 n≥1,r∈Rn y t1,...,tn∈Tτ. 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 φ=(t≡s) 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+1−Fτk. Por el lema de lectura única de fórmulas hay varios casos:

Caso φ=(φ1∨φ2), con φ1,φ2∈Fτ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, φ1∈Fτk. Veamos cada implicacion por separado. Supongamos A⊨φ[→a]. Entonces por la def de ⊨ se tiene que A⊨φ1[↓aj(→a)], para todo a∈A. Por Teok tenemos que B⊨φ1[F(↓aj(→a))], para todo a∈A. Pero ya que F(↓aj(→a))=↓F(a)j(F(→a)) tenemos que B⊨φ1[↓F(a)j(F(→a))], para todo a∈A. Como F es suryectiva obtenemos que B⊨φ1[↓bj(F(→a))], para todo b∈B. 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 b∈B. Obviamente esto nos dice que B⊨φ1[↓F(a)j(F(→a))], para todo a∈A. Pero como ↓F(a)j(F(→a))=F(↓aj(→a)) , tenemos que B⊨φ1[F(↓aj(→a))], para todo a∈A. Por Teok tenemos entonces que A⊨φ1[↓aj(→a)], para todo a∈A, 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.

Proof. Solo falta probar que F−1 es un homomorfismo. Supongamos que c∈C. Ya que F(cA)=cB, tenemos que F−1(cB)=cA, por lo cual F−1 cumple (1) de la definicion de homomorfismo. Supongamos ahora que f∈Fn y sean b1,...,bn∈B. Sean a1,...,an∈A tales que F(ai)=bi, i=1,...,n. Tenemos que F−1(fB(b1,...,bn))=F−1(fB(F(a1),...,F(an)))=F−1(F(fA(a1,...,an)))=fA(a1,...,an)=fA(F−1(b1),...,F−1(bn)) por lo cual F−1 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) A⊆B

2. (2) cA=cB, para cada c∈C

3. (3) fA=fB|An, para cada f∈Fn, n≥1

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

1. (1) ∅≠A⊆B

2. (2) cB∈A, para cada c∈C

3. (3) fB(a1,...,an)∈A, para cada (a1,...,an)∈An, f∈Fn

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 c∈C

3. (3) fA=fB|An, para cada f∈Fn.

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≠∅, tenemos que IF≠∅. Es claro que cB=F(cA)∈IF, para cada c∈C. Sea f∈Fn y sean b1,...,bn∈IF 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,...,bn∈A yf∈Fn.

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

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

2. (2) fA/θ(a1/θ,...,an/θ)=fA(a1,...,an)/θ, para cada f∈Fn.

3. (3) cA/θ=cA/θ, para cada c∈C

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

Proof. Sea f∈Fn. Supongamos que a1,...,an,b1,...,bn∈A 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 A→A/θa→a/θ lo llamaremos la proyeccion canonica y lo denotaremos con πθ.

Proof. Sea c∈C. Tenemos que πθ(cA)=cA/θ=cA/θ Sea f∈Fn, con n≥1 y sean a1,...,an∈A. Tenemos que πθ(fA(a1,...,an))=fA(a1,...,an)/θ=fA/θ(a1/θ,...,an/θ)=fA/θ(πθ(a1),...,πθ(an)) con lo cual πθ es un homomorfismo. Es trivial que kerπθ=θ  

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

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 c∈C. Tenemos que ˉF(cA/kerF)=ˉF(cA/kerF)=F(cA)=cB Sea f∈Fn. Sean a1,...,an∈A. 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 c∈C

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

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

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

Proof. Veamos que π1 es un homomorfismo. Primero notese que si c∈C, entonces π1(cA×B)=π1((cA,cB))=cA Sea f∈Fn, con n≥1 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