Lo que los dos tipos comparten dice lo mismo

El enunciado, textual: «Sean

$$\tau =(\{\mathrm{un},\mathrm{do},\mathrm{△}\},\{+,\mathrm{Fa}\},\{\mathrm{Her},\le \},\{(+,2),(\mathrm{Fa},1),(\mathrm{Her},3),(\le ,2)\})$$ $${\tau }^{\prime }=(\{\mathrm{un},\mathrm{do},\mathrm{▽}\},\{+,\mathrm{G}\},\{\mathrm{Her},\mathrm{r}\},\{(+,2),(\mathrm{G},4),(\mathrm{Her},3),(\mathrm{r},1)\})$$

Notar que ${\tau }_{\cap }=(\{\mathrm{un},\mathrm{do}\},\{+\},\{\mathrm{Her}\},\{(+,2),(\mathrm{Her},3)\})$. Sean $𝐀$ y ${𝐀}^{\prime }$ modelos de tipo $\tau$ y ${\tau }^{\prime }$ respectivamente tales que $A=A^{\prime }$, ${\mathrm{un}}^{𝐀}={\mathrm{un}}^{{𝐀}^{\prime }}$, ${\mathrm{do}}^{𝐀}={\mathrm{do}}^{{𝐀}^{\prime }}$, ${+}^{𝐀}={+}^{{𝐀}^{\prime }}$ y ${\mathrm{Her}}^{𝐀}={\mathrm{Her}}^{{𝐀}^{\prime }}$. Entonces: (a) para cada $t{=}_{d}t(v_1,\dots ,v_n)\in T^{{\tau }_{\cap }}$ se tiene que $t^{𝐀}[a_1,a_2,\dots ,a_n]=t^{{𝐀}^{\prime }}[a_1,a_2,\dots ,a_n]$ para cada $a_1,a_2,\dots ,a_n\in A$; (b) para cada $\phi {=}_d\phi (v_1,\dots ,v_n)\in F^{{\tau }_{\cap }}$ se tiene que $𝐀\models \phi [a_1,a_2,\dots ,a_n]$ si y sólo si ${𝐀}^{\prime }\models \phi [a_1,a_2,\dots ,a_n]$, para cada $a_1,a_2,\dots ,a_n\in A$.»

No viene de una guía. Está enunciado en notación declaratoria, así que el encabezado de la lista pide resolverlo dentro de ella, con los lemas y convenciones de la sección «Manejo técnico de la notación declaratoria» de la Guía 11.

01 · Qué dice, en criollo

$𝐀$ y ${𝐀}^{\prime }$ son estructuras de tipos distintos: $𝐀$ sabe interpretar $\mathrm{△}$, $\mathrm{Fa}$ y $\le$, que ${𝐀}^{\prime }$ ni conoce, y ${𝐀}^{\prime }$ sabe interpretar $\mathrm{▽}$, $\mathrm{G}$ y $\mathrm{r}$. Pero en lo que los dos tipos tienen en común —$\mathrm{un}$, $\mathrm{do}$, $+$ y $\mathrm{Her}$— son idénticas, y además tienen el mismo universo. El ejercicio dice que un término o una fórmula que sólo usa el vocabulario común no las puede distinguir.

Un caso concreto. Universo $\{0,1,2,3\}$ para los dos; $\mathrm{un}=1$, $\mathrm{do}=2$, $+$ la suma módulo 4 y $\mathrm{Her}(x,y,z)$ si $x+y=z$ módulo 4, en los dos. Además, en $𝐀$: $\mathrm{△}=0$, $\mathrm{Fa}(x)=x+1$ módulo 4 y $\le$ el orden usual; en ${𝐀}^{\prime }$: $\mathrm{▽}=3$, $\mathrm{G}$ el máximo de sus cuatro argumentos y $\mathrm{r}$ los pares. La fórmula $\exists x_3\mathrm{Her}(x_1,x_3,\mathrm{do})$ es de ${\tau }_{\cap }$ y es verdadera en las dos para cualquier $a_1$. La fórmula $\le (x_1,x_2)$ es de $\tau$ pero no de ${\tau }^{\prime }$: preguntar si ${𝐀}^{\prime }\models \le (x_1,x_2)[0,1]$ no tiene sentido. Medido con las cinco fórmulas de ${\tau }_{\cap }$ del widget, en los 16 pares $(a_1,a_2)$, la verdad coincide siempre. Si se cambia ${\mathrm{Her}}^{{𝐀}^{\prime }}$ por $x·y=z$ módulo 4 —rompiendo una hipótesis—, cuatro de las cinco pasan a diferir en algún par; la que no, $(+(x_1,\mathrm{un})\equiv x_2)$, no usa $\mathrm{Her}$.

