7.11 Dos teoremas de reemplazo

Probaremos dos teoremas muy importantes que en algun sentido nos dicen que el reemplazo sintactico se lleva bien con la semantica. Usaremos la notacion declaratoria para expresarlos ya que los vuelve mucho mas accesibles e intuitivos.

7.11.1 Teorema de reemplazo para terminos

1. (a) Todas las variables de $t(s_1,...,s_k)$ estan en $\{v_1,...,v_n\}$

2. (b) Si declaramos $t(s_1,...,s_k){=}_{d}t(s_1,...,s_k)(v_1,...,v_n)$, entonces para cada estructura $A$ y $a_1,....,a_n\in A,$ se tiene que $$t(s_1,...,s_k{)}^A[a_1,....,a_n]=t^A[s_1^A[a_1,....,a_n],...,s_k^A[a_1,....,a_n]].$$

Proof. Probaremos que se dan (a) y (b), por induccion en el $l$ tal que $t\in T_l^{\tau }$. El caso $l=0$ es dejado al lector. Supongamos entonces que el teorema vale siempre que $t\in T_l^{\tau }$ y veamos que entonces vale cuando $t\in T_{l+1}^{\tau }-T_l^{\tau }$. Por el Lema 7.25 hay $f\in F_m$ y $t_1,...,t_m$ terminos tales $t=f(t_1,...,t_m)$ y las variables que ocurren en cada $t_i$ estan en $\{w_1,...,w_k\}$. Por la unicidad de la lectura de terminos tenemos que $t_1,...,t_m\in T_l^{\tau }$ (por que?). Notese que por nuestra Convencion Notacional 3 asumimos ya hechas las declaraciones $$t_1{=}_d{t}_1(w_1,...,w_k),...,t_m{=}_d{t}_m(w_1,...,w_k)$$ Por HI tenemos que las variables de cada $t_i(s_1,...,s_k)$ estan en $\{v_1,...,v_n\}$, lo cual nos permite hacer las siguientes declaraciones: $$t_i(s_1,...,s_k){=}_d{t}_i(s_1,...,s_k)(v_1,...,v_n),i=1,...,m$$ Por HI tenemos entonces que $$t_i(s_1,...,s_k{)}^A[\overrightarrow{a}]=t_i^A[s_1^A\left[\overrightarrow{a}\right],...,s_k^A\left[\overrightarrow{a}\right]],i=1,...,m$$ Ya que las variables de cada $t_i(s_1,...,s_k)$ estan en $\{v_1,...,v_n\}$, tenemos que las variables de $t(s_1,...,s_k)=f\left(t_1\right(s_1,...,s_k),...,t_m(s_1,...,s_k\left)\right)$ estan en $\{v_1,...,v_n\}$. Declaremos entonces $t(s_1,...,s_k){=}_{d}t(s_1,...,s_k)(v_1,...,v_n)$. Solo nos falta probar que $$t(s_1,...,s_k{)}^A[a_1,....,a_n]=t^A[s_1^A[a_1,....,a_n],...,s_k^A[a_1,....,a_n]].$$ lo cual se detalla a continuacion $$\begin{array}{ccc}t(s_1,...,s_k{)}^A[\overrightarrow{a}]& =& f\left(t_1\right(s_1,...,s_k),...,t_m(s_1,...,s_k\left){)}^A\right[\overrightarrow{a}]\\ & =& f^A\left(t_1\right(s_1,...,s_k{)}^A\left[\overrightarrow{a}\right],...,t_m(s_1,...,s_k{)}^A[\overrightarrow{a}\left]\right)\\ & =& f^A\left(t_1^A\right[s_1^A\left[\overrightarrow{a}\right],...,s_k^A\left[\overrightarrow{a}\right]],...,t_m^A[s_1^A\left[\overrightarrow{a}\right],...,s_k^A\left[\overrightarrow{a}\right]\left]\right)\\ & =& t^A\left[s_1^A\right[\overrightarrow{a}],...,s_k^A[\overrightarrow{a}\left]\right]\end{array}$$  

