Introducción
Como lo dijimos en la entrada anterior buscamos la manera de definir a la suma en el conjunto de los naturales y esto nos lo permitirá el teorema de recursión. En esta nueva entrada presentaremos la definición formal de la suma y demostraremos algunas de las propiedades que satisface.
Suma
Definición: Dado $n\in \mathbb{N}$ fijo pero arbitrario y $g:\mathbb{N}\to \mathbb{N}$ dada por $g(m)=s(m)$ para cualquier $m\in \mathbb{N}$, existe una única función (esto lo podemos asegurar por el teorema de recursión) tal que $f_n(0)=n$ y $f_n(s(k))=g(f_n(k))=s(f_n(k))$ para cualquier $k\in \mathbb{N}$.
Está definición nos dice como sumar a un número natural con un $n$ fijo, por lo que requerimos definir una operación binaria que nos diga como sumar a dos números naturales cualesquiera.
Definición: Sea $g:\mathbb{N}\to \mathbb{N}$ dada por $g(m)=s(m)$ para cualquier $m\in \mathbb{N}$. Definimos a la suma de los naturales como la función $+: \mathbb{N}\times \mathbb{N}\to \mathbb{N}$ tal que $+(m,n)=m+n=f_n(m)$ para cualesquiera $n,m\in \mathbb{N}$.
La función $+$ satisface las siguientes condiciones:
- $0+n=n$ para cualquier $n\in \mathbb{N}$,
- $s(m)+n=s(m+n)$ para cualesquiera $m,n\in \mathbb{N}$.
Esto último se sigue de que $+(m,n)=f_n(m)$ y $f_n$ satisface tales condiciones.
Teorema: La función $+$ es única.
Demostración:
Sea $+$ la función que definimos arriba y supongamos que existe $h:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ que satisface $h(0,n)=n$ y $h(s(m), n)= s(h(m,n))$. Veamos que $+=h$.
Definamos para cada $n\in\mathbb{N}$ la función $h_n:\mathbb{N}\to\mathbb{N}$ por medio de $h_n(0)=h(0,n)$ y $h_n(m)=h(m,n)$. Notemos que para todo $n\in\mathbb{N}$, $h_n(0)=n$ y $h_n(s(m))=h(s(m),n)=s(h(m,n))=s(h_{n}(m))$, y por el teorema de recursión se sigue que $h_n=f_n$.
Así, para $n,m\in\mathbb{N}$ arbitrarios, $+(m,n)=f_n(m)=h_n(m)=h(m,n)$ y en consecuencia, $+=h$.
$\square$
Dado que seguimos trabajando con conjuntos y hemos definido una nueva operación binaria, podemos preguntarnos si esta operación conmuta, es asociativa o si cumple alguna otra propiedad tal como lo hace el producto cartesiano. Notaremos que para demostrar estas propiedades ocuparemos en todo momento el principio de inducción.
Asociatividad de la suma
Teorema: Para cualesquier $m,n,k\in \mathbb{N}$, $m+(n+k)=(m+n)+k$.
Demostración: Procederemos por inducción sobre $m$ y dejaremos fijos a $n$ y $k$.
Base de inducción: Si $m=0$, $0+(n+k)=n+k=(0+n)+k$.
Hipótesis de inducción: Supongamos que se cumple para $m$, es decir, $m+(n+k)= (m+n)+k$.
Paso inductivo: Veamos que se cumple para $s(m)$, es decir, $s(m)+(n+k)=(s(m)+n)+k$.
\begin{align*}
s(m)+(n+k)&=s(m+(n+k)) \tag{Definición $+$}\\
&= s((m+n)+k) \tag{Hipótesis de inducción}\\
&= s(m+n)+k\tag{Definición $+$}\\
&= (s(m)+n)+k\tag{Definición $+$}.
\end{align*}
Por lo tanto, $+$ es asociativa.
$\square$
Conmutatividad de la suma
Ahora vamos a ver que la suma conmuta, para ello demostraremos los siguientes lemas:
Lema 1: Para cualquier $m\in \mathbb{N}$, $0+m=m+0$.
Demostración:
Procederemos por inducción sobre $n$.
Base de inducción: Si $m=0$, tenemos que $0+0=0+0$.
Hipótesis de inducción: Supongamos que para algún $k\in \mathbb{N}$ se satisface que $0+k=k+0$.
Paso de inductivo: Veamos que se cumple para $s(k)$, es decir, $0+s(k)=s(k)+0$.
\begin{align*}
s(k)+0 &=s(k+0)\tag{Definición $+$}\\
&= s(0+k)\tag{Hipótesis de inducción}\\
&= s(k)\tag{Definición $+$}\\
&= 0+s(k)\tag{Definición $+$}.
\end{align*}
Por lo tanto, $0+m=m+0$, para cualquier $m\in \mathbb{N}$.
$\square$
Lema 2: Para cualesquiera $m,n\in \mathbb{N}$, $s(n)+m=n+s(m)$.
Demostración:
Procederemos por inducción sobre $m$.
Base de inducción: Si $n=0$, tenemos que $s(0)+m=s(0+m)= s(m)=0+s(m)$.
Hipótesis de inducción: Supongamos que para algún $k\in \mathbb{N}$ se satisface que $s(k)+m=k+s(m)$.
Paso de inductivo: Veamos que se cumple para $s(k)$, es decir, $s(s(k))+m=s(k)+s(m)$.
\begin{align*}
s(s(k))+m &=s(s(k)+m) \tag{Definición $+$}\\
&= s(k+s(m)) \tag{Hipótesis de Inducción}\\
&= s(k)+s(m) \tag{Definición $+$}.
\end{align*}
Por lo tanto, para cualesquiera $m,n\in \mathbb{N}$, $s(n)+m=n+s(m)$.
$\square$
Proposición: Para cualesquiera $m,n\in \mathbb{N}$, $n+m=m+n$.
Demostración:
Por inducción sobre $m$.
Base de inducción: Si $m=0$, entonces $n+0=0+n$. (Lo probamos por inducción en el primer lema 1).
Hipótesis de inducción: Supongamos que para $k$ se cumple que $n+k=k+n$.
Paso inductivo: Veamos que para $s(k)$ se satisface que $n+s(k)= s(k)+n$.
\begin{align*}
s(k)+n&= s(k+n)\tag{Definición $+$}\\
&= s(n+k)\tag{Hipótesis de Inducción}\\
&= s(n)+k\tag{Definición $+$}\\
&= n+s(k)\tag{Lema 2}.
\end{align*}
Por lo tanto, $+$ es conmutativa.
$\square$
Ley de cancelación
En álgebra, cuando tenemos una ecuación como la siguiente:
$x+5=y+5$,
dado que $5=5$, entonces ponemos $x=y$, esto tiene una justificación y la llamaremos ley de cancelación de la suma. El teorema dice lo siguiente:
Teorema: Si $n+k=m+k$, entonces $n=m$.
Demostración:
Demostraremos que si $n\not=m$, entonces $n+k\not=m+k$. Procederemos por inducción sobre $k$.
Base de inducción: Supongamos que $n\not=m$. Luego, $n+0=0+n=n$ y $m+0=0+m=m$ y así, $n+0=n\not=m=m+0$.
Hipótesis de inducción: Supongamos que para algún $k\in \mathbb{N}$, se satisface que si $n\not=m$, entonces $n+k\not=m+k$.
Paso inductivo: Veamos que se cumple para $s(k)$, es decir, si $n\not=m$, entonces $n+s(k)\not=m+s(k)$.
Supongamos que $n\not=m$. Luego,
\begin{align*}
n+s(k)&= s(n)+k\tag{Lema 2}\\
&= s(n+k)\tag{Definición $+$}\\
&\not= s(m+k)\tag{Hipótesis de inducción}\\
&= s(m)+k\tag{Definición $+$}\\
&= m+s(k)\tag{Lema 2}.
\end{align*}
Por lo tanto, se cumple la ley de cancelación para la suma.
$\square$
A continuación probaremos un resultado que podría parecer natural para todos, $s(m)=m+1$ para cualquier $m\in \mathbb{N}$.
Teorema: Para cualquier $m\in \mathbb{N}$, $s(m)=m+1$.
Demostración:
Procederemos por inducción sobre $m$.
Base de inducción: Si $m=0$, entonces $s(0)=1=0+1$.
Hipótesis de inducción: Supongamos que para $k\in \mathbb{N}$ se cumple que $s(k)=k+1$.
Paso inductivo: Veamos que la propiedad se satisface para $s(k)$, es decir, $s(s(k))= s(k)+1$.
\begin{align*}
s(k)+1&= s(k+1)\tag{Definición $+$}\\
&= s(s(k))\tag{Hipótesis de inducción}.
\end{align*}
Por lo tanto, $s(m)=m+1$ para cualquier $m\in \mathbb{N}$.
$\square$
A partir de este momento usaremos el hecho de que $s(m)=m+1$.
Tarea moral
La siguiente lista de ejercicios te permitirá reforzar el contenido de esta sección:
- Demuestra que si $n,m\in \mathbb{N}$ tales que $n\not=m$, entonces $s(n)\not= s(m)$.
- Demuestra usando el principio de inducción que para cualesquiera $m, n \in \mathbb{N}$, $m + n \geq n$.
- Prueba que para cualesquiera $m,n\in \mathbb{N}$ tales que $m+n=0$, entonces $m=0$ y $n=0$.
Más adelante…
En la siguiente entrada definiremos al producto en el conjunto de los números naturales.
Enlaces
Entrada anterior: Teoría de los Conjuntos I: Teorema de recursión
Siguiente entrada: Teoría de los Conjuntos I: Producto en los naturales