Respuestas
Respuesta:
Los números enteros y su ordenación. El principio de inducción matemática.
Los números enteros
Los números enteros se definen como el conjunto de los números Z={...,-2,-1,0,1,2,3,...}. Dentro de este conjunto está el subconjunto de los números naturales, N={1,2,3,4,...}. Es decir, el subconjunto de los números enteros positivos (mayores que 0).
Pueden definirse en Z dos operaciones internas binarias + , . : Z x Z ⇒ Z, a las que llamamos suma y producto, respectivamente. Estas operaciones cumplen las siguientes propiedades:
Cerradas: a+b ∈ Z y a.b ∈ Z, ∀a,b ∈Z
Conmutativas: a+b = b+a , a.b = b.a , ∀ a,b ∈ Z
Asociativas: a+(b+c) = (a+b)+c , a.(b.c) = (a.b).c , ∀ a,b ∈ Z
Existencia de elementos neutros: a+0 = a , a.1 = a , ∀ a ∈ Z
Existencia de elemento opuesto para la suma: ∀a ∈Z existe -a ∈ Z tal que a + (-a) = 0
Cancelativa: Si a es distinto de 0, y a.b = a.c entonces b = c
Distributiva: a.(b+c) = a.b + a.c ∀ a,b,c ∈ Z
La ordenación de los números enteros
En Z se puede definir una relación de orden total, con el orden usual <. Así, para cualesquiera dos elementos distintos de Z, a<b o bien b<a. Es decir, Z es un conjunto totalmente ordenado.
Esta relación de orden total es compatible con la suma y el producto:
a < b ⇒ a+c < b+c, para todo entero c.
a < b ⇒ a.c < b.c, para todo entero c mayor que 0.
Dado un (A,<) conjunto ordenado y dado un subconjunto no vacío S de A, se dice que:
c ∈ A es cota inferior de S si c < x, para todo x ∈ S
m ∈ S es mínimo de S si m < x, para todo x ∈ S
Se dice por tanto que S está acotado inferiormente si existe un elemento c ∈ A que es cota inferior de S.
Axioma de buena ordenación en (Z , <)
Si X es un subconjunto no vacío de Z y está acotado inferiormente, entonces X tiene mínimo (habrá pues siempre un primer elemento del conjunto).
Una consecuencia inmediata de esta propiedad es que un subconjunto de los números naturales también tendrá mínimo, evidentemente.
El principio de inducción matemática
Formulación del principio de inducción:
Sea S ⊂ N tal que
1 ∈ S
si k ∈ S ⇒ k+1 ∈ S
Entonces S = N.
Si la pertenencia al conjunto S viene determinada por una propiedad P que queramos probar, podríamos utilizar el principio de inducción para demostrar que esa propiedad se satisface para todo entero positivo.
Otra formulación del principio de inducción:
Dado un enunciado P dependiente de un parámetro n ∈ Z, supongamos que se demuestra que:
P(n0) es cierto para un cierto n0 ∈ Z
Siempre que P(k) es cierto para cualquier entero k > n0, entonces es cierto para el siguiente entero P(k+1).
Entonces podemos afirmar que P(n) es cierto ∀n ∈ Z con n > n0
La demostración de un enunciado matemático mediante el principio de inducción, consiste primero en probar que para el caso básico inicial de n0 se satisface el enunciado. Después supondremos que se cumple para un determinado valor k mayor que n0 (a esta suposición se la llama hipótesis de inducción) y comprobamos si se satisface también para k+1. Si también se cumple el enunciado para k+1, entonces quedará demostrado que se cumple el enunciado para todo entero mayor o igual que n0.
El principio de inducción fuerte:
A veces resulta conveniente tomar como hipótesis de inducción la suposición de que el resultado es cierto para todos los valores anteriores relevantes n < k, en lugar de suponer cierto sólo el caso n = k. Esta variante del principio de inducción se la suele llamar principio de inducción fuerte, que se formularía así:
Dado un enunciado P(n) dependiente de un parámetro n ∈ Z, supongamos que se demuestra que:
P(n0) es cierto para un cierto n0 ∈ Z
Siempre que P(m) es cierto para cualquier entero n0 < m < k, entonces P(k+1) es cierto.
Entonces podemos afirmar que P(n) es cierto ∀n ∈ Z con n > n0
Un ejemplo de prueba mediante el principio de inducción matemática: el juego del NIM
Este sencillo juego por turnos para dos jugadores puede presentar algunas variantes en sus reglas; nosotros vamos a ver ahora la versión más simple. Se trata de disponer sobre el tablero, en la forma que se desee, un número cualquiera de objetos iguales -normalmente se usan palillos. En cada turno un jugador elimina del tablero uno, dos o tres objetos. El jugador que quite el último objeto es el que pierde.
Este juego o alguna de sus variantes ha sido muchas veces usado en la enseñanza informática como práctica de programación básica, o como ejemplo de estudio cuando alguien empieza a estudiar la disciplina de la Teoría de Juegos. Mediante el principio de inducción fuerte es posible demostrar que en la mayor parte de los casos existe una estrategia ganadora para el primer jugador en el juego del Nim. Pinchando en la imagen de abajo se abrirá una ventana nueva en donde se demostrará esta estrategia.