Lo que hay que notar antes de empezar, porque el enunciado lo da por sentado:

• Un término de ${\tau }_{\cap }$ es término de $\tau$ y de ${\tau }^{\prime }$; una fórmula de ${\tau }_{\cap }$ es fórmula de $\tau$ y de ${\tau }^{\prime }$. Si no, $t^{𝐀}$ o ${𝐀}^{\prime }\models \phi$ no estarían definidos. Se prueba abajo, en dos líneas.
• $A=A^{\prime }$ hace dos trabajos: que $a_1,\dots ,a_n\in A$ sean también elementos de $A^{\prime }$, para que $t^{{𝐀}^{\prime }}[a_1,\dots ,a_n]$ tenga sentido, y que «para todo $a\in A$» y «para todo $a\in A^{\prime }$» digan lo mismo en el caso del cuantificador.
• ${\mathrm{un}}^{𝐀}={\mathrm{un}}^{{𝐀}^{\prime }}$, ${\mathrm{do}}^{𝐀}={\mathrm{do}}^{{𝐀}^{\prime }}$, ${+}^{𝐀}={+}^{{𝐀}^{\prime }}$ se usan en (a), y ${\mathrm{Her}}^{𝐀}={\mathrm{Her}}^{{𝐀}^{\prime }}$ en las atómicas de (b): es el único nombre de relación de ${\tau }_{\cap }$.

02 · Las herramientas

Los niveles (Guía 9): $T_0^{\tau }=\mathrm{Var}\cup \mathrm{𝒞}$; $T_{k+1}^{\tau }$ agrega $f(t_1,\dots ,t_m)$ con $f\in {ℱ}_m$ y $t_i\in T_k^{\tau }$. $F_0^{\tau }$ son las atómicas $(t\equiv s)$ y $r(t_1,\dots ,t_m)$ con términos de tipo $\tau$; $F_{k+1}^{\tau }$ agrega $\neg \phi$, $(\phi \eta \psi )$ y $Qv\phi$ con $\phi ,\psi \in F_k^{\tau }$.

Para términos, de la Guía 11, p. 8–9: el Lema 1 (si $t{=}_{d}t(v_1,\dots ,v_n)$, entonces $t=c$, o $t=v_j$, o $t=f(t_1,\dots ,t_m)$ con $f\in {ℱ}_m$, $m\ge 1$; una y sólo una; y si $t\in T_{k+1}^{\tau }$, en el tercer caso $t_1,\dots ,t_m\in T_k^{\tau }$), la Convención 5 (en ese tercer caso, $t_i{=}_d{t}_i(v_1,\dots ,v_n)$) y el Lema 3 ($t^{𝐀}[a_1,\dots ,a_n]$ es $c^{𝐀}$, $a_j$ o $f^{𝐀}(t_1^{𝐀}[a_1,\dots ,a_n],\dots ,t_m^{𝐀}[a_1,\dots ,a_n])$ según el caso). Están enunciados enteros en el Ejercicio 28.

Para fórmulas, de la Guía 11, p. 9–11: el Lema 4 (las seis formas de $\phi {=}_d\phi (v_1,\dots ,v_n)$: $(t\equiv s)$, $r(t_1,\dots ,t_m)$, $({\phi }_1\eta {\phi }_2)$, $\neg {\phi }_1$, $Q{v}_j{\phi }_1$ con $j\in \{1,\dots ,n\}$, $Qv{\phi }_1$ con $v\notin \{v_1,\dots ,v_n\}$; y si $\phi \in F_{k+1}^{\tau }$ las piezas están en $F_k^{\tau }$), la Convención 6 (las piezas quedan declaradas con $v_1,\dots ,v_n$, salvo en la última forma, donde ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n,v)$) y el Lema 6 (la verdad de $\phi$ en términos de la de sus piezas, casos (1) a (11)). Enunciados enteros en el Ejercicio 29.

