Fórmulas y sentencias elementales

La Guía 6 armó el lenguaje de los reticulados cuaterna. La Guía 7 lo repitió para posets, grafos, median álgebras y los demás, y la Guía 8 notó que era siempre lo mismo con otros símbolos. Lo que cambia de una estructura a otra es una lista: qué constantes, qué funciones y qué relaciones hay, y cuántos argumentos lleva cada una. Esa lista es el tipo. Fijado el tipo salen tres cosas en cadena: las estructuras que lo interpretan, las palabras que se escriben con sus símbolos, y cuándo una de esas palabras es verdadera.

01 · El tipo: qué símbolos hay y cuántos argumentos lleva cada uno

Definición (Guía 8). Un tipo es una 4-upla $\tau =(C,F,R,a)$ donde $C$ es un conjunto de nombres de constante, $F$ uno de nombres de función, $R$ uno de nombres de relación, y $a:F\cup R\to \mathbb{N}$ es una función que le asocia a cada nombre de función o de relación su aridad: cuántos argumentos lleva. Para cada $n$ se escribe

$$F_n=\{f\in F:a(f)=n\}{R}_n=\{r\in R:a(r)=n\}$$

Los nombres son palabras sobre alfabetos disjuntos de a pares que no usan ninguno de los símbolos lógicos —$\forall$, $\exists$, $\neg$, $\vee$, $\wedge$, $\to$, $\leftrightarrow$, los paréntesis, la coma, $\equiv$— ni los que se usan para escribir variables, y ninguna palabra de $C$ (o de $F$, o de $R$) es subpalabra propia de otra del mismo conjunto. Las dos restricciones están para que una fórmula se pueda leer de una sola manera.

Los ocho tipos de estructura de la Guía 7, cada uno con su nombre:

Los elementos de $C$, $F$ y $R$ son símbolos, no lo que denotan. El tipo de los posets no sabe que $\le$ es un orden: sabe que es un nombre de relación de aridad 2, y nada más. Y nada lo ata a la costumbre. En $(\{\le \},\varnothing ,\varnothing ,\varnothing )$ el $\le$ es un nombre de constante; en $(\varnothing ,\{1\},\varnothing ,\{(1,3)\})$ el numeral $1$ nombra una operación de tres argumentos; en $(\varnothing ,\varnothing ,\{\le \},\{(\le ,3)\})$ el $\le$ es una relación ternaria. Los tres son tipos, y los tres son ejemplos de la Guía 8.

02 · Una estructura de tipo τ interpreta cada símbolo

Definición (Guía 8). Una estructura, o modelo, de tipo $\tau$ es 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$ —la interpretación— que cumple:

• $i(c)\in A$ para cada $c\in C$;
• $i(f)$ es una operación $n$-aria sobre $A$, una función de $A^n$ en $A$, para cada $f\in F_n$;
• $i(r)$ es una relación $n$-aria sobre $A$, un subconjunto de $A^n$, para cada $r\in R_n$.

La interpretación puede ser cualquiera. Una estructura del tipo de los posets es un conjunto no vacío con una relación binaria cualquiera: $(\{1,2,3\},\{(\le ,\varnothing )\})$ es una, y $(\mathbb{N},i)$ con $i(\le )=\{(1,2),(1000,1),(1,1)\}$ es otra. Cuando $i(\le )$ es un orden parcial, la estructura es esencialmente un poset: tiene la misma información, aunque un par $(A,i)$ no sea, letra por letra, un poset.

Cuántas hay. Si $A$ es finito y $C$, $F$ y $R$ también, las estructuras de tipo $\tau$ con universo $A$ son

$${|A|}^{|C|}\text{ · }\prod _{f\in F}{|A|}^{{|A|}^{a(f)}}\text{ · }\prod _{r\in R}{2}^{{|A|}^{a(r)}}$$

