El término que cambia vive en una atómica

La consigna, textual: «Supongamos $s,t\in T^{\tau }$. Sea $\gamma \in F^{\tau }$ y sea $\tilde{\gamma }$ = resultado de reemplazar en $\gamma$ una ocurrencia no contigua de $t$ por $s$. Nótese que por un lema de la Guía 9 tenemos que $\tilde{\gamma }\in F^{\tau }$. Supongamos $𝐀$ es una estructura de tipo $\tau$ tal que $t^{𝐀}[\overrightarrow{a}]=s^{𝐀}[\overrightarrow{a}]$, para cada $\overrightarrow{a}\in A^{𝐍}$. Pruebe que entonces $𝐀\models \gamma [\overrightarrow{a}]$ si y solo si $𝐀\models \tilde{\gamma }[\overrightarrow{a}]$ para cada $\overrightarrow{a}\in A^{𝐍}$. Puede usar el Ejercicio (7) de esta lista». Es el Ejercicio 15 de la Guía 10 (p. 10). Va sin notación declaratoria, con asignaciones infinitas.

01 · Qué dice, con un ejemplo

Es el Ejercicio 7 un piso más arriba: si dos términos valen siempre lo mismo, cambiar uno por el otro en una fórmula no cambia si es verdadera. Pero con dos condiciones que en el 7 no estaban. La ocurrencia tiene que ser no contigua, y la hipótesis pide que $t$ y $s$ valgan lo mismo en todas las asignaciones, no en una.

Contigua (Guía 9, p. 13): una ocurrencia de un término $t$ en una fórmula $\phi$ es contigua cuando no es a partir del primer símbolo de $\phi$ y el símbolo anterior a ella en $\phi$ es $\forall$ o $\exists$. Es la variable pegada a un cuantificador, y sólo una variable puede tener una ocurrencia así.

Un ejemplo en el tipo de los reticulados terna, $\tau =(\varnothing ,\{\mathrm{s},\mathrm{i}\},\varnothing ,\{(\mathrm{s},2),(\mathrm{i},2)\})$, con $𝐀$ de universo $\{1,2,3,6\}$, $i(\mathrm{s})$ el mínimo común múltiplo e $i(\mathrm{i})$ el máximo común divisor. Sean $t=\mathrm{X}1$ y $s=\mathrm{s}(\mathrm{X}1,\mathrm{X}1)$: como $\mathrm{mcm}(a_1,a_1)=a_1$, vale $t^{𝐀}[\overrightarrow{a}]=s^{𝐀}[\overrightarrow{a}]$ para cada $\overrightarrow{a}$. En la fórmula de 26 símbolos

$$\gamma =((\mathrm{X}1\equiv \mathrm{X}2)\wedge \forall \mathrm{X}1(\mathrm{i}(\mathrm{X}1,\mathrm{X}2)\equiv \mathrm{X}1))$$

$\mathrm{X}1$ ocurre a partir de 3, 11, 16 y 23, y la de 11 es la contigua. Con $\overrightarrow{a}=(6,6,6,\dots )$, $𝐀\models \gamma [\overrightarrow{a}]$: $a_1=a_2$, y todo $x$ cumple $\mathrm{mcd}(x,6)=x$. Reemplazar la ocurrencia de 3, la de 16 o la de 23 por $\mathrm{s}(\mathrm{X}1,\mathrm{X}1)$ da fórmulas que también son verdaderas en $\overrightarrow{a}$. Reemplazar la de 11 da

$$((\mathrm{X}1\equiv \mathrm{X}2)\wedge \forall \mathrm{s}(\mathrm{X}1,\mathrm{X}1)(\mathrm{i}(\mathrm{X}1,\mathrm{X}2)\equiv \mathrm{X}1))$$

que no es una fórmula: después de $\forall$ tiene que venir una variable.

Por qué en todas las asignaciones. Con $s=\mathrm{X}2$, la igualdad $t^{𝐀}[\overrightarrow{a}]=s^{𝐀}[\overrightarrow{a}]$ dice $a_1=a_2$, y vale en $(6,6,6,\dots )$ pero no en todas. Reemplazar la ocurrencia de 16, la que está adentro del $\forall \mathrm{X}1$, da