7.11.2 Teorema de reemplazo para formulas

Para expresar este teorema necesitaremos dar una definicion que garantice que cuando reemplazamos una variable libre $v$ por otra variable $w$ en una formula, el significado de la formula no se altere. Por supuesto esto es solo una idea y a continuacion daremos el concepto en forma precisa. Antes el concepto de alcance el cual esta emparentado con el de sustitucion de variables.

Alcance de la ocurrencia de un cuantificador en una formula

Proof. Por induccion en el $k$ tal que $\phi \in F^{\tau }$.  

Dada una ocurrencia de $Qv$ en una formula $\phi$, la formula $\psi$ del lema anterior sera llamada el alcance de dicha ocurrencia en $\phi$. Notese que dos ocurrencias distintas de $Qv$ en $\phi$ pueden tener alcances distintos por lo cual el concepto de alcance es relativo a una ocurrencia de un cuantificador y no relativo a un cuantificador a secas.

Sustitucion de variables libres

Diremos que $v$ es sustituible por $w$ en $\phi$ cuando ninguna ocurrencia libre de $v$ en $\phi$ sucede dentro de una ocurrencia de una subformula de la forma $Qw\psi$ en $\phi$. En otras palabras $v$ no sera sustituible por $w$ en $\phi$ cuando alguna ocurrencia libre de $v$ en $\phi$ suceda dentro de una ocurrencia en $\phi$ de una formula de la forma $Qw\psi$. Notese que puede suceder que $v$ sea sustituible por $w$ en $\phi$ y que sin envargo haya una subformula de la forma $Qw\psi$ para la cual $v\in Li\left(Qw\psi \right)$. Dejamos como ejercicio encontrar un ejemplo de esta situacion.

Usando lemas anteriores podemos ver que se dan las siguientes propiedades:

1. (1) Si $\phi$ es atomica, entonces $v$ es sustituible por $w$ en $\phi$

2. (2) Si $\phi =\left({\phi }_1\eta {\phi }_2\right)$, entonces $v$ es sustituible por $w$ en $\phi$ sii $v$ es sustituible por $w$ en ${\phi }_1$ y $v$ es sustituible por $w$ en ${\phi }_2$

3. (3) Si $\phi =\neg {\phi }_1$, entonces $v$ es sustituible por $w$ en $\phi$ sii $v$ es sustituible por $w$ en ${\phi }_1$

4. (4) Si $\phi =Qv{\phi }_1$, entonces $v$ es sustituible por $w$ en $\phi$

5. (5) Si $\phi =Qw{\phi }_1$ y $v\in Li\left({\phi }_1\right)$, entonces $v$ no es sustituible por $w$ en $\phi$

6. (6) Si $\phi =Qw{\phi }_1$ y $v\notin Li\left({\phi }_1\right)$, entonces $v$ es sustituible por $w$ en $\phi$

7. (7) Si $\phi =Qu{\phi }_1$, con $u\ne v,w$, entonces $v$ es sustituible por $w$ en $\phi$ sii $v$ es sustituible por $w$ en ${\phi }_1$

Notese que las propiedades (1),...,(7) pueden usarse para dar una definicion recursiva de la relacion $"v$ $essustituibleporwen$ $\phi "$.

Dado un termino $t$, diremos que una variable $v$ es sustituible por $t$ en $\phi$ cuando $v$ sea sustituible en $\phi$ por cada variable que ocurre en $t$.

Proof. Probaremos que se dan (a) y (b), por induccion en el $l$ tal que $\phi \in F_l^{\tau }.$ El caso $l=0$ es una consecuencia directa del Teorema 7.4. Supongamos (a) y (b) valen para cada $\phi \in F_l^{\tau }$ y sea $\phi \in F_{l+1}^{\tau }-F_l^{\tau }.$ Notese que se puede suponer que cada $v_i$ ocurre en algun $t_i$, y que cada $w_i\in Li\left(\phi \right)$, ya que para cada $\phi$, el caso general se desprende del caso con estas restricciones. Hay varios casos

