Lo que sólo tiene el 14

El enunciado, textual: «De una formula elemental pura $φ$ de posets la cual tenga a $x$ como su única variable libre y la cual cumpla: $φ$ es verdadera en $({1, 2, 3, 9, 10, 14, 20}, |)$ cuando le asignamos a $x$ el elemento $e \in {1, 2, 3, 9, 10, 14, 20}$ si y solo si $e = 14$ ». Es el Ejercicio 3 (c) de la Guía 7. No hay nada que probar: hay que escribir una fórmula y mostrar que hace lo que se le pide, elemento por elemento.

01 · Antes de escribir: qué se entrega

Una fórmula, no una sentencia. Tiene que quedar exactamente una variable libre, $x$ , y todas las demás ligadas por algún cuantificador. Su valor de verdad depende entonces de qué elemento se le asigne a $x$ , y eso es lo que el enunciado mide: siete asignaciones posibles, una sola verdadera.

Pura, y de posets. El lenguaje de posets tiene $\leq$ , $=$ , los nexos y los cuantificadores. No tiene constantes, y una fórmula pura tampoco puede usar nombres de elementos fijos. O sea que el 14 no se puede nombrar: $x = 14$ ni siquiera es una fórmula del lenguaje. Lo único que se puede decir de $x$ es cómo está ubicado en el orden. Y en esta estructura el $\leq$ se interpreta como «divide».

Una estructura fija. La fórmula tiene que andar en este poset y en ningún otro. No hace falta que «diga» algo con sentido general: alcanza con que separe al 14 de los otros seis acá. Eso afloja mucho el problema, y es lo que permite atacarlo mirando un dibujo.

El «si y solo si» son dos cosas a verificar: que $φ$ sea verdadera cuando $x$ vale 14, y que sea falsa en cada uno de los otros seis. Una fórmula que es verdadera en el 14 y también en el 9 no resuelve nada.

02 · Las herramientas

Las cláusulas de fórmula elemental de posets de la Guía 7: las atómicas $(t = s)$ y $(t \leq s)$ , con $t$ y $s$ variables; y si $φ_{1}$ y $φ_{2}$ son fórmulas, también lo son $(φ_{1} \land φ_{2})$ , $(φ_{1} \lor φ_{2})$ , $(φ_{1} \to φ_{2})$ , $(φ_{1} \leftrightarrow φ_{2})$ , $\neg φ_{1}$ , $\forall y φ_{1}$ y $\exists y φ_{1}$ . La lista permite abreviar $\neg (y = z)$ como $y \neq z$ , y conviene una abreviatura más, que no es un símbolo del lenguaje sino un atajo de lectura:

y < x abrevia (y \leq x \land y \neq x)

Y dos fórmulas del Ejercicio 1 de la Guía 7, que sirven de ladrillos. « $x$ es maximal»: $\forall y (x \leq y \to x = y)$ , nada está estrictamente arriba de $x$ . « $x$ es minimal»: $\forall y (y \leq x \to y = x)$ . Lo que se traduce en este ejercicio es la misma operación que se practica en decilo con una fórmula: escribir algo cuya columna de verdades coincida con la de la propiedad.

03 · La mariposa: el dibujo primero

Sin el diagrama de Hasse no se ve nada. El 1 divide a todos y va abajo. Encima, el 2 y el 3. El 2 divide al 10, al 14 y al 20; el 3, sólo al 9; el 10 divide al 20. Los cubrimientos son seis:

1 < 2 1 < 3 2 < 10 2 < 14 3 < 9 10 < 20

Con el dibujo a la vista, la pregunta es qué tiene el 14 que no tenga nadie más. Conviene hacerla en orden, empezando por lo más grueso.

Primera pregunta: ¿qué se ve del 14 a primera vista? Está arriba de todo: no divide a nadie más. Es maximal. Pero el 9 y el 20 también, así que la cláusula « $x$ es maximal» descarta al 1, al 2, al 3 y al 10, y deja tres candidatos. Hace falta algo que separe al 14 del 9 y del 20.

Segunda pregunta: ¿qué tienen el 9 y el 20 que el 14 no? Mirá lo que está debajo de cada uno. Debajo del 9 está el 3, y por encima del 3 no hay nadie más que el 9: el 3 es un elemento propio del 9. Lo mismo el 10 para el 20: por encima del 10 sólo está el 20. Debajo del 14, en cambio, están el 1 y el 2, y los dos tienen a otros por encima: el 2 está debajo del 10 y del 20. El 14 no tiene nada propio.

Tercera pregunta: ¿cómo se escribe? «Todo lo que está estrictamente debajo de $x$ está también estrictamente debajo de algún otro»:

\forall y (y < x \to \exists z (y < z \land z \neq x))

El $z \neq x$ es la mitad de la idea. Sin él, el $z$ que pide el $\exists$ puede ser el mismo $x$ , que siempre está arriba de lo que está debajo suyo, y la cláusula pasa a ser verdadera en los siete elementos.

El otro camino, y por qué no alcanza solo. Lo primero que uno prueba es contar: el 14 tiene dos elementos estrictamente debajo, el 1 y el 2. Pero el 9 también tiene dos —el 1 y el 3— y el 10 también. Contar separa al 20, que tiene tres, y deja al 9 pegado al 14. Para despegarlos hay que volver a mirar a quién tienen debajo, que es la segunda pregunta otra vez. Casi nunca la primera propiedad que se prueba separa al elemento buscado: cada cláusula se agrega para romper un empate concreto, y el widget de abajo deja hacerlo a mano.

