La notación declaratoria

Con asignaciones infinitas, decir « $φ$ es verdadera cuando $x_{2}$ vale 1 y $x_{16}$ vale 2» obliga a escribir una infinitupla con un 1 en el lugar 2, un 2 en el lugar 16 y cualquier cosa en el resto. La notación declaratoria hace eso de una vez: se declara una lista finita de variables, $φ =_{d} φ (x_{2}, x_{16})$ , y desde ahí $𝐀 ⊨ φ [1, 2]$ dice exactamente eso, y $φ (P_{1}, P_{2})$ es la palabra que se obtiene poniendo $P_{1}$ y $P_{2}$ en lugar de las variables. Todo depende de una cosa que es fácil perder de vista: el orden de la lista. Los Ejercicios 21 a 30 de la lista se enuncian y se resuelven adentro de esta notación, con los lemas y convenciones de la sección «Manejo técnico» de la Guía 11.

01 · Declarar las variables de un término

Supongamos $v_{1}, \dots, v_{n} \in Var$ y $t$ un término de tipo $τ$ . Se escribe

t =_{d} t (v_{1}, \dots, v_{n})

para declarar que $v_{1}, \dots, v_{n}$ son variables distintas y que toda variable que ocurre en $t$ pertenece a ${v_{1}, \dots, v_{n}}$ . No hace falta que toda $v_{j}$ ocurra en $t$ : se puede declarar de más. El caso $n = 0$ también vale: $t =_{d} t ()$ declara que $t$ es un término cerrado, sin variables (Guía 11, p. 1).

Una declaración no cambia el término: $t$ sigue siendo la misma palabra. Lo que agrega es una lista ordenada de variables, y las convenciones que siguen leen todo por esa lista.

02 · Convención 1: poner palabras en lugar de las variables

Convención Notacional 1. Cuando se hizo la declaración $t =_{d} t (v_{1}, \dots, v_{n})$ , si $P_{1}, \dots, P_{n}$ son palabras cualesquiera (no necesariamente términos), $t (P_{1}, \dots, P_{n})$ denota la palabra que resulta de reemplazar simultáneamente cada ocurrencia de $v_{1}$ en $t$ por $P_{1}$ , cada ocurrencia de $v_{2}$ por $P_{2}$ , etc.

El ejemplo de la guía. Sea $τ = ({cero}, {FU}, \emptyset, {(FU, 2)})$ y $t = FU (FU (x_{2}, x_{16}), x_{3})$ . Con tres palabras fijas, el resultado depende de cómo se declaró:

