En una cadena, el término elige un argumento

El enunciado, textual: «Sea $\tau =(\varnothing ,\{{\mathrm{s}}^2,{\mathrm{i}}^2\},\varnothing ,a)$. Sea $t{=}_{d}t(v_1,v_2,v_3)\in T^{\tau }$. Sea $𝐀$ una estructura de tipo $\tau$ tal que $(A,{\mathrm{s}}^{𝐀},{\mathrm{i}}^{𝐀})$ es un reticulado terna cuyo orden asociado es total. Pruebe que $t^{𝐀}[a,b,c]\in \{a,b,c\}$, para cada $a,b,c\in A$». Es el Ejercicio 29 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.

Tiene el esqueleto del Ejercicio 21. Lo nuevo es la cuenta del paso, que ahora usa una hipótesis sobre el orden, y que hay tres variables declaradas en lugar de dos.

01 · Qué pide, en criollo

El orden asociado a un reticulado terna es el de la Guía 4: $x\le y$ si y sólo si ${\mathrm{s}}^{𝐀}(x,y)=y$. Que sea total quiere decir que dos elementos cualesquiera son comparables: $x\le y$ o $y\le x$. El diagrama de Hasse es una cadena, una sola columna de puntos.

En una cadena el supremo de dos elementos es el más alto de los dos y el ínfimo, el más bajo: ${\mathrm{s}}^{𝐀}$ e ${\mathrm{i}}^{𝐀}$ no fabrican elementos nuevos, devuelven uno de sus dos argumentos. Un término en $v_1,v_2,v_3$ combina las variables sólo con $\mathrm{s}$ e $\mathrm{i}$, así que su valor termina siendo el de una de las tres. En la cadena $0<p<q<1$, con $a=q$, $b=1$ y $c=p$, el término $\mathrm{s}(\mathrm{i}(v_1,v_2),v_3)$ vale ${\mathrm{s}}^{𝐀}({\mathrm{i}}^{𝐀}(q,1),p)={\mathrm{s}}^{𝐀}(q,p)=q$: eligió $a$.

Sin el orden total es falso, y alcanza con dos variables. En el diamante ${\mathrm{M}}_3$, con $a=p$, $b=q$ y $c=0$, el término $\mathrm{s}(v_1,v_2)$ vale $1$, que no es ninguno de los tres. Medido sobre los 885 términos de nivel a lo sumo 2 en $x_1,x_2,x_3$, con todas las ternas $a,b,c$: en la cadena de cuatro elementos y en la de cinco el valor es siempre uno de los tres (56 640 y 110 625 evaluaciones); en el diamante sale afuera 16 704 veces de 110 625, y en el pentágono ${\mathrm{N}}_5$, 11 424.

