Unidad V. Inducción y recursividad

INDUCCIÓN MATEMÁTICA

Una descripción informal de la inducción matemática puede ser ilustrada por el efecto dominó, donde ocurre una reacción con una secuencia de piezas de dominó cayendo una detrás de la otra.

En matemáticas, la inducción es un razonamiento que permite demostrar una infinidad de proposiciones, o una proposición que depende de un parámetro   que toma una infinidad de valores enteros. En términos simples, la inducción matemática consiste en el siguiente razonamiento:

Premisa mayor: El número entero   tiene la propiedad .

Premisa menor: El hecho de que cualquier número entero   tenga la propiedad   implica que   también la tiene.

Conclusión: Todos los números enteros a partir de   tienen la propiedad  .

v PRINCIPIO DE INDUCCIÓN MATEMÁTICA

Conjuntos Inductivos.

Intuitivamente se obtienen los enteros positivos, tomando como punto de partida un primero designado por "1" y formando 1 + 1 (llamado "2"), 2 + 1 (llamado "3"), y así sucesivamente.

En virtud de que no se puede depender del significado un poco oscuro de "y así sucesivamente" y de que se debe tener una base para proporcionar teoremas relativos a los enteros positivos, se da una definición del conjunto de los enteros positivos, basada en el concepto de conjunto inductivo. 

Definición. Un conjunto S de números es un conjunto inductivo sí y sólo sí S tiene las siguientes propiedades: 
Ejemplo 1. El conjunto  S₁ = {1, 3, 5, 7, ...} no es un conjunto inductivo, porque no obstante que 1   S₁; (1+1) S₁.

El conjunto  Z⁺ es el conjunto de números con la propiedad de que si k es cualquier conjunto inductivo de números, entonces Z⁺  k. Se dice a veces, que el conjunto de los enteros positivos, es el "más pequeño" conjunto inductivo de números. 

Teorema fundamental de Inducción Matemática. Sea S_n una función proposicional cuyo conjunto de referencia es Z⁺. Si S_n satisface las siguientes dos condiciones: 

 

Entonces S_n es cierta para todo n   Z⁺. 

Demostración

Sea k el conjunto de todos los enteros positivos para el cual S_n es cierta. Es decir:



De i. se observa que 1   k.

De ii. se observa que  k   k   (k + 1) k.

Por tanto k es un conjunto inductivo y por la definición de k se sabe que k   Z⁺.

De otra parte  Z⁺  k. Por consiguiente  Z⁺= k, es decir S_n es cierta para todo n   Z⁺. 

DEMOSTRACIONES POR INDUCCIÓN

El razonamiento para demostrar una proposición cualquiera mediante el esquema del razonamiento es como sigue. Llamemos   a la proposición, donde   es el rango.

§  Se demuestra que  , el primer valor que cumple la proposición (iniciación de la inducción), es cierta.

§  Se demuestra que si se asume   como cierta y como hipótesis inductiva, entonces   lo es también, y esto sin condición sobre el entero natural   (relación de inducción).

Luego, demostrado esto, concluimos por inducción, que   es cierto para todo natural  .

La inducción puede empezar por otro término que  , digamos por  . Entonces   será válido a partir del número , es decir, para todo natural  .

Ejemplo 1

Para todo  ,   es un número que acaba en 6.

Sea   la proposición: «  acaba en 6».

§  Es claro que   es cierto, porque  .

§  Supongamos que   es cierto para un valor de   natural, y probemos  .

o   Un entero acaba por 6 si se puede escribir así:  , con   entero positivo o igual a cero. La hipótesis es, pues,  .

Entonces:  , con  , entero.

Esta última escritura prueba que   acaba por 6, o sea que   es cierto.

Luego   es cierto para todo .

La inducción es válida por la construcción misma del conjunto de los naturales mediante los axiomas de Peano. En este caso:

§  1 es un natural;

§  si   lo es, entonces   (sucesor de  ) lo es también.

Existen otras inducciones, para otros conjuntos elaborados de forma distinta, como por ejemplo la inducción transfinita, y la inducción sobre las fórmulas de la lógica proposicional.

INDUCCIÓN MATEMÁTICA

En matemáticas, la inducción es un razonamiento que permite demostrar una infinidad de proposiciones, o una proposición que depende de un parámetro que toma una infinidad de valores enteros. En términos simples, la inducción matemática consiste en el siguiente razonamiento:

Premisa mayor: El número entero tiene la propiedad.

Premisa menor: El hecho de que cualquier número entero tenga la propiedad implica que también la tiene (que se anota).

Conclusión: Todos los números enteros a partir de tienen la propiedad .

 

PRINCIPIO DE INDUCCIÓN MATEMÁTICA.

 

La inducción matemática se usa a menudo para verificar o probar, una conjetura obtenida mediante inducción no matemática. Hablando con precisión, el axioma de inducción dice: si M es un conjunto de enteros positivos, con las siguientes propiedades

IA. M Contiene al entero 1, y,

IIA. Si M contiene al entero n, se puede demostrar que M contiene además al entero n+1, entonces M contiene a todos los enteros positivos.

La primera parte del axioma de inducción, IA suele llamarse base, y la segunda parte, IIA parte inductiva. El axioma de inducción es útil para demostrar ciertas expresiones matemáticas. Suponiendo que la proposición P(n) es verdadera o falsa dependiendo solo del valor de la n, el axioma de inducción se puede utilizar para demostrar que si

IB. P(1) es verdadera, y

IIB. El saber que P(n) es verdadera, implica que P(n+1) es también verdadera, entonces P(n) se cumple para cualquier n.

Usamos inducción sobre los naturales para: Demostrar que todos los números naturales tienen una cierta propiedad.

Definir diversos objetos asociados a los números naturales: Definiciones inductivas/recursivas de funciones relaciones etc. Ejemplo: n!= 1, (n+1)!= (n+1)∗n!

La inducción nos permite demostrar que existe una única función: N→N que satisface las ecuaciones de arriba.

Hay al menos tres principios de inducción para los naturales que son equivalentes.