7.8 Modelo matematico del valor de verdad de una formula

En esta seccion daremos una definicion matematica que modeliza la idea intuitiva de cuando una formula de tipo τ$\tau$ es verdadera en una estructura dada para una asignacion de elementos a las variables libres de dicha formula. Esto corresponde al punto (2) del Programa de Logica Matematica.

7.8.1 El valor de un termino en una estructura

Sea A=(A,i)$A=(A,i)$ una estructura de tipo τ$\tau$. Una asignacion de A$A$ sera un elemento de AN={$A^N=\{$infinituplas de elementos de A}$A\}$. Si →a=(a1,a2,...)$\overrightarrow{a}=(a_1,a_2,...)$ es una asignacion, entonces diremos que aj$a_j$ es el valor que →a$\overrightarrow{a}$ le asigna a la variable xj$x_j$.

Dada una estructura A$A$ de tipo τ$\tau$, un termino t∈Tτ$t\in T^{\tau }$ y una asignacion →a=(a1,a2,...)∈AN$\overrightarrow{a}=(a_1,a_2,...)\in A^N$ definamos recursivamente tA[→a]$t^A\left[\overrightarrow{a}\right]$ de la siguiente manera

1. (1) Si t=xi∈Var$t=x_i\in Var$, entonces tA[→a]=ai$t^A\left[\overrightarrow{a}\right]=a_i$

2. (2) Si t=c∈C$t=c\in C$, entonces tA[→a]=i(c)$t^A\left[\overrightarrow{a}\right]=i\left(c\right)$

3. (3) Si t=f(t1,...,tn)$t=f(t_1,...,t_n)$, con f∈Fn,n≥1$f\in F_n,n\ge 1$ y t1,...,tn∈Tτ$t_1,...,t_n\in T^{\tau }$, entonces tA[→a]=i(f)(tA1[→a],...,tAn[→a])$t^A\left[\overrightarrow{a}\right]=i\left(f\right)\left(t_1^A\right[\overrightarrow{a}],...,t_n^A[\overrightarrow{a}\left]\right)$

El elemento tA[→a]$t^A\left[\overrightarrow{a}\right]$ sera llamado el valor de t$t$ en la estructura A$A$ para la asignacion →a$\overrightarrow{a}$.

Veamos un ejemplo. Sea τ$\tau$ el tipo ({uno,doli},{MAS,P},{Her},{(MAS,4),(P,1),(Her,3)})$$\left(\right\{uno,doli\},\{MAS,P\},\{Her\},\{(MAS,4),(P,1),(Her,3)\left\}\right)$$ y sea A=(A,i)$A=(A,i)$ la estructura de tipo τ$\tau$ con universo A=R$A=R$ y

1. - i(uno)=9$i\left(uno\right)=9$

2. - i(doli)=0$i\left(doli\right)=0$

3. - i(MAS)$i\left(MAS\right)$ igual a la operacion R4→R(x,y,z,w)→2x+4y$$\begin{array}{ccc}{R}^4& \to & R\\ (x,y,z,w)& \to & 2x+4y\end{array}$$

4. - i(P)$i\left(P\right)$ igual a la operacion R→Rx→5x$$\begin{array}{ccc}R& \to & R\\ x& \to & 5^x\end{array}$$

5. - i(Her)={(x,y,z)∈R3:x.y.z=9}$i\left(Her\right)=\left\{\right(x,y,z)\in R^3:x.y.z=9\}$

Sea →a=(1,2,3,4,5,...)$\overrightarrow{a}=(1,2,3,4,5,...)$. Claramente →a$\overrightarrow{a}$ es una asignacion de A$A$. Se tiene que:

1. Si t=X554$t=X554$, entonces tA[→a]=X554A[→a]=554$t^A\left[\overrightarrow{a}\right]=X554^A\left[\overrightarrow{a}\right]=554$ (por (1) de la definicion recursiva de tA[→a]$t^A\left[\overrightarrow{a}\right]$)

