Archivo de la etiqueta: principio de inducción

Cálculo Diferencial e Integral I: Repaso. Inducción matemática.

Introducción

En el curso de Álgebra Superior I se presenta al conjunto de los números naturales ($\mathbb{N}$). Posteriormente, en el curso de Álgebra Superior II se habla mucho más de ellos: se construyen a partir de teoría de conjuntos y se muestran desde los fundamentos muchas de sus propiedades.

Nosotros no nos enfocaremos en los aspectos anteriores, pero sí aprovecharemos que dicho conjunto posee una propiedad muy importante: el principio de inducción matemática. Como mencionamos en la entrada pasada, este método de demostración es aplicado frecuentemente en las pruebas en las que se desea probar que alguna propiedad se satisface para todos los números naturales.

En Cálculo Diferencial e Integral I haremos uso de la Inducción matemática constantemente, por lo que en esta entrada daremos una visita a lo necesario para nuestro curso.

Efecto dominó

Imagina que te han regalado una cantidad infinita de fichas de dominó y que has decidido acomodadas en una fila, una tras otra. Tu propósito al terminar de acomodarlas es el dejar caer todas las fichas, por ello consideras empujar la primer ficha para que al caer esta choque con la segunda provocando su caída y así sucesivamente.

El riesgo del Efecto Dominó: Micro triangulaciones y sus ventajas en  Trabajos de Investigación

Una vez que has decidido poner en marcha tu plan y empujas la ficha 1, te comienzas a preguntar: ¿Cómo puedo asegurar que la ficha 1,000 caerá si sólo he visto caer las primeras 50 fichas? ¿Y que hay de la ficha 1,000,000?

El Principio de Inducción es el que daría respuesta a tu pregunta. El razonamiento de este principio sustenta que si sabes que el procedimiento se ha cumplido para las primeras 50 fichas, en consecuencia cada ficha irá cayendo al final para cualquier ficha que consideres.

Ahora que tenemos una noción de su comportamiento, veremos la definición formal.

Principio de Inducción matemática

Definición: Sea $P$ una propiedad y $n\in \mathbb{N}$. Decimos que la propiedad $P$ es válida para todos los naturales si tenemos que:

  1. La propiedad $P$ se cumple para 0.
  2. Si la propiedad $P$ se cumple para $n \Rightarrow$ la propiedad también se cumple para $n + 1$.

El punto número 1 es conocido como Base de Inducción. El antecedente del punto número 2 es llamado Hipótesis de Inducción y su consecuente Paso Inductivo. En algunos problemas basta con demostrar la afirmación únicamente cuando $n\geq 1$. En estos casos, la base de inducción

A continuación veremos un par de ejemplos para ver cómo funciona dicho principio.

Ejemplo: Demuestra utilizando Inducción matemática la siguiente fórmula.

$$1+2+ \ldots + n = \frac{n(n+1)}{2}, \forall n\in \mathbb{N}$$
Demostración: Haremos inducción sobre $n$.
Base de Inducción.- Verificamos que la fórmula se cumple cuando $n=1$

\begin{align*}
\frac{1(1+1)}{2}&= \frac{1(2)}{2}\\
&=\frac{2}{2}\\
&= 1
\end{align*}
Lo cuál es cierto.

Hipótesis de Inducción.- Suponemos que la fórmula se cumple para cualquier $k\in \mathbb{N}$ así:
$$1+2+ \ldots + k = \frac{k(k+1)}{2}$$

Paso Inductivo.- Queremos probar que la fórmula se cumple para $k+1$, por lo que bastará probar la siguiente igualdad:
$$1+2+ \ldots + k+ (k+1) = \frac{(k+1)((k+1)+1)}{2}$$ es decir, $$1+2+ \ldots + k+ (k+1) = \frac{(k+1)(k+2)}{2}$$

Desarrollaremos el lado izquierdo de la igualdad sustituyendo lo que tenemos en la Hipótesis de Inducción, así queda lo siguiente:
\begin{align*}
1+2+ \ldots + k+ (k+1) &= \frac{k(k+1)}{2} + (k+1)\\
&= \frac{k(k+1)}{2}+ \frac{2(k+1)}{2}\\
&=\frac{k(k+1)+ 2(k+1)}{2}\\
&=\frac{(k+1)(k+2)}{2}
\end{align*}


$$\therefore 1+2+ \ldots + n = \frac{n(n+1)}{2}, \forall n\in \mathbb{N}$$

$\square$

Observación: $\therefore$ se lee «por lo tanto» y $\forall$ significa «para todo».

Ejemplo: Demuestra que $$2^{n} < n!$$ si $n > 4$.
Demostración: Aplicando inducción sobre $n$. Vemos que dada la condición de $n > 4$, bastaría probar que:
$$2^{n+3} < (n+3)!, \forall n \in \mathbb{N}$$

Y recordemos que $n!$ es llamado $n$ factorial que está definido como: $n! = 1\cdot 2 \cdot \ldots \cdot (n-1)(n)$ por lo que $4!= 4\cdot 3\cdot 2\cdot 1 =24$.

Base de Inducción.- Verificamos que la desigualdad se cumpla para $n=1$. Así sustituyendo vemos:
$$2^{1+3} = 2^{4}=16$$ y que $$(1+3)! = 4! =24$$.
Por lo que se cumple la desigualdad: $$2^{1+3} < (1+3)!$$.

Hipótesis de Inducción.- Suponemos que la desigualdad se cumple para cualquier $k \in \mathbb{N}$.
$$2^{k+3} < (k+3)!$$

Paso Inductivo.- Queremos probar que la desigualdad se cumple para $k+1$, esto sería:
$$2^{(k+1)+3} < ((k+1)+3)!$$ que es lo mismo que, $$2^{k+4} < (k+4)!$$.

Vemos que al reescribir la desigualdad anterior tenemos:
$$2\cdot 2^{k+3} < (k+3)! (k+4)$$.
Por hipótesis de inducción sabemos se cumple $2^{k+3} < (k+3)!$, por lo que si se cumple la desigualdad $2< k+4$ terminamos.

$P.d:$ $$2< k+4, \forall k\in \mathbb{N}$$
Demostración: Utilizaremos inducción sobre $k$.
Base Inducción.- Vemos para $k=1$ que $$2< 1+4 = 5$$ se cumple.

Hipótesis de Inducción.- Suponemos que es cierta la desigualdad $2< k+4$ para cualquier $k$.

Paso Inductivo.- Queremos probar que para $k+1$ se cumple la desigualdad $2< (k+1)+4$.
Observemos que $(k+1)+4= (k+4)+1$ que es el sucesor de $k+4$ por lo que cumple $k+4 < (k + 4)+1$.
Así haciendo uso de lo anterior y de la Hipótesis de Inducción se tiene lo siguiente:
$$2< k+4 < (k+4)+1 \Rightarrow 2 < (k+4)+1$$.
$$\therefore 2 < (k+1)+4$$
$$\therefore 2 < k+4 , \forall k\in \mathbb{N}$$

$\square$

Por lo que ya podemos afirmar que $$2\cdot 2^{k+3} < (k+3)! (k+4)$$.
Así concluimos: $$2^{n+3} < (n+3)!, \forall n \in \mathbb{N}$$

