Ninguna estructura es un poset

El enunciado, textual: «Sea $\tau =(\varnothing ,\varnothing ,\{\le \},\{(\le ,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 poset?
3. De una biyección entre el conjunto formado por todos los posets y un subconjunto del conjunto de todas las estructuras de tipo $\tau$».

Es el primero de tres ejercicios hechos con el mismo molde: el 18 lo repite con el tipo de los grafos bicoloreados y el 19 con el de los reticulados terna. El Lema 1 y la idea de la biyección son los mismos en los tres.

01 · Antes de resolver: tres preguntas de tres especies

Los tres incisos piden cosas de naturaleza distinta, y conviene separarlas antes de escribir nada.

(a) pide un número. El universo está fijo: es $\{1,\dots ,9\}$ y no otro. Lo que varía es todo lo demás que hace falta para tener una estructura, y hay que ver qué es eso.

(b) pide un sí o un no, y es no. La tentación es contestar «sí, la del orden usual» o «sí, la de la divisibilidad». Esas estructuras existen, pero no son posets: son esencialmente posets. El inciso pregunta por la identidad estricta, y la diferencia entre ser y ser esencialmente es todo lo que la Guía 8 quiere que se vea acá.

(c) pide una función, y que se diga cuál es su codominio. No alcanza con «una biyección entre los posets y algunas estructuras»: hay que nombrar el subconjunto, definir la función, y probar que es biyectiva sobre él. Y hay un cambio de escenario que se lee rápido y se pierde: el universo ya no está fijo. El dominio son todos los posets, con cualquier conjunto de base.

02 · Las herramientas

El tipo. Un tipo es una 4-upla $\tau =(C,F,R,a)$: nombres de constante, de función, de relación, y la aridad de cada nombre de función o de relación. Acá $C=F=\varnothing$, $R=\{\le \}$ y $a(\le )=2$. El símbolo $\le$ es una palabra, un nombre de relación binaria. No dice nada de cómo se lo va a interpretar: la Guía 8 lo llama «el tipo de los posets» por la intención, no porque obligue a algo.

La estructura de tipo τ, con la definición de la Guía 8: un par $(A,i)$ tal que $A$ es un conjunto no vacío —el universo— e $i$ es una función con dominio $C\cup F\cup R$ que manda cada nombre de constante a un elemento de $A$, cada nombre de función $n$-aria a una operación $n$-aria sobre $A$, y cada nombre de relación $n$-aria a una relación $n$-aria sobre $A$. Con este $\tau$ queda poco: $i$ tiene dominio $\{\le \}$ e $i(\le )\subseteq A^2$. O sea que, como conjunto,

$$i=\{(\le ,i(\le ))\}$$

un conjunto con un solo elemento: el par ordenado cuya primera coordenada es la palabra $\le$ y cuya segunda es una relación binaria cualquiera sobre $A$.

El poset. Un par $(P,⊑)$ con $P$ un conjunto no vacío y $⊑$ un orden parcial sobre $P$: un subconjunto de $P^2$ reflexivo, antisimétrico y transitivo. Lo escribimos con $⊑$ y no con $\le$ sólo para no confundir el orden de un poset con el nombre $\le$ del tipo, que es otra cosa.

Esencialmente. La Guía 8 lo explica con un ejemplo: la estructura $(\mathbb{N},i)$ con $i(\le )=\{(x,y)\in {\mathbb{N}}^2:x\mid y\}$ «estrictamente hablando no es un poset», pero «a nivel de información» es lo mismo que $(\mathbb{N},\mid )$. Las estructuras de tipo $\tau$ en las que $\le$ se interpreta como un orden parcial sobre el universo son las que llama esencialmente posets. Son exactamente los modelos de la teoría elemental de los posets: las estructuras que hacen verdaderas las tres sentencias elementales A≤R, A≤A y A≤T.

El Lema 1 de la Guía 8, que el enunciado deja usar. Igual se enuncia, y la prueba es corta.

(1) Dados $A$, $B$ conjuntos finitos no vacíos, hay $|B{|}^{|A|}$ funciones con dominio $A$ e imagen contenida en $B$.

(2) Si $A$ es un conjunto finito, entonces hay $2^{|A|}$ subconjuntos de $A$.

Prueba de (1). Sea $A=\{a_1,\dots ,a_n\}$ con $n=|A|$, y sea $\mathrm{Fu}$ el conjunto de las funciones con dominio $A$ e imagen contenida en $B$. La función

$$\mathrm{Fu}\to B^n,f\mapsto (f(a_1),\dots ,f(a_n))$$

es biyectiva. Es inyectiva: si $f$ y $g$ dan la misma $n$-upla, coinciden en cada $a_k$, y como tienen el mismo dominio son la misma función. Es sobreyectiva: dada $(b_1,\dots ,b_n)\in B^n$, la función $\{(a_1,b_1),\dots ,(a_n,b_n)\}$ tiene dominio $A$, imagen contenida en $B$, y va a parar a esa $n$-upla. Luego $|\mathrm{Fu}|=|B^n|=|B{|}^n$.

Prueba de (2). A cada $S\subseteq A$ le corresponde su función característica ${\chi }_S:A\to \{0,1\}$, que vale $1$ en los elementos de $S$ y $0$ en los demás. Eso es una biyección entre los subconjuntos de $A$ y las funciones de $A$ en $\{0,1\}$: su inversa manda $f$ a $\{a\in A:f(a)=1\}$. Por (1) hay $2^{|A|}$ de esas funciones. (Si $A=\varnothing$, (1) no aplica, pero se ve a mano: el único subconjunto es $\varnothing$, y $2^0=1$.)

03 · La mariposa

Para (a): ¿qué hay que elegir para tener una estructura? El universo ya está elegido. Queda $i$, y de $i$ hay que elegir un solo valor, $i(\le )$, que puede ser cualquier subconjunto de $A^2$. Una estructura con universo $\{1,\dots ,9\}$ es, entonces, lo mismo que un subconjunto de $\{1,\dots ,9{\}}^2$. Hay que dibujarlo: una grilla de $9\times 9$, una casilla por par ordenado, y cada casilla encendida o apagada. Son $81$ casillas y dos opciones en cada una, independientes. Es el Lema 1 (2) con $A^2$ en lugar de $A$:

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

Son 2 417 851 639 229 258 349 412 352, veinticinco cifras. Se deja escrito como potencia: el número decimal no agrega nada.

Para (b): poner las dos formas una al lado de la otra.

$$\text{estructura: }(A,\{(\le ,S)\}),\text{ con }S\subseteq A^2$$ $$\text{poset: }(P,⊑),\text{ con }⊑\subseteq P^2$$

Las dos son pares, y la primera coordenada es un conjunto en las dos. La diferencia está en la segunda. La de un poset es una relación sobre $P$: un conjunto de pares de elementos de $P$, y si es reflexiva, tiene por lo menos $|P|$ elementos. La de una estructura es la función $i$, que tiene un solo elemento, y ese elemento es un par cuya primera coordenada es la palabra $\le$, no un número. Para que $(\{1,\dots ,9\},i)$ fuera un poset, $i$ tendría que contener los nueve pares $(1,1),\dots ,(9,9)$. No entran nueve cosas distintas en un conjunto de una.

Lo que sí hay es estructuras que, desarmadas, dan un poset. Si $i(\le )$ es la divisibilidad sobre $\{1,\dots ,9\}$, el par $(\{1,\dots ,9\},i(\le ))$ es un poset y $(\{1,\dots ,9\},i)$ es esencialmente un poset.

Para (c): armar y desarmar. La palabra «esencialmente» ya sugiere la función. Dado un poset $(P,⊑)$, se arma la estructura con el mismo universo cuya $i$ le asigna al nombre $\le$ el orden $⊑$. Al revés, dada una estructura, se desarma $i$ evaluándola en $\le$. Lo que vuelve de desarmar es un poset sólo si $i(\le )$ era un orden parcial, y por eso la biyección no es con todas las estructuras: es con las esencialmente posets. Ése es el subconjunto que hay que nombrar.

¿Cuántas de las $2^{n^2}$ son esencialmente posets? En universos chicos se puede contar entero. Recorridas una por una, evaluando en cada una los tres axiomas como fórmulas:

La columna del medio es la fórmula, y el recorrido la reproduce en los cinco casos. La de la derecha no tiene una fórmula cerrada: es la cantidad de órdenes parciales sobre un conjunto de $n$ elementos rotulados. Ya con cinco elementos es una de cada ocho mil. Con nueve, el ejercicio no pide el número y no hace falta: alcanza con saber que el subconjunto es una parte ínfima del total.

La fila de ceros y unos de abajo es la función característica de $i(\le )$, leída casilla por casilla: es la biyección del Lema 1 hecha visible, y por eso hay exactamente tantas estructuras como palabras de $n^2$ dígitos binarios. La lectura «¿es un poset?» dice que no en todas, incluso cuando la de al lado dice que sí.

04 · El escarabajo

(a) Sea $A=\{1,\dots ,9\}$. Una estructura de tipo $\tau$ con universo $A$ es un par $(A,i)$ con $i$ una función de dominio $\{\le \}$ tal que $i(\le )\subseteq A^2$; o sea, $i=\{(\le ,S)\}$ con $S\subseteq A^2$. La correspondencia $(A,\{(\le ,S)\})\mapsto S$ es una biyección entre esas estructuras y los subconjuntos de $A^2$: dos pares ordenados son iguales sii coinciden coordenada a coordenada, así que estructuras distintas tienen $S$ distintos, y todo $S\subseteq A^2$ da una estructura. Por el Lema 1 (2), hay $2^{|A^2|}$ subconjuntos de $A^2$, y $|A^2|=9·9=81$. Luego hay $2^{81}$ estructuras de tipo $\tau$ con universo $A$.

(b) No, ninguna. Sea $(A,i)$ una estructura de tipo $\tau$ con universo $A=\{1,\dots ,9\}$. Si fuera un poset, $i$ sería un orden parcial sobre $A$, en particular una relación reflexiva, y entonces $(1,1),(2,2),\dots ,(9,9)\in i$: $i$ tendría al menos nueve elementos. Pero $i$ es una función con dominio $\{\le \}$, así que tiene exactamente un elemento, el par $(\le ,i(\le ))$. Absurdo. Lo que sí hay son estructuras esencialmente posets, es decir con $i(\le )$ un orden parcial sobre $A$; por ejemplo, la de $i(\le )=\{(x,y)\in A^2:x\mid y\}$, que es reflexiva ($x\mid x$), antisimétrica (si $x\mid y$ e $y\mid x$ con $x,y\ge 1$, entonces $x=y$) y transitiva (si $x\mid y$ e $y\mid z$, entonces $x\mid z$).

(c) Sea $𝒮$ el conjunto de las estructuras $(A,i)$ de tipo $\tau$ tales que $i(\le )$ es un orden parcial sobre $A$, o sea, de las estructuras de tipo $\tau$ que son esencialmente posets. Para cada poset $(P,⊑)$ definamos

$$\Phi ((P,⊑))=(P,\{(\le ,⊑)\})$$

Está bien definida y cae en 𝒮. Si $(P,⊑)$ es un poset, $P$ es no vacío y $⊑\subseteq P^2$, así que $\{(\le ,⊑)\}$ es una función con dominio $\{\le \}=C\cup F\cup R$ que manda el nombre de relación binaria $\le$ a una relación binaria sobre $P$: $\Phi ((P,⊑))$ es una estructura de tipo $\tau$. Y como su interpretación de $\le$ es $⊑$, que es un orden parcial sobre $P$, está en $𝒮$.

Es inyectiva. Si $\Phi ((P,⊑))=\Phi ((Q,{⊑}^{\prime }))$, entonces $(P,\{(\le ,⊑)\})=(Q,\{(\le ,{⊑}^{\prime })\})$. Igualando coordenadas, $P=Q$ y $\{(\le ,⊑)\}=\{(\le ,{⊑}^{\prime })\}$; evaluando esa función en $\le$, $⊑={⊑}^{\prime }$. Luego $(P,⊑)=(Q,{⊑}^{\prime })$.

Es sobreyectiva sobre 𝒮. Sea $(A,i)\in 𝒮$. Entonces $A$ es no vacío e $i(\le )$ es un orden parcial sobre $A$, así que $(A,i(\le ))$ es un poset. Como el dominio de $i$ es $\{\le \}$, $i=\{(\le ,i(\le ))\}$, y por lo tanto $\Phi ((A,i(\le )))=(A,\{(\le ,i(\le ))\})=(A,i)$.

Luego $\Phi$ es una biyección entre el conjunto de todos los posets y el subconjunto $𝒮$ del conjunto de todas las estructuras de tipo $\tau$. Su inversa es $(A,i)\mapsto (A,i(\le ))$. ∎

05 · Lo que se lleva a otros ejercicios

La receta de conteo. Con el universo fijo, una estructura es una elección de $i(p)$ para cada nombre $p$ del tipo, y las elecciones son independientes, así que se multiplican. Lo que aporta cada nombre depende sólo de su especie y de su aridad. Con $|A|=m$:

• un nombre de constante: un elemento de $A$, $m$ opciones;
• un nombre de función $n$-aria: una función de $A^n$ en $A$, $m^{m^n}$ opciones, por el Lema 1 (1);
• un nombre de relación $n$-aria: un subconjunto de $A^n$, $2^{m^n}$ opciones, por el Lema 1 (2).

El Ejercicio 18 agrega una relación unaria, que aporta $2^9$ y no $2^{81}$; el 19 cambia relaciones por operaciones, y la base pasa de $2$ a $9$.

La biyección es siempre la misma. Armar $i$ con las coordenadas de la tupla, una por nombre; desarmarla evaluando en cada nombre. El subconjunto es el de las estructuras esencialmente de esa clase, que son los modelos de su teoría elemental.

Lo que hace perder puntos. Contestar «sí» en (b) mostrando una estructura esencialmente poset. Dar en (c) una función sin decir cuál es el subconjunto, o sin probar que es biyectiva sobre él. Fijar en (c) el universo en $\{1,\dots ,9\}$, que deja afuera casi todos los posets. Confundir $2^{81}$ con ${81}^2$ o con $2^9$. Y usar el Lema 1 sin enunciarlo: el enunciado lo permite, pero la regla de la cátedra es que un resultado de una guía se enuncia, y probarlo son tres renglones.

Para tener a mano

1. Con este $\tau$, una estructura es $(A,\{(\le ,S)\})$ con $S\subseteq A^2$. Con $A$ fijo, elegir la estructura es elegir $S$: hay $2^{81}$.
2. Lema 1: $|B{|}^{|A|}$ funciones de $A$ en $B$; $2^{|A|}$ subconjuntos de $A$, por la función característica.
3. Ninguna estructura es un poset: $i$ tiene un solo elemento, y un orden reflexivo sobre nueve elementos tiene nueve pares por lo menos.
4. Esencialmente poset: $i(\le )$ es un orden parcial sobre el universo. Son los modelos de A≤R, A≤A y A≤T.
5. La biyección: $(P,⊑)\mapsto (P,\{(\le ,⊑)\})$, sobre el subconjunto de las esencialmente posets, con universo cualquiera. La inversa desarma $i$.