Fórmulas de tipo τ y su lectura única

Una fórmula de tipo $\tau$ es una palabra, igual que un término: se arma por niveles a partir de las atómicas, y se lee de una sola manera. Lo que la separa de los términos es una asimetría. Una fórmula nunca es el principio de otra, pero sí puede ser su final: $\neg \phi$ termina en $\phi$. Y cuando eso pasa, lo que sobra adelante es siempre una cadena de negaciones y cuantificadores. De ese hecho salen la lectura única y todas las pruebas que comparan dos fórmulas por atrás.

01 · Las fórmulas atómicas

La Guía 9, en la página 9, las define así. Dado un tipo $\tau$, las fórmulas atómicas de tipo $\tau$ son las palabras de alguna de estas dos formas:

• $(t\equiv s)$, con $t,s\in T^{\tau }$;
• $r(t_1,\dots ,t_n)$, con $r\in R_n$, $n\ge 1$ y $t_1,\dots ,t_n\in T^{\tau }$.

Son palabras armadas por concatenación, no expresiones que denotan algo: $r(t_1,\dots ,t_n)$ es el resultado de concatenar las $n+(n-1)+3$ palabras

$$r(t_1,t_2,\dots ,t_n)$$

Por eso la longitud sale de sumar las piezas, como la de un término:

$$|(t\equiv s)|=|t|+|s|+3$$ $$|r(t_1,\dots ,t_n)|=|r|+|t_1|+\cdots +|t_n|+(n-1)+2$$

El 3 de la primera son los dos paréntesis y el $\equiv$; en la segunda, $n-1$ cuenta las comas y el 2 los paréntesis. Con el tipo de la guía $\tau =(\{\mathrm{uno},\mathrm{doli}\},\{\mathrm{MAS},\mathrm{P}\},\{\mathrm{Her}\},a)$, con $a(\mathrm{MAS})=4$, $a(\mathrm{P})=1$ y $a(\mathrm{Her})=3$: $(\mathrm{uno}\equiv \mathrm{doli})$ tiene longitud $3+4+3=10$; $\mathrm{Her}(\mathrm{uno},\mathrm{X}4,\mathrm{doli})$, $3+(3+2+4)+2+2=16$, porque la variable $\mathrm{X}4$ son dos símbolos; y $\mathrm{Her}(\mathrm{P}(\mathrm{P}(\mathrm{uno})),\mathrm{MAS}(\mathrm{P}(\mathrm{X}4),\mathrm{doli},\mathrm{X}19,\mathrm{X}5),\mathrm{X}19)$, $3+(9+22+3)+2+2=41$.

Tres detalles de la definición que deciden ejercicios. La igualdad va siempre entre paréntesis: $(t\equiv s)$ es atómica y $t\equiv s$ no es nada. No hay relaciones de aridad 0, así que toda atómica lleva paréntesis. Y $\equiv$ es un símbolo del alfabeto, no un nombre del tipo: está en todas las fórmulas de todos los tipos, y ningún nombre de constante, función o relación lo puede usar.

02 · Los niveles

Con las atómicas como piso, la guía arma los conjuntos $F_k^{\tau }$ por recursión en $k$:

$$F_0^{\tau }=\text{fórmulas atómicas de tipo }\tau$$

y $F_{k+1}^{\tau }$ es $F_k^{\tau }$ más tres clases de palabras nuevas, todas hechas con fórmulas de $F_k^{\tau }$:

• $\neg \phi$, con $\phi \in F_k^{\tau }$;
• $(\phi \eta \psi )$, con $\phi ,\psi \in F_k^{\tau }$ y $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$;
• $Qv\phi$, con $\phi \in F_k^{\tau }$, $Q\in \{\forall ,\exists \}$ y $v\in \mathrm{Var}$.

Las fórmulas de tipo $\tau$ son los elementos de $F^{\tau }={\bigcup }_{k\ge 0}{F}_k^{\tau }$. Otra vez, todo es concatenación: $(\phi \wedge \psi )$ es la concatenación de las cinco palabras $(\phi \wedge \psi )$, y $\forall v\phi$ la de las tres palabras $\forall v\phi$.