$\square$


Observación: $P.d.$ es una abreviación de «Por demostrar».

Principio de Inducción Fuerte

Existe otra forma de inducción que debemos recordar por su utilidad conocida cómo: Inducción Fuerte, que es consecuencia del Principio de Inducción que vimos al principio.

Definición (Principio de Inducción fuerte): Consideremos $P$ una propiedad y $n , l \in \mathbb{N}$. Decimos que la propiedad $P$ es válida para todos los naturales si tenemos que:

  1. $P$ se cumple para $0$.
  2. Si $P$ se cumple para cualquier $l \leq n \Rightarrow P$ se cumple para $n+1$.

Ejemplo: Todos los números positivos $n >1$ son producto de primos.

Demostración: Utilizaremos Inducción fuerte sobre $n$.
Base de Inducción.- Como tenemos la condición $n>1$ consideraremos $n=2$.
Observamos que $2 = 2$ es un producto de primos ( 2 cumple la definición de ser primo).

Hipótesis de Inducción.- Supongamos que todos los números desde 2 hasta $k$ cumplen ser producto de números primos.

Paso Inductivo.- Queremos probar que $k+1$ es producto de números primos.
Recordemos que todo número es primo ó compuesto, por lo que tenemos que considerar los siguientes casos.

Caso 1: $k+1$ es primo.
Como $k+1 = k+1$ se sigue que es producto de números primos y se cumple lo que queremos.

Caso 2: $k+1$ es compuesto.
Esto quiere decir que podemos expresar a $k+1$ como un producto de la siguiente manera:
$$k+1= a\cdot b$$ donde $k+1 > a$ y $b > 1$.
Observemos que las últimas desigualdades implican que $k \geq a,b \geq 2$, así por Hipótesis de Inducción $a$ y $b$ cumplen ser producto de números primos.
$\therefore k+1$ es producto de primos.
$\therefore$ Todos los números positivos $n >1$ son producto de primos.

$\square$

Tarea moral

A continuación encontrarás ejercicios en los que pondrás en practica el Principio de Inducción matemática:

  1. Probar que: $n^{3} – n$ es un múltiplo de 6, $\forall n\in \mathbb{N}$.
  2. Utiliza inducción para probar la siguiente igualdad:
    $$1^{2}+2^{2}+\ldots + n^{2} = \frac{n(n+1)(2n+1)}{6}, \forall n\in \mathbb{N}$$
  3. Demuestra que:
    $$1+3+5+7+\ldots +2n-1 = n^{2}, \forall n\in \mathbb{N}$$
  4. Demuestra por inducción sobre $n$, con $r \neq 1$:
    $$1+r+r^{2}+ \ldots +r^{n} = \frac{1-r^{n+1}}{1-r}$$
  5. Utiliza inducción para probar la siguiente igualdad:
    $$2+5+8+ \ldots+ (3n-1)= \frac{n(3n+1)}{2}$$

Más adelante

Ahora que hemos terminado con el repaso de Inducción matemática. En la siguiente entrada comenzaremos a ver un conjunto de números de suma importancia para el Cálculo: los reales.

Entradas relacionadas

Álgebra Superior II: El principio del buen orden

Introducción

En la entrada pasada definimos una relación de orden en el conjunto de números naturales, más aun, probamos algunas propiedades de esta nueva relación, de las cuales, la más importante fue que este orden era un orden total. Ya en los ejercicios morales, vimos que podíamos restringir esta relación a cualquier número natural $n$ para definir un orden en los conjuntos con $n$ elementos.

En esta entrada definiremos una de las propiedades más importantes del orden en los naturales: el principio de buena ordenación, veremos que en cierto sentido es equivalente al principio de inducción, y daremos una breve presentación a algunos otros conjuntos que en este sentido se comportan de forma similar a los naturales.

La propiedad de buena ordenación

Pensemos en un número natural $n\neq 0$ con el orden que este hereda de $\mathbb{N}$, abusando de la notación, podemos escribir de forma ordenada a $n$ como $\{0<1<…<n-1\}$, parece ser que no habrá muchas sorpresas a la hora de estudiar a los números como conjuntos ordenados. Sin embargo, vale la pena notar que debido a lo que probamos en la sección de El tamaño de los naturales, cualquier subconjunto $A$ de $n$ será finito. Gracias a esto, y a que demostramos que el orden es total, podemos comparar todos los elementos de $A$ y fijarnos en el menor de todos ellos. Antes de formalizar esta prueba, recordaremos qué significa que un elemento de un conjunto sea mínimo.

Definición. Si $A$ es un conjunto ordenado por $\leq$, decimos que $a_0\in A$ es un elemento mínimo, si para todo $a\in A$ se tiene que $a_0\leq a$.

Ahora sí, enunciamos y demostramos nuestro primer teorema

Teorema. Si $n\neq 0$ y $A\subseteq n$ es distinto del vacío, entonces existe $a_0$ mínimo en $A$

Demostración. El hecho de que $A$ sea un conjunto finito no necesita más demostración que la que se mencionó en el párrafo anterior. Entonces podemos proceder por inducción sobre $m=\vert A\vert$.

Como $A\neq \emptyset$ la base de inducción se probará para $m=1$. Es decir que $A=\{a\}$, evidentemente, el elemento $a$ es el mínimo de $A$.

Supongamos ahora que si un conjunto no vacío tiene $m$ elementos, entonces tiene un elemento mínimo y supongamos que $A$ es un conjunto con $\sigma(m)$ elementos. Como $A$ es no vacío, entonces podemos elegir algún $a\in A$ arbitrario, entonces el conjunto $A\setminus\{a\}$ es un conjunto con $m$ elementos, y por la hipótesis de inducción, tiene un mínimo, llamémoslo $a’$. Como el orden en $A$ es el de los naturales, y este es total, $a’$ y $a$ son comparables, llamemos $a_0$ al mínimo entre estos dos elementos y demostremos que $a_0$ es el mínimo de $A$.

Sea $x\in A$ arbitrario, si $x=a$, ya terminamos, pues por definición $a_0\leq a$, en caso contrario $x \in A\setminus\{a\}$, pero como $a’$ es el mínimo de este conjunto, entonces $a’\leq x$, y como $a_0\leq a’$, por transitividad concluimos que $a_0\leq x$, por lo que $A$ sí tiene mínimo.

$\square$

Como mencionamos antes, la propiedad de que todos los subconjuntos de un conjunto arbitrario tengan mínimo elemento es importante, por lo que damos la siguiente definición.

Definición. Si $B$ es un conjunto ordenado por $\leq$, decimos que $B$ tiene la propiedad del buen orden si todo subconjunto no vacío de $B$ tiene un mínimo.

Entonces el teorema anterior puede ser reformulado como

Teorema. Si $n$ es un número natural, entonces $n$ está bien ordenado

El conjunto de los números naturales está bien ordenado.

Un error lógico, sería asumir que por el teorema anterior, el conjunto de los números naturales también cumple la propiedad del buen orden, ya que a diferencia de cualquier número natural, en $\mathbb{N}$ existen conjuntos con una infinidad de elementos; sin embargo, aunque esta prueba no funcione, no se sigue que $\mathbb{N}$ no esté bien ordenado, es por esto que enunciamos el siguiente teorema.

