Reemplazar por una equivalente da una equivalente

El enunciado, textual: «Sean ${\phi }_1,{\phi }_2,\alpha$ formulas de tipo $\tau$. Pruebe que si ${\phi }_1\sim {\phi }_2$ y ${\alpha }^{\prime }$ es el resultado de reemplazar en $\alpha$ algunas (posiblemente 0) ocurrencias de ${\phi }_1$ por ${\phi }_2$, entonces $\alpha \sim {\alpha }^{\prime }$. Acepte sin demostración que ${\phi }^{\prime }\in F^{\tau }$.» Es el Lema 5 de la Guía 10 (p. 9). La guía lo prueba con un solo caso del paso inductivo, el de $({\alpha }_1\eta {\alpha }_2)$, y de los demás dice que «son similares y dejados al lector»; en el parcial van todos.

Lo que se acepta sin prueba es que el resultado del reemplazo es una fórmula. Todo lo demás se prueba: la equivalencia, y dos cosas que la prueba de la guía usa sin probar, el Lema 4(b) de la Guía 10 y los incisos (a) a (d) del lema de ocurrencias de fórmulas de la Guía 9.

01 · Qué pide, en criollo

Dos fórmulas son equivalentes cuando dicen lo mismo en toda estructura y para toda asignación. El ejercicio dice que adentro de una fórmula más grande una se puede cambiar por la otra, en uno, varios o ningún lugar, y lo que queda dice lo mismo que lo que había.

Un ejemplo con un tipo que tiene una relación unaria $\mathrm{P}$ y una binaria $\mathrm{R}$. Las fórmulas

$${\phi }_1=(\mathrm{P}(\mathrm{X}1)\to \mathrm{R}(\mathrm{X}1,\mathrm{X}2)){\phi }_2=(\neg \mathrm{P}(\mathrm{X}1)\vee \mathrm{R}(\mathrm{X}1,\mathrm{X}2))$$

son equivalentes: «si $p$ entonces $q$» y «no $p$ o $q$» tienen la misma tabla. La fórmula

$$\alpha =\forall \mathrm{X}2((\mathrm{P}(\mathrm{X}1)\to \mathrm{R}(\mathrm{X}1,\mathrm{X}2))\wedge \exists \mathrm{X}1(\mathrm{P}(\mathrm{X}1)\to \mathrm{R}(\mathrm{X}1,\mathrm{X}2)))$$

tiene 41 símbolos, y ${\phi }_1$ ocurre en ella dos veces, a partir de 5 y de 25. Reemplazando ninguna, la primera, la segunda o las dos por ${\phi }_2$ salen cuatro fórmulas, y las cuatro son equivalentes a $\alpha$: evaluadas con la definición de $\models$ en las 4164 estructuras de hasta tres elementos para ese tipo, con todas las asignaciones posibles de $\mathrm{X}1,\mathrm{X}2,\mathrm{X}3$, no difieren de $\alpha$ en ningún caso.

La segunda ocurrencia es la que enseña algo. Vive debajo de $\exists \mathrm{X}1$, y ahí $\mathrm{X}1$ toma todos los valores del universo, no el que le da la asignación con la que se evalúa $\alpha$. El reemplazo funciona igual porque ${\phi }_1\sim {\phi }_2$ vale para toda asignación, también para las que el cuantificador fabrica. Ese es el centro de la prueba, y es lo que el Ejercicio 12 obliga a escribir con cuidado.

02 · Las herramientas

Se pueden usar sin enunciar los lemas Menú y la lectura única. Lo demás se enuncia, y se prueba salvo lo que la guía acepta sin prueba.

Equivalencia (Guía 10, p. 8). «Dadas $\phi ,\psi \in F^{\tau }$ diremos que $\phi$ y $\psi$ son equivalentes cuando se de la siguiente condición: $𝐀\models \phi [\overrightarrow{a}]$ si y solo si $𝐀\models \psi [\overrightarrow{a}]$, para cada modelo de tipo $\tau$, $𝐀$ y cada $\overrightarrow{a}\in A^{𝐍}$.» Se escribe $\phi \sim \psi$. Como se define con un «si y sólo si», $\sim$ es reflexiva, simétrica y transitiva.

