7.9 Modelo matemático del valor de verdad de una fórmula

En esta sección daremos una definición matemática que modeliza la idea intuitiva de cuando una fórmula de tipo \(\tau\) es verdadera en una estructura dada para una asignación de elementos a las variables libres de dicha fórmula. Esto corresponde al punto (2) del Programa de Lógica Matemática.

7.9.1 El valor de un término en una estructura

Sea \(\mathbf{A}=(A,i)\) una estructura de tipo \(\tau\). Una asignación de \(\mathbf{A}\) será un elemento de \(A^{\mathbf{N}}=\{\)infinituplas de elementos de \(A\}\). Si \(\vec{a}=(a_{1},a_{2},...)\) es una asignación, 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 término \(t\in T^{\tau}\) y una asignación \(\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}]\) será llamado el valor de \(t\) en la estructura \(\mathbf{A}\) para la asignación \(\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 operación \[\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 operación \[\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 asignación de \(\mathbf{A}\). Se tiene que:

1. adhocprefix-adhocsufix 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 definición recursiva de \(t^{\mathbf{A}}[\vec{a}]\))

2. adhocprefix-adhocsufix Si \(t=\mathrm{uno}\), entonces \(t^{\mathbf{A}}[\vec{a}]=\mathrm{uno}^{\mathbf{A}}[\vec{a}]=9\) (por (2) de la definición recursiva de \(t^{\mathbf{A}}[\vec{a}]\))

3. adhocprefix-adhocsufix 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. adhocprefix-adhocsufix 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. Usaremos la Regla de Inducción desde 0. Para cada \(k\in\omega\) sea \(\mathrm{Enu}_{k}\) el siguiente enunciado:

1. adhocprefix\(\mathrm{Enu}_{k}\):adhocsufix Sea \(\mathbf{A}\) una estructura de tipo \(\tau\) y sea \(t\in T_{k}^{\tau}\). Supongamos que \(\vec{a},\vec{b}\) son asignaciones tales que \(a_{i}=b_{i},\) cada vez que \(x_{i}\) ocurra en \(t\). Entonces \(t^{\mathbf{A}}[\vec{a}]=t^{\mathbf{A}}[\vec{b}]\).

Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(0\).

Prueba de que \(\mathrm{Enu}_{0}\) es verdadero. Fácil y dejado al lector.

Prueba de que si \(\mathrm{Enu}_{k}\) es verdadero entonces \(\mathrm{Enu}_{k+1}\) lo es. Supongamos entonces que vale \(\mathrm{Enu}_{k}\). Sea \(\mathbf{A}\) una estructura de tipo \(\tau\), sea \(t\in T_{k+1}^{\tau}\) y supongamos que \(\vec{a},\vec{b}\) son asignaciones tales que \(a_{i}=b_{i},\) cada vez que \(x_{i}\) ocurra en \(t\). Por definición de \(T_{k+1}^{\tau}\), hay dos casos.

Caso \(t\in T_{k}^{\tau}\). Ya que es verdadero \(\mathrm{Enu}_{k}\), es claro que se cumple la conclusión de \(\mathrm{Enu}_{k+1}\).

Caso \(t=f(t_{1},...,t_{n})\), con \(f\in\mathcal{F}_{n}\), \(n\geq1\) y \(t_{1},...,t_{n}\in T_{k}^{\tau}\). Nótese que para cada \(j=1,...,n\), tenemos que \(a_{i}=b_{i},\) cada vez que \(x_{i}\) ocurra en \(t_{j}\), lo cual ya que \(\mathrm{Enu}_{k}\) es verdadero, 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.9.2 La relación \(\models\)

Fijemos un tipo \(\tau\). A continuación definiremos matemáticamente una relación \(\mathbf{"A}\models\varphi[\vec{a}]"\), donde \(\mathbf{A}\) es una estructura de tipo \(\tau\), \(\vec{a}\) es una asignación de \(\mathbf{A}\) y \(\varphi\in F^{\tau}\). Intuitivamente hablando \(\mathbf{A}\models\varphi[\vec{a}]\) significara que la fórmula \(\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 definición matemática será recursiva y mas abajo explicaremos por que la definición es precisa o rigurosa matemáticamente hablando. Dada una estructura \(\mathbf{A}\) de tipo \(\tau\), una asignación \(\vec{a}\in A^{\mathbf{N}}\) y \(a\in A\), con \(\downarrow_{i}^{a}(\vec{a})\) denotaremos la asignación que resulta de reemplazar en \(\vec{a}\) el \(i\)-ésimo elemento por \(a\). Ahora sí la definición 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 definición de la relación “\(\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 atómica, 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 también 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 comenzando desde la capa \(0\) vemos que se va determinando para todas las fórmulas de las distintas capas cuando vale y cuando no vale la relación \(\mathbf{A}\models\varphi[\vec{a}]\). Nótese que en todo este razonamiento es crucial la unicidad de la lectura de fórmulas ya que de no haber unicidad la definición se volvería ambigua.

Cuando se dé \(\mathbf{A}\models\varphi[\vec{a}]\) diremos que la estructura \(\mathbf{A}\) satisface \(\varphi\) en la asignación \(\vec{a}\) y en tal caso diremos que \(\varphi\) es verdadera en \(\mathbf{A}\) para la asignación \(\vec{a}\). Cuando no se dé \(\mathbf{A}\models\varphi[\vec{a}]\) diremos que la estructura \(\mathbf{A}\) no satisface \(\varphi\) en la asignación \(\vec{a}\) y en tal caso diremos que \(\varphi\) es falsa en \(\mathbf{A}\) para la asignación \(\vec{a}\). También hablaremos del valor de verdad de \(\varphi\) en \(\mathbf{A}\) para la asignación \(\vec{a}\) el cual será 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 operación \[\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 operación \[\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 asignación de \(\mathbf{A}\). Ejemplos:

1. adhocprefix(E1)adhocsufix Sea \(\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}))\). Nótese que

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

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

   O sea que (1) de la definición 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 Sea \(\varphi=\lnot\mathrm{Her}(\mathrm{P}(\mathrm{P}(\mathsf{X}\mathbf{6})),\mathsf{X}\mathbf{3},\mathrm{doli})\). Nótese 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\)

   O sea que (7) de la definición nos dice que \[\mathbf{A}\models\varphi[\vec{a}]\text{ sii }\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 definición nos dice que \[\mathbf{A}\models\mathrm{Her}(\mathrm{P}(\mathrm{P}(\mathsf{X}\mathbf{6})),\mathsf{X}\mathbf{3},\mathrm{doli})[\vec{a}]\text{ sii }(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 Sea \(\varphi=\exists\mathsf{X}\mathbf{3}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{3},\mathrm{uno})\). Por (9) de la definición 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...)]\)

   Pero (2) de la definición 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,...)]\) 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 Sea \(\varphi=\forall\mathsf{X}\mathbf{1(}(\mathsf{X}\mathbf{4}\equiv\mathsf{X}\mathbf{1})\rightarrow\exists\mathsf{X}\mathbf{6}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{1},\mathrm{uno}))\). Por (8) de la definición tenemos que \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si para cada \(r\in\mathbf{R}\) se da que \[\mathbf{A}\models\mathbf{(}(\mathsf{X}\mathbf{4}\equiv\mathsf{X}\mathbf{1})\rightarrow\exists\mathsf{X}\mathbf{6}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{1},\mathrm{uno}))[\downarrow_{1}^{r}(\vec{a})]\] Es decir que \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si para cada \(r\in\mathbf{R}\) se da que \[\mathbf{A}\models\mathbf{(}(\mathsf{X}\mathbf{4}\equiv\mathsf{X}\mathbf{1})\rightarrow\exists\mathsf{X}\mathbf{6}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{1},\mathrm{uno}))[(r,2,3,...)]\] Pero entonces (5) de la definición nos dice que \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si para cada \(r\in\mathbf{R}\) se da que \[\mathbf{A}\not\models(\mathsf{X}\mathbf{4}\equiv\mathsf{X}\mathbf{1})[(r,2,3,...)]\text{ o }\mathbf{A}\models\exists\mathsf{X}\mathbf{6}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{1},\mathrm{uno}))[(r,2,3,...)]\] O sea que \(\mathbf{A}\models\varphi[\vec{a}]\) si y solo si para cada \(r\in\mathbf{R}\) se da que \[4\neq r\text{ o }\mathbf{A}\models\exists\mathsf{X}\mathbf{6}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{1},\mathrm{uno}))[(r,2,3,...)]\] Pero por (9) y (2) de la definición tenemos que cualquiera sea el \(r\in\mathbf{R}\) se da que \[\mathbf{A}\models\exists\mathsf{X}\mathbf{6}\mathrm{Her}(\mathsf{X}\mathbf{6},\mathsf{X}\mathbf{1},\mathrm{uno}))[(r,2,3,...)]\] si y solo si hay un \(s\in\mathbf{R}\) tal que \(s.r.9=9\). Esto nos dice finalmente que \(\mathbf{A}\models\varphi[\vec{a}]\) sii para cada \(r\in\mathbf{R}\) se da que \[4\neq r\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. Usaremos la Regla de Inducción desde 0. Para cada \(k\in\omega\) sea \(\mathrm{Enu}_{k}\) el siguiente enunciado:

1. adhocprefix\(\mathrm{Enu}_{k}\):adhocsufix Sea \(\mathbf{A}\) una estructura de tipo \(\tau\) y sea \(\varphi\in F_{k}^{\tau}\). Supongamos que \(\vec{a},\vec{b}\) son asignaciones tales que \(a_{i}=b_{i},\) cada vez que \(x_{i}\in Li(\varphi)\). Entonces \(\mathbf{A}\models\varphi[\vec{a}]\) sii \(\mathbf{A}\models\varphi[\vec{b}]\)

Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(0\).

Prueba de que \(\mathrm{Enu}_{0}\) es verdadero. Se desprende del Lema 7.16 y es dejado al lector.

Prueba de que si \(\mathrm{Enu}_{k}\) es verdadero entonces \(\mathrm{Enu}_{k+1}\) lo es. Supongamos entonces que vale \(\mathrm{Enu}_{k}\). Sea \(\mathbf{A}\) una estructura de tipo \(\tau\) y sea \(\varphi\in F_{k+1}^{\tau}\). Supongamos que \(\vec{a},\vec{b}\) son asignaciones tales que \(a_{i}=b_{i},\) cada vez que \(x_{i}\in Li(\varphi)\). Por definición de \(F_{k+1}^{\tau}\), hay varios casos.

Caso \(\varphi\in F_{k}^{\tau}\). Ya que es verdadero \(\mathrm{Enu}_{k}\), es claro que se cumple la conclusión de \(\mathrm{Enu}_{k+1}\).

Caso \(\varphi=(\varphi_{1}\wedge\varphi_{2})\), con \(\varphi_{1},\varphi_{2}\in F_{k}^{\tau}\). Ya que \(Li(\varphi_{i})\subseteq Li(\varphi)\), \(i=1,2\), tenemos que \(\mathrm{Enu}_{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\\ \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=\forall x_{j}\varphi_{1}\), con \(\varphi_{1}\in F_{k}^{\tau}\) y \(j\in\mathbf{N}\). Supongamos \(\mathbf{A}\models\varphi[\vec{a}]\). Entonces por (8) en la definición 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\). Nótese 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 \(\mathrm{Enu}_{k}\) nos dice \(\mathbf{A}\models\varphi_{1}[\downarrow_{j}^{a}(\vec{b})]\), para todo \(a\in A\), lo cual por (8) en la definición 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 \(\mathbf{A}\models\varphi[\vec{a}]\) es similar.

Los otros casos son similares y dejados al lector.  

En virtud del corolario anterior tenemos que el valor de verdad de una sentencia \(\varphi\) en una estructura dada \(\mathbf{A}\) para una asignación \(\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\))