Prueba. La interpretación se elige símbolo por símbolo, y cada elección es independiente de las otras. Para un nombre de constante hay $|A|$ elecciones. Para un $f\in F_n$, $i(f)$ es una función con dominio $A^n$, que tiene ${|A|}^n$ elementos, e imagen contenida en $A$: por el Lema 1 (1) de la Guía 8 hay ${|A|}^{{|A|}^n}$. Para un $r\in R_n$, $i(r)$ es un subconjunto de $A^n$: por el Lema 1 (2) hay $2^{{|A|}^n}$. Multiplicando las elecciones queda la fórmula. ∎

Con $A=\{1,2\}$, recorridas una por una: el tipo de los posets da $2^{2^2}=16$ estructuras, y 3 son posets —la anticadena y las dos cadenas—. El de los reticulados terna da ${(2^{2^2})}^2=256$, y en 2 valen los ocho axiomas de terna: las dos formas de ordenar $\{1,2\}$ en cadena. Casi todas las estructuras de un tipo no son nada de lo que el nombre del tipo promete. Los Ejercicios 17 a 19 de la lista hacen la misma cuenta con nueve elementos.

03 · Términos: las palabras que nombran elementos

Además de los símbolos del tipo, el lenguaje tiene las variables $x,y,z,w,\dots$, los nombres de elementos fijos $a,b,c,d,\dots$, los nexos, los cuantificadores, los paréntesis, la coma y el $=$. Los términos elementales de tipo $\tau$ se definen por cláusulas (Guía 8):

1. cada palabra de $C$ es un término;
2. cada variable es un término;
3. cada nombre de elemento fijo es un término;
4. si $f\in F_n$, con $n\ge 1$, y $t_1,\dots ,t_n$ son términos, la palabra $f(t_1,\dots ,t_n)$ es un término;
5. una palabra es un término si y sólo si se construye con las cláusulas anteriores.

La palabra $f(t_1,\dots ,t_n)$ mide $|f|+|t_1|+\dots +|t_n|+(n-1)+2$: los dos paréntesis y las $n-1$ comas cuentan. Un término es puro si no tiene nombres de elementos fijos. En el tipo de los reticulados complementados, $s(i(x,0),z)$ y $c(s(i(0,0),0))$ son términos puros y $s(x,a)$ no es puro. Y las aridades se respetan: en un tipo con $P$ de aridad 1, $P(x,y)$ no es un término. Que un término es la palabra y no el elemento que termina valiendo es la tesis de Un término es una palabra, no un valor.

04 · Fórmulas: las palabras que pueden ser verdaderas o falsas

Las fórmulas elementales de tipo $\tau$ también se definen por cláusulas:

1. si $t$ y $s$ son términos, $(t=s)$ es una fórmula;
2. si $r\in R_n$, con $n\ge 1$, y $t_1,\dots ,t_n$ son términos, $r(t_1,\dots ,t_n)$ es una fórmula;
3. si ${\phi }_1$ y ${\phi }_2$ son fórmulas, también lo son $({\phi }_1\wedge {\phi }_2)$, $({\phi }_1\vee {\phi }_2)$, $({\phi }_1\to {\phi }_2)$ y $({\phi }_1\leftrightarrow {\phi }_2)$;
4. si $\phi$ es una fórmula, también lo son $\neg \phi$, $\forall x\phi$, $\forall y\phi$, … y $\exists x\phi$, $\exists y\phi$, …;
5. una palabra es una fórmula si y sólo si se construye con las cláusulas anteriores.

Las dos primeras son las atómicas, y son las únicas donde aparecen los términos. Fijate en la cuarta: negar y cuantificar no agregan paréntesis; sólo los nexos los agregan. Por eso $\neg$ y los cuantificadores se pegan a lo que les sigue y nada más, y $(\exists z(a\le z)\wedge (b\le z))$ es la conjunción de $\exists z(a\le z)$ con $(b\le z)$, no «existe $z$ tal que las dos». Se cuantifica sólo por delante y sólo variables: $(x\le a)\forall x$ y $\forall a(a=x)$ no son fórmulas.

