Inducción estructural

La inducción estructural es un método de demostración que se utiliza en lógica matemática (por ejemplo, en la demostración del teorema de Łoś ), informática , teoría de grafos y otros campos matemáticos. Es una generalización de la inducción matemática sobre números naturales y puede generalizarse aún más a la inducción noetheriana arbitraria . La recursión estructural es un método recursivo que guarda la misma relación con la inducción estructural que la recursión ordinaria con la inducción matemática ordinaria .

La inducción estructural se utiliza para demostrar que una proposición P ( x ) se cumple para todo x de una estructura definida recursivamente , como fórmulas , listas o árboles . Se define un orden parcial bien fundado sobre las estructuras ("subfórmula" para fórmulas, "sublista" para listas y "subárbol" para árboles). La demostración por inducción estructural prueba que la proposición se cumple para todas las estructuras mínimas y que, si se cumple para las subestructuras inmediatas de una estructura S , entonces también debe cumplirse para S. (Formalmente, esto satisface las premisas de un axioma de inducción bien fundada , que afirma que estas dos condiciones son suficientes para que la proposición se cumpla para todo x ).

Una función recursiva estructural utiliza la misma idea para definir una función recursiva: los "casos base" manejan cada estructura mínima y una regla de recursión. La recursión estructural generalmente se demuestra correcta mediante inducción estructural; en casos particularmente sencillos, el paso inductivo suele omitirse. Las funciones length y ++ del ejemplo siguiente son recursivas estructurales.

Por ejemplo, si las estructuras son listas, se suele introducir el orden parcial "<", en el que L < M siempre que la lista L sea la cola de la lista M. Bajo este orden, la lista vacía [] es el único elemento mínimo. Una prueba de inducción estructural de alguna proposición P ( L ) consta entonces de dos partes: una prueba de que P ([]) es verdadera y una prueba de que si P ( L ) es verdadera para alguna lista L , y si L es la cola de la lista M , entonces P ( M ) también debe ser verdadera.

Eventualmente, puede existir más de un caso base y/o más de un caso inductivo, dependiendo de cómo se haya construido la función o estructura. En esos casos, una prueba de inducción estructural de alguna proposición P ( L ) consiste entonces en:

Un árbol genealógico es una estructura de datos comúnmente conocida que muestra los padres, abuelos, etc., de una persona hasta donde se sabe (ver imagen para un ejemplo). Se define recursivamente:

• En el caso más sencillo, un árbol genealógico muestra solo una persona (si no se sabe nada sobre sus padres);
• Alternativamente, un árbol genealógico muestra a una persona y, conectados por ramas, los dos subárboles genealógicos de sus padres (utilizando, para abreviar la demostración, la suposición simplificadora de que si se conoce a uno de ellos, se conocen ambos).

Como ejemplo, la propiedad "Un árbol genealógico que se extiende a lo largo de g generaciones muestra como máximo 2 ^g − 1 personas" se puede demostrar mediante inducción estructural de la siguiente manera:

• En el caso más simple, el árbol muestra solo una persona y, por lo tanto, una generación; la propiedad es verdadera para tal árbol, ya que 1 ≤ 2 ¹ − 1 .
• Alternativamente, el árbol muestra a una persona y los árboles de sus padres. Dado que cada uno de estos últimos es una subestructura del árbol completo, se puede asumir que satisface la propiedad que se pretende demostrar (también conocida como hipótesis de inducción ). Es decir, se puede asumir que p ≤ 2 ^g − 1 y q ≤ 2 ^h − 1 , donde g y h denotan el número de generaciones que abarcan los subárboles del padre y de la madre, respectivamente, y p y q denotan el número de personas que representan.
  • En caso de que g ≤ h , todo el árbol se extiende a lo largo de 1 + h generaciones y muestra p + q + 1 personas, y$${\displaystyle p+q+1\leq (2^{g}-1)+(2^{h}-1)+1\leq 2^{h}+2^{h}-1=2^{1+h}-1,}$$es decir, todo el árbol cumple con la propiedad.
  • En caso de que h ≤ g , todo el árbol se extiende a lo largo de 1 + g generaciones y muestra p + q + 1 ≤ 2 ^{g + 1} − 1 personas mediante un razonamiento similar, es decir, todo el árbol satisface la propiedad también en este caso.

Por lo tanto, mediante inducción estructural, cada árbol ancestral satisface la propiedad.

Como otro ejemplo más formal, consideremos la siguiente propiedad de las listas  :

${\displaystyle {\text{EQ:}}\quad \operatorname {len} (L+\!+\ M)=\operatorname {len} (L)+\operatorname {len} (M)}$

Aquí , ++ denota la operación de concatenación de listas, len() la longitud de la lista, y L y M son listas.

Para demostrar esto, necesitamos definiciones de longitud y de la operación de concatenación. Sea ( h : t ) una lista cuyo primer elemento (cabeza) es h y cuyo elemento restante (cola) es t , y sea [] la lista vacía. Las definiciones de longitud y de la operación de concatenación son:

${\displaystyle {\begin{array}{ll}{\text{LEN1:}}&\operatorname {len} ([\ ])=0\\{\text{LEN2:}}&\operatorname {len} (h:t)=1+\operatorname {len} (t)\\&\\{\text{APP1:}}&[\ ]+\!+\ list=list\\{\text{APP2:}}&(h:t)+\!+\ list=h:(t+\!+\ list)\end{array}}}$

Nuestra proposición P ( l ) es que EQ es verdadera para todas las listas M cuando L es l . Queremos demostrar que P ( l ) es verdadera para todas las listas l . Lo demostraremos mediante inducción estructural sobre listas.

