El valor de un término en una estructura

Un término es una palabra: $\mathrm{MAS}(\mathrm{X}1,\mathrm{uno},\mathrm{X}3,\mathrm{X}554)$ no vale nada hasta que se dice en qué estructura se lo lee y qué elemento le toca a cada variable. Con esas dos cosas, el valor se calcula de adentro hacia afuera siguiendo la forma del término, y la lectura única de términos de la Guía 9 garantiza que haya una sola manera de hacerlo. Todo lo que la Guía 10 hace con fórmulas —la relación $\models$, las equivalencias, los homomorfismos— se apoya en esta definición.

01 · Asignaciones

Sea $𝐀=(A,i)$ una estructura de tipo $\tau$. Una asignación de $𝐀$ es un elemento de

$$A^{𝐍}=\{\text{infinituplas de elementos de }A\}$$

Si $\overrightarrow{a}=(a_1,a_2,\dots )$ es una asignación, se dice que $a_j$ es el valor que $\overrightarrow{a}$ le asigna a la variable $x_j$. La tupla es infinita porque las variables son infinitas: $x_1,x_2,x_3,\dots$, y una asignación le da un valor a cada una de una vez, sin tener que saber de antemano cuáles van a aparecer en el término. El lugar $j$ de la tupla es el de la variable $x_j$, la palabra $\mathrm{X}$ seguida de la escritura decimal de $j$: el valor de $\mathrm{X}554$ es $a_{554}$, el lugar 554, por más que la variable tenga sólo cuatro símbolos.

En el ejemplo de la guía, $𝐀$ tiene universo $𝐑$ y $\overrightarrow{a}=(1,2,3,4,5,\dots )$: a cada $x_j$ le toca el número $j$.

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

Dada una estructura $𝐀$ de tipo $\tau$, un término $t\in T^{\tau }$ y una asignación $\overrightarrow{a}=(a_1,a_2,\dots )\in A^{𝐍}$, se define $t^{𝐀}[\overrightarrow{a}]$ recursivamente:

1. (1) VariableSi $t=x_i\in \mathrm{Var}$, entonces $t^{𝐀}[\overrightarrow{a}]=a_i$.
2. (2) ConstanteSi $t=c\in 𝒞$, entonces $t^{𝐀}[\overrightarrow{a}]=i(c)$.
3. (3) FunciónSi $t=f(t_1,\dots ,t_n)$, con $f\in {ℱ}_n$, $n\ge 1$ y $t_1,\dots ,t_n\in T^{\tau }$, entonces $t^{𝐀}[\overrightarrow{a}]=i(f)(t_1^{𝐀}[\overrightarrow{a}],\dots ,t_n^{𝐀}[\overrightarrow{a}])$.

El elemento $t^{𝐀}[\overrightarrow{a}]$ se llama el valor de $t$ en la estructura $𝐀$ para la asignación $\overrightarrow{a}$. La variable mira la tupla, la constante mira la estructura, y la función junta los valores de los argumentos con la operación que la estructura le da al nombre. En la cláusula (3) la asignación es la misma para todos los argumentos: un término no tiene cuantificadores, y nada adentro de él cambia lo que vale una variable.

El ejemplo de la página 1. El tipo es $\tau =(\{\mathrm{uno},\mathrm{doli}\},\{\mathrm{MAS},\mathrm{P}\},\{\mathrm{Her}\},\{(\mathrm{MAS},4),(\mathrm{P},1),(\mathrm{Her},3)\})$, y $𝐀$ tiene universo $𝐑$ con $i(\mathrm{uno})=9$, $i(\mathrm{doli})=0$, $i(\mathrm{MAS})(x,y,z,w)=2x+4y$, $i(\mathrm{P})(x)=5^x$ e $i(\mathrm{Her})=\{(x,y,z)\in {𝐑}^3:x·y·z=9\}$. Con $\overrightarrow{a}=(1,2,3,\dots )$:

• ${\mathrm{X}554}^{𝐀}[\overrightarrow{a}]=a_{554}=554$, por (1).
• ${\mathrm{uno}}^{𝐀}[\overrightarrow{a}]=i(\mathrm{uno})=9$, por (2).
• $\mathrm{P}(\mathrm{X}3{)}^{𝐀}[\overrightarrow{a}]=i(\mathrm{P})({\mathrm{X}3}^{𝐀}[\overrightarrow{a}])=i(\mathrm{P})(3)=5^3=125$, por (3) y después (1).
• $\mathrm{MAS}(\mathrm{X}1,\mathrm{uno},\mathrm{X}3,\mathrm{X}554{)}^{𝐀}[\overrightarrow{a}]=i(\mathrm{MAS})(1,9,3,554)=2·1+4·9=38$, por (3), y cada argumento por (1) o (2).