7.9.3 Sentencias universalmente válidas

Una sentencia \(\varphi\) de tipo \(\tau\) sera llamada universalmente valida si es verdadera en cada modelo de tipo \(\tau\), es decir si \(\mathbf{A}\models\varphi\), para cada estructura \(\mathbf{A}\) de tipo \(\tau\) (o equivalentemente si \(\mathbf{A}\models\varphi[\vec{a}]\), para cada estructura \(\mathbf{A}\) de tipo \(\tau\) y cada asignación \(\vec{a}\in A^{\mathbf{N}}\)).

7.9.4 Equivalencia de fórmulas

Dadas \(\varphi,\psi\in F^{\tau}\) diremos que \(\varphi\) y \(\psi\) son equivalentes cuando se dé la siguiente condición

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. Nótese que \[\{(\varphi,\psi)\in F^{\tau}\times F^{\tau}:\varphi\thicksim\psi\}\] es una relación de equivalencia sobre \(F^{\tau}\).

Proof. (a) Tenemos que \[\begin{array}{l} \varphi\thicksim\psi\\ \ \ \Updownarrow\text{ (por (6) de la def de}\models\text{)}\\ \mathbf{A}\models(\phi\leftrightarrow\psi)[\vec{a}]\text{, para todo }\mathbf{A}\text{ y toda }\vec{a}\in A^{\mathbf{N}}\\ \ \ \Updownarrow\\ \mathbf{A}\models(\phi\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}}(\phi\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}}(\phi\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}}(\phi\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}}(\phi\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}}(\phi\leftrightarrow\psi)\text{ es universalmente valida} \end{array}\]