Los lemas son para un tipo cualquiera, y acá se usan con tres: el Lema 1 y el Lema 4 con ${\tau }_{\cap }$, para desarmar $t$ o $\phi$; el Lema 3 y el Lema 6 con $\tau$ en $𝐀$ y con ${\tau }^{\prime }$ en ${𝐀}^{\prime }$, para calcular.

Lo que se prueba aparte: $T^{{\tau }_{\cap }}\subseteq T^{\tau }$ y $F^{{\tau }_{\cap }}\subseteq F^{\tau }$ (y lo mismo con ${\tau }^{\prime }$). Usaremos la Regla de Inducción desde 0 con ${\mathrm{Enu}}_k$: $T_k^{{\tau }_{\cap }}\subseteq T_k^{\tau }$. Para $k=0$: $T_0^{{\tau }_{\cap }}=\mathrm{Var}\cup \{\mathrm{un},\mathrm{do}\}\subseteq \mathrm{Var}\cup \{\mathrm{un},\mathrm{do},\mathrm{△}\}=T_0^{\tau }$. Si vale ${\mathrm{Enu}}_k$ y $t\in T_{k+1}^{{\tau }_{\cap }}$, o bien $t\in T_k^{{\tau }_{\cap }}\subseteq T_k^{\tau }\subseteq T_{k+1}^{\tau }$, o bien $t=+(t_1,t_2)$ con $t_1,t_2\in T_k^{{\tau }_{\cap }}\subseteq T_k^{\tau }$, y como $+$ es nombre de función de aridad 2 en $\tau$, $t\in T_{k+1}^{\tau }$. Para fórmulas, también por la Regla de Inducción desde 0, con ${\mathrm{Enu}}_k$: $F_k^{{\tau }_{\cap }}\subseteq F_k^{\tau }$. Una atómica de ${\tau }_{\cap }$ es $(t\equiv s)$ con $t,s\in T^{{\tau }_{\cap }}\subseteq T^{\tau }$, o $\mathrm{Her}(t_1,t_2,t_3)$ con $t_i\in T^{\tau }$ y $\mathrm{Her}$ de aridad 3 en $\tau$; en los dos casos está en $F_0^{\tau }$. Si vale ${\mathrm{Enu}}_k$ y $\phi \in F_{k+1}^{{\tau }_{\cap }}$, o bien $\phi \in F_k^{{\tau }_{\cap }}\subseteq F_k^{\tau }\subseteq F_{k+1}^{\tau }$, o bien φ se arma con piezas de nivel $k$: si $\phi ,\psi \in F_k^{{\tau }_{\cap }}\subseteq F_k^{\tau }$, entonces $\neg \phi$, $(\phi \eta \psi )$ y $Qv\phi$ están en $F_{k+1}^{\tau }$. Para ${\tau }^{\prime }$ es la misma cuenta con $\mathrm{▽}$ en lugar de $\mathrm{△}$. En particular, el nivel de $t$ o $\phi$ en ${\tau }_{\cap }$ acota su nivel en $\tau$ y en ${\tau }^{\prime }$, aunque la prueba no lo necesita.

03 · La mariposa: dos inducciones, la segunda apoyada en la primera

(a) es el Ejercicio 28 sin $F$. Inducción en $k$ con $t\in T_k^{{\tau }_{\cap }}$. El Lema 1, aplicado en ${\tau }_{\cap }$, deja tres casos: $t$ es $\mathrm{un}$ o $\mathrm{do}$ (las únicas constantes de ${\tau }_{\cap }$), $t$ es una $v_j$, o $t=+(t_1,t_2)$ (la única función). El Lema 3 calcula cada lado —en $𝐀$ con $\tau$, en ${𝐀}^{\prime }$ con ${\tau }^{\prime }$— y los dos dan lo mismo porque las interpretaciones coinciden y, en el último caso, por la hipótesis inductiva.

