El tercero no puede ser el primero

El enunciado, textual: «De una prueba elemental de posets de la sentencia elemental pura de posets:

». Es el Ejercicio 17 (d) de la Guía 7, pasado a la lista. Una prueba elemental de posets parte de un poset $(P,\le )$ fijo pero arbitrario, del que lo único que se sabe es que cumple los tres axiomas de poset, y avanza en pasos simples, cada uno justificado en una frase.

01 · Antes de probar: qué dice cada lado

El antecedente, $\forall x\exists y(\neg (x=y)\wedge x\le y)$, dice que todo elemento tiene otro, distinto, por encima. O sea: nadie es maximal. El consecuente, $\exists x\exists y\exists z(\neg (x=y)\wedge \neg (x=z)\wedge \neg (y=z))$, dice que hay tres elementos distintos de a pares. No habla del orden: sólo cuenta, y dice que el universo tiene al menos tres.

La sentencia entera es una implicación entre dos sentencias. No hay ningún $\forall$ por fuera que abarque a las dos, así que la prueba no empieza con «sean fijos pero arbitrarios» ni termina generalizando: se supone el antecedente y se fabrica el consecuente.

Y hay una trampa para quien quiera dibujar. Todo poset finito tiene un elemento maximal, así que en ningún dibujo finito se cumple el antecedente. Medido sobre todos los posets con rótulos de uno a cuatro elementos —son 1, 3, 19 y 219—: el antecedente no se cumple en ninguno. En todos ellos la sentencia es verdadera porque su antecedente es falso. Los posets donde el antecedente vale son infinitos, como $(\mathbb{N},\le )$, y ésos no se dibujan enteros. La prueba es la única manera de verlos.

02 · Las herramientas

Los axiomas elementales de posets son tres; los nombres son los que la Guía 7 usa en la lista de cuaterna:

• A≤R, reflexiva: $\forall x(x\le x)$.
• A≤T, transitiva: $\forall x\forall y\forall z((x\le y\wedge y\le z)\to x\le z)$.
• A≤A, antisimétrica: $\forall x\forall y((x\le y\wedge y\le x)\to x=y)$.

Además, un poset tiene universo no vacío: es parte de la definición de estructura, y es lo que deja nombrar el primer elemento. Las otras dos herramientas son las dos caras de un existencial. Para usar uno que ya se tiene, se le pone nombre a un testigo: «sea $b$ tal que …». Para probar uno, se exhiben los testigos. Esta prueba hace las dos cosas: los testigos que pide el consecuente son los mismos que entrega el antecedente.

03 · La mariposa: subir, y no volver

De atrás para adelante: hacen falta tres nombres de elementos distintos. ¿De dónde salen? El tipo de los posets no tiene constantes, así que los nombres sólo pueden salir de dos lugares: del universo, que no es vacío y da un primer elemento $a$, y del antecedente, que a cada elemento le da otro.

El camino que no sale. Preguntarle dos veces al antecedente por $a$. Da un $b$ arriba de $a$ y un $b^{\prime }$ arriba de $a$, los dos distintos de $a$. Pero nada dice que sean distintos entre sí: en $(\mathbb{N},\le )$, con $a=0$, los dos pueden ser $1$. El antecedente promete uno arriba de cada elemento, nunca dos arriba del mismo.

El camino que sale: subir. Del antecedente en $a$ sale $b$, con $\neg (a=b)$ y $a\le b$. Del antecedente en $b$ sale $c$, con $\neg (b=c)$ y $b\le c$. Dos de las tres desigualdades vienen gratis, una con cada testigo. Falta $\neg (a=c)$, y ahí está el ejercicio entero.

Porque tres nombres no son tres elementos. Cada elección da un nombre nuevo, y nada impide, por ahora, que $c$ nombre lo mismo que $a$: subir de $b$ y caer de vuelta en el punto de partida. ¿Qué haría falta para eso? Si $c=a$, entonces $b\le c$ dice $b\le a$. Y ya teníamos $a\le b$. Son dos puntos distintos que se miran los dos, y A≤A dice que entonces son el mismo: $a=b$, contra $\neg (a=b)$. El tercero no puede ser el primero.

Dos detalles de la mariposa. No hizo falta A≤T: $b\le a$ sale de $b\le c$ reemplazando $c$ por $a$, sin pasar por ningún intermedio. Y A≤R tampoco aparece. De los tres axiomas, la prueba usa uno, una vez.

Con dos puntos, la única forma de que los dos tengan a alguien arriba es poner las dos flechas, y ahí la cadena vuelve: $c$ cae en $a$. Contado sobre las 16 relaciones de dos elementos, la sentencia falla en exactamente 4: las que tienen las dos flechas, con cualquier diagonal. Ninguna de las 4 es antisimétrica, y una de ellas —la completa— es reflexiva y transitiva: A≤R y A≤T no la pueden descartar. Con tres puntos o más la sentencia no falla nunca —0 de 512, 0 de 65 536—, porque el consecuente ya es verdadero.

