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 \(\mathbf{A}=(A,i)\) una estructura de tipo \(\tau\). Una asignacion de \(\mathbf{A}\) sera un elemento de \(A^{\mathbf{N}}=\{\)infinituplas de elementos de \(A\}\). Si \(\vec{a}=(a_{1},a_{2},...)\) es una asignacion, entonces diremos que \(a_{j}\) es el valor que \(\vec{a}\) le asigna a la variable \(x_{j}\).

Dada una estructura \(\mathbf{A}\) de tipo \(\tau\), un termino \(t\in T^{\tau}\) y una asignacion \(\vec{a}=(a_{1},a_{2},...)\in A^{\mathbf{N}}\) definamos recursivamente \(t^{\mathbf{A}}[\vec{a}]\) de la siguiente manera

1. adhocprefix(1)adhocsufix Si \(t=x_{i}\in Var\), entonces \(t^{\mathbf{A}}[\vec{a}]=a_{i}\)

2. adhocprefix(2)adhocsufix Si \(t=c\in\mathcal{C}\), entonces \(t^{\mathbf{A}}[\vec{a}]=i(c)\)

3. adhocprefix(3)adhocsufix Si \(t=f(t_{1},...,t_{n})\), con \(f\in\mathcal{F}_{n},\;n\geq1\) y \(t_{1},...,t_{n}\in T^{\tau}\), entonces \(t^{\mathbf{A}}[\vec{a}]=i(f)(t_{1}^{\mathbf{A}}[\vec{a}],...,t_{n}^{\mathbf{A}}[\vec{a}])\)

El elemento \(t^{\mathbf{A}}[\vec{a}]\) sera llamado el valor de \(t\) en la estructura \(\mathbf{A}\) para la asignacion \(\vec{a}\).

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

1. adhocprefix-adhocsufix \(i(\mathrm{uno})=9\)

2. adhocprefix-adhocsufix \(i(\mathrm{doli})=0\)

3. adhocprefix-adhocsufix \(i(\mathrm{MAS})\) igual a la operacion \[\begin{array}{rcl} \mathbf{R}^{4} & \rightarrow & \mathbf{R}\\ (x,y,z,w) & \rightarrow & 2x+4y \end{array}\]

4. adhocprefix-adhocsufix \(i(\mathrm{P})\) igual a la operacion \[\begin{array}{rcl} \mathbf{R} & \rightarrow & \mathbf{R}\\ x & \rightarrow & 5^{x} \end{array}\]

5. adhocprefix-adhocsufix \(i(\mathrm{Her})=\{(x,y,z)\in\mathbf{R}^{3}:x.y.z=9\}\)

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

1. Si \(t=\mathsf{X}\mathit{55}\mathbf{4}\), entonces \(t^{\mathbf{A}}[\vec{a}]=\mathsf{X}\mathit{55}\mathbf{4}^{\mathbf{A}}[\vec{a}]=554\) (por (1) de la definicion recursiva de \(t^{\mathbf{A}}[\vec{a}]\))

2. Si \(t=\mathrm{uno}\), entonces \(t^{\mathbf{A}}[\vec{a}]=\mathrm{uno}^{\mathbf{A}}[\vec{a}]=9\) (por (2) de la definicion recursiva de \(t^{\mathbf{A}}[\vec{a}]\))

3. Si \(t=\mathrm{P}(\mathsf{X}\mathbf{3})\), entonces \[\begin{aligned} t^{\mathbf{A}}[\vec{a}] & =\mathrm{P}(\mathsf{X}\mathbf{3})^{\mathbf{A}}[\vec{a}]\\ & =i(\mathrm{P})(\mathsf{X}\mathbf{3}^{\mathbf{A}}[\vec{a}])\text{ (por (3) de la definicion de }t^{\mathbf{A}}[\vec{a}]\text{)}\\ & =i(\mathrm{P})(3)\\ & =5^{3}=125 \end{aligned}\]