(b) apoya las atómicas en (a). $(t\equiv s)$: el Lema 6 (1) la convierte en una igualdad de valores de términos de ${\tau }_{\cap }$, y (a) dice que esos valores son los mismos en $𝐀$ y en ${𝐀}^{\prime }$. $\mathrm{Her}(t_1,t_2,t_3)$: lo mismo con el Lema 6 (2) y ${\mathrm{Her}}^{𝐀}={\mathrm{Her}}^{{𝐀}^{\prime }}$. Los conectivos son la hipótesis inductiva en las piezas.

El cuantificador es donde se usa $A=A^{\prime }$. El Lema 6 (8) en $𝐀$ dice «para todo $a\in A$», y en ${𝐀}^{\prime }$, «para todo $a\in A^{\prime }$». Con la hipótesis inductiva, lo de adentro es lo mismo; si los universos fueran distintos, los dos «para todo» recorrerían conjuntos distintos y no habría nada que comparar.

El ${\mathrm{Enu}}_k$. $𝐀$ y ${𝐀}^{\prime }$ los fija el enunciado y no cambian en ningún caso, así que pueden quedar afuera. Lo que va adentro es lo que cambia: $n$ y las variables (el caso $Qv{\phi }_1$ con $v$ fuera de la lista declara ${\phi }_1$ con $n+1$ variables), la fórmula y los elementos (el caso $Q{v}_j{\phi }_1$ aplica la hipótesis con $a$ en el lugar de $a_j$).

Lo medido. Las cinco fórmulas de ${\tau }_{\cap }$ del widget coinciden en $𝐀$ y ${𝐀}^{\prime }$ en los 16 pares. Con ${\mathrm{Her}}^{{𝐀}^{\prime }}$ cambiado, difieren en 14, 4, 10 y 8 pares las cuatro que usan $\mathrm{Her}$, y en 0 la que no. Las otras cinco no son de ${\tau }_{\cap }$: $\le (x_1,x_2)$ y $(\mathrm{Fa}(x_1)\equiv +(x_1,\mathrm{un}))$ son sólo de $\tau$, $\mathrm{r}(x_1)$ y $(\mathrm{G}(x_1,x_1,x_2,x_2)\equiv x_2)$ sólo de ${\tau }^{\prime }$, y $(\mathrm{△}\equiv \mathrm{▽})$ no es fórmula de ninguno de los dos.

04 · El escarabajo: la prueba escrita

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

Recordemos que $t\in T^{{\tau }_{\cap }}$ es término de $\tau$ y de ${\tau }^{\prime }$, y que $a_1,\dots ,a_n\in A=A^{\prime }$, así que los dos lados están definidos.

Prueba de que ${\mathrm{Enu}}_0$ es verdadero. Sea $t\in T_0^{{\tau }_{\cap }}$ con $t{=}_{d}t(v_1,\dots ,v_n)$, y sean $a_1,\dots ,a_n\in A$. Como $T_0^{{\tau }_{\cap }}=\mathrm{Var}\cup \{\mathrm{un},\mathrm{do}\}$, por el Lema 1 (en ${\tau }_{\cap }$) $t$ es $\mathrm{un}$, $\mathrm{do}$ o alguna $v_j$.

• Si $t=\mathrm{un}$: $t^{𝐀}[a_1,\dots ,a_n]={\mathrm{un}}^{𝐀}$ (Lema 3 (1) en $𝐀$) $={\mathrm{un}}^{{𝐀}^{\prime }}$ (hipótesis) $=t^{{𝐀}^{\prime }}[a_1,\dots ,a_n]$ (Lema 3 (1) en ${𝐀}^{\prime }$).
• Si $t=\mathrm{do}$: igual, con ${\mathrm{do}}^{𝐀}={\mathrm{do}}^{{𝐀}^{\prime }}$.
• Si $t=v_j$: $t^{𝐀}[a_1,\dots ,a_n]=a_j=t^{{𝐀}^{\prime }}[a_1,\dots ,a_n]$, por el Lema 3 (2) en $𝐀$ y en ${𝐀}^{\prime }$.