Si $t =_{d} t (x_{3}, x_{2}, x_{16})$ , entonces $t (##, ▲#▲, @@) = FU (FU (▲#▲, @@), ##)$ .
Si $t =_{d} t (x_{16}, x_{3}, x_{2})$ , entonces $t (##, ▲#▲, @@) = FU (FU (@@, ##), ▲#▲)$ .
Si $t =_{d} t (x_{3}, x_{200}, x_{2}, x_{16}, x_{100})$ , entonces $t (##,!!!!, ▲#▲, @@,!!) = FU (FU (▲#▲, @@), ##)$ : las palabras de los lugares 2 y 5 no aparecen, porque $x_{200}$ y $x_{100}$ no ocurren en $t$ .

La palabra $P_{j}$ va al lugar de la $j$ -ésima variable de la lista, no al de $x_{j}$ . Por eso el orden es clave: la misma $t$ con las mismas palabras da dos resultados distintos según la declaración.

Y simultáneo quiere decir de una sola vez, no una variable después de la otra. Con $t = FU (x_{1}, x_{2})$ y $t =_{d} t (x_{1}, x_{2})$ , $t (x_{2}, x_{1}) = FU (x_{2}, x_{1})$ : se intercambian. Si se reemplazara primero $x_{1}$ por $x_{2}$ y después $x_{2}$ por $x_{1}$ , saldría $FU (x_{2}, x_{2})$ y después $FU (x_{1}, x_{1})$ .

Si las $P_{j}$ son términos $t_{1}, \dots, t_{n}$ , $t (t_{1}, \dots, t_{n})$ es un término. La guía lo justifica aplicando $n$ veces el ítem (c) del lema de ocurrencias de términos en términos de la Guía 9, con el cuidado de que las $n$ aplicaciones sucesivas imiten al reemplazo simultáneo; con los lemas de la sección 06 sale por inducción (Ejercicio 22 de la guía, y el Teorema 8 (a)).

03 · Convención 2: el valor con una tupla finita

Convención Notacional 2. Cuando se declaró $t =_{d} t (v_{1}, \dots, v_{n})$ , si $𝐀$ es un modelo de tipo $τ$ y $a_{1}, \dots, a_{n} \in A$ , $t^{𝐀} [a_{1}, \dots, a_{n}]$ denota el elemento $t^{𝐀} [\vec{b}]$ , donde $\vec{b}$ es una asignación que a cada $v_{i}$ le asigna el valor $a_{i}$ . Para $n = 0$ , $t^{𝐀} []$ es $t^{𝐀} [\vec{b}]$ con $\vec{b}$ cualquiera.

Con el $t$ de recién y $𝐀$ dado por $A = {1, 2, 3}$ , ${cero}^{𝐀} = 1$ y ${FU}^{𝐀} (i, j) = j$ :

con $t =_{d} t (x_{3}, x_{2}, x_{16})$ , $t^{𝐀} [2, 1, 3] = {FU}^{𝐀} ({FU}^{𝐀} (1, 3), 2) = 2$ ;
con $t =_{d} t (x_{16}, x_{3}, x_{2})$ , $t^{𝐀} [2, 1, 3] = {FU}^{𝐀} ({FU}^{𝐀} (3, 2), 1) = 1$ ;
con $t =_{d} t (x_{3}, x_{200}, x_{2}, x_{16}, x_{100})$ , $t^{𝐀} [2, 3, 1, 3, 2] = 2$ : los valores de los lugares 2 y 5 no se usan;
y si $t = FU (FU (cero, cero), cero)$ , se puede declarar $t =_{d} t ()$ , y $t^{𝐀} [] = {FU}^{𝐀} ({FU}^{𝐀} (1, 1), 1) = 1$ .

Por qué no hay ambigüedad (Ejercicio 1 de la guía). Hay infinitas $\vec{b}$ que le asignan $a_{i}$ a cada $v_{i}$ : coinciden en los lugares de $v_{1}, \dots, v_{n}$ y en el resto valen cualquier cosa. Pero dos de ellas coinciden en todas las variables que ocurren en $t$ , porque esas están entre las $v_{i}$ , y por el Lema 1 de la Guía 10 dan el mismo valor. Y que alguna exista es porque las $v_{i}$ son distintas: si se pudiera declarar $t =_{d} t (x_{1}, x_{1})$ , $t^{𝐀} [1, 2]$ pediría una asignación con $b_{1} = 1$ y $b_{1} = 2$ .

04 · Declarar las variables de una fórmula: Convenciones 3 y 4

Para fórmulas lo que cuenta son las variables libres. Supongamos $v_{1}, \dots, v_{n} \in Var$ y $φ$ una fórmula de tipo $τ$ . Se escribe $φ =_{d} φ (v_{1}, \dots, v_{n})$ para declarar que $v_{1}, \dots, v_{n}$ son variables distintas y que $Li (φ) \subseteq {v_{1}, \dots, v_{n}}$ . Con $n = 0$ , $φ =_{d} φ ()$ declara que $φ$ es una sentencia. Una variable que ocurre sólo acotada no hace falta declararla.

Convención Notacional 3. Cuando se hizo la declaración $φ =_{d} φ (v_{1}, \dots, v_{n})$ , si $P_{1}, \dots, P_{n}$ son palabras cualesquiera, $φ (P_{1}, \dots, P_{n})$ denota la palabra que resulta de reemplazar simultáneamente cada ocurrencia libre de $v_{1}$ en $φ$ por $P_{1}$ , cada ocurrencia libre de $v_{2}$ por $P_{2}$ , etc.

Convención Notacional 4. Cuando se declaró $φ =_{d} φ (v_{1}, \dots, v_{n})$ , si $𝐀$ es un modelo de tipo $τ$ y $a_{1}, \dots, a_{n} \in A$ , $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ significa que $𝐀 ⊨ φ [\vec{b}]$ , donde $\vec{b}$ es una asignación que a cada $v_{i}$ le asigna $a_{i}$ ; $𝐀 ⊭ φ [a_{1}, \dots, a_{n}]$ significa que no sucede $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ .

Los Ejercicios 3 y 6 de la guía. Sea $τ = (\emptyset, {F}, {E}, {(F, 1), (E, 2)})$ y

φ = (\forall x_{16} E (x_{2}, x_{16}) \land (F (x_{16}) \equiv F (x_{17})))

con $Li (φ) = {x_{2}, x_{16}, x_{17}}$ : la $x_{16}$ de $F (x_{16})$ es libre, las dos de la izquierda no.

Con $φ =_{d} φ (x_{2}, x_{16}, x_{17}, x_{18})$ : $φ ($$, &$&, @@, %) = (\forall x_{16} E ($$, x_{16}) \land (F (&$&) \equiv F (@@)))$ .
Con $φ =_{d} φ (x_{18}, x_{16}, x_{17}, x_{2})$ : $φ ($$, &$&, @@, %) = (\forall x_{16} E (%, x_{16}) \land (F (&$&) \equiv F (@@)))$ .

En los dos, la $x_{16}$ que acompaña al $\forall$ y la de $E (\dots, x_{16})$ quedan: no son ocurrencias libres. Con $𝐀$ de universo ${1, 2, 3, 4, 5}$ , $F^{𝐀} (x) = \max {x, 3}$ y $E^{𝐀} = {1} \times A$ : con la primera declaración, $𝐀 ⊨ φ [1, 2, 2, 4]$ , porque $x_{2}$ vale 1 y ${1} \times A$ relaciona al 1 con todos, y $F^{𝐀} (2) = F^{𝐀} (2)$ ; con la segunda, $𝐀 ⊭ φ [1, 2, 2, 4]$ , porque ahora $x_{2}$ vale 4 y $(4, 1) \notin E^{𝐀}$ . La misma tupla, la misma fórmula, distinto valor de verdad.

La Convención 4 tampoco es ambigua (Ejercicio 5 de la guía), por la misma razón que la 2, con el Lema 2 de la Guía 10 en lugar del Lema 1: el valor de verdad sólo depende de lo que la asignación les da a las variables libres, y esas están declaradas.

05 · La trampa: una variable que queda acotada

En la Convención 3 nada impide que $P_{j}$ tenga variables, y una variable de $P_{j}$ puede caer adentro de un cuantificador de $φ$ . En el reticulado de la página 5 de la guía, de 16 elementos con $s^{𝐀}$ e $i^{𝐀}$ el supremo y el ínfimo del diagrama,

φ_{15} = \forall x_{200} (s (x_{1}, x_{200}) \equiv x_{1})

define al 15: $s (a, b) = a$ para todo $b$ sólo si $a$ es el máximo. Declarando $φ_{15} =_{d} φ_{15} (x_{1})$ , $φ_{15} (x_{7}) = \forall x_{200} (s (x_{7}, x_{200}) \equiv x_{7})$ también lo define (con $x_{7}$ en el papel de $x_{1}$ ). Pero

φ_{15} (x_{200}) = \forall x_{200} (s (x_{200}, x_{200}) \equiv x_{200})

ya no habla de nadie: las $x_{200}$ puestas quedaron en el alcance de $\forall x_{200}$ , la fórmula es una sentencia, y es verdadera en $𝐀$ porque $s$ es idempotente. Se reemplazó $x_{1}$ por una variable que $φ_{15}$ usa en forma auxiliar y acotada.

Lo mismo rompe el «obvio» $Li (ψ (x_{2}, x_{3}, x_{1})) = {x_{1}, x_{2}, x_{3}}$ del Ejercicio 4 de la guía: con $ψ = (\forall x_{2} (x_{1} \equiv x_{2}) \land (x_{2} \equiv x_{3})) =_{d} ψ (x_{1}, x_{2}, x_{3})$ , que tiene $Li (ψ) = {x_{1}, x_{2}, x_{3}}$ , queda $ψ (x_{2}, x_{3}, x_{1}) = (\forall x_{2} (x_{2} \equiv x_{2}) \land (x_{3} \equiv x_{1}))$ , con $Li = {x_{1}, x_{3}}$ . La sección 09 le pone nombre a la condición que evita esto.

En azul, lo que se puso; en gris, las ocurrencias acotadas de las variables declaradas, que la Convención 3 no toca. Con $x_{200}$ en $φ_{15}$ , lo puesto queda en rojo: la palabra sigue siendo una fórmula, pero las variables nuevas no están libres.

06 · Términos declarados: Lemas 1, 2 y 3

Una declaración da un poco más de información que un término a secas: si $t =_{d} t (v_{1}, \dots, v_{n})$ y $t \in Var$ , entonces $t \in {v_{1}, \dots, v_{n}}$ . La sección «Manejo técnico de la notación declaratoria» de la Guía 11 (p. 8) convierte eso en una lectura única con la lista adentro.

Lema 1 (lectura única de términos declarados). Sea $τ$ un tipo y $t \in T^{τ}$ . Si $t =_{d} t (v_{1}, \dots, v_{n})$ , se da una y sólo una de las siguientes:

Más aún, si $t \in T_{k + 1}^{τ}$ , cuando se da (3) los términos $t_{1}, \dots, t_{m}$ están en $T_{k}^{τ}$ .

Es la lectura única de términos más la declaración: si $t$ es una variable, ocurre en $t$ , así que es alguna $v_{j}$ , y una sola porque son distintas. Cuando $n = 0$ la opción (2) no puede darse.

Convención Notacional 5. Cuando se declaró $t =_{d} t (v_{1}, \dots, v_{n})$ y se da el caso (3) del Lema 1, se supone tácitamente que también se hicieron las declaraciones $t_{1} =_{d} t_{1} (v_{1}, \dots, v_{n}), \dots, t_{m} =_{d} t_{m} (v_{1}, \dots, v_{n})$ .

Se puede porque toda variable que ocurre en un $t_{i}$ ocurre en $t$ , y entonces está en la lista. La declaración baja a los argumentos con la misma lista y en el mismo orden.

Lema 2 (conmutatividad de reemplazo y armado para términos). Supongamos $t =_{d} t (v_{1}, \dots, v_{n})$ y sean $P_{1}, \dots, P_{n}$ palabras cualesquiera. Cuando se da el caso (3) del Lema 1,

t (P_{1}, \dots, P_{n}) = f (t_{1} (P_{1}, \dots, P_{n}), \dots, t_{m} (P_{1}, \dots, P_{n}))

Armar $f (t_{1}, \dots, t_{m})$ y después reemplazar da lo mismo que reemplazar en cada pieza y después armar: es la conmutatividad del nombre. La guía lo acepta sin prueba —pediría una definición precisa del reemplazo simultáneo—, y la razón intuitiva es que $f$ , los paréntesis y las comas no tienen variables, así que toda ocurrencia de una $v_{j}$ en $t$ está adentro de algún $t_{i}$ .

Lema 3 (carácter recursivo de $t^{𝐀} [a_{1}, \dots, a_{n}]$ ). Sea $t \in T^{τ}$ con $t =_{d} t (v_{1}, \dots, v_{n})$ , $𝐀$ un modelo de tipo $τ$ y $a_{1}, \dots, a_{n} \in A$ .

Prueba. (1) y (2) son las cláusulas (1) y (2) de $t^{𝐀} [\vec{b}]$ . Para (3), sea $\vec{b}$ una asignación que a cada $v_{i}$ le asigna $a_{i}$ . Por la Convención 2, por la cláusula (3) de $t^{𝐀} [\vec{b}]$ , y por la Convención 2 aplicada a cada $t_{i}$ (que está declarado con la misma lista por la Convención 5):

t^{𝐀} [a_{1}, \dots, a_{n}] = t^{𝐀} [\vec{b}] = f^{𝐀} (t_{1}^{𝐀} [\vec{b}], \dots, t_{m}^{𝐀} [\vec{b}]) = f^{𝐀} (t_{1}^{𝐀} [a_{1}, \dots, a_{n}], \dots, t_{m}^{𝐀} [a_{1}, \dots, a_{n}])

∎ Con el Lema 3, la notación con tuplas finitas se calcula igual que la de asignaciones, sin volver a mencionar ninguna $\vec{b}$ .

07 · Fórmulas declaradas: Lemas 4, 5 y 6

Lema 4 (lectura única de fórmulas declaradas, p. 9). Sea $φ \in F^{τ}$ con $φ =_{d} φ (v_{1}, \dots, v_{n})$ . Se da una y sólo una de las siguientes:

Más aún, si $φ \in F_{k + 1}^{τ}$ , en (3) las fórmulas $φ_{1}$ y $φ_{2}$ están en $F_{k}^{τ}$ , y en (4), (5) o (6) la fórmula $φ_{1}$ está en $F_{k}^{τ}$ .

La novedad es que el cuantificador se parte en dos casos: el que cuantifica una variable de la lista y el que cuantifica una que no está. Con $n = 0$ el caso (5) no puede darse.

Observación (Ejercicio 23 de la guía). En el caso (1), las variables que ocurren en $t$ y en $s$ están en ${v_{1}, \dots, v_{n}}$ ; en el (2), las de $t_{1}, \dots, t_{m}$ ; en el (3), $Li (φ_{1}) \cup Li (φ_{2}) \subseteq {v_{1}, \dots, v_{n}}$ ; en el (4) y el (5), $Li (φ_{1}) \subseteq {v_{1}, \dots, v_{n}}$ ; y en el (6), $Li (φ_{1}) \subseteq {v_{1}, \dots, v_{n}, v}$ . Todo sale del Lema 10 de la Guía 9: en una atómica, las libres son todas las que ocurren; $Li ((φ_{1} η φ_{2})) = Li (φ_{1}) \cup Li (φ_{2})$ ; $Li (\neg φ_{1}) = Li (φ_{1})$ ; y $Li (Q w φ_{1}) = Li (φ_{1}) - {w}$ , así que $Li (φ_{1}) \subseteq Li (φ) \cup {w}$ . En el (5), $w = v_{j}$ ya está en la lista; en el (6), $w = v$ no está, y hay que agregarla.

Convención Notacional 6. Cuando se declaró $φ =_{d} φ (v_{1}, \dots, v_{n})$ , se supone tácitamente que también se hicieron estas declaraciones: en el caso (1) del Lema 4, $t =_{d} t (v_{1}, \dots, v_{n})$ y $s =_{d} s (v_{1}, \dots, v_{n})$ ; en el (2), $t_{i} =_{d} t_{i} (v_{1}, \dots, v_{n})$ para cada $i$ ; en el (3), $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n})$ y $φ_{2} =_{d} φ_{2} (v_{1}, \dots, v_{n})$ ; en el (4) o el (5), $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n})$ ; y en el (6), $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n}, v)$ .