2. Si t=uno$t=uno$, entonces tA[→a]=unoA[→a]=9$t^A\left[\overrightarrow{a}\right]={uno}^A\left[\overrightarrow{a}\right]=9$ (por (2) de la definicion recursiva de tA[→a]$t^A\left[\overrightarrow{a}\right]$)

3. Si t=P(X3)$t=P\left(X3\right)$, entonces tA[→a]=P(X3)A[→a]=i(P)(X3A[→a]) (por (3) de la definicion de tA[→a])=i(P)(3)=53=125$$\begin{array}{cc}{t}^A\left[\overrightarrow{a}\right]& =P\left(X3{)}^A\right[\overrightarrow{a}]\\ & =i\left(P\right)\left(X{3}^A\right[\overrightarrow{a}\left]\right)\text{(por (3) de la definicion de}{t}^A\left[\overrightarrow{a}\right]\text{)}\\ & =i\left(P\right)\left(3\right)\\ & =5^3=125\end{array}$$

4. Si t=MAS(X1,uno,X3,X554)$t=MAS(X1,uno,X3,X554)$, entonces tA[→a]=MAS(X1,uno,X3,X554)A[→a]=i(MAS)(X1A[→a],unoA[→a],X3A[→a],X554A[→a])=i(MAS)(1,9,3,554)=2.1+4.9=38$$\begin{array}{cc}{t}^A\left[\overrightarrow{a}\right]& =MAS(X1,uno,X3,X554{)}^A[\overrightarrow{a}]\\ & =i\left(MAS\right)\left(X{1}^A\right[\overrightarrow{a}],{uno}^A[\overrightarrow{a}],X{3}^A[\overrightarrow{a}],X554^A[\overrightarrow{a}\left]\right)\\ & =i\left(MAS\right)(1,9,3,554)\\ & =2.1+4.9=38\end{array}$$

Proof. Sea

Teok${}_k$: El lema vale para t∈Tτk$t\in T_k^{\tau }$.

Teo0${}_0$ es facil de probar. Veamos Teok⇒${}_k\Rightarrow$Teok+1${}_{k+1}$. Supongamos t∈Tτk+1−Tτk$t\in T_{k+1}^{\tau }-T_k^{\tau }$ y sean →a,→b$\overrightarrow{a},\overrightarrow{b}$ asignaciones tales que ai=bi$a_i=b_i$, cada vez que xi$x_i$ ocurra en t$t$. Notese que t=f(t1,...,tn)$t=f(t_1,...,t_n)$, con f∈Fn$f\in F_n$,n≥1$n\ge 1$ y t1,...,tn∈Tτk$t_1,...,t_n\in T_k^{\tau }$. Notese que para cada j=1,...,n$j=1,...,n$, tenemos que ai=bi,$a_i=b_i,$ cada vez que xi$x_i$ ocurra en tj$t_j$, lo cual por Teok${}_k$ nos dice que tAj[→a]=tAj[→b], j=1,...,n$$t_j^A\left[\overrightarrow{a}\right]=t_j^A\left[\overrightarrow{b}\right]\text{,}j=1,...,n$$ Se tiene entonces que tA[→a]=i(f)(tA1[→a],...,tAn[→a]) (por def de tA[→a])=i(f)(tA1[→b],...,tAn[→b])=tA[→b] (por def de tA[→b])$$\begin{array}{ccc}{t}^A\left[\overrightarrow{a}\right]& =& i\left(f\right)\left(t_1^A\right[\overrightarrow{a}],...,t_n^A[\overrightarrow{a}\left]\right)\text{(por def de}{t}^A\left[\overrightarrow{a}\right]\text{)}\\ & =& i\left(f\right)\left(t_1^A\right[\overrightarrow{b}],...,t_n^A[\overrightarrow{b}\left]\right)\\ & =& t^A\left[\overrightarrow{b}\right]\text{(por def de}{t}^A\left[\overrightarrow{b}\right]\text{)}\end{array}$$   