4. Si \(t=\mathrm{MAS}(\mathsf{X}\mathbf{1},\mathrm{uno},\mathsf{X}\mathbf{3},\mathsf{X}\mathit{55}\mathbf{4})\), entonces \[\begin{aligned} t^{\mathbf{A}}[\vec{a}] & =\mathrm{MAS}(\mathsf{X}\mathbf{1},\mathrm{uno},\mathsf{X}\mathbf{3},\mathsf{X}\mathit{55}\mathbf{4})^{\mathbf{A}}[\vec{a}]\\ & =i(\mathrm{MAS})(\mathsf{X}\mathbf{1}^{\mathbf{A}}[\vec{a}],\mathrm{uno}^{\mathbf{A}}[\vec{a}],\mathsf{X}\mathbf{3}^{\mathbf{A}}[\vec{a}],\mathsf{X}\mathit{55}\mathbf{4}^{\mathbf{A}}[\vec{a}])\\ & =i(\mathrm{MAS})(1,9,3,554)\\ & =2.1+4.9=38 \end{aligned}\]

Proof. Sea

1. adhocprefix-adhocsufix Teo\(_{k}\): El lema vale para \(t\in T_{k}^{\tau}\).

Teo\(_{0}\) es facil de probar. Veamos Teo\(_{k}\Rightarrow\)Teo\(_{k+1}\). Supongamos \(t\in T_{k+1}^{\tau}-T_{k}^{\tau}\) y sean \(\vec{a},\vec{b}\) asignaciones tales que \(a_{i}=b_{i}\), cada vez que \(x_{i}\) ocurra en \(t\). Notese que \(t=f(t_{1},...,t_{n})\), con \(f\in\mathcal{F}_{n}\),\(\;n\geq1\) y \(t_{1},...,t_{n}\in T_{k}^{\tau}\). Notese que para cada \(j=1,...,n\), tenemos que \(a_{i}=b_{i},\) cada vez que \(x_{i}\) ocurra en \(t_{j}\), lo cual por Teo\(_{k}\) nos dice que \[t_{j}^{\mathbf{A}}[\vec{a}]=t_{j}^{\mathbf{A}}[\vec{b}]\text{, }j=1,...,n\] Se tiene entonces que \[\begin{array}{ccl} t^{\mathbf{A}}[\vec{a}] & = & i(f)(t_{1}^{\mathbf{A}}[\vec{a}],...,t_{n}^{\mathbf{A}}[\vec{a}])\text{ (por def de }t^{\mathbf{A}}[\vec{a}]\text{)}\\ & = & i(f)(t_{1}^{\mathbf{A}}[\vec{b}],...,t_{n}^{\mathbf{A}}[\vec{b}])\\ & = & t^{\mathbf{A}}[\vec{b}]\text{ (por def de }t^{\mathbf{A}}[\vec{b}]\text{)} \end{array}\]   

7.8.2 La relacion \(\models\)

