Libre o acotada no agota los casos

El enunciado, textual: «V o F o I, justifique.

(a) Sean $v \in Var$ , $φ \in F^{τ}$ e $i \in ω$ . Si $v$ ocurre libremente en $φ$ a partir de algún $i$ entonces $\forall v$ no es subpalabra de $φ$
(b) Sean $v \in Var$ , $φ \in F^{τ}$ e $i \in {1, \dots, | φ |}$ . Entonces $v$ ocurre libremente en $φ$ a partir de $i$ o $v$ ocurre acotadamente en $φ$ a partir de $i$
(c) Si $φ \in F^{τ}$ y $j \in 𝐍$ , entonces $Li (\forall x_{j} φ) \cup {x_{j}} = Li (φ)$ »

Es el último ejercicio de la guía, y los tres ítems son falsos. Cada uno cae con una fórmula de entre siete y veinte símbolos, y los tres por lo mismo: le agregan a la definición algo que la definición no dice. El (a) supone que una variable es libre o cuantificada en toda la fórmula; el (b), que en cada posición pasa una de dos cosas; el (c), que cuantificar y volver a agregar la variable deja todo como estaba.

01 · Antes de decidir: la definición, y tres casos, no dos

Ocurrir a partir de $i$ . Dadas palabras $α$ y $β$ , $α$ ocurre a partir de $i$ en $β$ cuando $β = δ α γ$ con $| δ | = i - 1$ : leyendo $β$ desde su símbolo $i$ -ésimo, lo primero que aparece es $α$ entero. Las posiciones cuentan símbolos, y una variable es una palabra de varios: $X 1$ son dos, la $X$ y el numeral negrita. En $(X 1 \equiv X 2)$ , $X 1$ ocurre a partir de 2, y en la 3 hay un numeral, no el comienzo de nada.

Ocurrir libremente. La guía lo define por recursión sobre la forma de $φ$ , para $v \in Var$ , $φ \in F^{τ}$ e $i \in {1, \dots, | φ |}$ :