7.8.2 La relacion ⊨$\models$

Fijemos un tipo τ$\tau$. A continuacion definiremos matematicamente una relacion "A⊨φ[→a]"$"A\models \phi \left[\overrightarrow{a}\right]"$, donde A$A$ es una estructura de tipo τ$\tau$, →a$\overrightarrow{a}$ es una asignacion de A$A$ y φ∈Fτ$\phi \in F^{\tau }$. Intuitivamente hablando A⊨φ[→a]$A\models \phi \left[\overrightarrow{a}\right]$ significara que la formula φ$\phi$ es verdadera en la estructura A$A$ cuando le asignamos a las variables libres de φ$\phi$ los valores que asigna →a$\overrightarrow{a}$. Escribiremos A⊭φ[→a] para expresar que no se da A⊨φ[→a]. Nuestra definicion matematica sera recursiva y mas abajo explicaremos por que la definicion es precisa o rigurosa matematicamente hablando. Dada una estructura A de tipo τ, una asignacion →a∈AN y a∈A, con ↓ai(→a) denotaremos la asignacion que resulta de reemplazar en →a el i-esimo elemento por a. Ahora si la definicion recursiva:

1. (1) Si φ=(t≡s), entonces

   1. - A⊨φ[→a] si y solo si tA[→a]=sA[→a]

2. (2) Si φ=r(t1,...,tm), entonces

   1. - A⊨φ[→a] si y solo si (tA1[→a],...,tAm[→a])∈i(r)

3. (3) Si φ=(φ1∧φ2), entonces

   1. - A⊨φ[→a] si y solo si A⊨φ1[→a] y A⊨φ2[→a]

4. (4) Si φ=(φ1∨φ2), entonces

   1. - A⊨φ[→a] si y solo si A⊨φ1[→a] o A⊨φ2[→a]

5. (5) Si φ=(φ1→φ2), entonces

   1. - A⊨φ[→a] si y solo si A⊭φ1[→a] o A⊨φ2[→a]

6. (6) Si φ=(φ1↔φ2), entonces

   1. - A⊨φ[→a] si y solo si ya sea se dan A⊨φ1[→a] y A⊨φ2[→a] o se dan A⊭φ1[→a] y A⊭φ2[→a]

7. (7) Si φ=¬φ1, entonces

   1. - A⊨φ[→a] si y solo si A⊭φ1[→a]

8. (8) Si φ=∀xiφ1, entonces

   1. - A⊨φ[→a] si y solo si para cada a∈A, se da que A⊨φ1[↓ai(→a)]

9. (9) Si φ=∃xiφ1, entonces

   1. - A⊨φ[→a] si y solo si hay un a∈A tal que A⊨φ1[↓ai(→a)]

Para ver que la definicion de la relacion “A⊨φ[→a]" es correcta, notemos que en (1) y (2) se dice cuando se da A⊨φ[→a] y cuando no se da A⊨φ[→a] para el caso en que φ es atomica, es decir el caso en que φ∈Fτ0. Las siguientes clausulas nos aseguran que si ya esta definido cuando se da A⊨φ[→a] y cuando no se da A⊨φ[→a] para el caso en que φ∈Fτk, entonces tambien queda definido cuando se da A⊨φ[→a] y cuando no se da A⊨φ[→a] para el caso en que φ∈Fτk+1. De esta forma comensando desde la capa 0 vemos que se va determinando para todas las formulas de las distintas capas cuando vale y cuando no vale la relacion A⊨φ[→a].

Cuando se de A⊨φ[→a] diremos que la estructura A satisface φ en la asignacion →a y en tal caso diremos que φ es verdadera en A para la asignacion →a. Cuando no se de A⊨φ[→a] diremos que la estructura A no satisface φ en la asignacion →a y en tal caso diremos que φ es falsa en A para la asignacion →a. Tambien hablaremos del valor de verdad de φ en A para la asignacion →a el cual sera igual a 1 si se da A⊨φ[→a] y 0 en caso contrario.

