Un subuniverso es cerrado por términos

El enunciado, textual: «Sea $τ = ({0, 1}, {s^{2}, i^{2}}, \emptyset, a)$ . Sea $𝐀$ una estructura de tipo $τ$ tal que $(A, s^{𝐀}, i^{𝐀}, 0^{𝐀}, 1^{𝐀})$ es un reticulado acotado. Sea $S$ un subuniverso de $(A, s^{𝐀}, i^{𝐀}, 0^{𝐀}, 1^{𝐀})$ . Pruebe que cualesquiera sea $t =_{d} t (v_{1}, \dots, v_{n}) \in T^{τ}$ y $a_{1}, \dots, a_{n} \in S$ , se tiene que $t^{𝐀} [a_{1}, \dots, a_{n}] \in S$ ». Es el Ejercicio 30 de la Guía 11, enunciado en notación declaratoria: se resuelve dentro de ella, con los lemas y las convenciones de la Guía 11.

Los dos anteriores, el 21 y el 22, eran inducciones cuyo paso pedía probar que cierto conjunto es cerrado por $s^{𝐀}$ e $i^{𝐀}$ . Acá eso es la hipótesis. Lo que aparece es otra cosa: el tipo tiene constantes.

01 · Qué pide, en criollo

El tipo tiene dos nombres de constante, $0$ y $1$ , además de $s$ e $i$ . Los términos son las variables, las constantes $0$ y $1$ , y $s (t_{1}, t_{2})$ , $i (t_{1}, t_{2})$ con $t_{1}, t_{2}$ términos. $𝐀$ interpreta $0$ y $1$ como el mínimo y el máximo de un reticulado acotado.

Subuniverso, como lo define la Guía 5 (p. 2): si $(L, s, i, 0, 1)$ es un reticulado acotado, un conjunto $S \subseteq L$ es subuniverso de $(L, s, i, 0, 1)$ si $0, 1 \in S$ y además $S$ es cerrado bajo las operaciones $s$ e $i$ : si $x, y \in S$ , entonces $x s y \in S$ y $x i y \in S$ . Acá el reticulado es $(A, s^{𝐀}, i^{𝐀}, 0^{𝐀}, 1^{𝐀})$ , así que eso es $0^{𝐀}, 1^{𝐀} \in S$ y $s^{𝐀} (x, y), i^{𝐀} (x, y) \in S$ para todos $x, y \in S$ . Es un conjunto, no una 5-upla.

El enunciado dice que si a las variables se les dan valores en $S$ , el término entero cae en $S$ . Cada operación que el término hace queda adentro porque $S$ es cerrado; cada constante que el término usa queda adentro porque $S$ tiene al $0^{𝐀}$ y al $1^{𝐀}$ . Un ejemplo en el cubo, el reticulado de los subconjuntos de un conjunto de tres elementos: tres átomos $p, q, r$ , sus supremos de a dos $u = p s q$ , $v = p s r$ , $w = q s r$ , y el $0$ y el $1$ . $S = {0, p, u, 1}$ es un subuniverso, y $s (i (v_{1}, 1), v_{2})$ en $p, u$ vale $s^{𝐀} (i^{𝐀} (p, 1), u) = s^{𝐀} (p, u) = u$ , que está en $S$ .

Las constantes son las que se olvidan. $S = {p, u}$ también es cerrado por $s^{𝐀}$ e $i^{𝐀}$ — $p s u = u$ , $p i u = p$ —, pero no tiene al $0$ , y el término $i (v_{1}, 0)$ en $p, u$ vale $0^{𝐀} = 0$ , que no está en $S$ . Medido en el cubo: de sus 256 subconjuntos, 29 son subuniversos, y en ellos los 2596 términos de nivel a lo sumo 2 en $x_{1}, x_{2}, 0, 1$ , con todos los pares de valores en $S$ , caen siempre en $S$ (1 640 672 evaluaciones). Hay además 44 conjuntos no vacíos cerrados por $s^{𝐀}$ e $i^{𝐀}$ a los que les falta el $0$ o el $1$ . Ahí los mismos términos se salen 203 786 veces, y todas con un término que usa 0 o 1: sin constantes, ninguno se sale. La hipótesis $0^{𝐀}, 1^{𝐀} \in S$ está para el caso base de las constantes, y para nada más.

02 · Las herramientas

La lista deja usar sin enunciar los lemas Menú y los teoremas de lectura única, y en los ejercicios declaratorios manda usar los lemas y las convenciones de la Guía 11, que se citan con su número. Lo demás se enuncia y se prueba. Las piezas:

La declaración (Guía 11, p. 1). Si $v_{1}, \dots, v_{n} \in Var$ y $t \in T^{τ}$ , escribir $t =_{d} t (v_{1}, \dots, v_{n})$ declara 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 ocurran todas. Con $n = 0$ , $t =_{d} t ()$ dice que $t$ es cerrado.
Convención Notacional 2 (p. 2). Declarado $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 $a_{i}$ .
Lema 1, lectura única de términos declarados (p. 8). Si $t \in T^{τ}$ y $t =_{d} t (v_{1}, \dots, v_{n})$ , se da una y sólo una de las siguientes: (1) $t = c$ , para algún $c \in 𝒞$ ; (2) $t = v_{j}$ , para algún $j \in {1, \dots, n}$ ; (3) $t = f (t_{1}, \dots, t_{m})$ , con $f \in ℱ_{m}$ , $m \geq 1$ y $t_{1}, \dots, t_{m} \in T^{τ}$ únicos. 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}^{τ}$ .
Convención Notacional 5 (p. 8). Declarado $t =_{d} t (v_{1}, \dots, v_{n})$ , si se da el caso (3) del Lema 1 se suponen hechas también las declaraciones $t_{1} =_{d} t_{1} (v_{1}, \dots, v_{n})$ , …, $t_{m} =_{d} t_{m} (v_{1}, \dots, v_{n})$ : las variables de cada $t_{j}$ están entre las de $t$ .
Lema 3, carácter recursivo de $t^{𝐀} [a_{1}, \dots, a_{n}]$ (p. 9). Si $t =_{d} t (v_{1}, \dots, v_{n})$ , $𝐀$ es un modelo de tipo $τ$ y $a_{1}, \dots, a_{n} \in A$ : (1) si $t = c$ , $t^{𝐀} [a_{1}, \dots, a_{n}] = c^{𝐀}$ ; (2) si $t = v_{j}$ , $t^{𝐀} [a_{1}, \dots, a_{n}] = a_{j}$ ; (3) si $t = f (t_{1}, \dots, t_{m})$ , con $f \in ℱ_{m}$ , $m \geq 1$ y $t_{1}, \dots, t_{m} \in T^{τ}$ , entonces $t^{𝐀} [a_{1}, \dots, a_{n}] = f^{𝐀} (t_{1}^{𝐀} [a_{1}, \dots, a_{n}], \dots, t_{m}^{𝐀} [a_{1}, \dots, a_{n}])$ .
Subuniverso (Guía 5, p. 2), enunciado arriba: $0^{𝐀}, 1^{𝐀} \in S$ , y $S$ cerrado bajo $s^{𝐀}$ e $i^{𝐀}$ .
La Regla de Inducción desde 0. Si para cada $k \in ω$ hay un enunciado ${Enu}_{k}$ , y se prueba ${Enu}_{0}$ y que ${Enu}_{k}$ implica ${Enu}_{k + 1}$ , entonces vale ${Enu}_{k}$ para todo $k$ . Como $T^{τ} = ⋃_{k \in ω} T_{k}^{τ}$ , probar ${Enu}_{k}$ para todo $k$ es probarlo para todo término.

Y dos datos del tipo: $𝒞 = {0, 1}$ y $ℱ = ℱ_{2} = {s, i}$ . En el caso (1) del Lema 1, $c$ es $0$ o $1$ ; en el (3), $f$ es $s$ o $i$ , con $m = 2$ . La guía nota, después del Lema 1, que con $n = 0$ el caso (2) no puede suceder: un término cerrado como $s (0, 1)$ sólo tiene constantes en sus hojas.

Ninguna identidad de reticulado aparece en la lista. No hace falta: que $𝐀$ sea un reticulado acotado sólo sirve para que tenga sentido hablar de un subuniverso suyo.

03 · La mariposa: lo que va adentro del Enu

Inducción en el nivel, como en el 21 y el 22. La diferencia es que $n$ y las variables declaradas no vienen fijas en el enunciado: la consigna dice «cualesquiera sea $t =_{d} t (v_{1}, \dots, v_{n})$ ». Por eso van adentro del ${Enu}_{k}$ , junto con el término y los valores. $𝐀$ y $S$ sí están fijos por el enunciado, y quedan afuera.

${Enu}_{k}$ : Cualesquiera sean $n \in ω$ , las variables distintas $v_{1}, \dots, v_{n}$ y $t \in T_{k}^{τ}$ con $t =_{d} t (v_{1}, \dots, v_{n})$ , se tiene que $t^{𝐀} [a_{1}, \dots, a_{n}] \in S$ para cada $a_{1}, \dots, a_{n} \in S$ .

En el paso, la Convención 5 declara las piezas con las mismas $v_{1}, \dots, v_{n}$ , así que ${Enu}_{k}$ se aplica a ellas con el mismo $n$ y los mismos valores $a_{1}, \dots, a_{n}$ . Que $n$ y las variables estén cuantificados adentro no se usa para cambiarlos; está porque el enunciado del ejercicio los cuantifica, y el ${Enu}_{k}$ tiene que decir lo que se va a probar.