Fijemos un tipo \(\tau\). A continuacion definiremos matematicamente una relacion \(\mathbf{"A}\models\varphi[\vec{a}]"\), donde \(\mathbf{A}\) es una estructura de tipo \(\tau\), \(\vec{a}\) es una asignacion de \(\mathbf{A}\) y \(\varphi\in F^{\tau}\). Intuitivamente hablando \(\mathbf{A}\models\varphi[\vec{a}]\) significara que la formula \(\varphi\) es verdadera en la estructura \(\mathbf{A}\) cuando le asignamos a las variables libres de \(\varphi\) los valores que asigna \(\vec{a}\). Escribiremos \(\mathbf{A}\not\models\varphi[\vec{a}]\) para expresar que no se da \(\mathbf{A}\models\varphi[\vec{a}]\). Nuestra definicion matematica sera recursiva y mas abajo explicaremos por que la definicion es precisa o rigurosa matematicamente hablando. Dada una estructura \(\mathbf{A}\) de tipo \(\tau\), una asignacion \(\vec{a}\in A^{\mathbf{N}}\) y \(a\in A\), con \(\downarrow_{i}^{a}(\vec{a})\) denotaremos la asignacion que resulta de reemplazar en \(\vec{a}\) el \(i\)-esimo elemento por \(a\). Ahora si la definicion recursiva:

1. adhocprefix(1)adhocsufix Si \(\varphi=(t\equiv s),\) entonces

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si \(t^{\mathbf{A}}[\vec{a}]=s^{\mathbf{A}}[\vec{a}]\)

2. adhocprefix(2)adhocsufix Si \(\varphi=r(t_{1},...,t_{m})\), entonces

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si \((t_{1}^{\mathbf{A}}[\vec{a}],...,t_{m}^{\mathbf{A}}[\vec{a}])\in i(r)\)

3. adhocprefix(3)adhocsufix Si \(\varphi=(\varphi_{1}\wedge\varphi_{2})\), entonces

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si \(\mathbf{A}\models\varphi_{1}[\vec{a}]\) y \(\mathbf{A}\models\varphi_{2}[\vec{a}]\)

4. adhocprefix(4)adhocsufix Si \(\varphi=(\varphi_{1}\vee\varphi_{2})\), entonces

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si \(\mathbf{A}\models\varphi_{1}[\vec{a}]\) o \(\mathbf{A}\models\varphi_{2}[\vec{a}]\)

5. adhocprefix(5)adhocsufix Si \(\varphi=(\varphi_{1}\rightarrow\varphi_{2})\), entonces

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si \(\mathbf{A}\not\models\varphi_{1}[\vec{a}]\) o \(\mathbf{A}\models\varphi_{2}[\vec{a}]\)

6. adhocprefix(6)adhocsufix Si \(\varphi=(\varphi_{1}\leftrightarrow\varphi_{2})\), entonces

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si ya sea se dan \(\mathbf{A}\models\varphi_{1}[\vec{a}]\) y \(\mathbf{A}\models\varphi_{2}[\vec{a}]\) o se dan \(\mathbf{A}\not\models\varphi_{1}[\vec{a}]\) y \(\mathbf{A}\not\models\varphi_{2}[\vec{a}]\)

7. adhocprefix(7)adhocsufix Si \(\varphi=\lnot\varphi_{1},\) entonces

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si \(\mathbf{A}\not\models\varphi_{1}[\vec{a}]\)

8. adhocprefix(8)adhocsufix Si \(\varphi=\forall x_{i}\varphi_{1}\), entonces

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si para cada \(a\in A\), se da que \(\mathbf{A}\models\varphi_{1}[\downarrow_{i}^{a}(\vec{a})]\)

9. adhocprefix(9)adhocsufix Si \(\varphi=\exists x_{i}\varphi_{1}\), entonces

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si hay un \(a\in A\) tal que \(\mathbf{A}\models\varphi_{1}[\downarrow_{i}^{a}(\vec{a})]\)

Para ver que la definicion de la relacion “\(\mathbf{A}\models\varphi[\vec{a}]"\) es correcta, notemos que en (1) y (2) se dice cuando se da \(\mathbf{A}\models\varphi[\vec{a}]\) y cuando no se da \(\mathbf{A}\models\varphi[\vec{a}]\) para el caso en que \(\varphi\) es atomica, es decir el caso en que \(\varphi\in F_{0}^{\tau}\). Las siguientes clausulas nos aseguran que si ya esta definido cuando se da \(\mathbf{A}\models\varphi[\vec{a}]\) y cuando no se da \(\mathbf{A}\models\varphi[\vec{a}]\) para el caso en que \(\varphi\in F_{k}^{\tau}\), entonces tambien queda definido cuando se da \(\mathbf{A}\models\varphi[\vec{a}]\) y cuando no se da \(\mathbf{A}\models\varphi[\vec{a}]\) para el caso en que \(\varphi\in F_{k+1}^{\tau}\). 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 \(\mathbf{A}\models\varphi[\vec{a}]\).

Cuando se de \(\mathbf{A}\models\varphi[\vec{a}]\) diremos que la estructura \(\mathbf{A}\) satisface \(\varphi\) en la asignacion \(\vec{a}\) y en tal caso diremos que \(\varphi\) es verdadera en \(\mathbf{A}\) para la asignacion \(\vec{a}\). Cuando no se de \(\mathbf{A}\models\varphi[\vec{a}]\) diremos que la estructura \(\mathbf{A}\) no satisface \(\varphi\) en la asignacion \(\vec{a}\) y en tal caso diremos que \(\varphi\) es falsa en \(\mathbf{A}\) para la asignacion \(\vec{a}\). Tambien hablaremos del valor de verdad de \(\varphi\) en \(\mathbf{A}\) para la asignacion \(\vec{a}\) el cual sera igual a \(1\) si se da \(\mathbf{A}\models\varphi[\vec{a}]\) y \(0\) en caso contrario.

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

1. adhocprefix-adhocsufix \(i(\mathrm{uno})=9\)

2. adhocprefix-adhocsufix \(i(\mathrm{doli})=0\)

3. adhocprefix-adhocsufix \(i(\mathrm{MAS})\) igual a la operacion \[\begin{array}{rcl} \mathbf{R}^{4} & \rightarrow & \mathbf{R}\\ (x,y,z,w) & \rightarrow & 2x+4y \end{array}\]

4. adhocprefix-adhocsufix \(i(\mathrm{P})\) igual a la operacion \[\begin{array}{rcl} \mathbf{R} & \rightarrow & \mathbf{R}\\ x & \rightarrow & 5^{x} \end{array}\]

5. adhocprefix-adhocsufix \(i(\mathrm{Her})=\{(x,y,z)\in\mathbf{R}^{3}:x.y.z=9\}\)

Sea \(\vec{a}=(1,2,3,4,5,...)\). Claramente \(\vec{a}\) es una asignacion de \(\mathbf{A}\). Consideremos los siguientes ejemplos:

1. adhocprefix(E1)adhocsufix Si \(\varphi=(\mathrm{MAS}(\mathsf{X}\mathbf{1},\mathrm{uno},\mathsf{X}\mathbf{3},\mathsf{X}\mathit{55}\mathbf{4})\equiv\mathrm{P}(\mathsf{X}\mathbf{3}))\), entonces ya que

   1. \(\mathrm{MAS}(\mathsf{X}\mathbf{1},\mathrm{uno},\mathsf{X}\mathbf{3},\mathsf{X}\mathit{55}\mathbf{4})^{\mathbf{A}}[\vec{a}]=38\)

   2. \(\mathrm{P}(\mathsf{X}\mathbf{3})^{\mathbf{A}}[\vec{a}]=125\)

   tenemos que (1) de la definicion nos dice que \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si \(38=125\) por lo cual se saca que \(\mathbf{A}\not\models\varphi[\vec{a}]\).

2. adhocprefix(E2)adhocsufix Si \(\varphi=\lnot\mathrm{Her}(\mathrm{P}(\mathrm{P}(\mathsf{X}\mathbf{6})),\mathsf{X}\mathbf{3},\mathrm{doli})\), entonces ya que

   1. adhocprefix-adhocsufix \(\mathrm{P}(\mathrm{P}(\mathsf{X}\mathbf{6}))^{\mathbf{A}}[\vec{a}]=5^{(5^{6})}\)

   2. adhocprefix-adhocsufix \(\mathsf{X}\mathbf{3}^{\mathbf{A}}[\vec{a}]=3\)

   3. adhocprefix-adhocsufix \(\mathrm{doli}^{\mathbf{A}}[\vec{a}]=0\)

   tenemos que (7) de la definicion nos dice que \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si \(\mathbf{A}\not\models\mathrm{Her}(\mathrm{P}(\mathrm{P}(\mathsf{X}\mathbf{6})),\mathsf{X}\mathbf{3},\mathrm{doli})[\vec{a}]\). Pero (2) de la definicion nos dice que \(\mathbf{A}\models\mathrm{Her}(\mathrm{P}(\mathrm{P}(\mathsf{X}\mathbf{6})),\mathsf{X}\mathbf{3},\mathrm{doli})[\vec{a}]\) si y solo si \((5^{(5^{6})},3,0)\in i(\mathrm{Her})\) ya que no se da que \((5^{(5^{6})},3,0)\in i(\mathrm{Her})\), tenemos que \(\mathbf{A}\not\models\mathrm{Her}(\mathrm{P}(\mathrm{P}(\mathsf{X}\mathbf{6})),\mathsf{X}\mathbf{3},\mathrm{doli})[\vec{a}]\) lo cual nos dice que \(\mathbf{A}\models\varphi[\vec{a}]\).

3. adhocprefix(E3)adhocsufix Si \(\varphi=\exists\mathsf{X}\mathbf{3}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{3},\mathrm{uno})\), entonces por (9) de la definicion tenemos que

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) sii hay un \(r\in\mathbf{R}\) tal que \(\mathbf{A}\models\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{3},\mathrm{uno})[\downarrow_{3}^{r}(\vec{a})]\)

   es decir que

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) sii hay un \(r\in\mathbf{R}\) tal que \(\mathbf{A}\models\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{3},\mathrm{uno})[(1,2,r,4,5,6,...)]\)

   Pero (2) de la definicion nos dice que cualquiera sea \(r\in\mathbf{R}\) se tiene que

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{3},\mathrm{uno})[(1,2,r,4,5,6,...)]\) sii \((6,r,9)\in i(\mathrm{Her})\)

   O sea que obtenemos finalmente que

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) sii hay un \(r\in\mathbf{R}\) tal que \(6.r.9=9\)

   Lo cual claramente implica que \(\mathbf{A}\models\varphi[\vec{a}]\) ya que podemos tomar \(r=1/6\).

