Archivo de la etiqueta: numeros naturales

Álgebra Superior I: Principio de recursión en los números naturales

Introducción

En esta entrada revisaremos el concepto de recursión en un sentido matemático y revisaremos algunos ejemplos. Probablemente ya hayas escuchado el término, pues verás que es una herramienta útil para definir funciones en términos de las evaluaciones pasadas.

La suma de los primeros n números naturales

Carl Friedrich Gauss fue un matemático alemán del siglo XVIII el cual es uno de los más importantes en distintas disciplinas matemáticas como la teoría de números, la geometría y estadística. Sus aportes son varios en estas y más áreas por lo que nos tomaría varios años de estudio para llegar a muchos de sus resultados. En esta ocasión veremos uno de sus razonamientos más famosos el cual muchos le atribuyen cuando este solo estaba en el colegio cuando aún era niño.

Se dice que el profesor de su clase de matemáticas había castigado a todo el salón haciéndoles sumar los números naturales del $1$ al $100$. La historia dice que no pasó mucho tiempo (y mucho menos del esperado por el profesor) hasta que Gauss llegó con la respuesta «5050». El razonamiento que tuvo fue el siguiente: Para llegar a la suma, pondremos los números del $1$ al $100$ en una lista, y debajo los mismos números pero al revés, es decir, del $100$ al $1$, y notemos que sumando uno a uno los números de las dos listas como los hemos acomodado, queda un mismo número:

$$\begin{array}{cccccc}
&1 & 2 & \dots &99 & 100 \\
+&100 & 99 & \dots &2 & 1 \\
=&101 & 101 & \dots &101 & 101\\
\end{array}$$

De manera que si tenemos los primeros $100$ números, entonces el número resultante de la suma es $101$, de manera que si sumamos estos números, estaríamos sumando $100$ veces el número $101$, pero como hemos sumado dos veces la lista, entonces deberemos dividir entre $2$ para obtener la suma real. Dicho de otra forma: $$ \sum_{i=0}^{100} i = \frac{100(100+1)}{2} .$$
Si recuerdas, esta es la fórmula que probamos en la entrada pasada, pues en el caso general: $$ \sum_{i=0}^{n} i = \frac{n(n+1)}{2} $$

Viendo la suma como recursión

Sigamos pensando en el ejemplo. Para cada $n \in \mathbb{N}$, llamemos $$S_n = \sum_{i=0}^{n} i = \frac{n(n+1)}{2} .$$ Y nota que para cada número natural $n$ se cumple que:

  1. $S_0=0$
  2. Si $n>0$ entonces $S_n = S_{n-1}+n$

Nota ahora que podemos definir a $S_n$ únicamente en términos de la suma de su antecesor con el número. Esto quiere decir que si nos pidieran calcular $S_{51},S_{52},S_{53}$, primero podemos calcular $S_{51}$ sumando todos los números del $0$ al $51$, pero una vez tengamos ese resultado, no es necesario volver a sumar todos los números para $S_{52}$, sino que basta saber quién es $S_{51}$ y sumarle $52$ para obtener el término deseado, lo mismo para el siguiente número de la sucesión $S_{53}=S_{52}+53$. A $S$ se le puede ver como una función $S:\mathbb{N} \rightarrow \mathbb{N} $ donde $S_n$ hace referencia a la función $S$ valuada en $n$, esto quiere decir que $S(n)=S_n$. A esta función se le llamará una función recursiva.

Definición. Una función $\phi: \mathbb{N} \rightarrow \mathbb{N} $ se dice tener la propiedad de recursión si existe $a \in \mathbb{N} $ y una función $f : \mathbb{N} \rightarrow \mathbb{N} $ tal que:

  1. $\phi(0)=a$
  2. Si $n>0$ entonces $\phi(\sigma(n)) = f(\phi(n))$

Veamos esta definición por partes. Retomemos nuestro ejemplo de la suma de los primeros números naturales. La función que es recursiva es $\phi$, esta función debe satisfacer dos condiciones. La primera condición es que se defina a dónde «manda» el $0$, es decir, hace falta saber cómo empezar la definición recursiva, en este caso, se trata de cómo definimos el comportamiento de la función en el primer número del conjunto de los números naturales. La segunda condición se pone más interesante, pues lo que nos dice es que existe una función $f$ tal que la función $\phi$ evaluada en el sucesor de $n$ ($\sigma(n)=n+1$) es la función $f$ valuada en $\phi (n)$. Lo que quiere decir esta oración es que «Si quieres saber quién es $\phi(n+1)$ y ya sabes quién es $\phi (n)$, entonces basta hacerle algo a ese resultado (valuar ese resultado en $f$) para obtener lo querido».

