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 la inducción noetheriana arbitraria . La recursión estructural es un método de recursión 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 alguna proposición $P (x)$ es válida para todos los $x$ de algún tipo de estructura definida recursivamente , como fórmulas , listas o árboles . Se define un orden parcial bien fundado en las estructuras ("subfórmula" para fórmulas, "sublista" para listas y "subárbol" para árboles). La prueba de inducción estructural es una prueba de que la proposición es válida para todas las estructuras mínimas y que si es válida para las subestructuras inmediatas de una cierta estructura $S$ , entonces debe ser válida también para $S$ . (Formalmente hablando, 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 sea válida para todos $los 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 para la recursión. La recursión estructural suele demostrarse correcta mediante inducción estructural; en casos particularmente fáciles, el paso inductivo suele omitirse. Las funciones length y ++ en el ejemplo siguiente son recursivas estructuralmente.

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:

una prueba de que $P (BC)$ es verdadera para cada caso base $BC$ ,
una prueba de que si $P (I)$ es verdadera para algún caso $I$ , y $M$ puede obtenerse a partir de $I$ aplicando una sola regla recursiva, entonces $P (M)$ también debe ser verdadera.

Ejemplos

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

En el caso más simple, un árbol ancestral muestra sólo una persona (si no se sabe nada acerca de sus padres);
Como alternativa, un árbol ancestral muestra una persona y, conectados por ramas, los dos subárboles ancestrales de sus padres (usando para abreviar la prueba el supuesto simplificador de que si uno de ellos es conocido, ambos lo son).

A modo de ejemplo, la propiedad "Un árbol ancestral que se extiende a lo largo de $g$ generaciones muestra como máximo $2 g - 1$ personas" se puede demostrar por inducción estructural de la siguiente manera:

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

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

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

{\text{EQ:}}\quad \nombreoperador {len} (L+\!+\ M)=\nombreoperador {len} (L)+\nombreoperador {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 para la longitud y para la operación de concatenación. Sea $(h : t)$ una lista cuya cabeza (primer elemento) es $h$ y cuya cola (lista de elementos restantes) es $t$ , y sea $[]$ la lista vacía. Las definiciones para la longitud y la operación de concatenación son:

{\begin{array}{ll}{\text{LEN1:}}&\operatorname {len} ([\ ])=0\\{\text{LEN2:}}&\operatorname {len} (h:t)=1+\operatorname {len} (t)\\&\\{\text{APP1:}}&[\ ]+\!+\ lista=lista\\{\text{APP2:}}&(h:t)+\!+\ lista=h:(t+\!+\ lista)\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 verdadera; es decir, $EQ$ es verdadera para todas las listas $M$ cuando $L$ es la lista vacía $[]$ . Consideremos $EQ$ :

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

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

A continuación, considere cualquier lista no vacía $I$ . Como $I$ no está vacía, tiene un elemento de cabecera, $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$ :

{\text{HYP:}}\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:

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

Así, por inducción estructural, obtenemos que $P (L)$ es verdadero para todas las listas $L$ .

Buen orden

Así como la inducción matemática estándar es equivalente al principio de buen ordenamiento , la inducción estructural también es equivalente a un principio de buen ordenamiento. Si el conjunto de todas las estructuras de un cierto tipo admite un orden parcial bien fundado, entonces cada 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 es que nos permite deducir que si hay contraejemplos del teorema que queremos demostrar, entonces debe haber un contraejemplo mínimo. Si podemos demostrar que la existencia del contraejemplo mínimo implica un contraejemplo aún más pequeño, tenemos una contradicción (ya que el contraejemplo mínimo no es mínimo) y, por lo tanto, el conjunto de contraejemplos debe estar vacío.

Como ejemplo de este tipo de argumento, considere 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 \neq 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. Elimine esta hoja y su padre del árbol, promoviendo el nodo hermano de la hoja a la posición anteriormente ocupada por su padre. Esto reduce tanto $n$ como $l$ en 1, por lo que el nuevo árbol también tiene $n + 1 \neq 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 para empezar debe haber sido falsa. El ordenamiento parcial que implica 'más pequeño' aquí es el que dice que S $< T siempre$ que $S$ tenga menos nodos que $T.$

Véase también

Coinducción
Álgebra inicial
Invariante de bucle , análogo a bucles for

Referencias

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 Mass: Addison-Wesley. ISBN 978-0-201-44124-6.
"Lógica matemática - Vídeo 01.08 - Inducción estructural generalizada" en YouTube

Las primeras publicaciones sobre la inducción estructural incluyen:

Burstall, RM (1969). "Demostración de propiedades de programas mediante inducción estructural". 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). "Pruebas por inducción en teorías ecuacionales con constructores" (PDF) . 21.° 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 ) .