Una fórmula es pura si no tiene nombres de elementos fijos; entonces sus términos también son puros. Los axiomas y lo que la lista pide probar o escribir son sentencias o fórmulas puras: los nombres de elementos fijos aparecen adentro de las pruebas, para hablar de un elemento «fijo pero arbitrario».

05 · Libres, ligadas y sentencias

Una ocurrencia de una variable $v$ en $\phi$ es acotada si está adentro de una ocurrencia en $\phi$ de una subfórmula de la forma $\forall v\psi$ o $\exists v\psi$, y libre si no. La $\psi$ que sigue a una ocurrencia de un cuantificador es su alcance. Una variable libre de $\phi$ es una que ocurre libre al menos una vez, aunque también ocurra acotada. Una sentencia es una fórmula sin variables libres.

El ejemplo largo de la Guía 6:

$$(((x\le z)\vee \exists x\forall y((a\le x)\wedge (y\le x)))\to \forall y(z\le y))$$

Las dos ocurrencias de $z$ son libres. Todas las de $y$ son acotadas: cada una está adentro de algún $\forall y$. La primera ocurrencia de $x$ es libre y las otras tres son acotadas. Las variables libres son $x$ y $z$. El $a$ no es ni libre ni acotado: no es una variable, es un nombre de elemento fijo, y la fórmula no es pura.

Esto último tiene una consecuencia que conviene tener presente: $\forall x(a\le x)$ es una sentencia —no tiene variables libres— y aun así su valor de verdad depende del valor que se le dé a $a$. En $(\{A\subseteq \mathbb{N}:A\text{ es finito}\},\cup ,\cap ,\subseteq )$ es verdadera si $a$ vale $\varnothing$ y falsa con cualquier otro valor. Sólo una sentencia pura queda decidida por la estructura sola.

06 · Verdadera en una estructura, con una asignación

Una fórmula sola no es verdadera ni falsa. Hacen falta una estructura $𝐀=(A,i)$ de su tipo y una asignación: un elemento de $A$ para cada variable y para cada nombre de elemento fijo. Con eso, primero cada término asume un valor:

• una variable o un nombre de elemento fijo vale lo que le da la asignación;
• un nombre de constante $c$ vale $i(c)$;
• $f(t_1,\dots ,t_n)$ vale $i(f)$ aplicada a los valores de $t_1,\dots ,t_n$.

Y después cada fórmula es verdadera o falsa, siguiendo cómo se construyó:

• $(t=s)$ es verdadera si $t$ y $s$ valen el mismo elemento;
• $r(t_1,\dots ,t_n)$ es verdadera si la $n$-upla de los valores está en $i(r)$;
• $\neg \phi$, $({\phi }_1\wedge {\phi }_2)$, $({\phi }_1\vee {\phi }_2)$, $({\phi }_1\to {\phi }_2)$ y $({\phi }_1\leftrightarrow {\phi }_2)$, según las tablas de siempre, con los valores de $\phi$, ${\phi }_1$ y ${\phi }_2$ con la misma asignación;
• $\forall x\phi$ es verdadera si $\phi$ es verdadera con cada asignación que se obtiene de ésta cambiando sólo el valor de $x$ por un elemento de $A$;
• $\exists x\phi$ es verdadera si $\phi$ es verdadera con alguna de esas asignaciones.

Los cuantificadores recorren el universo de la estructura, y nada más. Es la versión que usan las guías: el segundo punto del programa de la Guía 8 es dar una definición matemática precisa de esto.

Propiedad: sólo importan las libres. Si dos asignaciones les dan los mismos valores a las variables libres y a los nombres de elementos fijos de $\phi$, entonces $\phi$ tiene el mismo valor de verdad con las dos.

