Al 3 lo delata el 6

El enunciado, textual: «Sea $\tau =(\varnothing ,\varnothing ,\{\mathrm{rel}\},\{(\mathrm{rel},2)\})$. Sea $A=(A,i)$, con $A=\{\mathrm{1,3},\mathrm{5,6},30\}$ y

$$i(\mathrm{rel})=\{(i,j)\in A^2:\text{i divide a j}\}$$

(a) Dé una fórmula $\phi$ elemental pura de tipo $\tau$ la cual tenga como su única variable libre a $x$ y la cual sea verdadera en $A$ cuando asignamos a $x$ el valor $i\in A$ si y sólo si $i=1$». Los incisos (b), (c), (d) y (e) piden lo mismo para $i=3$, $i=5$, $i=6$ e $i=30$.

01 · Antes de resolver: qué hay en el lenguaje

El tipo tiene un solo símbolo: la relación binaria $\mathrm{rel}$. No hay constantes ni funciones, así que los únicos términos puros son las variables. Las fórmulas atómicas son $(t=s)$ y $\mathrm{rel}(t,s)$ con $t$ y $s$ variables, y de ahí para arriba, conectivos y cuantificadores.

«Pura» quiere decir sin nombres de elementos fijos. Ésa es toda la dificultad: no se puede escribir $x=3$, porque en el lenguaje no hay ningún 3. Lo único que una fórmula puede decir de $x$ es cómo se relaciona con los demás por $\mathrm{rel}$. O sea: hay que describir a cada elemento por su lugar, sin decir su nombre.

Lo que se entrega son cinco fórmulas, cada una con $x$ como única variable libre: toda variable auxiliar tiene que quedar ligada por un cuantificador. Y «si y sólo si» pide dos cosas por fórmula: que sea verdadera en su elemento y falsa en los otros cuatro. La segunda mitad es la que se olvida.

02 · Las herramientas

Sólo la definición de verdad de la Guía 8, aplicada a esta estructura. Con una asignación que le da a cada variable un valor en $A$:

• $\mathrm{rel}(t,s)$ es verdadera cuando el valor de $t$ divide al valor de $s$; $(t=s)$, cuando los dos valores coinciden.
• $\neg \psi$, $(\psi \wedge \theta )$ y $(\psi \to \theta )$ se evalúan como siempre.
• $\forall y\psi$ es verdadera cuando $\psi$ lo es para todo valor de $A$ que se le dé a $y$, dejando las otras variables como estaban; $\exists y\psi$, cuando lo es para alguno.

Y las abreviaturas que la lista permite: $z\ne x$ en lugar de $\neg (z=x)$, y paréntesis de menos cuando no hay ambigüedad. Un detalle que se usa todo el tiempo: la negación y los cuantificadores no agregan paréntesis, así que en $\neg \forall y\mathrm{rel}(x,y)\wedge \psi$ la negación alcanza sólo a $\forall y\mathrm{rel}(x,y)$.

03 · La mariposa: mirar el dibujo

Lo primero es la tabla de la relación, que en este caso es un orden: la divisibilidad sobre $A$ es reflexiva, antisimétrica y transitiva. Su diagrama de Hasse tiene al $1$ abajo de todo, al $30$ arriba de todo, y en el medio dos caminos: $1,3,6,30$ por un lado, y $1,5,30$ por el otro.

De cada elemento, lo que tiene propio debajo y propio arriba (propio quiere decir distinto de él):

Los fáciles. El $1$ es el único que divide a todos: su fila de la tabla de $\mathrm{rel}$ está llena. El $30$ es el único al que todos dividen. Cada uno sale con un cuantificador: $\forall y\mathrm{rel}(x,y)$ y $\forall y\mathrm{rel}(y,x)$.

La pregunta fina. El $3$ y el $5$ se parecen mucho: los dos tienen debajo sólo al $1$, los dos son incomparables con el otro. Si hubiera una biyección de $A$ en sí mismo que respetara la división y los intercambiara, ninguna fórmula pura podría separarlos: lo único que una fórmula ve es la forma del dibujo, y para esa forma serían el mismo lugar. Entonces el ejercicio no tendría solución para (b) y (c).

No la hay. Recorriendo las 120 permutaciones de $A$, la única que respeta la división en los dos sentidos es la identidad. Y se ve sin contar: el $3$ divide al $6$ y el $5$ no divide a nadie salvo al $30$. El $3$ tiene arriba algo que no es el techo; el $5$, no. Ésa es la frase que lo delata, y la fórmula es esa frase traducida.

Con eso el resto es romper empates, de a uno. El $6$ es, entre los que no son el techo, el único que tiene debajo algo que no es el piso (el $3$). El $3$ es, entre los que no son el piso, el único que tiene arriba algo que no es el techo (el $6$). Y el $5$ es el que queda: todo lo que tiene debajo propio es el piso, y todo lo que tiene arriba propio es el techo. Eso solo ya deja afuera a los otros cuatro, incluidos el $1$ y el $30$: el $1$ tiene arriba al $3$, que no es el techo, y el $30$ tiene debajo al $6$, que no es el piso.

