1.5: Inducción

Estás familiarizado, sin duda, con las pruebas por inducción. Son la ruina de la mayoría de los estudiantes de matemáticas desde su primera introducción en la escuela secundaria hasta los años universitarios. Es nuestro objetivo en esta sección discutir las pruebas por inducción que tan bien conoces, ponerlas bajo una luz diferente, y luego generalizar esa noción de inducción a un entorno que nos permita usar la inducción para probar cosas sobre términos y fórmulas en lugar de solo los números naturales.

Sólo para recordarle la forma general de una prueba por inducción sobre los números naturales, expongamos y probemos un teorema familiar, asumiendo por el momento que el conjunto de números naturales es\(\{1, 2, 3, \ldots \}\).

Teorema 1.4.1. Por cada número natural\(n\),

\[1 + 2 + \cdots + n = \frac{n \left( n + 1 \right)}{2}.\]

Comprobante. Si\(n = 1\), el cálculo simple muestra que la igualdad se mantiene. Para el caso inductivo, arregle\(k \geq 1\) y asuma que

\[1 + 2 + \cdots + k = \frac{k \left( k + 1 \right)}{2}.\]

Si sumamos\(k + 1\) a ambos lados de esta ecuación, obtenemos

\[1 + 2 + \cdots + k + \left( k + 1 \right) = \frac{k \left( k + 1 \right)}{2} + \left( k + 1 \right),\]

y simplificar el lado derecho de esta ecuación muestra que

\[1 + 2 + \cdots + \left( k + 1 \right) = \frac{\left( k + 1 \right) \left( \left( k + 1 \right) + 1 \right)}{2},\]

terminando el paso inductivo, y la prueba.

Al mirar la prueba de este teorema, se nota que hay un caso base, cuándo\(n = 1\), y un caso inductivo. En el paso inductivo de la prueba, probamos la implicación

Si la fórmula se mantiene para\(k\), entonces la fórmula se mantiene para\(k + 1\).

Demostramos esta implicación asumiendo el antecedente, que el teorema sostiene para un número (fijo, pero desconocido)\(k\), y a partir de esa suposición demostrando lo consecuente, que el teorema hods para el siguiente número,\(k + 1\). Observe que esto no es lo mismo que asumir el teorema que estamos tratando de probar. El teorema es una declaración universal - afirma que una determinada fórmula se mantiene para cada número natural.

Mirando esto desde un ángulo ligeramente diferente, lo que hemos hecho es construir un conjunto de números con cierta propiedad. Si dejamos\(S\) reposar el conjunto de números para los que sostiene nuestro teorema, en nuestra prueba por inducción mostramos los siguientes hechos sobre S:

1. El número 1 es un elemento de\(S\). Esto lo demostramos explícitamente en el caso base de la prueba.
2. Si el número\(k\) es un elemento de\(S\), entonces el número\(k + 1\) es un elemento de\(S\). Este es el contenido del paso inductivo de la prueba.

Pero ahora, observe que sabemos que la colección de números naturales puede definirse como el conjunto más pequeño de tal manera que:

1. El número 1 es un número natural.
2. Si\(k\) es un número natural, entonces\(k + 1\) es un número natural.

Entonces\(S\), la colección de números para la que sostiene el teorema, es idéntica al conjunto de números naturales, así el teorema se mantiene para cada número natural\(n\), según sea necesario. (Si captó la leve mentira aquí, simplemente sustituya “superconjunto” en su caso).

Entonces, lo que hace una prueba por trabajo de inducción es el hecho de que los números naturales pueden definirse recursivamente. Hay un caso base, que consiste en el número natural más pequeño (“1 es un número natural”), y hay un caso recursivo, que muestra cómo construir números naturales más grandes a partir de números más pequeños (“Si\(k\) es un número natural, entonces\(k + 1\) es un número natural”).

