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

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 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.13. 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\).

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}\).

1. adhocprefix(a)adhocsufix Si \(Li(\phi)\cup Li(\psi)\subseteq\{x_{i_{1}},...,x_{i_{n}}\},\) entonces \(\phi\thicksim\psi\) si y solo si la sentencia \(\forall x_{i_{1}}...\forall x_{i_{n}}(\phi\leftrightarrow\psi)\) es universalmente valida.

2. adhocprefix(b)adhocsufix Si \(\phi_{i}\thicksim\psi_{i},\) \(i=1,2,\) entonces \(\lnot\phi_{1}\thicksim\lnot\psi_{1},\) \((\phi_{1}\eta\phi_{2})\thicksim(\psi_{1}\eta\psi_{2})\) y \(Qv\phi_{1}\thicksim Qv\psi_{1}.\)

3. adhocprefix(c)adhocsufix Si \(\phi\thicksim\psi\) y \(\alpha^{\prime}\) es el resultado de reemplazar en una formula \(\alpha\) algunas (posiblemente \(0\)) ocurrencias de \(\phi\) por \(\psi\), entonces \(\alpha\thicksim\alpha^{\prime}.\)

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}\).