En nuestro ejemplo de la función $S$ (en la definición, esta sería la función $\phi$), la función $f$ es aquella que a cada suma parcial le agrega el número correspondiente. Esto quiere decir que $f$ es la función: $$\begin{align*} f(S(n)) &= S(n)+n \\&= S(n+1)=S(\sigma(n))\end{align*}.$$

Teorema de recursión débil

El siguiente teorema nos garantiza no solo la existencia de funciones recursivas, sino que además nos garantiza que esta es una herramienta para conjuntos distintos al de los números naturales:

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 $\phi:\mathbb{N}\to X$ tal que:

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

La demostración de este teorema se verá en el curso de Álgebra Superior II. Y a grandes rasgos nos garantiza el hecho de que las definiciones de las funciones por recursión son matemáticamente válidas. En otras palabras, muestra que somos capaces de definir y usar funciones recursivas.

Algunos ejemplos

Veamos otro ejemplo de este tipo de funciones. Sea $n \in \mathbb{N}$ Definamos $$ n! = n*(n-1)*(n-2)*\dots*2*1.$$ Por ejemplo, $3!=3*2*1=6$. Nota que esta es una función que podemos describir como recursiva al establecer las siguientes condiciones:

  1. $0!=1$
  2. $n!=(n-1)!*n.$

Como veremos en siguientes entradas, esta función llamada factorial se utilizará mucho en conteo y combinatoria, pues nos hablará de el número de formas de combinar un conjunto con algún número de elementos.

El siguiente ejemplo requiere de una pequeña definición:

Definición. Sea $a$ una función. La función $a$ es una sucesión si $a : \mathbb{N} \rightarrow \mathbb{N} $ es una función entre números naturales.

Esta definición nos indica que a las funciones entre números naturales también se les conoce como sucesiones, muchas veces este no será el nombre común al que se refieran a las funciones de $ \mathbb{N} $ en $ \mathbb{N} $ pero si en alguna ocasión ves el término, sabrás a qué se refiere. También es común, al estar hablando de sucesiones, de escribir las evaluaciones de $a$ en cada término $n$ simplemente como $a_n$ es decir $a_n=a(n)$.

Supongamos ahora que tenemos la sucesión definida como $$a_n=5n+2$$. Los cinco primeros términos de esta sucesión son:$$a_0=2$$ $$a_1=7$$ $$a_2=12$$ $$a_3=17$$ $$a_4=22$$ Notemos que podemos escribir esto de forma recursiva, para ello, notemos que únicamente en cada paso estamos sumando un 5, de manera que $$a_{n+1}=a_n+5.$$Adicionalmente, ya sabemos cuánto vale en el $0$, así la siguiente proposición demuestra este hecho:

Proposición $a_n$ puede definirse de forma recursiva como:

  1. $a_0=2$
  2. $a_{n+1}=a_n+5.$

Demostración (por inducción)

Base inductiva. Es claro que $$a_0 = 2 = 0*5+2$$ De manera que se cumple la base de inducción.

Hipótesis inductiva. Supongamos que para $n\geq 0$ se cumple que $$a_n = a_{n-1}+5=5n+2.$$

Paso inductivo. Para demostrar que $$a_{n+1}=a_n+5$$ como dice la proposición, notemos que por definición de la sucesión, $$a_{n+1}=5(n+1)+2=5n+2+5.$$
Ahora, por hipótesis de inducción, $$a_n=5n+2.$$De esta forma, $$a_{n+1}=5(n+1)+2)+5=a_n+5. $$ tal como se quería demostrar.

$\square$

Tarea Moral

  1. Muestra que hay una única función $\phi$ entre número naturales tal que:
    1. $\phi(0)=10$
    2. $\phi(\sigma(n))=2\phi(n)$
  2. Da una definición explícita de la función del inciso anterior.
  3. Da una definición recursiva para las siguientes sucesiones:
    • $a_n=2n$
    • $a_n=2n+1$
    • $a_n=2^n$
    • $a_n=0$

Más adelante…

En esta entrada dimos la idea de lo que significa la recursión en las matemáticas, en la siguiente entrada usaremos esta idea para empezar a definir las operaciones básicas en los números naturales: la suma y el producto.

Entradas relacionadas

  • Ir a Álgebra Superior I
  • Entrada anterior del curso: Problemas de inducción
  • Siguiente entrada del curso: Suma y producto de naturales y sus propiedades

Álgebra Superior I: Introducción a números naturales

Introducción

Hasta ahora hemos hablado de conceptos introductorios de conjuntos, lógica, funciones y relaciones. Ahora empezaremos a ver más aplicaciones de estos fundamentos matemáticos, y en esta unidad empezaremos a hablar de un concepto que muchos de nosotros usamos todos los días y uno de los conceptos clave que históricamente es la base del estudio matemático en muchas culturas: los números naturales.

