Teorías elementales y sus modelos

Una teoría elemental son palabras: un tipo y un conjunto de sentencias. Sus modelos son las estructuras donde esas sentencias son verdaderas. Probar algo en la teoría es mostrar que vale en todos los modelos sin mirar ninguno en particular, y de ahí sale la herramienta más barata de la guía: para ver que algo no se puede probar, alcanza con un solo modelo donde sea falso.

01 · La definición

Las dos definiciones son de la Guía 8, pág. 21. Una teoría elemental es un par $(\Sigma ,\tau )$ donde $\tau$ es un tipo cualquiera y $\Sigma$ es un conjunto de sentencias elementales puras de tipo $\tau$. A las sentencias de $\Sigma$ se las llama axiomas. Un modelo de $(\Sigma ,\tau )$ es una estructura de tipo $\tau$ que hace verdaderos a todos los elementos de $\Sigma$.

El ejemplo que sirve para todo lo que sigue es el Ejercicio 22 de la lista (el 16 de la Guía 8). El tipo tiene un solo símbolo, de función y unario, y la teoría un solo axioma:

$$\tau =(\varnothing ,\{\mathrm{Op}\},\varnothing ,\{(\mathrm{Op},1)\})\Sigma =\{\forall x(\mathrm{Op}(\mathrm{Op}(x))=x)\}$$

Una estructura de tipo $\tau$ es un par $(A,i)$ con $A$ no vacío e $i(\mathrm{Op})$ una función cualquiera de $A$ en $A$. Es modelo cuando esa función, aplicada dos veces, devuelve siempre el punto de partida. Sobre $\{1,2\}$ hay cuatro estructuras: la identidad y la que intercambia los dos elementos son modelos; las dos constantes no, porque mandan todo a un mismo punto y el otro no vuelve.

Tres cosas de la definición que conviene leer despacio.

Es sintaxis. $\Sigma$, los símbolos de $\tau$ y cada axioma son palabras. La teoría no habla de ningún conjunto ni de ninguna función: los modelos son su semántica, y viven del otro lado. Un axioma es una sentencia que en cada estructura vale o no vale, y eso se puede preguntar estructura por estructura, como se hace con los siete de reticulado cuaterna en Las tres reglas eran axiomas.

El tipo no trae los axiomas. Hasta la Guía 7, decir «prueba elemental de posets» ya suponía los tres axiomas de poset. Acá se separan: sobre el tipo de los reticulados cuaterna viven la teoría de los reticulados cuaterna, la de los distributivos (ejemplo E9 de la guía, un axioma más) y las de los Ejercicios 24 y 25, que agregan constantes y axiomas. Mismo lenguaje, otros modelos.

Puras, pero con constantes. Los axiomas no llevan nombres de elementos fijos: $a$, $b$, $c$ nombran objetos hipotéticos adentro de una prueba, y un axioma es el punto de partida, anterior a cualquier prueba. Lo que sí pueden llevar son nombres de constante, como el $0$ o el $\text{ato}$ del Ejercicio 24: ésos son parte del tipo, y cada estructura los interpreta con su $i$.

02 · Qué son los modelos, contados

Leer una teoría es poder decir qué son sus modelos con otras palabras. Si $f=i(\mathrm{Op})$ cumple $f(f(x))=x$, cada elemento o queda quieto, $f(x)=x$, o va a otro $y$ que lo devuelve, $f(y)=x$. Dibujada con una flecha de cada elemento a su imagen, una involución son puntos sueltos con un rulo y parejas con dos flechas. Nada más puede pasar, y cualquier forma de partir el universo en sueltos y parejas da un modelo. Así que un modelo de esta teoría es, esencialmente, una manera de emparejar algunos elementos y dejar quietos los demás.

Eso se cuenta. Paso 1: elegir quiénes se emparejan. Con $k$ parejas hay que elegir $2k$ de los $n$ elementos. Paso 2: emparejarlos. El primero tiene $2k-1$ compañeros posibles, el primero de los que quedan $2k-3$, y así hasta $1$; ese producto es $(2k)!/(k!2^k)$. Paso 3: sumar sobre $k$.

$$I(n)=\sum _{k=0}^{\lfloor n/2\rfloor }\frac{n!}{k!2^k(n-2k)!}$$

Y se compara contra la enumeración: sobre $\{1,\dots ,n\}$ hay $n^n$ estructuras de tipo $\tau$ —una por cada función, por el Lema 1 de la guía—, y en cada una se evaluó el axioma como sentencia, cuantificador por cuantificador.