Lema 5 (conmutatividad de reemplazo y armado para fórmulas, p. 10). Supongamos $φ =_{d} φ (v_{1}, \dots, v_{n})$ y sean $P_{1}, \dots, P_{n}$ palabras cualesquiera. Según el caso del Lema 4:

En (5) y (6), en el lugar de la variable cuantificada va ella misma: adentro de $Q v_{j} φ_{1}$ las ocurrencias de $v_{j}$ son acotadas, y la Convención 3 no las toca. Con $φ = \forall x_{1} r (x_{1}) =_{d} φ (x_{1})$ , $φ (x_{9}) = \forall x_{1} r (x_{1})$ , mientras que $\forall x_{1} φ_{1} (x_{9})$ sería $\forall x_{1} r (x_{9})$ . La guía también acepta este lema sin prueba.

Lema 6 (carácter recursivo de $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ , p. 11). Supongamos $φ =_{d} φ (v_{1}, \dots, v_{n})$ , $𝐀 = (A, i)$ un modelo de tipo $τ$ y $a_{1}, \dots, a_{n} \in A$ . Escribimos $[\vec{a}]$ por $[a_{1}, \dots, a_{n}]$ .

(1) Si $φ = (t \equiv s)$ : $𝐀 ⊨ φ [\vec{a}]$ sii $t^{𝐀} [\vec{a}] = s^{𝐀} [\vec{a}]$ .
(2) Si $φ = r (t_{1}, \dots, t_{m})$ : $𝐀 ⊨ φ [\vec{a}]$ sii $(t_{1}^{𝐀} [\vec{a}], \dots, t_{m}^{𝐀} [\vec{a}]) \in r^{𝐀}$ .
(3) Si $φ = (φ_{1} \land φ_{2})$ : sii $𝐀 ⊨ φ_{1} [\vec{a}]$ y $𝐀 ⊨ φ_{2} [\vec{a}]$ .
(4) Si $φ = (φ_{1} \lor φ_{2})$ : sii $𝐀 ⊨ φ_{1} [\vec{a}]$ o $𝐀 ⊨ φ_{2} [\vec{a}]$ .
(5) Si $φ = (φ_{1} \to φ_{2})$ : sii $𝐀 ⊨ φ_{2} [\vec{a}]$ o $𝐀 ⊭ φ_{1} [\vec{a}]$ .
(6) Si $φ = (φ_{1} \leftrightarrow φ_{2})$ : sii se dan $𝐀 ⊨ φ_{1} [\vec{a}]$ y $𝐀 ⊨ φ_{2} [\vec{a}]$ , o $𝐀 ⊭ φ_{1} [\vec{a}]$ y $𝐀 ⊭ φ_{2} [\vec{a}]$ .
(7) Si $φ = \neg φ_{1}$ : sii $𝐀 ⊭ φ_{1} [\vec{a}]$ .
(8) Si $φ = \forall v_{j} φ_{1}$ : sii $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{j - 1}, a, a_{j + 1}, \dots, a_{n}]$ para todo $a \in A$ .
(9) Si $φ = \forall v φ_{1}$ , con $v \notin {v_{1}, \dots, v_{n}}$ : sii $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{n}, a]$ para todo $a \in A$ .
(10) Si $φ = \exists v_{j} φ_{1}$ : sii $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{j - 1}, a, a_{j + 1}, \dots, a_{n}]$ para algún $a \in A$ .
(11) Si $φ = \exists v φ_{1}$ , con $v \notin {v_{1}, \dots, v_{n}}$ : sii $𝐀 ⊨ φ_{1} [a_{1}, \dots, a_{n}, a]$ para algún $a \in A$ .

