Variables y términos de tipo τ

La Guía 8 terminó con un programa: darles una definición matemática precisa a las cosas que las guías anteriores usaban con palabras —«término elemental» y «fórmula elemental», «verdadera en una estructura», «prueba elemental»—. La definición de término que había decía que una palabra es un término si y sólo si se construye con ciertas cláusulas, y no decía de qué están hechas las variables ni qué quiere decir «se construye». La Guía 9 cumple el primer punto del programa con una idea sola: términos y fórmulas son palabras, de un alfabeto fijado de antemano, armadas por niveles. Lo primero que hay que fijar son las variables.

01 · Las variables son palabras concretas

Hasta la Guía 8 las variables eran $x,y,z,w,\dots$, y nunca se dijo cuántas había ni de qué símbolos estaban hechas. La Guía 9 las fija de una vez: $\mathrm{Var}$ es el siguiente conjunto de palabras del alfabeto $\{\mathrm{X},0,1,\dots ,9,0,1,\dots ,9\}$:

$$\mathrm{Var}=\{\mathrm{X}1,\mathrm{X}2,\dots ,\mathrm{X}9,\mathrm{X}10,\mathrm{X}11,\dots ,\mathrm{X}19,\mathrm{X}20,\mathrm{X}21,\dots \}$$

El elemento $n$-ésimo de $\mathrm{Var}$ es la palabra $\mathrm{X}\alpha$, donde $\alpha$ es la escritura decimal de $n$ con el último numeral en negrita y los anteriores en itálica. El trescientos cuarenta y uno es la palabra $\mathrm{X}341$, de longitud cuatro. Para cada $i\in \mathbb{N}$ se escribe $x_i$ para el $i$-ésimo elemento de $\mathrm{Var}$, y a los elementos de $\mathrm{Var}$ se los llama variables. Ojo con lo que es cada cosa: $x_i$ es una abreviatura que se usa para hablar de la variable; la variable misma es la palabra, una $\mathrm{X}$ seguida de numerales. Por eso su longitud es

$$|x_n|=1+\text{(cantidad de dígitos de }n\text{)}$$

y no $n+1$: $\mathrm{X}1$ mide 2, $\mathrm{X}1119$ mide 5 y $\mathrm{X}156669$ mide 7.

El alfabeto tiene dos decisiones de diseño, y las dos son de contenido, no de tipografía. Los numerales normales quedan para los tipos. El tipo de los reticulados acotados tiene las constantes $0$ y $1$, y ese $1$ nunca ocurre adentro de una variable: el numeral de $\mathrm{X}1$ es el negrita $1$, que es otro símbolo. Una variable y un nombre del tipo no comparten ningún símbolo, y por eso nunca se confunden.

El último numeral es el único negrita, y eso hace que ninguna variable sea subpalabra de otra distinta. La prueba entra en un párrafo. Si $x_i$ ocurre adentro de $x_j$, la $\mathrm{X}$ de $x_i$ tiene que ser la única $\mathrm{X}$ de $x_j$, que está en la posición 1, y el negrita de $x_i$ tiene que ser el único negrita de $x_j$, que es su último símbolo. Entonces $x_i$ empieza donde empieza $x_j$ y termina donde termina: es $x_j$. Con todos los numerales en itálica la cuenta se rompe: $\mathrm{X}1$ sería el comienzo de $\mathrm{X}10$, de $\mathrm{X}11$ y de $\mathrm{X}100$. Es lo que la guía llama simplificar la escritura de los resultados: cuando se buscan las apariciones de $x_1$ en una palabra, ninguna está escondida adentro de $x_{12}$.

02 · El tipo fija los nombres

Los términos se escriben con las variables y con los nombres de un tipo. El tipo es el de la Guía 8, desarrollado en Fórmulas y sentencias elementales: una 4-upla $\tau =(C,F,R,a)$, con $C$ los nombres de constante, $F$ los de función, $R$ los de relación y $a:F\cup R\to \mathbb{N}$ la aridad de cada nombre de función o de relación. Para cada $n$, $F_n=\{f\in F:a(f)=n\}$. Los nombres cumplen tres condiciones:

1. son palabras sobre alfabetos finitos, uno para $C$, otro para $F$ y otro para $R$, disjuntos de a pares;
2. ningún símbolo de esos alfabetos es $\forall$, $\exists$, $\neg$, $\vee$, $\wedge$, $\to$, $\leftrightarrow$, un paréntesis, la coma, $\equiv$, la $\mathrm{X}$ de las variables ni un numeral itálico o negrita;
3. ninguna palabra de $C$ es subpalabra propia de otra palabra de $C$, y lo mismo dentro de $F$ y dentro de $R$.

Las tres apuntan a lo mismo: que una palabra hecha con estos símbolos se pueda leer de una sola manera. La segunda es la mitad que le toca al tipo del acuerdo de la sección anterior —las variables no usan numerales normales, los nombres no usan los otros—, y la tercera hace para los nombres lo que la negrita final hace para las variables.