Coinciden en las siete filas, y no por construcción: una columna sale de evaluar la sentencia en cada función, la otra de la descripción en parejas. Que coincidan es lo que dice que la descripción es correcta. Y la columna de estructuras dice lo otro: los modelos son una parte ínfima del tipo, menos de una en tres mil con siete elementos.

03 · Probar en la teoría no es mirar un modelo

La Guía 8, págs. 23-24, define una prueba elemental de $\phi$ en $(\Sigma ,\tau )$ con tres condiciones: se parte de una estructura de tipo $\tau$ fija pero arbitraria, de la que lo único que se sabe es que satisface los axiomas de $\Sigma$; cada deducción es simple y se justifica con una frase; y lo matemático se escribe sólo con sentencias elementales de tipo $\tau$. Cómo se escribe una así está en La prueba elemental; lo que importa acá es la primera condición. La prueba no puede mirar el modelo: no sabe cuál es.

Por eso hay que separar cuatro cosas que suenan parecido. Que $\phi$ sea verdadera en un modelo, en algunos, en todos, o que se pueda probar. En la teoría del Ejercicio 22, cuatro sentencias, evaluadas en todos sus modelos de hasta siete elementos:

Las dos primeras son los incisos del Ejercicio 22, $\forall x\forall y(\neg (x=y)\to \neg (\mathrm{Op}(x)=\mathrm{Op}(y)))$ y $\forall x\exists y(\mathrm{Op}(y)=x)$: valen en todos los modelos de la tabla, y tienen prueba; la de la segunda está en El testigo lo construís vos. La última, $\forall x(\mathrm{Op}(x)=x)$, vale en un solo modelo de cada tamaño: la identidad. Verdadera en un modelo no es nada. Y la tercera, $\exists x(\mathrm{Op}(x)=x)$, es la que confunde: vale en todos los modelos de tamaño impar —con una cantidad impar de elementos, emparejando de a dos siempre sobra uno— y en los de tamaño par no.

04 · La corrección, y el contraejemplo

La relación entre probar y valer es una línea:

Si $\phi$ tiene una prueba elemental en $(\Sigma ,\tau )$, entonces $\phi$ es verdadera en todo modelo de $(\Sigma ,\tau )$.

La razón es la de la sección anterior. La prueba arrancó con un modelo fijo pero arbitrario y no usó nada de él salvo los axiomas, así que se puede leer entera con cualquier modelo en ese lugar; cada paso lleva de cosas verdaderas en él a cosas verdaderas en él; y los axiomas son verdaderos en él porque es modelo. La última línea, $\phi$, también. La Guía 8 lo anota como «una forma sólida de justificar» y lo deja para después: cuando la prueba elemental tenga su modelo matemático, la prueba formal, esto va a ser un teorema, el Teorema de Corrección de la Guía 14.

Dada vuelta, es la herramienta. Si hay un modelo de $(\Sigma ,\tau )$ donde $\phi$ es falsa, entonces $\phi$ no tiene prueba elemental en $(\Sigma ,\tau )$. Para mostrar que algo no se puede probar no hace falta revisar todas las pruebas posibles, que son infinitas: alcanza con una estructura. Pero tiene que cumplir dos cosas, y las dos se verifican:

• que sea modelo: cada axioma de $\Sigma$, verdadero ahí;
• que $\phi$ falle ahí.

En el Ejercicio 22, el modelo de dos elementos que los intercambia hace falsas a $\exists x(\mathrm{Op}(x)=x)$ y a $\forall x(\mathrm{Op}(x)=x)$: ninguna de las dos se prueba. Y la identidad, que es modelo, hace falsa a la negación $\neg \exists x(\mathrm{Op}(x)=x)$. Así que la teoría no decide si hay un punto fijo: ni la sentencia ni su negación tienen prueba.

La primera condición no es decorativa. La suryectividad falla en casi todas las funciones de cuatro elementos y ninguna de ésas es modelo, que es la cuenta que hace El testigo lo construís vos. Una estructura que no cumple $\Sigma$ no dice nada sobre lo que se prueba en $(\Sigma ,\tau )$, falle ahí lo que falle.

Es la pregunta del final del Ejercicio 16 de la lista: la sentencia «si $x$ es vecino de todos los demás, entre los demás no hay aristas» se prueba en la teoría de los grafos bicoloreados, y la lista pregunta si puede haber una prueba en la de los grafos. No: el triángulo es un grafo —cumple $\forall x\neg r(x,x)$ y $\forall x\forall y(r(x,y)\to r(y,x))$— y ahí la sentencia es falsa. Evaluada en todos los grafos de tres vértices falla sólo en ése, uno de ocho; con cuatro vértices, en 19 de 64. En los modelos de la teoría de los bicoloreados —2, 6, 26 y 162 con uno a cuatro vértices— no falla nunca, como tiene que pasar con algo que se prueba.