Si $φ$ es atómica, $v$ ocurre libremente en $φ$ a partir de $i$ si y sólo si $v$ ocurre en $φ$ a partir de $i$ .
Si $φ = (φ_{1} η φ_{2})$ , si y sólo si $v$ ocurre libremente en $φ_{1}$ a partir de $i - 1$ , o en $φ_{2}$ a partir de $i - | (φ_{1} η |$ .
Si $φ = \neg φ_{1}$ , si y sólo si $v$ ocurre libremente en $φ_{1}$ a partir de $i - 1$ .
Si $φ = Q w φ_{1}$ , si y sólo si $v \neq w$ y $v$ ocurre libremente en $φ_{1}$ a partir de $i - | Q w |$ .

Cada cláusula le saca a $φ$ lo que tiene adelante de la pieza —el paréntesis, el $\neg$ , el $(φ_{1} η$ , el $Q w$ — y corre la posición en esa misma cantidad. La recursión está bien definida porque cada fórmula se descompone de una sola manera: es la lectura única de fórmulas. Si una posición corrida cae fuera de la pieza, por ese lado no hay nada. Y la única cláusula que puede decir que no a una ocurrencia es la cuarta: dentro de $Q w φ_{1}$ , ninguna ocurrencia de $w$ es libre.

Ocurrir acotadamente. $v$ ocurre acotadamente en $φ$ a partir de $i$ cuando $v$ ocurre en $φ$ a partir de $i$ y no ocurre libremente a partir de $i$ .

Tres casos, no dos. Fijados $v$ , $φ$ e $i$ , puede pasar que $v$ no ocurra a partir de $i$ ; que ocurra y libremente; o que ocurra y no libremente, que es ocurrir acotadamente. Las dos palabras de la definición nombran el segundo y el tercero. El primero no tiene nombre, y es el más común: en la fórmula del ítem (a), de sus 20 posiciones, $X 1$ ocurre a partir de 5, y en las otras 15 no es ni libre ni acotada.

Y las tres cosas se dicen de una ocurrencia, el par $v$ e $i$ , no de la variable. Lo que se dice de la variable es $Li (φ)$ , el conjunto de las $v \in Var$ para las que hay un $i$ tal que $v$ ocurre libremente en $φ$ a partir de $i$ . Se calcula con el Lema 10, de abajo hacia arriba: $Li ((t \equiv s))$ y $Li (r (t_{1}, \dots, t_{n}))$ son las variables que ocurren en los términos; $Li (\neg φ) = Li (φ)$ ; $Li ((φ η ψ)) = Li (φ) \cup Li (ψ)$ ; y $Li (Q x_{j} φ) = Li (φ) - {x_{j}}$ . Antes de decidir un VoFoI, la pregunta es la de qué clase de objeto es cada cosa: «libre» es de una ocurrencia, $Li$ es de una fórmula. La definición entera, con los ejemplos de la guía, está en Variables libres.

Abajo se apuesta antes de ver: elegís la fórmula, la variable y la posición, y decís libre, acotada o ninguna. Después aparece el recorrido de la definición, cláusula por cláusula.

02 · El ítem (a) es falso: libre en un lado, cuantificada en el otro

El contraejemplo: $v = X 1$ y

φ = ((X 1 \equiv X 1) \land \forall X 1 (X 1 \equiv X 1))

que tiene 20 símbolos. Las posiciones 1 y 2 son los dos paréntesis; 3 y 4, la primera $X 1$ ; 5, el $\equiv$ ; 6 y 7, la segunda $X 1$ ; 8, el paréntesis que cierra; 9, el $\land$ ; 10, el $\forall$ ; 11 y 12, la $X 1$ del cuantificador; 13, el paréntesis; 14–15 y 17–18, las dos $X 1$ de adentro, con el $\equiv$ en 16; y 19 y 20, los dos paréntesis del final.

$X 1$ ocurre libremente a partir de 3. $φ$ es $(φ_{1} \land φ_{2})$ con $φ_{1} = (X 1 \equiv X 1)$ y $φ_{2} = \forall X 1 (X 1 \equiv X 1)$ , y $| (φ_{1} \land | = 9$ . Por la cláusula de los nexos, $X 1$ ocurre libremente en $φ$ a partir de 3 si ocurre libremente en $φ_{1}$ a partir de $3 - 1 = 2$ , o en $φ_{2}$ a partir de $3 - 9$ , que cae fuera. $φ_{1}$ es atómica, así que alcanza con que $X 1$ ocurra en $(X 1 \equiv X 1)$ a partir de 2, y ocurre. Lo mismo a partir de 6, que en $φ_{1}$ es la 5.

$\forall X 1$ es subpalabra de $φ$ : ocurre a partir de 10. La hipótesis del ítem se cumple y la conclusión no. Falso.

Del otro lado del $\land$ pasa lo contrario. A partir de 14, la cláusula de los nexos manda a $φ_{1}$ a partir de 13, que cae fuera de sus 7 símbolos, o a $φ_{2}$ a partir de $14 - 9 = 5$ . $φ_{2}$ empieza con $\forall X 1$ , y la cuarta cláusula pide $v \neq w$ : acá $v$ y $w$ son la misma $X 1$ , y no hay ocurrencia libre. Como $X 1$ sí ocurre a partir de 14, ocurre acotadamente. Lo mismo a partir de 17, y a partir de 11: la $X 1$ pegada al cuantificador también es una ocurrencia, y también es acotada.

Así que $X 1$ es libre a partir de 3 y 6, acotada a partir de 11, 14 y 17, y $X 1 \in Li (φ)$ . El ítem confunde « $v$ es libre en alguna parte» con « $v$ no está cuantificada en ninguna». Lo que sí vale está en el Lema 10(e): si la fórmula entera es $\forall v ψ$ , entonces $v \notin Li (\forall v ψ)$ . Que un $\forall v$ aparezca adentro no dice nada.

03 · El ítem (b) es falso: en esa posición puede no ocurrir

Las dos opciones del ítem exigen que $v$ ocurra en $φ$ a partir de $i$ : la libre porque, por inducción en la construcción de $φ$ , toda ocurrencia libre es una ocurrencia —la cláusula atómica lo pide, y las otras la corren adentro de una pieza—; la acotada porque lo dice su definición. Si en la posición $i$ no empieza una ocurrencia de $v$ , no vale ninguna.

El contraejemplo: $φ = (X 1 \equiv X 2)$ , $v = X 1$ e $i = 1$ . $φ$ es atómica, así que $X 1$ ocurre libremente a partir de 1 si y sólo si ocurre a partir de 1. En la posición 1 está el paréntesis « $($ », y no ocurre. Tampoco acotadamente, que pide que ocurra. Falso.

El $i \in {1, \dots, | φ |}$ del enunciado cierra la salida fácil —una posición fuera de la fórmula— pero no ésta. En $(X 1 \equiv X 2)$ , $X 1$ ocurre sólo a partir de 2: de las 7 posiciones, 6 son contraejemplo. La 3 también, aunque ahí esté el numeral de $X 1$ : una variable empieza con $X$ .

Lo que sí vale es el ítem con una hipótesis más: si $v$ ocurre en $φ$ a partir de $i$ , entonces ocurre libremente o acotadamente a partir de $i$ , y exactamente una de las dos. Es la definición de acotada leída al revés.

04 · El ítem (c) es falso: $x_{j}$ tenía que ser libre

Por el Lema 10(e), $Li (\forall x_{j} φ) = Li (φ) - {x_{j}}$ , así que

Li (\forall x_{j} φ) \cup {x_{j}} = (Li (φ) - {x_{j}}) \cup {x_{j}} = Li (φ) \cup {x_{j}}

y eso es $Li (φ)$ si y sólo si $x_{j} \in Li (φ)$ . Cuantificar saca a $x_{j}$ y la unión la vuelve a poner, haya estado o no.

El contraejemplo: $φ = (X 1 \equiv X 1)$ y $j = 2$ . Por el Lema 10(a), $Li (φ) = {X 1}$ . Por el (e), $Li (\forall X 2 (X 1 \equiv X 1)) = {X 1} - {X 2} = {X 1}$ , y el lado izquierdo es ${X 1} \cup {X 2} = {X 1, X 2} \neq {X 1}$ . Falso.

Sin el lema, contando posiciones, da lo mismo. $\forall X 2 (X 1 \equiv X 1)$ tiene 10 símbolos. $X 1$ es libre a partir de 5 y de 8: la cuarta cláusula pide $X 1 \neq X 2$ , que vale, y manda a $(X 1 \equiv X 1)$ a partir de $5 - 3 = 2$ y $8 - 3 = 5$ , donde ocurre. $X 2$ ocurre sólo a partir de 2, pegada al cuantificador, y ahí es acotada. $Li$ es ${X 1}$ , y la unión agrega una variable que no estaba.

El ítem se vuelve verdadero agregando la hipótesis $x_{j} \in Li (φ)$ . Con $φ = (X 1 \equiv X 2)$ y $j = 2$ : $Li (\forall X 2 (X 1 \equiv X 2)) = {X 1}$ , y ${X 1} \cup {X 2} = {X 1, X 2} = Li (φ)$ .

La regla de corrección de la cátedra es que un resultado de una guía que se usa se enuncia y se prueba. La prueba del (e) es corta. Si $v \in Li (Q x_{j} φ)$ , hay un $i$ a partir del cual $v$ ocurre libremente en $Q x_{j} φ$ ; por la cuarta cláusula, $v \neq x_{j}$ y $v$ ocurre libremente en $φ$ a partir de $i - | Q x_{j} |$ , así que $v \in Li (φ) - {x_{j}}$ . Recíprocamente, si $v \in Li (φ)$ a partir de $i$ y $v \neq x_{j}$ , la misma cláusula da que $v$ ocurre libremente en $Q x_{j} φ$ a partir de $i + | Q x_{j} |$ .

05 · Lo que se lleva a otros ejercicios

Libre y acotada son de una ocurrencia; $Li$ es de la fórmula. Una misma variable puede tener ocurrencias libres y acotadas en la misma fórmula, y pertenece a $Li (φ)$ apenas tiene una libre. Ver un $\forall v$ adentro no la saca de $Li$ : lo que decide es si alguna de sus ocurrencias sale libre del recorrido.

Ante una posición, la primera pregunta es si $v$ ocurre ahí. Recién después se pregunta cuál de las dos. Y para contar posiciones, una variable son tantos símbolos como numerales más uno.

Para calcular $Li$ , el Lema 10, de abajo hacia arriba. El cuantificador $Q x_{j}$ saca a $x_{j}$ y nunca agrega nada; una igualdad entre conjuntos que lo involucra se decide preguntando si $x_{j}$ estaba en $Li (φ)$ .

Lo que hace perder puntos. En (a), decir que $\forall X 1$ liga todas las $X 1$ de $φ$ , o dar la ocurrencia libre a partir de 2, cuando 1 y 2 son los dos paréntesis. En (b), refutar con una posición fuera de $φ$ , que el enunciado excluye. En (c), contestar «verdadero» habiendo probado sólo con una fórmula donde $x_{j}$ ya era libre, o citar el Lema 10(e) sin enunciarlo ni probarlo.

Para tener a mano

Fijados $v$ , $φ$ e $i$ , hay tres casos: $v$ no ocurre a partir de $i$ , ocurre libremente, u ocurre acotadamente.
(a) Falso: en $((X 1 \equiv X 1) \land \forall X 1 (X 1 \equiv X 1))$ , $X 1$ es libre a partir de 3 y 6, acotada a partir de 11, 14 y 17, y $\forall X 1$ ocurre a partir de 10.
(b) Falso: en $(X 1 \equiv X 2)$ , a partir de 1, $X 1$ no ocurre, así que no es ni libre ni acotada.
(c) Falso: $Li (\forall x_{j} φ) \cup {x_{j}} = Li (φ) \cup {x_{j}}$ , que es $Li (φ)$ sólo si $x_{j} \in Li (φ)$ . Contraejemplo: $(X 1 \equiv X 1)$ con $j = 2$ . Con esa hipótesis agregada, es verdadero.
La recursión baja corriendo la posición: $- 1$ por el paréntesis o el $\neg$ , $- | (φ_{1} η |$ al segundo miembro, $- | Q w |$ adentro de un cuantificador; y sólo la cuarta cláusula corta, cuando $v = w$ .