$$((\mathrm{X}1\equiv \mathrm{X}2)\wedge \forall \mathrm{X}1(\mathrm{i}(\mathrm{X}2,\mathrm{X}2)\equiv \mathrm{X}1))$$

que en $(6,6,6,\dots )$ es falsa: dice que todo $x$ es igual a 6. La ocurrencia de 16 no se evalúa en $\overrightarrow{a}$, sino en ${\downarrow }_1^x(\overrightarrow{a})$ para cada $x\in A$, y ahí $a_1$ pasa a ser $x$, que no siempre es 6.

02 · Las herramientas

La relación $\models$ (Guía 10, p. 4). Dados $𝐀$ de tipo $\tau$ y $\overrightarrow{a}\in A^{𝐍}$: (1) $𝐀\models (u_1\equiv u_2)[\overrightarrow{a}]$ sii $u_1^{𝐀}[\overrightarrow{a}]=u_2^{𝐀}[\overrightarrow{a}]$; (2) $𝐀\models r(u_1,\dots ,u_m)[\overrightarrow{a}]$ sii $(u_1^{𝐀}[\overrightarrow{a}],\dots ,u_m^{𝐀}[\overrightarrow{a}])\in i(r)$; (3) $𝐀\models ({\phi }_1\wedge {\phi }_2)[\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$; (4) con $\vee$, sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$; (5) con $\to$, sii $𝐀⊭{\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$; (6) con $\leftrightarrow$, sii valen las dos o no vale ninguna; (7) $𝐀\models \neg {\phi }_1[\overrightarrow{a}]$ sii $𝐀⊭{\phi }_1[\overrightarrow{a}]$; (8) $𝐀\models \forall x_j{\phi }_1[\overrightarrow{a}]$ sii para cada $a\in A$, $𝐀\models {\phi }_1[{\downarrow }_j^a(\overrightarrow{a})]$; (9) $𝐀\models \exists x_j{\phi }_1[\overrightarrow{a}]$ sii hay un $a\in A$ tal que $𝐀\models {\phi }_1[{\downarrow }_j^a(\overrightarrow{a})]$. Acá ${\downarrow }_j^a(\overrightarrow{a})$ es la asignación que resulta de reemplazar en $\overrightarrow{a}$ el $j$-ésimo elemento por $a$. Los términos de las atómicas se llaman $u_j$ para no confundirlos con los $t$ y $s$ del ejercicio.

Los niveles de fórmulas (Guía 9, p. 9): $F_0^{\tau }$ son las atómicas, y $F_{k+1}^{\tau }$ agrega a $F_k^{\tau }$ las palabras $\neg \phi$, $(\phi \eta \psi )$ con $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$ y $Qv\phi$ con $Q\in \{\forall ,\exists \}$ y $v\in \mathrm{Var}$, para $\phi ,\psi \in F_k^{\tau }$. El lema Menú para fórmulas y la lectura única se usan sin enunciar.

El Ejercicio 7, que la consigna deja usar: si $t_0,s_1,s_2\in T^{\tau }$, $t_0^{\prime }$ es el resultado de reemplazar algunas (posiblemente 0) ocurrencias de $s_1$ en $t_0$ por $s_2$ (y $t_0^{\prime }\in T^{\tau }$), $𝐀$ es de tipo $\tau$ y $\overrightarrow{a}\in A^{𝐍}$ cumple $s_1^{𝐀}[\overrightarrow{a}]=s_2^{𝐀}[\overrightarrow{a}]$, entonces $t_0^{\prime 𝐀}[\overrightarrow{a}]=t_0^{𝐀}[\overrightarrow{a}]$. Lo de la Guía 9 que dice que $\tilde{\gamma }$ es fórmula lo da la consigna; vale para cualquier fórmula y cualquier ocurrencia no contigua, y se usa también para los pedazos de $\gamma$.

Lema 9 de la Guía 9 (p. 14), incisos (a) a (e), que dicen dónde puede estar una ocurrencia de un término en una fórmula. La guía los da sin prueba, y como no son Menú ni lectura única, se prueban en el escarabajo:

• (a) Si $t$ ocurre en $(u_1\equiv u_2)$, tal ocurrencia es en $u_1$ o en $u_2$.
• (b) Si $t$ ocurre en $r(u_1,\dots ,u_n)$, dicha ocurrencia sucede dentro de algún $u_j$.
• (c) Si $t$ ocurre en $(\psi \eta \phi )$, tal ocurrencia es en $\psi$ o en $\phi$.
• (d) Si $t$ ocurre en $\neg \psi$, tal ocurrencia es en $\psi$.
• (e) Si $t$ ocurre en $Q{x}_k\psi$, tal ocurrencia es la primera de $x_k$ o sucede dentro de $\psi$.

03 · La mariposa: bajar hasta la atómica

De atrás para adelante. Un término sólo vive en dos lugares de una fórmula: adentro de una atómica, como parte de uno de sus argumentos, o pegado a un cuantificador. La ocurrencia no contigua no es la segunda, así que está adentro de una atómica, y ahí el Ejercicio 7 dice que el argumento que la contiene sigue valiendo lo mismo. Todo lo demás es llevar esa igualdad hacia arriba, piso por piso, con las cláusulas de $\models$. Eso es una inducción en el nivel de $\gamma$: el caso base es la atómica, y en el paso los incisos (c), (d) y (e) del Lema 9 mandan la ocurrencia a un pedazo de nivel menor.

Por qué el ${\mathrm{Enu}}_k$ cuantifica las asignaciones. En el caso $\forall x_j{\gamma }_1$, la cláusula (8) no mira ${\gamma }_1$ en $\overrightarrow{a}$: lo mira en ${\downarrow }_j^a(\overrightarrow{a})$, para cada $a\in A$. Para pasar de $𝐀\models {\tilde{\gamma }}_1[{\downarrow }_j^a(\overrightarrow{a})]$ a $𝐀\models {\gamma }_1[{\downarrow }_j^a(\overrightarrow{a})]$, la hipótesis inductiva tiene que valer en esas otras asignaciones. Si el ${\mathrm{Enu}}_k$ dijera «para la $\overrightarrow{a}$ fija», el paso del cuantificador no tendría con qué hacerse. Por eso «para cada $\overrightarrow{a}\in A^{𝐍}$» va adentro del ${\mathrm{Enu}}_k$, y lo que queda afuera, fijo, son $s$, $t$ y $𝐀$, que no cambian al bajar.

Por qué la hipótesis es para todas. Es la misma cuenta mirada desde abajo. Cuando la inducción llega a la atómica, la asignación ya pasó por todos los cuantificadores de arriba, y puede ser cualquier ${\downarrow }_j^a({\downarrow }_l^b(\dots ))$. El Ejercicio 7 se aplica en esa asignación, y pide $t^{𝐀}=s^{𝐀}$ ahí. El ejemplo de $s=\mathrm{X}2$ es exactamente eso: la hipótesis vale en $(6,6,6,\dots )$ y falla en $(1,6,6,\dots )$, que es una de las asignaciones a las que llega el $\forall \mathrm{X}1$.

Por qué no contigua. El inciso (e) tiene dos salidas: la ocurrencia es la primera de $x_k$, o está en $\psi$. La primera es justamente la contigua, y no está adentro de ninguna atómica: el Ejercicio 7 no tiene nada que decir de ella. La hipótesis del ejercicio cierra esa salida. Y al bajar, la ocurrencia sigue siendo no contigua en el pedazo: si empieza en el primer símbolo del pedazo, no es contigua por definición; si no, el símbolo anterior en el pedazo es el mismo que en $\gamma$.

El camino es la inducción leída de arriba hacia abajo: la conjunción manda la ocurrencia a un miembro, el cuantificador multiplica las asignaciones por cuatro, y en la atómica el Ejercicio 7 se aplica una vez por cada asignación que llegó. Con $s=\mathrm{s}(\mathrm{X}1,\mathrm{X}1)$ la hipótesis vale en todas y la verdad no se mueve. Con $s=\mathrm{X}2$, en $(6,6,6,\dots )$ la hipótesis vale en $\overrightarrow{a}$ pero, para la ocurrencia de 16, sólo en una de las cuatro asignaciones que llegan a la atómica, y la verdad cambia. Para la ocurrencia de 3, que no está bajo ningún cuantificador, llega sólo $\overrightarrow{a}$.

04 · El escarabajo: la prueba escrita

Hechos sobre símbolos. Son los del Ejercicio 7, y se repiten porque la prueba se entrega entera. ${\Sigma }_1$, ${\Sigma }_2$ y ${\Sigma }_3$ son los alfabetos de los nombres de constante, de función y de relación, que por la definición de tipo (Guía 8, p. 4) son disjuntos de a pares y no contienen $\forall$, $\exists$, $\neg$, nexos, paréntesis, coma, $\equiv$, la $X$ ni numerales itálicos o negritas.

• (S1) Todo término empieza con $X$, con un símbolo de ${\Sigma }_1$ o con uno de ${\Sigma }_2$: por lectura única es una variable, un nombre de constante o $g(s_1,\dots ,s_m)$.
• (S2) Un término sólo tiene la $X$, numerales itálicos y negritas, símbolos de ${\Sigma }_1$ y ${\Sigma }_2$, paréntesis y comas. Por la Regla de Inducción desde 0, con ${\mathrm{Enu}}_k$: todo $u\in T_k^{\tau }$ tiene sólo esos símbolos. Vale para variables y constantes, y si vale para $u_1,\dots ,u_n\in T_k^{\tau }$, vale para $f(u_1,\dots ,u_n)$, que agrega símbolos de ${\Sigma }_2$, paréntesis y comas.
• (S3) Si un término $t$ ocurre en una palabra $w$ a partir de una posición que está dentro de una ocurrencia de un término $u$, y el símbolo de $w$ que sigue a esa ocurrencia de $u$ no está en ${\Sigma }_1$ (o no hay ninguno), la ocurrencia de $t$ está dentro de la de $u$. Si no, $u=xy$ y $t=yz$ con $y,z\ne \epsilon$, y por el Lema 2 de la Guía 9 (mordisqueo de términos, que la guía da sin prueba) es $t,u\in 𝒞$; pero $t$ contiene el símbolo que sigue a $u$, que no está en ${\Sigma }_1$. Absurdo.

(L) Dónde están los símbolos de términos en una fórmula. Llamemos argumento atómico de una fórmula $\phi$ a una ocurrencia de un término $u$ en $\phi$ que es uno de los argumentos de una ocurrencia en $\phi$ de una fórmula atómica: $u_1$ o $u_2$ en $(u_1\equiv u_2)$, o un $u_j$ en $r(u_1,\dots ,u_n)$. Usaremos la Regla de Inducción desde 0, con

${\mathrm{Enu}}_k$: para toda $\phi \in F_k^{\tau }$, toda posición de $\phi$ donde hay una $X$ o un símbolo de ${\Sigma }_1$ o de ${\Sigma }_2$ está dentro de un argumento atómico de $\phi$ o dentro de una ocurrencia de una variable cuyo símbolo anterior en $\phi$ es $\forall$ o $\exists$.

• ${\mathrm{Enu}}_0$. En $(u_1\equiv u_2)$, los símbolos fuera de $u_1$ y $u_2$ son «(», «≡» y «)». En $r(u_1,\dots ,u_n)$, los de fuera de los $u_j$ son los de $r$, que están en ${\Sigma }_3$, y paréntesis y comas. Ninguno es $X$ ni de ${\Sigma }_1\cup {\Sigma }_2$.
• ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$. Sea $\phi \in F_{k+1}^{\tau }$. Si $\phi \in F_k^{\tau }$, vale por ${\mathrm{Enu}}_k$. Si no, $\phi$ es $\neg {\phi }_1$, $({\phi }_1\eta {\phi }_2)$ o $Qv{\phi }_1$ con ${\phi }_1,{\phi }_2\in F_k^{\tau }$. Los símbolos $\neg$, «(», $\eta$, «)» y $Q$ no son de los que habla el enunciado. Una posición dentro de $v$ está en una variable precedida por $Q$. Una posición dentro de ${\phi }_1$ o de ${\phi }_2$ está, por ${\mathrm{Enu}}_k$, dentro de un argumento atómico del pedazo, que lo es también de $\phi$, o dentro de una variable precedida por $\forall$ o $\exists$ en el pedazo, y entonces también en $\phi$.

(M) Consecuencia. Si un término $t$ ocurre en una fórmula $\phi$ a partir de una posición que está dentro de una subfórmula ${\phi }_1$, la ocurrencia está dentro de ${\phi }_1$. En efecto, el primer símbolo de $t$ es una $X$ o de ${\Sigma }_1\cup {\Sigma }_2$, por (S1), así que por (L) aplicado a ${\phi }_1$ esa posición está dentro de un argumento atómico $u$ de ${\phi }_1$ o de una variable $v$ de ${\phi }_1$ precedida por un cuantificador. En el primer caso, lo que sigue a $u$ es una coma, «)» o «≡», que no están en ${\Sigma }_1$, y por (S3) la ocurrencia está dentro de $u$. En el segundo, los símbolos de $v$ salvo el primero son numerales, con los que no empieza ningún término, así que $t$ empieza en la $X$ de $v$; por lectura única $t$ es una variable, y termina en su único negrita, que es el primero a partir de esa $X$: el último de $v$. En los dos casos la ocurrencia queda dentro de ${\phi }_1$.

Prueba de los incisos (a) a (e) del Lema 9.

• (a) Por (S1), la ocurrencia no empieza en «(», en «≡» ni en «)»; empieza dentro de $u_1$ o de $u_2$. Lo que sigue a $u_1$ es «≡» y lo que sigue a $u_2$ es «)», que no están en ${\Sigma }_1$: por (S3), está en $u_1$ o en $u_2$.
• (b) Los símbolos de $r$ están en ${\Sigma }_3$, que es disjunto de ${\Sigma }_1$ y ${\Sigma }_2$ y no tiene la $X$; por (S1) la ocurrencia no empieza ahí, ni en «(», las comas o «)». Empieza dentro de algún $u_j$, al que le sigue una coma o «)», y por (S3) sucede dentro de $u_j$.
• (c) Por (S1) no empieza en «(», en $\eta$ ni en «)». Si empieza en $\psi$, por (M) está dentro de $\psi$; si empieza en $\phi$, por (M) está dentro de $\phi$.
• (d) No empieza en $\neg$, por (S1); empieza en $\psi$, y por (M) está en $\psi$.
• (e) No empieza en $Q$. Si empieza en la posición 2, que es la $X$ de $x_k$, por lectura única $t$ es una variable, y termina en su único negrita, que es el primero a partir de la posición 2: el último símbolo de $x_k$. Luego $t=x_k$ y es la ocurrencia a partir de 2, la primera de $x_k$. En las posiciones $3,\dots ,|x_k|+1$ hay numerales, y ningún término empieza con un numeral. Si empieza en $\psi$, por (M) está en $\psi$.

