Ocurrencias y reemplazos

Un término es una palabra, y adentro tiene otras palabras: algunas son términos y otras no. La Guía 9 da el vocabulario para decir dónde está cada una —ocurrir a partir de una posición— y prueba que los subtérminos se acomodan como un árbol: dos ocurrencias son disjuntas o una está dentro de la otra, y nunca se cruzan. De ahí sale que reemplazar un subtérmino por otro término da un término, y lo mismo con fórmulas. Hay una sola ocurrencia que no se deja reemplazar por cualquier término: la variable pegada a un cuantificador.

01 · Ocurrir a partir de una posición

Dadas palabras $\alpha ,\beta \in {\Sigma }^{*}$, con $|\alpha |,|\beta |\ge 1$, y un natural $i\in \{1,\dots ,|\beta |\}$, se dice que $\alpha$ ocurre a partir de $i$ en $\beta$ cuando existen palabras $\delta ,\gamma$ tales que

$$\beta =\delta \alpha \gamma \text{ y }|\delta |=i-1$$

Leyendo $\beta$ desde el lugar $i$ en adelante se lee $\alpha$ completa, y después posiblemente otros símbolos. Esa ocurrencia ocupa las posiciones $i,\dots ,i+|\alpha |-1$. La misma $\alpha$ puede ocurrir a partir de $i$ y también a partir de $j$, con $i\ne j$: son distintas ocurrencias de $\alpha$ en $\beta$.

Los dos ejemplos de la guía son la palabra $aba$ dentro de dos palabras de 22 letras. En la primera ocurre a partir de 8 y de 15, y las dos ocurrencias ocupan las posiciones 8 a 10 y 15 a 17:

Son disjuntas: no comparten ninguna posición. En la segunda ocurre a partir de 8 y de 10, y las dos ocurrencias comparten la posición 10:

Una ocurrencia está contenida, o sucede, dentro de otra cuando todas sus posiciones están entre las de la otra. En $babbbfabcccfabccc$ la palabra $ab$ ocurre a partir de 2, de 7 y de 13, y $fabc$ a partir de 6 y de 12: la segunda ocurrencia de $ab$, en las posiciones 7 y 8, está contenida en la primera de $fabc$, que va de 6 a 9.

Las posiciones cuentan símbolos, no letras impresas. En los ejemplos de tipo de la guía, un nombre como $\mathrm{doli}$ son cuatro símbolos y la variable $\mathrm{X}12$ son tres: la $\mathrm{X}$, el 1 itálico y el 2 negrita. Por eso $\mathrm{X}1$ no ocurre en $\mathrm{X}12$: su 1 es negrita, y el de $\mathrm{X}12$ es itálico. En $\mathrm{Her}(\mathrm{X}12,\mathrm{X}1,\mathrm{doli})$, $\mathrm{X}1$ ocurre sólo a partir de 9. Que ninguna variable sea subpalabra de otra es lo que se gana con el último numeral en negrita, y está en Variables y términos de tipo τ.

02 · Reemplazar: una, todas a la vez, en secuencia

Una ocurrencia. Reemplazar una ocurrencia de $\alpha$ en $\beta$ por $\gamma$ es sacar los símbolos que ocupa y poner $\gamma$ en su lugar. Si $\beta =\delta \alpha \eta$ con $|\delta |=i-1$, reemplazar la ocurrencia a partir de $i$ da $\delta \gamma \eta$. El ejemplo de la guía: $abb$ ocurre en $ccabbgfgabbgg$ a partir de 3 y de 9, y reemplazar la primera por $oolala$ da $ccoolalagfgabbgg$. Como $oolala$ tiene tres letras más que $abb$, la otra ocurrencia se corrió: ahora está a partir de 12.

Todas a la vez. Cuando las ocurrencias de $\alpha$ en $\beta$ son disjuntas entre sí, tiene sentido hablar del resultado de reemplazar simultáneamente cada ocurrencia de $\alpha$ en $\beta$ por $\gamma$. Con $\alpha =yet$, $\beta =ghsyetcjjjyetbcpyeteabc$ y $\gamma =\text{\%\%}$, las ocurrencias están a partir de 4, 11 y 17, y el resultado es $ghs\text{\%}\text{\%}cjjj\text{\%}\text{\%}bcp\text{\%}\text{\%}eabc$. Si dos ocurrencias se superpusieran, como las de $aba$ en la segunda regla, no habría manera de reemplazar las dos: la posición compartida tendría que ir a parar a dos lugares.