Prueba, siguiendo la construcción de $\phi$. Primero para términos: si las dos asignaciones coinciden en las variables y los nombres fijos que ocurren en $t$, $t$ vale lo mismo con las dos; es inmediato en las tres cláusulas de valor. Si $\phi$ es atómica, todas las ocurrencias de variables en $\phi$ son libres, así que sus términos valen lo mismo con las dos asignaciones, y $\phi$ tiene el mismo valor. Si $\phi$ es $\neg \psi$ o $({\phi }_1\wedge {\phi }_2)$ —o con cualquier otro nexo—, las libres de $\psi$, ${\phi }_1$ y ${\phi }_2$ son libres de $\phi$, así que por hipótesis inductiva cada pedazo vale lo mismo con las dos, y $\phi$ también. Si $\phi$ es $\forall x\psi$, las libres de $\psi$ son las de $\phi$ más, quizás, $x$. Para cada elemento $e\in A$, cambiar en las dos asignaciones el valor de $x$ por $e$ da dos asignaciones que coinciden en todas las libres de $\psi$: por hipótesis inductiva $\psi$ vale lo mismo con las dos. Como eso pasa para cada $e$, $\forall x\psi$ vale lo mismo con las dos. El caso $\exists x\psi$ es el mismo argumento cambiando «cada» por «alguna». ∎

Consecuencia. Una sentencia pura no tiene ni libres ni nombres fijos, así que es verdadera con todas las asignaciones o con ninguna: en cada estructura de su tipo es verdadera o falsa, sin asignar nada. Por eso los axiomas son sentencias puras, y por eso un modelo de un conjunto de sentencias puras es simplemente una estructura donde todas son verdaderas.

Y una más, que la Guía 6 deja escrita: el papel de una variable acotada es mudo. Cambiar todas sus ocurrencias en un bloque $\forall y\psi$ por una variable $w$ que no figure en $\psi$ no cambia lo que la fórmula dice. Abajo, $((x\le y)\wedge \forall y((y\le x)\to (y=x)))$ y la misma con $\forall w$ en lugar de $\forall y$ dan el mismo valor en las 72 asignaciones de $x$ e $y$ sobre las dos estructuras del widget.

En «$y$ cubre a $x$» sobre los divisores de 12, con $x=2$ e $y=12$ el renglón que cae es el del $\neg \exists z$: el $\exists z$ encuentra un testigo, el $4$, que está en el medio. De las 36 asignaciones, la fórmula es verdadera en 7, las siete aristas del diagrama de Hasse. Con la estructura cambiada —el mismo símbolo $\le$ interpretado como el menor estricto entre números, que no es un orden parcial— es verdadera en 5: los pares de vecinos de la lista $1,2,3,4,6,12$. La palabra no cambió; cambió lo que dice.

En la segunda fórmula la $y$ es libre por su primera ocurrencia y acotada en el $\forall y$. Mové $y$ y mirá el renglón del $\forall y$: no lista a $y$ entre sus valores, y no cambia nunca. Es la propiedad de arriba, vista de cerca. La tercera es una sentencia pura: no hay nada que asignar, y el valor lo decide la estructura sola —verdadera con la divisibilidad, donde el $12$ está arriba de todos, y falsa con el menor estricto, donde nadie está arriba de sí mismo—.

07 · Leer una fórmula en castellano

Leer es desarmar la fórmula en el orden inverso al que se construyó. Cuatro pasos:

1. El conectivo principal. Si la fórmula empieza con $\neg$ o con un cuantificador, es ése. Si no, es el único nexo que queda afuera de todos los paréntesis interiores.
2. Cada cuantificador, con su alcance. $\forall x$ es «para todo $x$ de la estructura»; $\exists x$, «hay un $x$ tal que». El alcance es exactamente la fórmula que le sigue.
3. Nombre para los bloques. $(x\le z\wedge \neg (z=x))$ es «$z$ está estrictamente arriba de $x$»; con un $\neg \exists z$ adelante es «nada está estrictamente arriba de $x$», o sea, $x$ es maximal.
4. La frase, hablando de las libres. Una fórmula con $x$ libre dice algo de $x$; una sentencia pura dice algo de la estructura.

Un ejemplo de grafos, que es el del Ejercicio 15 de la Guía 7 y el 16 de la lista:

$$\forall x(\forall z(\neg (z=x)\to r(x,z))\to \forall u\forall v((\neg (u=x)\wedge \neg (v=x))\to \neg r(u,v)))$$

El conectivo principal es el $\forall x$, y adentro hay una implicación. El antecedente, $\forall z(\neg (z=x)\to r(x,z))$, dice que $x$ está conectado con todos los otros vértices. El consecuente dice que entre dos vértices distintos de $x$ no hay arista. Junto: si un vértice está conectado con todos los demás, entre los demás no hay ninguna arista. Comparado con la propiedad calculada directamente sobre los 64 grafos con vértices $\{0,1,2,3\}$, la sentencia coincide con la frase en los 64.

Dos parejas que se confunden. «Todo $\phi$ es $\psi$» es $\forall x(\phi \to \psi )$, no $\forall x(\phi \wedge \psi )$, que dice que todo es $\phi$ y $\psi$. Y «algún $\phi$ es $\psi$» es $\exists x(\phi \wedge \psi )$, no $\exists x(\phi \to \psi )$, que es verdadera apenas hay un elemento que no es $\phi$. Con $\mathrm{Max}(x)=\neg \exists z(x\le z\wedge \neg (z=x))$, en $(\{1,2,3,4,6,12\},\mid )$:

Las filas en rojo son la traducción equivocada de la de arriba. La tercera es «todo maximal es máximo», la del Ejercicio 4 de la lista; cuándo vale en un poset es lo que mira Maximal no es máximo, salvo que todo par tenga cota.

08 · Traducir una propiedad a una fórmula

El camino inverso, y el que piden los Ejercicios 7, 8, 9, 20 y 21 de la lista. Cuatro pasos:

1. Mirá el tipo. Sólo se escribe con sus símbolos. En el tipo de los posets no hay $s$, ni $0$, ni numerales: un elemento concreto no se nombra, se describe por su lugar en el orden. $(x=4)$ no es una fórmula de un tipo donde $4$ no es un nombre de constante, por más que «diga» lo correcto.
2. Decila en castellano matemático, con cada «para todo» y cada «existe» a la vista, y sin palabras que el tipo no tenga: «mayor», «par», «primo» se reemplazan por lo que significan en términos de la estructura.
3. Armá fórmulas auxiliares para los pedazos con nombre —$\mathrm{Max}(x)$, $\mathrm{Cub}(x,y)$— y reemplazá. Al reemplazar, renombrá las ligadas para que no atrapen nada.
4. Controlá. Que las variables libres sean exactamente las que pide el enunciado, y evaluala en la estructura del enunciado, elemento por elemento.

La trampa del tercer paso, concreta: $\mathrm{Max}(z)$ escrito cambiando $x$ por $z$ en $\neg \exists z(x\le z\wedge \neg (z=x))$ da $\neg \exists z(z\le z\wedge \neg (z=z))$. La $z$ que se quería libre quedó atrapada por el $\exists z$: la palabra resultante es una sentencia, y como $\neg (z=z)$ es falsa siempre, es verdadera en toda estructura. No dice nada. Renombrando la ligada antes de reemplazar sale $\neg \exists w(z\le w\wedge \neg (w=z))$, que en los divisores de 12 es verdadera sólo con $z=12$.

Un ejemplo entero, el Ejercicio 3 (b) de la Guía 7: una fórmula pura de posets, con $x$ como única libre, verdadera en $(\{1,2,4,9\},\mid )$ si y sólo si a $x$ se le asigna el $4$. Primer intento, «$x$ es maximal»: vale en el $4$ y en el $9$. Hay que separarlos, y la diferencia está abajo: debajo del $4$ hay una cadena de dos pasos, $1\mid 2\mid 4$, y debajo del $9$ sólo está el $1$. Eso se escribe:

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

Su única libre es $x$, y evaluada elemento por elemento:

«Tener al menos dos elementos distintos estrictamente debajo» también separa al $4$, y evaluada da la misma columna. Hay muchas respuestas correctas; lo que no se negocia es que la columna dé verdadera exactamente en el elemento pedido.