Hay que mirar dónde van los paréntesis. Sólo los nexos binarios los agregan, uno de cada lado. $\neg$ y $Qv$ se pegan adelante y no agregan nada atrás: $\forall \mathrm{X}1(\mathrm{X}1\equiv \mathrm{X}1)$ es una fórmula y $\forall \mathrm{X}1\mathrm{X}1\equiv \mathrm{X}1$ no. Ese detalle es toda la asimetría de la sección 06.

Como $F_k^{\tau }\subseteq F_{k+1}^{\tau }$, una fórmula está en todos los niveles a partir de uno; el nivel de una fórmula es el mínimo. Los ejemplos de la guía (página 10), leídos de afuera hacia adentro: los cinco de (E1) con el tipo de arriba, y los seis de (E2) con $\tau =(\{0,1\},\{\mathrm{s},\mathrm{i}\},\{\mathrm{\le }\},\{(\mathrm{s},2),(\mathrm{i},2),(\mathrm{\le },2)\})$.

El nivel no mide el largo. La cuarta fórmula tiene 37 símbolos y la quinta 61, y las dos son de nivel 4. Lo que cuenta es la cadena más larga de construcciones: en la quinta, $\mathrm{Her}(\mathrm{doli},\mathrm{doli},\mathrm{doli})$ es atómica, pero del otro lado del $\to$ hay tres cuantificadores apilados sobre una igualdad, y $3+1=4$. Y la conjunción de (E2) tiene 27 símbolos y es de nivel 1: sus dos miembros son atómicos.