En cada cláusula, la fórmula de la derecha se lee con la declaración que le da la Convención 6: en (8) y (10), $φ_{1}$ con la misma lista, y el $a$ va en el lugar $j$ ; en (9) y (11), $φ_{1}$ con la lista alargada por $v$ , y el $a$ va al final. La guía lo acepta sin prueba. Su consecuencia más usada es el Corolario 7: si $ψ =_{d} ψ (v)$ , $𝐀 ⊨ \exists v ψ (v)$ sii existe $a \in A$ tal que $𝐀 ⊨ ψ [a]$ , y $𝐀 ⊨ \forall v ψ (v)$ sii para cada $a \in A$ , $𝐀 ⊨ ψ [a]$ (con $φ = \exists v ψ (v)$ , o $\forall v ψ (v)$ , declarada $φ =_{d} φ ()$ , se aplica el caso (11) o el (9) del lema).

08 · El molde de una inducción declaratoria

Una prueba de los Ejercicios 21 a 30 no menciona asignaciones infinitas: desarma el término o la fórmula con el Lema 1 o el Lema 4, baja la declaración con la Convención 5 o la 6, y calcula con el Lema 3 o el Lema 6. Con términos, el molde es el del Ejercicio 21:

Usaremos la Regla de Inducción desde 0. Para cada $k \in ω$ sea ${Enu}_{k}$ el enunciado: Sea $𝐀$ una estructura de tipo $τ$ tal que $(A, s^{𝐀}, i^{𝐀})$ es un reticulado terna. Si $t \in T_{k}^{τ}$ y $t =_{d} t (v_{1}, v_{2})$ , entonces $t^{𝐀} [a, b] \in {a, b, s^{𝐀} (a, b), i^{𝐀} (a, b)}$ para cada $a, b \in A$ .

