Posts Tagged ‘Inducción completa’

Euclides y sus primos

11/10/2009

El teorema fundamental de la aritmética aparece publicado en los Elementos de Euclides, Libro VII, proposiciones 30 y 32. La primera demostración completa y correcta del resultado se debe a Gauss. A continuación presentamos la demostración de Euclides para la existencia.

Teorema Fundamental de la Aritmética. Cualquier número natural mayor que uno se descompone como producto de factores primos. Además, la descomposición es única salvo el orden de los factores.

Demostración. Razonamos por inducción completa. La proposición es trivial cuando n=2 porque se trata de un número primo. Supongamos que cualquier número natural m \in \{2,3, \ldots , n\} se descompone como producto de factores primos y veamos cómo n+1 también admite una factorización de este tipo. Si n+1 es primo entonces la descomposición es trivial, y en caso contrario n+1=r \cdot s donde 2 \leq r, s\leq n. La hipótesis de inducción conduce a factorizaciones r=p_1 \cdots p_j, s=q_1 \cdots q_k, de donde se obtiene la descomposición n+1=p_1 \cdots p_j \cdot q_1 \cdots q_k.

*   *   *   *   *

Existen infinitos números primos. La demostración más antigua que se conoce para este resultado se debe a Euclides y aparece publicada en sus Elementos, Libro IX, Proposición 20.

Teorema de Euclides. Existe una cantidad infinita de números primos.

Demostración. Razonamos por reducción al absurdo. Supongamos que solamente hay una cantidad finita de números primos, digamos p_1, \ldots , p_r. Ahora definimos n= p_1 \cdots p_r+1 y observamos que n no es divisible por ningún p_j cuando 1 \leq j \leq r porque el resto de la división es igual a uno. La contradicción ha llegado porque n+1 bien es primo y hemos comcluido o bien tiene un factor primo p de modo que p \notin \{p_1 \ldots , p_r\} y también hemos concluido.

Inducción matemática

08/10/2009

La inducción matemática es una forma de demostración que se usa para establecer la validez de una proposición acerca de los números naturales. Se procede probando que la proposición es cierta para el primer número natural y después probando que si la proposición es cierta para un número natural entonces también es cierta para el siguiente. Este método se puede enunciar formalmente del siguiente modo.


Principio de inducción matemática.
Sea P \subseteq \mathbb{N} y supongamos que

  • 1 \in P,
  • n \in P \Longrightarrow n+1 \in P.

Entonces P=\mathbb{N}.

El conjunto P representa a aquellos números naturales que satisfacen la proposición que se quiere demostrar. La condición n \in P se llama hipótesis de inducción y la implicación n \in P \Longrightarrow n+1 \in P se llama paso inductivo. La siguiente forma equivalente del principio de inducción matemática consiste en realizar la hipótesis de inducción sobre un número natural y todos los anteriores a él.


Principio de inducción completa.
Sea P \subseteq \mathbb{N} y supongamos que

  • 1 \in P,
  • \{1, \ldots ,  n\} \subseteq P \Longrightarrow n+1 \in P.

Entonces P=\mathbb{N}.