En el último, $i(\mathrm{MAS})$ recibe cuatro números y usa los dos primeros: el 3 y el 554 se calculan y se descartan. Eso va a importar en la sección 05.

03 · Por qué la definición no es ambigua

Es el Ejercicio 1 de la guía. Una definición recursiva dice «si $t$ tiene tal forma, su valor es tal cosa». Para que eso defina un elemento hacen falta dos cosas: que cada término caiga en exactamente una cláusula, y que en la cláusula (3) el nombre $f$, la cantidad $n$ y los argumentos $t_1,\dots ,t_n$ queden determinados por $t$. Si un término se pudiera leer como $f(t_1,\dots ,t_n)$ y también como $g(s_1,\dots ,s_m)$ con otras piezas, la cláusula (3) daría $i(f)(t_1^{𝐀}[\overrightarrow{a}],\dots )$ por un lado e $i(g)(s_1^{𝐀}[\overrightarrow{a}],\dots )$ por el otro, y nada impide que sean distintos.

El teorema de lectura única de términos de la Guía 9 dice exactamente lo que falta: todo $t\in T^{\tau }$ es una variable, o un nombre de constante, o de la forma $f(t_1,\dots ,t_n)$, una sola de las tres, y en el tercer caso $f$, $n$ y los $t_j$ son únicos. Con eso cada término tiene una sola cláusula que le corresponde y una sola manera de aplicarla.

Para ver qué se perdería, alcanza con imaginarse términos escritos a la manera de la escuela, sin paréntesis: $x_1+x_2·x_3$ con $\overrightarrow{a}=(1,2,3,\dots )$ vale $1+2·3=7$ si se lo lee como una suma y $(1+2)·3=9$ si se lo lee como un producto. La gramática de la Guía 9 —todo nombre de función seguido de sus argumentos entre paréntesis y separados por comas— está hecha para que eso no pase.

Y la recursión termina: en la cláusula (3), si $t\in T_{k+1}^{\tau }-T_k^{\tau }$, los argumentos están en $T_k^{\tau }$. El valor queda definido primero para los términos de $T_0^{\tau }=\mathrm{Var}\cup 𝒞$ por (1) y (2), y si ya está definido en $T_k^{\tau }$, la cláusula (3) lo define en $T_{k+1}^{\tau }$. Como todo término está en algún $T_k^{\tau }$, todo término tiene valor.

04 · Cambiar un lugar: la asignación ↓

Dada una asignación $\overrightarrow{a}\in A^{𝐍}$ y $a\in A$, ${\downarrow }_i^a(\overrightarrow{a})$ es la asignación que resulta de reemplazar en $\overrightarrow{a}$ el $i$-ésimo elemento por $a$:

$${\downarrow }_i^a(\overrightarrow{a})=(a_1,\dots ,a_{i-1},a,a_{i+1},\dots )$$

Por ejemplo, ${\downarrow }_2^7(1,2,3,4,\dots )=(1,7,3,4,\dots )$. Es la asignación que va a aparecer en la cláusula del $\forall$ y del $\exists$: para decidir $\forall x_i\phi$ se prueba $\phi$ con todos los valores posibles en el lugar $i$, dejando los demás quietos. En términos sirve para comparar valores: $\mathrm{MAS}(\mathrm{X}1,\mathrm{uno},\mathrm{X}3,\mathrm{X}554)$ vale $2·5+4·9=46$ en ${\downarrow }_1^5(1,2,3,\dots )$, y sigue valiendo 38 en ${\downarrow }_3^{10}(1,2,3,\dots )$.

Cuatro cuentas que se usan sin decirlo, y que salen de comparar lugar por lugar:

• El lugar $i$ de ${\downarrow }_i^a(\overrightarrow{a})$ es $a$, y el lugar $j\ne i$ es $a_j$.
• ${\downarrow }_i^{a_i}(\overrightarrow{a})=\overrightarrow{a}$: poner en el lugar $i$ lo que ya estaba no cambia nada.
• ${\downarrow }_i^a({\downarrow }_i^b(\overrightarrow{a}))={\downarrow }_i^a(\overrightarrow{a})$: el último cambio en el mismo lugar es el que queda.
• Si $i\ne j$, ${\downarrow }_i^a({\downarrow }_j^b(\overrightarrow{a}))={\downarrow }_j^b({\downarrow }_i^a(\overrightarrow{a}))$: las dos tienen $a$ en el lugar $i$, $b$ en el $j$ y $a_l$ en cualquier otro $l$.