Caso base: $t \in T_{0}^{τ}$ y $t =_{d} t (v_{1}, v_{2})$ . Por el Lema 1 de la Guía 11, $t = c$ o $t = v_{j}$ ; como $τ$ no tiene constantes, $t = v_{1}$ o $t = v_{2}$ , y por el Lema 3 (2), $t^{𝐀} [a, b] = a$ o $t^{𝐀} [a, b] = b$ .

Paso: supongamos que vale ${Enu}_{k}$ , y sea $t \in T_{k + 1}^{τ}$ con $t =_{d} t (v_{1}, v_{2})$ . Caso $t \in T_{k}^{τ}$ : vale por ${Enu}_{k}$ . Caso $t \in T_{k + 1}^{τ} - T_{k}^{τ}$ : no es $c$ ni $v_{j}$ , que están en $T_{0}^{τ} \subseteq T_{k}^{τ}$ ; por el Lema 1, $t = f (t_{1}, t_{2})$ con $f \in {s, i}$ y $t_{1}, t_{2} \in T_{k}^{τ}$ , y por la Convención 5, $t_{1} =_{d} t_{1} (v_{1}, v_{2})$ y $t_{2} =_{d} t_{2} (v_{1}, v_{2})$ . Por el Lema 3 (3), $t^{𝐀} [a, b] = f^{𝐀} (t_{1}^{𝐀} [a, b], t_{2}^{𝐀} [a, b])$ ; por ${Enu}_{k}$ aplicado a $t_{1}$ y a $t_{2}$ , los dos argumentos están en ${a, b, s^{𝐀} (a, b), i^{𝐀} (a, b)}$ , y lo que queda es ver que ese conjunto es cerrado por $s^{𝐀}$ e $i^{𝐀}$ .

