Contar operaciones cambia la base

El enunciado, textual: «Sea $\tau =(\varnothing ,\{\mathrm{s},\mathrm{i}\},\varnothing ,\{(\mathrm{s},2),(\mathrm{i},2)\})$.

1. ¿Cuántas estructuras de tipo $\tau$ con universo igual a $\{1,2,3,4,5,6,7,8,9\}$ hay? (Puede usar el Lema 1 de la Guía 8)
2. ¿Alguna de ellas es un reticulado terna?
3. Cuales de ellas son "esencialmente" reticulados terna
4. De una biyección entre el conjunto formado por todos los reticulados terna y un subconjunto del conjunto de todas las estructuras de tipo $\tau$».

Es el tercero del molde. El Lema 1 con su prueba y la idea de armar y desarmar la interpretación están en el Ejercicio 17; el Ejercicio 18 mostró que la aridad pone el exponente. Acá lo que cambia es otra cosa.

01 · Antes de resolver: en qué casillero está cada nombre

El tipo es una 4-upla $(C,F,R,a)$, y lo primero es mirar en qué coordenada están $\mathrm{s}$ e $\mathrm{i}$: en la segunda. Son nombres de función, no de relación. Una estructura los interpreta con operaciones binarias, funciones de $A^2$ en $A$, y no con subconjuntos de $A^2$. En cada uno de los $81$ pares no se decide «está o no está», sino cuál de los nueve elementos devuelve.

Los otros incisos son los del molde. (b) es no, por la forma. (c) pide una condición sobre $(A,i)$. (d) pide la biyección con todos los reticulados terna, sobre cualquier universo, y nombrar el subconjunto.

Hay además un choque de notación que conviene resolver antes de escribir. La cátedra llama $i$ a la función interpretación de una estructura, y el tipo tiene un nombre de función que también se llama $\mathrm{i}$. Los nombres van en letra derecha; la interpretación, en cursiva. Así, $i(\mathrm{i})$ se lee «la operación con la que la estructura interpreta al nombre $\mathrm{i}$».

02 · Las herramientas

La estructura de tipo τ (Guía 8): un par $(A,i)$ con $A$ no vacío e $i$ una función con dominio $\{\mathrm{s},\mathrm{i}\}$ tal que $i(\mathrm{s})$ e $i(\mathrm{i})$ son operaciones binarias sobre $A$. Como conjunto, $i=\{(\mathrm{s},i(\mathrm{s})),(\mathrm{i},i(\mathrm{i}))\}$.

El reticulado terna (Guía 4): una 3-upla $(L,s,i)$ con $L$ un conjunto no vacío y $s$, $i$ operaciones binarias sobre $L$ que cumplen, para todos $x,y,z\in L$, las siete identidades:

• I1 $xsx=x$ y $xix=x$;
• I2 $xsy=ysx$; I3 $xiy=yix$;
• I4 $(xsy)sz=xs(ysz)$; I5 $(xiy)iz=xi(yiz)$;
• I6 $xs(xiy)=x$; I7 $xi(xsy)=x$.

Por el teorema de Dedekind, eso es lo mismo que pedir que haya un orden parcial sobre $L$ en el que todo par tenga supremo e ínfimo, y que $s$ e $i$ sean exactamente esas dos operaciones: el orden es $x\le y$ sii $xsy=y$. Es la tesis de cuando las siete identidades se cumplen, aparece un orden.

El Lema 1 de la Guía 8: (1) si $A$ y $B$ son finitos no vacíos, hay $|B{|}^{|A|}$ funciones con dominio $A$ e imagen contenida en $B$; (2) hay $2^{|A|}$ subconjuntos de un conjunto finito $A$. Acá se usa el (1). La prueba está en el Ejercicio 17.

Esencialmente. La Guía 8 da el ejemplo: $(\mathbb{N},i)$ con $i=\{(\mathrm{s},\max ),(\mathrm{i},\min )\}$ «estrictamente hablando no es un reticulado terna ya que es una 2-upla y los reticulados terna son 3-uplas», pero a nivel de información es lo mismo que $(\mathbb{N},\max ,\min )$. Las estructuras así son los modelos de la teoría elemental de los reticulados terna, que tiene como axiomas las siete identidades escritas como sentencias elementales.

03 · La mariposa

Para (a): dibujar una operación. Una operación binaria sobre $\{1,\dots ,9\}$ es una tabla de $9\times 9$, como la de multiplicar: en cada una de las $81$ casillas va un elemento, y cualquiera de los nueve sirve. Son $9·9\cdots 9$, ochenta y una veces: el Lema 1 (1) con dominio $A^2$ y codominio $A$,

$$|A{|}^{|A^2|}=9^{81}$$

La estructura pide dos tablas, una para $\mathrm{s}$ y otra para $\mathrm{i}$, que se llenan sin mirarse:

$$9^{81}·9^{81}=9^{162}$$

Es un número de 155 cifras; también es $3^{324}$. Contra los $2^{90}$ del Ejercicio 18 la diferencia es enorme, y viene de un solo lugar: el exponente sigue siendo $81$ por nombre —lo pone la aridad—, pero la base pasó de $2$ a $9$. Una relación elige, en cada casilla, entre dos; una operación, entre $|A|$.

Para (b): contar coordenadas. Un reticulado terna es una 3-upla; una estructura, una 2-upla. Es el argumento literal de la Guía 8.

Para (c): desarmar y preguntar. Se desarma $i$ en la 3-upla $(A,i(\mathrm{s}),i(\mathrm{i}))$ y se pregunta si cumple I1 a I7. Los nombres $\mathrm{s}$ e $\mathrm{i}$ no obligan a nada: la Guía 8 da $(ℝ,\{(\mathrm{s},+),(\mathrm{i},+)\})$ como estructura de este tipo, y la suma no es idempotente. Casi ninguna estructura pasa. En universos chicos se puede contar:

La columna del medio es $n^{2n^2}$, y con uno, dos y tres elementos se reprodujo recorriendo todas las tablas: las $\mathrm{19 683}$ operaciones sobre $\{1,2,3\}$, al cuadrado. La de la derecha salió de evaluar las siete identidades. Con cuatro y cinco elementos se recorrieron sólo las operaciones conmutativas e idempotentes, porque las otras ya fallan I1, I2 o I3. Los números se pueden entender: con hasta tres elementos todo reticulado es una cadena, y hay $n!$ maneras de ordenar los rótulos. Con cuatro aparecen las $24$ cadenas más los $12$ rombos —el rombo tiene una simetría, así que son $4!/2$—, y dan $36$.

Para (d): armar y desarmar. A la 3-upla se le arma la $i$ que manda $\mathrm{s}$ a la segunda coordenada e $\mathrm{i}$ a la tercera. La imagen es el conjunto de (c).

Con tres elementos, «Contar todas» no puede recorrer los 387 millones de pares uno por uno en el navegador. Hace lo mismo que el recorrido de la tabla: separa primero las operaciones que cumplen por sí solas lo que I1, I2 e I4 le piden a $s$ —son 9 de las 19 683—, porque un par cuya primera tabla falla eso ya no es reticulado mire lo que mire la segunda. Lo mismo para $i$. Después prueba las absorciones en los 81 pares que quedan. Quedan 6, las seis cadenas.

04 · El escarabajo

(a) Sea $A=\{1,\dots ,9\}$ y sea $\mathrm{Op}$ el conjunto de las operaciones binarias sobre $A$, es decir de las funciones con dominio $A^2$ e imagen contenida en $A$. Por el Lema 1 (1), con $A^2$ como dominio y $A$ como codominio, $|\mathrm{Op}|=|A{|}^{|A^2|}=9^{81}$. Una estructura de tipo $\tau$ con universo $A$ es un par $(A,i)$ con $i=\{(\mathrm{s},f),(\mathrm{i},g)\}$ y $f,g\in \mathrm{Op}$, y la correspondencia $(A,\{(\mathrm{s},f),(\mathrm{i},g)\})\mapsto (f,g)$ es una biyección entre esas estructuras y $\mathrm{Op}\times \mathrm{Op}$: estructuras iguales tienen la misma $i$, y evaluándola en $\mathrm{s}$ y en $\mathrm{i}$, el mismo par $(f,g)$; y cada par da una estructura. Luego hay $9^{81}·9^{81}=9^{162}$ estructuras de tipo $\tau$ con universo $A$.

(b) No, ninguna: un reticulado terna es una 3-upla y una estructura de tipo $\tau$ es una 2-upla. Lo que sí hay son estructuras esencialmente reticulados terna, como $(A,\{(\mathrm{s},\max ),(\mathrm{i},\min )\})$, con el máximo y el mínimo respecto del orden usual. $(A,\max ,\min )$ cumple las siete identidades: el máximo y el mínimo son idempotentes, conmutativos y asociativos, y $\max (x,\min (x,y))=x$ porque $\min (x,y)\le x$, y dualmente $\min (x,\max (x,y))=x$ porque $x\le \max (x,y)$.

(c) Son las estructuras $(A,i)$ de tipo $\tau$ tales que la 3-upla $(A,i(\mathrm{s}),i(\mathrm{i}))$ es un reticulado terna, es decir, tales que las operaciones $i(\mathrm{s})$ e $i(\mathrm{i})$, puestas en el lugar de $s$ y de $i$, cumplen I1 a I7 para todos $x,y,z\in A$. Por ejemplo, I6 pide $i(\mathrm{s})(x,i(\mathrm{i})(x,y))=x$. Equivalentemente, son los modelos de la teoría elemental de los reticulados terna.