La guía cierra con un contraejemplo: $(\mathrm{X}1\le \mathrm{X}2)$ no es una fórmula de ese tipo, aunque $\mathrm{\le }\in R_2$. Los nombres de relación van adelante, como los de función: la fórmula es $\mathrm{\le }(\mathrm{X}1,\mathrm{X}2)$. Leída de afuera, $(\mathrm{X}1\le \mathrm{X}2)$ empieza con $($, así que sólo podría ser $(t\equiv s)$ o $(\phi \eta \psi )$; y adentro del paréntesis de afuera no hay ningún $\equiv$ ni ningún nexo. La guía avisa que probarlo «no es trivial de la definición»: cómo se escribe esa prueba está en Probar que una palabra no es término ni fórmula.

Las fórmulas de tipo $\tau$ son el modelo matemático de las fórmulas elementales puras de tipo $\tau$, las que no usan nombres de elementos fijos. La diferencia es de estatuto: «fórmula elemental» era una idea que se reconocía al verla; $F^{\tau }$ es un conjunto de palabras definido con precisión, del que se pueden probar cosas.

03 · El menú: Lema 5

Lema 5 (Menú para fórmulas). Sea $k\ge 0$. Si $\phi \in F_{k+1}^{\tau }$, entonces se da alguna de las siguientes:

1. $\phi =(t\equiv s)$, con $t,s\in T^{\tau }$;
2. $\phi =r(t_1,\dots ,t_n)$, con $r\in R_n$, $n\ge 1$, $t_1,\dots ,t_n\in T^{\tau }$;
3. $\phi =({\phi }_1\eta {\phi }_2)$, con $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$, ${\phi }_1,{\phi }_2\in F_k^{\tau }$;
4. $\phi =\neg {\phi }_1$, con ${\phi }_1\in F_k^{\tau }$;
5. $\phi =Qv{\phi }_1$, con $Q\in \{\forall ,\exists \}$, $v\in \mathrm{Var}$ y ${\phi }_1\in F_k^{\tau }$.

Parece la definición repetida, y no lo es. La definición dice que $F_{k+1}^{\tau }$ es $F_k^{\tau }$ unión las palabras nuevas; una fórmula de $F_{k+1}^{\tau }$ puede venir de $F_k^{\tau }$, y ésa a su vez de $F_{k-1}^{\tau }$, y así hasta abajo. El lema dice que no importa: igual tiene una de las cinco formas, con piezas un nivel más abajo.

Se prueba con la Regla de Inducción desde 0, tomando como ${\mathrm{Enu}}_k$ el enunciado mismo. ${\mathrm{Enu}}_0$ sale directo de la definición de $F_1^{\tau }$. Para el paso, si vale ${\mathrm{Enu}}_k$ y $\phi \in F_{k+2}^{\tau }$, hay dos casos. Si $\phi \in F_{k+1}^{\tau }$, ${\mathrm{Enu}}_k$ da una de las cinco formas con piezas en $F_k^{\tau }\subseteq F_{k+1}^{\tau }$, que es la conclusión de ${\mathrm{Enu}}_{k+1}$. Si no, $\phi$ es $\neg {\phi }_1$, $({\phi }_1\eta {\phi }_2)$ o $Qv{\phi }_1$ con piezas en $F_{k+1}^{\tau }$, y eso ya es la conclusión. El molde de esta inducción, y por qué el $k$ va cuantificado adentro de ${\mathrm{Enu}}_k$, está en Inducción en la construcción.

Lo que el lema no dice es que la forma sea una sola, ni que las piezas sean únicas: «alguna de las siguientes». Eso es el Teorema 7, y para llegar hace falta el mordisqueo.

04 · El mordisqueo: Proposición 6

Dos palabras se solapan cuando el final de una es el principio de la otra. La guía, en la página 12, acepta sin prueba lo que pasa cuando las dos son fórmulas:

Proposición 6 (Mordisqueo de fórmulas). Si $\phi ,\psi \in F^{\tau }$ y $x,y,z$ son palabras tales que $\phi =xy$, $\psi =yz$ e $y\ne \epsilon$, entonces $z=\epsilon$ y

$$x\in (\{\neg \}\cup \{Qv:Q\in \{\forall ,\exists \},v\in \mathrm{Var}\}{)}^{*}$$

En particular, ningún tramo inicial propio de una fórmula es una fórmula, y ningún tramo final propio de una fórmula atómica es una fórmula.

Leída despacio: si el final de $\phi$ se superpone con el principio de $\psi$, la superposición se traga a $\psi$ entera ($z=\epsilon$, así que $\psi =y$ es tramo final de $\phi$), y lo que queda de $\phi$ adelante es una tira de bloques, cada uno un $\neg$ o un cuantificador con su variable. Por ejemplo, con $\phi =\neg \forall \mathrm{X}1(\mathrm{X}1\equiv \mathrm{X}2)$ y $\psi =(\mathrm{X}1\equiv \mathrm{X}2)$, el corte es $x=\neg \forall \mathrm{X}1$, $y=\psi$, $z=\epsilon$: dos bloques, $\neg$ y $\forall \mathrm{X}1$. Con $\psi =\forall \mathrm{X}1(\mathrm{X}1\equiv \mathrm{X}2)$ en cambio, $x=\neg$: un bloque.

Las dos consecuencias «en particular» salen de elegir bien las tres palabras. Si $\phi$ fuera tramo inicial propio de $\psi$, sería $x=\epsilon$ e $y=\phi$, y la conclusión $z=\epsilon$ diría que $\psi =\phi$. Si $\psi$ fuera tramo final propio de una atómica $\phi$, el $x$ no vacío tendría que empezar con $\neg$, $\forall$ o $\exists$, y una atómica empieza con $($ o con un nombre de relación.

La guía no la prueba. El apunte sí, borrando de las palabras todo lo que no es paréntesis. Lo que queda de una fórmula es una palabra balanceada, como lo que queda de $\phi =xy$ y de $\psi =yz$; y como $\phi$ termina en $)$, lo que queda de $y$ no es vacío. El balanceo obliga a que $y$ se quede con todos los paréntesis de $\phi$ y de $\psi$: $x$ y $z$ no tienen ninguno. Como $\psi$ termina en $)$, eso fuerza $z=\epsilon$. Y una palabra sin paréntesis que puesta delante de una fórmula da otra fórmula sólo puede ser una cadena de $\neg$ y $Qv$, que se ve por inducción en el nivel de $\phi$.

05 · Por adelante, nunca

La mitad fácil es el Ejercicio 16:

Pruebe que si $\phi ,\psi \in F^{\tau }$, entonces $\phi$ no puede ser tramo inicial propio de $\psi$ (Hint: elija bien $x,y$ y $z$ y aplique la proposición anterior).