En secuencia. La guía avisa que el reemplazo es simultáneo y no secuencial: no es reemplazar la primera ocurrencia, después reemplazarle al resultado su primera ocurrencia, y así sucesivamente. Deja armar los ejemplos al lector, y salen con palabras de cuatro letras.

Con $\alpha =ab$, $\gamma =ba$ y $\beta =abab$, las ocurrencias están a partir de 1 y de 3, disjuntas, y el reemplazo simultáneo da $baba$. El secuencial da otra cosa:

$$abab\to baab\to baba\to bbaa$$

y ahí se detiene, porque $bbaa$ ya no tiene $ab$. El paso que se desvía es el tercero: la $ab$ que se reemplaza en $baba$, a partir de 2, no estaba en $abab$; la formaron la última letra de un $ba$ y la primera del otro. El reemplazo secuencial ve las ocurrencias que los reemplazos anteriores fabrican, y el simultáneo sólo las que estaban.

Y si $\gamma$ contiene a $\alpha$, el secuencial puede no terminar nunca. Con $\gamma =aab$ y la misma $abab$:

$$abab\to aabab\to aaabab\to aaaabab\to \cdots$$

Cada paso agrega una letra y corre la primera ocurrencia un lugar a la derecha: la palabra es siempre $a^{n}bab$ con $n\ge 1$, su primera $ab$ empieza en la posición $n$, y reemplazarla da $a^{n+1}bab$, que vuelve a tener una. El simultáneo da $aabaab$ en un paso.

Varias palabras a la vez. También se reemplazan simultáneamente palabras distintas ${\alpha }_1,\dots ,{\alpha }_n$ en $\beta$, por ${\gamma }_1,\dots ,{\gamma }_n$, siempre que ${\alpha }_i\ne {\alpha }_j$ para $i\ne j$, que las ocurrencias de cada ${\alpha }_i$ sean disjuntas entre sí, y que una ocurrencia de ${\alpha }_i$ y una de ${\alpha }_j$, con $i\ne j$, también lo sean. El ejemplo de la guía reemplaza $gh$, $yet$ y $ana$ por $AA$, $BBBB$ y $CCC$ en