Empezando a contar

Vamos a pensar en los números que nosotros usamos para contar, cuando estamos pagando algún objeto, pensamos en unidades de dinero, un objeto $x$ puede costar $10$ monedas, en una tienda, puede haber $5$ camisas, $2$ pantalones y como se agotaron los zapatos, podemos decir que hay $0$ zapatos.

A estos números que usamos para contar, les llamaremos «números naturales», el término de natural viene del hecho que es un concepto que se viene de forma intuitiva, o a que surgen naturalmente a raíz de las necesidades de las distintas culturas que han existido a lo largo de la historia. Esta idea de pensar a los números naturales es buena para tener una intuición de cómo funcionan, sin embargo vamos a abstraer un poco la idea de lo que significa un número en esta y las siguientes entradas, desde su definición hasta la forma en que se suman y se multiplican, por ejemplo.

Los axiomas de Peano

Giuseppe Peano fue un matemático del siglo XIX que llegó a formalizar el término de «número natural», explicando algunas reglas que cumplían los números naturales, antes de ver cómo se construyen estos, veamos cuáles son estas reglas o axiomas que estableció Peano.

Para Peano, los números naturales son un conjunto al que denominaremos por $\mathbb{N}$ junto con una relación $\sigma \in \mathbb{N} \times \mathbb{N} $, es decir considera a una pareja de términos $( \mathbb{N} , \sigma)$ que cumplirán los siguientes axiomas:

Axioma 1. Existe un elemento especial en $ \mathbb{N} $ que denominaremos por $0$.

Axioma 2. Para cada elemento $m \in \mathbb{N} $ existirá un único elemento $n \in \mathbb{N} $ tal que $(m,n) \in \sigma$, es decir $\sigma$ es una función.

Axioma 3. Para todo número natural $n$, sucede que $\sigma(n) \neq 0$.

Axioma 4. $\sigma$ es una función inyectiva.

Axioma 5 (Primer principio de inducción). Si $S$ es un subconjunto de $ \mathbb{N} $ tal que:

  1. $0 \in \mathbb{N}$
  2. Para cada número $n \in S$, sucede que $\sigma(n) \in S$

Entonces $S=\mathbb{N}$

Normalmente a la función $\sigma$ se le conoce como la función sucesora. Pensemos en esto con la intuición que tenemos sobre el sucesor de un número. Primero notemos que podemos resumir los primeros cuatro axiomas diciendo que $\sigma$ es una función biyectiva $\sigma: \mathbb{N} \rightarrow \mathbb{N} \setminus \{0\}$. Para ver eso, consideremos la siguiente proposición:

Proposición. $Im(\sigma)=\mathbb{N}\setminus \{0\}$.

Demostración. Para esta demostración, solo basta probar que $Im(\sigma) \supset \mathbb{N}\setminus \{0\}$. Ahora supongamos que $n \in Im(\sigma)$, entonces como $n \in \mathbb{N}$ sucede que $\sigma(n) \in Im(\sigma)$. Como $\mathbb{N}$ satisface los axiomas de Peano y el conjunto $Im(\sigma) \cup \{0\}$ satisface las condiciones del axioma 5, entonces $Im(\sigma) = \mathbb{N}$. De tal manera que $(Im(\sigma) \cup \{0\}) \setminus \{0\} = \mathbb{N} \setminus \{0\}$, esto debido a que $0$ no es sucesor de ningún número.

$\square$

Construcción de los números naturales

Normalmente llamamos a este conjunto de los números naturales al conjunto $\{0,1,2,3,\dots\}$ y la función sucesora es la función: $$\begin{align*}1&\xrightarrow{\sigma}2\\ 2&\xrightarrow{\sigma}3\\ 3&\xrightarrow{\sigma}4 \\&\vdots\end{align*}$$ Es decir, es la función que a cada número lo manda a su sucesor. Esta forma de pensar a los números es la habitual, y de hecho cualquier sistema numérico que satisfaga los axiomas, será equivalente a los números naturales, es decir que existe un único sistema numérico que cumpla los axiomas de Peano salvo isomorfismos. No te preocupes si no entiendes este término aún, solo es otra forma de decir que podemos pensar a los números naturales como cualquier conjunto que cumpla los axiomas.

A continuación vamos a presentar una forma conjuntista de construir a los números naturales. Para ello, nos olvidaremos un rato de los axiomas de Peano y daremos algunas definiciones.