Prueba de que ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$. Supongamos que vale ${\mathrm{Enu}}_k$. Sean $t\in T_{k+1}^{{\tau }_{\cap }}$ con $t{=}_{d}t(v_1,\dots ,v_n)$ y $a_1,\dots ,a_n\in A$. Caso $t\in T_k^{{\tau }_{\cap }}$: vale por ${\mathrm{Enu}}_k$. Caso $t\in T_{k+1}^{{\tau }_{\cap }}-T_k^{{\tau }_{\cap }}$: $t$ no es constante ni variable, así que por el Lema 1 en ${\tau }_{\cap }$, $t=+(t_1,t_2)$ —$+$ es el único nombre de función de ${\tau }_{\cap }$, de aridad 2— con $t_1,t_2\in T_k^{{\tau }_{\cap }}$. Por la Convención 5, $t_1{=}_d{t}_1(v_1,\dots ,v_n)$ y $t_2{=}_d{t}_2(v_1,\dots ,v_n)$. Entonces

Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ vale para todo $k$, y como todo término de ${\tau }_{\cap }$ está en algún $T_k^{{\tau }_{\cap }}$, vale (a). ∎

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

Prueba de que ${\mathrm{Enu}}_0$ es verdadero. Sea $\phi \in F_0^{{\tau }_{\cap }}$ con $\phi {=}_d\phi (v_1,\dots ,v_n)$, y sean $a_1,\dots ,a_n\in A$. $\phi$ es atómica, así que por el Lema 4 en ${\tau }_{\cap }$ se da (1) o (2).

Caso $\phi =(t\equiv s)$, con $t,s\in T^{{\tau }_{\cap }}$. Por la Convención 6, $t{=}_{d}t(v_1,\dots ,v_n)$ y $s{=}_{d}s(v_1,\dots ,v_n)$. $𝐀\models \phi [a_1,\dots ,a_n]$ sii $t^{𝐀}[a_1,\dots ,a_n]=s^{𝐀}[a_1,\dots ,a_n]$ (Lema 6 (1) en $𝐀$) sii $t^{{𝐀}^{\prime }}[a_1,\dots ,a_n]=s^{{𝐀}^{\prime }}[a_1,\dots ,a_n]$ (por (a), en $t$ y en $s$) sii ${𝐀}^{\prime }\models \phi [a_1,\dots ,a_n]$ (Lema 6 (1) en ${𝐀}^{\prime }$).

Caso $\phi =r(t_1,\dots ,t_m)$. El único nombre de relación de ${\tau }_{\cap }$ es $\mathrm{Her}$, de aridad 3, así que $\phi =\mathrm{Her}(t_1,t_2,t_3)$ con $t_i\in T^{{\tau }_{\cap }}$, y por la Convención 6, $t_i{=}_d{t}_i(v_1,\dots ,v_n)$. $𝐀\models \phi [a_1,\dots ,a_n]$ sii $(t_1^{𝐀}[a_1,\dots ,a_n],t_2^{𝐀}[a_1,\dots ,a_n],t_3^{𝐀}[a_1,\dots ,a_n])\in {\mathrm{Her}}^{𝐀}$ (Lema 6 (2) en $𝐀$) sii $(t_1^{{𝐀}^{\prime }}[a_1,\dots ,a_n],t_2^{{𝐀}^{\prime }}[a_1,\dots ,a_n],t_3^{{𝐀}^{\prime }}[a_1,\dots ,a_n])\in {\mathrm{Her}}^{{𝐀}^{\prime }}$ (por (a) en cada $t_i$, y ${\mathrm{Her}}^{𝐀}={\mathrm{Her}}^{{𝐀}^{\prime }}$) sii ${𝐀}^{\prime }\models \phi [a_1,\dots ,a_n]$ (Lema 6 (2) en ${𝐀}^{\prime }$).