Veamos algunos ejemplos. Sea τ el tipo ({uno,doli},{MAS,P},{Her},{(MAS,4),(P,1),(Her,3)}) y sea A=(A,i) la estructura de tipo τ con universo A=R y

1. - i(uno)=9

2. - i(doli)=0

3. - i(MAS) igual a la operacion R4→R(x,y,z,w)→2x+4y

4. - i(P) igual a la operacion R→Rx→5x

5. - i(Her)={(x,y,z)∈R3:x.y.z=9}

Sea →a=(1,2,3,4,5,...). Claramente →a es una asignacion de A. Consideremos los siguientes ejemplos:

1. (E1) Si φ=(MAS(X1,uno,X3,X554)≡P(X3)), entonces ya que

   1. MAS(X1,uno,X3,X554)A[→a]=38

   2. P(X3)A[→a]=125

   tenemos que (1) de la definicion nos dice que A⊨φ[→a] si y solo si 38=125 por lo cual se saca que A⊭φ[→a].

2. (E2) Si φ=¬Her(P(P(X6)),X3,doli), entonces ya que

   1. - P(P(X6))A[→a]=5(56)

   2. - X3A[→a]=3

   3. - doliA[→a]=0

   tenemos que (7) de la definicion nos dice que A⊨φ[→a] si y solo si A⊭Her(P(P(X6)),X3,doli)[→a]. Pero (2) de la definicion nos dice que A⊨Her(P(P(X6)),X3,doli)[→a] si y solo si (5(56),3,0)∈i(Her) ya que no se da que (5(56),3,0)∈i(Her), tenemos que A⊭Her(P(P(X6)),X3,doli)[→a] lo cual nos dice que A⊨φ[→a].

3. (E3) Si φ=∃X3Her(X6,X3,uno), entonces por (9) de la definicion tenemos que

   1. - A⊨φ[→a] sii hay un r∈R tal que A⊨Her(X6,X3,uno)[↓r3(→a)]

   es decir que

   1. - A⊨φ[→a] sii hay un r∈R tal que A⊨Her(X6,X3,uno)[(1,2,r,4,5,6,...)]

   Pero (2) de la definicion nos dice que cualquiera sea r∈R se tiene que

   1. - A⊨Her(X6,X3,uno)[(1,2,r,4,5,6,...)] sii (6,r,9)∈i(Her)

   O sea que obtenemos finalmente que

   1. - A⊨φ[→a] sii hay un r∈R tal que 6.r.9=9

   Lo cual claramente implica que A⊨φ[→a] ya que podemos tomar r=1/6.

4. (E4) Si φ=∀X3((X4≡X3)→∃X6Her(X6,X3,uno)), entonces por (8) de la definicion tenemos que

   1. - A⊨φ[→a] sii para cada r∈R se da que A⊨((X4≡X3)→∃X6Her(X6,X3,uno))[↓r3(→a)]

   es decir que

   1. - A⊨φ[→a] sii para cada r∈R se da que A⊨((X4≡X3)→∃X6Her(X6,X3,uno))[(1,2,r,4,5,6,...)]

   Pero entonces (5) de la definicion nos dice que

   1. - A⊨φ[→a] sii para cada r∈R se da que A⊭(X4≡X3)[(1,2,r,4,5,6,...)] o A⊨∃X6Her(X6,X3,uno))[(1,2,r,4,5,6,...)] O sea que

   2. - A⊨φ[→a] sii para cada r∈R se da que r≠4 o A⊨∃X6Her(X6,X3,uno))[(1,2,r,4,5,6,...)] Es decir que debemos ver cuando se da que A⊨∃X6Her(X6,X3,uno))[(1,2,r,4,5,6,...)]. Por (9) y (2) de la definicion tenemos que cualquiera sea el r∈R se da que

   3. - A⊨∃X6Her(X6,X3,uno))[(1,2,r,4,5,6,...)] sii hay un s∈R tal que s.r.9=9.

   Esto nos dice finalmente que

   1. - A⊨φ[→a] sii para cada r∈R se da que r≠4 o hay un s∈R tal que s.r.9=9

   Pensando un poco esto nos dice que A⊨φ[→a] (separar los casos r=4 y r≠4)