Definición. Sea $S$ un conjunto, entonces el sucesor $\sigma(S)$ de $S$ es el conjunto $$\sigma(S)= S \cup \{S\} $$.

Por ejemplo:

  1. $\sigma(\emptyset) = \{\emptyset\}$
  2. $\sigma(\{\emptyset\}) = \sigma(\sigma(\emptyset))=\{\emptyset\} \cup \{\{\emptyset\}\}$.

Definición. Un conjunto $X$ es inductivo si:

  1. $\emptyset \in X$
  2. $x \in X \Rightarrow \sigma(x) \in X.$

Ahora definamos al conjunto $\mathbb{N}$ como el conjunto formado por $\emptyset$ y los elementos resultantes de la aplicación iterativa de la función sucesora, es decir: $$ \mathbb{N} = \{\emptyset, \sigma(\emptyset),\sigma(\sigma(\emptyset)),\sigma(\sigma(\sigma(\emptyset))),\dots \}$$ Por construcción, este es un conjunto inductivo.

Con esto en mente, podemos entonces pensar a estos números naturales como a los conjuntos $$\begin{align*}&\emptyset\\
&\{\emptyset\} \\
&\{ \emptyset \} \cup \{\{ \emptyset \}\} = \{\emptyset,\{\emptyset\}\}\\
&\{ \emptyset \} \cup \{\{ \emptyset \}\} \cup \{ \{ \emptyset \} \cup \{\{ \emptyset \}\} \}= \{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\} \\ &\dots \end{align*}$$

Uniendo con los axiomas de Peano

Ahora veremos que de hecho estos conjuntos cumplen los axiomas de Peano.

Teorema. $\mathbb{N}$ cumple los axiomas de Peano.

Demostración. Recordemos que primero deberíamos demostrar que $\sigma: \mathbb{N} \rightarrow \mathbb{N} \setminus \emptyset$ es una función biyectiva. Para ello, notemos que es inyectiva, para probar esto, supongamos que $n,m \in \mathbb{N}$ tales que $\sigma(n)=\sigma(m)$. Como $n \in \sigma(n)$ entonces $n \in \sigma(m)$. Esto significa que $n \in m \lor n=m$. De la misma manera $m \in m \lor n=m$. De manera que al cumplirse las dos condiciones al mismo tiempo sucede que $(n \in m \land m \in n) \lor m=n$. La primera condición resulta en una contradicción de la teoría de conjuntos que no revisaremos en este curso1.
Además. $\sigma$ también es suprayectiva, pues recordemos que por construcción, cada elemento de $\mathbb{N}\setminus(\emptyset)$ es de la forma $\sigma(n)$. Así que si consideramos cualquier elemento $m \in \mathbb{N}\setminus(\emptyset) $ existirá $n \in \mathbb{N}$ tal que $\sigma(n)=m$. De esta forma, la función es biyectiva.

Ahora, para ver que se cumple el quinto axioma, recordemos que $ \mathbb{N}$ es un conjunto inductivo. Ahora, veamos que si $\emptyset$ es nuestro elemento como en el axioma 1, se cumple del primer al cuarto axioma. Además, se cumplirá el quinto axioma, pues el $0$ de este conjunto es $\emptyset$. Así, el conjunto satisface los axiomas de Peano.

$\square$

Para usar la notación normal de los números naturales, vamos a escribir la numeración normal que conocemos:
$$\begin{align*}
&0 \rightarrow\emptyset\\
&1 \rightarrow \{\emptyset\} \\
&2 \rightarrow \{\emptyset,\{\emptyset\}\}\\
&3 \rightarrow \{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\} \\ &\dots \end{align*}$$

Notas

  1. En particular la contradicción de la demostración es con un axioma que se llama el axioma de regularidad, este axioma se revisa en cursos específicos de Teoría de Conjuntos o en cursos de Lógica y Conjuntos

Tarea moral

  1. ¿Cuál es el sucesor del conjunto $\{1,\{2,3\}\}$?
  2. Demuestra que para cada conjunto $S$, $\sigma(S)$ tiene al menos un elemento.
  3. Demuestra que para cualquier conjunto $X$, $|X|=n$ si y solo si existe una biyección entre $X$ y $n$.

Más adelante…

El quinto axioma de Peano que también se le conoce como primer principio de inducción como está definido es muy útil para pensar algunas cosas de las matemáticas que tienen que ver con números naturales. Es incluso tan importante este axioma que existe un tipo de demostración matemática que no hemos revisado y será el uso de este axioma para las «demostraciones por inducción»

Entradas relacionadas

  • Ir a Álgebra Superior I
  • Entrada anterior del curso: Problemas de cardinalidad de conjuntos finitos
  • Siguiente entrada del curso: Principio de inducción en los números naturales