(b) Es dejado al lector.  

Dadas \(\varphi_{1},\varphi_{2},\alpha\in F^{\tau}\) el ítem (f) del Lema de Ocurrencias de Fórmulas en Fórmulas nos dice que las distintas ocurrencias de \(\varphi_{1}\) en \(\alpha\) son disjuntas. También el ítem (f) de dicho lema nos dice que el resultado de reemplazar en \(\alpha\) algunas ocurrencias de \(\varphi_{1}\) por \(\varphi_{2}\) es una fórmula. Mas aún

Proof. Usaremos la Regla de Inducción desde 0. Para cada \(k\in\omega\) sea \(\mathrm{Enu}_{k}\) el siguiente enunciado:

1. adhocprefix\(\mathrm{Enu}_{k}\):adhocsufix Sean \(\varphi_{1},\varphi_{2}\in F^{\tau}\) tales que \(\varphi_{1}\thicksim\varphi_{2}\) y sea \(\alpha\in F_{k}^{\tau}\). Sea \(\alpha^{\prime}\) el resultado de reemplazar en \(\alpha\) algunas (posiblemente \(0\)) ocurrencias de \(\varphi_{1}\) por \(\varphi_{2}\). Entonces \(\alpha\thicksim\alpha^{\prime}.\)

Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(0\).