(N) La ocurrencia sigue siendo no contigua. Si una ocurrencia no contigua de $t$ en $\gamma$ está dentro de un pedazo ${\gamma }_1$ que es fórmula, es no contigua en ${\gamma }_1$: si empieza en el primer símbolo de ${\gamma }_1$ no es contigua por definición, y si no, el símbolo anterior a ella en ${\gamma }_1$ es el mismo que en $\gamma$, que no es $\forall$ ni $\exists$.

Prueba del ejercicio. Fijemos $s,t\in T^{\tau }$ y $𝐀=(A,i)$ de tipo $\tau$ tales que $t^{𝐀}[\overrightarrow{b}]=s^{𝐀}[\overrightarrow{b}]$ para cada $\overrightarrow{b}\in A^{𝐍}$. Usaremos la Regla de Inducción desde 0. Para cada $k\in \omega$ sea ${\mathrm{Enu}}_k$ el enunciado:

${\mathrm{Enu}}_k$: Si $\gamma \in F_k^{\tau }$ y $\tilde{\gamma }$ es el resultado de reemplazar en $\gamma$ una ocurrencia no contigua de $t$ por $s$, entonces para cada $\overrightarrow{a}\in A^{𝐍}$ se tiene que $𝐀\models \gamma [\overrightarrow{a}]$ si y solo si $𝐀\models \tilde{\gamma }[\overrightarrow{a}]$.