Primero demostraremos que P ([]) es verdadero; es decir, EQ es verdadero para todas las listas M cuando L resulta ser la lista vacía [] . Consideremos EQ :

${\displaystyle {\begin{array}{rll}\operatorname {len} (L+\!+\ M)&=\operatorname {len} ([\ ]+\!+\ M)\\&=\operatorname {len} (M)&({\text{por APP1}})\\&=0+\operatorname {len} (M)\\&=\operatorname {len} ([\ ])+\operatorname {len} (M)&({\text{por LEN1}})\\&=\operatorname {len} (L)+\operatorname {len} (M)\\\end{array}}}$

Así pues, esta parte del teorema queda demostrada; EQ es verdadera para todo M , cuando L es [] , porque el lado izquierdo y el lado derecho son iguales.

A continuación, consideremos cualquier lista no vacía I. Dado que I no está vacía, tiene un elemento de cabeza, x , y una lista de cola, xs , por lo que podemos expresarla como ( x : xs ) . La hipótesis de inducción es que EQ es verdadera para todos los valores de M cuando L es xs :

${\displaystyle {\text{HIP:}}\quad \operatorname {len} (xs+\!+\ M)=\operatorname {len} (xs)+\operatorname {len} (M)}$

Nos gustaría demostrar que, si este es el caso, entonces EQ también es cierto para todos los valores de M cuando L = I = ( x : xs ) . Procedemos como antes:

${\displaystyle {\begin{array}{rll}\operatorname {len} (L)+\operatorname {len} (M)&=\operatorname {len} (x:xs)+\operatorname {len} (M)\\&=1+\operatorname {len} (xs)+\operatorname {len} (M)&({\text{por LEN2}})\\&=1+\operatorname {len} (xs+\!+\ M)&({\text{por HYP}})\\&=\operatorname {len} (x:(xs+\!+\ M))&({\text{por LEN2}})\\&=\operatorname {len} ((x:xs)+\!+\ M)&({\text{por APP2}})\\&=\operatorname {len} (L+\!+\ M)\end{array}}}$

Por lo tanto, a partir de la inducción estructural, obtenemos que P ( L ) es verdadera para todas las listas L .

Así como la inducción matemática estándar es equivalente al principio de buen orden , la inducción estructural también lo es. Si el conjunto de todas las estructuras de un tipo determinado admite un orden parcial bien fundado, entonces todo subconjunto no vacío debe tener un elemento mínimo. (Esta es la definición de " bien fundado "). La importancia del lema en este contexto radica en que nos permite deducir que si existen contraejemplos al teorema que queremos demostrar, entonces debe existir un contraejemplo mínimo. Si podemos demostrar que la existencia del contraejemplo mínimo implica un contraejemplo aún menor, llegamos a una contradicción (ya que el contraejemplo mínimo no es mínimo) y, por lo tanto, el conjunto de contraejemplos debe ser vacío.

Como ejemplo de este tipo de argumento, consideremos el conjunto de todos los árboles binarios . Demostraremos que el número de hojas en un árbol binario completo es uno más que el número de nodos interiores. Supongamos que hay un contraejemplo; entonces debe existir uno con el mínimo número posible de nodos interiores. Este contraejemplo, C , tiene n nodos interiores y l hojas, donde n + 1 ≠ l . Además, C debe ser no trivial, porque el árbol trivial tiene n = 0 y l = 1 y, por lo tanto, no es un contraejemplo. Por lo tanto, C tiene al menos una hoja cuyo nodo padre es un nodo interior. Eliminemos esta hoja y su padre del árbol, promoviendo el nodo hermano de la hoja a la posición que antes ocupaba su padre. Esto reduce tanto n como l en 1, por lo que el nuevo árbol también tiene n + 1 ≠ l y, por lo tanto, es un contraejemplo más pequeño. Pero por hipótesis, C ya era el contraejemplo más pequeño; Por lo tanto, la suposición de que existían contraejemplos desde el principio debe haber sido falsa. El orden parcial implícito en "menor" aquí es el que dice que S < T siempre que S tenga menos nodos que T.

• Coinducción
• Álgebra inicial
• Invariante de bucle , bucles for análogos

• Hopcroft, John E.; Rajeev Motwani; Jeffrey D. Ullman (2001). Introducción a la teoría de autómatas, lenguajes y computación (2.ª  ed.). Reading, Massachusetts: Addison-Wesley. ISBN 978-0-201-44124-6.
• "Lógica matemática - Vídeo 01.08 - Inducción generalizada (estructural)" en YouTube

Las primeras publicaciones sobre inducción estructural incluyen:

• Burstall, RM (1969). "Proving Properties of Programs by Structural Induction". The Computer Journal . 12 (1): 41– 48. doi : 10.1093/comjnl/12.1.41 .
• Aubin, Raymond (1976), Mecanización de la inducción estructural , EDI-INF-PHD, vol. 76–002 , Universidad de Edimburgo, hdl : 1842/6649 
• Huet, G.; Hullot, JM (1980). "Demostraciones por inducción en teorías ecuacionales con constructores" (PDF) . XXI Simposio anual sobre fundamentos de la informática . IEEE. págs. 96–107 . 
• Rózsa Péter , Über die Verallgemeinerung der Theorie der rekursiven Funktionen für abstrakte Mengen geeigneter Struktur als Definicionesbereiche , Symposium International, Varsovie septiembre (1959) ( Sobre la generalización de la teoría de funciones recursivas para cantidades abstractas con estructuras adecuadas como dominios ) .