Variables libres

Que una variable sea libre o acotada no es una propiedad de la variable: es una propiedad de cada lugar donde aparece. La misma $\mathrm{X}2$ puede ser libre en la posición 6 de una fórmula y acotada en la 11 de esa misma fórmula. Por eso la Guía 9 la define por posición, y la define recursivamente: para saber qué pasa en la posición $i$, se desarma la fórmula de afuera hacia adentro, se corre la posición cada vez que se saca un pedazo de adelante, y el camino sólo se corta si aparece un cuantificador con la misma variable.

01 · Ocurrir a partir de una posición

La definición se apoya en una anterior. Dadas palabras $\alpha ,\beta$ con $|\alpha |,|\beta |\ge 1$ y $i\in \{1,\dots ,|\beta |\}$, $\alpha$ ocurre a partir de $i$ en $\beta$ si hay palabras $\delta ,\gamma$ tales que $\beta =\delta \alpha \gamma$ y $|\delta |=i-1$: empezando a leer $\beta$ desde su símbolo $i$-ésimo se lee $\alpha$ entera, y después quizás siguen otros símbolos.

Las posiciones se cuentan sobre la palabra, símbolo por símbolo. En $\mathrm{Her}(\mathrm{doli},\mathrm{doli},\mathrm{X}9)$ el nombre $\mathrm{Her}$ son tres símbolos y $\mathrm{doli}$ son cuatro, porque los nombres del tipo son palabras; la variable $\mathrm{X}9$ son dos, la $\mathrm{X}$ y el numeral. Contando así, la palabra tiene 17 símbolos y $\mathrm{X}9$ ocurre a partir de 15. Y como ninguna variable es subpalabra de otra —el último numeral es el único en negrita—, en cada posición empieza a lo sumo una variable: si en la posición $i$ hay una $\mathrm{X}$, queda determinado cuál.

02 · La definición, cláusula por cláusula

Sean $v\in \mathrm{Var}$, $\phi \in F^{\tau }$ e $i\in \{1,\dots ,|\phi |\}$. La relación «$v$ ocurre libremente en $\phi$ a partir de $i$» se define según la forma de $\phi$:

1. (1) AtómicaSi $\phi$ es $(t\equiv s)$ o $r(t_1,\dots ,t_n)$: $v$ ocurre libremente en $\phi$ a partir de $i$ si y sólo si $v$ ocurre en $\phi$ a partir de $i$.
2. (2) Con un nexoSi $\phi =({\phi }_1\eta {\phi }_2)$: si y sólo si se da alguna de estas dos: (a) $v$ ocurre libremente en ${\phi }_1$ a partir de $i-1$; (b) $v$ ocurre libremente en ${\phi }_2$ a partir de $i-|({\phi }_1\eta |$.
3. (3) NegaciónSi $\phi =\neg {\phi }_1$: si y sólo si $v$ ocurre libremente en ${\phi }_1$ a partir de $i-1$.
4. (4) CuantificadorSi $\phi =Qw{\phi }_1$: si y sólo si $v\ne w$ y $v$ ocurre libremente en ${\phi }_1$ a partir de $i-|Qw|$.

Y la otra mitad: $v$ ocurre acotadamente en $\phi$ a partir de $i$ cuando $v$ ocurre en $\phi$ a partir de $i$ y no ocurre libremente en $\phi$ a partir de $i$. No hay una definición aparte de «acotada»: es lo que queda. Y queda sólo entre las posiciones donde $v$ ocurre. En una posición donde $v$ no empieza —un paréntesis, un nexo, un numeral—, $v$ no ocurre ni libre ni acotadamente: libre y acotada no agotan los casos.

Que la recursión defina algo es la lectura única de fórmulas. Cada cláusula pregunta por la forma de $\phi$ y por sus piezas —${\phi }_1$, $\eta$, ${\phi }_2$, $Q$, $w$—, y si una fórmula pudiera leerse de dos maneras, la definición podría contestar dos cosas distintas. El Teorema 7 garantiza que no: cada fórmula no atómica tiene una sola forma y una sola descomposición. Y cada cláusula baja a una fórmula más corta, así que el camino termina siempre, en una atómica o en un cuantificador que lo corta.

03 · Por qué se corre la posición

La posición $i$ se cuenta en $\phi$. Cuando la recursión entra a ${\phi }_1$, la pregunta pasa a ser sobre ${\phi }_1$, y en ${\phi }_1$ las posiciones se cuentan desde su primer símbolo. El mismo símbolo tiene en la pieza la posición que tenía en $\phi$ menos la cantidad de símbolos que la pieza tiene delante. Eso es todo lo que miden los corrimientos.

Delante de ${\phi }_1$ en $({\phi }_1\eta {\phi }_2)$ hay un solo símbolo, el paréntesis: por eso $i-1$. Delante de ${\phi }_2$ están el paréntesis, ${\phi }_1$ entera y el nexo, o sea $|({\phi }_1\eta |$, que vale $|{\phi }_1|+2$. Delante de ${\phi }_1$ en $\neg {\phi }_1$ está el $\neg$, un símbolo. Y en $Qw{\phi }_1$ están el cuantificador y la variable: $|Qw|=1+|w|$, que depende de la variable. $\exists \mathrm{X}2$ tiene 3 símbolos y $\forall \mathrm{X}5559$ tiene 6.

El ejemplo de la guía, con las cuentas. Sea

$$((\mathrm{X}1\equiv \mathrm{X}2)\wedge \exists \mathrm{X}2\mathrm{Her}(\mathrm{P}(\mathrm{doli}),\mathrm{doli},\mathrm{X}2))$$

con 33 símbolos. Es de la forma $({\phi }_1\wedge {\phi }_2)$ con ${\phi }_1=(\mathrm{X}1\equiv \mathrm{X}2)$, de 7 símbolos, y ${\phi }_2=\exists \mathrm{X}2\mathrm{Her}(\mathrm{P}(\mathrm{doli}),\mathrm{doli},\mathrm{X}2)$, que empieza en la posición 10 porque $|({\phi }_1\wedge |=9$. La variable $\mathrm{X}2$ ocurre a partir de 6, de 11 y de 30.

Posición 6. La cláusula (2a) pregunta por ${\phi }_1$ a partir de $6-1=5$. ${\phi }_1$ es atómica, y $\mathrm{X}2$ ocurre en $(\mathrm{X}1\equiv \mathrm{X}2)$ a partir de 5. Libre.

Posición 11. La (2a) pediría ${\phi }_1$ a partir de 10, y ${\phi }_1$ tiene 7 símbolos: no se da. La (2b) pasa a ${\phi }_2$ a partir de $11-9=2$. ${\phi }_2$ es $Qw\psi$ con $w=\mathrm{X}2$, que es $v$: la cláusula (4) pide $v\ne w$ y falla. No es libre, y como $\mathrm{X}2$ ocurre ahí, es acotada. Es la $\mathrm{X}2$ pegada al $\exists$.

Posición 30. Lo mismo: ${\phi }_2$ a partir de $30-9=21$, y el $\exists \mathrm{X}2$ corta. Acotada. La cláusula (4) no mira la posición: si la variable del cuantificador es $v$, toda ocurrencia de $v$ que caiga debajo de él es acotada, sea la que lo acompaña o cualquiera de su alcance.

En la cláusula (2) sólo una de las dos alternativas puede darse, aunque la definición diga «alguna». Si $i$ cae dentro de ${\phi }_1$, el índice corrido de (b) da cero o negativo; si cae dentro de ${\phi }_2$, el de (a) se pasa del largo de ${\phi }_1$. En los dos casos esa alternativa no se da, y la recursión sigue por una sola rama: la de la pieza donde está el símbolo.

Así, el camino recorre exactamente las subfórmulas que contienen la posición $i$, de la más grande a la más chica. Es la versión precisa de lo que Fórmulas y sentencias elementales dice en castellano —una ocurrencia es acotada si está adentro de una subfórmula $\forall v\psi$ o $\exists v\psi$—, con un detalle: la recursión se corta en el primer $Qv$ que encuentra desde afuera, y lo que pase más adentro ya no importa.

La primera fórmula tiene a $\mathrm{X}2$ libre y acotada a la vez, en posiciones distintas, y la cuarta es la del Ejercicio 21 (a): $\mathrm{X}1$ es libre a partir de 3 y de 6 aunque $\forall \mathrm{X}1$ esté en la fórmula. En la sexta, $\mathrm{X}7$ a partir de 34 pasa por un $\neg$ (corre 1) y por un $\exists \mathrm{X}9$ que no la corta (corre 3) antes de que la corte $\forall \mathrm{X}7$. En la última, $\mathrm{X}1$ y $\mathrm{X}12$ conviven sin confundirse: en las posiciones donde empieza $\mathrm{X}12$ no empieza $\mathrm{X}1$.

04 · Los ejemplos de la guía, medidos

Los ejemplos de la página 15, con el tipo $\tau =(\{\mathrm{uno},\mathrm{doli}\},\{\mathrm{MAS},\mathrm{P}\},\{\mathrm{Her}\},a)$, $a(\mathrm{MAS})=4$, $a(\mathrm{P})=1$ y $a(\mathrm{Her})=3$. Cada posición es la de la $\mathrm{X}$ donde empieza la ocurrencia, contada símbolo por símbolo como en la sección 01:

La tercera, desarmada. Es $({\phi }_1\to {\phi }_2)$ con ${\phi }_1=\exists \mathrm{X}2\mathrm{Her}(\mathrm{X}2,\mathrm{X}7,\mathrm{uno})$, de 17 símbolos, y ${\phi }_2=\mathrm{Her}(\mathrm{X}2,\mathrm{X}7,\mathrm{uno})$, así que $|({\phi }_1\to |=19$. A partir de 3 y de 9, la (2a) baja a ${\phi }_1$ a partir de 2 y de 8, y ahí el $\exists \mathrm{X}2$ corta: acotadas, la que acompaña al cuantificador y la de su alcance. A partir de 24, la (2b) baja a ${\phi }_2$ a partir de $24-19=5$, que es atómica, y $\mathrm{X}2$ ocurre en $\mathrm{Her}(\mathrm{X}2,\mathrm{X}7,\mathrm{uno})$ a partir de 5: libre. La $\mathrm{X}7$, a partir de 12 y de 27, es libre las dos veces: el $\exists \mathrm{X}2$ no la corta, porque su variable es otra.

05 · Las variables libres de una fórmula y las sentencias

Con la relación por posición, la noción de variable libre de una fórmula sale sola. Dada una fórmula $\phi$,

$$\mathrm{Li}(\phi )=\{v\in \mathrm{Var}:\text{hay un }i\text{ tal que }v\text{ ocurre libremente en }\phi \text{ a partir de }i\}$$

Los elementos de $\mathrm{Li}(\phi )$ son las variables libres de $\phi$. Alcanza con una ocurrencia libre: $\mathrm{X}2$ está en $\mathrm{Li}(((\mathrm{X}1\equiv \mathrm{X}2)\wedge \exists \mathrm{X}2\mathrm{Her}(\mathrm{P}(\mathrm{doli}),\mathrm{doli},\mathrm{X}2)))$ por la posición 6, aunque tenga otras dos acotadas. Que $v$ aparezca cuantificada en algún lado no dice nada sobre si es libre.

Los dos $\mathrm{Li}$ que da la guía. Para

$$(\exists \mathrm{X}7(\mathrm{X}7\equiv \mathrm{X}6)\to ((\mathrm{X}1\equiv \mathrm{X}2)\wedge \exists \mathrm{X}2\mathrm{Her}(\mathrm{doli},\mathrm{doli},\mathrm{X}2)))$$

es $\mathrm{Li}(\phi )=\{\mathrm{X}1,\mathrm{X}2,\mathrm{X}6\}$. En sus 43 símbolos, $\mathrm{X}7$ ocurre a partir de 3 y de 6, y las dos veces la corta el $\exists \mathrm{X}7$; $\mathrm{X}6$ ocurre a partir de 9, dentro del alcance de $\exists \mathrm{X}7$, que no la corta; $\mathrm{X}1$ a partir de 15, libre; y $\mathrm{X}2$ a partir de 18, libre, y de 23 y 39, acotada por $\exists \mathrm{X}2$. Para $(\exists \mathrm{X}2\mathrm{Her}(\mathrm{X}2,\mathrm{X}7,\mathrm{uno})\to \mathrm{Her}(\mathrm{X}2,\mathrm{X}7,\mathrm{uno}))$, la de la sección anterior, $\mathrm{Li}(\phi )=\{\mathrm{X}2,\mathrm{X}7\}$: $\mathrm{X}2$ por la posición 24 y $\mathrm{X}7$ por cualquiera de las dos.

Una sentencia es una fórmula $\phi$ con $\mathrm{Li}(\phi )=\varnothing$, y $S^{\tau }$ es el conjunto de las sentencias de tipo $\tau$. $\exists \mathrm{X}9\mathrm{Her}(\mathrm{doli},\mathrm{doli},\mathrm{X}9)$ es una, y también $\neg \exists \mathrm{X}9\forall \mathrm{X}7(\mathrm{Her}(\mathrm{X}9,\mathrm{doli},\mathrm{X}7)\to (\mathrm{P}(\mathrm{doli})\equiv \mathrm{X}7))$: todas sus ocurrencias de variables son acotadas. Y como en una fórmula de tipo $\tau$ no hay nombres de elementos fijos, una sentencia de tipo $\tau$ es lo que en la Guía 7 era una sentencia elemental pura: queda decidida por la estructura sola, sin asignar nada.

06 · El Lema 10: las variables libres sin contar posiciones

Contar posiciones sirve para entender la definición; para calcular $\mathrm{Li}$ conviene el Lema 10, que lo hace de abajo hacia arriba siguiendo la forma de la fórmula. Sea $\tau$ un tipo.

1. $\mathrm{Li}((t\equiv s))=\{v\in \mathrm{Var}:v\text{ ocurre en }t\text{ o }v\text{ ocurre en }s\}$
2. $\mathrm{Li}(r(t_1,\dots ,t_n))=\{v\in \mathrm{Var}:v\text{ ocurre en algún }{t}_i\}$
3. $\mathrm{Li}(\neg \phi )=\mathrm{Li}(\phi )$
4. $\mathrm{Li}((\phi \eta \psi ))=\mathrm{Li}(\phi )\cup \mathrm{Li}(\psi )$
5. $\mathrm{Li}(Q{x}_j\phi )=\mathrm{Li}(\phi )-\{x_j\}$

(a) y (b) salen directo de la cláusula (1): en una atómica, ocurrir libremente a partir de $i$ es ocurrir a partir de $i$, y una variable que ocurre en una atómica ocurre adentro de alguno de sus términos, porque los otros símbolos —el nombre de relación, los paréntesis, las comas, el $\equiv$— no tienen ninguna $\mathrm{X}$.

Prueba de (d). Supongamos $v\in \mathrm{Li}((\phi \eta \psi ))$. Hay un $i$ tal que $v$ ocurre libremente en $(\phi \eta \psi )$ a partir de $i$. Por la cláusula (2), $v$ ocurre libremente en $\phi$ a partir de $i-1$ o en $\psi$ a partir de $i-|(\phi \eta |$, y en cualquiera de los dos casos $v\in \mathrm{Li}(\phi )\cup \mathrm{Li}(\psi )$. Recíprocamente, supongamos $v\in \mathrm{Li}(\phi )\cup \mathrm{Li}(\psi )$. Si $v\in \mathrm{Li}(\psi )$, hay un $i$ tal que $v$ ocurre libremente en $\psi$ a partir de $i$; tomando la posición $i+|(\phi \eta |$ de $(\phi \eta \psi )$, la (2b) la lleva exactamente a esa, así que $v$ ocurre libremente en $(\phi \eta \psi )$ a partir de $i+|(\phi \eta |$ y $v\in \mathrm{Li}((\phi \eta \psi ))$. Si $v\in \mathrm{Li}(\phi )$, lo mismo con $i+1$ y la (2a). ∎

Prueba de (c). Es la de (d) con una sola pieza y el corrimiento de 1: la posición $i$ de $\neg \phi$ va a la $i-1$ de $\phi$, y la $i$ de $\phi$ viene de la $i+1$ de $\neg \phi$. ∎

Prueba de (e). Supongamos $v\in \mathrm{Li}(Q{x}_j\phi )$. Hay un $i$ tal que $v$ ocurre libremente en $Q{x}_j\phi$ a partir de $i$. Por la cláusula (4), $v\ne x_j$ y $v$ ocurre libremente en $\phi$ a partir de $i-|Q{x}_j|$, así que $v\in \mathrm{Li}(\phi )-\{x_j\}$. Recíprocamente, supongamos $v\in \mathrm{Li}(\phi )-\{x_j\}$. Hay un $i$ tal que $v$ ocurre libremente en $\phi$ a partir de $i$, y como $v\ne x_j$, la cláusula (4) dice que $v$ ocurre libremente en $Q{x}_j\phi$ a partir de $i+|Q{x}_j|$. Así que $v\in \mathrm{Li}(Q{x}_j\phi )$. ∎

Las dos pruebas son la misma idea: la cláusula de la definición traduce posiciones de la fórmula en posiciones de la pieza, y la traducción se puede deshacer sumando lo que se había restado. Lo único que no se deshace es la condición $v\ne x_j$, y por eso (e) es la única con una resta de conjuntos.

Con el lema, el primer ejemplo de la sección anterior se calcula sin contar nada. $\mathrm{Li}((\mathrm{X}7\equiv \mathrm{X}6))=\{\mathrm{X}6,\mathrm{X}7\}$ por (a), y el $\exists \mathrm{X}7$ saca a $\mathrm{X}7$ por (e): queda $\{\mathrm{X}6\}$. Del otro lado, $\mathrm{Li}((\mathrm{X}1\equiv \mathrm{X}2))=\{\mathrm{X}1,\mathrm{X}2\}$; $\mathrm{Li}(\mathrm{Her}(\mathrm{doli},\mathrm{doli},\mathrm{X}2))=\{\mathrm{X}2\}$ por (b), y el $\exists \mathrm{X}2$ la vacía. Por (d), la conjunción da $\{\mathrm{X}1,\mathrm{X}2\}$, y la implicación $\{\mathrm{X}1,\mathrm{X}2,\mathrm{X}6\}$.

07 · Nombres de elementos fijos: extender el tipo

En una fórmula de tipo $\tau$ no hay nombres de elementos fijos, así que las fórmulas de tipo $\tau$ modelan sólo las fórmulas elementales puras. Pero una prueba elemental los usa todo el tiempo: «sean $a$, $b$ fijos pero arbitrarios», «sea $c$ tal que…». La página 16 de la guía resuelve eso sin agregar nada nuevo a la sintaxis: el nombre fijo se vuelve un nombre de constante.

Si $\tau =(C,F,R,a)$ es un tipo, un tipo ${\tau }^{\prime }$ es una extensión de $\tau$ por nombres de constante si es de la forma ${\tau }^{\prime }=(C^{\prime },F,R,a)$ con $C\subseteq C^{\prime }$. Sólo crecen las constantes: los nombres de función y de relación, y sus aridades, son los mismos.

La razón está en cómo trabaja el matemático. Una prueba elemental en una teoría $(\Sigma ,\tau )$ empieza imaginando una estructura de tipo $\tau$ de la que sólo sabe que cumple las sentencias de $\Sigma$. Cuando fija un elemento y le pone nombre, digamos $b$, se puede pensar que expandió su estructura imaginaria a una de tipo $(C\cup \{b\},F,R,a)$: la misma estructura, con un elemento más señalado por un nombre. Cada «sea» vuelve a hacerlo, así que a lo largo de la prueba el tipo va creciendo. Por eso lo natural es modelar las fórmulas elementales de tipo $\tau$ con fórmulas de tipo ${\tau }_1$, donde ${\tau }_1$ es alguna extensión de $\tau$ por nombres de constante.

Con el tipo de la sección 04, $\mathrm{Her}(b,\mathrm{doli},\mathrm{X}9)$ no es una fórmula de tipo $\tau$: al leerla, su primer argumento $b$ no es un término, porque $b$ no es una variable ni un nombre de constante de $\tau$. Sí es una fórmula de tipo ${\tau }_1=(\{\mathrm{uno},\mathrm{doli},b\},\{\mathrm{MAS},\mathrm{P}\},\{\mathrm{Her}\},a)$, con 14 símbolos y $\mathrm{Li}=\{\mathrm{X}9\}$. Y $\forall \mathrm{X}9\mathrm{Her}(b,\mathrm{doli},\mathrm{X}9)$ es una sentencia de tipo ${\tau }_1$: el $b$ no es una variable, así que no es ni libre ni acotado, y la única variable está cuantificada.

Eso precisa lo que Fórmulas y sentencias elementales dejaba dicho de $\forall x(a\le x)$: es una sentencia y su valor de verdad depende de qué elemento nombre $a$. Ahora la frase tiene su tipo: es una sentencia de una extensión que tiene a $a$ entre sus constantes, y una estructura de ese tipo extendido incluye el valor de $a$. Lo que se prueba —una sentencia de tipo $\tau$, sin nombres— no depende de ninguno.

Para tener a mano

1. Libre o acotada es una propiedad de cada ocurrencia: «$v$ ocurre libremente en $\phi$ a partir de $i$». La misma variable puede ser las dos cosas en una fórmula.
2. La definición desarma $\phi$ de afuera hacia adentro. Atómica: libre si ocurre. $({\phi }_1\eta {\phi }_2)$: a ${\phi }_1$ con $i-1$ o a ${\phi }_2$ con $i-|({\phi }_1\eta |$. $\neg {\phi }_1$: $i-1$. $Qw{\phi }_1$: $v\ne w$ y $i-|Qw|$.
3. Cada corrimiento resta los símbolos que la pieza tiene delante. $|({\phi }_1\eta |=|{\phi }_1|+2$ y $|Qw|=1+|w|$.
4. Acotada: ocurre y no libremente. En una posición donde $v$ no empieza, no es ninguna de las dos.
5. Las posiciones se cuentan símbolo por símbolo: $\mathrm{doli}$ son cuatro, $\mathrm{X}12$ son tres.
6. $\mathrm{Li}(\phi )$: las variables con al menos una ocurrencia libre. Sentencia: $\mathrm{Li}(\phi )=\varnothing$, y $S^{\tau }$ las junta.
7. Lema 10: en las atómicas, todas las variables que ocurren; $\neg$ no cambia nada; un nexo une; $Q{x}_j$ saca a $x_j$. Las pruebas traducen posiciones en un sentido y en el otro.
8. Un nombre fijo de una prueba elemental es una constante nueva: el tipo pasa a $(C\cup \{b\},F,R,a)$, y crece con cada «sea».