Cubrir y tapar · Lógica

Las dos palabras hablan de un elemento que está arriba de otro y suenan a lo mismo. No lo son. Cubrir es estar inmediatamente arriba: no hay nada en el medio. Tapar pide más: estar arriba, y además debajo de todo lo que está arriba. Tapar implica cubrir, al revés no, y en un poset finito la diferencia se reduce a una sola pregunta: cuántos elementos cubren al de abajo.

01 · Las dos definiciones

Las dos son de la Guía 2, sobre un poset $(P, \leq)$ y dos elementos $a, b \in P$ . Como siempre, $a < b$ abrevia $a \leq b$ y $a \neq b$ .

Cubrir. $b$ cubre a $a$ —o $a$ es cubierto por $b$ — cuando

a ≺ b ⟺ a < b y no existe z \in P con a < z < b

Tapar. $b$ tapa a $a$ —o $a$ es tapado por $b$ — cuando

a < b y b \leq c para cada c \in P tal que a < c

En un diagrama de Hasse, que $b$ cubra a $a$ es que haya una arista de $a$ hacia arriba que llega a $b$ : las aristas del diagrama son exactamente los pares que se cubren. Tapar no se ve en una arista sola, porque habla de todo lo que está arriba de $a$ , no sólo de lo que está pegado.

02 · El mismo conjunto, dos preguntas

Las dos definiciones se ordenan si se mira un solo conjunto: el de lo que está estrictamente arriba de $a$ ,

A = {c \in P : a < c}

Paso 1: cubrir es ser minimal de ese conjunto. Si $a < b$ , entonces $b \in A$ , y «no existe $z$ con $a < z < b$ » dice que ningún elemento de $A$ está estrictamente debajo de $b$ . Eso es, letra por letra, que $b$ sea un elemento minimal de $A$ .

Paso 2: tapar es ser el mínimo de ese conjunto. « $b \leq c$ para cada $c$ con $a < c$ » dice que $b$ está debajo de todos los elementos de $A$ , y $a < b$ dice que está en $A$ . Un elemento del conjunto que está debajo de todos los del conjunto es su mínimo.

Así que la diferencia entre cubrir y tapar es la diferencia entre minimal y mínimo, aplicada a lo que está arriba de $a$ . Un conjunto puede tener varios minimales y ningún mínimo; el mínimo, si existe, es único y es el único minimal. Todo lo que sigue sale de ahí.

03 · Tapar implica cubrir

Es el Ejercicio 9 de la Guía 2. La prueba usa la antisimetría y nada más.

Prueba. Supongamos que $b$ tapa a $a$ . La primera mitad de cubrir, $a < b$ , viene dada. Para la segunda, supongamos por el absurdo que hay un $z \in P$ con $a < z < b$ . Como $a < z$ , la definición de tapar aplicada a $c = z$ da $b \leq z$ . Y $z < b$ da $z \leq b$ . Por antisimetría, $z = b$ , que contradice $z < b$ . Luego no existe tal $z$ , y $a ≺ b$ . ∎

Leída desde la sección anterior es inmediata: el mínimo de un conjunto siempre es minimal.

04 · Al revés no: la V

La otra mitad del Ejercicio 9 pide un contraejemplo, y el más chico es la V: $P = {1, 2, 3}$ con $1 < 2$ , $1 < 3$ y $2$ , $3$ incomparables. El $2$ cubre al $1$ : el único otro elemento es el $3$ , y no está entre los dos. Pero no lo tapa: $1 < 3$ y $2 ≰ 3$ . Lo de arriba del $1$ es ${2, 3}$ , con dos minimales y ningún mínimo.

No es un caso raro. Contando todos los posets de hasta cinco elementos —4473 con los elementos rotulados—, hay 17 400 pares en los que un elemento cubre a otro, y en 7910 de ellos, el 45 %, lo cubre sin taparlo. Casi la mitad de las aristas de un diagrama de Hasse son de cubrir y no de tapar.

05 · En un poset finito, tapar es ser el único

Si $P$ es finito, las dos nociones se separan por un solo número:

b tapa a a ⟺ b es el único elemento que cubre a a

De izquierda a derecha. Si $b$ tapa a $a$ , lo cubre (sección 03). Si otro $c$ también cubre a $a$ , entonces $a < c$ y por tapar $b \leq c$ ; si fuera $b < c$ , $b$ estaría entre $a$ y $c$ , y $c$ no cubriría a $a$ . Luego $c = b$ . Esta mitad no usa la finitud.

De derecha a izquierda. Sea $c$ con $a < c$ ; hay que ver que $b \leq c$ . El conjunto ${z \in P : a < z \leq c}$ no es vacío —tiene a $c$ — y es finito, así que tiene un elemento minimal $m$ . Ese $m$ cubre a $a$ : si hubiera un $z$ con $a < z < m$ , ese $z$ también estaría en el conjunto y debajo de $m$ . Como el único que cubre a $a$ es $b$ , $m = b$ , y $b = m \leq c$ . ∎