Teorema. $\mathbb{N}$ satisface la propiedad del buen orden.

Demostración. Sea $A$ un subconjunto no vacío de números naturales, procedamos por contradicción, es decir, supongamos que $A$ no tiene elemento mínimo. Consideremos $B=\{n\in\mathbb{N}\mid m\leq n \Rightarrow m\notin A\}$, veamos que B es inductivo.

Evidentemente $0$ está en $B$, porque si no, existiría $m\leq 0$ tal que $m\in A$, como el único natural menor o igual a $0$ es $0$, tenemos que $0\in A$, pero entonces, $0$ sería un mínimo de $A$, ya que es menor o igual a todo natural.

Supongamos entonces que $n\in B$ y demostremos que $\sigma(n)\in B$, supongamos que no, entonces existirá $m\leq\sigma(n)$, tal que $m\in A$, como $m\in A$, por la definición de $B$, debe ocurrir que $n<m$ y por uno de los resultados de la entrada pasada, tenemos que $\sigma(n) \leq m$, por la antisimetría del orden, tenemos que $m=\sigma(n)$.

De nuevo usemos reducción al absurdo para probar que $\sigma(m)$ es un mínimo de $A$, si no lo fuera, existiría $a \in A$ tal que es falso que $\sigma(n)\leq a$, esto implicaría que es falso que $n<a$, es decir que $a\leq n$ y como $n\in B$, esto implicaría que $a\notin A $ lo cual es absurdo, entonces $\sigma(n)$ sí es un mínimo de $A$, pero de nuevo, esto es contradictorio con la suposición de que $A$ no tenía elemento mínimo, esta contradicción se deriva de suponer que $\sigma(n)\notin B$, entonces $\sigma(n)\in B$, por lo que el paso inductivo queda probado y $B=\mathbb{N}$

Como $B=\mathbb{N}$, debe ocurrir que $A= \emptyset$ ya que si $a\in A$, como $a\leq \sigma(a)$, por la definición de $B$ debería pasar que $\sigma(a)\notin B$, contradiciendo que $B=\mathbb{N}$, pero desde un inicio, supusimos que $A\neq \emptyset$, esto quiere decir que suponer que $A$ no tiene mínimo es absurdo. Entonces, concluimos que $A$ sí debe de tener un elemento mínimo.

$\square$

El principio de inducción y el principio del buen orden

La idea de una prueba más corta de este resultado se da en los ejercicios morales; sin embargo, damos esta prueba para ver como el principio de inducción prueba el del buen orden. De forma análoga podemos demostrar el principio de inducción a partir del principio del buen orden

Teorema. Supongamos cierto que $\mathbb{N}$ satisface la propiedad del buen orden, entonces, el principio de inducción también es cierto

Demostración. Sea $A$ un conjunto inductivo, debemos de demostrar que $A=\mathbb{N}$, supongamos que no lo es, entonces $\mathbb{N}\setminus A\neq\emptyset$, por lo que, por el principio del buen orden, este conjunto tiene un elemento mínimo, sea $n$ el mínimo. Como $A$ es inductivo, $0\in A$. por lo que $n\neq 0$, entonces existe un $m$ tal que $\sigma(m)=n$, como $n$ es el mínimo, de $\mathbb{N}\setminus A$, tenemos que $m\notin \mathbb{N}\setminus A$, por lo que $m\in A$, pero como $A$ es inductivo, $\sigma(m)=n\in A$, lo cual es una contradicción, entonces, $A=\mathbb{N}$

$\square$

En $\mathbb{N}$, existe otra formulación equivalente al principio de inducción, llamado principio de inducción fuerte, y dice que

Teorema. Si $A$ es un conjunto tal que:

  • $0\in A$
  • Es cierto que si $n\in A$ y para todo $m\leq n$, se tiene que también $m\in A$ entonces $\sigma(n)\in A$

Entonces $A=\mathbb{N}$

Los detalles de la prueba se mencionan en uno de los ejercicios morales.

Conjuntos bien ordenados.

Antes de estudiar otros conjuntos bien ordenados damos la siguiente proposición elemental

Teorema. Si $A$ es un conjunto bien ordenado por $\leq$, entonces $A$ es un orden lineal

Demostración. Sean $a,b\in A$, consideremos el conjunto $\{a,b\}\subset A$, como $A$ es un buen orden, entonces, este subconjunto tiene un elemento mínimo, es decir que $a\leq b$ ó $b\leq a$, esto quiere decir que los elementos son comparables.

$\square$

Hemos demostrado que todo número natural y el conjunto de los naturales, tienen un buen orden natural, una pregunta natural es si estos son los únicos conjuntos bien ordenados, la respuesta es que no; sin embargo hay varias cosas que analizar.

Lo primero que mencionaremos, es que todo conjunto finito $A$ y linealmente ordenado, satisface la propiedad del buen orden y más aun, se puede probar que si $\vert A\vert=n$, entonces el orden de $A$ y de $n$ son indistinguibles, detallamos esta afirmación en uno de los problemas de la tarea moral.

El caso infinito es más complicado, ya que existen muchos conjuntos numerables que pueden ordenarse de forma distinta a $\mathbb{N}$ y aun así tener la propiedad del buen orden, en realidad, es muy sencillo construirlos, como mencionamos en el siguiente teorema

Teorema. Si $A$ es un conjunto bien ordenado bajo $\leq$, entonces $\sigma(A)$ es un conjunto bien ordenado con el orden $\leq’=\leq\cup\bigcup_{a\in \sigma(A)}(a,A)$

Demostración. El hecho de que $\leq’$ es un orden, será un ejercicio moral, veamos que $\leq’$ está bien ordenado. Sea $B\subseteq \sigma(A)$ distinto del vacío, entonces debemos encontrar un elemento mínimo para $B$. Si $B=\{A\}$ el resultado es trivial.

Entonces supongamos que $B\neq\{A\}$ y consideremos $B\setminus \{A\}\subseteq A$, el cual es distinto del vacío. Como $A$ es un buen orden, entonces, existe $b$ elemento mínimo para este conjunto, afirmamos que $b$ también es un elemento mínimo para $B$. Para ver esto, sea $b’\in B$, si $b’\in B\setminus \{A\}\subseteq A$ el resultado se sigue de la definición de $b$, mientras que si $b’=A$, tenemos que $b’\leq A$ ya que por definición $(b’,A)\in \leq’$. Con esto finaliza la prueba.

$\square$

Aplicando el teorema anterior a $\mathbb{N}$, tenemos que $\mathbb{N}\cup\{\mathbb{N}\}$ es un buen orden con $\leq$ definido como $a\leq b$ si y solo si $a\in b$ o $a=b$, sin embargo, a diferencia de $\mathbb{N}$, este conjunto tiene un máximo, dígase $\mathbb{N}$ (ahora visto como elemento).

Otra cosa curiosa que podemos notar del conjunto $\sigma(\mathbb{N})$ es que aunque el principio del buen orden es válido, el principio de inducción no lo es, a diferencia de como pasaba en $\mathbb{N}$, en realidad, esta no es la única propiedad que perdemos, por ejemplo, en $\sigma(\mathbb{N})$, el cero no es el único elemento sin un antecesor, en realidad, esta es una de las razones por las que la prueba del principio de inducción a partir del principio del buen orden no es válida para este conjunto.