Prueba. Supongamos que $\phi$ es tramo inicial propio de $\psi$: $\psi =\phi w$ con $w\ne \epsilon$. Tomemos $x=\epsilon$, $y=\phi$, $z=w$. Entonces $\phi =xy$, $\psi =yz$ e $y\ne \epsilon$, porque ninguna fórmula es vacía. Por la Proposición 6, $z=\epsilon$, o sea $w=\epsilon$. Absurdo. ∎

Con esto se cancela por adelante, que es el Ejercicio 18: si ${\psi }_1{\psi }_2={\phi }_1{\phi }_2$ con las cuatro fórmulas, ${\psi }_1$ y ${\phi }_1$ son tramos iniciales de la misma palabra, así que uno es tramo inicial del otro; por el Ejercicio 16 ninguno lo es propio, y entonces ${\psi }_1={\phi }_1$. Sacando ese tramo de las dos escrituras, ${\psi }_2={\phi }_2$. Es la misma cancelación que con términos, y la que va a usar el Teorema 7 en su forma (3).

06 · Por atrás, sí

Con los términos, el mordisqueo es simétrico. El Lema 2 de la guía da $x=z=\epsilon$, salvo el caso de dos constantes que se mordisquean: un término no es tramo inicial ni tramo final propio de otro. La Proposición 6 da sólo $z=\epsilon$, y $x$ puede no ser vacía. $(\mathrm{X}1\equiv \mathrm{X}2)$ es tramo final propio de $\neg (\mathrm{X}1\equiv \mathrm{X}2)$, y de $\forall \mathrm{X}1(\mathrm{X}1\equiv \mathrm{X}2)$, y de $\neg \exists \mathrm{X}2\forall \mathrm{X}1(\mathrm{X}1\equiv \mathrm{X}2)$. La razón está en la sección 02: $\neg$ y $Qv$ construyen agregando sólo adelante, así que la fórmula de la que se partió queda intacta al final de la nueva. Los nexos binarios, en cambio, la encierran entre paréntesis.

Lo que la Proposición 6 agrega es que ésa es la única manera. Si una fórmula es tramo final propio de otra, lo que sobra adelante es exactamente una cadena de esos prefijos. Medido sobre 3370 fórmulas distintas del tipo $(\{0\},\{\mathrm{f}\},\{r\},\{(\mathrm{f},1),(r,1)\})$, armadas desde las atómicas $(\mathrm{X}1\equiv \mathrm{X}2)$, $(\mathrm{X}1\equiv 0)$, $(0\equiv 0)$, $r(\mathrm{X}1)$, $r(\mathrm{f}(0))$ y $(\mathrm{f}(\mathrm{X}2)\equiv \mathrm{X}1)$ con dos capas de $\neg$, $\forall \mathrm{X}1$, $\exists \mathrm{X}2$, $\wedge$ y $\to$, y hasta 26 símbolos: de los 11 356 900 pares ordenados, en 3712 el final de la primera coincide con el principio de la segunda, con $y\ne \epsilon$. Así se reparten:

Los 288 son 96 de cada bloque, y los 54 son 6 de cada uno de los nueve pares de bloques: con dos capas no hay más. En los 342 tramos finales propios lo que sobra adelante se parte en negaciones y cuantificadores, y ninguno de los 3712 contradice la Proposición 6. La primera fila es el control: cualquier fórmula se solapa consigo misma, y si no apareciera, la cuenta estaría mal.