4. adhocprefix(E4)adhocsufix Si \(\varphi=\forall\mathsf{X}\mathbf{3(}(\mathsf{X}\mathbf{4}\equiv\mathsf{X}\mathbf{3})\rightarrow\exists\mathsf{X}\mathbf{6}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{3},\mathrm{uno}))\), entonces por (8) de la definicion tenemos que

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) sii para cada \(r\in\mathbf{R}\) se da que \[\mathbf{A}\models\mathbf{(}(\mathsf{X}\mathbf{4}\equiv\mathsf{X}\mathbf{3})\rightarrow\exists\mathsf{X}\mathbf{6}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{3},\mathrm{uno}))[\downarrow_{3}^{r}(\vec{a})]\]

   es decir que

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) sii para cada \(r\in\mathbf{R}\) se da que \[\mathbf{A}\models\mathbf{(}(\mathsf{X}\mathbf{4}\equiv\mathsf{X}\mathbf{3})\rightarrow\exists\mathsf{X}\mathbf{6}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{3},\mathrm{uno}))[(1,2,r,4,5,6,...)]\]

   Pero entonces (5) de la definicion nos dice que

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) sii para cada \(r\in\mathbf{R}\) se da que \[\mathbf{A}\not\models(\mathsf{X}\mathbf{4}\equiv\mathsf{X}\mathbf{3})[(1,2,r,4,5,6,...)]\text{ o }\mathbf{A}\models\exists\mathsf{X}\mathbf{6}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{3},\mathrm{uno}))[(1,2,r,4,5,6,...)]\] O sea que

   2. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) sii para cada \(r\in\mathbf{R}\) se da que \[r\neq4\text{ o }\mathbf{A}\models\exists\mathsf{X}\mathbf{6}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{3},\mathrm{uno}))[(1,2,r,4,5,6,...)]\] Es decir que debemos ver cuando se da que \(\mathbf{A}\models\exists\mathsf{X}\mathbf{6}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{3},\mathrm{uno}))[(1,2,r,4,5,6,...)]\). Por (9) y (2) de la definicion tenemos que cualquiera sea el \(r\in\mathbf{R}\) se da que

   3. adhocprefix-adhocsufix \(\mathbf{A}\models\exists\mathsf{X}\mathbf{6}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{3},\mathrm{uno}))[(1,2,r,4,5,6,...)]\) sii hay un \(s\in\mathbf{R}\) tal que \(s.r.9=9\).

   Esto nos dice finalmente que

   1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) sii para cada \(r\in\mathbf{R}\) se da que \[r\neq4\text{ o hay un }s\in\mathbf{R}\text{ tal que }s.r.9=9\]

   Pensando un poco esto nos dice que \(\mathbf{A}\models\varphi[\vec{a}]\) (separar los casos \(r=4\) y \(r\neq4\))