Prueba de que \(\mathrm{Enu}_{0}\) es verdadero. Es fácil ya que las fórmulas atómicas no tienen suformulas propias (Lema de Ocurrencias de Fórmulas en Fórmulas).

Prueba de que si \(\mathrm{Enu}_{k}\) es verdadero entonces \(\mathrm{Enu}_{k+1}\) lo es. Supongamos entonces que vale \(\mathrm{Enu}_{k}\). Sean \(\varphi_{1},\varphi_{2}\in F^{\tau}\) tales que \(\varphi_{1}\thicksim\varphi_{2}\) y sea \(\alpha\in F_{k+1}^{\tau}\). Sea \(\alpha^{\prime}\) el resultado de reemplazar en \(\alpha\) algunas (posiblemente \(0\)) ocurrencias de \(\varphi_{1}\) por \(\varphi_{2}\). Probaremos que entonces \(\alpha\thicksim\alpha^{\prime}\). Por definición de \(F_{k+1}^{\tau}\), hay varios casos.

Caso \(\alpha\in F_{k}^{\tau}\). Ya que es verdadero \(\mathrm{Enu}_{k}\), es claro que \(\alpha\thicksim\alpha^{\prime}\).

Caso \(\alpha=(\alpha_{1}\eta\alpha_{2})\), con \(\alpha_{1},\alpha_{2}\in F_{k}^{\tau}\). Si \(\varphi_{1}=\alpha\) entonces \(\alpha^{\prime}=\varphi_{2}\) y por lo tanto \(\alpha\thicksim\alpha^{\prime}\) ya que por hipótesis \(\varphi_{1}\thicksim\varphi_{2}\). Supongamos entonces \(\varphi_{1}\neq\alpha\). Por (b) del Lema de Ocurrencias de Fórmulas en Fórmulas las ocurrencias de \(\varphi_{1}\) en \(\alpha\) que fueron reemplazadas por \(\varphi_{2}\) para obtener \(\alpha^{\prime}\) suceden ya sea en \(\alpha_{1}\) o en \(\alpha_{2}\). O sea que \(\alpha^{\prime}=(\alpha_{1}^{\prime}\eta\alpha_{2}^{\prime})\) donde cada \(\alpha_{i}^{\prime}\) se obtiene como resultado de reemplazar algunas (posiblemente \(0\)) ocurrencias de \(\varphi_{1}\) en \(\alpha_{i}\) por \(\varphi_{2}\). Ya que vale \(\mathrm{Enu}_{k}\) y \(\alpha_{1},\alpha_{2}\in F_{k}^{\tau}\) tenemos que \(\alpha_{i}\thicksim\alpha_{i}^{\prime}\) para \(i=1,2\). Pero esto por (b) del lema anterior nos dice que \((\alpha_{1}\eta\alpha_{2})\thicksim(\alpha_{1}^{\prime}\eta\alpha_{2}^{\prime})\), es decir \(\alpha\thicksim\alpha^{\prime}\).