$$ghbbbyetbbgh\text{\%}\text{\%}ana\text{\#}\text{\#}ana\text{!}\text{!}\text{!}ana$$

donde $gh$ ocurre a partir de 1 y de 11, $yet$ a partir de 6, y $ana$ a partir de 15, 20 y 26. Son seis ocurrencias, todas disjuntas de a pares, y el resultado es $AAbbbBBBBbbAA\text{\%}\text{\%}CCC\text{\#}\text{\#}CCC\text{!}\text{!}\text{!}CCC$.

03 · Los subtérminos no se cruzan

Sean $s,t\in T^{\tau }$. Se dice que $s$ es subtérmino de $t$ si $s$ es subpalabra de $t$, y subtérmino propio si además no es igual a $t$. El lema que dice cómo están acomodados es el 4 de la guía.

Lema 4 (ocurrencias de términos en términos). Sean $r,s,t,t_1,\dots ,t_n\in T^{\tau }$, con $n\ge 1$, y sea $f\in {ℱ}_n$.

1. (a)Si $v\in \mathrm{Var}$, entonces $v$ no tiene subtérminos propios.
2. (b)Si $c\in 𝒞$, entonces $c$ no tiene subtérminos propios.
3. (c)Si $s\ne f(t_1,\dots ,t_n)$ y $s$ ocurre en $f(t_1,\dots ,t_n)$, entonces dicha ocurrencia sucede dentro de algún $t_j$, $j=1,\dots ,n$.
4. (d)Si $r,s$ ocurren en $t$, entonces dichas ocurrencias son disjuntas o una ocurre dentro de otra.
5. (e)Si $r$ ocurre en $t$, entonces las distintas ocurrencias de $r$ en $t$ son disjuntas.
6. (f)Si $t^{\prime }$ es el resultado de reemplazar una ocurrencia de $s$ en $t$ por $r$, entonces $t^{\prime }\in T^{\tau }$.

(a) y (b). La guía las deja al lector, y son la mitad del Ejercicio 12. Un subtérmino $s$ de una variable $v$ no es de la forma $g(\dots )$, porque tendría paréntesis, ni un nombre de constante, porque $v$ sólo tiene la $\mathrm{X}$ y numerales, que ningún nombre usa. Es una variable, así que empieza con la $\mathrm{X}$ —la única de $v$ está en la posición 1— y termina en un numeral negrita —el único de $v$ es el último—: $s=v$. Para una constante $c$, sus símbolos no son $\mathrm{X}$ ni paréntesis, así que un subtérmino es otro nombre de constante, y ningún nombre de constante es subpalabra propia de otro: es una de las condiciones de la definición de tipo.

(c), la que hace el trabajo. Si la ocurrencia de $s$ empieza dentro de algún $t_j$, el mordisqueo de términos la encierra en $t_j$: un término que empieza en medio de otro no puede asomarse por detrás de él. Queda ver que no empieza en ningún otro lado. No empieza en un paréntesis ni en una coma, porque ningún término empieza así. Y no empieza en las primeras $|f|$ posiciones, las del nombre $f$: ahí $s$ tendría que ser $g(s_1,\dots ,s_m)$, porque su primer símbolo es de $f$, y los nombres de constante no comparten símbolos con los de función; no a partir de 1, porque $s$ sería tramo inicial propio de $f(t_1,\dots ,t_n)$, que el mordisqueo prohíbe; y no más adelante, porque entonces $g$ sería tramo final propio de $f$, que la definición de tipo también prohíbe.

(d), por inducción. Con la Regla de Inducción desde 0 sobre

${\mathrm{Enu}}_k$: si $t\in T_k^{\tau }$ y $r,s\in T^{\tau }$ ocurren en $t$, entonces dichas ocurrencias son disjuntas o una ocurre dentro de otra.

En la base, $t$ es una variable o una constante, y por (a) y (b) $r=s=t$: las dos ocurrencias son la de $t$ entera. En el paso, si $t=f(t_1,\dots ,t_n)$ con los $t_j\in T_k^{\tau }$ y ni $r$ ni $s$ son $t$, por (c) cada ocurrencia sucede dentro de algún argumento. Si caen en argumentos distintos son disjuntas, porque los argumentos ocupan tramos disjuntos; si caen en el mismo, lo resuelve ${\mathrm{Enu}}_k$.

(e) y (f). El (e) sale del (d) con $s=r$: dos ocurrencias de la misma palabra tienen la misma longitud, y si una está contenida en la otra ocupan las mismas posiciones, o sea que es la misma ocurrencia. El (f) es otra inducción, la otra mitad del Ejercicio 12. Si $t$ es una variable o una constante, la ocurrencia de $s$ es $t$ entera y el resultado es $r$. Si $t=f(t_1,\dots ,t_n)$ y $s\ne t$, por (c) la ocurrencia está dentro de un $t_j$, el resultado es $f(t_1,\dots ,t_j^{\prime },\dots ,t_n)$, y $t_j^{\prime }$ es término por hipótesis inductiva.

Medido en el término de nivel 3 de la guía,

$$\mathrm{P}(\mathrm{MAS}(\mathrm{P}(\mathrm{X}4),\mathrm{MAS}(\mathrm{X}1,\mathrm{X}2,\mathrm{X}3,\mathrm{X}4),\mathrm{X}19,\mathrm{X}5))$$

de 37 símbolos, del tipo con constantes $\mathrm{uno}$ y $\mathrm{doli}$ y funciones $\mathrm{MAS}$ de aridad 4 y $\mathrm{P}$ de aridad 1. Tiene 11 ocurrencias de subtérminos —él mismo, los dos $\mathrm{MAS}$, $\mathrm{P}(\mathrm{X}4)$, y siete variables, con $\mathrm{X}4$ dos veces, a partir de 9 y de 26—, que forman 55 pares: 31 disjuntos, 24 anidados y ninguno que se cruce. El cruce no es raro entre palabras cualesquiera: de los 246 753 pares de ocurrencias de subpalabras de este término, 73 815 se cruzan.

El (f) pide que $s$ y $r$ sean términos, y las dos condiciones trabajan. La palabra $\mathrm{X}1,\mathrm{X}2$ ocurre en ese término a partir de 17 y no es un término. Reemplazarla por el término $\mathrm{uno}$ da

$$\mathrm{P}(\mathrm{MAS}(\mathrm{P}(\mathrm{X}4),\mathrm{MAS}(\mathrm{uno},\mathrm{X}3,\mathrm{X}4),\mathrm{X}19,\mathrm{X}5))$$

que no es un término: el $\mathrm{MAS}$ de adentro quedó con tres argumentos. Reemplazarla por $\mathrm{X}2,\mathrm{X}1$ sí da un término, pero eso no lo garantiza ningún lema; es suerte de este caso. En cambio, el subtérmino $\mathrm{MAS}(\mathrm{X}1,\mathrm{X}2,\mathrm{X}3,\mathrm{X}4)$, a partir de 13, reemplazado por $\mathrm{uno}$, da $\mathrm{P}(\mathrm{MAS}(\mathrm{P}(\mathrm{X}4),\mathrm{uno},\mathrm{X}19,\mathrm{X}5))$, y la segunda $\mathrm{X}4$ reemplazada por $\mathrm{P}(\mathrm{P}(\mathrm{uno}))$ da un término de nivel 5. El nivel cambia; lo que se conserva es ser término.

04 · Una prueba rigurosa sin definir «ocurrencia»

«Ocurre a partir de $i$» está definido con precisión: es la ecuación $\beta =\delta \alpha \gamma$ con $|\delta |=i-1$. Pero «una ocurrencia», «disjuntas», «sucede dentro de» y «el resultado de reemplazar» la guía los deja en el castellano, y dice que no los va a definir en forma matemática precisa. Y sin embargo la prueba del Lema 4 es una prueba. La guía lo explica en una nota a continuación del lema: la prueba sólo usa propiedades del concepto de ocurrencia y de reemplazo que tendrían que ser comunes a cualquier definición o formulación matemática que se hiciera de ellos.

Leída de nuevo con esa lente, la prueba usa poco: que una ocurrencia a partir de $i$ ocupa las posiciones $i$ a $i+|\alpha |-1$; que estar dentro de otra o ser disjunta es una relación entre esos tramos; y que reemplazar una ocurrencia que vive dentro de un argumento es reemplazarla en el argumento y dejar el resto de la palabra igual. Cualquier formalización razonable —por ejemplo, identificar la ocurrencia con el par $(\alpha ,i)$ y el reemplazo con $\delta \gamma \eta$— cumple las tres, así que la prueba vale para todas. La guía agrega que en este caso sí se puede dar una definición precisa y satisfactoria, a diferencia de otros conceptos, como el de prueba absoluta de consistencia, para los que todavía no se encontró una formulación matemática adecuada.

05 · Las subfórmulas tampoco se cruzan

Una fórmula $\phi$ es subfórmula de una fórmula $\psi$ cuando $\phi$ es subpalabra de $\psi$, y propia si además no es igual a $\psi$. El Lema 8 es el Lema 4 con fórmulas, y se apoya en la lectura única de fórmulas como aquél se apoyaba en la de términos.

Lema 8 (ocurrencias de fórmulas en fórmulas). Sea $\tau$ un tipo y $\phi ,\psi ,\varphi ,{\phi }_1,{\phi }_2,\lambda$ fórmulas de tipo $\tau$.

1. (a)Las fórmulas atómicas no tienen subfórmulas propias.
2. (b)Si $\phi \ne (\psi \eta \varphi )$ y $\phi$ ocurre en $(\psi \eta \varphi )$, entonces tal ocurrencia sucede en $\psi$ o en $\varphi$.
3. (c)Si $\phi \ne \neg \psi$ y $\phi$ ocurre en $\neg \psi$, entonces tal ocurrencia sucede en $\psi$.
4. (d)Si $\phi \ne Qv\psi$ y $\phi$ ocurre en $Qv\psi$, entonces tal ocurrencia sucede en $\psi$.
5. (e)Si ${\phi }_1,{\phi }_2$ ocurren en $\phi$, entonces dichas ocurrencias son disjuntas o una contiene a la otra.
6. (f)Si $\psi$ ocurre en $\phi$, entonces las distintas ocurrencias de $\psi$ en $\phi$ son disjuntas.
7. (g)Si ${\lambda }^{\prime }$ es el resultado de reemplazar alguna ocurrencia de ${\phi }_1$ en $\lambda$ por ${\phi }_2$, entonces ${\lambda }^{\prime }\in F^{\tau }$.

La guía prueba el (g) con el mismo molde que el (f) de términos. En la base, $\lambda$ es atómica, por (a) ${\phi }_1=\lambda$, y el resultado es ${\phi }_2$. En el paso, si $\lambda =({\lambda }_1\eta {\lambda }_2)$ con ${\lambda }_1,{\lambda }_2\in F_k^{\tau }$ y ${\phi }_1\ne \lambda$, por (b) la ocurrencia reemplazada sucede en ${\lambda }_1$ o en ${\lambda }_2$; si es en ${\lambda }_2$, el resultado es $({\lambda }_1\eta {\lambda }_2^{\prime })$, y ${\lambda }_2^{\prime }\in F^{\tau }$ por hipótesis inductiva. Los casos $\neg {\lambda }_1$ y $Qv{\lambda }_1$ son iguales, con (c) y (d).

Medido en la fórmula de la página 15 de la guía, de 33 símbolos,

$$((\mathrm{X}1\equiv \mathrm{X}2)\wedge \exists \mathrm{X}2\mathrm{Her}(\mathrm{P}(\mathrm{doli}),\mathrm{doli},\mathrm{X}2))$$

hay cuatro ocurrencias de subfórmulas: ella misma, $(\mathrm{X}1\equiv \mathrm{X}2)$ a partir de 2, $\exists \mathrm{X}2\mathrm{Her}(\mathrm{P}(\mathrm{doli}),\mathrm{doli},\mathrm{X}2)$ a partir de 10 y $\mathrm{Her}(\mathrm{P}(\mathrm{doli}),\mathrm{doli},\mathrm{X}2)$ a partir de 13. De sus seis pares, dos son disjuntos, cuatro anidados y ninguno se cruza.

Una consecuencia: el Ejercicio 20. Si $\psi ,\phi ,\alpha \in F^{\tau }$ son tales que $\psi$ ocurre en $\alpha$ a partir de $i$ y $\phi$ ocurre en $\alpha$ a partir de $i+1$, entonces $|\phi |<|\psi |$. La ocurrencia de $\psi$ ocupa las posiciones $i,\dots ,i+|\psi |-1$, y la de $\phi$ las $i+1,\dots ,i+|\phi |$. Como toda fórmula tiene más de un símbolo, la posición $i+1$ está en las dos: no son disjuntas. Por el (e), una contiene a la otra, y la de $\phi$ no puede contener a la de $\psi$, porque empieza después. Entonces la de $\psi$ contiene a la de $\phi$: $i+|\phi |\le i+|\psi |-1$. En la fórmula de arriba pasa en las posiciones 1 y 2: la que empieza en 1 tiene 33 símbolos y $(\mathrm{X}1\equiv \mathrm{X}2)$, que empieza en 2, tiene 7.

06 · Términos en fórmulas: la ocurrencia contigua

Un término dentro de una fórmula vive casi siempre dentro de una atómica, y ahí lo cubre el Lema 4. La excepción es la variable que acompaña a un cuantificador. Si $t$ es un término y $\phi$ una fórmula, una ocurrencia de $t$ en $\phi$ se llama 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$. Dicho de otra forma: cuando está contenida en una ocurrencia de una palabra $Qt$, con $Q\in \{\forall ,\exists \}$.

Sólo un término que sea variable puede tener una ocurrencia contigua, por dos hechos fáciles de probar: si $Q\in \{\forall ,\exists \}$ ocurre a partir de $i$ en una fórmula, entonces $\mathrm{X}$ ocurre a partir de $i+1$; y si un término empieza con $\mathrm{X}$, es una variable.

Lema 9 (ocurrencias de términos en fórmulas). Sea $\tau$ un tipo.

1. (a)Si $t$ ocurre en $(t_1\equiv t_2)$, entonces tal ocurrencia es en $t_1$ o en $t_2$.
2. (b)Si $t$ ocurre en $r(t_1,\dots ,t_n)$, entonces dicha ocurrencia sucede dentro de algún $t_j$, $j=1,\dots ,n$.
3. (c)Si $t$ ocurre en $(\psi \eta \varphi )$, entonces tal ocurrencia es en $\psi$ o en $\varphi$.
4. (d)Si $t$ ocurre en $\neg \psi$, entonces tal ocurrencia es en $\psi$.
5. (e)Si $t$ ocurre en $Q{x}_k\psi$, entonces tal ocurrencia es la primera de $x_k$ o sucede dentro de $\psi$.
6. (f)Si $t_1,t_2$ ocurren en $\phi$, entonces dichas ocurrencias son disjuntas o una contiene a la otra.
7. (g)Si $t$ ocurre en $\phi$, entonces las distintas ocurrencias de $t$ en $\phi$ son disjuntas.
8. (h)Si ${\lambda }^{\prime }$ es el resultado de reemplazar alguna ocurrencia no contigua de $t_1$ en $\lambda$ por $t_2$, entonces ${\lambda }^{\prime }\in F^{\tau }$.

La guía lo acepta sin prueba y remite al apunte. El (e) es el único ítem con dos salidas, y la primera —la $x_k$ pegada a $Q$— es justamente la ocurrencia contigua: no está dentro de ninguna atómica, así que nada de lo que se sabe de términos la protege. Por eso el (h) la excluye. Con

$$\forall \mathrm{X}1\mathrm{Her}(\mathrm{X}1,\mathrm{doli},\mathrm{P}(\mathrm{X}1))$$

de 21 símbolos, $\mathrm{X}1$ ocurre a partir de 2, 8 y 18, y la de 2 es la contigua. Reemplazar la de 8 por $\mathrm{P}(\mathrm{X}1)$ da $\forall \mathrm{X}1\mathrm{Her}(\mathrm{P}(\mathrm{X}1),\mathrm{doli},\mathrm{P}(\mathrm{X}1))$, una fórmula, como promete el (h). Reemplazar la de 2 por el mismo término da

$$\forall \mathrm{P}(\mathrm{X}1)\mathrm{Her}(\mathrm{X}1,\mathrm{doli},\mathrm{P}(\mathrm{X}1))$$

que no es una fórmula: después de $\forall$ tiene que venir una variable. Si lo que entra es otra variable, la palabra sigue siendo fórmula —$\forall \mathrm{X}2\mathrm{Her}(\mathrm{X}1,\mathrm{doli},\mathrm{P}(\mathrm{X}1))$—, pero ya dice otra cosa: la $\mathrm{X}1$ que antes estaba acotada ahora es libre. Ése es el caso del Ejercicio 14(d).

07 · Marcar y reemplazar

Abajo, una palabra del tipo de la guía —constantes $\mathrm{uno}$ y $\mathrm{doli}$, funciones $\mathrm{MAS}$ y $\mathrm{P}$, relación $\mathrm{Her}$ de aridad 3— con sus posiciones. Marcás dos ocurrencias tocando el primer y el último símbolo de cada una, y reemplazás la que está en azul por lo que escribas. El resultado se lee de afuera hacia adentro.

En el término de la página 2, marcar $\mathrm{X}1,\mathrm{X}2$ y reemplazarla por $\mathrm{uno}$ rompe el $\mathrm{MAS}$ de adentro; marcar $\mathrm{MAS}(\mathrm{X}1,\mathrm{X}2,\mathrm{X}3,\mathrm{X}4)$ y reemplazarlo por lo mismo, no. Y en los tres ejemplos, ninguna pareja de ocurrencias que sean cada una término o fórmula se cruza —son 21, 55 y 55 pares—: para ver un cruce, una de las dos tiene que no ser ni término ni fórmula.

08 · En los ejercicios

Ejercicio 12. Pide completar las partes del Lema 4 que la guía no hace: (a), (b), (e) y (f), más el detalle de la base del (d). Son las de la sección 03, y están resueltas en Se compara por el lado de lo que ya se sabe.

Ejercicio 14(d). Reemplazar algunas ocurrencias de la variable $x_1$ en $\phi$ por $x_2$ da una fórmula. Las ocurrencias no contiguas las cubre el Lema 9(h), y como $|x_1|=|x_2|$, reemplazar una no corre las posiciones de las demás. La contigua no la cubre ningún lema, pero en $Qv{\phi }_1$ reemplazar $v$ por otra variable deja $Q{v}^{\prime }{\phi }_1$, que sigue teniendo la forma: la inducción en $F_k^{\tau }$ cierra con eso. En $\forall \mathrm{X}1(\mathrm{X}1\equiv \mathrm{X}2)$ cambiar sólo la $\mathrm{X}1$ de la posición 2 da $\forall \mathrm{X}2(\mathrm{X}1\equiv \mathrm{X}2)$: otra fórmula, con otro significado.

Ejercicio 14(e). Reemplazar algunas ocurrencias de $\forall x_1\exists x_2$ por $\exists x_1\forall x_2$ también da una fórmula, y acá no hay lema que ayude, porque $\forall x_1\exists x_2$ no es término ni fórmula. Lo que la salva es que tiene un solo $\forall$, en su primer símbolo: dos ocurrencias que se superpusieran tendrían que empezar en el mismo lugar, así que son disjuntas y el reemplazo de varias tiene sentido. La prueba es una inducción en $F_k^{\tau }$ donde el único caso nuevo es una ocurrencia a partir de la posición 1, y ahí $\phi =\forall x_1\exists x_2\psi$. Así, $\forall \mathrm{X}1\exists \mathrm{X}2(\mathrm{X}1\equiv \mathrm{X}2)$ pasa a $\exists \mathrm{X}1\forall \mathrm{X}2(\mathrm{X}1\equiv \mathrm{X}2)$. Los dos ítems están en Contar paréntesis no alcanza.

Ejercicio 20. Es la consecuencia del Lema 8(e) de la sección 05, y está en Una fórmula puede ser el final de otra, nunca el principio. Si en una resolución se usa el Lema 4, el 8 o el 9, la regla de corrección de la cátedra pide enunciarlo y probarlo, salvo que la consigna diga que se puede usar sin demostración; el 9, que la guía no prueba, se saca del apunte.

Para tener a mano

1. $\alpha$ ocurre a partir de $i$ en $\beta$ si $\beta =\delta \alpha \gamma$ con $|\delta |=i-1$. Esa ocurrencia ocupa las posiciones $i$ a $i+|\alpha |-1$, contando símbolos.
2. Dos ocurrencias son disjuntas si no comparten posiciones; una sucede dentro de otra si sus posiciones están entre las de la otra. Entre palabras cualesquiera, también pueden cruzarse.
3. El reemplazo simultáneo pide ocurrencias disjuntas y es uno solo. El secuencial puede dar otra cosa, porque ve las ocurrencias que fabrica, y puede no terminar si $\gamma$ contiene a $\alpha$.
4. Lema 4: variables y constantes no tienen subtérminos propios; un subtérmino propio de $f(t_1,\dots ,t_n)$ está dentro de algún $t_j$; dos subtérminos son disjuntos o anidados; reemplazar un subtérmino por un término da un término.
5. Lema 8: lo mismo con subfórmulas. Ejercicio 20: si una fórmula ocurre a partir de $i$ y otra a partir de $i+1$, la segunda está dentro de la primera y es más corta.
6. Lema 9: lo mismo con términos en fórmulas, salvo la ocurrencia contigua, la $x_k$ de $Q{x}_k$. Reemplazarla por un término que no es variable rompe la fórmula; por una variable, no la rompe pero le cambia el sentido.
7. La prueba es rigurosa sin definir «ocurrencia» porque sólo usa propiedades que cualquier definición razonable tiene que cumplir.