Abajo se arma cada fórmula sumando cláusulas. Cada una es una frase sobre la posición de $x$ y se puede pedir o pedir negada; la fórmula es la conjunción de las que elegiste, y se evalúa en los cinco elementos.

Cada renglón de la tabla es la columna de verdad de una cláusula, medida con la definición de la sección 02. Pedir una cláusula deja vivas las columnas donde vale; pedirla negada, las otras. Con el $6$ adentro, cada elemento se aísla con a lo sumo dos cláusulas: barridas las 3⁵ = 243 combinaciones, el $1$ y el $30$ salen con una, y el $3$, el $5$ y el $6$ con dos. Sin el $6$ el dibujo es un rombo, el $3$ y el $5$ pasan a tener columnas idénticas en todas las cláusulas, y no hay combinación que los separe: en ninguna de las 243 difieren. Ahí sí habría una simetría, y el ejercicio no tendría respuesta.

04 · El escarabajo: las cinco fórmulas, verificadas

En cada inciso, la fórmula y después la verificación en los cinco valores de $x$. Las cinco tienen a $x$ como única variable libre: $y$, $z$ y $w$ aparecen siempre bajo su cuantificador.

(a) $i=1$.

$${\phi }_1=\forall y\mathrm{rel}(x,y)$$

Con $x$ como $1$: el $1$ divide a $1,3,5,6$ y $30$, así que $\mathrm{rel}(x,y)$ es verdadera para todo valor de $y$ y ${\phi }_1$ es verdadera. Con $x$ como $3$, tomando $y$ como $5$, $\mathrm{rel}(x,y)$ es falsa porque $3$ no divide a $5$. Con $x$ como $5$, tomando $y$ como $3$: $5$ no divide a $3$. Con $x$ como $6$, tomando $y$ como $3$: $6$ no divide a $3$. Con $x$ como $30$, tomando $y$ como $1$: $30$ no divide a $1$. En esos cuatro, ${\phi }_1$ es falsa.

(e) $i=30$. La misma, con los argumentos dados vuelta:

$${\phi }_{30}=\forall y\mathrm{rel}(y,x)$$

Con $x$ como $30$: $1,3,5,6$ y $30$ dividen a $30$, así que es verdadera. Con $x$ como $1$, tomando $y$ como $3$: $3$ no divide a $1$. Con $x$ como $3$, tomando $y$ como $5$: $5$ no divide a $3$. Con $x$ como $5$, tomando $y$ como $3$: $3$ no divide a $5$. Con $x$ como $6$, tomando $y$ como $5$: $5$ no divide a $6$. Falsa en esos cuatro.

(d) $i=6$. No es el techo, y tiene debajo, propio, algo que no es el piso:

$${\phi }_6=\neg \forall y\mathrm{rel}(y,x)\wedge \exists z(\mathrm{rel}(z,x)\wedge z\ne x\wedge \neg \forall w\mathrm{rel}(z,w))$$

Con $x$ como $6$: por (e), $\forall y\mathrm{rel}(y,x)$ es falsa en $6$, así que el primer conjunto vale; y tomando $z$ como $3$, $3$ divide a $6$, $3\ne 6$, y $\forall w\mathrm{rel}(z,w)$ es falsa (tomando $w$ como $5$, $3$ no divide a $5$): el segundo conjunto vale. Verdadera. Con $x$ como $30$: por (e), $\forall y\mathrm{rel}(y,x)$ es verdadera, y el primer conjunto falla. Con $x$ como $1$: el único valor de $z$ que divide a $1$ es $1$, y ahí $z\ne x$ falla. Con $x$ como $3$: los valores de $z$ que dividen a $3$ son $1$ y $3$; con $3$ falla $z\ne x$, y con $1$ falla $\neg \forall w\mathrm{rel}(z,w)$, porque por (a) el $1$ divide a todos. Con $x$ como $5$: lo mismo, con $1$ y $5$. Falsa en los cuatro.

(b) $i=3$. No es el piso, y tiene arriba, propio, algo que no es el techo:

$${\phi }_3=\neg \forall y\mathrm{rel}(x,y)\wedge \exists z(\mathrm{rel}(x,z)\wedge z\ne x\wedge \neg \forall w\mathrm{rel}(w,z))$$

Con $x$ como $3$: por (a), $\forall y\mathrm{rel}(x,y)$ es falsa en $3$; y tomando $z$ como $6$, $3$ divide a $6$, $6\ne 3$, y $\forall w\mathrm{rel}(w,z)$ es falsa (tomando $w$ como $5$, $5$ no divide a $6$). Verdadera. Con $x$ como $1$: por (a), $\forall y\mathrm{rel}(x,y)$ es verdadera y el primer conjunto falla. Con $x$ como $5$: los múltiplos de $5$ en $A$ son $5$ y $30$; con $5$ falla $z\ne x$, y con $30$ falla $\neg \forall w\mathrm{rel}(w,z)$ porque por (e) todos dividen a $30$. Con $x$ como $6$: los múltiplos son $6$ y $30$, y fallan por las mismas dos razones. Con $x$ como $30$: su único múltiplo es $30$, y falla $z\ne x$. Falsa en los cuatro.