Con tres puntos el antecedente sí se puede cumplir sin romper A≤A: con el ciclo $1\le 2\le 3\le 1$, en cualquiera de sus dos sentidos. De las 512 relaciones de tres elementos, 16 son antisimétricas y cumplen el antecedente, y son exactamente esos dos ciclos con sus ocho diagonales. Ninguna es transitiva. Eso dice cuánto compra cada axioma: A≤A solo alcanza para tres elementos, y no para cuatro.

04 · El escarabajo: la prueba escrita

Prueba. Sea $(P,\le )$ un poset fijo pero arbitrario, del cual sólo sabemos que satisface los axiomas elementales de posets. Supongamos

$$\forall x\exists y(\neg (x=y)\wedge x\le y)$$

Ya que $P$ es no vacío, sea $a\in P$.

Lo supuesto, tomando $x$ como $a$, nos dice que $\exists y(\neg (a=y)\wedge a\le y)$. Sea $b\in P$ tal que $\neg (a=b)\wedge a\le b$.

Lo supuesto, tomando $x$ como $b$, nos dice que $\exists y(\neg (b=y)\wedge b\le y)$. Sea $c\in P$ tal que $\neg (b=c)\wedge b\le c$.

Veamos que $\neg (a=c)$. Supongamos, por el absurdo, que $a=c$. Ya que se da $b\le c$, reemplazando $c$ por $a$ obtenemos $b\le a$. Ya que también se da $a\le b$, se da $(a\le b\wedge b\le a)$. El axioma A≤A, tomando $x$ como $a$ e $y$ como $b$, nos dice que $((a\le b\wedge b\le a)\to a=b)$, por lo cual se da $a=b$. Pero se da $\neg (a=b)$, lo cual es una contradicción. Luego se da $\neg (a=c)$.

Cierre. Se dan $\neg (a=b)$, $\neg (a=c)$ y $\neg (b=c)$, o sea $(\neg (a=b)\wedge \neg (a=c)\wedge \neg (b=c))$. Tomando $a$, $b$ y $c$ como testigos, se da

$$\exists x\exists y\exists z(\neg (x=y)\wedge \neg (x=z)\wedge \neg (y=z))$$

Hemos probado que, si se da el antecedente, se da el consecuente; o sea, vale la sentencia del enunciado. ∎

Al final no se generaliza, y por dos razones. La sentencia no empieza con un $\forall$: es una implicación entre sentencias. Y aunque empezara, $b$ y $c$ no son arbitrarios: salieron de dos elecciones, y sobre un testigo elegido no se generaliza nunca. Acá los testigos no se fabrican, como en El testigo lo construís vos: te los da el antecedente, y se los pasás al consecuente tal cual.

05 · Lo que se lleva a otros ejercicios

Encadenar testigos. Cuando un $\forall \exists$ tiene que dar varios elementos, no se lo interroga varias veces sobre el mismo punto: se lo aplica al testigo anterior. Cada eslabón es distinto del de al lado gratis; lo que cuesta son los que no se tocan.

Un elemento más, un axioma más. Si el consecuente pidiera cuatro, la cadena seguiría a un $d$ arriba de $c$. $\neg (d=b)$ sale igual que antes, con A≤A. Pero $\neg (d=a)$ necesita $c\le a$ y $a\le c$, y la segunda sólo sale encadenando $a\le b$ con $b\le c$: ahí entra A≤T. Los ciclos de tres puntos de la sección anterior son justo el contraejemplo que tiene A≤A y le falta A≤T.

El ejercicio de al lado. El 11 de la lista también es de posets y también habla de maximales, pero ahí la jugada es otra: una cota común convierte al maximal en máximo. Está resuelto en Alcanza con una cota, y la idea detrás, en Maximal no es máximo.

Lo que hace perder puntos. Dar por hecho que $a$, $b$ y $c$ son distintos porque tienen nombres distintos: es saltear el único paso que el ejercicio evalúa. Generalizar al final sobre testigos elegidos. Arrancar sin decir de dónde sale $a$. Y citar «un poset sin maximales es infinito»: es verdad, pero es un resultado, y la regla de la cátedra dice que si se usa un resultado de alguna guía hay que enunciarlo y probarlo por separado. Probarlo cuesta más que el ejercicio.

Para tener a mano

1. El antecedente dice «nadie es maximal»; el consecuente, «hay al menos tres elementos». Ningún poset finito cumple el antecedente.
2. Es una implicación entre sentencias: se supone el antecedente, se fabrica el consecuente, y no se generaliza.
3. Subir: $a$ del universo no vacío, $b$ arriba de $a$, $c$ arriba de $b$. Dos desigualdades vienen con los testigos.
4. La tercera, $\neg (a=c)$, por el absurdo: $c=a$ da $b\le a$, y con $a\le b$, A≤A da $a=b$.
5. Usa sólo A≤A. Sin ella falla en dos puntos que se miran; para cuatro elementos haría falta también A≤T.