Proof. Probaremos por induccion en \(k\) que el lema vale para cada \(\varphi\in F_{k}^{\tau}\). El caso \(k=0\) se desprende del Lema 7.14. Veamos que Teo\(_{k}\) implica Teo\(_{k+1}.\) Sea \(\varphi\in F_{k+1}^{\tau}-F_{k}^{\tau}.\) Hay varios casos:

CASO \(\varphi=(\varphi_{1}\wedge\varphi_{2})\).

Ya que \(Li(\varphi_{i})\subseteq Li(\varphi)\), \(i=1,2\), Teo\(_{k}\) nos dice que \(\mathbf{A}\models\varphi_{i}[\vec{a}]\) sii \(\mathbf{A}\models\varphi_{i}[\vec{b}]\), para \(i=1,2\). Se tiene entonces que \[\begin{array}{l} \mathbf{A}\models\varphi[\vec{a}]\\ \ \ \Updownarrow\text{ (por (3) en la def de }\mathbf{A}\models\varphi[\vec{a}]\text{)}\\ \mathbf{A}\models\varphi_{1}[\vec{a}]\text{ y }\mathbf{A}\models\varphi_{2}[\vec{a}]\\ \ \ \Updownarrow\text{ (por Teo}_{k}\text{)}\\ \mathbf{A}\models\varphi_{1}[\vec{b}]\text{ y }\mathbf{A}\models\varphi_{2}[\vec{b}]\\ \ \ \Updownarrow\text{(por (3) en la def de }\mathbf{A}\models\varphi[\vec{a}]\text{)}\\ \mathbf{A}\models\varphi[\vec{b}] \end{array}\]