Lo que se ve al tocar la tupla es la mitad del Lema 1: si el lugar que cambiaste no es el de una variable que ocurre en $t$, no cambia ningún nodo. La otra mitad no vale. $\mathrm{X}3$ ocurre en $\mathrm{MAS}(\mathrm{X}1,\mathrm{uno},\mathrm{X}3,\mathrm{X}554)$, su nodo cambia, y la raíz no se entera.

05 · El Lema 1: sólo importan las variables que ocurren

Las dos asignaciones pueden diferir en infinitos lugares; mientras coincidan en los lugares de las variables que aparecen en $t$, el valor es el mismo. Con $\overrightarrow{b}=(1,1002,3,1004,1005,\dots )$, que coincide con $(1,2,3,\dots )$ en los lugares 1, 3 y 554, $\mathrm{MAS}(\mathrm{X}1,\mathrm{uno},\mathrm{X}3,\mathrm{X}554)$ vale 38 en las dos. La guía hace la prueba por inducción y deja el caso base al lector; acá va entera.

Prueba. Usaremos la Regla de Inducción desde 0. Para cada $k\in \omega$ sea ${\mathrm{Enu}}_k$ el enunciado:

Prueba de que ${\mathrm{Enu}}_0$ es verdadero. Sea $𝐀$ una estructura de tipo $\tau$, sea $t\in T_0^{\tau }=\mathrm{Var}\cup 𝒞$ y sean $\overrightarrow{a},\overrightarrow{b}$ asignaciones tales que $a_i=b_i$ cada vez que $x_i$ ocurra en $t$. Hay dos casos.

• Caso $t=x_i$. La variable $x_i$ ocurre en $t$, porque $t$ es ella misma (ocurre a partir de 1). Entonces $a_i=b_i$, y por la cláusula (1), $t^{𝐀}[\overrightarrow{a}]=a_i=b_i=t^{𝐀}[\overrightarrow{b}]$.
• Caso $t=c\in 𝒞$. Por la cláusula (2), $t^{𝐀}[\overrightarrow{a}]=i(c)=t^{𝐀}[\overrightarrow{b}]$. La hipótesis sobre $\overrightarrow{a}$ y $\overrightarrow{b}$ no se usa: un nombre de constante no tiene variables, y su valor no depende de la asignación.

Prueba de que si ${\mathrm{Enu}}_k$ es verdadero, entonces ${\mathrm{Enu}}_{k+1}$ lo es. Supongamos que vale ${\mathrm{Enu}}_k$. Sea $𝐀$ una estructura de tipo $\tau$, sea $t\in T_{k+1}^{\tau }$ y sean $\overrightarrow{a},\overrightarrow{b}$ asignaciones tales que $a_i=b_i$ cada vez que $x_i$ ocurra en $t$. Por definición de $T_{k+1}^{\tau }$ hay dos casos.