Lo que tienen que decir todas: «Regla de Inducción desde 0»; ${Enu}_{k}$ con la estructura, la declaración y los elementos adentro; en el paso, primero el caso $t \in T_{k}^{τ}$ ; y el lema citado con su número y su guía. Con términos la lista no cambia al bajar, así que el ${Enu}_{k}$ puede fijarla.

Con fórmulas, la lista sí cambia. En el caso (6) del Lema 4, la Convención 6 declara $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n}, v)$ , con una variable más, y la hipótesis inductiva se tiene que poder aplicar con $n + 1$ variables. Por eso el ${Enu}_{k}$ de una fórmula cuantifica la cantidad de variables y la declaración. Los Ejercicios 29 y 30 comparan el valor de verdad de $φ$ en dos estructuras $𝐀$ y $𝐁$ a través de una función $F : A \to B$ ; el 26 y el 27 usan el mismo esqueleto con la identidad, comparando dos fórmulas en una estructura o una fórmula en dos estructuras de tipos distintos. El molde, con lo que cada caso le pide a $F$ , es:

EnunciarUsaremos la Regla de Inducción desde 0. Para cada $k \in ω$ sea ${Enu}_{k}$ : cualesquiera sean los modelos $𝐀$ , $𝐁$ de tipo $τ$ y la función $F : A \to B$ con la hipótesis del ejercicio, el número $n \geq 0$ , las variables distintas $v_{1}, \dots, v_{n}$ y la fórmula $φ \in F_{k}^{τ}$ con $φ =_{d} φ (v_{1}, \dots, v_{n})$ , se tiene $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ sii $𝐁 ⊨ φ [F (a_{1}), \dots, F (a_{n})]$ , para cada $a_{1}, \dots, a_{n} \in A$ .
Base $φ \in F_{0}^{τ}$ : por el Lema 4, caso (1) o (2). Por la Convención 6, $t =_{d} t (v_{1}, \dots, v_{n})$ , $s =_{d} s (v_{1}, \dots, v_{n})$ (o los $t_{i}$ ). Por el Lema 6 (1), $𝐀 ⊨ φ [\vec{a}]$ sii $t^{𝐀} [\vec{a}] = s^{𝐀} [\vec{a}]$ , y se pasa a $𝐁$ con el resultado de términos, $F (t^{𝐀} [\vec{a}]) = t^{𝐁} [F (a_{1}), \dots, F (a_{n})]$ (Ejercicio 28, por inducción en términos con los Lemas 1 y 3 y la Convención 5). La vuelta de $\equiv$ pide $F$ inyectiva; la del caso (2), Lema 6 (2), que $F$ refleje las relaciones.
Caso $F_{k}$ Si $φ \in F_{k}^{τ}$ , vale por ${Enu}_{k}$ .
NexosCaso (3): $φ = (φ_{1} η φ_{2})$ con $φ_{1}, φ_{2} \in F_{k}^{τ}$ y, por la Convención 6, $φ_{i} =_{d} φ_{i} (v_{1}, \dots, v_{n})$ . Lema 6 (3), (4), (5) o (6) según $η$ , ${Enu}_{k}$ aplicado a $φ_{1}$ y a $φ_{2}$ con los mismos $a_{i}$ , y el mismo caso del Lema 6 en $𝐁$ . Cada nexo es un caso propio, escrito.
NegaciónCaso (4): $φ = \neg φ_{1}$ , $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n})$ , Lema 6 (7). Necesita el «sii» entero de la hipótesis: con una sola dirección, $\neg$ la da vuelta (y $\to$ y $\leftrightarrow$ también, porque tienen una $φ_{1}$ negada adentro).
Q de la listaCaso (5): $φ = \forall v_{j} φ_{1}$ o $\exists v_{j} φ_{1}$ , $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n})$ . Lema 6 (8) o (10): $𝐀 ⊨ φ [\vec{a}]$ sii $𝐀 ⊨ φ_{1} [a_{1}, \dots, a, \dots, a_{n}]$ para todo (algún) $a \in A$ ; por ${Enu}_{k}$ , sii $𝐁 ⊨ φ_{1} [F (a_{1}), \dots, F (a), \dots, F (a_{n})]$ para todo (algún) $a \in A$ . Del lado de $𝐁$ el Lema 6 pide todo (algún) $b \in B$ : ir del $\forall$ de $A$ al de $B$ , o volver del $\exists$ de $B$ al de $A$ , pide $F$ sobre.
Q fueraCaso (6): $φ = \forall v φ_{1}$ o $\exists v φ_{1}$ con $v \notin {v_{1}, \dots, v_{n}}$ , y por la Convención 6 $φ_{1} =_{d} φ_{1} (v_{1}, \dots, v_{n}, v)$ . Lema 6 (9) u (11), con el $a$ al final, y ${Enu}_{k}$ aplicado a $φ_{1}$ con $n + 1$ variables y los elementos $a_{1}, \dots, a_{n}, a$ : es el caso que obliga a cuantificar $n$ adentro del ${Enu}_{k}$ . Lo que pide de $F$ , lo mismo que el (5).
ConcluirVale ${Enu}_{k}$ para todo $k$ , y como toda fórmula está en algún $F_{k}^{τ}$ , el enunciado vale para toda $φ$ y toda declaración.

