La Inducción, el buen orden y el descenso infinito

Una de las cosas mas importantes en matemáticas es el principio de inducción. Sea A(n) una propiedad de algunos números de modo que ésta propiedad se “contagie” de un número al siguiente. Si el cero cumple esta propiedad, entonces todos los naturales cumplen.

Puesto como formula…
\displaystyle \textrm{Si } A(0) \textrm{ y } A(n) \Rightarrow A(n+1),\; \textrm{entonces} \; \forall i \in \mathbb{N},\;A(i)

un buen ejercicio que requiere inducción es el siguiente:

Encontrar todas las funciones de números naturales que cumplen con que f(n+f(m)) = f(n) +m

Pero hay un hecho equivalente en los números naturales, se le llama el principio del buen orden:

Cualquiér subconjunto de los números naturales tiene un mínimo.

Para ilustrar aquí está la demostración de una implicación:
Supongamos que cualquier conjunto de naturales tienen un mínimo, entonces el siguiente conjunto tiene un mínimo:

\displaystyle \mathbb{A} = \left\{ n \in \mathbb{N} \mid A(n) \; \textrm{no se cumple}\right\}
llamemos m a ese mínimo. si m no es cero, entonces m-1 \not\in \mathbb{A} y se cumple A(m-1), por lo tanto A(m) contradicción! (m es el primero que no cumple).

El principio del buen orden se usa mucho con otra técnica llamada descenso infinito. A veces para encontrar si existe o no un objeto suponemos que hay alguno de tamaño n y lo transformamos para encontrar otro de tamaño menor, a esa técnica se le llama descenso infinito, es muy usada para demostrar por contradicción, p.ej

Encontrar las soluciones enteras de
\displaystyle x^2+y^2=7xyn

para resolverlo primero hay que ver cuáles son las congruencias de un cuadrado módulo 7:
1, 4, 2, 2, 2, 4, 1, 0
Es fácil notar aqui que ninguna suma de dos residuos es cero, mas que cuando ambos son cero, o sea si ambos son divisibles por 7. En ese caso se pueden escribir como 7a y 7b y nos queda la siguiente ecuación:
\displaystyle 7^2a^2 + 7^2b^2 = 7^3abn
que es equivalente a
\displaystyle a^2+b^2=7abn
pero en esta ultima a y b son menores… Entonces si hubiera una solución entera distinta de cero, podríamos encontrar otra menor (eso contradice el principio del buen orden)

About these ads

Un comentario en “La Inducción, el buen orden y el descenso infinito

incluye tu respuesta

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s