• Caso $t\in T_k^{\tau }$. Como vale ${\mathrm{Enu}}_k$, se cumple su conclusión: $t^{𝐀}[\overrightarrow{a}]=t^{𝐀}[\overrightarrow{b}]$.
• Caso $t=f(t_1,\dots ,t_n)$, con $f\in {ℱ}_n$, $n\ge 1$ y $t_1,\dots ,t_n\in T_k^{\tau }$. Primero, para cada $j$, si $x_i$ ocurre en $t_j$ entonces $x_i$ ocurre en $t$: $t=\delta t_j\gamma$ con $\delta =f(t_1,\dots ,t_{j-1},$ (o $\delta =f($ si $j=1$), y si $x_i$ ocurre en $t_j$ a partir de $p$, ocurre en $t$ a partir de $|\delta |+p$. Entonces, para cada $j=1,\dots ,n$, $a_i=b_i$ cada vez que $x_i$ ocurra en $t_j$, y ${\mathrm{Enu}}_k$ aplicado a $𝐀$, $t_j$, $\overrightarrow{a}$ y $\overrightarrow{b}$ da $t_j^{𝐀}[\overrightarrow{a}]=t_j^{𝐀}[\overrightarrow{b}]$. Se tiene entonces que
  $$t^{𝐀}[\overrightarrow{a}]=i(f)(t_1^{𝐀}[\overrightarrow{a}],\dots ,t_n^{𝐀}[\overrightarrow{a}])=i(f)(t_1^{𝐀}[\overrightarrow{b}],\dots ,t_n^{𝐀}[\overrightarrow{b}])=t^{𝐀}[\overrightarrow{b}]$$
  donde la primera y la última igualdad son la cláusula (3), con $\overrightarrow{a}$ y con $\overrightarrow{b}$, y la del medio es la que dio ${\mathrm{Enu}}_k$ en cada argumento.

Luego ${\mathrm{Enu}}_k$ es verdadero para todo $k\in \omega$. Como todo $t\in T^{\tau }$ está en algún $T_k^{\tau }$, el lema vale para todo término. ∎

Dos cosas de la forma de la prueba. El ${\mathrm{Enu}}_k$ tiene adentro la estructura y las dos asignaciones: «sea $𝐀$… supongamos que $\overrightarrow{a},\overrightarrow{b}$…». En esta prueba la hipótesis inductiva se aplica con las mismas $𝐀$, $\overrightarrow{a}$ y $\overrightarrow{b}$ que se tienen afuera, así que no se nota; en el Lema 2, que es la versión para fórmulas, el caso $\forall x_j{\phi }_1$ aplica la hipótesis con ${\downarrow }_j^a(\overrightarrow{a})$ y ${\downarrow }_j^a(\overrightarrow{b})$, y si las asignaciones hubieran quedado fijas afuera del ${\mathrm{Enu}}_k$, la prueba no cerraría. Y el lema va en una sola dirección: que $x_3$ ocurra en $t$ no quiere decir que el valor dependa de $a_3$. Lo que cuenta en la cláusula (3) es la operación $i(f)$, y $i(\mathrm{MAS})$ ignora sus dos últimos argumentos.

06 · Cómo se usa en los ejercicios

Los Ejercicios 5 a 8 de la lista comparan el valor de un término $t$ con el de un término $t^{\prime }$ que sale de $t$ por un reemplazo, y todos se prueban con el molde del Lema 1: Regla de Inducción desde 0, ${\mathrm{Enu}}_k$ con la estructura y las asignaciones cuantificadas adentro, caso base con $t=x_j$ y $t=c$, y en el paso el caso $t\in T_k^{\tau }$ y el caso $t=f(t_1,\dots ,t_n)$. Lo que cambia de uno a otro es qué pasa con las ocurrencias de lo reemplazado: en el Ejercicio 5 se cambia $x_i$ por $x_l$ y se compara ${t^{\prime }}^{𝐀}[{\downarrow }_l^a(\overrightarrow{a})]$ con $t^{𝐀}[{\downarrow }_i^a(\overrightarrow{a})]$; en el 6 y el 7 se reemplaza un término por otro que vale lo mismo; en el 8, un nombre de función por otro con la misma interpretación. En los cuatro, el paso necesita saber dónde puede estar una ocurrencia de lo reemplazado adentro de $f(t_1,\dots ,t_n)$: o es el término entero, o vive adentro de un único argumento.

Y en el Ejercicio 13 el resultado de términos se sube a fórmulas: el término que se cambia vive en una atómica, y ahí la cláusula de $\equiv$ o de $r$ compara valores de términos.

Para tener a mano

1. Una asignación es una infinitupla $\overrightarrow{a}=(a_1,a_2,\dots )\in A^{𝐍}$; $a_j$ es el valor de $x_j$. El lugar es el índice de la variable, no su largo.
2. $t^{𝐀}[\overrightarrow{a}]$: variable $x_i$ da $a_i$; constante $c$ da $i(c)$; $f(t_1,\dots ,t_n)$ da $i(f)$ aplicada a los valores de los argumentos, con la misma $\overrightarrow{a}$.
3. No es ambigua por la lectura única de términos: cada término cae en una sola cláusula, y en la (3) $f$, $n$ y los $t_j$ son únicos. Termina porque los argumentos están un nivel más abajo.
4. ${\downarrow }_i^a(\overrightarrow{a})$ cambia sólo el lugar $i$. Cambios en lugares distintos conmutan; en el mismo lugar, gana el último.
5. Lema 1: si $\overrightarrow{a}$ y $\overrightarrow{b}$ coinciden en las variables que ocurren en $t$, $t^{𝐀}[\overrightarrow{a}]=t^{𝐀}[\overrightarrow{b}]$. La vuelta no vale.
6. El molde: Regla de Inducción desde 0; ${\mathrm{Enu}}_k$ con $𝐀$ y las asignaciones adentro; base $x_i$ y $c$; paso con el caso $t\in T_k^{\tau }$ y el caso $f(t_1,\dots ,t_n)$, justificando que lo que ocurre en un $t_j$ ocurre en $t$.