El estudio de los buenos ordenes es importante en Teoría de conjuntos y está muy relacionada con la teoría de conjuntos transitivos

Tarea moral

Los siguientes ejercicios y problemas te ayudarán a reforzar lo aprendido en esta entrada.

  • Si $A$ es un conjunto con $n$ elementos, y $\leq_A$ es un orden total en $A$, demuestra que existe una función $f:n \longrightarrow A$ tal que $n\leq m \Leftrightarrow f(n)\leq_A f(m)$. Sugerencia: Usa inducción sobre $n$ y después el principio del buen orden
  • Prueba el principio del buen orden a partir del axioma de regularidad y de la definición de $<$. Sugerencia: recuerda que el axioma de regularidad prohíbe la existencia de sucesiones infinitas de conjuntos tales que $…\in a_2\in a_1\in a_0$
  • Demuestra que en $\mathbb{N}$, el principio de inducción fuerte es equivalente al principio de inducción. Sugerencia: Prueba el principio de inducción fuerte a partir del débil, y el principio del buen orden a partir del fuerte.
  • Usando la notación del último teorema, demuestra que $\leq’$ sí define una relación de orden en $\sigma(A)$
  • Si $A$ es un conjunto bien ordenado e infinito con $a_0$ elemento mínimo, prueba que existe una función $f:\mathbb{N}\longrightarrow A$ tal que $f(0)= a_0$ y si $n\leq m$ entonces $f(n)\leq f(m)$. Sugerencia: Usa la técnica que se ocupó a la hora de demostrar que los naturales son el conjunto infinito más pequeño.

Más adelante.

Ya que hemos estudiado la propiedad más importante del orden en los naturales. solo falta ver como es que esta propiedad se relaciona con las operaciones que definimos, los resultados vistos en esta sección y en la siguiente, serán muy importantes en los siguientes temas que desarrollemos, ya que serán la base de muchos resultados, sobre todo al ver los resultados de la teoría de números en $\mathbb{Z}$, donde el orden, la inducción y el buen orden tendrán papeles fundamentales.

Entradas relacionadas

Álgebra Superior II: Definición de la suma y sus propiedades básicas

Introducción

Para continuar con nuestra tarea de construir las operaciones más elementales de los números naturales, en esta entrada definimos la conocida operación suma. Un buen ejercicio antes de empezar con el contenido de la entrada, es pensar ¿Cómo podemos definir la suma de dos números enteros? De nuevo nos encontramos con el problema de intentar definir formalmente algo que ha sido intuitivo para nosotros durante la mayor parte de nuestra vida.

Sin embargo, todo el trabajo que hicimos en las entradas anteriores, especialmente en la demostración del teorema de Recursión, nos servirán para poder dar una definición precisa de qué es la suma. Además, usando el principio de Inducción, podremos demostrar las propiedades que nos han sido tan familiares desde hace mucho tiempo.

La idea intuitiva de la suma

La primera forma en la que aprendimos a sumar, al menos de manera intuitiva y tal vez limitada, fue usando nuestros dedos. Ocuparemos esta idea como hilo conductor, para poder llegar a la definición recursiva de la suma. Con esta forma de pensar, si queríamos sumar $3+4$, poníamos frente a nosotros nuestras manos con los dedos abajo, e instantáneamente mencionábamos la palabra «tres«. Después estirábamos un primer dedo y al mismo tiempo, mencionábamos la palabra «cuatro» (a quien ahora conocemos como el sucesor de $3$), después alzábamos un segundo dedo y decíamos «cinco» (el sucesor de $4$) , y continuábamos de la misma manera hasta que tuviéramos cuatro dedos totalmente extendidos; momento en el cual, decíamos el resultado: «siete«.

Analicemos un poco qué es lo que queremos decir con «continuábamos de la misma manera«. Entre cada número que contábamos, varias cosas pasaban por nuestra mente. Al mencionar un número, lo primero que hacíamos era cerciorarnos que aún tuviéramos extendidos menos dedos de los que queríamos añadir. Si esta condición se satisfacía, teníamos que grabarnos el número que habíamos mencionado justo en ese instante (el olvidar dicho número, tenía como consecuencia empezar el procedimiento desde el inicio), después alzábamos el siguiente dedo, y mencionábamos el sucesor del número memorizado (es por esto que recordar ese número era tan importante). Muy a grandes rasgos esto es lo mismo que lo que haremos de manera formal.

Definición de la suma

Esperamos que en los párrafos anteriores puedas encontrar una analogía entre el algoritmo que usábamos para sumar cotidianamente, y el método recursivo que describiremos a continuación. Antes de precisar la definición de la suma, hay que aclarar que no definiremos «de golpe» qué quiere decir «sumar dos números». Más bien, lo que haremos es, para cada natural, decir qué quiere decir «sumarle otro». Lo haremos de esta manera pues esto es lo que nos permite hacer el teorema de Recursión. Así, para cada número natural $m$ (fijo) obtendremos una función que nos sume a ese número fijo, una cantidad arbitraria.

Definición: Sea $m\in\mathbb{N}$. Definimos la función $s_{m}:\mathbb{N}\longrightarrow\mathbb{N}$, como la única función que satisface las propiedades siguientes:

  1. $s_{m}(0)=m$
  2. $s_{m}(\sigma(n))=\sigma(s_{m}(n))$.

Denotaremos $s_{m}(n)$ como $m+n$.

Vale la pena hacer un par de comentarios de la definición anterior. Primero mencionamos que esta definición depende totalmente del teorema de Recursión Débil. Si regresas al enunciado del teorema, podemos notar que la función $s_m$ se obtiene tomando $X=\mathbb{N}$, $x_{0}=m$, $f=\sigma$ y $g=s_{m}$.

En segundo lugar, hay que remarcar que a pesar de nuestra intuición, los papeles de $m$ y $n$ en la expresión $m+n$, no son intercambiables. Por definición $m+n=s_{m}(n)$, mientras que $n+m=s_{n}(m)$. A primera vista, estos valores no tienen por qué coincidir. Veremos que en efecto esta y otras propiedades sí son válidas, para que posteriormente podamos utilizarlas de manera directa.

Aprender a sumar cero

De aquí en adelante probaremos varias propiedades de la suma. Debido a la definición recursiva de esta función, la mayor herramienta que ocuparemos es el principio de Inducción.

Antes de lanzarnos a demostrar la primer propiedad, nota que directamente de las definiciones de las funciones $s_{m}$ y de la notación que estamos usando, se tiene que $m+0=s_m(0)=m$. Ahora nos gustaría ver que también $0+m=m$, pero como aún no sabemos que la suma sea conmutativa, tendremos que probarlo por inducción.

Proposición: Para todo $n\in\mathbb{N}$ se tiene que $s_{0}(n)=n$, es decir, $0+n=n$

Demostración. Como se mencionó, procedamos por inducción sobre $n$.

Base inductiva: Por el punto (1) de la definición de $s_0$, tenemos que s_{0}(0)=0.

Hipótesis inductiva: Supongamos que para algún $n\in\mathbb{N}$, se tiene que $s_{0}(n)=n$

