Desarrollaremos una notación que vuelve mas intuitiva y dinámica la escritura en lo referente a la semántica de los términos y fórmulas. Por supuesto el precio que esto tiene es que deberemos dedicarnos bastante a aprender a manejar esta notación en forma precisa, para no perder rigor matemático. Es importante manejarla bien ya que los resultados mas importantes de la materia están expresados mediante esta notación.
Supongamos \(v_{1},...,v_{n}\in Var\) y \(t\) es un término de tipo \(\tau\). Entonces escribiremos \(t=_{d}t(v_{1},...,v_{n})\) para declarar que \(v_{1},...,v_{n}\) son variables distintas y tales que toda variable que ocurre en \(t\) pertenece a \(\{v_{1},...,v_{n}\}\) (no necesariamente toda \(v_{j}\) debe ocurrir en \(t\)). Consideraremos el caso \(n=0\), es decir a veces haremos la declaración \(t=_{d}t()\) la cual simplemente expresara que \(t\) es un término cerrado.
El uso de declaraciones de la forma \(t=_{d}t(v_{1},...,v_{n})\) es muy útil cuando se lo combina con ciertas convenciones notacionales que describiremos a continuación.
Convención Notacional 1: Cuando hayamos hecho la declaración \(t=_{d}t(v_{1},...,v_{n})\), si \(P_{1},...,P_{n}\) son palabras cualesquiera (no necesariamente términos), entonces \(t(P_{1},...,P_{n})\) denotará la palabra que resulta de reemplazar simultáneamente cada ocurrencia de \(v_{1}\) en \(t\), por \(P_{1}\), cada ocurrencia de \(v_{2}\) en \(t\), por \(P_{2}\), etc.
Nótese que en esta convención notacional, el orden de las variables \(v_{1},...,v_{n}\) es clave. Por ejemplo si \(\tau=(\{\mathrm{cero}\},\{\mathrm{FU}\},\emptyset,\{(\mathrm{FU},2)\})\) y \(t=\mathrm{FU}(\mathrm{FU}(x_{2},x_{16}),x_{3})\), entonces
adhocprefix-adhocsufix Si declaramos \(t=_{d}t(x_{3},x_{2},x_{16})\), entonces \(t(\#\#,\blacktriangle\#\blacktriangle,@@)\) denotará la palabra \(\mathrm{FU}(\mathrm{FU}(\blacktriangle\#\blacktriangle,@@),\#\#)\)
adhocprefix-adhocsufix Si declaramos \(t=_{d}t(x_{16},x_{3},x_{2})\), entonces \(t(\#\#,\blacktriangle\#\blacktriangle,@@)\) denotará la palabra \(\mathrm{FU}(\mathrm{FU}(@@,\#\#),\blacktriangle\#\blacktriangle)\)
También podríamos haber declarado \(t=_{d}t(x_{3},x_{200},x_{2},x_{16},x_{100})\) y en tal caso \(t(\#\#,!!!!,\blacktriangle\#\blacktriangle,@@,!!)\) denotará la palabra \(\mathrm{FU}(\mathrm{FU}(\blacktriangle\#\blacktriangle,@@),\#\#)\).
Además nótese que si hemos hecho la declaración \(t=_{d}t(v_{1},...,v_{n})\) y \(t_{1},...,t_{n}\) son términos, entonces \(t(t_{1},...,t_{n})\) es un término. Esto se puede ver aplicando \(n\) veces (c) del Lema 7.6, aunque hay que tener en cuenta que según la Convención Notacional 1 el reemplazo para obtener \(t(t_{1},...,t_{n})\) es simultaneo por lo que las \(n\) aplicaciones antes mencionadas deben ser bien elegidas para producir el mismo efecto que en el reemplazo simultaneo. De todas maneras mas adelante probaremos esto en el Teorema de Reemplazo para Términos.
Convención Notacional 2: Cuando hayamos declarado \(t=_{d}t(v_{1},...,v_{n})\), si \(\mathbf{A}\) es un modelo de tipo \(\tau\) y \(a_{1},...,a_{n}\in A\), entonces con \(t^{\mathbf{A}}[a_{1},...,a_{n}]\) denotaremos al elemento \(t^{\mathbf{A}}[\vec{b}]\), donde \(\vec{b}\) es una asignación tal que a cada \(v_{i}\) le asigna el valor \(a_{i}\). Note que esto nos dice que para el caso \(n=0\), con \(t^{\mathbf{A}}[]\) denotaremos al elemento \(t^{\mathbf{A}}[\vec{b}]\), donde \(\vec{b}\) es una asignación cualquiera. Cabe destacar que esta notación es inambigua gracias al Lema 7.16.
De nuevo, el orden de las variables \(v_{1},...,v_{n}\) es clave. Por ejemplo si \(\tau\) y \(t\) son los dados en el ejemplo anterior y \(\mathbf{A}\) es dado por \(A=\{1,2,3\}\), \(\mathrm{cero}^{\mathbf{A}}=1\) y \(\mathrm{FU}^{\mathbf{A}}(i,j)=j\), para cada \(i,j\in A\), tenemos que
adhocprefix-adhocsufix Si declaramos \(t=_{d}t(x_{3},x_{2},x_{16})\), entonces \[t^{\mathbf{A}}[2,1,3]=\mathrm{FU}(\mathrm{FU}(x_{2},x_{16}),x_{3})^{\mathbf{A}}[2,1,3]=\mathrm{FU^{\mathbf{A}}}(\mathrm{FU^{\mathbf{A}}}(1,3),2)=2\]
adhocprefix-adhocsufix Si declaramos \(t=_{d}t(x_{16},x_{3},x_{2})\), entonces \[t^{\mathbf{A}}[2,1,3]=\mathrm{FU}(\mathrm{FU}(x_{2},x_{16}),x_{3})^{\mathbf{A}}[2,1,3]=\mathrm{FU^{\mathbf{A}}}(\mathrm{FU^{\mathbf{A}}}(3,2),1)=1\]
También podríamos haber declarado \(t=_{d}t(x_{3},x_{200},x_{2},x_{16},x_{100})\) y en tal caso \(t^{\mathbf{A}}[2,10,1,3,1000]=2\). Para dar un ejemplo con \(n=0\), si tomamos \[t=\mathrm{FU}(\mathrm{FU}(\mathrm{cero},\mathrm{cero}),\mathrm{cero})\] entonces podemos hacer la declaración \(t=_{d}t()\) y en tal caso \[t^{\mathbf{A}}[]=\mathrm{FU^{\mathbf{A}}}(\mathrm{FU^{\mathbf{A}}}(1,1),1)=1.\]
Cuando hacemos una declaración \(t=_{d}t(v_{1},...,v_{n})\) tenemos un poco mas de información que la que tenemos sobre un término \(t\) en general. Por ejemplo sabemos que si \(t\in Var\), entonces \(t\in\{v_{1},...,v_{n}\}\). Haremos entonces un lema de "lectura única de términos declarados", el cual será muy útil para hacer demostraciones usando la notación declaratoria.
7.28 (Lectura Única de Términos Declarados). Sea \(\tau\) un tipo cualquiera y supongamos \(t\in T^{\tau}\). Si \(t=_{d}t(v_{1},...,v_{n})\), entonces se da una y solo una de las siguientes:
adhocprefix(1)adhocsufix \(t=c,\) para algún \(c\in\mathcal{C}\)
adhocprefix(2)adhocsufix \(t=v_{j},\) para algún \(j\)
adhocprefix(3)adhocsufix \(t=f(t_{1},...,t_{m})\), con \(f\in\mathcal{F}_{m}\), \(m\geq1\) y \(t_{1},...,t_{m}\in T^{\tau}\) únicos
Mas aun si \(t\in T_{k+1}^{\tau}\) entonces cuando se da (3) los términos \(t_{1},...,t_{n}\) están en \(T_{k}^{\tau}\).
Proof. Es concecuencia directa del Teorema de Lectura Única de Términos.
Nótese que cuando \(n=0\) en el lema anterior, la opción (2) no puede suceder.
Convención Notacional 3: Cuando hayamos declarado \(t=_{d}t(v_{1},...,v_{n})\) y se dé el caso (3) del Lema 7.28 supondremos tácitamente que también hemos hecho las declaraciones \(t_{1}=_{d}t_{1}(v_{1},...,v_{n}),...,t_{m}=_{d}t_{m}(v_{1},...,v_{n})\). Esto lo podemos hacer ya que obviamente las variables que ocurren en cada uno de los \(t_{i}^{\prime}s\) están en \(\{v_{1},...,v_{n}\}\).
La Convención Notacional 3 nos permite enunciar el siguiente resultado que es intuitivamente claro pero para dar una prueba formal de él habría que antes dar definiciones matemáticas precisas de los conceptos de ocurrencia y de reemplazo simultáneo de ocurrencias.
7.29 (Conmutatividad de Reemplazo y Armado para Términos). Supongamos \(t=_{d}t(v_{1},...,v_{n})\) y sean \(P_{1},...,P_{n}\) palabras cualesquiera. Cuando se dé el caso (3) del lema anterior se tiene que \[t(P_{1},...,P_{n})=f(t_{1}(P_{1},...,P_{n}),...,t_{m}(P_{1},...,P_{n})).\]
El siguiente lema se basa en la Convención Notacional 3 y nos permite darle carácter recursivo a la notación \(t^{\mathbf{A}}[a_{1},....,a_{n}]\). Esto será muy útil para hacer demostraciones usando la notación declaratoria.
7.30 (Carácter Recursivo de la Notación \(t^{\mathbf{A}}[a_{1},....,a_{n}]\)). Sea \(\tau\) un tipo cualquiera y \(t\in T^{\tau}\). Supongamos \(t=_{d}t(v_{1},...,v_{n})\). Sea \(\mathbf{A}\) un modelo de tipo \(\tau\). Sean \(a_{1},...,a_{n}\in A\). Se tiene que:
adhocprefix(1)adhocsufix Si \(t=c,\) entonces \(t^{\mathbf{A}}[a_{1},....,a_{n}]=c^{\mathbf{A}}\)
adhocprefix(2)adhocsufix Si \(t=v_{j},\) entonces \(t^{\mathbf{A}}[a_{1},....,a_{n}]=a_{j}\)
adhocprefix(3)adhocsufix Si \(t=f(t_{1},...,t_{m})\), con \(f\in\mathcal{F}_{m}\) y \(t_{1},...,t_{m}\in T^{\tau}\), entonces \[t^{\mathbf{A}}[a_{1},....,a_{n}]=f^{\mathbf{A}}(t_{1}^{\mathbf{A}}[a_{1},....,a_{n}],...,t_{m}^{\mathbf{A}}[a_{1},....,a_{n}])\]
Proof. (1) y (2) son triviales.
(3) Sea \(\vec{b}\) una asignación tal que a cada \(v_{i}\) le asigna el valor \(a_{i}\). Tenemos que \[\begin{aligned} t^{\mathbf{A}}[a_{1},....,a_{n}] & =t^{\mathbf{A}}[\vec{b}]\text{ (por def. de }t^{\mathbf{A}}[a_{1},....,a_{n}]\text{)}\\ & =f^{\mathbf{A}}(t_{1}^{\mathbf{A}}[\vec{b}],...,t_{m}^{\mathbf{A}}[\vec{b}])\text{ (por def. de }t^{\mathbf{A}}[\vec{b}]\text{)}\\ & =f^{\mathbf{A}}(t_{1}^{\mathbf{A}}[a_{1},....,a_{n}],...,t_{m}^{\mathbf{A}}[a_{1},....,a_{n}])\text{ (por def. de cada }t_{i}^{\mathbf{A}}[a_{1},....,a_{n}]\text{)} \end{aligned}\]
Veamos un ejemplo de como se pueden probar cosas con la notación declaratoria.
7.31. Supongamos que \(F:\mathbf{A}\rightarrow\mathbf{B}\) es un homomorfismo. Sean \(t=_{d}t(v_{1},...,v_{n})\in T^{\tau}\) y \(a_{1},...,a_{n}\in A\). Entonces \[F(t^{\mathbf{A}}[a_{1},...,a_{n}])=t^{\mathbf{B}}[F(a_{1}),...,F(a_{n})]\]
Proof. Usaremos la Regla de Inducción desde 0. Para cada \(k\in\omega\) sea \(\mathrm{Enu}_{k}\) el siguiente enunciado:
adhocprefix\(\mathrm{Enu}_{k}\):adhocsufix Supongamos \(F:\mathbf{A}\rightarrow\mathbf{B}\) un homomorfismo. Sean \(t=_{d}t(v_{1},...,v_{n})\in T_{k}^{\tau}\) y \(a_{1},...,a_{n}\in A\). Entonces \[F(t^{\mathbf{A}}[a_{1},...,a_{n}])=t^{\mathbf{B}}[F(a_{1}),...,F(a_{n})]\]
Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(0\).
Prueba de que \(\mathrm{Enu}_{0}\) es verdadero. Supongamos \(F:\mathbf{A}\rightarrow\mathbf{B}\) es un homomorfismo y sean \(t=_{d}(v_{1},...,v_{n})\in T_{0}^{\tau}\) y \(a_{1},...,a_{n}\in A\). Ya que \(T_{0}^{\tau}=Var\cup\mathcal{C}\), tenemos que dos casos posibles. En ambos utilizaremos el Lema Caracter Recursivo de la Notación \(t^{\mathbf{A}}[a_{1},....,a_{n}]\).
Caso \(t=v_{j}\), para algún \(j\). Tenemos que \[\begin{aligned} F(t^{\mathbf{A}}[a_{1},....,a_{n}]) & =F(a_{j})\\ & =t^{\mathbf{B}}[F(a_{1}),...,F(a_{n})] \end{aligned}\]
Caso \(t=c\), para algún \(c\in\mathcal{C}\). Tenemos que \[\begin{aligned} F(t^{\mathbf{A}}[a_{1},....,a_{n}]) & =F(c^{\mathbf{A}})\\ & =c^{\mathbf{B}}\\ & =t^{\mathbf{B}}[F(a_{1}),...,F(a_{n})] \end{aligned}\]
Prueba de que si \(\mathrm{Enu}_{k}\) es verdadero entonces \(\mathrm{Enu}_{k+1}\) lo es. Supongamos entonces que vale \(\mathrm{Enu}_{k}\). Supongamos \(F:\mathbf{A}\rightarrow\mathbf{B}\) es un homomorfismo y sean \(t=_{d}(v_{1},...,v_{n})\in T_{k+1}^{\tau}\) y \(a_{1},...,a_{n}\in A\). Por el Lema de Lectura Única de Términos Declarados hay varios casos.
Caso \(t=c,\) para algún \(c\in\mathcal{C}\). Ya fue probado en la prueba de \(\mathrm{Enu}_{0}\).
Caso \(t=v_{j}\), para algún \(j\). Ya fue probado en la prueba de \(\mathrm{Enu}_{0}\).
Caso \(t=f(t_{1},...,t_{m})\), con \(f\in\mathcal{F}_{m}\), \(m\geq1\) y \(t_{1},...,t_{m}\in T^{\tau}\). Ya que \(t\in T_{k+1}^{\tau}\) el mismo lema nos dice que \(t_{1},...,t_{m}\in T_{k}^{\tau}\). Dado que hemos declarado \(t=_{d}(v_{1},...,v_{n})\), por la Convención Notacional 3, tenemos declarados también \(t_{1}=_{d}t_{1}(v_{1},...,v_{n}),...,t_{m}=_{d}t_{m}(v_{1},...,v_{n})\). Ya que \(\mathrm{Enu}_{k}\) es verdadero, tenemos que \[F(t_{i}^{\mathbf{A}}[a_{1},...,a_{n}])=t_{i}^{\mathbf{B}}[F(a_{1}),...,F(a_{n})]\] para cada \(i=1,...,m\). Entonces \[\begin{aligned} F(t^{\mathbf{A}}[a_{1},....,a_{n}]) & =F(f^{\mathbf{A}}(t_{1}^{\mathbf{A}}[a_{1},...,a_{n}],...,t_{m}^{\mathbf{A}}[a_{1},...,a_{n}]))\\ & =f^{\mathbf{B}}(F(t_{1}^{\mathbf{A}}[a_{1},...,a_{n}]),...,F(t_{m}^{\mathbf{A}}[a_{1},...,a_{n}]))\\ & =f^{\mathbf{B}}(t_{1}^{\mathbf{B}}[F(a_{1}),...,F(a_{n})],...,t_{m}^{\mathbf{B}}[F(a_{1}),...,F(a_{n})])\text{ }\\ & =t^{\mathbf{B}}[F(a_{1}),...,F(a_{n})] \end{aligned}\] lo cual nos dice que \(\mathrm{Enu}_{k+1}\) es verdadero.
Supongamos \(v_{1},...,v_{n}\in Var\) y \(\varphi\) es una fórmula de tipo \(\tau\). Entonces escribiremos \(\varphi=_{d}\varphi(v_{1},...,v_{n})\) para declarar que \(v_{1},...,v_{n}\) son variables distintas y tales que \(Li(\varphi)\subseteq\{v_{1},...,v_{n}\}\). Consideraremos el caso \(n=0\), es decir a veces haremos la declaración \(\varphi=_{d}\varphi()\) la cual simplemente expresara que \(\varphi\) es una sentencia. Tal como para el caso de términos, el uso de declaraciones de la forma \(\varphi=_{d}\varphi(v_{1},...,v_{n})\) será muy útil cuando se combina con ciertas convenciones notacionales que describiremos a continuación.
Convención Notacional 4: Cuando hayamos hecho la declaración \(\varphi=_{d}\varphi(v_{1},...,v_{n})\), si \(P_{1},...,P_{n}\) son palabras cualesquiera, entonces \(\varphi(P_{1},...,P_{n})\) denotará la palabra que resulta de reemplazar simultáneamente cada ocurrencia libre de \(v_{1}\) en \(\varphi\), por \(P_{1}\), cada ocurrencia libre de \(v_{2}\) en \(\varphi\), por \(P_{2}\), etc.
Nótese que si hemos hecho la declaración \(\varphi=_{d}\varphi(v_{1},...,v_{n})\) y \(t_{1},...,t_{n}\) son términos, entonces \(\varphi(t_{1},...,t_{n})\) es una fórmula. Esto se puede ver aplicando \(n\) veces (g) del Lema de Ocurrencias de Términos en Fórmulas aunque hay que tener en cuenta que según la Convención Notacional 3 el reemplazo para obtener \(\varphi(t_{1},...,t_{n})\) es simultaneo por lo que las \(n\) aplicaciones antes mencionadas deben ser bien elegidas para producir el mismo efecto que en el reemplazo simultaneo. De todas maneras mas adelante probaremos esto en el Teorema de Reemplazo para Fórmulas.
Tal como para el caso de términos, en esta Convención Notacional 4, el orden de las variables \(v_{1},...,v_{n}\) es clave. Es fácil dar el ejemplo análogo al dado para términos.
Convención Notacional 5: Cuando hayamos declarado \(\varphi=_{d}\varphi(v_{1},...,v_{n})\), si \(\mathbf{A}\) es un modelo de tipo \(\tau\) y \(a_{1},...,a_{n}\in A\), entonces \(\mathbf{A}\models\varphi[a_{1}...,a_{n}]\) significara que \(\mathbf{A}\models\varphi[\vec{b}],\) donde \(\vec{b}\) es una asignación tal que a cada \(v_{i}\) le asigna el valor \(a_{i}\). Note que esto nos dice que para el caso \(n=0\), \(\mathbf{A}\models\varphi[]\) significara que \(\mathbf{A}\models\varphi[\vec{b}],\) donde \(\vec{b}\) es una asignación cualquiera. (Nótese que esta convención es inambigua gracias al Lema 7.17). En gral \(\mathbf{A}\not\models\varphi[a_{1},....,a_{n}]\) significara que no sucede \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\).
Nuevamente cabe destacar que en esta convención notacional, el orden de las variables \(v_{1},...,v_{n}\) es clave. Veamos un ejemplo. Sea \(\tau=(\emptyset,\{\mathrm{F}\},\{\mathrm{E}\},\{(\mathrm{F},1),(\mathrm{E},2)\})\) y sea \[\varphi=((\mathrm{F}(x_{16})\equiv\mathrm{F}(x_{17}))\wedge\forall x_{16}\mathrm{E}(x_{2},x_{16}))\] Sea \(\mathbf{A}\) el modelo de tipo \(\tau\) dado por \(A=\{1,2,3,4,5\}\), \(\mathrm{F}^{\mathbf{A}}(x)=\max\{x,3\}\) y \(\mathrm{E}^{\mathbf{A}}=\{1\}\times A\). Entonces
adhocprefix-adhocsufix Si declaramos \(\varphi=_{d}\varphi(x_{2},x_{16},x_{17},x_{18})\) tenemos que \(\mathbf{A}\models\varphi[1,2,2,4]\)
adhocprefix-adhocsufix Si declaramos \(\varphi=_{d}\varphi(x_{18},x_{16},x_{17},x_{2})\) tenemos que no se da que \(\mathbf{A}\models\varphi[1,2,2,4]\), es decir \(\mathbf{A}\not\models\varphi[1,2,2,4]\).
Para establecer nuestra Convención Notacional 6, debemos antes enunciar un "lema de lectura única de fórmulas declaradas".
7.32 (Lectura Única de Fórmulas Declaradas). Sea \(\tau\) un tipo cualquiera y \(\varphi\in F^{\tau}\). Supongamos \(\varphi=_{d}\varphi(v_{1},...,v_{n})\). Entonces se da una y solo una de las siguientes:
adhocprefix(1)adhocsufix \(\varphi=(t\equiv s)\), con \(t,s\in T^{\tau}\), únicos
adhocprefix(2)adhocsufix \(\varphi=r(t_{1},...,t_{m})\), con \(r\in\mathcal{R}_{m}\) y \(t_{1},...,t_{m}\in T^{\tau}\), únicos
adhocprefix(3)adhocsufix \(\varphi=(\varphi_{1}\eta\varphi_{2}),\) con \(\eta\in\{\wedge,\vee,\rightarrow,\leftrightarrow\},\;\varphi_{1},\varphi_{2}\in F^{\tau}\), únicas
adhocprefix(4)adhocsufix \(\varphi=\lnot\varphi_{1}\), con \(\varphi_{1}\in F^{\tau}\), única
adhocprefix(5)adhocsufix \(\varphi=Qv_{j}\varphi_{1}\), con \(Q\in\{\forall,\exists\}\), \(j\in\{1,...,n\}\) y \(\varphi_{1}\in F^{\tau}\), únicas
adhocprefix(6)adhocsufix \(\varphi=Qv\varphi_{1}\), con \(Q\in\{\forall,\exists\}\), \(v\in Var-\{v_{1},...,v_{n}\}\) y \(\varphi_{1}\in F^{\tau}\), únicas
Mas aun si \(\varphi\in F_{k+1}^{\tau}\) entonces cuando se da (3) las fórmulas \(\varphi_{1}\text{ y }\varphi_{2}\) están en \(F_{k}^{\tau}\) y cuando se da (4) o (5) o (6) la fórmula \(\varphi_{1}\) esta en \(F_{k}^{\tau}\).
Proof. Es consecuencia directa del Teorema de Lectura Única de Fórmulas.
Nótese que cuando \(n=0\) en el lema anterior, la opción (5) no puede suceder.
Observación: Cuando hayamos declarado \(\varphi=_{d}\varphi(v_{1},...,v_{n})\), entonces:
Si se da el caso (1) del Lema 7.32, entonces las variables que ocurren en \(t\) y \(s\) están en \(\{v_{1},...,v_{n}\}\).
Si se da el caso (2) del Lema 7.32, entonces las variables que ocurren en \(t_{1},...,t_{m}\) están en \(\{v_{1},...,v_{n}\}\).
Si se el caso (3) del Lema 7.32, entonces \(Li(\varphi_{1})\cup Li(\varphi_{2})\subseteq\{v_{1},...,v_{n}\}\)
Si se da el caso (4) o el (5) del Lema 7.32, entonces \(Li(\varphi_{1})\subseteq\{v_{1},...,v_{n}\}\)
Si se da el caso (6) del Lema 7.32, entonces \(Li(\varphi_{1})\subseteq\{v_{1},...,v_{n},v\}\)
La observación anterior nos permite hacer la siguiente:
Convención Notacional 6: Cuando hayamos declarado \(\varphi=_{d}\varphi(v_{1},...,v_{n})\), entonces:
Si se da el caso (1) del Lema 7.32, supondremos tácitamente que también hemos hecho las declaraciones \(t=_{d}t(v_{1},...,v_{n})\) y \(s=_{d}s(v_{1},...,v_{n})\).
Si se da el caso (2) del Lema 7.32, supondremos tácitamente que también hemos hecho las declaraciones \(t_{1}=_{d}t_{1}(v_{1},...,v_{n}),...,t_{m}=_{d}t_{m}(v_{1},...,v_{n})\).
Si se el caso (3) del Lema 7.32, supondremos tácitamente que también hemos hecho las declaraciones \(\varphi_{1}=_{d}\varphi_{1}(v_{1},...,v_{n})\) y \(\varphi_{2}=_{d}\varphi_{2}(v_{1},...,v_{n})\).
Si se da el caso (4) o el (5) del Lema 7.32, supondremos tácitamente que también hemos hecho la declaración \(\varphi_{1}=_{d}\varphi_{1}(v_{1},...,v_{n})\).
Si se da el caso (6) del Lema 7.32, supondremos tácitamente que también hemos hecho la declaración \(\varphi_{1}=_{d}\varphi_{1}(v_{1},...,v_{n},v)\).
La Convención Notacional 6 nos permite enunciar el siguiente resultado que es intuitivamente claro pero para dar una prueba formal de él habría que antes dar definiciones matemáticas precisas de los conceptos de ocurrencia y de reemplazo simultáneo de ocurrencias.
7.33 (Conmutatividad de Reemplazo y Armado para Fórmulas). Supongamos \(\varphi=_{d}\varphi(v_{1},...,v_{n})\) y sean \(P_{1},...,P_{n}\) palabras cualesquiera. Se tiene que
adhocprefix-adhocsufix Si se da el caso (1) del Lema 7.32, entonces \[\varphi(P_{1},...,P_{n})=(t(P_{1},...,P_{n})\equiv s(P_{1},...,P_{n}))\]
adhocprefix-adhocsufix Si se da el caso (2) del Lema 7.32, entonces \[\varphi(P_{1},...,P_{n})=r(t_{1}(P_{1},...,P_{n}),...,t_{m}(P_{1},...,P_{n}))\]
adhocprefix-adhocsufix Si se el caso (3) del Lema 7.32, entonces \[\varphi(P_{1},...,P_{n})=(\varphi_{1}(P_{1},...,P_{n})\eta\varphi_{2}(P_{1},...,P_{n}))\]
adhocprefix-adhocsufix Si se da el caso (4) del Lema 7.32, entonces \[\varphi(P_{1},...,P_{n})=\neg\varphi_{1}(P_{1},...,P_{n})\]
adhocprefix-adhocsufix Si se da el caso (5) del Lema 7.32, entonces \[\varphi(P_{1},...,P_{n})=Qv_{j}\varphi_{1}(P_{1},...,P_{n})\]
adhocprefix-adhocsufix Si se da el caso (6) del Lema 7.32, entonces \[\varphi(P_{1},...,P_{n})=Qv\varphi_{1}(P_{1},...,P_{n},v)\]
El siguiente lema se basa en la Convención Notacional 6 y nos permite darle carácter recursivo a la notación \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\). Esto será muy útil para hacer demostraciones usando la notación declaratoria.
7.34 (Carácter Recursivo de la Notación \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\)). Supongamos \(\varphi=_{d}\varphi(v_{1},...,v_{n})\). Sea \(\mathbf{A}=(A,i)\) un modelo de tipo \(\tau\) y sean \(a_{1},...,a_{n}\in A\). Entonces
adhocprefix(1)adhocsufix Si \(\varphi=(t\equiv s)\), entonces
adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\) si y solo si \(t^{\mathbf{A}}[a_{1},...,a_{n}]=s^{\mathbf{A}}[a_{1},...,a_{n}]\)
adhocprefix(2)adhocsufix Si \(\varphi=r(t_{1},...,t_{m})\), entonces
adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\) si y solo si \((t_{1}^{\mathbf{A}}[a_{1},...,a_{n}],...,t_{m}^{\mathbf{A}}[a_{1},...,a_{n}])\in r^{\mathbf{A}}\)
adhocprefix(3)adhocsufix Si \(\varphi=(\varphi_{1}\wedge\varphi_{2}),\) entonces
adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\) si y solo si \(\mathbf{A}\models\varphi_{1}[a_{1},....,a_{n}]\) y \(\mathbf{A}\models\varphi_{2}[a_{1},....,a_{n}]\)
adhocprefix(4)adhocsufix Si \(\varphi=(\varphi_{1}\vee\varphi_{2}),\) entonces
adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\) si y solo si \(\mathbf{A}\models\varphi_{1}[a_{1},....,a_{n}]\) o \(\mathbf{A}\models\varphi_{2}[a_{1},....,a_{n}]\)
adhocprefix(5)adhocsufix Si \(\varphi=(\varphi_{1}\rightarrow\varphi_{2}),\) entonces
adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\) si y solo si \(\mathbf{A}\models\varphi_{2}[a_{1},....,a_{n}]\) o \(\mathbf{A}\not\models\varphi_{1}[a_{1},....,a_{n}]\)
adhocprefix(6)adhocsufix Si \(\varphi=(\varphi_{1}\leftrightarrow\varphi_{2}),\) entonces
adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\) si y solo si ya sea \(\mathbf{A}\models\varphi_{1}[a_{1},....,a_{n}]\) y \(\mathbf{A}\models\varphi_{2}[a_{1},....,a_{n}]\) o \(\mathbf{A}\not\models\varphi_{1}[a_{1},....,a_{n}]\) y \(\mathbf{A}\not\models\varphi_{2}[a_{1},....,a_{n}]\)
adhocprefix(7)adhocsufix Si \(\varphi=\lnot\varphi_{1},\) entonces
adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\) si y solo si \(\mathbf{A}\not\models\varphi_{1}[a_{1},....,a_{n}]\)
adhocprefix(8)adhocsufix Si \(\varphi=\forall v_{j}\varphi_{1},\) entonces
adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\) si y solo si \(\mathbf{A}\models\varphi_{1}[a_{1},....,a_{j-1},a,a_{j+1},...,a_{n}],\) para todo \(a\in A.\)
adhocprefix(9)adhocsufix Si \(\varphi=\forall v\varphi_{1},\) con \(v\not\in\{v_{1},...,v_{n}\}\), entonces
adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\) si y solo si \(\mathbf{A}\models\varphi_{1}[a_{1},....,a_{n},a]\), para todo \(a\in A.\)
adhocprefix(10)adhocsufix Si \(\varphi=\exists v_{j}\varphi_{1}\), entonces
adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\) si y solo si \(\mathbf{A}\models\varphi_{1}[a_{1},....,a_{j-1},a,a_{j+1},...,a_{n}]\), para algún \(a\in A.\)
adhocprefix(11)adhocsufix Si \(\varphi=\exists v\varphi_{1}\), con \(v\not\in\{v_{1},...,v_{n}\}\), entonces
adhocprefix-adhocsufix \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\) si y solo si \(\mathbf{A}\models\varphi_{1}[a_{1},....,a_{n},a]\), para algún \(a\in A.\)
Proof. Rutina.
Note que en el caso \(n=0\) las opciones (8) y (10) no pueden suceder.
7.3. Supongamos \(\psi=_{d}\psi(v)\) y sea \(\mathbf{A}\) una estructura de tipo \(\tau\). Entonces
adhocprefix(a)adhocsufix \(\mathbf{A}\models\exists v\psi(v)\) si y solo si existe \(a\in A\) tal que \(\mathbf{A}\models\psi[a]\)
adhocprefix(b)adhocsufix \(\mathbf{A}\models\forall v\psi(v)\) si y solo si para cada \(a\in A\) se tiene que \(\mathbf{A}\models\psi[a]\)
Proof. (a) Sea \(\varphi=\exists v\psi(v)\). Declaremos \(\varphi=_{d}\varphi()\). Por el caso (11) del lema de anterior (aplicado a esta última declaración) tenemos que se da \(\mathbf{A}\models\varphi[]\) si y solo si existe \(a\in A\) tal que \(\mathbf{A}\models\psi[a]\). Pero nótese que las definiciones de \(\mathbf{A}\models\varphi[]\) y de \(\mathbf{A}\models\varphi\) coinciden.