B.5: Inducción estructural

Última actualización
Guardar como PDF

Page ID: 103523

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Template:MathJaxZach

Hasta el momento hemos utilizado la inducción para establecer resultados sobre todos los números naturales. Pero un principio correspondiente se puede usar directamente para probar resultados sobre todos los elementos de un conjunto definido inductivamente. Esto a menudo se llama inducción estructural, porque depende de la estructura de los objetos definidos inductivamente.

Generalmente, una definición inductiva viene dada por (a) una lista de elementos “iniciales” del conjunto y (b) una lista de operaciones que producen nuevos elementos del conjunto a partir de los antiguos. En el caso de términos agradables, por ejemplo, los objetos iniciales son las letras. Solo tenemos una operación: las operaciones son Incluso\[\begin{aligned} o(s_1, s_2) = & [s_1 \circ s_2]\end{aligned}\] puedes pensar en los\(\Nat\) propios números naturales como dados por una definición inductiva: el objeto inicial es\(0\), y la operación es la función sucesora\(x + 1\).

Para probar algo sobre todos los elementos de un conjunto definido inductivamente, es decir, que cada elemento del conjunto tiene una propiedad\(P\), debemos:

Demostrar que los objetos iniciales tienen\(P\)
Demostrar que para cada operación\(o\), si los argumentos tienen\(P\), también lo hace el resultado.

Por ejemplo, para probar algo sobre todos los términos agradables, demostraríamos que es cierto sobre todas las letras, y que es cierto sobre\([s_1 \circ s_2]\) siempre que sea cierto\(s_1\) e\(s_2\) individualmente.

Proposición\(\PageIndex{1}\)

El número de\([\) es igual al número de\(]\) en cualquier término agradable\(t\).

Prueba. Utilizamos inducción estructural. Los términos agradables se definen inductivamente, con letras como objetos iniciales y las operaciones\(o\) para construir nuevos términos agradables a partir de los antiguos.

El reclamo es cierto para cada letra, ya que el número de\([\) en una letra por sí mismo es\(0\) y el número de\(]\) en ella también lo es\(0\).
Supongamos que el número de\([\) in\(s_1\) es igual al número de\(]\), y lo mismo es cierto para\(s_2\). El número de\([\) in\(o(s_1, s_2)\), es decir\([s_1 \circ s_2]\), in, es la suma del número de\([\) in\(s_1\) y\(s_2\). El número de\(]\) in\(o(s_1, s_2)\) es la suma del número de\(]\) in\(s_1\) y\(s_2\). Así, el número de\([\) in\(o(s_1, s_2)\) es igual al número de\(]\) in\(o(s_1,s_2)\).

◻

Problema\(\PageIndex{1}\)

Demostrar por inducción estructural que ningún término agradable comienza con\(]\).

Demos otra prueba por inducción estructural: un segmento inicial apropiado de una cadena\(t\) de símbolos es cualquier cadena\(s\) que concuerde con\(t\) símbolo por símbolo, leído desde la izquierda, pero que\(t\) sea más largo. Entonces, e.g.,\([a \circ {}\) es un segmento inicial apropiado de\([a \circ b]\), pero tampoco lo son\([b \circ {}\) (no están de acuerdo en el segundo símbolo) ni\([a \circ b]\) (tienen la misma longitud).

Proposición\(\PageIndex{2}\)

Cada segmento inicial adecuado de un buen término\(t\) tiene más que\([\)\(]\)'s.

Prueba. Por inducción en\(t\):

\(t\)es una letra por sí misma: Entonces no\(t\) tiene segmentos iniciales adecuados.
\(t = [s_1 \circ s_2]\)por algunos buenos términos\(s_1\) y\(s_2\). Si\(r\) es un segmento inicial adecuado de\(t\), hay una serie de posibilidades:
1. \(r\)es solo\([\): Entonces\(r\) tiene uno\([\) más que lo hace\(]\).
2. \(r\)es\([r_1\) donde\(r_1\) es un segmento inicial apropiado de\(s_1\): Ya que\(s_1\) es un término agradable, por hipótesis de inducción,\(r_1\) tiene\([\) más de\(]\) y lo mismo es cierto para\([r_1\).
3. \(r\)es\([s_1\) o\([s_1 \circ {}\): Por el resultado anterior, el número de\([\) y\(]\) en\(s_1\) son iguales; por lo tanto, el número de\([\) in\([s_1\) o\([s_1 \circ {}\) es uno más que el número de\(]\).
4. \(r\)es\([s_1 \circ r_2\) donde\(r_2\) es un segmento inicial apropiado de\(s_2\): Por hipótesis de inducción,\(r_2\) contiene\([\) más de\(]\). Por el resultado anterior, el número de\([\) y de\(]\) in\(s_1\) son iguales. Entonces el número de\([\) in\([s_1 \circ r_2\) es mayor que el número de\(]\).
5. \(r\)es\([s_1 \circ s_2\): Por el resultado anterior, el número de\([\) y\(]\) en\(s_1\) son iguales, y lo mismo para\(s_2\). Entonces hay uno\([s_1 \circ s_2\) más\([\) adentro de lo que hay\(]\).

◻