Paso inductivo: Demostremos que $s_{0}(\sigma(n))=\sigma(n)$.

La demostración se sigue de la siguiente cadena de igualdades, las cuales justificamos una a una abajo:

\begin{align*}
s_{0}(\sigma(n))&=\sigma(s_{0}(n)) \\&\overset{\text{H.I.}}{=}\sigma(n).
\end{align*}

La primera igualdad sucede por el punto (2) de la definición de $s_0$. La segunda igualdad sucede por la hipótesis inductiva, lo cual estamos indicando con un «H.I.» sobre el símbolo de igualdad.

Esto termina el paso inductivo y entonces la proposición se vale para todos los naturales.

$\square$

Así, ya sabemos «sumar cero».

Aprender a sumar uno

Veamos ahora que nuestra intuición de «sumar uno» en efecto coincide de manera formal con «ir al sucesor».

Observación: Tenemos la siguiente cadena de igualdades \[n+1=s_{n}(1)=s_{n}(\sigma(0))=\sigma(s_{n}(0))=\sigma(n).\]

La primera es por nuestra elección de notación. La segunda por la definición del símbolo 1, pues simplemente es el sucesor de 0. La tercera es por el punto (2) de la definición de $s_n$. Finalmente, la última es por el punto (1) de la definición de $s_n$.

$\square$

Proposición: Para todo $n\in\mathbb{N}$ se tiene que $s_{1}(n)=\sigma(n)$, es decir, que al juntarlo con la observación anterior obtenemos $1+n=\sigma(n)=n+1$.

Demostración. Demostremos que $s_1(n)=\sigma(n)$ por inducción sobre $n$. Tenemos que $s_{1}(0)=1=\sigma(0)$ por el punto (1) de la definición de $s_1$ y por la definición de 1. Esto muestra que la igualdad se cumple en el caso base $n=0$.

Nuestra hipótesis de inducción es suponer que $s_{1}(n)=\sigma(n)$ y a partir de ella debemos demostrar que $s_{1}(\sigma(n))=\sigma(\sigma(n))$. Esto lo logramos mediante la siguiente cadena de igualdades:

\begin{align*}
s_{1}(\sigma(n))&=\sigma(s_{1}(n))\\ &= \sigma(\sigma(n))
\end{align*}

La primera igualdad se debe al punto (2) de la definición de $s_1$. La segunda, a la hipótesis inductiva.

$\square$

La suma es asociativa

Con los resultados probados en las dos secciones anteriores, continuamos ahora probando propiedades más interesantes de la suma. Aunque las aprendimos desde la educación básica, ahora será momento de justificar por qué se deducen de lo que hemos construido. Empezamos por la asociatividad.

Proposición (asociatividad): Si $a, b, n$, son naturales arbitrarios, entonces $(a+b)+n=a+(b+n)$.

Como es usual, aquí los paréntesis significan «hacer esa operación primero». Si quisiéramos usar la notación formal, tendríamos que enunciar la asociatividad como $$s_{a+b}(n)=s_a(s_b(n)),$$ y cuando hagamos la demostración aprovecharemos la definición de estas funciones $s_{a+b}$, $s_a$ y $s_b$.

Demostración. Procedamos por inducción. Tenemos tres variables naturales. ¿Sobre cuál hacemos inducción? Esto es una decisión importante y el hacer una elección incorrecta puede dificultar la prueba o impedir concluirla. Haremos inducción sobre $n$, pero te recomendamos que intentes hacerlo sobre las otras variables para detectar las dificultades que pueden surgir.

Base inductiva: $(a+b)+0=a+b=a+(b+0)$. En el primer paso usamos el punto (1) de la definición de $s_{a+b}$ y en el segundo usamos el punto (1) de la definición de $s_b$.

Hipótesis inductiva: Supongamos que $(a+b)+n=a+(b+n)$. Recuerda que en una prueba inductiva sólo se hace la hipótesis inductiva para un valor fijo de $n$, pero lo que se quiere suponer es que se vale para todo valor de $n$. Así, no estamos suponiendo que cualquier $n$ pueda asociarse con cualesquiera dos números, solo estamos suponiendo que una $n$ fija puede asociarse con los valores fijos de $a$ y de $b$; más aún, el orden de $a$ y $b$ importa, ya que no hemos demostrado aún la conmutatividad.

Paso inductivo: Demostremos que $(a+b)+\sigma(n)=a+(b+\sigma(n))$.

Hagamos esto mediante la siguiente cadena de igualdades:

\begin{align*}
(a+b)+\sigma(n)&=\sigma((a+b)+n)\\
&\overset{\text{H.I}}{=}\sigma(a+(b+n))\\
&=a+\sigma(b+n)\\
&=a+(b+\sigma(n)).
\end{align*}

Aquí las igualdades se siguen, respectivamente, de la definición de $s_{a+b}$, de la hipótesis inductiva, de la definición de $s_a$ y de la definición de $s_b$. Con esto, concluimos la prueba del paso inductivo y con ello la prueba por inducción.

$\square$

En la demostración anterior ya no estamos siendo tan específicos con exactamente qué parte de la definición de las funciones estamos usando. Sin embargo, te sugerimos completar estos detalles pues te ayudarán a entender mucho mejor por qué cada uno de los pasos tiene su justificación.

La suma es conmutativa

Otra de las propiedades de la suma que nos enseñan en educación básica es que «el orden de los factores no afecta el resultado». Esto tiene un nombre en matemáticas formales: conmutatividad. El objetivo de la siguiente proposición es demostrar que en efecto la suma es conmutativa.

Proposición (conmutatividad): Si, $n, m$ son naturales, entonces $n+m=m+n$.

En términos de las funciones que construimos mediante el teorema de recursión esto se ve como $s_n(m)=s_m(n)$.

Demostración. De nuevo, procedamos por inducción sobre $n$, por la misma razón remarcamos que entonces $m$ es un número arbitrario pero fijo.

Base inductiva. Por la primer proposición que probamos, tenemos que $0+m=m=m+0$.

Hipótesis de Inducción: Supongamos que $n$ cumple que $n+m=m+n$.

Paso inductivo: Demostremos que $\sigma(n)+m=m+\sigma(n)$.

Hagamos esto mediante la siguiente cadena de igualdades:

\begin{align*}
m+\sigma(n)&=\sigma(m+n)\\
&\overset{H.I.}{=}\sigma(n+m)\\
&=n+\sigma(m)\\
&=n+(1+m)\\
&=(n+1)+m\\
&=\sigma(n)+m.
\end{align*}

Como siempre, es importante justificar cada igualdad. Pero ahora es tu turno. ¿Cuáles son las justificaciones de cada una de estas igualdades? Nota que algunas serán las definiciones, algunas serán la notación que estamos usando y finalmente otras se deducen de propiedades que ya demostramos (como la asociatividad).

$\square$

La suma se cancela

Imagina por un momento que tenemos una igualdad del estilo $x+8=y+8$ en los números naturales. Nos gustaría poder concluir que $x=y$. Sin embargo, no podemos hacer el «truco tradicional» de «restar 8» en cada lado de la igualdad para cancelar al 8, pues en los naturales no existe la operación de resta. Nos encontraremos con ella más adelante, hasta que trabajemos con los números enteros.