CASO \(\varphi=(\varphi_{1}\vee\varphi_{2})\).

Es completamente similar al anterior.

CASO \(\varphi=(\varphi_{1}\rightarrow\varphi_{2})\).

Es completamente similar al anterior.

CASO \(\varphi=(\varphi_{1}\leftrightarrow\varphi_{2})\).

Es completamente similar al anterior.

CASO \(\varphi=\lnot\varphi_{1}.\)

Es completamente similar al anterior.

CASO \(\varphi=\forall x_{j}\varphi_{1}.\)

Supongamos \(\mathbf{A}\models\varphi[\vec{a}]\). Entonces por (8) en la def de \(\mathbf{A}\models\varphi[\vec{a}]\) se tiene que \(\mathbf{A}\models\varphi_{1}[\downarrow_{j}^{a}(\vec{a})]\), para todo \(a\in A\). Notese que \(\downarrow_{j}^{a}(\vec{a})\) y \(\downarrow_{j}^{a}(\vec{b})\) coinciden en toda \(x_{i}\in Li(\varphi_{1})\) ya que \(Li(\varphi_{1})\subseteq Li(\varphi)\cup\{x_{j}\}\). O sea que por Teo\(_{k}\) se tiene que \(\mathbf{A}\models\varphi_{1}[\downarrow_{j}^{a}(\vec{b})]\), para todo \(a\in A\), lo cual por (8) en la def de \(\mathbf{A}\models\varphi[\vec{a}]\) nos dice que \(\mathbf{A}\models\varphi[\vec{b}]\). La prueba de que \(\mathbf{A}\models\varphi[\vec{b}]\) implica que \(\mathbf{A}\models\varphi[\vec{a}]\) es similar.

CASO \(\varphi=\exists x_{j}\varphi_{1}\).

Es similar al anterior.  