Los otros casos son similares y dejados al lector.  

7.9.5 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 además nótese que una ves puesto estos nombres a los elementos de \(A\), también podemos manejar dentro de nuestra computadora a las interpretaciones de los nombres de cte, función y relación en \(\mathbf{A}\) (por ejemplo si \(f\in\mathcal{F}_{2}\) podemos representar a \(i(f)\) con una tabla de tres columnas. Entonces el lector no tendrá problema en imaginar como haría un programa (en cualquier lenguaje de los actuales) con las siguientes características:

1. adhocprefix-adhocsufix Datos de entrada: Una fórmula \(\varphi\) de tipo \(\tau\) y elementos \(a_{1},...,a_{n}\) de \(A\) donde \(n\in\mathbf{N}\) es tal que \(\{v\in Var:v\text{ ocurre en }\varphi\}\subseteq\{x_{1},...,x_{n}\}\)

2. adhocprefix-adhocsufix 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. adhocprefix-adhocsufix 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 matemático de las fórmulas elementales y sus valores de verdad, resulta que ahora este programa nos esta permitiendo calcular sin pensar el valor de verdad de una fórmula en una estructura finita! Por supuesto esto tiene sentido si la noción matemática de valor de verdad es realmente un modelo adecuado de nuestra idea intuitiva de valor de verdad. Pero ...

7.9.6 Hemos creado un monstruo?

Que tal si nuestro modelo matemático de valor de verdad no es del todo satisfactorio, es decir, que tal si el programa anterior en algún caso da como salida el Booleano \(1\) y para nosotros la fórmula de entrada era falsa en la asignación de entrada. En ese caso nos deberíamos sentir identificados con el Dr Frankenstein, el cual quiso hacer un humano pero su creación tenia detalles ....

Veamos un ejemplo feo. Sea \(\tau=(\{c\},\emptyset,\{\mathrm{P1},\mathrm{P2},\mathrm{R}\},\{(\mathrm{P1},1),(\mathrm{P2},1),(\mathrm{R},1)\})\). 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))))\] Nótese que esta sentencia nos dice que si tenemos que \((\mathrm{P1}(c)\wedge\mathrm{P2}(c))\) implica \(\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 intuición nos dice que podría 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 embargo una fácil inspección usando la definición de \(\models\) nos permite probar que \(\mu\) es universalmente válida.

Este ejemplo nos hace pensar que quizás 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 explicación tiene que ver con el hecho que en general en la matemática real no le asignamos valor de verdad a una implicación 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\) denota un elemento concreto y fijo.

Otra sentencia que rompe nuestra intuición por ser siempre verdadera es la siguiente \[((\forall x_{1}\mathrm{P1}(x_{1})\rightarrow\mathrm{P2}(c))\rightarrow\exists x_{1}(\mathrm{P1}(x_{1})\rightarrow\mathrm{P2}(c)))\] Dejamos al lector que medite hasta entender que el fenómeno por el cual se rompe la intuición es el mismo que en \(\mu\) (note que un \(\forall\) es en algún sentido la conjunción de muchos casos). Solo resta decir que son casos marginales, estos en los cuales se rompe la intuición, y en general no aparecen en la escritura real de los matemáticos. Mas aun, quizás deberíamos pensar que el modelo matemático dado nos enseña a pensar de una manera mas madura este tipo de casos que nunca ocurren en la matemática real.