Aunque no podamos restar, de cualquier forma podemos realizar cancelaciones de este estilo. La siguiente proposición formaliza este hecho.

Proposición (cancelación por la derecha): Si, $a, b, n$ son naturales, tales que $a+n=b+n$, entonces $a=b$.

Demostración. Como ya esperábamos, sean $a$ y $b$ arbitrarios, y procedamos por inducción sobre $n$.

Base inductiva. Si $a+0=b+0$, por definición de $s_a$ y $s_b$ obtenemos $a=b$.

Hipótesis inductiva. Supongamos que $n$ es tal que cada vez que tengamos $a+n=b+n$, obtenemos que $a=b$.

Paso inductivo. Demostremos que si $a+\sigma(n)=b+\sigma(n)$, entonces $a=b$.

Entonces supongamos que $a+\sigma(n)=b+\sigma(n)$. Por definición $a+\sigma(n)=\sigma(a+n)$ y $b+\sigma(n)=\sigma(b+n)$. Por nuestra hipótesis tendríamos entonces que $\sigma(a+n)=\sigma(b+n)$. Usando el cuarto axioma de Peano, obtendríamos entonces que $a+n=b+n$. Finalmente, la hipótesis inductiva nos garantiza que entonces $a=b$, como buscábamos.

$\square$

Podemos enunciar el resultado anterior en una forma un poco más «funcional».

Corolario: Las funciones $s_{m}$ con $m\in \mathbb{N}$ son inyectivas.

Demostración: Con todas las herramientas que hemos desarrollado, ya no será necesario ocupar la inducción.

Si $s_{m}(a)=s_{m}(b)$, por la conmutatividad de la suma, tenemos que $s_{m}(a)=s_{a}(m)$ y $s_{m}(b)=s_{b}(m)$. Esto quiere decir que $a+m=b+m$, y por la proposición anterior, $a=b$.

$\square$

Con esto hemos demostrado las propiedades más fundamentales de la suma, a partir de las cuales podremos probar muchas más.

Resumen de propiedades de la suma

Para recapitular, en esta entrada demostramos las siguientes propiedades de la suma y por lo tanto podremos usarlas directamente de aquí en adelante:

  • Para todo $n$ natural, se tiene $0+n=n=n+0$.
  • Para todo $n$ natural, se tiene $1+n=\sigma(n)=n+1$.
  • Para $m$ y $n$ naturales cualesquiera, se tiene $m+n=n+m$.
  • Para $l,m,n$ naturales cualesquiera, se tiene que $l+(m+n)=(l+m)+n$.
  • Para $l,m,n$ naturales cualesquiera, si $m+l=n+l$, entonces $m=n$.

Tarea moral

Los siguientes ejercicios y problemas te ayudarán a reforzar lo aprendido en esta entrada.

  1. Demuestra que si $a, b\in \mathbb{N}$, y $a+b=0$, entonces $a=b=0$.
  2. Demuestra que si $a+a=b+b$, entonces $a=b$. ¡Ten cuidado! En los números naturales no se vale «dividir», así que más bien tendrás que hacer una prueba inductiva.
  3. Sean $m,n,l$ naturales cualesquiera. Demuestra, usando sólo las propiedades que ya mostramos (ya sin inducción), que todas las siguientes expresiones son iguales:
    \begin{align*}
    m+(n+l)\\
    (l+m)+n\\
    n+(m+l)\\
    (n+l)+m\\
    \end{align*}
  4. ¿Cuáles de las funciones $s_{m}$ tienen inversa? ¿Qué significa esto?
  5. Antes de dominar las tablas de multiplicar de memoria, ¿Cómo multiplicabas? Ocupa esta idea para motivar una definición recursiva del producto de números naturales.

Más adelante…

Ya que conocemos las propiedades de la suma, podemos pasar a definir el producto, y análogamente, a como lo hicimos antes, estudiaremos sus propiedades usando el principio de Inducción.

Entradas relacionadas

Álgebra Superior II: Principio de inducción y teoremas de recursión

Introducción

Inducción y recursión son dos conceptos similares con los que seguramente te has topado en tu formación matemática, e incluso tal vez antes. Muchas veces se llegan a confundir ambos conceptos, ya que ambos tienen una fuerte relación con el 5° axioma de Peano.

Aunque lo detallaremos a lo largo de la entrada, el principio de Inducción es una propiedad de los números naturales, que nos sirve para demostrar que todos los naturales satisfacen una propiedad. Es decir, es una estrategia de demostración. En contraste, la recursión es un resultado que justifica el hecho de poder dar una definición para todos los naturales, basándonos en la definición de su antecesor. En otras palabras, es una estrategia de definición.

Al final de la entrada demostraremos el teorema de recursión débil, en cuya prueba, podremos apreciar cómo es que depende directamente del Principio de inducción.

Pruebas por inducción

Recordemos el 5° axioma de Peano, el cual probamos en la entrada pasada que se satisface en nuestro modelo:

Si $S\subset \mathbb{N}$ satisface que

  • $0\in S$ y
  • si $n\in S$, implica que $\sigma(s)\in S$,

entonces $S=\mathbb{N}$.

Como hemos mencionado en entradas anteriores, esta proposición es muy similar al principio de Inducción que probablemente hayas ocupado desde el curso de Álgebra Superior I. Más aún, en la entrada pasada, seguimos la misma estrategia que en otros cursos, a la hora de ocupar el 5° axioma. Efectivamente, la equivalencia entre ambos resultados es casi inmediata, y como ejemplo ilustrativo, probaremos el Principio de Inducción a partir del 5° axioma de Peano.

Proposición (Principio de Inducción): Sea $P(n)$ una propiedad, es decir, una proposición matemática que depende de un entero $n$. Si se tiene que:

  1. $P(0)$ es verdadera y
  2. cada vez que $P(n)$ es cierto, también lo es $P(n+1)$,

entonces P(n) es cierta para todos los números naturales.

Demostración. Sea $P(n)$ una propiedad que satisface 1. y 2. y consideremos el conjunto $S:=\{n\in\mathbb{N}: P(n)\text{es verdadera}\}$.

Como $P(0)$ es verdadera, entonces $0\in S$.

Tomemos $n\in S$, entonces $P(n)$ es verdadera, y por 2., tenemos que $P(n+1)$ es verdadera; es decir, $n+1\in S$. Por el 5° Axioma de Peano, se tiene que $S=\mathbb{N}$, por lo que por la definición de $S$, se tiene que $P(n)$ es cierta para cada $n\in \mathbb{N}$

$\square$

Definiciones por recursión

Una de nuestras primeras ideas para poder construir a $\mathbb{N}$, fue intentar construir a mano cada elemento. Para esto, dimos una definición de lo que significaba el $0$ y el sucesor de un número. Después empezamos a iterar una y otra vez la función sucesor para obtener el sucesor del último número encontrado. Discutimos por qué es que esta idea no sería el mejor camino (sólo nos permite llegar hasta una cantidad finita de naturales), por lo tuvimos que introducir el Axioma del Infinito para resolver el problema. Veamos la analogía entre esta idea y el siguiente ejemplo intuitivo.

Ejemplo: Definamos la función factorial de un número natural, como:

  • $0!=1$
  • $(n+1)!=(n!)(n+1)$