09 · Las abreviaturas que permite la lista

La Guía 8 escribe todo en la forma general —$\le (x,y)$, $s(x,y)$— para no tratar distinto a los símbolos binarios. La lista, para que se lea, permite:

• $x\le y$ en lugar de $\le (x,y)$;
• $xsy$ en lugar de $s(x,y)$;
• $x\ne y$ en lugar de $\neg (x=y)$;
• $x\nleqq y$ en lugar de $\neg (x\le y)$, y así con las demás relaciones;
• $\forall x,y,z,w$ en lugar de $\forall x\forall y\forall z\forall w$, y lo mismo con $\exists$;
• paréntesis de menos, siempre que no haya ambigüedad.

La última es la delicada. Una cadena del mismo nexo, $x\le y\wedge y\le z\wedge z=c$, se lee de una sola manera. Mezclar nexos no: $x\le y\wedge y\le z\vee a=b$ puede ser dos fórmulas distintas, y la Guía 6 escribe $(x\le y\wedge y\le z)\vee a=b$. Y los paréntesis que siguen a un cuantificador no son de lectura: marcan el alcance. $\exists z(a\le z\wedge b\le z)$ y $\exists za\le z\wedge b\le z$ son fórmulas distintas, y la segunda tiene a $z$ libre. Abreviar es escribir menos; la fórmula sigue siendo la palabra entera, y sus libres y su longitud se cuentan sobre ella.

10 · Palabras que parecen fórmulas y no lo son

Las cláusulas dicen qué es una fórmula, y con eso dicen qué no. Las que más se cuelan:

• $\le (x,y,z)$ en el tipo de los posets: $\le$ tiene aridad 2.
• $(x\le y)$ en el tipo de los reticulados terna: $\le$ no es un símbolo del tipo. Para hablar del orden ahí se escribe $xsy=y$.
• $s(x,y)$ sola: es un término, nombra un elemento, no dice nada verdadero ni falso.
• $\forall a(a=x)$: sólo se cuantifican variables.
• $(x\le a)\forall x$: se cuantifica por delante.
• $(x\le 4)$ en el tipo de los posets, o $\neg \mathrm{Verde}(\pi )$ en el ejemplo de la Guía 8: ni $4$ ni $\pi$ son nombres del tipo, aunque la frase sea verdadera en la estructura.

Y al revés: una misma palabra puede ser fórmula de dos tipos. $(x\le y)$ es fórmula de posets y de reticulados cuaterna; $\forall x\forall y(xsy=y\to xiy=x)$ es sentencia de terna y de cuaterna. Ser fórmula es relativo al tipo, y lo que eso le hace a una prueba es otra historia.

Para tener a mano

1. Un tipo $\tau =(C,F,R,a)$ es la lista de símbolos y sus aridades. Son palabras, no lo que denotan.
2. Una estructura $(A,i)$ interpreta cada símbolo en un universo no vacío, como se le ocurra. Con $A$, $C$, $F$, $R$ finitos hay ${|A|}^{|C|}·\prod {|A|}^{{|A|}^{a(f)}}·\prod 2^{{|A|}^{a(r)}}$.
3. Términos y fórmulas son palabras, construidas por cláusulas. Negar y cuantificar no agregan paréntesis. Pura: sin nombres de elementos fijos.
4. Libre es una propiedad de cada ocurrencia; una variable es libre de $\phi$ si ocurre libre al menos una vez. Sentencia: sin variables libres.
5. Verdadera es siempre «en una estructura, con una asignación». Sólo importan las libres y los nombres fijos; una sentencia pura queda decidida por la estructura.
6. Leer: conectivo principal, cuantificadores con su alcance, nombre a los bloques. «Todo $\phi$ es $\psi$» es $\forall x(\phi \to \psi )$; «algún $\phi$ es $\psi$» es $\exists x(\phi \wedge \psi )$.
7. Traducir: sólo con los símbolos del tipo, con auxiliares renombrando las ligadas, y evaluando en la estructura elemento por elemento.