Con «maximal» y «nada propio debajo» la conjunción queda verdadera sólo en el 14. Hay otro par que también aísla: «maximal» y «cubre a uno que tiene otro arriba», que es la misma idea dicha con cubrimientos. De las siete cláusulas del panel, ésos son los dos únicos pares que lo logran; ninguna sola alcanza. Y la versión sin $z \neq x$ no descarta a nadie: es verdadera en los siete.

04 · El escarabajo: la fórmula y su verificación

La fórmula. Escrita sin el atajo $<$ , con las abreviaturas que permite la lista:

φ = (\forall y (x \leq y \to x = y) \land \forall y ((y \leq x \land y \neq x) \to \exists z ((y \leq z \land y \neq z) \land z \neq x)))

Es elemental de posets: sólo usa $\leq$ , $=$ , nexos y cuantificadores. Es pura: no aparece ningún nombre de elemento fijo. Su única variable libre es $x$ : la $y$ del primer conjunto está ligada por su $\forall y$ , la del segundo por el otro $\forall y$ , y la $z$ por el $\exists z$ . Que las dos $y$ se llamen igual no es un problema, porque sus alcances no se tocan.

La verificación. El primer conjunto dice « $x$ es maximal»; el segundo, «nada de lo que está estrictamente debajo de $x$ es propio de $x$ ». Elemento por elemento, con el testigo de cada falso:

x	maximal	nada propio debajo	φ
1	F: 1 \| 2 y 1 ≠ 2	V: nada está debajo del 1	F
2	F: 2 \| 10	V: 1 \| 3	F
3	F: 3 \| 9	V: 1 \| 2	F
9	V	F: sobre el 3 sólo está el 9	F
10	F: 10 \| 20	V: 1 \| 3, 2 \| 14	F
14	V	V: 1 \| 3, 2 \| 10	V
20	V	F: sobre el 10 sólo está el 20	F

Las casillas que deciden, escritas como se entregan:

Con $x$ en 1, 2, 3 o 10, el primer conjunto es falso. Tomando $y$ como 2, 10, 9 y 20 respectivamente, $x \leq y$ es verdadera (1 divide a 2, 2 a 10, 3 a 9, 10 a 20) y $x = y$ es falsa. La implicación falla, así que el $\forall y$ es falso, y con él la conjunción.
Con $x$ en 9, el segundo conjunto es falso. Tomando $y$ como 3, el antecedente $(3 \leq 9 \land 3 \neq 9)$ es verdadero. Para el consecuente haría falta un $z$ con $3 \leq z$ , $3 \neq z$ y $z \neq 9$ ; pero los múltiplos de 3 en el conjunto son el 3 y el 9, y los dos quedan excluidos. El $\exists z$ es falso, la implicación también, y el $\forall y$ cae.
Con $x$ en 20, el segundo conjunto es falso. Tomando $y$ como 10: $10 \leq 20$ y $10 \neq 20$ , y los múltiplos de 10 en el conjunto son el 10 y el 20. No hay $z$ que sirva.
Con $x$ en 14, los dos conjuntos son verdaderos. El 14 no divide a ningún otro elemento del conjunto, así que para todo $y$ , si $14 \leq y$ entonces $y = 14$ : es maximal. Para el segundo, los $y$ con $y \leq 14$ e $y \neq 14$ son el 1 y el 2. Para $y$ igual a 1, tomando $z$ como 3: $1 \leq 3$ , $1 \neq 3$ y $3 \neq 14$ . Para $y$ igual a 2, tomando $z$ como 10: $2 \leq 10$ , $2 \neq 10$ y $10 \neq 14$ . Para cualquier otro $y$ el antecedente es falso y la implicación es verdadera.

Luego $φ$ es verdadera en $({1, 2, 3, 9, 10, 14, 20}, |)$ asignándole a $x$ el elemento $e$ si y solo si $e = 14$ . ∎

05 · Lo que se lleva a otros ejercicios

La receta. Dibujar el Hasse; filtrar con la propiedad más gruesa que tenga el elemento buscado; y por cada empate que quede, preguntar qué tiene el otro que el buscado no, y agregar una cláusula que lo diga. Sirve igual para los incisos (a) y (b) del mismo ejercicio de la guía y para los Ejercicios 20 y 21 de la lista, que cambian de tipo pero no de método. Y si el tipo trae constantes, todavía no se las puede usar para nombrar al elemento buscado de cualquier manera: hay que ver qué permite el lenguaje.

Lo que hace perder puntos. Escribir el 14, o cualquier otro número, dentro de la fórmula: no es un término de posets. Dejar una variable libre además de $x$ , que convierte la fórmula en otra cosa: su verdad pasaría a depender de un valor que nadie asignó. Verificar sólo que es verdadera en el 14 y no mirar los otros seis, que es la mitad del «si y solo si». Y olvidar el $z \neq x$ , que es la diferencia entre una cláusula que separa y una que vale en todo el poset. Acá no se usa ningún resultado de guía, pero la regla de la cátedra sigue valiendo: si en la justificación se cita uno, hay que enunciarlo y probarlo aparte.

Para tener a mano

Pura y de posets: el 14 no se puede nombrar. Hay que encontrarle una propiedad de orden que sólo tenga él, en esta estructura.
Maximal deja al 9, al 14 y al 20. Contar menores deja al 9, al 10 y al 14. Ninguna cláusula sola alcanza.
El 9 y el 20 tienen algo propio debajo (el 3 y el 10). El 14 no: el 1 y el 2 tienen a otros arriba.
$φ = (\forall y (x \leq y \to x = y) \land \forall y (y < x \to \exists z (y < z \land z \neq x)))$ , con $y < x$ abreviando $(y \leq x \land y \neq x)$ .
Se verifica en los siete elementos, con el testigo de cada falso. Sin el $z \neq x$ la segunda cláusula vale en todos.