CASO $\phi =\forall w{\phi }_1$, con $w\notin \{w_1,...,w_k\}$.

Notese que cada $w_j\in Li\left({\phi }_1\right)$. Ademas notese que $w\notin \{v_1,...,v_n\}$ ya que de lo contrario $w$ ocurriria en algun $t_j$, y entonces $w_j$ no seria sustituible por $t_j$ en $\phi$. Sean $$\begin{array}{ccc}{\tilde{t}}_1& =& t_1\\ & ⋮& \\ {\tilde{t}}_k& =& t_k\\ {\tilde{t}}_{k+1}& =& w\end{array}$$ Declaremos $${\tilde{t}}_j{=}_d{\tilde{t}}_j(v_1,...,v_n,w)$$ Notese que nuestra Convencion Notacional 6 nos dice que tenemos implicitamente hecha la declaracion ${\phi }_1{=}_d{\phi }_1(w_1,...,w_k,w)$. Por (a) de la hipotesis inductiva tenemos que $$Li\left({\phi }_1\right(t_1,...,t_k,w\left)\right)=Li\left({\phi }_1\right({\tilde{t}}_1,...,{\tilde{t}}_k,{\tilde{t}}_{k+1}\left)\right)\subseteq \{v_1,...,v_n,w\}$$ y por lo tanto $$Li\left(\phi \right(t_1,...,t_k\left)\right)\subseteq \{v_1,...,v_n\}$$ lo cual prueba (a). Finalmente para probar (b) declaremos $\phi (t_1,...,t_k){=}_d\phi (t_1,...,t_k)(v_1,...,v_n)$. Se tiene que $$\begin{array}{c}A\models \phi (t_1,...,t_k)[\overrightarrow{a}]\\ \Updownarrow \\ A\models {\phi }_1({\tilde{t}}_1,...,{\tilde{t}}_k,{\tilde{t}}_{k+1})[\overrightarrow{a},a]\text{, para todo}a\in A\\ \Updownarrow \text{(por HI)}\\ A\models {\phi }_1\left[{\tilde{t}}_1^A\right[\overrightarrow{a},a],...,{\tilde{t}}_k^A[\overrightarrow{a},a],{\tilde{t}}_{k+1}^A[\overrightarrow{a},a\left]\right]\text{, para todo}a\in A\\ \Updownarrow \\ A\models {\phi }_1\left[t_1^A\right[\overrightarrow{a}],...,t_k^A[\overrightarrow{a}],a]\text{, para todo}a\in A\\ \Updownarrow \\ A\models \phi \left[t_1^A\right[\overrightarrow{a}],...,t_k^A[\overrightarrow{a}\left]\right]\end{array}$$ lo cual pueba (b). Dejamos al lector los casos restantes.  

1. Ejemplo: Sea $\tau =(\varnothing ,\{f\},\varnothing ,\{(f,1)\left\}\right)$. Sean $\phi =\exists v_1\left(f\right(v_1)\equiv w_1)$ y $t=v_1$, donde $v_1$ y $w_1$ son variables distintas. Declaremos $\phi {=}_d\phi \left(w_1\right)$ y $t{=}_{d}t\left(v_1\right)$. Notese que $w_1$ no es sustituible en $\phi$ por $t$, por lo cual el teorema anterior no se puede aplicar. De hecho la conclusion del teorema no se da en este caso ya que puede verse facilmente que, cualesquiera sea la estructura de tipo $\tau$, $A$ y $a_1\in A$, tenemos que:

   1. $A\models \phi \left(t\right)\left[a_1\right]$ si y solo si $f^A$ tiene un pto fijo, es decir, $f^A\left(a\right)=a$, para algun $a\in A$

   2. $A\models \phi \left[t^A\right[a_1\left]\right]$ si y solo si $a_1$ esta en la imagen de $f^A$

   las cuales son condiciones claramente no equivalentes.