Prueba de que ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$. Supongamos que vale ${\mathrm{Enu}}_k$. Sean $\phi \in F_{k+1}^{{\tau }_{\cap }}$ con $\phi {=}_d\phi (v_1,\dots ,v_n)$ y $a_1,\dots ,a_n\in A$. Caso $\phi \in F_k^{{\tau }_{\cap }}$: vale por ${\mathrm{Enu}}_k$. Caso $\phi \in F_{k+1}^{{\tau }_{\cap }}-F_k^{{\tau }_{\cap }}$: $\phi$ no es atómica, así que por el Lema 4 en ${\tau }_{\cap }$ se da (3), (4), (5) o (6), con las piezas en $F_k^{{\tau }_{\cap }}$. Escribimos $[\overrightarrow{a}]$ por $[a_1,\dots ,a_n]$.

Caso (3), $\phi =({\phi }_1\eta {\phi }_2)$. Por la Convención 6, ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n)$ y ${\phi }_2{=}_d{\phi }_2(v_1,\dots ,v_n)$, y por ${\mathrm{Enu}}_k$, $𝐀\models {\phi }_i[\overrightarrow{a}]$ sii ${𝐀}^{\prime }\models {\phi }_i[\overrightarrow{a}]$ para $i=1,2$ (y, negando, $𝐀⊭{\phi }_i[\overrightarrow{a}]$ sii ${𝐀}^{\prime }⊭{\phi }_i[\overrightarrow{a}]$). Llamemos (H) a eso.

• $\eta =\wedge$: $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models {\phi }_1[\overrightarrow{a}]$ y $𝐀\models {\phi }_2[\overrightarrow{a}]$ (Lema 6 (3)) sii ${𝐀}^{\prime }\models {\phi }_1[\overrightarrow{a}]$ y ${𝐀}^{\prime }\models {\phi }_2[\overrightarrow{a}]$ (H) sii ${𝐀}^{\prime }\models \phi [\overrightarrow{a}]$ (Lema 6 (3)).
• $\eta =\vee$: igual, con «o» y el Lema 6 (4).
• $\eta =\to$: $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀\models {\phi }_2[\overrightarrow{a}]$ o $𝐀⊭{\phi }_1[\overrightarrow{a}]$ (Lema 6 (5)) sii ${𝐀}^{\prime }\models {\phi }_2[\overrightarrow{a}]$ o ${𝐀}^{\prime }⊭{\phi }_1[\overrightarrow{a}]$ (H) sii ${𝐀}^{\prime }\models \phi [\overrightarrow{a}]$ (Lema 6 (5)).
• $\eta =\leftrightarrow$: $𝐀\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}]$) (Lema 6 (6)) sii lo mismo con ${𝐀}^{\prime }$ (H) sii ${𝐀}^{\prime }\models \phi [\overrightarrow{a}]$ (Lema 6 (6)).

Caso (4), $\phi =\neg {\phi }_1$. Con ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n)$: $𝐀\models \phi [\overrightarrow{a}]$ sii $𝐀⊭{\phi }_1[\overrightarrow{a}]$ (Lema 6 (7)) sii ${𝐀}^{\prime }⊭{\phi }_1[\overrightarrow{a}]$ (${\mathrm{Enu}}_k$) sii ${𝐀}^{\prime }\models \phi [\overrightarrow{a}]$ (Lema 6 (7)).

Caso (5), $\phi =\forall v_j{\phi }_1$. Por la Convención 6, ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n)$.

Caso (5), $\phi =\exists v_j{\phi }_1$. La misma cadena con «para algún $a$» y el Lema 6 (10): $𝐀\models \phi [a_1,\dots ,a_n]$ sii hay $a\in A$ con $𝐀\models {\phi }_1[a_1,\dots ,a_{j-1},a,a_{j+1},\dots ,a_n]$ sii hay $a\in A$ con ${𝐀}^{\prime }\models {\phi }_1[a_1,\dots ,a_{j-1},a,a_{j+1},\dots ,a_n]$ (${\mathrm{Enu}}_k$) sii hay $a\in A^{\prime }$ con eso ($A=A^{\prime }$) sii ${𝐀}^{\prime }\models \phi [a_1,\dots ,a_n]$.