El caso base tiene tres casos, no uno. Por el Lema 1, un $t \in T_{0}^{τ}$ declarado es $0$ , $1$ o una $v_{j}$ . Para $v_{j}$ , el Lema 3 (2) da $a_{j}$ , que está en $S$ por hipótesis. Para $0$ , el Lema 3 (1) da $0^{𝐀}$ , que está en $S$ porque lo pide la definición de subuniverso; para $1$ , lo mismo con $1^{𝐀}$ . Una prueba copiada del 21, donde el tipo no tenía constantes, tiene sólo el caso de las variables, y le faltan dos.

El paso es el del 21 con el lema de cierre reemplazado por la definición: $t = s (t_{1}, t_{2})$ o $t = i (t_{1}, t_{2})$ , las piezas en $T_{k}^{τ}$ y declaradas por la Convención 5, sus valores en $S$ por ${Enu}_{k}$ , y el Lema 3 (3) dice que el valor de $t$ es $s^{𝐀}$ o $i^{𝐀}$ de dos elementos de $S$ , que está en $S$ porque $S$ es cerrado.

Abajo, el cubo con $S = {p, u}$ , que es cerrado por $s$ e $i$ pero no tiene ni el $0$ ni el $1$ . Cada subtérmino tiene su renglón con su valor, de las hojas a la raíz, y el primero que se sale de $S$ dice qué parte de la definición faltó.

S — cerrado por s e i — 0 ∈ S — 1 ∈ S — subuniverso — tᴬ[a₁,a₂] — en S —

04 · El escarabajo: la prueba escrita

Prueba. Usaremos la Regla de Inducción desde 0. Sean $𝐀$ y $S$ como en el enunciado. Para cada $k \in ω$ sea ${Enu}_{k}$ el enunciado:

Cualesquiera sean $n \in ω$ , las variables distintas $v_{1}, \dots, v_{n}$ y $t \in T_{k}^{τ}$ con $t =_{d} t (v_{1}, \dots, v_{n})$ , se tiene que $t^{𝐀} [a_{1}, \dots, a_{n}] \in S$ para cada $a_{1}, \dots, a_{n} \in S$ .

Caso base: ${Enu}_{0}$ . Sean $n \in ω$ , $v_{1}, \dots, v_{n}$ variables distintas, $t \in T_{0}^{τ}$ con $t =_{d} t (v_{1}, \dots, v_{n})$ , y $a_{1}, \dots, a_{n} \in S$ . Por el Lema 1 de la Guía 11, $t = c$ para algún $c \in 𝒞$ , o $t = v_{j}$ para algún $j \in {1, \dots, n}$ ; el caso (3) no se da, porque $T_{0}^{τ} = Var \cup 𝒞$ y un término de la forma $f (t_{1}, \dots, t_{m})$ no es una variable ni un nombre de constante. Como $𝒞 = {0, 1}$ , quedan tres casos.

$t = 0$ . Por el Lema 3 (1) de la Guía 11, $t^{𝐀} [a_{1}, \dots, a_{n}] = 0^{𝐀}$ , y $0^{𝐀} \in S$ porque $S$ es subuniverso de $(A, s^{𝐀}, i^{𝐀}, 0^{𝐀}, 1^{𝐀})$ .
$t = 1$ . Por el Lema 3 (1), $t^{𝐀} [a_{1}, \dots, a_{n}] = 1^{𝐀}$ , y $1^{𝐀} \in S$ porque $S$ es subuniverso.
$t = v_{j}$ , con $1 \leq j \leq n$ . Por el Lema 3 (2), $t^{𝐀} [a_{1}, \dots, a_{n}] = a_{j}$ , que está en $S$ por hipótesis. (Si $n = 0$ , este caso no se da.)

Paso: ${Enu}_{k} \Rightarrow {Enu}_{k + 1}$ . Supongamos que vale ${Enu}_{k}$ . Sean $n \in ω$ , $v_{1}, \dots, v_{n}$ variables distintas, $t \in T_{k + 1}^{τ}$ con $t =_{d} t (v_{1}, \dots, v_{n})$ , y $a_{1}, \dots, a_{n} \in S$ .

Caso $t \in T_{k}^{τ}$ . Entonces $t^{𝐀} [a_{1}, \dots, a_{n}] \in S$ por ${Enu}_{k}$ .