(d) Para no mezclar las operaciones con los nombres, escribamos un reticulado terna cualquiera como $(L,\bigsqcup ,\sqcap )$. Sea $𝒮$ el conjunto de las estructuras de (c), con universo cualquiera, y definamos

$$\Phi ((L,\bigsqcup ,\sqcap ))=(L,\{(\mathrm{s},\bigsqcup ),(\mathrm{i},\sqcap )\})$$

Está bien definida y cae en 𝒮. $L$ es no vacío y $\bigsqcup$, $\sqcap$ son operaciones binarias sobre $L$, así que $\{(\mathrm{s},\bigsqcup ),(\mathrm{i},\sqcap )\}$ es una función con dominio $\{\mathrm{s},\mathrm{i}\}$ que manda cada nombre de función binaria a una operación binaria sobre $L$: $\Phi ((L,\bigsqcup ,\sqcap ))$ es una estructura de tipo $\tau$. Desarmada da $(L,\bigsqcup ,\sqcap )$, que es un reticulado terna; luego está en $𝒮$.

Es inyectiva. Si $\Phi ((L,\bigsqcup ,\sqcap ))=\Phi ((L^{\prime },{\bigsqcup }^{\prime },{\sqcap }^{\prime }))$, igualando coordenadas $L=L^{\prime }$ y $\{(\mathrm{s},\bigsqcup ),(\mathrm{i},\sqcap )\}=\{(\mathrm{s},{\bigsqcup }^{\prime }),(\mathrm{i},{\sqcap }^{\prime })\}$. Evaluando en $\mathrm{s}$, $\bigsqcup ={\bigsqcup }^{\prime }$; evaluando en $\mathrm{i}$, $\sqcap ={\sqcap }^{\prime }$. Luego las 3-uplas son iguales.

Es sobreyectiva sobre 𝒮. Sea $(A,i)\in 𝒮$. Entonces $(A,i(\mathrm{s}),i(\mathrm{i}))$ es un reticulado terna, y como el dominio de $i$ es $\{\mathrm{s},\mathrm{i}\}$, $i=\{(\mathrm{s},i(\mathrm{s})),(\mathrm{i},i(\mathrm{i}))\}$. Luego $\Phi ((A,i(\mathrm{s}),i(\mathrm{i})))=(A,i)$.

Por lo tanto $\Phi$ es una biyección entre el conjunto de todos los reticulados terna y el subconjunto $𝒮$ de las estructuras de tipo $\tau$, con inversa $(A,i)\mapsto (A,i(\mathrm{s}),i(\mathrm{i}))$. ∎

05 · Lo que se lleva a otros ejercicios

Base y exponente, cada uno por su lado. El exponente lo pone la aridad: $|A{|}^n$ casillas para un nombre $n$-ario. La base la pone la especie del nombre: $2$ si es de relación, $|A|$ si es de función, porque una casilla de relación decide pertenencia y una de función decide un valor. Un nombre de constante, que es elegir un elemento, aporta $|A|$. Con esas tres reglas sale cualquier conteo del estilo, como los de los Ejercicios 5 a 7 de la Guía 8.

Los nombres no obligan. Que el tipo diga $\mathrm{s}$ e $\mathrm{i}$ no hace que se interpreten como supremo e ínfimo: la suma también vale. Qué estructuras se parecen a lo que el nombre sugiere lo decide una teoría, no el tipo.

Lo que hace perder puntos. Contar $2^{81}·2^{81}$ como si $\mathrm{s}$ e $\mathrm{i}$ fueran relaciones, o ${81}^9$ dando vuelta el Lema 1. Contestar «sí» en (b) con $(A,\max ,\min )$. En (c), pedir sólo que las operaciones sean conmutativas o asociativas y olvidar las absorciones, que son las que atan una tabla con la otra. En (d), no nombrar el subconjunto o fijar el universo.

Para tener a mano

1. $\mathrm{s}$ e $\mathrm{i}$ están en $F$: se interpretan con funciones $A^2\to A$. Cada una aporta $9^{81}$; juntas, $9^{162}$.
2. Relación: base $2$. Operación: base $|A|$. El exponente, en los dos casos, es $|A{|}^{\mathrm{aridad}}$.
3. Ninguna estructura es un reticulado terna: es un par, y un reticulado terna es una 3-upla.
4. Esencialmente: $(A,i(\mathrm{s}),i(\mathrm{i}))$ cumple I1 a I7. Con tres elementos son 6 de 387 420 489.
5. La biyección: $(L,\bigsqcup ,\sqcap )\mapsto (L,\{(\mathrm{s},\bigsqcup ),(\mathrm{i},\sqcap )\})$, con universo cualquiera.