Ahora, veamos la Definición 1.3.3, la definición de una fórmula. Observe que las cinco cláusulas de la definición se pueden separar en dos grupos. Las dos primeras cláusulas, las fórmulas atómicas, se definen explícitamente: Por ejemplo, el primer caso dice que cualquier cosa que sea de la forma\(= t_1 t_2\) es una fórmula si\(t_1\) y\(t_2\) son términos. Estas dos primeras cláusulas forman el caso base de la definición. Las tres últimas cláusulas son el caso recursivo, mostrando cómo si\(\alpha\) y\(\beta\) son fórmulas, se pueden utilizar para construir fórmulas más complejas, como\(\left( \alpha \lor \beta \right)\) o\(\left( \forall v \right) \left( \alpha \right)\).

Ahora como la colección de fórmulas se define recursivamente, podemos usar una prueba de estilo inductivo cuando queremos demostrar que algo es cierto sobre cada fórmula. La prueba inductiva constará de dos partes, una caja base y una caja inductiva. En el caso base de la prueba verificaremos que el teorema es cierto sobre cada fórmula atómica, sobre cada cadena que se sabe que es una fórmula a partir del caso base de la definición. En el paso inductivo de la prueba, asumimos que el teorema es cierto sobre las fórmulas simples (\(\alpha\)y\(\beta\)), y usamos esa suposición para probar que el teorema posee una fórmula más complicada\(\phi\) que se genera por una cláusula recursiva de la definición. Este método de prueba se llama inducción sobre la complejidad de la fórmula, o inducción sobre la estructura de la fórmula.

Hay (al menos) dos formas de pensar sobre la palabra “simple” en el último párrafo. Una forma en la que una fórmula\(\alpha\) podría ser más simple que una fórmula complicada\(\phi\) es si\(\alpha\) es una subfórmula de\(\phi\). El siguiente teorema, aunque ligeramente interesante por derecho propio, se incluye aquí principalmente para que se pueda ver un ejemplo de una prueba por inducción en este escenario:

Teorema 1.4.2. Supongamos que\(\phi\) es una fórmula en el idioma\(\mathcal{L}\). Entonces el número de paréntesis izquierdos que ocurren en\(\phi\) es igual al número de paréntesis derechos que ocurren en\(\phi\).

Comprobante. Presentaremos esta prueba con un poco de detalle, con el fin de enfatizar la técnica de prueba. A medida que te acostumbras a probar teoremas por inducción sobre la complejidad, no se necesita tanto detalle. '

Estuche Base. Comenzamos nuestra prueba inductiva con el caso base, como cabría esperar. Nuestro teorema hace una afirmación sobre todas las fórmulas, y las fórmulas más simples son las fórmulas atómicas. Constituyen nuestro caso base. Supongamos que\(\phi\) es una fórmula atómica. Existen dos variedades de fórmulas atómicas: O\(\phi\) comienza con un signo igual seguido de dos términos, o\(\phi\) comienza con un símbolo de relación seguido de varios términos. Como no hay paréntesis en ningún término (estamos usando la definición oficial de término, aquí), no hay paréntesis en\(\phi\). Así, hay tantos paréntesis izquierdos como paréntesis derechos en\(\phi\), y hemos establecido el teorema si\(\phi\) es una fórmula atómica.

Caso Inductivo. El paso inductivo de una prueba por inducción sobre la complejidad de una fórmula toma la siguiente forma: Supongamos que\(\phi\) es una fórmula en virtud de la cláusula (3), (4) o (5) de la Definición 1.3.3. Asumir también que la afirmación del teorema es verdadera cuando se aplica a las fórmulas\(\alpha\) y\(\beta\). Con esos supuestos probaremos que la afirmación del teorema es cierta cuando se aplica a la fórmula\(\phi\). Así, como toda fórmula es una fórmula ya sea en virtud de ser una fórmula atómica o por aplicación de la cláusula (3), (4), o (5) de la definición, habremos demostrado que la afirmación del teorema es cierta cuando se aplica a cualquier fórmula, que ha sido nuestro objetivo.

Entonces, supongamos que\(\alpha\) y\(\beta\) son fórmulas que contienen números iguales de paréntesis izquierdo y derecho. Supongamos que hay paréntesis\(k\)\(k\) izquierdos y paréntesis derechos\(\alpha\) y paréntesis\(l\) izquierdos y paréntesis\(l\) derecho en\(\beta\).