La vuelta también vale, aunque es mucho más difícil y es la otra mitad del programa de la guía: si $\phi$ es verdadera en todo modelo, tiene prueba. Es el Teorema de Completitud de Gödel, también de la Guía 14. Con los dos juntos, «no se puede probar» y «hay un modelo donde falla» son lo mismo.

Con tres elementos, «hay un punto fijo» no cae: los cuatro modelos de ese tamaño lo tienen. Hay que ir a dos o a cuatro, y armar un emparejamiento completo. Las dos primeras no caen con ningún tamaño ni con ninguna tabla, y no es falta de búsqueda: tienen prueba. En la segunda teoría no hay nada que refutar, porque no aparece ningún modelo; eso es la sección 07.

05 · «Esencialmente»: el modelo y el objeto que ya conocías

Ninguna estructura de tipo $\tau$ es un poset. Un poset es un par $(P,\le )$ cuya segunda coordenada es una relación; una estructura del tipo de los posets es un par $(A,i)$ cuya segunda coordenada es una función con dominio $\{\le \}$, la palabra. Un reticulado terna es una terna y la estructura sigue siendo un par. La Guía 8, pág. 8, lo dice así: a nivel de información son la misma cosa.

«Esencialmente» es esa identificación hecha precisa. Una estructura $(A,i)$ es esencialmente un poset cuando la tupla que sale de desarmar $i$, evaluándola en cada nombre del tipo, es un poset:

$$(A,i)⟼(A,i(\le ))(P,\le )⟼(P,\{(\le ,\le )\})$$

La segunda flecha arma $i$: al nombre $\le$ le asigna la relación del poset (el primer $\le$ del par es la palabra, el segundo la relación). Armar y desarmar son inversas, y por eso la segunda es una biyección entre todos los posets y un subconjunto de las estructuras: justo las que son modelo de la teoría elemental de los posets. «Ser esencialmente un poset» y «ser modelo de la teoría de los posets» terminan siendo lo mismo, que es lo que la guía anota al lado de cada una de las teorías que vienen de la Guía 7.

Y son pocas. De las 512 estructuras del tipo de los posets sobre tres elementos —una por cada subconjunto de los nueve pares, por el Lema 1— 19 son esencialmente posets; de las 256 del tipo de los reticulados terna sobre dos elementos —16 tablas para $s$ por 16 para $i$—, 2 son esencialmente reticulados terna. Los Ejercicios 17, 18 y 19 de la lista hacen esta cuenta sobre nueve elementos, donde las estructuras son $2^{81}$, $2^{90}$ y $9^{162}$, y piden la biyección.

06 · Con constantes: un elemento distinguido

Cuando el tipo tiene nombres de constante, desarmar $i$ también los evalúa, y la tupla trae elementos marcados. El Ejercicio 24 de la lista agrega al tipo de los reticulados cuaterna dos constantes, $0$ y $\text{ato}$, y a los siete axiomas tres más:

$$\forall x\le (0,x)\neg (\text{ato}=0)\forall x(\le (x,\text{ato})\to (x=0\vee x=\text{ato}))$$

Leídos en un modelo: $i(0)$ es el mínimo, $i(\text{ato})$ no lo es, y debajo de $i(\text{ato})$ no hay nada más que esos dos. O sea, $i(\text{ato})$ cubre al mínimo: es un átomo. Los modelos son, esencialmente, reticulados con mínimo en los que se eligió un átomo, y desarmar $i$ da la 6-upla $(A,i(s),i(i),i(\le ),i(0),i(\text{ato}))$. Nada obliga a que el átomo sea único ni a que haya máximo.

Las dos constantes no hacen lo mismo. El $0$ está determinado: un orden tiene a lo sumo un mínimo, así que en cada reticulado hay una sola forma de interpretarlo. $\text{ato}$ está sólo restringido: cualquier átomo sirve. Entonces cada reticulado finito da tantos modelos como átomos tiene: el rombo, dos; una cadena, uno. La constante determinada no agrega modelos; la elegida los multiplica.

El Ejercicio 25 es el contraste. Sobre el tipo con $0$, $1$ y $\text{mono}$, pide $\forall x\le (x,1)$, $\forall x\le (0,x)$, $\neg (\text{mono}=0)$ y $\forall x(\neg (x=0)\to \le (\text{mono},x))$. Los dos últimos juntos dicen que $i(\text{mono})$ está estrictamente arriba del mínimo y debajo de todo lo que está estrictamente arriba del mínimo: que lo tapa. Tapar fuerza unicidad, así que las tres constantes quedan determinadas, y los modelos son esencialmente los reticulados acotados cuyo mínimo está tapado. En uno finito, eso es que una sola arista salga hacia arriba del $0$; dicho de otra forma, un reticulado acotado cualquiera con un cero nuevo pegado abajo.