Verificado sobre los 4473 posets de hasta cinco elementos: en todos, y para todo par, tapar y ser el único que cubre dan lo mismo. En la práctica es la forma rápida de contestar: se mira el diagrama de Hasse, se cuentan las aristas que salen de $a$ hacia arriba, y si es una sola, la punta de esa arista tapa a $a$ ; si son dos o más, o ninguna, nadie lo tapa.

06 · Sin finitud no alcanza

La mitad que usa la finitud de verdad la necesita. Sea $P$ formado por $a$ , $b$ y una cadena que baja sin fin, $c_{1} > c_{2} > c_{3} > \dots$ , con $a$ debajo de todos y $b$ incomparable con cada $c_{n}$ . El único que cubre a $a$ es $b$ : ningún $c_{n}$ lo cubre, porque entre $a$ y $c_{n}$ siempre está $c_{n + 1}$ . Y sin embargo $b$ no tapa a $a$ , porque $a < c_{1}$ y $b ≰ c_{1}$ . Lo que falla es el paso del minimal: el conjunto ${z : a < z \leq c_{1}}$ es la cadena entera, y no tiene minimal.

En la cadena todo elemento menos el de arriba tiene una sola arista hacia arriba, y esa punta lo tapa. En la V, el rombo y el pentágono, el de abajo tiene dos aristas hacia arriba y nadie lo tapa, aunque cualquiera de las dos puntas lo cubre. En los divisores de 12 conviven los dos casos: al $2$ lo cubren el $4$ y el $6$ y nadie lo tapa; al $3$ lo cubre sólo el $6$ , y el $6$ lo tapa: todo lo que está arriba del $3$ , el $6$ y el $12$ , está arriba del $6$ .

07 · Para qué sirve tapar: el supremo no ve la diferencia

Tapar es la noción fuerte, y por eso se puede usar en una cuenta. En un reticulado, con $s$ el supremo, es el Ejercicio 17 de la lista del primer parcial:

b tapa a a y x ≰ a ⟹ a s x = b s x

Prueba. Como $a < b$ , $a \leq b \leq b s x$ , y también $x \leq b s x$ : es una cota superior de $a$ y $x$ , así que $a s x \leq b s x$ . Para la otra desigualdad hace falta tapar. $a \leq a s x$ , y no pueden ser iguales: si $a s x = a$ , sería $x \leq a$ , contra la hipótesis. Entonces $a < a s x$ , y como $b$ tapa a $a$ , $b \leq a s x$ . Con $x \leq a s x$ , $a s x$ es cota superior de $b$ y $x$ , y $b s x \leq a s x$ . Por antisimetría, son iguales. ∎

Con cubrir no alcanza, y el rombo lo muestra: $0 < p, q < 1$ . El $p$ cubre al $0$ , y con $x = q$ —que no está debajo del $0$ — da $0 s q = q$ pero $p s q = 1$ . Verificado sobre los 425 reticulados que hay entre los posets de hasta cinco elementos: en los 3452 casos con $b$ tapando a $a$ y $x ≰ a$ , la igualdad vale siempre.

08 · Las dos, dichas con una fórmula

Las dos definiciones usan sólo $\leq$ , cuantificadores y la igualdad, así que se escriben como fórmulas del lenguaje de los posets, como pide la Guía 7. Con $x < y$ abreviando $x \leq y \land \neg (x = y)$ :

Cub (x, y) = x < y \land \neg \exists z (x < z \land z < y)

Tapa (y, x) = x < y \land \forall z (x < z \to y \leq z)

La diferencia entre las dos está en el cuantificador: cubrir niega un $\exists$ —no hay nadie en el medio— y tapar pide un $\forall$ —todos los de arriba están arriba de $y$ —. Y como las dos se dicen con fórmulas, un isomorfismo de posets las preserva y las refleja: para tapar es el Ejercicio 33 de la Guía 2, y la razón por la que alcanza con mirar la fórmula está en Decilo con una fórmula.

Para tener a mano

$a ≺ b$ ( $b$ cubre a $a$ ): $a < b$ y no hay nadie en el medio. Son las aristas del diagrama de Hasse.
$b$ tapa a $a$ : $a < b$ y $b$ está debajo de todo lo que está arriba de $a$ .
Sobre lo de arriba de $a$ : cubrir es ser minimal, tapar es ser el mínimo.
Tapar implica cubrir (Guía 2, Ejercicio 9), por antisimetría. Al revés no: en la V, el 2 cubre al 1 y no lo tapa.
En un poset finito, $b$ tapa a $a$ si y sólo si es el único que lo cubre: se cuentan las aristas hacia arriba. Sin finitud, falla.
En un reticulado, si $b$ tapa a $a$ y $x ≰ a$ , entonces $a s x = b s x$ . Con cubrir no alcanza.