Esa forma de lo que sobra es lo que se usa para comparar por atrás. El Ejercicio 19 pide probar que si $(\alpha \wedge \beta ),\beta \in F^{\tau }$, entonces $\alpha \in F^{\tau }$. Como $(\alpha \wedge \beta )$ empieza con $($ y tiene un $\wedge$, el Teorema 7 la da de la forma (3): $(\alpha \wedge \beta )=({\phi }_1\eta {\phi }_2)$ con ${\phi }_1,{\phi }_2\in F^{\tau }$, y sacando los paréntesis de afuera, $\alpha \wedge \beta ={\phi }_1\eta {\phi }_2$. Lo que se sabe fórmula es $\beta$, así que se compara por el final: $\beta$ y ${\phi }_2$ son tramos finales de la misma palabra, y uno es tramo final del otro. Acá el Ejercicio 16 no sirve, porque por atrás una fórmula sí puede ser tramo final propio de otra. Pero si lo fuera, lo que sobra adelante sería una cadena de $\neg$ y $Qv$, y una cadena así termina en $\neg$ o en el numeral negrita de una variable. Y su último símbolo es el que va justo antes del tramo final más corto en la otra escritura: el $\wedge$ de $\alpha \wedge \beta$ si lo que sobra está adelante de $\beta$, el $\eta$ de ${\phi }_1\eta {\phi }_2$ si está adelante de ${\phi }_2$. Los dos son nexos. Así que no sobra nada, $\beta ={\phi }_2$, y cancelando, $\eta =\wedge$ y $\alpha ={\phi }_1$. La prueba entera, con sus dos casos, está en Una fórmula puede ser el final de otra, nunca el principio.

La hipótesis $\beta \in F^{\tau }$ no es decorativa. El Ejercicio 13 pregunta si de $(\alpha \wedge \beta )\in F^{\tau }$ sale que $\alpha ,\beta \in F^{\tau }$, y es falso: en $(((\mathrm{X}1\equiv \mathrm{X}2)\wedge (\mathrm{X}1\equiv \mathrm{X}1))\wedge (\mathrm{X}2\equiv \mathrm{X}2))$, que es de nivel 2, tomar el primer $\wedge$ como separador da $\alpha =((\mathrm{X}1\equiv \mathrm{X}2)$, con dos paréntesis que abren y uno que cierra, que no es fórmula. Es el corte equivocado de Un corte equivocado rompe las dos piezas, y está resuelto en Contar paréntesis no alcanza.

07 · La lectura única: Teorema 7

Teorema 7 (Lectura única de fórmulas). Dada $\phi \in F^{\tau }$ se da una y sólo una de las siguientes:

1. $\phi =(t\equiv s)$, con $t,s\in T^{\tau }$, únicos;
2. $\phi =r(t_1,\dots ,t_n)$, con $r\in R_n$, $t_1,\dots ,t_n\in T^{\tau }$, únicos;
3. $\phi =({\phi }_1\eta {\phi }_2)$, con $\eta \in \{\wedge ,\vee ,\to ,\leftrightarrow \}$, ${\phi }_1,{\phi }_2\in F^{\tau }$, únicos;
4. $\phi =\neg {\phi }_1$, con ${\phi }_1\in F^{\tau }$, única;
5. $\phi =Qv{\phi }_1$, con $Q\in \{\forall ,\exists \}$, ${\phi }_1\in F^{\tau }$ y $v\in \mathrm{Var}$, únicos.

Más aún, si $\phi \in F_{k+1}^{\tau }$, cuando se da (3) las fórmulas ${\phi }_1$ y ${\phi }_2$ están en $F_k^{\tau }$, y cuando se da (4) o (5) la fórmula ${\phi }_1$ está en $F_k^{\tau }$.

Que se dé alguna es el Lema 5 (y, para las atómicas, la definición de $F_0^{\tau }$). Lo nuevo son el «sólo una» y los «únicos», y la guía deja completarlos en el Ejercicio 17.

Las formas se excluyen por el primer símbolo:

Ningún nombre del tipo usa $($, $\neg$, $\forall$ ni $\exists$, así que (2), (4) y (5) se separan entre sí y de las otras dos. Sólo el $($ deja dos formas abiertas, y las separa un nexo: en $(t\equiv s)$ no ocurre ninguno, porque los términos no los tienen, y en $({\phi }_1\eta {\phi }_2)$ ocurre $\eta$. Cómo este cuadro se vuelve un procedimiento que decide si una palabra es fórmula está en El primer símbolo ya dice qué forma tiene.

Las piezas son únicas, forma por forma:

• (1) Los términos no contienen $\equiv$: en $t\equiv s$ hay uno solo, y lo de antes es $t$ y lo de después $s$.
• (2) Los nombres de relación no tienen paréntesis, así que $r$ es todo lo anterior al primer $($, y su aridad fija $n$. Los argumentos salen como en la lectura única de términos: $t_1$ y $s_1$ son tramos iniciales de la misma palabra, el mordisqueo de términos los iguala, se cancela $t_1$ con su coma y se repite.
• (3) Si $({\phi }_1\eta {\phi }_2)=({\psi }_1{\eta }^{\prime }{\psi }_2)$, entonces ${\phi }_1\eta {\phi }_2={\psi }_1{\eta }^{\prime }{\psi }_2$; ${\phi }_1$ y ${\psi }_1$ son tramos iniciales de la misma palabra y, por el Ejercicio 16, iguales. Cancelando, $\eta ={\eta }^{\prime }$ y ${\phi }_2={\psi }_2$.
• (4) Se cancela el $\neg$.
• (5) El primer símbolo da $Q$. La variable empieza en la posición 2 y termina en su único numeral negrita, que es el primer negrita desde ahí; eso la fija, y cancelando $Qv$, también ${\phi }_1$.

Los niveles. Si $\phi \in F_{k+1}^{\tau }$ es de la forma (3), el Lema 5 la escribe como alguna de (a) a (e) con piezas en $F_k^{\tau }$; como las formas se excluyen, tiene que ser la (c), $\phi =({\psi }_1{\eta }^{\prime }{\psi }_2)$ con ${\psi }_1,{\psi }_2\in F_k^{\tau }$; y por la unicidad en (3), ${\phi }_1={\psi }_1$ y ${\phi }_2={\psi }_2$. Las formas (4) y (5) van igual, con (d) y (e).

Lo que habilita el teorema es definir funciones sobre $F^{\tau }$ por recursión en la forma: dar el valor en las atómicas y decir cómo se calcula en $\neg \phi$, $(\phi \eta \psi )$ y $Qv\phi$ a partir del valor en las piezas. Sin la unicidad, una misma fórmula podría recibir dos valores, uno por cada manera de leerla. Así se definen la ocurrencia libre y $\mathrm{Li}(\phi )$, en Variables libres, y más adelante la verdad de una fórmula en una estructura.

Para tener a mano

1. Atómicas: $(t\equiv s)$ y $r(t_1,\dots ,t_n)$ con $n\ge 1$. $|(t\equiv s)|=|t|+|s|+3$; la de $r(t_1,\dots ,t_n)$ suma $|r|$, los $|t_i|$, $n-1$ comas y 2 paréntesis.
2. $F_{k+1}^{\tau }=F_k^{\tau }$ más $\neg \phi$, $(\phi \eta \psi )$ y $Qv\phi$ con piezas de $F_k^{\tau }$. Sólo los nexos binarios agregan paréntesis. El nivel es el mínimo $k$, y no mide el largo.
3. $(\mathrm{X}1\le \mathrm{X}2)$ no es fórmula: el nombre de relación va adelante, $\mathrm{\le }(\mathrm{X}1,\mathrm{X}2)$.
4. Lema 5: toda $\phi \in F_{k+1}^{\tau }$ tiene alguna de las cinco formas, con piezas en $F_k^{\tau }$. Se prueba por inducción desde 0.
5. Proposición 6: si $\phi =xy$, $\psi =yz$ e $y\ne \epsilon$, entonces $z=\epsilon$ y $x\in (\{\neg \}\cup \{Qv:Q\in \{\forall ,\exists \},v\in \mathrm{Var}\}{)}^{*}$.
6. Por adelante, nunca (Ejercicio 16): $x=\epsilon$, $y=\phi$, $z=w$. Da la cancelación ${\psi }_1{\psi }_2={\phi }_1{\phi }_2\Rightarrow {\psi }_1={\phi }_1$ (Ejercicio 18).
7. Por atrás, sí: $\phi$ es tramo final propio de $\neg \phi$ y de $\forall \mathrm{X}1\phi$. Lo que sobra adelante termina en $\neg$ o en un numeral negrita, nunca en un nexo ni en un paréntesis: así se cancela por atrás (Ejercicio 19).
8. Teorema 7: el primer símbolo decide la forma: $($, un nombre de relación, $\neg$, $\forall$ o $\exists$. Si es $($, decide si hay nexo. Las piezas son únicas y bajan un nivel.
9. Sin hipótesis no se cancela: $(\alpha \wedge \beta )\in F^{\tau }$ no dice que $\alpha$ sea fórmula (Ejercicio 13).