Entonces, $3!:=(2!)(3)=(1!)(2)(3)=(0!)(1)(2)(3)=(1)(1)(2)(3)=6$.

Recordemos que al definir a los naturales, necesitábamos conocer un número para poder definir su sucesor. Aquí sucede lo mismo: en la definición de factorial necesitamos conocer quién es el factorial de un número para poder definir el factorial de su sucesor. A este tipo de definiciones se les conoce como definiciones recursivas, ya que para definir algo para un número, necesitamos tener conocimiento del valor de la función en los números anteriores.

Queda una pregunta muy importante. Si a los naturales no los pudimos definir de manera recursiva, ¿por qué podemos afirmar que la función factorial sí existe? A continuación enunciaremos algunos teoremas que nos garantizarán que sí podemos hacer este tipo de definiciones recursivas en nuestro modelo. Daremos una versión fuerte y una versión débil. Demostraremos la versión débil, pues basta para mucho de lo que queremos definir en los naturales (sumas, productos, potencias).

Las siguientes secciones son un poquito técnicas. Si las puedes seguir por completo, es fantástico. Pero incluso si no es así, basta con que en el fondo te quedes con la idea importante detrás: sí se vale definir de manera recursiva. Más adelante podrás regresar a este tema y entenderlo por completo.

Los teoremas de la recursión

Antes de la demostración principal de esta entrada, enunciaremos los teoremas que nos importan y hablaremos de manera intuitiva de lo que dicen. Hay dos versiones que veremos: una fuerte y una débil. Aunque parece que dicen cosas diferentes, en realidad son equivalentes. Será muy claro que la versión fuerte «implica» a la débil. Pero luego, en los problemas de tarea moral, se esbozará cómo ver que la versión débil se puede utilizar para demostrar la fuerte.