(c) $i=5$. Todo lo que tiene debajo propio es el piso, y todo lo que tiene arriba propio es el techo:

Con $x$ como $5$: los valores de $z$ que dividen al $5$ y son distintos de él se reducen al $1$, que divide a todos; los múltiplos del $5$ distintos de él se reducen al $30$, al que todos dividen. Los dos conjuntos valen: verdadera. Con $x$ como $1$ falla el segundo: tomando $z$ como $3$, $1$ divide a $3$ y $3\ne 1$, pero $\forall w\mathrm{rel}(w,z)$ es falsa (el $5$ no divide al $3$). Con $x$ como $3$ falla el segundo: tomando $z$ como $6$, $3$ divide a $6$ y $6\ne 3$, pero $\forall w\mathrm{rel}(w,z)$ es falsa (el $5$ no divide al $6$). Con $x$ como $6$ falla el primero: tomando $z$ como $3$, $3$ divide a $6$ y $3\ne 6$, pero $\forall w\mathrm{rel}(z,w)$ es falsa (el $3$ no divide al $5$). Con $x$ como $30$ falla el primero: tomando $z$ como $6$, $6$ divide a $30$ y $6\ne 30$, pero $\forall w\mathrm{rel}(z,w)$ es falsa (el $6$ no divide al $5$). Falsa en los cuatro.

Hay una más corta para (c), por incomparabilidad. Los pares incomparables de $A$ son $\{\mathrm{3,5}\}$ y $\{\mathrm{5,6}\}$: el $5$ es el único incomparable con dos elementos distintos.

$$\begin{array}{l}{\psi }_5=\exists y\exists z(y\ne z\wedge \neg \mathrm{rel}(x,y)\wedge \neg \mathrm{rel}(y,x)\wedge \\ \neg \mathrm{rel}(x,z)\wedge \neg \mathrm{rel}(z,x))\end{array}$$

Con $x$ como $5$, tomando $y$ como $3$ y $z$ como $6$, los cinco conjuntos valen. Con $x$ como $3$, el único incomparable es el $5$, y $y$ y $z$ tendrían que valer los dos $5$, cosa que $y\ne z$ prohíbe. Con $x$ como $6$, lo mismo con el $5$. Con $x$ como $1$ o $30$ no hay ningún incomparable. No hace falta pedir $y\ne x$: como todo elemento se divide a sí mismo, $\neg \mathrm{rel}(x,y)$ ya lo impide.

Las seis fórmulas, evaluadas elemento por elemento con la definición de verdad, dan verdadero exactamente en la diagonal:

05 · Lo que se lleva a otros ejercicios

El método. Dibujar el Hasse, anotar qué tiene cada elemento debajo y arriba, y romper empates de a uno con cláusulas que hablen de posición: ser el piso, ser el techo, tener debajo o arriba algo que no es el piso o el techo, ser incomparable con alguien. Las fórmulas de los elementos ya resueltos sirven de piezas para los siguientes: ${\phi }_6$, ${\phi }_3$ y ${\phi }_5$ usan ${\phi }_1$ y ${\phi }_{30}$ adentro, con $w$ en lugar de $y$ y aplicadas a $z$.

Antes de buscar, preguntá si hay simetría. Si una biyección que respeta la relación intercambia dos elementos, ninguna fórmula pura los separa, y vale la pena saberlo antes de pasar media hora probando. Acá no la hay, y la razón entra en una línea: el $6$ es múltiplo del $3$ y no del $5$. Ese argumento es de la mariposa; la respuesta no lo necesita, porque lo que se entrega son las fórmulas y su verificación.

Lo que hace perder puntos. Escribir algo como $x=3$ o $\mathrm{rel}(x,6)$: no son fórmulas puras de tipo $\tau$. Reusar una fórmula ya escrita con su $x$ libre adentro de otra sin cambiarle la variable, y quedar con dos libres. Verificar sólo que la fórmula vale en su elemento y no que es falsa en los otros cuatro. Y la regla de la cátedra: si se usa un resultado de alguna guía, hay que enunciarlo y probarlo por separado; esta resolución no usa ninguno, sólo la definición de verdad.

Para tener a mano

1. Sin constantes, los únicos términos son variables: un elemento se describe por su lugar, nunca por su nombre.
2. El piso es $\forall y\mathrm{rel}(x,y)$ y el techo $\forall y\mathrm{rel}(y,x)$. Con esas dos piezas se arma el resto.
3. El $3$ y el $5$ no son simétricos: el $3$ tiene arriba al $6$, que no es el techo. Sin el $6$ serían indistinguibles.
4. Cada fórmula se verifica en los cinco valores: verdadera en el suyo, falsa en los otros cuatro, con el testigo o el contraejemplo escrito.
5. Toda variable auxiliar va ligada; la única libre es $x$.