Caso $t \in T_{k + 1}^{τ} - T_{k}^{τ}$ . Por el Lema 1 de la Guía 11, $t$ es de la forma (1), (2) o (3). Las formas (1) y (2) son elementos de $T_{0}^{τ} \subseteq T_{k}^{τ}$ , así que no se dan. Luego $t = f (t_{1}, \dots, t_{m})$ con $f \in ℱ_{m}$ y $m \geq 1$ , y por la segunda parte del Lema 1, $t_{1}, \dots, t_{m} \in T_{k}^{τ}$ . Como $ℱ = ℱ_{2} = {s, i}$ , $m = 2$ y $f$ es $s$ o $i$ . Por la Convención Notacional 5, $t_{1} =_{d} t_{1} (v_{1}, \dots, v_{n})$ y $t_{2} =_{d} t_{2} (v_{1}, \dots, v_{n})$ , y por ${Enu}_{k}$ aplicado a $t_{1}$ y a $t_{2}$ , con el mismo $n$ y las mismas variables y valores, $t_{1}^{𝐀} [a_{1}, \dots, a_{n}] \in S$ y $t_{2}^{𝐀} [a_{1}, \dots, a_{n}] \in S$ .

Subcaso $t = s (t_{1}, t_{2})$ . Por el Lema 3 (3) de la Guía 11, $t^{𝐀} [a_{1}, \dots, a_{n}] = s^{𝐀} (t_{1}^{𝐀} [a_{1}, \dots, a_{n}], t_{2}^{𝐀} [a_{1}, \dots, a_{n}])$ . Es $s^{𝐀}$ de dos elementos de $S$ , y como $S$ es cerrado bajo $s^{𝐀}$ , está en $S$ .

Subcaso $t = i (t_{1}, t_{2})$ . Por el Lema 3 (3), $t^{𝐀} [a_{1}, \dots, a_{n}] = i^{𝐀} (t_{1}^{𝐀} [a_{1}, \dots, a_{n}], t_{2}^{𝐀} [a_{1}, \dots, a_{n}])$ , y como $S$ es cerrado bajo $i^{𝐀}$ , está en $S$ .

Como $n$ , las variables, $t$ y los valores eran arbitrarios, vale ${Enu}_{k + 1}$ . Por la Regla de Inducción desde 0, vale ${Enu}_{k}$ para todo $k \in ω$ . Y como $T^{τ} = ⋃_{k \in ω} T_{k}^{τ}$ , todo $t \in T^{τ}$ con $t =_{d} t (v_{1}, \dots, v_{n})$ está en algún $T_{k}^{τ}$ , así que $t^{𝐀} [a_{1}, \dots, a_{n}] \in S$ para cada $a_{1}, \dots, a_{n} \in S$ . ∎

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

Lo que hace perder puntos. El caso base con una sola línea, $t = v_{j}$ , copiado de un ejercicio sin constantes: faltan $t = 0$ y $t = 1$ , que son los únicos lugares donde se usa que $0^{𝐀}, 1^{𝐀} \in S$ . Decir « $S$ es cerrado» sin decir que es por la definición de subuniverso de la Guía 5. Un ${Enu}_{k}$ con $n$ y las variables afuera, sin decir que son los del enunciado. Y lo de siempre: la Regla de Inducción desde 0 con su nombre, la declaración adentro, el caso $t \in T_{k}^{τ}$ .

Lo que se lleva. La prueba no usó ningún axioma de reticulado: vale igual para cualquier tipo y cualquier conjunto que contenga las interpretaciones de las constantes y sea cerrado por las de las funciones. El Ejercicio 21 y el 22 son casos sin constantes, y lo que costaba en ellos era probar que el conjunto es cerrado. El caso base con constantes vuelve en el Ejercicio 25, donde la constante $cero$ es lo que el término absorbe, y en el Ejercicio 28, donde el caso $t = c$ es la condición del homomorfismo sobre las constantes.

Para tener a mano

Subuniverso (Guía 5, p. 2): $0^{𝐀}, 1^{𝐀} \in S$ y $S$ cerrado bajo $s^{𝐀}$ e $i^{𝐀}$ . Las dos mitades se usan, cada una en un lugar distinto de la prueba.
${Enu}_{k}$ : cualesquiera sean $n$ , $v_{1}, \dots, v_{n}$ y $t \in T_{k}^{τ}$ con $t =_{d} t (v_{1}, \dots, v_{n})$ , $t^{𝐀} [a_{1}, \dots, a_{n}] \in S$ para cada $a_{1}, \dots, a_{n} \in S$ .
Base, tres casos: $t = 0$ y $t = 1$ por el Lema 3 (1) y la definición; $t = v_{j}$ por el Lema 3 (2) y la hipótesis.
Paso: caso $t \in T_{k}^{τ}$ ; si no, Lema 1, Convención 5, ${Enu}_{k}$ y Lema 3 (3), y $S$ cerrado.
Medido en el cubo: en los 29 subuniversos ningún término se sale. En los 44 conjuntos cerrados sin el 0 o sin el 1 se salen 203 786 veces, todas con un término que usa una constante.