Los ejemplos de la guía usan tres tipos, y son los que se eligen más abajo para armar términos:

1. (E1) $\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$;
2. (E2) $\tau =(\{0,1\},\{+,\times ,\uparrow \},\varnothing ,a)$, con $a(+)=2$, $a(\times )=3$ y $a(\uparrow )=1$;
3. (E3) $\tau =(\varnothing ,\{s,i\},\varnothing ,\{(s,2),(i,2)\})$, el tipo de los reticulados terna.

Los nombres son palabras y nada más. En (E2), $\times$ lleva tres argumentos: no tiene nada que ver con multiplicar. Y en (E1) el nombre $\mathrm{doli}$ son cuatro símbolos del alfabeto, no uno.

03 · Los términos se arman por niveles

Dado un tipo $\tau$, la guía define por recursión los conjuntos de palabras $T_k^{\tau }$, con $k\ge 0$:

$$T_0^{\tau }=\mathrm{Var}\cup C$$ $$T_{k+1}^{\tau }=T_k^{\tau }\cup \{f(t_1,\dots ,t_n):f\in F_n,n\ge 1\text{ y }{t}_1,\dots ,t_n\in T_k^{\tau }\}$$

y $T^{\tau }={\bigcup }_{k\ge 0}{T}_k^{\tau }$. Los elementos de $T^{\tau }$ son los términos de tipo $\tau$. La palabra $f(t_1,\dots ,t_n)$ es la concatenación de las $n+(n-1)+3$ palabras

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

así que su longitud es

$$|f|+|t_1|+\dots +|t_n|+(n-1)+2$$

En (E1), $\mathrm{MAS}(\mathrm{uno},\mathrm{doli},\mathrm{X}19,\mathrm{X}5)$ mide $3+3+4+3+2+3+2=20$: el nombre, los cuatro argumentos, tres comas y dos paréntesis. Las longitudes se cuentan en símbolos del alfabeto, y por eso $\mathrm{MAS}$ pesa 3 y $\mathrm{X}19$ también.

Cada nivel contiene al anterior, porque $T_{k+1}^{\tau }$ se define como $T_k^{\tau }$ unido a algo. Un término que está en $T_k^{\tau }$ está en todos los niveles de arriba, y la unión no cambia si se la empieza más tarde: $T^{\tau }={\bigcup }_{k\ge 6}{T}_k^{\tau }$, porque lo que nace antes de $T_6^{\tau }$ ya está en $T_6^{\tau }$.

Por eso tiene sentido hablar del nivel de un término $t$: el menor $k$ tal que $t\in T_k^{\tau }$. Las variables y las constantes tienen nivel 0. El de $f(t_1,\dots ,t_n)$ es uno más que el máximo de los niveles de sus argumentos. Que no puede ser más: si cada $t_j$ está en $T_{k_j}^{\tau }$, todos están en $T_M^{\tau }$ con $M=max{k}_j$, y entonces $f(t_1,\dots ,t_n)\in T_{M+1}^{\tau }$. Que no puede ser menos necesita saber que el término se descompone de una sola manera —que no hay otros argumentos que den la misma palabra—, y eso es el Teorema 3 de la guía, desarrollado en Mordisqueo y lectura única de términos. En (E1), $\mathrm{MAS}(\mathrm{P}(\mathrm{X}4),\mathrm{doli},\mathrm{X}19,\mathrm{X}5)$ tiene argumentos de niveles 1, 0, 0 y 0, y nace en $T_2^{\tau }$: cuenta el piso más alto, no cuántos argumentos tienen pisos.

04 · Los ejemplos de la guía, leídos

La guía da estos términos. En (E1) dice en qué nivel está cada uno salvo el último cerrado, y leídos de afuera hacia adentro el nivel que dice es justo el menor; en (E2) y (E3) no da el nivel, y la tabla lo agrega:

El último de (E1) nace en $T_3^{\tau }$ porque su único argumento, $\mathrm{MAS}(\mathrm{P}(\mathrm{X}4),\mathrm{MAS}(\mathrm{X}1,\mathrm{X}2,\mathrm{X}3,\mathrm{X}4),\mathrm{X}19,\mathrm{X}5)$, tiene adentro dos argumentos de nivel 1 y es de nivel 2. Los dos compuestos de (E2) llegan a 3 por el mismo camino, uno con 32 símbolos y el otro con 19. La longitud no dice el nivel: $\mathrm{MAS}(\mathrm{uno},\mathrm{doli},\mathrm{doli},\mathrm{doli})$ mide 23 y es de nivel 1, y $\mathrm{P}(\mathrm{P}(\mathrm{uno}))$ mide 9 y es de nivel 2.

