unidad V

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+ 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  S1 = {1, 3, 5, 7, ...} no es un conjunto inductivo, porque no obstante que 1   S1; (1+1) S1.

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 Sn una función proposicional cuyo conjunto de referencia es Z+. Si Sn satisface las siguientes dos condiciones: 


 

Entonces Sn es cierta para todo n   Z+. 

Demostración

Sea k el conjunto de todos los enteros positivos para el cual Sn 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 Sn 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.

<>§<>§Ejemplo 1

Para todo  ,   es un número que acaba en 6.
Sea   la proposición: «  acaba en 6».

<>§<>§<>oEntonces:  , 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:

<>§<>§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.