Los once casos del Lema 6 aparecen todos: (1) y (2) en la base, (3) a (6) en los nexos, (7) en la negación, (8) y (10) con una variable de la lista, (9) y (11) con una que no está. Leído al revés, el molde dice qué hace falta en cada ejercicio. Un isomorfismo cumple todo y da el «sii» (Ejercicio 29). Un homomorfismo sobre sólo da la ida: las atómicas pasan de $𝐀$ a $𝐁$ , $\land$ , $\lor$ y $\exists$ llevan la ida, $\forall$ la lleva usando que es sobre, y $\neg$ , $\to$ y $\leftrightarrow$ quedan afuera (Ejercicio 30). En el Ejercicio 26 y el 27, $F$ es la identidad y lo que cambia es la fórmula o el tipo.

09 · Los teoremas de reemplazo

Los dos dicen que el reemplazo sintáctico conmuta con la evaluación: poner términos en lugar de variables y después evaluar da lo mismo que evaluar los términos y usar sus valores. La guía los acepta sin prueba.

Teorema 8 (reemplazo para términos, p. 13). Supongamos $t =_{d} t (w_{1}, \dots, w_{k})$ , $s_{1} =_{d} s_{1} (v_{1}, \dots, v_{n}), \dots, s_{k} =_{d} s_{k} (v_{1}, \dots, v_{n})$ . Entonces (a) $t (s_{1}, \dots, s_{k}) \in T^{τ}$ ; (b) todas las variables de $t (s_{1}, \dots, s_{k})$ están en ${v_{1}, \dots, v_{n}}$ ; (c) si se declara $t (s_{1}, \dots, s_{k}) =_{d} t (s_{1}, \dots, s_{k}) (v_{1}, \dots, v_{n})$ , para cada $𝐀$ y $a_{1}, \dots, a_{n} \in A$ ,

t (s_{1}, \dots, s_{k})^{𝐀} [a_{1}, \dots, a_{n}] = t^{𝐀} [s_{1}^{𝐀} [a_{1}, \dots, a_{n}], \dots, s_{k}^{𝐀} [a_{1}, \dots, a_{n}]]

Con fórmulas no vale sin una condición, y el ejemplo de la página 13 muestra por qué. Sea $φ = \exists x_{1} (f (x_{1}) \equiv x_{2})$ , declarada $φ =_{d} φ (x_{2})$ : $𝐀 ⊨ φ [a]$ sii $a$ está en la imagen de $f^{𝐀}$ . Pero $φ (x_{1}) = \exists x_{1} (f (x_{1}) \equiv x_{1})$ no dice « $x_{1}$ está en la imagen»: es una sentencia, verdadera sii $f^{𝐀}$ tiene un punto fijo. En $A = {0, 1}$ con $f^{𝐀}$ constante 0, $𝐀 ⊨ φ [1]$ es falso (el 1 no está en la imagen) y $φ (x_{1})$ es verdadera (el 0 es fijo). La ocurrencia libre de $x_{2}$ que se reemplazó estaba en el alcance de $\exists x_{1}$ , y la $x_{1}$ puesta quedó ligada.