Las dos descripciones se pueden contar por separado. Por un lado, los modelos: sobre $\{1,\dots ,n\}$, todas las relaciones para $\le$, todas las tablas para $s$ y para $i$, todas las interpretaciones de las constantes, evaluando cada axioma de $\Sigma$ como sentencia. Por el otro, el orden: los reticulados rotulados de $n$ elementos, la suma de sus átomos, y los que tienen el mínimo tapado.

La columna de reticulados es la conocida, 1, 2, 6, 36, que es el control de que la enumeración no se salteó ninguno. Con dos elementos se recorrieron todas las estructuras del tipo, 16 384 para el Ejercicio 24 y 32 768 para el 25, y en cada una hay exactamente dos modelos. Con más elementos la enumeración aprovecha que los axiomas de $s$ y de $i$ hablan de cada casilla de la tabla por separado: se cuenta cuántos valores sirven en cada una y se multiplica. La fila de cuatro es la que separa. Los 36 reticulados son 24 cadenas y 12 rombos rotulados; cada cadena da un modelo de cada ejercicio, y cada rombo da dos del 24 —uno por átomo— y ninguno del 25, porque su mínimo tiene dos aristas hacia arriba y nadie lo tapa.

07 · Lo que rompe la búsqueda chica

El contraejemplo es la mitad fácil: si aparece un modelo donde $\phi$ falla, está demostrado que no hay prueba. Lo que no vale es la otra dirección con modelos chicos. Que $\phi$ valga en todos los modelos de hasta tal tamaño no prueba nada, y ya aparecieron dos casos.

El tamaño equivocado. «Hay un punto fijo» vale en los 1, 4, 26 y 232 modelos de uno, tres, cinco y siete elementos: 263 modelos sin un solo contraejemplo. El contraejemplo existe, y tiene dos elementos.

Ningún modelo finito. El ejemplo E7 de la Guía 8, pág. 22, toma el tipo $(\{\text{ex}\},\{F\},\varnothing ,\{(F,1)\})$ y dos axiomas: $F$ es inyectiva y $\text{ex}$ no está en su imagen. Una función inyectiva de un conjunto finito en sí mismo es suryectiva, así que en un universo finito los dos axiomas no pueden valer juntos. Contado: sobre uno a cinco elementos hay 1, 8, 81, 1024 y 15 625 estructuras del tipo, y ningún modelo. Y la teoría tiene modelos: $(\omega ,\{(\text{ex},0),(F,\mathrm{Suc})\})$, los naturales con el sucesor. Una búsqueda por computadora sobre universos chicos no encuentra ni uno, y de ahí no se puede sacar que no haya. En el widget es la segunda teoría.

Por eso el reparto de trabajo es asimétrico. Para decir que algo no se prueba, se exhibe un modelo y se verifica, axioma por axioma, que lo es. Para decir que algo sí se prueba, se escribe la prueba: ninguna cantidad de modelos revisados la reemplaza.

Para tener a mano

1. Teoría elemental: $(\Sigma ,\tau )$, con $\Sigma$ sentencias elementales puras de tipo $\tau$. Es sintaxis. Modelo: estructura de tipo $\tau$ donde valen todas las de $\Sigma$.
2. Puras quiere decir sin nombres de elementos fijos. Los nombres de constante del tipo sí pueden aparecer.
3. Probar en $(\Sigma ,\tau )$: partir de un modelo fijo pero arbitrario, del que sólo se sabe que cumple $\Sigma$. Verdadera en un modelo, o en algunos, no es probada.
4. Corrección: lo que se prueba vale en todo modelo. Al revés: un modelo donde $\phi$ falla demuestra que $\phi$ no se prueba. Hay que verificar las dos cosas: que es modelo y que falla.
5. En el Ejercicio 22, ni «hay un punto fijo» ni su negación se prueban: el intercambio de dos elementos refuta una, la identidad la otra.
6. Esencialmente: desarmar $i$ en la tupla $(A,i(p),\dots )$. Los modelos de la teoría de los posets son esencialmente los posets, y así con cada tipo.
7. Con constantes, la tupla trae elementos distinguidos. Una constante que los axiomas determinan (el $0$) no multiplica los modelos; una que sólo restringen ($\text{ato}$) da uno por cada elección.
8. Que algo valga en todos los modelos chicos no prueba nada: «hay un punto fijo» vale en todos los de tamaño impar, y la teoría E7 de la guía no tiene ningún modelo finito.