Las cláusulas de la relación ⊨ (Guía 10, p. 4) que se usan, para $𝐀$ de tipo $\tau$ y $\overrightarrow{a}\in A^{𝐍}$:

• (3) $𝐀\models ({\phi }_1\wedge {\phi }_2)[\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$.
• (4) $𝐀\models ({\phi }_1\vee {\phi }_2)[\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$.
• (5) $𝐀\models ({\phi }_1\to {\phi }_2)[\overrightarrow{a}]$ sii $𝐀⊭{\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$.
• (6) $𝐀\models ({\phi }_1\leftrightarrow {\phi }_2)[\overrightarrow{a}]$ sii se dan $𝐀\models {\phi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$, o se dan $𝐀⊭{\phi }_1[\overrightarrow{a}]$ y $𝐀⊭{\phi }_2[\overrightarrow{a}]$.
• (7) $𝐀\models \neg {\phi }_1[\overrightarrow{a}]$ sii $𝐀⊭{\phi }_1[\overrightarrow{a}]$.
• (8) $𝐀\models \forall x_i{\phi }_1[\overrightarrow{a}]$ sii para cada $a\in A$ se da $𝐀\models {\phi }_1[{\downarrow }_i^a(\overrightarrow{a})]$.
• (9) $𝐀\models \exists x_i{\phi }_1[\overrightarrow{a}]$ sii hay un $a\in A$ tal que $𝐀\models {\phi }_1[{\downarrow }_i^a(\overrightarrow{a})]$.

Acá ${\downarrow }_i^a(\overrightarrow{a})$ es la asignación que resulta de reemplazar en $\overrightarrow{a}$ el $i$-ésimo elemento por $a$.

Lema 4(b) (Guía 10, p. 8). «Si ${\phi }_i\sim {\psi }_i$, $i=1,2$, entonces $\neg {\phi }_1\sim \neg {\psi }_1$, $({\phi }_1\eta {\phi }_2)\sim ({\psi }_1\eta {\psi }_2)$ y $Qv{\phi }_1\sim Qv{\psi }_1$.» La guía lo deja al lector: es su Ejercicio 11. Se prueba en la sección 05.

Lema 8 de la Guía 9 (Ocurrencias de Fórmulas en Fórmulas, p. 13), los incisos que se usan. Sean $\phi ,\psi ,\varphi \in F^{\tau }$.

• (a) Las fórmulas atómicas no tienen subfórmulas propias.
• (b) Si $\phi \ne (\psi \eta \varphi )$ y $\phi$ ocurre en $(\psi \eta \varphi )$, entonces tal ocurrencia sucede en $\psi$ o en $\varphi$.
• (c) Si $\phi \ne \neg \psi$ y $\phi$ ocurre en $\neg \psi$, entonces tal ocurrencia sucede en $\psi$.
• (d) Si $\phi \ne Qv\psi$ y $\phi$ ocurre en $Qv\psi$, entonces tal ocurrencia sucede en $\psi$.

Una subfórmula de $\psi$ es una fórmula que es subpalabra de $\psi$; propia, si además no es $\psi$. La Guía 9 enuncia el lema y prueba sólo el inciso (g); estos cuatro se prueban en la sección 04, con dos resultados que la Guía 9 acepta sin prueba y que por eso se enuncian sin probar:

• Proposición 6 (Mordisqueo de Fórmulas, Guía 9, p. 12). «Si $\phi ,\psi \in F^{\tau }$ y $x,y,z$ son tales que $\phi =xy$, $\psi =yz$ y $y\ne \epsilon$, entonces $z=\epsilon$ y $x\in T^{*}$. En particular ningún tramo inicial propio de una fórmula es una fórmula y ningún tramo final propio de una fórmula atómica es una fórmula.» Acá $T^{*}$ son las concatenaciones de símbolos $\neg$ y palabras $Qv$.
• Lema 2 (Mordisqueo de Términos, Guía 9, p. 5), lo que dice «en particular»: si un término es tramo inicial o final de otro término, entonces dichos términos son iguales.

Y de la definición de tipo: los nombres de constante, de función y de relación están escritos sobre alfabetos disjuntos de a pares, ninguno de cuyos símbolos es $\forall$, $\exists$, $\neg$, un nexo, un paréntesis, la coma, $\equiv$, la $X$ ni un numeral itálico o negrita; y ningún nombre de relación es subpalabra propia de otro nombre de relación.

03 · La mariposa: el reemplazo baja, la equivalencia sube

Por qué inducción en el nivel de α. Las ocurrencias de ${\phi }_1$ pueden estar a cualquier profundidad dentro de $\alpha$. Lo natural es desarmar $\alpha$ con la lectura única: si $\alpha =({\alpha }_1\eta {\alpha }_2)$, cada ocurrencia que se reemplaza está en ${\alpha }_1$ o en ${\alpha }_2$, y ${\alpha }^{\prime }=({\alpha }_1^{\prime }\eta {\alpha }_2^{\prime })$, donde cada ${\alpha }_i^{\prime }$ es ${\alpha }_i$ con sus reemplazos. Por hipótesis inductiva ${\alpha }_1\sim {\alpha }_1^{\prime }$ y ${\alpha }_2\sim {\alpha }_2^{\prime }$, y hace falta un resultado que diga que armar con el mismo nexo dos pares equivalentes da equivalentes. Eso es exactamente el Lema 4(b), con un renglón para cada forma de armar una fórmula: $\neg$, cada nexo, cada cuantificador. El reemplazo baja por la fórmula; la equivalencia sube, de a un piso, por el Lema 4(b).

Dónde entra la hipótesis. Hay un caso que la hipótesis inductiva no cubre: que la ocurrencia reemplazada sea toda $\alpha$, o sea ${\phi }_1=\alpha$. Entonces ${\alpha }^{\prime }={\phi }_2$, y $\alpha \sim {\alpha }^{\prime }$ es la hipótesis ${\phi }_1\sim {\phi }_2$, sin más. Ese caso aparece en cada forma del paso, y en la base es el único que hay.

Por qué el Enu dice «posiblemente 0». En el caso $({\alpha }_1\eta {\alpha }_2)$ puede pasar que todas las ocurrencias reemplazadas estén en ${\alpha }_1$. Entonces a ${\alpha }_2$ no se le reemplaza nada, ${\alpha }_2^{\prime }={\alpha }_2$, y para usar la hipótesis inductiva con ${\alpha }_2$ el enunciado tiene que admitir cero reemplazos. Sin el «posiblemente 0» adentro de ${\mathrm{Enu}}_k$, ese lado queda sin justificar.

Por qué hace falta el lema de ocurrencias. Que una ocurrencia de ${\phi }_1$ en $({\alpha }_1\eta {\alpha }_2)$ esté en ${\alpha }_1$ o en ${\alpha }_2$ no es obvio: podría arrancar en ${\alpha }_1$ y terminar en ${\alpha }_2$, pisando el nexo. Con palabras cualesquiera pasa: en $(\mathrm{P}(\mathrm{X}1)\wedge \mathrm{P}(\mathrm{X}2))$ la palabra $\mathrm{P}(\mathrm{X}1)\wedge \mathrm{P}(\mathrm{X}2)$ ocurre a partir de 2 y pisa el $\wedge$. Pero no es una fórmula. El inciso (b) del Lema 8 dice que con una fórmula eso no pasa, y (c) y (d) dicen lo mismo para $\neg$ y para $Qv$, donde además la ocurrencia no puede tocar la $Qv$ del principio.

Por qué el caso del cuantificador funciona. En el Lema 4(b), para $Qv{\phi }_1\sim Qv{\psi }_1$ con $v=x_i$, la cláusula (8) pide comparar ${\phi }_1$ y ${\psi }_1$ en las asignaciones ${\downarrow }_i^a(\overrightarrow{a})$, para cada $a$. La hipótesis ${\phi }_1\sim {\psi }_1$ lo permite porque habla de todas las asignaciones. Si sólo se supiera que coinciden en $\overrightarrow{a}$, no alcanzaría; el Ejercicio 12 muestra un caso concreto en que falla.

Abajo está el ejemplo de la sección 01 con más opciones. Elegís $\alpha$, la fórmula ${\phi }_2$ que reemplaza a ${\phi }_1=(\mathrm{P}(\mathrm{X}1)\to \mathrm{R}(\mathrm{X}1,\mathrm{X}2))$ y cuáles ocurrencias se reemplazan, y la comparación recorre todas las estructuras de hasta dos elementos con todas las asignaciones de $\mathrm{X}1,\mathrm{X}2,\mathrm{X}3$.

Con una ${\phi }_2$ equivalente no aparece ningún caso, se elija lo que se elija. Con $(\mathrm{P}(\mathrm{X}1)\to \mathrm{R}(\mathrm{X}2,\mathrm{X}1))$, que difiere de ${\phi }_1$ en 64 de los 516 pares (estructura, asignación), reemplazar sólo la ocurrencia de adentro del $\exists \mathrm{X}1$ hace diferir a $\alpha$ y ${\alpha }^{\prime }$ en apenas 8: probar el reemplazo en unos pocos casos no habría encontrado nada. Y el lema es una sola dirección. No dice que con una ${\phi }_2$ no equivalente el resultado deje de ser equivalente; dice que con una equivalente nunca deja de serlo.

04 · Lo que se usa de la Guía 9, probado

Primero, dos observaciones sobre cómo empieza una fórmula. Por el Menú, toda fórmula es de una de las formas $(t\equiv s)$, $r(t_1,\dots ,t_n)$, $({\phi }_1\eta {\phi }_2)$, $\neg {\phi }_1$ o $Qv{\phi }_1$; así que empieza con $($, con un símbolo de un nombre de relación, con $\neg$ o con un cuantificador. Ninguna fórmula empieza con un nexo, con $)$, con la coma, con la $X$ ni con un numeral. Y, por la Proposición 6, si dos fórmulas ocurren en una palabra a partir de la misma posición, son la misma ocurrencia: la más corta es tramo inicial de la más larga, y no puede ser tramo inicial propio.

(b) Prueba. Sean $\alpha =(\psi \eta \varphi )$ y $\phi$ una fórmula que ocurre en $\alpha$ a partir de $i$, con $\phi \ne \alpha$. Las posiciones de $\alpha$ son: la 1, que tiene $($; de la 2 a la $|\psi |+1$, las de $\psi$; la $|\psi |+2$, que tiene $\eta$; las de $\varphi$; y la última, que tiene $)$.

• $i\ne 1$: si no, $\phi$ y $\alpha$ ocurren a partir de la misma posición y $\phi =\alpha$.
• $i$ no es la posición de $\eta$ ni la última: ninguna fórmula empieza con un nexo ni con $)$.
• Si $i$ es una posición de $\psi$, supongamos que la ocurrencia de $\phi$ no termina dentro de $\psi$. Sean $x$ los símbolos de $\psi$ anteriores a la posición $i$, $y$ los de $\psi$ desde la $i$ hasta su final, y $z$ los de $\phi$ que vienen después del final de $\psi$. Entonces $\psi =xy$, $\phi =yz$, $y\ne \epsilon$ porque $i$ es posición de $\psi$, y $z\ne \epsilon$ porque la ocurrencia se pasa de $\psi$. La Proposición 6 dice $z=\epsilon$: absurdo. Luego la ocurrencia sucede en $\psi$.
• Si $i$ es una posición de $\varphi$, el mismo argumento con $\varphi$ en lugar de $\psi$ dice que sucede en $\varphi$. ∎

(c) Prueba. Sean $\alpha =\neg \psi$ y $\phi \ne \alpha$ que ocurre en $\alpha$ a partir de $i$. Como antes, $i\ne 1$. Entonces $i$ es una posición de $\psi$, y como $\psi$ llega hasta el final de $\alpha$, la ocurrencia termina dentro de $\psi$. ∎

(d) Prueba. Sean $\alpha =Qv\psi$ y $\phi \ne \alpha$ que ocurre en $\alpha$ a partir de $i$. Como antes, $i\ne 1$. Las posiciones 2 a $|v|+1$ tienen la $X$ y los numerales de $v$, y ninguna fórmula empieza con ellos. Entonces $i$ es una posición de $\psi$, que llega hasta el final de $\alpha$. ∎

(a) Prueba. Sean $\alpha$ atómica y $\phi$ una fórmula que ocurre en $\alpha$ a partir de $i$. Veamos que $\phi =\alpha$.

• $\alpha$ no contiene $\neg$, $\forall$, $\exists$ ni nexos: sus símbolos son los de sus términos (variables, nombres de constante y de función, paréntesis y comas), $\equiv$, paréntesis, comas y los del nombre de relación. Por lectura única, una fórmula no atómica contiene alguno de esos símbolos: $\neg {\phi }_1$ empieza con $\neg$, $Qv{\phi }_1$ con un cuantificador, y $({\phi }_1\eta {\phi }_2)$ contiene $\eta$. Luego $\phi$ es atómica.
• Si $\alpha =r(t_1,\dots ,t_n)$: $\alpha$ no contiene $\equiv$, así que $\phi =r^{\prime }(s_1,\dots ,s_m)$. Los únicos símbolos de $\alpha$ que son de nombres de relación son los de $r$, en las posiciones 1 a $|r|$, y el primer $($ de $\alpha$ está en la posición $|r|+1$. La ocurrencia de $r^{\prime }$ empieza en $i$, está hecha de símbolos de nombres de relación y la sigue un $($: luego $r^{\prime }$ es un tramo final de $r$. Ningún nombre de relación es subpalabra propia de otro, así que $r^{\prime }=r$ e $i=1$. Entonces $\phi$ y $\alpha$ ocurren a partir de la misma posición, y $\phi =\alpha$.
• Si $\alpha =(t\equiv s)$: $\alpha$ no tiene símbolos de nombres de relación, así que $\phi =(t^{\prime }\equiv s^{\prime })$. $\alpha$ tiene un solo $\equiv$, en la posición $|t|+2$, y la ocurrencia de $\phi$ lo contiene. Si $i=1$, $\phi =\alpha$ como antes. Si $i>1$, el $($ de $\phi$ está en una posición de $t$, y $t^{\prime }$ ocupa desde la $i+1$ hasta la $|t|+1$: es un tramo final propio de $t$, porque $t$ empieza en la 2. Por el Lema 2, $t^{\prime }=t$, absurdo. ∎

Y una consecuencia que la base de la inducción usa: si $\phi =\alpha$, la única ocurrencia de $\phi$ en $\alpha$ es a partir de 1, porque a partir de $i>1$ harían falta $i-1+|\alpha |>|\alpha |$ símbolos.

05 · El Lema 4(b), probado

Prueba. Sean ${\phi }_1,{\phi }_2,{\psi }_1,{\psi }_2\in F^{\tau }$ con ${\phi }_1\sim {\psi }_1$ y ${\phi }_2\sim {\psi }_2$. Sean $𝐀$ un modelo de tipo $\tau$ y $\overrightarrow{a}\in A^{𝐍}$ cualesquiera. Por la hipótesis, $𝐀\models {\phi }_1[\overrightarrow{a}]$ sii $𝐀\models {\psi }_1[\overrightarrow{a}]$, y $𝐀\models {\phi }_2[\overrightarrow{a}]$ sii $𝐀\models {\psi }_2[\overrightarrow{a}]$.

• ¬. Por (7), $𝐀\models \neg {\phi }_1[\overrightarrow{a}]$ sii $𝐀⊭{\phi }_1[\overrightarrow{a}]$ sii $𝐀⊭{\psi }_1[\overrightarrow{a}]$ sii, por (7), $𝐀\models \neg {\psi }_1[\overrightarrow{a}]$.
• ∧. Por (3), $𝐀\models ({\phi }_1\wedge {\phi }_2)[\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$, sii $𝐀\models {\psi }_1[\overrightarrow{a}]$ y $𝐀\models {\psi }_2[\overrightarrow{a}]$, sii, por (3), $𝐀\models ({\psi }_1\wedge {\psi }_2)[\overrightarrow{a}]$.
• ∨. Por (4), $𝐀\models ({\phi }_1\vee {\phi }_2)[\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$, sii $𝐀\models {\psi }_1[\overrightarrow{a}]$ o $𝐀\models {\psi }_2[\overrightarrow{a}]$, sii, por (4), $𝐀\models ({\psi }_1\vee {\psi }_2)[\overrightarrow{a}]$.
• →. Por (5), $𝐀\models ({\phi }_1\to {\phi }_2)[\overrightarrow{a}]$ sii $𝐀⊭{\phi }_1[\overrightarrow{a}]$ o $𝐀\models {\phi }_2[\overrightarrow{a}]$, sii $𝐀⊭{\psi }_1[\overrightarrow{a}]$ o $𝐀\models {\psi }_2[\overrightarrow{a}]$, sii, por (5), $𝐀\models ({\psi }_1\to {\psi }_2)[\overrightarrow{a}]$.
• ↔. Por (6), $𝐀\models ({\phi }_1\leftrightarrow {\phi }_2)[\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 {\psi }_1[\overrightarrow{a}]$ y $𝐀\models {\psi }_2[\overrightarrow{a}]$) o ($𝐀⊭{\psi }_1[\overrightarrow{a}]$ y $𝐀⊭{\psi }_2[\overrightarrow{a}]$), sii, por (6), $𝐀\models ({\psi }_1\leftrightarrow {\psi }_2)[\overrightarrow{a}]$.
• ∀. Sea $v=x_i$. Por (8), $𝐀\models \forall x_i{\phi }_1[\overrightarrow{a}]$ sii para cada $a\in A$, $𝐀\models {\phi }_1[{\downarrow }_i^a(\overrightarrow{a})]$. Para cada $a$, ${\downarrow }_i^a(\overrightarrow{a})$ es una asignación de $𝐀$, y como ${\phi }_1\sim {\psi }_1$ vale para toda asignación, $𝐀\models {\phi }_1[{\downarrow }_i^a(\overrightarrow{a})]$ sii $𝐀\models {\psi }_1[{\downarrow }_i^a(\overrightarrow{a})]$. Luego lo anterior vale sii para cada $a\in A$, $𝐀\models {\psi }_1[{\downarrow }_i^a(\overrightarrow{a})]$, sii, por (8), $𝐀\models \forall x_i{\psi }_1[\overrightarrow{a}]$.
• ∃. Sea $v=x_i$. Por (9), $𝐀\models \exists x_i{\phi }_1[\overrightarrow{a}]$ sii hay un $a\in A$ con $𝐀\models {\phi }_1[{\downarrow }_i^a(\overrightarrow{a})]$, sii, como en el caso anterior, hay un $a\in A$ con $𝐀\models {\psi }_1[{\downarrow }_i^a(\overrightarrow{a})]$, sii, por (9), $𝐀\models \exists x_i{\psi }_1[\overrightarrow{a}]$.

Como $𝐀$ y $\overrightarrow{a}$ eran cualesquiera, en cada renglón las dos fórmulas son equivalentes. ∎

06 · El escarabajo: la prueba del Lema 5

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

${\mathrm{Enu}}_k$: Sean ${\phi }_1,{\phi }_2\in F^{\tau }$ tales que ${\phi }_1\sim {\phi }_2$ y sea $\alpha \in F_k^{\tau }$. Sea ${\alpha }^{\prime }$ el resultado de reemplazar en $\alpha$ algunas (posiblemente 0) ocurrencias de ${\phi }_1$ por ${\phi }_2$. Entonces $\alpha \sim {\alpha }^{\prime }$.

Prueba de que ${\mathrm{Enu}}_0$ es verdadero. Sean ${\phi }_1\sim {\phi }_2$, $\alpha \in F_0^{\tau }$ y ${\alpha }^{\prime }$ como en el enunciado. Si no se reemplazó ninguna ocurrencia, ${\alpha }^{\prime }=\alpha$ y $\alpha \sim \alpha$. Si se reemplazó alguna, ${\phi }_1$ ocurre en $\alpha$, que es atómica; por el Lema 8(a) de la Guía 9, ${\phi }_1=\alpha$, y la única ocurrencia de ${\phi }_1$ en $\alpha$ es a partir de 1. Entonces ${\alpha }^{\prime }={\phi }_2$, y $\alpha ={\phi }_1\sim {\phi }_2={\alpha }^{\prime }$.

Prueba de que si ${\mathrm{Enu}}_k$ es verdadero entonces ${\mathrm{Enu}}_{k+1}$ lo es. Supongamos que vale ${\mathrm{Enu}}_k$. Sean ${\phi }_1\sim {\phi }_2$, $\alpha \in F_{k+1}^{\tau }$ y ${\alpha }^{\prime }$ el resultado de reemplazar en $\alpha$ algunas (posiblemente 0) ocurrencias de ${\phi }_1$ por ${\phi }_2$. Probaremos que $\alpha \sim {\alpha }^{\prime }$. En todos los casos de abajo vale lo mismo que en la base: si ${\phi }_1=\alpha$, su única ocurrencia en $\alpha$ es la de $\alpha$ entera, así que ${\alpha }^{\prime }=\alpha$ (si no se reemplazó nada) o ${\alpha }^{\prime }={\phi }_2$, y en los dos casos $\alpha \sim {\alpha }^{\prime }$. Por eso en cada caso alcanza con mirar ${\phi }_1\ne \alpha$. Por definición de $F_{k+1}^{\tau }$ hay varios casos.

• Caso $\alpha \in F_k^{\tau }$. Ya que vale ${\mathrm{Enu}}_k$, $\alpha \sim {\alpha }^{\prime }$.
• Caso $\alpha =({\alpha }_1\eta {\alpha }_2)$, con $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$ y ${\alpha }_1,{\alpha }_2\in F_k^{\tau }$. Sea ${\phi }_1\ne \alpha$. Por el Lema 8(b) de la Guía 9, cada ocurrencia de ${\phi }_1$ en $\alpha$ que fue reemplazada sucede en ${\alpha }_1$ o en ${\alpha }_2$. Luego ${\alpha }^{\prime }=({\alpha }_1^{\prime }\eta {\alpha }_2^{\prime })$, donde ${\alpha }_j^{\prime }$ es el resultado de reemplazar en ${\alpha }_j$ las ocurrencias reemplazadas que suceden en ${\alpha }_j$ (posiblemente 0), para $j=1,2$. Como ${\alpha }_1,{\alpha }_2\in F_k^{\tau }$, por ${\mathrm{Enu}}_k$ aplicado a cada una, ${\alpha }_1\sim {\alpha }_1^{\prime }$ y ${\alpha }_2\sim {\alpha }_2^{\prime }$. Por el Lema 4(b), $({\alpha }_1\eta {\alpha }_2)\sim ({\alpha }_1^{\prime }\eta {\alpha }_2^{\prime })$, es decir $\alpha \sim {\alpha }^{\prime }$. El Lema 4(b) está probado para cada uno de los cuatro nexos, así que este caso los cubre a los cuatro.
• Caso $\alpha =\neg {\alpha }_1$, con ${\alpha }_1\in F_k^{\tau }$. Sea ${\phi }_1\ne \alpha$. Por el Lema 8(c), cada ocurrencia reemplazada sucede en ${\alpha }_1$. Luego ${\alpha }^{\prime }=\neg {\alpha }_1^{\prime }$, con ${\alpha }_1^{\prime }$ el resultado de reemplazar en ${\alpha }_1$ esas ocurrencias. Por ${\mathrm{Enu}}_k$, ${\alpha }_1\sim {\alpha }_1^{\prime }$, y por el Lema 4(b), $\neg {\alpha }_1\sim \neg {\alpha }_1^{\prime }$, es decir $\alpha \sim {\alpha }^{\prime }$.
• Caso $\alpha =\forall v{\alpha }_1$, con $v\in \mathrm{Var}$ y ${\alpha }_1\in F_k^{\tau }$. Sea ${\phi }_1\ne \alpha$. Por el Lema 8(d), cada ocurrencia reemplazada sucede en ${\alpha }_1$: ninguna toca la palabra $\forall v$ del principio. Luego ${\alpha }^{\prime }=\forall v{\alpha }_1^{\prime }$, con ${\alpha }_1^{\prime }$ el resultado de reemplazar en ${\alpha }_1$ esas ocurrencias. Por ${\mathrm{Enu}}_k$, ${\alpha }_1\sim {\alpha }_1^{\prime }$, y por el Lema 4(b), $\forall v{\alpha }_1\sim \forall v{\alpha }_1^{\prime }$, es decir $\alpha \sim {\alpha }^{\prime }$.
• Caso $\alpha =\exists v{\alpha }_1$, con $v\in \mathrm{Var}$ y ${\alpha }_1\in F_k^{\tau }$. Sea ${\phi }_1\ne \alpha$. Por el Lema 8(d), cada ocurrencia reemplazada sucede en ${\alpha }_1$. Luego ${\alpha }^{\prime }=\exists v{\alpha }_1^{\prime }$, con ${\alpha }_1^{\prime }$ como antes. Por ${\mathrm{Enu}}_k$, ${\alpha }_1\sim {\alpha }_1^{\prime }$, y por el Lema 4(b), $\exists v{\alpha }_1\sim \exists v{\alpha }_1^{\prime }$, es decir $\alpha \sim {\alpha }^{\prime }$.

Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ vale para todo $k\in \omega$. Como $F^{\tau }={\bigcup }_{k\ge 0}{F}_k^{\tau }$, toda $\alpha \in F^{\tau }$ está en algún $F_k^{\tau }$, y vale el lema. ∎

07 · Lo que hace perder puntos, y lo que se lleva

Lo que hace perder puntos. Escribir sólo el caso $({\alpha }_1\eta {\alpha }_2)$ y «los otros son similares»: en el parcial van $\neg$, $\forall$ y $\exists$, cada uno con su inciso del lema de ocurrencias. Usar el Lema 4(b) sin probarlo: la guía no lo prueba, y la lista no lo deja usar sin prueba. Olvidar en cada caso del paso la posibilidad ${\phi }_1=\alpha$, que es la única en que se usa la hipótesis ${\phi }_1\sim {\phi }_2$. Sacar el «posiblemente 0» del ${\mathrm{Enu}}_k$, que deja sin hipótesis inductiva al lado donde no se reemplazó nada. Decir que ${\alpha }^{\prime }=({\alpha }_1^{\prime }\eta {\alpha }_2^{\prime })$ sin justificar que ninguna ocurrencia pisa el nexo. Y en el caso $\forall$ del Lema 4(b), aplicar la hipótesis en $\overrightarrow{a}$ en lugar de en ${\downarrow }_i^a(\overrightarrow{a})$.

Lo que se lleva. El molde —inducción en el nivel, la ocurrencia bajada a una subfórmula por el lema de ocurrencias, el Lema 4(b) para subir— es el del Ejercicio 12, que lo hace dentro de una sola estructura. El 14 y el 15 reemplazan una palabra que no es fórmula, y por eso no se pueden resolver citando este lema: tienen su propia inducción, con el Lema 4(b) en los casos que no cambian. El caso del cuantificador, con la hipótesis aplicada en ${\downarrow }_i^a(\overrightarrow{a})$, es el mismo que en los Ejercicios 12 y 13. En el Ejercicio 7, con términos, no hay cuantificador: ninguna cláusula cambia la asignación, y alcanza con la hipótesis en una sola.

Para tener a mano

1. Regla de Inducción desde 0 sobre el nivel de $\alpha$, con ${\phi }_1$, ${\phi }_2$ y el «posiblemente 0» adentro de ${\mathrm{Enu}}_k$.
2. En cada caso, primero ${\phi }_1=\alpha$: entonces ${\alpha }^{\prime }=\alpha$ o ${\alpha }^{\prime }={\phi }_2$, y vale por hipótesis. Si no, la ocurrencia baja a una subfórmula por el Lema 8 de la Guía 9, (b), (c) o (d), y sube por ${\mathrm{Enu}}_k$ y el Lema 4(b).
3. Lema 4(b): un renglón de «sii» por forma, con la cláusula de $\models$ que corresponde. En $\forall$ y $\exists$ la hipótesis se aplica en ${\downarrow }_i^a(\overrightarrow{a})$.
4. Lema 8 de la Guía 9: (b), (c) y (d) salen de que ninguna fórmula empieza con nexo, $)$, $X$ o numeral, y de la Proposición 6; (a), de que una atómica no tiene $\neg$, cuantificadores ni nexos, y del Lema 2.
5. Medido: con ${\phi }_1=(\mathrm{P}(\mathrm{X}1)\to \mathrm{R}(\mathrm{X}1,\mathrm{X}2))$ y ${\phi }_2=(\neg \mathrm{P}(\mathrm{X}1)\vee \mathrm{R}(\mathrm{X}1,\mathrm{X}2))$, los cuatro reemplazos en $\alpha$ no difieren de $\alpha$ en ninguna de las 4164 estructuras de hasta tres elementos.