B.4: Definiciones inductivas

En la lógica muy a menudo definimos tipos de objetos inductivamente, es decir, especificando reglas para lo que cuenta como un objeto del tipo a definir que explican cómo obtener nuevos objetos de ese tipo a partir de objetos antiguos de ese tipo. Por ejemplo, a menudo definimos clases especiales de secuencias de símbolos, como los términos y fórmulas de un lenguaje, por inducción. Para un ejemplo simple, considere cadenas consistentes en letras\(\mathrm{a}\),,\(\mathrm{b}\),\(\mathrm{c}\)\(\mathrm{d}\), el símbolo\(\circ\) y corchetes\([\) y\(]\), como “\([[\mathrm{c} \circ \mathrm{d}][\)”,” \([\mathrm{a}[]\circ]\)”, “\(\mathrm{a}\)” o “\([[\mathrm{a} \circ \mathrm{b}]\circ \mathrm{d}]\)”. Probablemente sientas que hay algo “mal” con las dos primeras cadenas: los corchetes no “equilibran” en absoluto en la primera, y podrías sentir que el “\(\circ\)” debería “conectar” expresiones que a su vez tienen sentido. La tercera y cuarta cuerda se ven mejor: por cada “\([\)” hay un cierre “\(]\)” (si hay alguna), y para cualquiera\(\circ\) podemos encontrar expresiones “bonitas” a cada lado, rodeadas de un par de paréntesis.

Nos gustaría especificar con precisión lo que cuenta como un “término agradable”. En primer lugar, cada letra por sí misma es agradable. Cualquier cosa que no sea solo una carta por sí misma debe ser de la forma “\([t \circ s]\)” donde\(s\) y\(t\) son ellos mismos agradables. Por el contrario, si\(t\) y\(s\) son agradables, entonces podemos formar un nuevo término agradable poniendo un\(\circ\) entre ellos y rodearlos por un par de corchetes. Podríamos usar estas operaciones para definir el conjunto de términos agradables. Esta es una definición inductiva.

Esta definición nos dice que algo cuenta como un término agradable si se puede construir de acuerdo con las dos condiciones (1) y (2) en algún número finito de pasos. En el primer paso, construimos todos los términos agradables simplemente consistentes en letras por sí mismos, es decir,\[\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}\nonumber\] En el segundo paso, aplicamos (2) a los términos que hemos construido. Obtendremos\[[\mathrm{a} \circ \mathrm{a}], [\mathrm{a} \circ \mathrm{b}], [\mathrm{b} \circ \mathrm{a}], \dots, [\mathrm{d} \circ \mathrm{d}]\nonumber\] para todas las combinaciones de dos letras. En el tercer paso, aplicamos (2) de nuevo, a cualesquiera dos términos agradables que hayamos construido hasta ahora. Obtenemos un nuevo término agradable como\([\mathrm{a} \circ [\mathrm{a} \circ \mathrm{a}]]\) —donde\(t\) es\(\mathrm{a}\) del paso 1 y\(s\) es\([\mathrm{a} \circ \mathrm{a}]\) del paso 2— y\([[\mathrm{b} \circ \mathrm{c}] \circ [\mathrm{d} \circ \mathrm{b}]]\) construido a partir de los dos términos\([\mathrm{b} \circ \mathrm{c}]\) y\([\mathrm{d} \circ \mathrm{b}]\) del paso 2. Y así sucesivamente. La cláusula (3) descarta que cualquier cosa que no se construya de esta manera se cuela en el conjunto de términos agradables.

Tenga en cuenta que aún no hemos demostrado que cada secuencia de símbolos que “se siente” bien sea agradable de acuerdo con esta definición. No obstante, debe quedar claro que todo lo que podemos construir hace de hecho “sentirse bien”: los brackets están equilibrados, y\(\circ\) conecta partes que son bonitas en sí mismas.

La característica clave de las definiciones inductivas es que si quieres probar algo sobre todos los términos agradables, la definición te dice qué casos debes considerar. Por ejemplo, si te dicen que\(t\) es un término agradable, la definición inductiva te dice cómo\(t\) puede verse:\(t\) puede ser una letra, o puede ser\([s_1 \circ s_2]\) para algún par de términos agradables\(s_1\) y\(s_2\) . Por la cláusula (3), esas son las únicas posibilidades.

Al probar afirmaciones sobre todo un conjunto definido inductivamente, la fuerte forma de inducción se vuelve particularmente importante. Por ejemplo, supongamos que queremos demostrar que por cada buen término de duración\(n\), el número de\([\) en él es\(< n/2\). Esto puede verse como una afirmación sobre todos\(n\): para cada\(n\), el número de\([\) en cualquier buen término de duración\(n\) es\(< n/2\).