¿Cuál es la diferencia entre la prueba de inducción estándar y la inducción estructural?

Pregunta originalmente respondida: ¿Cuál es la diferencia entre la prueba de inducción estándar y la inducción estructural?

He visto antes la palabra “inducción estructural” pero nunca he entendido bien cuál es su diferencia y sus relaciones con la inducción estándar.

La inducción estándar, o inducción matemática, es un principio de prueba utilizado para establecer que una propiedad es válida para todos los elementos de un conjunto bien ordenado. Un conjunto bien ordenado es un conjunto [math] \ mathbb {U} [/ math] que tiene un orden total definido de manera tal que cada subconjunto no vacío de [math] \ mathbb {U} [/ math] tiene un menos elemento por ese orden. Intuitivamente, tal conjunto es como una cadena lineal de elementos.

El caso interesante es, por supuesto, cuando [math] \ mathbb {U} [/ math] es infinito. El conjunto de números naturales, [math] \ mathbb {N} = \ {0,1,2, \ cdots \} [/ math] sería un buen ejemplo. Lo importante aquí es reconocer que para tal conjunto, cada elemento, excepto el último único si existe, tiene un sucesor único.

Entonces podemos llamar al primer elemento del conjunto ‘0’, al siguiente elemento ‘1’, etc., siempre y cuando uno recuerde que no hay una estructura algebraica implícita aquí como la suma o la multiplicación. Usando esta práctica mnemónica podemos formular el principio de inducción de la siguiente manera:

[matemáticas] \ displaystyle \ forall P. ((P (0) \ land \ forall n \ in \ mathbb {U}. (P (n) \ implica P (\ sigma (n))) \ implica (\ forall n \ in \ mathbb {U} .P (n)) [/ math], donde [math] \ sigma [/ math] es la operación sucesora (para números naturales: [math] \ sigma (n) = n + 1 [ /matemáticas]).

En palabras, se lee, para todas las propiedades, si la propiedad es verdadera para [math] 0 [/ math] y si, cuando la propiedad es verdadera para [math] n [/ math], también es verdadera para [math] \ sigma (n) [/ math], entonces la propiedad es verdadera para todos los elementos.

La inducción estructural es una generalización de este principio de prueba. Básicamente funciona no considerando solo conjuntos bien ordenados sino cualquier conjunto que pueda tener un orden parcial bien fundado definido en él.

Bien fundado, aquí simplemente significa que hay algunos casos básicos (que generalizan el ‘0’ de la inducción estándar). Un buen ejemplo serían los conjuntos. El caso base aquí sería el conjunto vacío.

El orden parcial aquí significa que no todos los elementos son necesariamente comparables por el orden. Por ejemplo, no todos los conjuntos son directamente comparables por el ordenamiento parcial [math] \ subset [/ math]. Tenemos que [math] \ {0 \} \ subset \ {0,1 \} [/ math] pero, [math] \ {0 \} \ not \ subset \ {1 \} [/ math].

Ahora, en la inducción estándar, siempre podemos encontrar el siguiente elemento. Otra forma de ver esto es que siempre podemos ‘construir’ el siguiente número a partir de cualquier número dado, realizando la operación sucesora, que en este caso es sumar 1.

De manera análoga, en el caso de la inducción estructural, tenemos operaciones que nos permiten construir un conjunto de elementos ‘próximos’, combinando los elementos base de alguna manera. En nuestro ejemplo de conjuntos, por ejemplo, podemos construir conjuntos más grandes a partir de conjuntos más pequeños mediante la operación de unión de conjuntos [math] \ cup [/ math].

El principio es entonces bastante simple. Si la propiedad es válida para todos los casos base, y si es válida para todos los componentes de una estructura, también es válida para la estructura misma, entonces es válida para todas las estructuras.

Un ejemplo simple se da en la excelente respuesta de Jakub Lédl.

La inducción estructural es otro nombre de inducción recursiva . Mientras su esquema recursivo cubra todos los casos en cuestión, su prueba es válida.

Por ejemplo, para probar una propiedad válida para todos los números naturales, [math] n [/ math], puede usar un esquema de inducción simple:

Esquema 1:

1) Mostrar [matemáticas] n = 1 [/ matemáticas] la propiedad es válida.

2) Suponga que [math] n = m [/ math] la propiedad es válida, luego muestre [math] n = m + 1 [/ math] que la propiedad es válida.

Repasemos la recursividad. 1) demuestra el caso de [matemáticas] n = 1 [/ matemáticas]. Luego, aplicar 2) una vez con [matemáticas] m = 1 [/ matemáticas] prueba el caso de [matemáticas] n = 2 [/ matemáticas]. Además, aplicar 2) una vez más con [matemáticas] m = 2 [/ matemáticas] demuestra el caso de [matemáticas] n = 3 [/ matemáticas], y así sucesivamente. Como puede ver, es un método recursivo simple.

Puede encontrar un problema que necesita separarse de manera par e impar, en tal caso su prueba inductiva es más probable como:

Esquema 2:

1) Mostrar [matemáticas] n = 1 [/ matemáticas] la propiedad es válida.

2) Mostrar [matemáticas] n = 2 [/ matemáticas] la propiedad es válida.

3) Suponga que [math] n = 2m-1 [/ math] y [math] n = 2m [/ math] la propiedad es válida, luego muestre [math] n = 2m + 1 [/ math] la propiedad es válida.

4) Suponga que [math] n = 2m [/ math] y [math] n = 2m + 1 [/ math] la propiedad es válida, luego muestre [math] n = 2m + 2 [/ math] la propiedad es válida.

Repasemos la recursión nuevamente. 1) prueba el caso de [matemáticas] n = 1 [/ matemáticas] y 2) prueba el caso de [matemáticas] n = 2 [/ matemáticas]. Luego, aplicar 3) con [matemática] m = 1 [/ matemática] prueba el caso de [matemática] n = 3 [/ matemática] y luego aplicar 4) con [matemática] m = 1 [/ matemática] prueba el caso de [matemática] n = 4. [/ matemática] Además, aplicar 3) con [matemática] m = 2 [/ matemática] demuestra el caso de [matemática] n = 5 [/ matemática] y luego aplicar 4) con [matemática] m = 2 [/ math] prueba el caso de [math] n = 6 [/ math], y así sucesivamente. Este es otro patrón recursivo.

También puede encontrar un problema que es fácil de mostrar cuando [matemáticas] n [/ matemáticas] es una potencia de 2, pero difícil para los otros casos. Sin embargo, es fácil de mostrar de forma recursiva hacia atrás. La prueba inductiva podría verse así:

Esquema 3:

1) Mostrar [matemáticas] n = 1 [/ matemáticas] la propiedad es válida.

2) Suponga que [math] n = m [/ math] la propiedad es válida, luego muestre [math] n = 2m [/ math] que la propiedad es válida.

3) Suponga que [math] n = m [/ math] la propiedad es válida, luego muestre [math] n = m-1 [/ math] que la propiedad es válida.

Este es otro patrón recursivo. Te dejo correr por la recursión por ti mismo.