Proof. Probaremos por induccion en k que el lema vale para cada φ∈Fτk. El caso k=0 se desprende del Lema 7.13. Veamos que Teok implica Teok+1. Sea φ∈Fτk+1−Fτk. Hay varios casos:

CASO φ=(φ1∧φ2).

Ya que Li(φi)⊆Li(φ), i=1,2, Teok nos dice que A⊨φi[→a] sii A⊨φi[→b], para i=1,2. Se tiene entonces que A⊨φ[→a]  ⇕ (por (3) en la def de A⊨φ[→a])A⊨φ1[→a] y A⊨φ2[→a]  ⇕ (por Teok)A⊨φ1[→b] y A⊨φ2[→b]  ⇕(por (3) en la def de A⊨φ[→a])A⊨φ[→b]

CASO φ=(φ1∨φ2).

Es completamente similar al anterior.

CASO φ=(φ1→φ2).

Es completamente similar al anterior.

CASO φ=(φ1↔φ2).

Es completamente similar al anterior.

CASO φ=¬φ1.

Es completamente similar al anterior.

CASO φ=∀xjφ1.

Supongamos A⊨φ[→a]. Entonces por (8) en la def de A⊨φ[→a] se tiene que A⊨φ1[↓aj(→a)], para todo a∈A. Notese que ↓aj(→a) y ↓aj(→b) coinciden en toda xi∈Li(φ1) ya que Li(φ1)⊆Li(φ)∪{xj}. O sea que por Teok se tiene que A⊨φ1[↓aj(→b)], para todo a∈A, lo cual por (8) en la def de A⊨φ[→a] nos dice que A⊨φ[→b]. La prueba de que A⊨φ[→b] implica que A⊨φ[→a] es similar.

CASO φ=∃xjφ1.

Es similar al anterior.  

En virtud del corolario anterior tenemos que el valor de verdad de una sentencia φ en una estructura dada A para una asignacion →a no depende de →a, es decir este valor es ya sea 1 para todas las asignaciones o 0 para todas las asignaciones. En el primer caso diremos que φ es verdadera en A (y escribiremos A⊨φ) y en el segundo caso diremos que φ es falsa en A (y escribiremos A⊭φ)

Una sentencia de tipo τ sera llamada universalmente valida si es verdadera en cada modelo de tipo τ.

El valor de verdad es “efectivamente computable” en el caso finito

Supongamos que τ es finito en el sentido que los conjuntos C,F y R son finitos. Y supongamos que tenemos dada una estructura A de tipo τ tal que A es finito. Por supuesto, podemos ponerles nombre a los elementos de A de manera que los podamos manejar dentro de una computadora y ademas notese que una ves puesto estos nombres a los elementos de A, tambien podemos manejar dentro de nuestra computadora a las interpretaciones de los nombres de cte, funcion y relacion en A (por ejemplo si f∈F2 podemos representar a fA con una tabla de tres columnas. Entonces el lector no tendra problema en imaginar como haria un programa (en cualquier lenguaje de los actuales) con las siguientes caracteristicas:

1. Datos de entrada: Una formula φ de tipo τ y elementos a1,...,an de A donde n es tal que Li(φ)⊆{x1,...,xn}

2. Si A⊨φ[a1,...,an,a1,a1,a1,a1,...] entonces el programa se detiene y da como salida el Booleano 1

3. Si A⊭φ[a1,...,an,a1,a1,a1,a1,...] entonces el programa se detiene y da como salida el Booleano 0