Si\(\phi\) es una fórmula en virtud de la cláusula (3) de la definición, entonces\(\phi : \equiv \left( \neg \alpha \right)\). Observamos que hay paréntesis\(k + 1\) izquierdos y paréntesis\(k + 1\) derechos en\(\phi\), y así\(\phi\) tiene un número igual de paréntesis izquierdo y derecho, según sea necesario.

Si\(\phi\) es una fórmula debido a la cláusula (4), entonces\(\phi : \equiv \left( \alpha \lor \beta \right)\), y\(\phi\) contiene paréntesis\(k + l + 1\) izquierdo y derecho, un número igual de cada tipo.

Finalmente, si\(\phi : \equiv \left( \forall v \right) \left( \alpha \right)\), entonces\(\phi\) contiene paréntesis\(k + 2\) izquierdos y paréntesis a la\(k + 2\) derecha, según sea necesario.

Esto concluye las posibilidades para el caso inductivo de la prueba, por lo que hemos establecido que en cada fórmula, el número de paréntesis izquierdos es igual al número de paréntesis derecho.

Una segunda forma en la que podríamos estructurar una prueba por inducción sobre la estructura de la fórmula es decir que\(\alpha\) es más simple que\(\phi\) si el número de conectivos/cuantificadores en\(\alpha\) es menor que el número en\(\phi\). En este caso se podría argumentar que el argumento de inducción es realmente una inducción ordinaria sobre los números naturales. Aquí hay un esquema de cómo podría proceder tal prueba:

Comprobante. Argumentamos por inducción sobre la estructura de\(\phi\).

Estuche Base. Supongamos que\(\phi\) tiene 0 conectivos/cuantificadores. Esto quiere decir que\(\phi\) es una fórmula atómica. {Insertar argumento que establece el teorema para las fórmulas atómicas.}

Caso Inductivo. Supongamos que\(\phi\) tiene\(k + 1\) conectivos/cuantificadores. Entonces ya sea\(\phi : \equiv \neg \alpha\),\(\phi : \equiv \alpha \lor \beta\) o o\(\phi : \equiv \left( \forall x \right) \alpha\), y podemos suponer que el teorema se mantiene para cada fórmula que tenga\(k\) o menos conectivos/cuantificadores. Ahora argumentamos que el teorema se sostiene para la fórmula\(\phi\). {Insertar argumento para los tres casos inductivos.}

Entre el caso base y el caso inductivo hemos establecido que el teorema se sostiene por\(\phi\) no importa cuántos conectivos/cuantificadores\(\phi\) contenga la fórmula, por lo que por inducción sobre la estructura de\(\phi\), hemos establecido que el teorema contiene para todas las fórmulas\(\phi\).

Esto puede resultar un poco confuso a primera vista, pero el poder de esta técnica de prueba se hará muy evidente a medida que trabaje a través de los siguientes ejercicios y cuando discutamos la semántica de nuestro lenguaje.

Observe también que la definición de un término (Definición 1.3.1) es también una definición recursiva, por lo que podemos utilizar la inducción sobre la complejidad de un término para demostrar que un teorema se sostiene para cada término.

Ejercicios

1. Demostrar, por inducción ordinaria sobre los números naturales, que
   \[1^2 + 2^2 + \cdots + n^2 = \frac{n \left( n + 1 \right) \left( 2n + 1 \right)}{6}.\]