• Prueba de que ${\mathrm{Enu}}_0$ es verdadero. Sea $\gamma \in F_0^{\tau }$, una atómica, sea $\tilde{\gamma }$ como en el enunciado y sea $\overrightarrow{a}\in A^{𝐍}$.
  • Caso $\gamma =(u_1\equiv u_2)$. Por (a), la ocurrencia reemplazada está en $u_1$ o en $u_2$. Si está en $u_1$, sea $u_1^{\prime }$ el resultado de reemplazarla en $u_1$ por $s$; entonces $\tilde{\gamma }=(u_1^{\prime }\equiv u_2)$. Por el Ejercicio 7, con $u_1$ en lugar de $t$, $t$ en lugar de $s_1$, $s$ en lugar de $s_2$, una ocurrencia reemplazada, y la asignación $\overrightarrow{a}$, en la que $t^{𝐀}[\overrightarrow{a}]=s^{𝐀}[\overrightarrow{a}]$ por hipótesis, se tiene $u_1^{\prime 𝐀}[\overrightarrow{a}]=u_1^{𝐀}[\overrightarrow{a}]$. Por la cláusula (1), $$𝐀\models \tilde{\gamma }[\overrightarrow{a}]\text{sii}{u}_1^{\prime 𝐀}[\overrightarrow{a}]=u_2^{𝐀}[\overrightarrow{a}]\text{sii}{u}_1^{𝐀}[\overrightarrow{a}]=u_2^{𝐀}[\overrightarrow{a}]\text{sii}𝐀\models \gamma [\overrightarrow{a}]$$ Si está en $u_2$, lo mismo con $\tilde{\gamma }=(u_1\equiv u_2^{\prime })$ y $u_2^{\prime 𝐀}[\overrightarrow{a}]=u_2^{𝐀}[\overrightarrow{a}]$.
  • Caso $\gamma =r(u_1,\dots ,u_n)$. Por (b), la ocurrencia reemplazada sucede dentro de algún $u_j$. Sea $u_j^{\prime }$ el resultado de reemplazarla en $u_j$ por $s$; entonces $\tilde{\gamma }=r(u_1,\dots ,u_j^{\prime },\dots ,u_n)$, y por el Ejercicio 7, como en el caso anterior, $u_j^{\prime 𝐀}[\overrightarrow{a}]=u_j^{𝐀}[\overrightarrow{a}]$. Las dos $n$-uplas de valores son iguales, y por la cláusula (2), $𝐀\models \tilde{\gamma }[\overrightarrow{a}]$ sii $(u_1^{𝐀}[\overrightarrow{a}],\dots ,u_j^{\prime 𝐀}[\overrightarrow{a}],\dots ,u_n^{𝐀}[\overrightarrow{a}])\in i(r)$ sii $(u_1^{𝐀}[\overrightarrow{a}],\dots ,u_n^{𝐀}[\overrightarrow{a}])\in i(r)$ sii $𝐀\models \gamma [\overrightarrow{a}]$.