En virtud del corolario anterior tenemos que el valor de verdad de una sentencia \(\varphi\) en una estructura dada \(\mathbf{A}\) para una asignacion \(\vec{a}\) no depende de \(\vec{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 \(\varphi\) es verdadera en \(\mathbf{A}\) (y escribiremos \(\mathbf{A}\models\varphi\)) y en el segundo caso diremos que \(\varphi\) es falsa en \(\mathbf{A}\) (y escribiremos \(\mathbf{A}\not\models\varphi\))

Una sentencia de tipo \(\tau\) sera llamada universalmente valida si es verdadera en cada modelo de tipo \(\tau\).

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

Supongamos que \(\tau\) es finito en el sentido que los conjuntos \(\mathcal{C},\mathcal{F}\text{ y }\mathcal{R}\) son finitos. Y supongamos que tenemos dada una estructura \(\mathbf{A}\) de tipo \(\tau\) 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 \(\mathbf{A}\) (por ejemplo si \(f\in\mathcal{F}_{2}\) podemos representar a \(f^{\boldsymbol{\mathbf{A}}}\) 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 \(\varphi\) de tipo \(\tau\) y elementos \(a_{1},...,a_{n}\) de \(A\) donde \(n\) es tal que \(Li(\varphi)\subseteq\{x_{1},...,x_{n}\}\)

2. Si \(\mathbf{A}\models\varphi[a_{1},...,a_{n},a_{1},a_{1},a_{1},a_{1},...]\) entonces el programa se detiene y da como salida el Booleano \(1\)

3. Si \(\mathbf{A}\not\models\varphi[a_{1},...,a_{n},a_{1},a_{1},a_{1},a_{1},...]\) entonces el programa se detiene y da como salida el Booleano \(0\)

Esto realmente es una consecuencia muy interesante de haber dado un modelo matematico de las formulas elementales y sus valores de verdad, resulta que ahora este programa nos esta permitiendo calcular sin pensar el valor de verdad de una formula en una estructura finita! Por supuesto esto tiene sentido si la nocion matematica de valor de verdad es realmente un modelo adecuado de nuestra idea intuitiva de valor de verdad. Pero ...

Hemos creado un mounstro?

Que tal si nuestro modelo matematico de valor de verdad no es del todo satisfactorio, es decir que tal si el programa anterior en algun caso da como salida el Booleano \(1\) y para nosotros la formula de entrada era falsa en la asignacion de entrada. En ese caso nos deberiamos sentir identificados con el Dr Frankenstein, el cual quizo hacer un humano pero su creacion tenia detalles ....

Veamos un ejemplo feo:

1. Sea \(\tau=(\{c\},\emptyset,\{\mathrm{P1}^{1},\mathrm{P2}^{1},\mathrm{R}^{1}\},a)\). Consideremos la sentencia \(\mu=(((\mathrm{P1}(c)\wedge\mathrm{P2}(c))\rightarrow\mathrm{R}(c)))\rightarrow((\mathrm{P1}(c)\rightarrow\mathrm{R}(c))\vee(\mathrm{P2}(c)\rightarrow\mathrm{R}(c))))\). Notese que esta sentencia nos dice que si tenemos que \(\mathrm{P1}(c)\text{ y }\mathrm{P2}(c)\text{ implican }\mathrm{R}(c)\), entonces ya sea se da que \(\mathrm{P1}(c)\text{ implica }\mathrm{R}(c)\) o que \(\mathrm{P2}(c)\text{ implica }\mathrm{R}(c)\). Esto intuitivamente hablando no parece cierto independientemente de en que estructura estemos pensando ya que la intuicion nos dice que podria hacer falta que \(c\) cumpla ambas propiedades (\(\mathrm{P1}\text{ y }\mathrm{P2}\)) para asegurar que entonces debe cumplir \(\mathrm{R}\) y que ninguna de las dos propiedades por separado asegure que se cumple \(\mathrm{R}\). Sin enbargo una facil inspeccion nos permite ver que \(\mathbf{A}\models\mu[\vec{a}]\), cualesquiera sea la estructura \(\mathbf{A}\) y la asignacion \(\vec{a}\in A^{\mathbf{N}}\) (dejamos este chequeo para el lector, aplicando la definicion de “\(\mathbf{A}\models\varphi[\vec{a}]\)”).

Este ejemplo nos hace pensar que quizas nuestro modelo no sea tan bueno. Pero la verdad es que es muy bueno y en este caso, en el que no parece modelizar bien, la explicacion tiene que ver con el hecho que en general en la matematica real no le asignamos valor de verdad a una implicacion de dos sentencias concretas ya verdaderas o falsas. Esto nos hace pensar las implicaciones de \(\mu\) de una forma “parametrizada” lo cual es incorrecto ya que para una estructura dada \(c\) esta fijo. Solo resta decir que son casos marginales, estos en los cuales se rompe la intuicion, y en general no aparecen en la escritura real de los matematicos. Mas aun, quisas deberiamos pensar que el modelo matematico dado nos enseña a pensar de una manera mas madura este tipo de casos que nunca ocurren en la matematica real.

7.8.3 Equivalencia de formulas

Dadas \(\varphi,\psi\in F^{\tau}\) diremos que \(\varphi\) y \(\psi\) son equivalentes cuando se de la siguiente condicion

1. adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si \(\mathbf{A}\models\psi[\vec{a}]\), para cada modelo de tipo \(\tau\), \(\mathbf{A}\) y cada \(\vec{a}\in A^{\mathbf{N}}\)

Escribiremos \(\varphi\thicksim\psi\) cuando \(\varphi\) y \(\psi\) sean equivalentes. Notese que \[\{(\varphi,\psi)\in F^{\tau}:\varphi\thicksim\psi\}\] es una relacion de equivalencia sobre \(F^{\tau}\).

Proof. (a) Tenemos que \[\begin{array}{l} \gamma\thicksim\psi\\ \ \ \Updownarrow\text{ (por (6) de la def de}\models\text{)}\\ \mathbf{A}\models(\gamma\leftrightarrow\psi)[\vec{a}]\text{, para todo }\mathbf{A}\text{ y toda }\vec{a}\in A^{\mathbf{N}}\\ \ \ \Updownarrow\\ \mathbf{A}\models(\gamma\leftrightarrow\psi)[\downarrow_{i_{n}}^{a}(\vec{a})]\text{, para todo }\mathbf{A}\text{, }a\in A\text{ y toda }\vec{a}\in A^{\mathbf{N}}\\ \ \ \Updownarrow(\text{por (8) de la def de}\models)\\ \mathbf{A}\models\forall x_{i_{n}}(\gamma\leftrightarrow\psi)[\vec{a}]\text{, para todo }\mathbf{A}\text{ y toda }\vec{a}\in A^{\mathbf{N}}\\ \ \ \Updownarrow\\ \mathbf{A}\models\forall x_{i_{n}}(\gamma\leftrightarrow\psi)[\downarrow_{i_{n-1}}^{a}(\vec{a})]\text{, para todo }\mathbf{A}\text{, }a\in A\text{ y toda }\vec{a}\in A^{\mathbf{N}}\\ \ \ \Updownarrow\text{ (por (8) de la def de}\models\text{)}\\ \mathbf{A}\models\forall x_{i_{n-1}}\forall x_{i_{n}}(\gamma\leftrightarrow\psi)[\vec{a}]\text{, para todo }\mathbf{A}\text{ y toda }\vec{a}\in A^{\mathbf{N}}\\ \ \ \Updownarrow\\ \ \ \ \ \vdots\\ \ \ \Updownarrow\\ \mathbf{A}\models\forall x_{i_{1}}...\forall x_{i_{n}}(\gamma\leftrightarrow\psi)[\vec{a}]\text{, para todo }\mathbf{A}\text{ y toda }\vec{a}\in A^{\mathbf{N}}\\ \ \ \Updownarrow\\ \forall x_{i_{1}}...\forall x_{i_{n}}(\gamma\leftrightarrow\psi)\text{ es universalmente valida} \end{array}\]

(b) Es dejado al lector.

(c) Por induccion en el \(k\) tal que \(\alpha\in F_{k}^{\tau}\).