2. Demostrar, por inducción, que la suma de los ángulos interiores en un\(n\) -gon convexo es\(\left( n - 2 \right) 180^\text{o}\). (Un\(n\) -gon convexo es un polígono con\(n\) lados, donde los ángulos interiores son todos menores que\(180^\text{o}\).)
3. Demostrar por inducción que si\(A\) es un conjunto que consiste en\(n\) elementos, entonces\(A\) tiene\(2^n\) subconjuntos.
4. Supongamos que\(\mathcal{L}\) es\(\{0, f, g\}\), donde 0 es un símbolo constante,\(f\) es un símbolo de función binaria, y\(g\) es un símbolo de función 4-aria. Utilice la inducción en la complejidad para mostrar que cada\(\mathcal{L}\) término tiene un número impar de símbolos.
5. Si\(\mathcal{L}\) es\(\{0, <\}\), donde 0 es un símbolo constante y\(<\) es un símbolo de relación binaria, mostrar que el número de símbolos en cualquier fórmula es divisible por 3.
6. Si\(s\) y\(t\) son cadenas, decimos que\(s\) es un segmento inicial de\(t\) si hay una cadena no vacía\(u\) tal que\(t : \equiv su\), donde\(su\) está la cadena\(s\) seguida de la cadena\(u\). Por ejemplo,\(KUMQ\) es un segmento inicial de\(KUMQUAT\) y\(+24\) es un segmento inicial de\(+24 u - v\). Demostrar, por inducción sobre la complejidad de\(s\), que si\(s\) y\(t\) son términos, entonces no\(s\) es un segmento inicial de\(t\). [Sugerencia: El caso base, cuando\(s\) es una variable o un símbolo constante, debería ser fácil. Entonces supongamos que\(s\) es un segmento inicial de\(t\) y\(s : \equiv f t_1 t_2 \ldots t_n\), donde se sabe que cada uno no\(t_i\) es un segmento inicial de ningún otro término. Busquen una contradicción.]
7. Se dice que un lenguaje satisface legibilidad única para términos si, para cada término\(t\),\(t\) se encuentra exactamente en una de las siguientes categorías:
   (a) Variable
   (b) Símbolo constante
   (c) Término complejo
   y además, si\(t\) es un término complejo, entonces hay un símbolo de función único\(f\) y una secuencia única de términos\(t_1, t_2, \ldots, t_n\) tales que\(t : \equiv f t_1 t_2 \ldots t_n\). Demostrar que nuestros lenguajes satisfacen una legibilidad única para términos. [Sugerencia: En su mayoría hay que preocuparse por la singularidad, por ejemplo, supongamos que\(t\) es\(c\), un símbolo constante. ¿Cómo sabes que no\(t\) es también un término complejo? Supongamos que\(t\) es\(f t_1 t_2 \ldots t_n\). ¿Cómo demuestras que los\(f\) y los\(t_i\) 's son únicos? Puede resultarle útil el Ejercicio 6.]
8. Decir que un lenguaje satisface legibilidad única para fórmulas es decir que cada fórmula\(\phi\) se encuentra exactamente en una de las siguientes categorías:
   (a) Igualdad (if\(\phi : \equiv = t_1 t_2\))
   (b) Otro atómico (si\(\phi : \equiv R t_1 t_2 \ldots t_n\) para un símbolo de relación\(n\) -aria\(R\))
   (c) Negación
   (d) Disyunción
   (e) Cuantificado
   También, debe ser que si\(\phi\) es ambos\(= t_1 t_2\) y\(= t_3 t_4\), entonces\(t_1\) es idéntico\(t_3\) y\(t_2\) es idéntico a\(t_4\), y de manera similar para otras fórmulas atómicas. Además, si (por ejemplo)\(\phi\) es una negación\(\left( \neg \alpha \right)\), entonces debe darse el caso de que no haya otra fórmula\(\beta\) tal que\(\phi\) sea también\(\left( \neg \beta \right)\), y de manera similar para disyunciones y fórmulas cuantificadas. Querrás mirar, y usar, el Ejercicio 7. Puede que tengas que probar un análogo del Ejercicio 6, en el que puede ser útil pensar en los paréntesis en un segmento inicial de una fórmula, para demostrar que ninguna fórmula es un segmento inicial de otra fórmula.
9. Toma el comprobante del Teorema 1.4.2 y escríbalo de la manera en que lo presentarías como parte de una tarea de tarea. Por lo tanto, debes cortar toda la motivación inesencial y presentar solo lo que se necesita para que la prueba funcione.