• Prueba de que ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$. Supongamos que vale ${\mathrm{Enu}}_k$. Sean $\gamma \in F_{k+1}^{\tau }$, $\tilde{\gamma }$ el resultado de reemplazar en $\gamma$ una ocurrencia no contigua de $t$ por $s$, y $\overrightarrow{a}\in A^{𝐍}$. Por definición de $F_{k+1}^{\tau }$ hay varios casos.
  • Caso $\gamma \in F_k^{\tau }$. Como vale ${\mathrm{Enu}}_k$, $𝐀\models \gamma [\overrightarrow{a}]$ sii $𝐀\models \tilde{\gamma }[\overrightarrow{a}]$.
  • Caso $\gamma =\neg {\gamma }_1$, con ${\gamma }_1\in F_k^{\tau }$. Por (d) la ocurrencia está en ${\gamma }_1$, y por (N) es no contigua en ${\gamma }_1$. Sea ${\tilde{\gamma }}_1$ el resultado de reemplazarla en ${\gamma }_1$ por $s$, que es fórmula por el lema de la Guía 9; entonces $\tilde{\gamma }=\neg {\tilde{\gamma }}_1$. Por ${\mathrm{Enu}}_k$, aplicado a ${\gamma }_1$ en la asignación $\overrightarrow{a}$, $𝐀\models {\gamma }_1[\overrightarrow{a}]$ sii $𝐀\models {\tilde{\gamma }}_1[\overrightarrow{a}]$. Por la cláusula (7), $𝐀\models \tilde{\gamma }[\overrightarrow{a}]$ sii $𝐀⊭{\tilde{\gamma }}_1[\overrightarrow{a}]$ sii $𝐀⊭{\gamma }_1[\overrightarrow{a}]$ sii $𝐀\models \gamma [\overrightarrow{a}]$.
  • Caso $\gamma =({\gamma }_1\eta {\gamma }_2)$, con $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$ y ${\gamma }_1,{\gamma }_2\in F_k^{\tau }$. Por (c) la ocurrencia está en ${\gamma }_1$ o en ${\gamma }_2$, y por (N) es no contigua ahí. Si está en ${\gamma }_1$, sea ${\tilde{\gamma }}_1$ el resultado de reemplazarla en ${\gamma }_1$ y ${\tilde{\gamma }}_2={\gamma }_2$; si está en ${\gamma }_2$, sea ${\tilde{\gamma }}_2$ el resultado de reemplazarla en ${\gamma }_2$ y ${\tilde{\gamma }}_1={\gamma }_1$. En los dos casos $\tilde{\gamma }=({\tilde{\gamma }}_1\eta {\tilde{\gamma }}_2)$, los dos miembros son fórmulas, y por ${\mathrm{Enu}}_k$ en la asignación $\overrightarrow{a}$ (o porque el miembro no cambió) $𝐀\models {\gamma }_i[\overrightarrow{a}]$ sii $𝐀\models {\tilde{\gamma }}_i[\overrightarrow{a}]$, para $i=1,2$. Entonces:
    • $\eta =\wedge$: por (3), $𝐀\models \tilde{\gamma }[\overrightarrow{a}]$ sii $𝐀\models {\tilde{\gamma }}_1[\overrightarrow{a}]$ y $𝐀\models {\tilde{\gamma }}_2[\overrightarrow{a}]$ sii $𝐀\models {\gamma }_1[\overrightarrow{a}]$ y $𝐀\models {\gamma }_2[\overrightarrow{a}]$ sii $𝐀\models \gamma [\overrightarrow{a}]$.
    • $\eta =\vee$: por (4), $𝐀\models \tilde{\gamma }[\overrightarrow{a}]$ sii $𝐀\models {\tilde{\gamma }}_1[\overrightarrow{a}]$ o $𝐀\models {\tilde{\gamma }}_2[\overrightarrow{a}]$ sii $𝐀\models {\gamma }_1[\overrightarrow{a}]$ o $𝐀\models {\gamma }_2[\overrightarrow{a}]$ sii $𝐀\models \gamma [\overrightarrow{a}]$.
    • $\eta =\to$: por (5), $𝐀\models \tilde{\gamma }[\overrightarrow{a}]$ sii $𝐀⊭{\tilde{\gamma }}_1[\overrightarrow{a}]$ o $𝐀\models {\tilde{\gamma }}_2[\overrightarrow{a}]$ sii $𝐀⊭{\gamma }_1[\overrightarrow{a}]$ o $𝐀\models {\gamma }_2[\overrightarrow{a}]$ sii $𝐀\models \gamma [\overrightarrow{a}]$.
    • $\eta =\leftrightarrow$: por (6), $𝐀\models \tilde{\gamma }[\overrightarrow{a}]$ sii ${\tilde{\gamma }}_1$ y ${\tilde{\gamma }}_2$ valen las dos en $\overrightarrow{a}$ o no vale ninguna, sii ${\gamma }_1$ y ${\gamma }_2$ valen las dos en $\overrightarrow{a}$ o no vale ninguna, sii $𝐀\models \gamma [\overrightarrow{a}]$.
  • Caso $\gamma =Q{x}_j{\gamma }_1$, con $Q\in \{\forall ,\exists \}$ y ${\gamma }_1\in F_k^{\tau }$. Por (e) la ocurrencia es la primera de $x_j$ o sucede dentro de ${\gamma }_1$. La primera de $x_j$ empieza en la posición 2 y el símbolo anterior es $Q$: es contigua, y la nuestra no lo es. Luego está dentro de ${\gamma }_1$, y por (N) es no contigua en ${\gamma }_1$. Sea ${\tilde{\gamma }}_1$ el resultado de reemplazarla en ${\gamma }_1$ por $s$, que es fórmula; entonces $\tilde{\gamma }=Q{x}_j{\tilde{\gamma }}_1$.
    • $Q=\forall$: por (8), $𝐀\models \tilde{\gamma }[\overrightarrow{a}]$ sii para cada $a\in A$, $𝐀\models {\tilde{\gamma }}_1[{\downarrow }_j^a(\overrightarrow{a})]$. Por ${\mathrm{Enu}}_k$, aplicado a ${\gamma }_1$ en la asignación ${\downarrow }_j^a(\overrightarrow{a})$, eso pasa sii para cada $a\in A$, $𝐀\models {\gamma }_1[{\downarrow }_j^a(\overrightarrow{a})]$, que por (8) es $𝐀\models \gamma [\overrightarrow{a}]$.
    • $Q=\exists$: por (9), $𝐀\models \tilde{\gamma }[\overrightarrow{a}]$ sii hay un $a\in A$ tal que $𝐀\models {\tilde{\gamma }}_1[{\downarrow }_j^a(\overrightarrow{a})]$. Por ${\mathrm{Enu}}_k$ en la asignación ${\downarrow }_j^a(\overrightarrow{a})$, eso pasa sii hay un $a\in A$ tal que $𝐀\models {\gamma }_1[{\downarrow }_j^a(\overrightarrow{a})]$, que por (9) es $𝐀\models \gamma [\overrightarrow{a}]$.

Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ vale para todo $k\in \omega$. Dada $\gamma \in F^{\tau }$, está en algún $F_k^{\tau }$, y ${\mathrm{Enu}}_k$ da $𝐀\models \gamma [\overrightarrow{a}]$ sii $𝐀\models \tilde{\gamma }[\overrightarrow{a}]$ para cada $\overrightarrow{a}\in A^{𝐍}$. ∎