En (E3) la guía agrega que $(\mathrm{X}2s\mathrm{X}3)$ no es un término de tipo $\tau$, y que probarlo no es trivial a partir de la definición: requiere una demostración. Es la forma en que se escribía el supremo desde la Guía 6, y en el modelo no existe; la única manera de aplicar $s$ es $\mathrm{s}(t_1,t_2)$. Pero la definición dice cómo se arman los términos, no cómo se reconocen los que no lo son, y mirar la palabra no alcanza. La prueba es una inducción en $k$: todo término de los reticulados terna empieza con $\mathrm{X}$, con $s$ o con $i$ —los de $T_0^{\tau }$ son variables, y los que agrega cada nivel empiezan con el nombre de función—, y esta palabra empieza con un paréntesis. El molde de esa inducción está en Inducción en la construcción, y las dos maneras de probar que una palabra no es un término, en Probar que una palabra no es término ni fórmula.

05 · Los términos cerrados

Un término $t$ es cerrado si $x_i$ no es subpalabra de $t$ para ningún $i\in \mathbb{N}$, y

$$T_c^{\tau }=\{t\in T^{\tau }:t\text{ es cerrado}\}$$

La definición habla de subpalabras porque $t$ es una palabra. Escribirla con $\mathrm{Var}\cap t$ no sirve: la intersección es entre conjuntos, y $t$ no es un conjunto.

En (E1) son cerrados $\mathrm{uno}$, $\mathrm{doli}$, $\mathrm{P}(\mathrm{uno})$ y $\mathrm{MAS}(\mathrm{uno},\mathrm{doli},\mathrm{doli},\mathrm{doli})$; en (E2), $\uparrow (+(\uparrow (0),\times (0,1,0)))$. En (E3) no hay ninguno: sin nombres de constante, $T_0^{\tau }$ son sólo variables, y cada término que agrega un nivel lleva adentro a sus argumentos, así que por inducción todo término tiene alguna variable. Y un término cerrado sigue siendo una palabra, no lo que vale: en un tipo con la constante $0$ y la función $s$, $0$ y $\mathrm{s}(0,0)$ son dos términos cerrados distintos aunque en todo reticulado valgan lo mismo. Es la tesis de Un término es una palabra, no un valor, ahora con una definición que la sostiene.

Los Ejercicios 1 y 2 de la guía son verdaderos, falsos o imprecisos sobre estas definiciones —qué clase de objeto es $\mathrm{Var}$, cuánto mide $x_n$, cuántos términos cerrados hay—, y están resueltos en Antes de decidir, preguntá qué clase de objeto es.

06 · Un modelo de los términos puros

La guía cierra los ejemplos con una «observación importante»: los términos de tipo $\tau$ son un modelo matemático de los términos elementales puros de tipo $\tau$, aquellos en los que no ocurren nombres de elementos fijos. En la Guía 8 un término podía tener $a$, $b$, $c$; en $T^{\tau }$ no hay dónde ponerlos, porque el alfabeto son las variables y los nombres del tipo.

Los nombres de elementos fijos vuelven al final de la guía por otro camino. Un tipo ${\tau }^{\prime }$ es una extensión de $\tau$ por nombres de constante si ${\tau }^{\prime }=(C^{\prime },F,R,a)$ con $C\subseteq C^{\prime }$. Cuando en una prueba elemental se fija un elemento y se lo llama $b$, se puede pensar que la estructura imaginaria pasó a ser de tipo $(C\cup \{b\},F,R,a)$, y $b$ es una constante más: un término con $b$ es un término de ese tipo extendido. Cómo se usa eso con fórmulas está en Variables libres.

Para tener a mano

1. $x_n$ es la palabra $\mathrm{X}$ seguida de la escritura decimal de $n$, en itálica salvo el último numeral, que va en negrita. Mide 1 más la cantidad de dígitos de $n$.
2. Los numerales normales son de los tipos. La negrita final hace que ninguna variable sea subpalabra de otra.
3. $\tau =(C,F,R,a)$: nombres sobre alfabetos disjuntos, sin símbolos lógicos, sin la $\mathrm{X}$ ni numerales itálicos o negritas, y ninguno subpalabra propia de otro de su clase.
4. $T_0^{\tau }=\mathrm{Var}\cup C$; $T_{k+1}^{\tau }$ agrega a $T_k^{\tau }$ las palabras $f(t_1,\dots ,t_n)$ con argumentos en $T_k^{\tau }$; $T^{\tau }$ es la unión, y cada nivel contiene al anterior.
5. $|f(t_1,\dots ,t_n)|=|f|+|t_1|+\dots +|t_n|+(n-1)+2$, contando en símbolos del alfabeto.
6. El nivel de un término es el menor $k$ con $t\in T_k^{\tau }$: 0 para variables y constantes, uno más que el máximo de los argumentos para $f(t_1,\dots ,t_n)$.
7. Cerrado: ningún $x_i$ es subpalabra. Sin nombres de constante no hay términos cerrados.
8. Que una palabra no sea término se prueba: la notación infija no existe en el modelo, y $(\mathrm{X}2s\mathrm{X}3)$ cae por una inducción sobre el primer símbolo.
9. Los términos de tipo $\tau$ modelan los términos elementales puros; los nombres de elementos fijos entran como constantes de una extensión de $\tau$.