Caso (6), $\phi =\forall v{\phi }_1$, con $v\notin \{v_1,\dots ,v_n\}$. Por la Convención 6, ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n,v)$, y ${\mathrm{Enu}}_k$ se aplica con $n+1$ variables. $𝐀\models \phi [a_1,\dots ,a_n]$ sii $𝐀\models {\phi }_1[a_1,\dots ,a_n,a]$ para todo $a\in A$ (Lema 6 (9)) sii ${𝐀}^{\prime }\models {\phi }_1[a_1,\dots ,a_n,a]$ para todo $a\in A$ (${\mathrm{Enu}}_k$) sii lo mismo para todo $a\in A^{\prime }$ ($A=A^{\prime }$) sii ${𝐀}^{\prime }\models \phi [a_1,\dots ,a_n]$ (Lema 6 (9)).

Caso (6), $\phi =\exists v{\phi }_1$, con $v\notin \{v_1,\dots ,v_n\}$. Con ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n,v)$: $𝐀\models \phi [a_1,\dots ,a_n]$ sii hay $a\in A$ con $𝐀\models {\phi }_1[a_1,\dots ,a_n,a]$ (Lema 6 (11)) sii hay $a\in A$ con ${𝐀}^{\prime }\models {\phi }_1[a_1,\dots ,a_n,a]$ (${\mathrm{Enu}}_k$) sii hay $a\in A^{\prime }$ con eso ($A=A^{\prime }$) sii ${𝐀}^{\prime }\models \phi [a_1,\dots ,a_n]$ (Lema 6 (11)).

Con esto vale ${\mathrm{Enu}}_{k+1}$. Por la Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ vale para todo $k$, y como toda fórmula de ${\tau }_{\cap }$ está en algún $F_k^{{\tau }_{\cap }}$, vale (b). ∎

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

Lo que hace perder puntos. Aplicar el Lema 3 o el Lema 6 en $𝐀$ a un término o fórmula de ${\tau }_{\cap }$ sin decir que es de $\tau$. Tratar las atómicas como si ${\tau }_{\cap }$ tuviera otras relaciones u otras funciones: el Lema 1 y el Lema 4 se aplican en ${\tau }_{\cap }$, y eso deja sólo $\mathrm{un}$, $\mathrm{do}$, $+$ y $\mathrm{Her}$. Pasar de «para todo $a\in A$» a «para todo $a\in A^{\prime }$» sin nombrar $A=A^{\prime }$. Olvidar el caso (6) o tratarlo como el (5). Y en (b), probar las atómicas de nuevo en lugar de citar (a).

Lo que se lleva. El inciso (a) es el Ejercicio 28 con la identidad en lugar de $F$, y el (b) es el Ejercicio 29 con la identidad: allá el cuantificador usaba que $F$ es sobre; acá, que los universos son el mismo. El Ejercicio 26 es el mismo fenómeno al revés: una estructura y dos fórmulas que sólo difieren en nombres que se interpretan igual.

Para tener a mano

1. Primero: $T^{{\tau }_{\cap }}\subseteq T^{\tau }\cap T^{{\tau }^{\prime }}$ y $F^{{\tau }_{\cap }}\subseteq F^{\tau }\cap F^{{\tau }^{\prime }}$, por inducción en el nivel.
2. (a): Regla de Inducción desde 0 en $t\in T_k^{{\tau }_{\cap }}$; Lema 1 en ${\tau }_{\cap }$ (casos $\mathrm{un}$, $\mathrm{do}$, $v_j$, $+(t_1,t_2)$), Convención 5, Lema 3 en $𝐀$ y en ${𝐀}^{\prime }$.
3. (b): Regla de Inducción desde 0 en $\phi \in F_k^{{\tau }_{\cap }}$; atómicas $(t\equiv s)$ y $\mathrm{Her}(t_1,t_2,t_3)$ con (a); conectivos con el Lema 6 (3)–(7).
4. Cuantificadores: cuatro casos, Lema 6 (8)–(11); el paso que se nombra es $A=A^{\prime }$. En $v\notin \{v_1,\dots ,v_n\}$, ${\phi }_1{=}_d{\phi }_1(v_1,\dots ,v_n,v)$.
5. En el ${\mathrm{Enu}}_k$, adentro: $n$, $v_1,\dots ,v_n$, $t$ o $\phi$, y $a_1,\dots ,a_n$.