05 · Lo que hace perder puntos y lo que se lleva

Lo que hace perder puntos. Fijar $\overrightarrow{a}$ antes de la inducción y escribir un ${\mathrm{Enu}}_k$ para esa sola asignación: el caso del cuantificador queda sin hipótesis inductiva. No decir, en el caso $Q{x}_j{\gamma }_1$, que la ocurrencia no puede ser la de $x_j$ porque es contigua. Aplicar el Ejercicio 7 sin decir en qué asignación ni que ahí $t^{𝐀}=s^{𝐀}$. Despachar los nexos o el $\exists$ con «los otros casos son similares», cuando cada uno es una línea. Usar el Lema 9 de la Guía 9 sin enunciarlo y probarlo. Y olvidar que los pedazos también tienen que ser fórmulas para aplicar las cláusulas: lo da el lema de la Guía 9 que cita la consigna.

Lo que se lleva. El molde, con «para cada $\overrightarrow{a}$» adentro del ${\mathrm{Enu}}_k$ porque el cuantificador cambia la asignación, es el del Ejercicio 12, que reemplaza una subfórmula por otra equivalente en una estructura, y el del Ejercicio 9, donde la equivalencia es en todas las estructuras. La diferencia con el 12 es dónde termina la inducción: allá en la subfórmula reemplazada, acá en una atómica. Y el Ejercicio 7 es el piso de abajo: la misma inducción hecha con términos, donde ninguna cláusula cambia la asignación y por eso alcanza con la hipótesis en una sola.

