Dos nombres para la misma relación

El enunciado, textual: «Sea $\tau$ el tipo $(\varnothing ,\varnothing ,\{\mathrm{R1},\mathrm{R2}\},\{(\mathrm{R1},2),(\mathrm{R2},2)\})$. Sea $\phi {=}_d\phi (v_1,\dots ,v_n)\in F^{\tau }$ y sea ${\phi }^{\prime }$ el resultado de reemplazar cada ocurrencia de la palabra $\mathrm{R1}$ en $\phi$ por la palabra $\mathrm{R2}$. Acepte como demostrado que ${\phi }^{\prime }\in F^{\tau }$ y $\mathrm{Li}({\phi }^{\prime })=\mathrm{Li}(\phi )$. Declaremos ${\phi }^{\prime }{=}_d{\phi }^{\prime }(v_1,\dots ,v_n)$. Pruebe que si $𝐀=(A,i)$ es una estructura de tipo $\tau$ tal que $i(\mathrm{R1})=i(\mathrm{R2})$, entonces $𝐀\models \phi [a_1,a_2,\dots ,a_n]$ si y solo si $𝐀\models {\phi }^{\prime }[a_1,a_2,\dots ,a_n]$ cualesquiera sean $a_1,a_2,\dots ,a_n\in A$.» Es el Ejercicio 33 de la Guía 11.

Está enunciado con ${=}_d$: se resuelve dentro de la notación declaratoria, con los lemas y convenciones de la sección «Manejo técnico de la notación declaratoria» de la Guía 11. Lo que la consigna da por aceptado —que ${\phi }^{\prime }$ es fórmula y tiene las mismas variables libres— no se prueba.

01 · Qué dice, antes de probar

El tipo tiene dos nombres de relación binaria y nada más: ni constantes ni funciones, así que los términos son sólo variables. Si la estructura interpreta los dos nombres con la misma relación, da lo mismo escribir uno u otro: cambiar $\mathrm{R1}$ por $\mathrm{R2}$ en todos lados no cambia la verdad de la fórmula en ningún $[a_1,\dots ,a_n]$.

Un ejemplo. Sea $A=\{1,2,3\}$ con $i(\mathrm{R1})=i(\mathrm{R2})=\{(a,b):a\le b\}$, y sea

$$\phi =\forall x_2(\mathrm{R1}(x_1,x_2)\to \exists x_1\mathrm{R2}(x_2,x_1))$$

declarada $\phi {=}_d\phi (x_1)$. Entonces ${\phi }^{\prime }=\forall x_2(\mathrm{R2}(x_1,x_2)\to \exists x_1\mathrm{R2}(x_2,x_1))$, y como las dos relaciones son la misma, $\phi$ y ${\phi }^{\prime }$ dicen lo mismo: «todo lo que está arriba de $a_1$ tiene algo arriba», verdadero en los tres elementos. Si en cambio $i(\mathrm{R2})$ fuera el orden estricto $\{(a,b):a<b\}$, las dos fórmulas se separan en $a_1=3$: $\phi [3]$ es falsa y ${\phi }^{\prime }[3]$ es verdadera. La hipótesis $i(\mathrm{R1})=i(\mathrm{R2})$ es lo que lo impide.

El ejemplo ya muestra lo que va a importar en la prueba. La fórmula tiene un $\forall x_2$ con $x_2$ que no está en la declaración, y adentro un $\exists x_1$ con $x_1$ que sí está: son los casos (6) y (5) del Lema 4, y se tratan distinto.

02 · Las herramientas

Los lemas y las convenciones de la sección «Manejo técnico de la notación declaratoria» son lo que el encabezado de la lista manda usar en los ejercicios 21 a 30: se enuncian y se citan. Lo que haga falta de otra parte —acá, dónde puede ocurrir $\mathrm{R1}$— se enuncia y se prueba.

La Regla de Inducción desde 0, con $F_k^{\tau }$, las fórmulas de nivel $k$: $F_0^{\tau }$ son las atómicas, los $F_k^{\tau }$ crecen con $k$, y toda fórmula está en alguno. Si se prueba ${\mathrm{Enu}}_0$ y que ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$, vale ${\mathrm{Enu}}_k$ para todo $k$.

Lema 4 de la Guía 11, p. 9 (lectura única de fórmulas declaradas). Si $\phi \in F^{\tau }$ y $\phi {=}_d\phi (v_1,\dots ,v_n)$, se da una y sólo una de:

1. $\phi =(t\equiv s)$, con $t,s\in T^{\tau }$ únicos;
2. $\phi =r(t_1,\dots ,t_m)$, con $r\in {ℛ}_m$ y $t_1,\dots ,t_m\in T^{\tau }$ únicos;
3. $\phi =({\phi }_1\eta {\phi }_2)$, con $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$ y ${\phi }_1,{\phi }_2\in F^{\tau }$ únicas;
4. $\phi =\neg {\phi }_1$, con ${\phi }_1\in F^{\tau }$ única;
5. $\phi =Q{v}_j{\phi }_1$, con $Q\in \{\forall ,\exists \}$, $j\in \{1,\dots ,n\}$ y ${\phi }_1\in F^{\tau }$ únicas;
6. $\phi =Qv{\phi }_1$, con $Q\in \{\forall ,\exists \}$, $v\in \mathrm{Var}-\{v_1,\dots ,v_n\}$ y ${\phi }_1\in F^{\tau }$ únicas.

Más aún, si $\phi \in F_{k+1}^{\tau }$, en el caso (3) ${\phi }_1$ y ${\phi }_2$ están en $F_k^{\tau }$, y en los casos (4), (5) y (6) ${\phi }_1$ está en $F_k^{\tau }$. Es un teorema de lectura única.

Convención Notacional 6 de la Guía 11, p. 10. Si $\phi {=}_d\phi (v_1,\dots ,v_n)$, se suponen hechas: en el caso (1), $t{=}_{d}t(v_1,\dots ,v_n)$ y $s{=}_{d}s(v_1,\dots ,v_n)$; en el (2), $t_j{=}_d{t}_j(v_1,\dots ,v_n)$ para cada $j$; en el (3), ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n)$ y ${\phi }_2{=}_d{\phi }_2(v_1,\dots ,v_n)$; en el (4) y el (5), ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n)$; y en el (6), ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n,v)$, con una variable más.

Lema 6 de la Guía 11, p. 11 (carácter recursivo de $𝐀\models \phi [a_1,\dots ,a_n]$). La guía lo acepta sin prueba. Si $\phi {=}_d\phi (v_1,\dots ,v_n)$, $𝐀=(A,i)$ es un modelo de tipo $\tau$ y $a_1,\dots ,a_n\in A$, escribiendo $\overrightarrow{a}$ por $a_1,\dots ,a_n$:

1. si $\phi =(t\equiv s)$: $𝐀\models \phi [\overrightarrow{a}]$ sii $t^{𝐀}[\overrightarrow{a}]=s^{𝐀}[\overrightarrow{a}]$;
2. si $\phi =r(t_1,\dots ,t_m)$: $𝐀\models \phi [\overrightarrow{a}]$ sii $(t_1^{𝐀}[\overrightarrow{a}],\dots ,t_m^{𝐀}[\overrightarrow{a}])\in r^{𝐀}$;
3. si $\phi =({\phi }_1\wedge {\phi }_2)$: $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$;
4. si $\phi =({\phi }_1\vee {\phi }_2)$: $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$;
5. si $\phi =({\phi }_1\to {\phi }_2)$: $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models {\phi }_2[\overrightarrow{a}]$ o $𝐀⊭{\phi }_1[\overrightarrow{a}]$;
6. si $\phi =({\phi }_1\leftrightarrow {\phi }_2)$: $𝐀\models \phi [\overrightarrow{a}]$ sii ya sea $𝐀\models {\phi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$, o $𝐀⊭{\phi }_1[\overrightarrow{a}]$ y $𝐀⊭{\phi }_2[\overrightarrow{a}]$;
7. si $\phi =\neg {\phi }_1$: $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀⊭{\phi }_1[\overrightarrow{a}]$;
8. si $\phi =\forall v_j{\phi }_1$: $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[a_1,\dots ,a_{j-1},a,a_{j+1},\dots ,a_n]$ para todo $a\in A$;
9. si $\phi =\forall v{\phi }_1$ con $v\notin \{v_1,\dots ,v_n\}$: $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[a_1,\dots ,a_n,a]$ para todo $a\in A$;
10. si $\phi =\exists v_j{\phi }_1$: $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[a_1,\dots ,a_{j-1},a,a_{j+1},\dots ,a_n]$ para algún $a\in A$;
11. si $\phi =\exists v{\phi }_1$ con $v\notin \{v_1,\dots ,v_n\}$: $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[a_1,\dots ,a_n,a]$ para algún $a\in A$.

$r^{𝐀}$ es $i(r)$. Cada cláusula se usa dos veces: una para $\phi$ y otra para ${\phi }^{\prime }$.

De la definición de tipo, en la Guía 9: los nombres de relación son palabras sobre un alfabeto en el que no hay paréntesis, coma, $\equiv$, $\neg$, nexos, cuantificadores, la $X$ de las variables ni numerales itálicos o negritas; y ningún nombre de relación es subpalabra propia de otro.

03 · La mariposa: el reemplazo se reparte y la lista crece

La afirmación es para toda fórmula, así que la prueba es por la Regla de Inducción desde 0 en el nivel de $\phi$. Antes de escribir ${\mathrm{Enu}}_k$ hay que contestar dos preguntas: cómo queda ${\phi }^{\prime }$ en cada caso del Lema 4, y con qué declaración queda cada pieza.

Cómo queda ${\phi }^{\prime }$. Los símbolos de $\mathrm{R1}$ no aparecen en una variable, ni son paréntesis, nexos, $\neg$ ni cuantificadores. Entonces una ocurrencia de $\mathrm{R1}$ en $({\phi }_1\eta {\phi }_2)$ no toca el «(», la $\eta$ ni el «)», y cae entera adentro de ${\phi }_1$ o de ${\phi }_2$; reemplazarlas todas en $\phi$ es reemplazarlas todas en ${\phi }_1$ y todas en ${\phi }_2$. Caso por caso:

• $\phi =(t\equiv s)$ da ${\phi }^{\prime }=\phi$: $t$ y $s$ son variables, y no hay ningún $\mathrm{R1}$.
• $\phi =\mathrm{R1}(t_1,t_2)$ da ${\phi }^{\prime }=\mathrm{R2}(t_1,t_2)$; $\phi =\mathrm{R2}(t_1,t_2)$ da ${\phi }^{\prime }=\phi$.
• $\phi =({\phi }_1\eta {\phi }_2)$ da ${\phi }^{\prime }=({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$.
• $\phi =\neg {\phi }_1$ da ${\phi }^{\prime }=\neg {\phi }_1^{\prime }$.
• $\phi =Q{v}_j{\phi }_1$ da ${\phi }^{\prime }=Q{v}_j{\phi }_1^{\prime }$, y $\phi =Qv{\phi }_1$ da ${\phi }^{\prime }=Qv{\phi }_1^{\prime }$.

Donde ${\phi }_1^{\prime }$ es el resultado de reemplazar cada $\mathrm{R1}$ de ${\phi }_1$ por $\mathrm{R2}$. Por lo que la consigna acepta, aplicado a ${\phi }_1$ —que está declarada por la Convención 6—, ${\phi }_1^{\prime }\in F^{\tau }$ y $\mathrm{Li}({\phi }_1^{\prime })=\mathrm{Li}({\phi }_1)$: se la puede declarar con la misma lista que ${\phi }_1$. Y por la unicidad del Lema 4 aplicado a ${\phi }^{\prime }{=}_d{\phi }^{\prime }(v_1,\dots ,v_n)$, las piezas de ${\phi }^{\prime }$ son estas ${\phi }_1^{\prime }$, con las declaraciones que les da la Convención 6.

Qué va adentro de ${\mathrm{Enu}}_k$, y por qué $n$ también. En el caso (6), $\phi =\forall v{\phi }_1$ con $v$ fuera de la lista, la Convención 6 declara ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n,v)$: una variable más. Para usar la hipótesis inductiva en ${\phi }_1$, ${\mathrm{Enu}}_k$ tiene que valer para cualquier declaración, de cualquier largo. Si ${\mathrm{Enu}}_k$ fijara $n$ y $v_1,\dots ,v_n$, no diría nada de ${\phi }_1$. Y los elementos también van adentro: en el caso (5) la cláusula (8) del Lema 6 cambia $a_j$ por un $a$ cualquiera, y en el (6) la (9) agrega un $a$ al final.

Dónde trabaja la hipótesis. En un solo lugar: la atómica $\mathrm{R1}(t_1,t_2)$, que pasa a $\mathrm{R2}(t_1,t_2)$. Por el Lema 6 (2) una es verdadera sii $(t_1^{𝐀}[\overrightarrow{a}],t_2^{𝐀}[\overrightarrow{a}])\in i(\mathrm{R1})$ y la otra sii está en $i(\mathrm{R2})$, y las dos relaciones son la misma. Todo lo demás es la misma cláusula del Lema 6 de los dos lados, con la hipótesis inductiva en el medio.

Abajo, una fórmula desarmada con el Lema 4 hasta las atómicas, cada pieza con la declaración que le da la Convención 6, y en cuántas tuplas de esa declaración coinciden la pieza y su reemplazo. Arranca con $i(\mathrm{R2})\ne i(\mathrm{R1})$.

Con $i(\mathrm{R2})=i(\mathrm{R1})$ coinciden todas las piezas, en todas las tuplas: es el teorema, pieza por pieza, como lo recorre la inducción. Con las relaciones distintas, la diferencia nace siempre en una atómica $\mathrm{R1}(t_1,t_2)$ y sube o no. En la tercera fórmula sube hasta las dos mitades de la conjunción, que difieren en las mismas tuplas, y ahí se pierde: $\phi$ y ${\phi }^{\prime }$ coinciden en los tres elementos aunque las relaciones sean distintas. La vuelta del teorema no vale.

04 · El escarabajo: la prueba escrita

Hecho (dónde está $\mathrm{R1}$). Sean $v_1,\dots ,v_n$ variables distintas, $\phi {=}_d\phi (v_1,\dots ,v_n)\in F^{\tau }$ y, para cada fórmula $\psi$, ${\psi }^{\prime }$ el resultado de reemplazar cada ocurrencia de $\mathrm{R1}$ en $\psi$ por $\mathrm{R2}$. Según el caso del Lema 4 en que esté $\phi$: (1) si $\phi =(t\equiv s)$, ${\phi }^{\prime }=\phi$; (2) si $\phi =\mathrm{R1}(t_1,t_2)$, ${\phi }^{\prime }=\mathrm{R2}(t_1,t_2)$, y si $\phi =\mathrm{R2}(t_1,t_2)$, ${\phi }^{\prime }=\phi$; (3) si $\phi =({\phi }_1\eta {\phi }_2)$, ${\phi }^{\prime }=({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$; (4) si $\phi =\neg {\phi }_1$, ${\phi }^{\prime }=\neg {\phi }_1^{\prime }$; (5) y (6) si $\phi =Qw{\phi }_1$, con $w$ una variable, ${\phi }^{\prime }=Qw{\phi }_1^{\prime }$.

Prueba. Como $\tau$ no tiene nombres de constante ni de función, $T_0^{\tau }=\mathrm{Var}$ y $T_{k+1}^{\tau }=T_k^{\tau }$ para todo $k$: los términos de tipo $\tau$ son las variables. Por la definición de tipo, ningún símbolo de $\mathrm{R1}$ es un paréntesis, la coma, $\equiv$, $\neg$, un nexo, un cuantificador, la $X$ ni un numeral itálico o negrita; en particular, ninguno aparece en una variable. Una ocurrencia de $\mathrm{R1}$ ocupa posiciones consecutivas, todas con símbolos de $\mathrm{R1}$.

• (1) Los símbolos de $(t\equiv s)$ son paréntesis, $\equiv$ y los de dos variables: ninguno es de $\mathrm{R1}$, así que $\mathrm{R1}$ no ocurre y ${\phi }^{\prime }=\phi$.
• (2) En $r(t_1,t_2)$ los únicos símbolos que pueden ser de $\mathrm{R1}$ son los de $r$, que ocupan las primeras $|r|$ posiciones; lo que sigue es «(», una variable, la coma, una variable y «)». Una ocurrencia de $\mathrm{R1}$ queda entonces dentro de esas $|r|$ posiciones. Si $r=\mathrm{R1}$, la única es la de $r$ entero, y ${\phi }^{\prime }=\mathrm{R2}(t_1,t_2)$. Si $r=\mathrm{R2}$, $\mathrm{R1}$ sería subpalabra de $\mathrm{R2}$, y como son distintas, subpalabra propia: la definición de tipo lo prohíbe. Luego $\mathrm{R1}$ no ocurre y ${\phi }^{\prime }=\phi$.
• (3) Una ocurrencia de $\mathrm{R1}$ en $({\phi }_1\eta {\phi }_2)$ no toca el primer «(», la $\eta$ ni el último «)», que no son símbolos de $\mathrm{R1}$. Un tramo de posiciones consecutivas que no toca la $\eta$ queda entero antes o entero después de ella: dentro de ${\phi }_1$ o dentro de ${\phi }_2$. Recíprocamente, toda ocurrencia de $\mathrm{R1}$ en ${\phi }_1$ o en ${\phi }_2$ es una ocurrencia en $\phi$. Reemplazarlas todas en $\phi$ es reemplazarlas todas en ${\phi }_1$ y todas en ${\phi }_2$: ${\phi }^{\prime }=({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$.
• (4), (5) y (6) Una ocurrencia de $\mathrm{R1}$ en $\neg {\phi }_1$ o en $Qw{\phi }_1$ no toca el $\neg$, el $Q$ ni los símbolos de $w$, así que cae dentro de ${\phi }_1$, que es un tramo final. Luego ${\phi }^{\prime }=\neg {\phi }_1^{\prime }$ y ${\phi }^{\prime }=Qw{\phi }_1^{\prime }$. ∎

Las declaraciones de las piezas. En los casos (3) a (6), cada pieza ${\phi }_i$ de $\phi$ está declarada por la Convención 6: con $(v_1,\dots ,v_n)$ en los casos (3), (4) y (5), y con $(v_1,\dots ,v_n,v)$ en el (6). Por lo aceptado en la consigna, aplicado a ${\phi }_i$, ${\phi }_i^{\prime }\in F^{\tau }$ y $\mathrm{Li}({\phi }_i^{\prime })=\mathrm{Li}({\phi }_i)$, así que ${\phi }_i^{\prime }$ admite la misma declaración que ${\phi }_i$. Por el Hecho, ${\phi }^{\prime }$ tiene la forma del mismo caso del Lema 4, con piezas ${\phi }_i^{\prime }$, y por la unicidad del Lema 4 aplicado a ${\phi }^{\prime }{=}_d{\phi }^{\prime }(v_1,\dots ,v_n)$, éstas son sus piezas; la Convención 6 aplicada a ${\phi }^{\prime }$ les da exactamente esas declaraciones. En el caso (6) ${\phi }^{\prime }$ también está en el caso (6), porque la variable cuantificada es la misma $v\notin \{v_1,\dots ,v_n\}$.

El ejercicio. Prueba. Usaremos la Regla de Inducción desde 0. Para cada $k\in \omega$ sea ${\mathrm{Enu}}_k$ el enunciado:

${\mathrm{Enu}}_k$: Sea $𝐀=(A,i)$ una estructura de tipo $\tau$ tal que $i(\mathrm{R1})=i(\mathrm{R2})$. Para todo $n\ge 0$ y todas las variables distintas $v_1,\dots ,v_n$: si $\phi \in F_k^{\tau }$, $\phi {=}_d\phi (v_1,\dots ,v_n)$, ${\phi }^{\prime }$ es el resultado de reemplazar cada ocurrencia de $\mathrm{R1}$ en $\phi$ por $\mathrm{R2}$ y declaramos ${\phi }^{\prime }{=}_d{\phi }^{\prime }(v_1,\dots ,v_n)$, entonces para cualesquiera $a_1,\dots ,a_n\in A$ se tiene que $𝐀\models \phi [a_1,\dots ,a_n]$ si y sólo si $𝐀\models {\phi }^{\prime }[a_1,\dots ,a_n]$.

Abreviamos $a_1,\dots ,a_n$ como $\overrightarrow{a}$.

• ${\mathrm{Enu}}_0$ es verdadero. Sean $𝐀$ como en el enunciado, $n\ge 0$, $v_1,\dots ,v_n$ distintas, $\phi \in F_0^{\tau }$ con $\phi {=}_d\phi (v_1,\dots ,v_n)$, ${\phi }^{\prime }{=}_d{\phi }^{\prime }(v_1,\dots ,v_n)$, y $a_1,\dots ,a_n\in A$. $\phi$ es atómica, así que por el Lema 4 de la Guía 11 está en el caso (1) o en el (2).
  • Si $\phi =(t\equiv s)$, por el Hecho ${\phi }^{\prime }=\phi$, y no hay nada que probar.
  • Si $\phi =\mathrm{R2}(t_1,t_2)$, por el Hecho ${\phi }^{\prime }=\phi$.
  • Si $\phi =\mathrm{R1}(t_1,t_2)$, por el Hecho ${\phi }^{\prime }=\mathrm{R2}(t_1,t_2)$. Por la Convención 6, $t_1{=}_d{t}_1(v_1,\dots ,v_n)$ y $t_2{=}_d{t}_2(v_1,\dots ,v_n)$, para $\phi$ y para ${\phi }^{\prime }$. Por el Lema 6 (2) de la Guía 11 aplicado a $\phi$, $𝐀\models \phi [\overrightarrow{a}]$ sii $(t_1^{𝐀}[\overrightarrow{a}],t_2^{𝐀}[\overrightarrow{a}])\in i(\mathrm{R1})$; como $i(\mathrm{R1})=i(\mathrm{R2})$, esto pasa sii $(t_1^{𝐀}[\overrightarrow{a}],t_2^{𝐀}[\overrightarrow{a}])\in i(\mathrm{R2})$, que por el Lema 6 (2) aplicado a ${\phi }^{\prime }$ es $𝐀\models {\phi }^{\prime }[\overrightarrow{a}]$.
• ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$. Supongamos ${\mathrm{Enu}}_k$. Sean $𝐀$ como en el enunciado, $n\ge 0$, $v_1,\dots ,v_n$ distintas, $\phi \in F_{k+1}^{\tau }$ con $\phi {=}_d\phi (v_1,\dots ,v_n)$, ${\phi }^{\prime }{=}_d{\phi }^{\prime }(v_1,\dots ,v_n)$, y $a_1,\dots ,a_n\in A$.
  • Caso $\phi \in F_k^{\tau }$. Vale por ${\mathrm{Enu}}_k$.
  • Caso $\phi \in F_{k+1}^{\tau }-F_k^{\tau }$. $\phi$ no es atómica, porque las atómicas están en $F_0^{\tau }\subseteq F_k^{\tau }$. Por el Lema 4, está en el caso (3), (4), (5) o (6), con sus piezas en $F_k^{\tau }$; por el Hecho y lo que sigue, ${\phi }^{\prime }$ está en el mismo caso, con las piezas ${\phi }_i^{\prime }$ declaradas como las ${\phi }_i$.
    • $\phi =({\phi }_1\eta {\phi }_2)$. Entonces ${\phi }^{\prime }=({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$, con ${\phi }_1,{\phi }_2\in F_k^{\tau }$, ${\phi }_i{=}_d{\phi }_i(v_1,\dots ,v_n)$ y ${\phi }_i^{\prime }{=}_d{\phi }_i^{\prime }(v_1,\dots ,v_n)$. Por ${\mathrm{Enu}}_k$ con el mismo $n$, las mismas variables y los mismos $a_1,\dots ,a_n$: $𝐀\models {\phi }_1[\overrightarrow{a}]$ sii $𝐀\models {\phi }_1^{\prime }[\overrightarrow{a}]$, y $𝐀\models {\phi }_2[\overrightarrow{a}]$ sii $𝐀\models {\phi }_2^{\prime }[\overrightarrow{a}]$. Negando los dos lados, también $𝐀⊭{\phi }_i[\overrightarrow{a}]$ sii $𝐀⊭{\phi }_i^{\prime }[\overrightarrow{a}]$.
      • Si $\eta =\wedge$: por el Lema 6 (3), $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$; por lo anterior, sii $𝐀\models {\phi }_1^{\prime }[\overrightarrow{a}]$ y $𝐀\models {\phi }_2^{\prime }[\overrightarrow{a}]$; por el Lema 6 (3) aplicado a ${\phi }^{\prime }$, sii $𝐀\models {\phi }^{\prime }[\overrightarrow{a}]$.
      • Si $\eta =\vee$: por el Lema 6 (4), $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$; sii $𝐀\models {\phi }_1^{\prime }[\overrightarrow{a}]$ o $𝐀\models {\phi }_2^{\prime }[\overrightarrow{a}]$; por el Lema 6 (4) aplicado a ${\phi }^{\prime }$, sii $𝐀\models {\phi }^{\prime }[\overrightarrow{a}]$.
      • Si $\eta =\to$: por el Lema 6 (5), $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models {\phi }_2[\overrightarrow{a}]$ o $𝐀⊭{\phi }_1[\overrightarrow{a}]$; sii $𝐀\models {\phi }_2^{\prime }[\overrightarrow{a}]$ o $𝐀⊭{\phi }_1^{\prime }[\overrightarrow{a}]$; por el Lema 6 (5) aplicado a ${\phi }^{\prime }$, sii $𝐀\models {\phi }^{\prime }[\overrightarrow{a}]$.
      • Si $\eta =\leftrightarrow$: por el Lema 6 (6), $𝐀\models \phi [\overrightarrow{a}]$ sii ($𝐀\models {\phi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$) o ($𝐀⊭{\phi }_1[\overrightarrow{a}]$ y $𝐀⊭{\phi }_2[\overrightarrow{a}]$); sii ($𝐀\models {\phi }_1^{\prime }[\overrightarrow{a}]$ y $𝐀\models {\phi }_2^{\prime }[\overrightarrow{a}]$) o ($𝐀⊭{\phi }_1^{\prime }[\overrightarrow{a}]$ y $𝐀⊭{\phi }_2^{\prime }[\overrightarrow{a}]$); por el Lema 6 (6) aplicado a ${\phi }^{\prime }$, sii $𝐀\models {\phi }^{\prime }[\overrightarrow{a}]$.
    • $\phi =\neg {\phi }_1$. Entonces ${\phi }^{\prime }=\neg {\phi }_1^{\prime }$, con ${\phi }_1\in F_k^{\tau }$, ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n)$ y ${\phi }_1^{\prime }{=}_d{\phi }_1^{\prime }(v_1,\dots ,v_n)$. Por el Lema 6 (7), $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀⊭{\phi }_1[\overrightarrow{a}]$; por ${\mathrm{Enu}}_k$, sii $𝐀⊭{\phi }_1^{\prime }[\overrightarrow{a}]$; por el Lema 6 (7) aplicado a ${\phi }^{\prime }$, sii $𝐀\models {\phi }^{\prime }[\overrightarrow{a}]$.
    • $\phi =\forall v_j{\phi }_1$, con $j\in \{1,\dots ,n\}$. Entonces ${\phi }^{\prime }=\forall v_j{\phi }_1^{\prime }$, con ${\phi }_1\in F_k^{\tau }$, ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n)$ y ${\phi }_1^{\prime }{=}_d{\phi }_1^{\prime }(v_1,\dots ,v_n)$. Por el Lema 6 (8), $𝐀\models \phi [\overrightarrow{a}]$ sii para todo $a\in A$, $𝐀\models {\phi }_1[a_1,\dots ,a_{j-1},a,a_{j+1},\dots ,a_n]$. Para cada $a$, ${\mathrm{Enu}}_k$ con el mismo $n$, las mismas variables y los elementos $a_1,\dots ,a_{j-1},a,a_{j+1},\dots ,a_n$ da que esto pasa sii $𝐀\models {\phi }_1^{\prime }[a_1,\dots ,a_{j-1},a,a_{j+1},\dots ,a_n]$. Por el Lema 6 (8) aplicado a ${\phi }^{\prime }$, eso para todo $a\in A$ es $𝐀\models {\phi }^{\prime }[\overrightarrow{a}]$.
    • $\phi =\exists v_j{\phi }_1$, con $j\in \{1,\dots ,n\}$. Igual que el anterior con el Lema 6 (10): $𝐀\models \phi [\overrightarrow{a}]$ sii para algún $a\in A$, $𝐀\models {\phi }_1[a_1,\dots ,a_{j-1},a,a_{j+1},\dots ,a_n]$; por ${\mathrm{Enu}}_k$ con esos elementos, sii para algún $a\in A$, $𝐀\models {\phi }_1^{\prime }[a_1,\dots ,a_{j-1},a,a_{j+1},\dots ,a_n]$; por el Lema 6 (10) aplicado a ${\phi }^{\prime }$, sii $𝐀\models {\phi }^{\prime }[\overrightarrow{a}]$.
    • $\phi =\forall v{\phi }_1$, con $v\notin \{v_1,\dots ,v_n\}$. Entonces ${\phi }^{\prime }=\forall v{\phi }_1^{\prime }$, con ${\phi }_1\in F_k^{\tau }$, y por la Convención 6, ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n,v)$ y ${\phi }_1^{\prime }{=}_d{\phi }_1^{\prime }(v_1,\dots ,v_n,v)$. Por el Lema 6 (9), $𝐀\models \phi [\overrightarrow{a}]$ sii para todo $a\in A$, $𝐀\models {\phi }_1[a_1,\dots ,a_n,a]$. Para cada $a$, ${\mathrm{Enu}}_k$ con $n+1$ en lugar de $n$, las variables distintas $v_1,\dots ,v_n,v$ y los elementos $a_1,\dots ,a_n,a$ da que esto pasa sii $𝐀\models {\phi }_1^{\prime }[a_1,\dots ,a_n,a]$. Por el Lema 6 (9) aplicado a ${\phi }^{\prime }$, eso para todo $a\in A$ es $𝐀\models {\phi }^{\prime }[\overrightarrow{a}]$.
    • $\phi =\exists v{\phi }_1$, con $v\notin \{v_1,\dots ,v_n\}$. Igual que el anterior con el Lema 6 (11): $𝐀\models \phi [\overrightarrow{a}]$ sii para algún $a\in A$, $𝐀\models {\phi }_1[a_1,\dots ,a_n,a]$; por ${\mathrm{Enu}}_k$ con $n+1$, $v_1,\dots ,v_n,v$ y $a_1,\dots ,a_n,a$, sii para algún $a\in A$, $𝐀\models {\phi }_1^{\prime }[a_1,\dots ,a_n,a]$; por el Lema 6 (11) aplicado a ${\phi }^{\prime }$, sii $𝐀\models {\phi }^{\prime }[\overrightarrow{a}]$.

Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ vale para todo $k\in \omega$. Sean ahora $\phi {=}_d\phi (v_1,\dots ,v_n)\in F^{\tau }$, ${\phi }^{\prime }$ declarada ${\phi }^{\prime }{=}_d{\phi }^{\prime }(v_1,\dots ,v_n)$, y $k$ tal que $\phi \in F_k^{\tau }$: por ${\mathrm{Enu}}_k$, $𝐀\models \phi [a_1,\dots ,a_n]$ sii $𝐀\models {\phi }^{\prime }[a_1,\dots ,a_n]$ cualesquiera sean $a_1,\dots ,a_n\in A$. ∎

05 · Lo que se lleva a otros ejercicios

Es el molde de toda inducción declaratoria en fórmulas. Lema 4 para los casos, Convención 6 para declarar las piezas, Lema 6 para evaluar, y ${\mathrm{Enu}}_k$ cuantificado sobre todas las declaraciones porque el caso (6) alarga la lista. El Ejercicio 29 (un isomorfismo no cambia ninguna verdad) y el (b) del Ejercicio 27 tienen exactamente estos once casos; cambia sólo qué pasa en las atómicas.

Es el gemelo del Ejercicio 8, que cambia un nombre de función por otro en un término, sin notación declaratoria y con asignaciones infinitas. Allá el reemplazo entra en los argumentos de un término; acá entra en las piezas de una fórmula y los términos quedan quietos.

Lo que hace perder puntos. Fijar $n$ y las variables afuera de ${\mathrm{Enu}}_k$: el caso (6) declara ${\phi }_1$ con $n+1$ variables y la hipótesis inductiva no se puede aplicar. Fijar los $a_1,\dots ,a_n$ afuera: los cuantificadores los cambian. No decir cómo queda ${\phi }^{\prime }$ en cada caso, o decirlo sin justificar que $\mathrm{R1}$ no puede cruzar un paréntesis, un nexo ni un cuantificador. Usar la Convención 6 para las piezas de ${\phi }^{\prime }$ sin decir que ${\phi }_1^{\prime }$ es fórmula y está declarada. Escribir «los demás nexos son análogos» sin las cuatro cláusulas: $\to$ y $\leftrightarrow$ usan $⊭$. Juntar los casos (5) y (6) del Lema 4, que usan cláusulas distintas del Lema 6. Y olvidar el caso $\phi =\mathrm{R2}(t_1,t_2)$, donde no se reemplaza nada.

Para tener a mano

1. ${\mathrm{Enu}}_k$: para toda $𝐀$ con $i(\mathrm{R1})=i(\mathrm{R2})$, todo $n$ y toda lista $v_1,\dots ,v_n$, toda $\phi \in F_k^{\tau }$ declarada con ella y todos $a_1,\dots ,a_n$: $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models {\phi }^{\prime }[\overrightarrow{a}]$.
2. ${\phi }^{\prime }$ caso por caso: $(t\equiv s)$ y $\mathrm{R2}(t_1,t_2)$ quedan iguales; $\mathrm{R1}(t_1,t_2)$ pasa a $\mathrm{R2}(t_1,t_2)$; $({\phi }_1^{\prime }\eta {\phi }_2^{\prime })$, $\neg {\phi }_1^{\prime }$, $Q{v}_j{\phi }_1^{\prime }$, $Qv{\phi }_1^{\prime }$. Porque $\mathrm{R1}$ no comparte símbolos con variables, paréntesis, nexos ni cuantificadores.
3. Las piezas: Convención 6 para las de $\phi$; lo aceptado da ${\phi }_i^{\prime }\in F^{\tau }$ con las mismas libres, y la unicidad del Lema 4 las hace piezas de ${\phi }^{\prime }$.
4. La hipótesis $i(\mathrm{R1})=i(\mathrm{R2})$ se usa una sola vez, en la atómica $\mathrm{R1}(t_1,t_2)$, con el Lema 6 (2).
5. Cuantificadores: (8) y (10) con $v_j$ en la lista, cambiando $a_j$; (9) y (11) con $v$ afuera, agregando $a$ y usando ${\mathrm{Enu}}_k$ con $n+1$.