Introduciremos una notacion que hace mas dinamica e intuitiva la manera de escribir las cosas. Por supuesto el precio que esto tiene es que deberemos dedicarnos bastante a aprender a manejar esta notacion en forma precisa, para no perder rigor matematico.
Si \(t\) es un termino de tipo \(\tau\), entonces escribiremos \(t=_{d}t(v_{1},...,v_{n})\) para declarar que \(v_{1},...,v_{n}\) son variables distintas (con \(n\geq1\)) y tales que toda variable que ocurre en \(t\) pertenece a \(\{v_{1},...,v_{n}\}\) (no necesariamente toda \(v_{j}\) debe ocurrir en \(t\)).
El uso de declaraciones de la forma \(t=_{d}t(v_{1},...,v_{n})\) sera muy util cuando se lo convina con ciertas convenciones notacionales que describiremos a continuacion.
adhocprefixConvencion Notacional 1:adhocsufix Cuando hayamos hecho la declaracion \(t=_{d}t(v_{1},...,v_{n})\), si \(P_{1},...,P_{n}\) son palabras cualesquiera (no necesariamente terminos), entonces \(t(P_{1},...,P_{n})\) denotara la palabra que resulta de reemplazar simultaneamente cada ocurrencia de \(v_{1}\) en \(t\), por \(P_{1}\), cada ocurrencia de \(v_{2}\) en \(t\), por \(P_{2}\), etc.
Notese que cuando las palabras \(P_{i}^{\prime}s\) son terminos, \(t(P_{1},...,P_{n})\) es un termino (Lema 7.7). Ademas notese que en esta convencion notacional, el orden de las variables \(v_{1},...,v_{n}\) es clave. Por ejemplo si \(\tau=(\emptyset,\{\mathrm{FU}\},\emptyset,\{(\mathrm{FU},2)\})\) y \(t=\mathrm{FU}(\mathrm{FU}(x_{2},x_{16}),x_{3})\) y declaramos \(t=_{d}t(x_{3},x_{2},x_{16})\), entonces
adhocprefix-adhocsufix Si declaramos \(t=_{d}t(x_{3},x_{2},x_{16})\), entonces \(t(\#\#,\blacktriangle\#\blacktriangle,@@)\) denotara 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,@@)\) denotara la palabra \(\mathrm{FU}(\mathrm{FU}(@@,\#\#),\blacktriangle\#\blacktriangle)\)
Tambien podriamos haber declarado \(t=_{d}t(x_{3},x_{200},x_{2},x_{16},x_{100})\) y en tal caso \(t(\#\#,!!!!,\blacktriangle\#\blacktriangle,@@,!!)\) denotara la palabra \(\mathrm{FU}(\mathrm{FU}(\blacktriangle\#\blacktriangle,@@),\#\#)\)
adhocprefixConvencion Notacional 2:adhocsufix 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 asignacion tal que a cada \(v_{i}\) le asigna el valor \(a_{i}\). (Notese que esta notacion es inhambigua gracias al Lema 7.13.)
Nuevamente cabe destacar que en esta convencion notacional, 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\}\) 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\)
Tambien podriamos 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 establecer nuestra Convencion Notacional 3, debemos antes probar un lema de "lectura de terminos declarados", el cual sera muy util para hacer demostraciones usando la notacion declaratoria.
7.24 ([Lectura unica de terminos 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 algun \(c\in\mathcal{C}\)
adhocprefix(2)adhocsufix \(t=v_{j},\) para algun \(j\)
adhocprefix(3)adhocsufix \(t=f(t_{1},...,t_{m})\), con \(f\in\mathcal{F}_{m}\) y \(t_{1},...,t_{m}\in T^{\tau}\) unicos y tales que las variables que ocurren en cada uno de ellos estan en \(\{v_{1},...,v_{n}\}\)
Proof. Rutina
adhocprefixConvencion Notacional 3:adhocsufix Cuando hayamos declarado \(t=_{d}t(v_{1},...,v_{n})\) y se el caso (3) del Lema 7.24 supondremos tacitamente que tambien hemos hecho las declaraciones \(t_{1}=_{d}t_{1}(v_{1},...,v_{n}),...,t_{m}=_{d}t_{m}(v_{1},...,v_{n})\).
Cabe destacar que esta ultima convencion notacional junto con la Convencion Notacional 1, nos dice que cuando se de el caso (3) del Lema 7.24, si \(P_{1},...,P_{n}\) son palabras cualesquiera, entonces \[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 Convencion Notacional 3 y nos permite darle caracter recursivo a la notacion \(t^{\mathbf{A}}[a_{1},....,a_{n}]\). Esto sera muy util para hacer demostraciones usando la notacion declaratoria.
7.25 ([Caracter recursivo de la notacion \(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 asignacion 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}\]
Si \(\varphi\) es una formula de tipo \(\tau\), entonces escribiremos \(\varphi=_{d}\varphi(v_{1},...,v_{n})\) para declarar que \(v_{1},...,v_{n}\) son variables distintas (con \(n\geq1\)) tales que \(Li(\varphi)\subseteq\{v_{1},...,v_{n}\}\). Tal como para el caso de terminos, el uso de declaraciones de la forma \(\varphi=_{d}\varphi(v_{1},...,v_{n})\) sera muy util cuando se convina con ciertas convenciones notacionales que describiremos a continuacion.
adhocprefixConvencion Notacional 4:adhocsufix Cuando hayamos hecho la declaracion \(\varphi=_{d}\varphi(v_{1},...,v_{n})\), si \(P_{1},...,P_{n}\) son palabras cualesquiera, entonces \(\varphi(P_{1},...,P_{n})\) denotara la palabra que resulta de reemplazar simultaneamente cada ocurrencia libre de \(v_{1}\) en \(\varphi\), por \(P_{1}\), cada ocurrencia libre de \(v_{2}\) en \(\varphi\), por \(P_{2}\), etc.
Notese que cuando las palabras \(P_{i}^{\prime}s\) son terminos, \(\varphi(P_{1},...,P_{n})\) es una formula. Ademas notese que tal como para el caso de terminos, en esta convencion notacional, el orden de las variables \(v_{1},...,v_{n}\) es clave. Es facil dar el ejemplo analogo al dado para terminos.
adhocprefixConvencion Notacional 5:adhocsufix 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 asignacion tal que a cada \(v_{i}\) le asigna el valor \(a_{i}\). (Notese que esta definicion es inambigua gracias al Lema 7.14). 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 convencion 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]\)
Para establecer nuestra Convencion Notacional 6, debemos antes enunciar un "lema de lectura unica de formulas declaradas".
7.26 ([Lectura unica de formulas declaradas). Sea \(\tau\) un tipo cualquiera y \(\varphi\in F^{\tau}\). Supongamos \(\varphi=_{d}\varphi(v_{1},...,v_{n})\). Entonces se una y solo una de las siguientes:
adhocprefix(1)adhocsufix \(\varphi=(t\equiv s)\), con \(t,s\in T^{\tau}\), unicos y tales que las variables que ocurren en \(t\) o en \(s\) estan todas en \(\{v_{1},...,v_{n}\}\)
adhocprefix(2)adhocsufix \(\varphi=r(t_{1},...,t_{m})\), con \(r\in\mathcal{R}_{m}\) y \(t_{1},...,t_{m}\in T^{\tau}\), unicos y tales que las variables que ocurren en cada \(t_{i}\) estan todas en \(\{v_{1},...,v_{n}\}\)
adhocprefix(3)adhocsufix \(\varphi=(\varphi_{1}\wedge\varphi_{2})\), con \(\varphi_{1},\varphi_{2}\in F^{\tau}\), unicas y tales que \(Li(\varphi_{1})\cup Li(\varphi_{2})\subseteq\{v_{1},...,v_{n}\}\)
adhocprefix(4)adhocsufix \(\varphi=(\varphi_{1}\vee\varphi_{2})\), con \(\varphi_{1},\varphi_{2}\in F^{\tau}\), unicas y tales que \(Li(\varphi_{1})\cup Li(\varphi_{2})\subseteq\{v_{1},...,v_{n}\}\)
adhocprefix(5)adhocsufix \(\varphi=(\varphi_{1}\rightarrow\varphi_{2})\), con \(\varphi_{1},\varphi_{2}\in F^{\tau}\), unicas y tales que \(Li(\varphi_{1})\cup Li(\varphi_{2})\subseteq\{v_{1},...,v_{n}\}\)
adhocprefix(6)adhocsufix \(\varphi=(\varphi_{1}\leftrightarrow\varphi_{2})\), con \(\varphi_{1},\varphi_{2}\in F^{\tau}\), unicas y tales que \(Li(\varphi_{1})\cup Li(\varphi_{2})\subseteq\{v_{1},...,v_{n}\}\)
adhocprefix(7)adhocsufix \(\varphi=\lnot\varphi_{1}\), con \(\varphi_{1}\in F^{\tau}\), unica y tal que \(Li(\varphi_{1})\subseteq\{v_{1},...,v_{n}\}\)
adhocprefix(8)adhocsufix \(\varphi=\forall v_{j}\varphi_{1}\), con \(v_{j}\in\{v_{1},...,v_{n}\}\) y \(\varphi_{1}\in F^{\tau}\), unicas y tales que \(Li(\varphi_{1})\subseteq\{v_{1},...,v_{n}\}\)
adhocprefix(9)adhocsufix \(\varphi=\forall v\varphi_{1}\), con \(v\in Var-\{v_{1},...,v_{n}\}\) y \(\varphi_{1}\in F^{\tau}\), unicas y tales que \(Li(\varphi_{1})\subseteq\{v_{1},...,v_{n},v\}\)
adhocprefix(10)adhocsufix \(\varphi=\exists v_{j}\varphi_{1}\), con \(v_{j}\in\{v_{1},...,v_{n}\}\) y \(\varphi_{1}\in F^{\tau}\), unicas y tales que \(Li(\varphi_{1})\subseteq\{v_{1},...,v_{n}\}\)
adhocprefix(11)adhocsufix \(\varphi=\exists v\varphi_{1}\), con \(v\in Var-\{v_{1},...,v_{n}\}\) y \(\varphi_{1}\in F^{\tau}\), unicas y tales que \(Li(\varphi_{1})\subseteq\{v_{1},...,v_{n},v\}\)
Proof. Ejercicio (haga induccion en el \(k\) tal que \(\varphi\in F_{k}^{\tau}\)).
adhocprefixConvencion Notacional 6:adhocsufix Cuando hayamos declarado \(\varphi=_{d}\varphi(v_{1},...,v_{n})\), entonces:
adhocprefix-adhocsufix si se da el caso (1) del Lema 7.26, supondremos tacitamente que tambien hemos hecho las declaraciones \(t=_{d}t(v_{1},...,v_{n})\) y \(s=_{d}s(v_{1},...,v_{n})\).
adhocprefix-adhocsufix si se da el caso (2) del Lema 7.26, supondremos tacitamente que tambien hemos hecho las declaraciones \(t_{1}=_{d}t_{1}(v_{1},...,v_{n}),...,t_{m}=_{d}t_{m}(v_{1},...,v_{n})\).
adhocprefix-adhocsufix si se da cualquiera de los casos (3), (4), (5) o (6) del Lema 7.26, supondremos tacitamente que tambien hemos hecho las declaraciones \(\varphi_{1}=_{d}\varphi_{1}(v_{1},...,v_{n})\) y \(\varphi_{2}=_{d}\varphi_{2}(v_{1},...,v_{n})\).
adhocprefix-adhocsufix si se da cualquiera de los casos (7), (8) o (10) del Lema 7.26, supondremos tacitamente que tambien hemos hecho la declaracion \(\varphi_{1}=_{d}\varphi_{1}(v_{1},...,v_{n})\).
adhocprefix-adhocsufix si se da el caso (9) o el caso (11) del Lema 7.26, supondremos tacitamente que tambien hemos hecho la declaracion \(\varphi_{1}=_{d}\varphi_{1}(v_{1},...,v_{n},v)\).
El siguiente lema se basa en la Convencion Notacional 6 y nos permite darle caracter recursivo a la notacion \(\mathbf{A}\models\varphi[a_{1},....,a_{n}]\). Esto sera muy util para hacer demostraciones usando la notacion declaratoria.
7.27 (Caracter recursivo de la notacion \(\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,...,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,...,a_{n}]\), para algun \(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 algun \(a\in A.\)
Proof. Rutina.