Se dice que $v$ es sustituible por $w$ en $φ$ cuando ninguna ocurrencia libre de $v$ en $φ$ sucede dentro de una ocurrencia de una subfórmula de la forma $Q w ψ$ . Dado un término $t$ , $v$ es sustituible por $t$ en $φ$ cuando $v$ es sustituible en $φ$ por cada variable que ocurre en $t$ . Recursivamente (p. 14): si $φ$ es atómica, $v$ es sustituible por $w$ ; en $(φ_{1} η φ_{2})$ , sii lo es en $φ_{1}$ y en $φ_{2}$ ; en $\neg φ_{1}$ , sii lo es en $φ_{1}$ ; en $Q v φ_{1}$ , siempre ( $v$ no tiene ocurrencias libres); en $Q w φ_{1}$ , sii $v \notin Li (φ_{1})$ ; en $Q u φ_{1}$ con $u \neq v, w$ , sii lo es en $φ_{1}$ . En el ejemplo, $x_{2}$ no es sustituible por $x_{1}$ en $\exists x_{1} (f (x_{1}) \equiv x_{2})$ , porque $x_{2} \in Li ((f (x_{1}) \equiv x_{2}))$ ; y en $φ_{15}$ , $x_{1}$ no es sustituible por $x_{200}$ .

Teorema 9 (reemplazo para fórmulas, p. 14). Supongamos $φ =_{d} φ (w_{1}, \dots, w_{k})$ , $t_{1} =_{d} t_{1} (v_{1}, \dots, v_{n}), \dots, t_{k} =_{d} t_{k} (v_{1}, \dots, v_{n})$ , y que cada $w_{j}$ es sustituible por $t_{j}$ en $φ$ . Entonces (a) $φ (t_{1}, \dots, t_{k}) \in F^{τ}$ ; (b) $Li (φ (t_{1}, \dots, t_{k})) \subseteq {v_{1}, \dots, v_{n}}$ ; (c) si se declara $φ (t_{1}, \dots, t_{k}) =_{d} φ (t_{1}, \dots, t_{k}) (v_{1}, \dots, v_{n})$ , para cada $𝐀$ y $a_{1}, \dots, a_{n} \in A$ ,

𝐀 ⊨ φ (t_{1}, \dots, t_{k}) [a_{1}, \dots, a_{n}] sii 𝐀 ⊨ φ [t_{1}^{𝐀} [a_{1}, \dots, a_{n}], \dots, t_{k}^{𝐀} [a_{1}, \dots, a_{n}]]

Sin la hipótesis, el ejemplo de arriba es el contraejemplo (Ejercicio 39 de la guía): $k = n = 1$ , $w_{1} = x_{2}$ , $t_{1} = x_{1}$ , $v_{1} = x_{1}$ . La conclusión (c) diría $𝐀 ⊨ φ (x_{1}) [1]$ sii $𝐀 ⊨ φ [x_{1}^{𝐀} [1]] = φ [1]$ , y en la estructura de recién la izquierda es verdadera y la derecha falsa.

Para tener a mano

$t =_{d} t (v_{1}, \dots, v_{n})$ : las $v_{i}$ son distintas y contienen a toda variable de $t$ . $φ =_{d} φ (v_{1}, \dots, v_{n})$ : distintas y $Li (φ) \subseteq {v_{1}, \dots, v_{n}}$ . Se puede declarar de más; $n = 0$ es cerrado o sentencia.
$t (P_{1}, \dots, P_{n})$ : $P_{j}$ va donde está la $j$ -ésima variable de la lista, todo a la vez. En fórmulas, sólo en las ocurrencias libres.
$t^{𝐀} [a_{1}, \dots, a_{n}]$ y $𝐀 ⊨ φ [a_{1}, \dots, a_{n}]$ : con cualquier $\vec{b}$ que le dé $a_{i}$ a $v_{i}$ ; no es ambiguo por los Lemas 1 y 2 de la Guía 10.
El orden de la lista es clave: la misma tupla con otro orden es otra afirmación.
Una variable de $P_{j}$ puede quedar acotada: $φ_{15} (x_{200})$ es una sentencia. Sustituible es la condición que lo impide.
Lema 1 y 4: lectura única con la lista adentro; el cuantificador se parte en «variable de la lista» y «variable nueva». Convenciones 5 y 6: la declaración baja a las piezas, con $v$ agregada en el caso (6).
Lema 3 y 6: $t^{𝐀} [\vec{a}]$ y $𝐀 ⊨ φ [\vec{a}]$ se calculan por cláusulas sin mencionar asignaciones infinitas; en (8) y (10) el $a$ va al lugar $j$ , en (9) y (11) al final.
El molde: Regla de Inducción desde 0, ${Enu}_{k}$ con estructura, declaración y elementos adentro; en fórmulas, también $n$ . Primero el caso $F_{k}$ , después cada caso del Lema 4.
Teoremas 8 y 9: reemplazar y evaluar conmutan; en fórmulas, si cada $w_{j}$ es sustituible por $t_{j}$ .