Teorema (Recursión Fuerte): Sea $X$ un conjunto y $x_{0}\in X$. Supongamos que tenemos varias funciones (una por cada natural $i$) $$\{f_{i}:X\to X\}_{i\in\mathbb{N}\setminus \{0\}.$$ Entonces existe una única función $g:\mathbb{N}\to X$ tal que:

  • $g(0)=x_{0}$
  • $g(\sigma(n))=f_{\sigma(n)}(g(n))$.

¿Qué es lo que quiere decir este teorema? Para responder esta pregunta veamos el siguiente diagrama:

Nuestro diagrama empieza en $0$, el cual queremos que sea mandado a algún $x_{0}\in X$, para la definición de los demás números, ocupamos la segunda característica que esperamos que $g$ satisfaga. Por ejemplo $g(1)=g(\sigma(0))=f_{1}(g(0))=f_{1}(x_{0})$. Este análisis coincide con lo que nos presenta el primer cuadro de flechas del diagrama anterior, que nos presenta los dos caminos que debe satisfacer $g$, para que sea la función que queremos. Como da lo mismo si «primero aplicamos $\sigma$ y luego $g$», a que si «primero aplicamos $g$ y luego $f_1$», decimos que el primer cuadrado del diagrama conmuta.

Análogamente, ya que conocemos la definición de $g(1)$ podemos fijarnos en el segundo cuadro, para poder definir $g(2)$ (de nuevo, conmuta) y seguir «recursivamente» para cualquier número natural.

Ejemplo: ¿Qué conjunto, y qué funciones necesitamos para definir el factorial?

Consideremos $X=\mathbb{N}$, definiremos intuitivamente (ya que aún no lo hemos definido formalmente), $f_{i}:\mathbb{N}\longrightarrow \mathbb{N}$, como $f_{i}(n)=i\cdot n$, es decir, el producto por $i$.

El teorema de Recursión Fuerte, nos dice que existe una única función $g$ tal que

  • $g(0)=1$
  • $g(\sigma(n))=f_{\sigma(n)}(g(n))=\sigma(n)\cdot g(n)$

Denotemos $n!:=g(n)$. Entonces tenemos que $\sigma(n)!=n!\cdot \sigma(n)$, justo como queremos.

$\square$

El teorema de Recursión Débil y su demostración

El teorema de Recursión Débil tiene un enunciado parecido al teorema de recursión fuerte y puede ser visto como una consecuencia directa del teorema anterior pues se obtiene de la versión fuerte tomando $f_{1}=f_{2}=\ldots=f_{n}=\ldots$

Teorema (Recursión Débil): Sea $X$ un conjunto y $x_{0}\in X$. Supongamos que tenemos una función $f:X\to X$. Entonces existe una única función $g:\mathbb{N}\to X$ tal que:

  • $g(0)=x_{0}$
  • $g(\sigma(n))=f(g(n))$.

Para concluir con esta entrada, probaremos el teorema de Recursión Débil. Antes de hacer esto introducimos un concepto auxiliar y una propiedad de los naturales.

Recordemos que como conjunto, $m=\{0,1,…,m-1\}$, lo que sugiere la siguiente definición.

Definición: Si $n,m\in \mathbb{N}$, decimos que $n<m$ si $n\in m$.

Puede probarse que esta relación en $\mathbb{N}$ es un orden total, y que sastisface la siguiente propiedad.

Teorema (Principio el Buen Orden): Sea $S\subset\mathbb{N}$ un conjunto no vacío, es decir $S\neq \emptyset$. Entonces $S$ tiene un elemento mínimo. Es decir, existe $n\in S$ tal que $n<m$ para todo $m\in S\setminus\{n\}$.

La prueba del Principio del Buen Orden y más propiedades de $<$ serán estudiadas con mayor detalle en entradas posteriores. Con esto en mente demostramos el teorema de Recursión Débil.

Demostración. Recordemos que por definición, toda función con dominio $A$ y codominio $B$, es un subconjunto de $A\times B$, por lo que una buena idea es analizar el conjunto $\wp(\mathbb{N}\times X)$, definamos

\[\Re:=\{R\in\wp(\mathbb{N}\times X)\mid (0,x_{0})\in R \text{ y si }(n,x)\in R\text{, entonces }(\sigma(n),f(x))\in R\}\]

Esta definición se ve terriblemente complicada. Pero la intuición es clara: $\Re$ tiene a todas las posibles colecciones de parejas de $\mathbb{N}\times X$ que cumplen lo que queremos. El problema es que muchas de ellas no son funciones y tenemos que «arreglar esto».

Probablemente, notarás alguna similitud entre el conjunto $\Re$ y el conjunto de los subconjuntos inductivos (que se menciona en La construcción de los naturales). Siguiendo esta analogía, definiremos $g:=\bigcap \Re$ (podemos hacer esta intersección ya que $\Re$ no es vacío pues $\mathbb{N}\times X$ está en $\Re$).

  • Demostremos que $g\in \Re$:

Por las propiedades de la intersección, tenemos que $g\subset\mathbb{N}\times X$, por lo que $g\in \wp(\mathbb{N}\times X)$. Veamos que $(0,x_{0})\in g$. Sea $R\in\Re$ arbitrario, entonces $(0,x_{0})\in R$, por lo que $(0,x_{0})\in\bigcap \Re=g$. Por último, si $(n,x)\in g$, demostremos que $(\sigma(n),f(x))\in g$, para esto, sea $R\in \Re$ arbitrario, como $(n,x)\in g$, entonces $(n,x)\in R$, por lo que $(\sigma(n),f(x))\in R$. Es decir, $(\sigma(n), f(x))\in\bigcap \Re=g$. Por todo lo anterior, $g\in\Re$.

  • Veamos ahora que $Dom(g)=\mathbb{N}$:

Usemos el quinto axioma de Peano, como $(0,x_{0})\in g$, entonces $0\in Dom(g)$. Supongamos ahora que $n\in Dom(g)$ y demostremos que $\sigma(n)\in Dom(g)$, por la hipótesis de inducción, existe $x\in X$ tal que $(n,x)\in g$, y como $g\in\Re$, tenemos que $(\sigma(n),f(x))\in g$, pero esto quiere decir que $\sigma(n)\in Dom(g)$. Entonces $Dom(g)$ es inductivo, entonces $Dom(g)=\mathbb{N}$.

  • Demostremos ahora que $g$ sí es función. Para esto, tenemos ver que «cada natural se va a un sólo elemento», en símbolos, si $(n,x),(n,y)\in g$ entonces $n=m$

Aquí es donde ocuparemos el Principio del Buen Orden. Consideremos $S:=\{n\in\mathbb{N}\mid (n,x),(n,y)\in g \text{ y } x\neq y \}$. Procedamos por contradicción, supongamos que $S\neq\emptyset$, entonces, $S$ tiene un elemento mínimo, denotémoslo por $n$.

Si $n=0$, entonces existe $x\in X$ tal que $(0,x)\in X$ y $x\neq x_{0}$. Entonces consideremos $g’=g\setminus\{(0,x)\}$. Notemos que $g’\in\Re$, ya que $(0,x_{0})\in g’$, ya que $(0,x_{0})\neq (0,x)$. Además si $(k,a)\in g’$, entonces $(k,a)\in g$, por lo que $(\sigma(k),f(a))\in g$, y como $0$ nunca es el sucesor de otro número, tenemos que $(\sigma(k),f(a))\neq(0,x)$, por lo tanto $(\sigma(k),f(a))\in g’$, es decir, $g’\in \Re$, lo que implica que $g=\bigcap \Re\subset g’=g\setminus\{(0,x)\}$ lo cual es absurdo, por lo que $n\neq 0$.

Como $n\neq 0$, debemos tener que existe $m$ tal que $\sigma(m)=n$ ¿Por qué?. Y como $n$ es el mínimo en $S$, tenemos que $m\not\in S$, es decir, existe un único $x\in X$ tal que $(m,x)\in g$, esto implica que $(\sigma(m),f(x))=(n,f(x))\in g$, y como $n\in S$, debe existir $y\in X$, $y\neq f(x)$ tal que $(n,y)\in g$. Análogamente a como lo hicimos antes, consideremos $g’=g\setminus (n,y)$ y veamos que $g’\in \Re$. Como $(n,y)\neq(0,x_{0})$, tenemos que $(0,x_{0})\in g’$. Más aún, si $(k,a)\in g’$, demostremos que $(\sigma(k),f(a))\in g’$, para esto supongamos que no.

Como $(k,a)\in g’$, tenemos que $(k,a)\in g$, por lo que $(\sigma(k),f(a))\in g$, esto implica que $(\sigma(k),f(a))=(n,y)$ ya que este es el único elemento de $g$ que no está en $g’$. Como $\sigma(k)=n=\sigma(m)$, concluimos, por la inyectividad de $\sigma$, que $k=m$. Esto quiere decir que $(k,a)=(m,a)\in g$, pero recordando que $x$ es el único elemento relacionado con $m$, concluimos que $x=a$, en síntesis, $(k,a)=(m,x)$, por lo que $(\sigma(k),f(a))=(\sigma(m),f(x))=(n,f(x))\neq(n,y)$. Esto implica que $(\sigma(k), f(a))\in g’$, contradiciendo nuestra suposición de que no lo estaba.

Entonces hemos probado que $(0,x_{0})\in g’$ y que cada vez que $(k,a)\in g’$, también lo está $(\sigma(k), f(a))$. Esto quiere decir que $g’\in\Re$, y como lo hicimos anteriormente, tendremos que $g=\bigcap \Re\subset g’=g\setminus\{(n,y)\}$, lo cual es una contradicción. Esto quiere decir, que suponer que $S$ tiene un elemento mínimo, es absurdo, por lo que $S=\emptyset$. Lo que traducido quiere decir que para todo $n\in\mathbb{N}$, existe un único $x\in X$ tal que $(n,x)\in g$. Es decir, que $g$ sí es una función.

  • Demostremos que $g$ satisface las dos propiedades del Teorema.

Ya vimos que $g\in \Re$, por lo que $g(0)=x_{0}$. Sea ahora $n\in \mathbb{N}$ y $x=g(n)$, de nuevo, como $g\in\Re$, tenemos que $g(\sigma(n))=f(x)=f(g(n))$.

  • Por último, demostremos la unicidad de $g$

Si $h:\mathbb{N}\longrightarrow X$ es otra función que satisface las características del Teorema, consideremos $A=\{n\in\mathbb{N}\mid h(n)=g(n)\}$, como $h(0)=x_{0}=g(0)$. Tenemos que $0\in A$. Supongamos que $n\in A$. Tendríamos entonces que $h(\sigma(n))=f(h(n))=f(g(n))=g(\sigma(n))$, es decir que $\sigma(n)\in\A$, por lo que $A$ es inductivo, y por consiguiente, $A=\mathbb{N}$. En resumen, $h$ y $g$, coinciden en dominio, codominio y regla de correspondencia, entonces $h=g$, como debíamos probar.

$\square$

La demostración del teorema de Recursión Fuerte requiere de algunos detalles adicionales, pero puede deducirse del teorema de Recursión Débil. Dejamos esto como uno de los problemas de la tarea moral.

Tarea Moral

Los siguientes ejercicios y problemas te ayudarán a reforzar lo aprendido en esta entrada.

  1. Demuestra el 5° Axioma de Peano a partir del Principio de Inducción
  2. Demuestra que si $n\neq 0$ entonces existe $m$ tal que $\sigma(m)=n$.
  3. ¿Qué función $g$, satisface que $g(0)=1$ y $g(\sigma(n))=2\cdot g(n)$? ¿Qué función $f$ estamos ocupando?
  4. ¿Qué conjunto y que función nos permitiría definir la sucesión de Fibonacci $a_{n+2}=a_{n+1}+a_{n}$ usando el Teorema de Recursión?
  5. Demuestra el Teorema de Recursión Fuerte, usando el Débil. Sugerencia: Considera, $F(n,x):\mathbb{N}\times X\longrightarrow \mathbb{N}\times X$, como $F(n,x)=(\sigma(n),f_{\sigma(n)}(x))$

Más adelante…

El teorema de Recursión será la mayor herramienta que tendremos para poder darle una forma más familiar a los números naturales, ya que las operaciones de suma y multiplicación, que veremos en la siguiente entrada, tendrán una definición recursiva.

Y así como el teorema de la Recursión nos permitirá definir, usaremos continuamente el principio de Inducción para poder demostrar las numerosas propiedades que estas operaciones tienen.

Entradas Relacionadas