Para tener a mano

1. ${\mathrm{Enu}}_k$: si $\gamma \in F_k^{\tau }$ y $\tilde{\gamma }$ es el resultado de reemplazar en $\gamma$ una ocurrencia no contigua de $t$ por $s$, entonces para cada $\overrightarrow{a}$, $𝐀\models \gamma [\overrightarrow{a}]$ sii $𝐀\models \tilde{\gamma }[\overrightarrow{a}]$. Con $s$, $t$ y $𝐀$ fijos afuera.
2. Caso base: la ocurrencia está en un argumento de la atómica, por el Lema 9 (a) o (b), y el Ejercicio 7 en $\overrightarrow{a}$ dice que el argumento vale lo mismo.
3. Paso: $\neg$ y los cuatro nexos en la misma $\overrightarrow{a}$; $\forall$ y $\exists$ en ${\downarrow }_j^a(\overrightarrow{a})$ para cada $a$, que es por qué el ${\mathrm{Enu}}_k$ y la hipótesis son para todas las asignaciones.
4. La ocurrencia de $x_j$ pegada al cuantificador es la contigua, la única que el Lema 9 (e) no manda adentro: el ejercicio la excluye, y al bajar a un pedazo se sigue siendo no contigua.
5. En el ejemplo, con $s=\mathrm{X}2$ y $\overrightarrow{a}=(6,6,6,\dots )$, reemplazar la $\mathrm{X}1$ de adentro del $\forall \mathrm{X}1$ vuelve falsa una fórmula verdadera: la hipótesis en una sola asignación no alcanza.