El título dice un poco más que la consigna: para cada $a,b,c$ hay una variable cuyo valor es el del término. Cuál, puede depender de $a,b,c$: $\mathrm{s}(v_1,v_2)$ elige $v_1$ cuando $b\le a$ y $v_2$ cuando $a\le b$.

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 \mathrm{Var}$ y $t\in T^{\tau }$, 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 $\tau$ y $a_1,\dots ,a_n\in A$, $t^{𝐀}[a_1,\dots ,a_n]$ denota el elemento $t^{𝐀}[\overrightarrow{b}]$, donde $\overrightarrow{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^{\tau }$ 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 \mathrm{𝒞}$; (2) $t=v_j$, para algún $j\in \{1,\dots ,n\}$; (3) $t=f(t_1,\dots ,t_m)$, con $f\in {\mathrm{ℱ}}_m$, $m\ge 1$ y $t_1,\dots ,t_m\in T^{\tau }$ únicos. Más aún, si $t\in T_{k+1}^{\tau }$, cuando se da (3) los términos $t_1,\dots ,t_m$ están en $T_k^{\tau }$.
• 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 $\tau$ 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 {\mathrm{ℱ}}_m$, $m\ge 1$ y $t_1,\dots ,t_m\in T^{\tau }$, entonces $t^{𝐀}[a_1,\dots ,a_n]=f^{𝐀}(t_1^{𝐀}[a_1,\dots ,a_n],\dots ,t_m^{𝐀}[a_1,\dots ,a_n])$.
• Tres identidades de reticulado terna (Guía 4, p. 1). Escribiendo $xsy$ por ${\mathrm{s}}^{𝐀}(x,y)$ y $xiy$ por ${\mathrm{i}}^{𝐀}(x,y)$, para todos $x,y\in A$: (I2) $xsy=ysx$; (I3) $xiy=yix$; (I7) $xi(xsy)=x$. Son las únicas que se usan.
• El orden asociado (Guía 4, p. 4): $\le =\{(x,y):xsy=y\}$. Total: para todos $x,y\in A$, $x\le y$ o $y\le x$.
• La Regla de Inducción desde 0. Si para cada $k\in \mathrm{\omega }$ hay un enunciado ${\mathrm{Enu}}_k$, y se prueba ${\mathrm{Enu}}_0$ y que ${\mathrm{Enu}}_k$ implica ${\mathrm{Enu}}_{k+1}$, entonces vale ${\mathrm{Enu}}_k$ para todo $k$. Como $T^{\tau }={\bigcup }_{k\in \mathrm{\omega }}{T}_k^{\tau }$, probar ${\mathrm{Enu}}_k$ para todo $k$ es probarlo para todo término.

Y dos datos del tipo: $\mathrm{𝒞}=\varnothing$ y $\mathrm{ℱ}={\mathrm{ℱ}}_2=\{\mathrm{s},\mathrm{i}\}$. El caso (1) del Lema 1 no se da, y en el (3) $f$ es $\mathrm{s}$ o $\mathrm{i}$, con $m=2$.

03 · La mariposa: el orden entra una sola vez

Igual que en el 21, la inducción no sabe nada de reticulados: baja de $t$ a sus piezas y lo único que pide es que el conjunto de valores posibles sea cerrado por ${\mathrm{s}}^{𝐀}$ e ${\mathrm{i}}^{𝐀}$. Acá el conjunto es $\{a,b,c\}$, y alcanza con algo más fuerte y más corto que en el 21: que ${\mathrm{s}}^{𝐀}(x,y)$ e ${\mathrm{i}}^{𝐀}(x,y)$ sean $x$ o $y$.

El supremo sale de la definición. Por ser total el orden, $x\le y$ o $y\le x$. Si $x\le y$, la definición del orden asociado dice $xsy=y$. Si $y\le x$, dice $ysx=x$, y por (I2) $xsy=x$.

El ínfimo no sale de la definición: el orden asociado se define con $\mathrm{s}$, y leerlo en $\mathrm{i}$ es un hecho que la Guía 4 deja preguntado («¿por qué?»). Por la regla de la lista se prueba, y es una línea: si $xsy=y$, reemplazando, $xiy=xi(xsy)=x$ por (I7). Si $ysx=x$, lo mismo con los papeles cambiados da $yix=y$, y por (I3) $xiy=y$.

Con eso $\{a,b,c\}$ es cerrado: si $x,y\in \{a,b,c\}$, ${\mathrm{s}}^{𝐀}(x,y)$ es $x$ o $y$, que están en $\{a,b,c\}$, y lo mismo ${\mathrm{i}}^{𝐀}(x,y)$. El ${\mathrm{Enu}}_k$ es el del 21 con tres variables, la declaración adentro y $a,b,c$ cuantificados adentro:

${\mathrm{Enu}}_k$: Sea $𝐀$ una estructura de tipo $\tau$ tal que $(A,{\mathrm{s}}^{𝐀},{\mathrm{i}}^{𝐀})$ es un reticulado terna cuyo orden asociado es total. Si $t\in T_k^{\tau }$ y $t{=}_{d}t(v_1,v_2,v_3)$, entonces $t^{𝐀}[a,b,c]\in \{a,b,c\}$ para cada $a,b,c\in A$.

El caso base son tres variables en vez de dos: $t=v_j$ con $j\in \{1,2,3\}$, y el Lema 3 (2) da $a$, $b$ o $c$. El paso es el del 21 palabra por palabra, con el lema del orden en lugar del de los cuatro valores.

Abajo se arma un término en $x_1,x_2,x_3$. En la cadena, cada renglón elige uno de sus dos argumentos y la elección baja hasta una variable. En el diamante y en el pentágono hay pares incomparables, y ahí un renglón puede no elegir ninguno.

04 · El escarabajo: la prueba escrita

Lema. Si $x,y\in A$, entonces ${\mathrm{s}}^{𝐀}(x,y)\in \{x,y\}$ e ${\mathrm{i}}^{𝐀}(x,y)\in \{x,y\}$.

Prueba del lema. Escribimos $xsy$ por ${\mathrm{s}}^{𝐀}(x,y)$ y $xiy$ por ${\mathrm{i}}^{𝐀}(x,y)$. Como $(A,{\mathrm{s}}^{𝐀},{\mathrm{i}}^{𝐀})$ es un reticulado terna, valen (I1) a (I7), y su orden asociado es $\le =\{(x,y):xsy=y\}$. Sean $x,y\in A$. Como el orden es total, $x\le y$ o $y\le x$.

• Si $x\le y$: por definición de $\le$, $xsy=y$, que está en $\{x,y\}$. Además, reemplazando $y$ por $xsy$, $xiy=xi(xsy)=x$ por (I7), que está en $\{x,y\}$.
• Si $y\le x$: por definición de $\le$, $ysx=x$, y por (I2) $xsy=ysx=x$, que está en $\{x,y\}$. Además $xiy=yix$ por (I3), y reemplazando $x$ por $ysx$, $yix=yi(ysx)=y$ por (I7); luego $xiy=y$, que está en $\{x,y\}$. ∎

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

Sea $𝐀$ una estructura de tipo $\tau$ tal que $(A,{\mathrm{s}}^{𝐀},{\mathrm{i}}^{𝐀})$ es un reticulado terna cuyo orden asociado es total. Si $t\in T_k^{\tau }$ y $t{=}_{d}t(v_1,v_2,v_3)$, entonces $t^{𝐀}[a,b,c]\in \{a,b,c\}$ para cada $a,b,c\in A$.

Caso base: ${\mathrm{Enu}}_0$. Sea $t\in T_0^{\tau }$ con $t{=}_{d}t(v_1,v_2,v_3)$. Por el Lema 1 de la Guía 11, $t=c\prime$ para algún $c\prime \in \mathrm{𝒞}$ (con prima, para no confundirla con el elemento $c$), o $t=v_j$ para algún $j\in \{1,2,3\}$; el caso (3) no se da, porque $T_0^{\tau }=\mathrm{Var}\cup \mathrm{𝒞}$ y un término de la forma $f(t_1,\dots ,t_m)$ no es una variable ni un nombre de constante. Como $\mathrm{𝒞}=\varnothing$, $t=v_j$ con $j\in \{1,2,3\}$. Sean $a,b,c\in A$. Por el Lema 3 (2) de la Guía 11, $t^{𝐀}[a,b,c]$ es $a$ si $j=1$, $b$ si $j=2$ y $c$ si $j=3$. En los tres casos está en $\{a,b,c\}$.

Paso: ${\mathrm{Enu}}_k\Rightarrow {\mathrm{Enu}}_{k+1}$. Supongamos que vale ${\mathrm{Enu}}_k$ y sea $t\in T_{k+1}^{\tau }$ con $t{=}_{d}t(v_1,v_2,v_3)$. Sean $a,b,c\in A$.

Caso $t\in T_k^{\tau }$. Entonces $t^{𝐀}[a,b,c]\in \{a,b,c\}$ por ${\mathrm{Enu}}_k$.

Caso $t\in T_{k+1}^{\tau }-T_k^{\tau }$. 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^{\tau }\subseteq T_k^{\tau }$, así que no se dan. Luego $t=f(t_1,\dots ,t_m)$ con $f\in {\mathrm{ℱ}}_m$ y $m\ge 1$, y por la segunda parte del Lema 1, $t_1,\dots ,t_m\in T_k^{\tau }$. Como $\mathrm{ℱ}={\mathrm{ℱ}}_2=\{\mathrm{s},\mathrm{i}\}$, $m=2$ y $f$ es $\mathrm{s}$ o $\mathrm{i}$. Por la Convención Notacional 5, $t_1{=}_d{t}_1(v_1,v_2,v_3)$ y $t_2{=}_d{t}_2(v_1,v_2,v_3)$, y por ${\mathrm{Enu}}_k$ aplicado a $t_1$ y a $t_2$, $t_1^{𝐀}[a,b,c]\in \{a,b,c\}$ y $t_2^{𝐀}[a,b,c]\in \{a,b,c\}$.

Subcaso $t=\mathrm{s}(t_1,t_2)$. Por el Lema 3 (3) de la Guía 11, $t^{𝐀}[a,b,c]={\mathrm{s}}^{𝐀}(t_1^{𝐀}[a,b,c],t_2^{𝐀}[a,b,c])$, y por el lema este valor es $t_1^{𝐀}[a,b,c]$ o $t_2^{𝐀}[a,b,c]$. Los dos están en $\{a,b,c\}$.

Subcaso $t=\mathrm{i}(t_1,t_2)$. Por el Lema 3 (3), $t^{𝐀}[a,b,c]={\mathrm{i}}^{𝐀}(t_1^{𝐀}[a,b,c],t_2^{𝐀}[a,b,c])$, y por la segunda mitad del lema es $t_1^{𝐀}[a,b,c]$ o $t_2^{𝐀}[a,b,c]$, que están en $\{a,b,c\}$.

Como $a,b,c$ eran arbitrarios, vale ${\mathrm{Enu}}_{k+1}$. Por la Regla de Inducción desde 0, vale ${\mathrm{Enu}}_k$ para todo $k\in \mathrm{\omega }$. Y como $T^{\tau }={\bigcup }_{k\in \mathrm{\omega }}{T}_k^{\tau }$, todo $t\in T^{\tau }$ con $t{=}_{d}t(v_1,v_2,v_3)$ está en algún $T_k^{\tau }$, así que $t^{𝐀}[a,b,c]\in \{a,b,c\}$ para cada $a,b,c\in A$. ∎

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

Lo que hace perder puntos. Decir que en una cadena el supremo es el máximo sin probarlo desde la definición del orden asociado. Probar el supremo y despachar el ínfimo con «análogamente»: el supremo es la definición más (I2), y el ínfimo necesita (I7), porque el orden no se definió con $\mathrm{i}$. Olvidar, en el supremo, el caso $y\le x$, que es el que usa (I2). Escribir el caso base con $j\in \{1,2\}$ copiado del 21. Y todo lo del molde: nombrar la Regla de Inducción desde 0, la declaración adentro del ${\mathrm{Enu}}_k$, el caso $t\in T_k^{\tau }$.

Lo que se lleva. Es el Ejercicio 21 con otro conjunto cerrado: allá $\{a,b,asb,aib\}$ y diez cuentas, acá $\{a,b,c\}$ y un lema de dos casos. En una cadena los dos coinciden en algo: con dos variables, $asb$ y $aib$ son $a$ o $b$, y el conjunto del 21 se achica a $\{a,b\}$. El Ejercicio 23 es la forma general: un conjunto que contiene los valores de las variables y de las constantes y es cerrado por las operaciones contiene el valor de todo término. Y el Ejercicio 24 vuelve a usar el orden, ahora para comparar dos valores en lugar de ubicar uno.

Para tener a mano

1. En un orden total, ${\mathrm{s}}^{𝐀}(x,y)\in \{x,y\}$ e ${\mathrm{i}}^{𝐀}(x,y)\in \{x,y\}$. El supremo sale de la definición $x\le y⟺xsy=y$ y de (I2); el ínfimo, de (I7) y de (I3).
2. Por eso $\{a,b,c\}$ es cerrado, y el valor del término es el de una de las tres variables. Cuál, depende de $a,b,c$.
3. ${\mathrm{Enu}}_k$: si $t\in T_k^{\tau }$ y $t{=}_{d}t(v_1,v_2,v_3)$, entonces $t^{𝐀}[a,b,c]\in \{a,b,c\}$ para cada $a,b,c\in A$.
4. Base: Lema 1 y Lema 3 (2), con $j\in \{1,2,3\}$. Paso: caso $t\in T_k^{\tau }$; si no, Lema 1, Convención 5, ${\mathrm{Enu}}_k$, Lema 3 (3) y el lema del orden.
5. Medido: 885 términos de nivel a lo sumo 2. En las cadenas de cuatro y cinco, ninguno se sale; en el diamante, 16 704 de 110 625.