Archivo de la etiqueta: naturales

Álgebra Superior II: Otras definiciones recursivas en los naturales (exponenciación y factorial)

[latexpage]

Introducción

En las entradas pasadas hemos dado la definición recursiva de la suma y del producto usando el teorema de la recursión débil y probamos las propiedades elementales de estas operaciones usando el principio de inducción.

Continuando con esta línea de pensamiento, en esta entrada definiremos las funciones exponenciales usando las funciones producto; sin embargo, para definir estas funciones, también ocuparemos el teorema de recursión débil. Para ver que no enunciamos en vano la versión fuerte de este teorema, daremos como aplicación la definición de la función factorial, y de la misma forma a como lo hicimos antes, probaremos algunas de sus propiedades haciendo uso del principio de Inducción. Sin embargo, dejaremos algunas de las propiedades como ejercicio para que puedas practicar este tipo de pruebas una vez más.

Exponenciación en los naturales

Desde la educación elemental nos enseñan que «multiplicar es sumar repetidas veces» y que «exponenciar es multiplicar repetidas veces». Formalicemos esta intuición mediante el teorema de recursión.

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

  1. $\eta_{m}(0)=1$
  2. $\eta_m(\sigma(n))=p_{m}(\eta_{m}(n)) $

Así como lo hemos hecho con la definición de producto y de suma, introduciremos la «notación usual» para hablar de esta función. En este caso, definimos $m^n:=\eta_m(n)$.

De este modo, en términos de las notaciones usuales, podemos suplir la propiedad (2) de la definición anterior como $m^{n+1}=m\cdot m^n$.

Las potencias de $0$ y de $1$

Así como lo hicimos con la suma y el producto, analizaremos de forma especial a las funciones $\eta_{0}$ y $\eta_{1}$.

Teorema: Tenemos que $\eta_{0}(0)=1$ y si $n\neq 0$, entonces $\eta_{0}(n)=0$.

La demostración queda como un ejercicio moral. La buena noticia es que hemos trabajado lo suficiente como para no tener que realizar una prueba por inducción. Cuando intentes demostrar esto por tu cuenta, recuerda qué sucede cuando multiplicamos por $0$.

Notemos que así como lo definimos, $0^0$ es $1$ en los números naturales. Sin embargo, como veremos más adelante y como posiblemente lo sabrás ya, la expresión $0^0$ no estará definida en otros sistemas numéricos como los números reales. Al igual que «$0$ es un natural», la definición de $0^0$ frecuentemente varía dependiendo del contexto.

Teorema: Tenemos que $\eta_{1}(n) =1$ para todo $n$ en los naturales.

Demostración. Para este resultado sí procederemos por inducción sobre $n$. Por la parte (1) de la definición de $\eta_{1}$, tenemos que $\eta_{1}(0)=1$. Esta es nuestra base de inducción.

Supongamos que $\eta_{1}(n)=1$. Queda demostrar que $\eta_{1}(\sigma(n))=1.$ Sin embargo esto se sigue ya que por definición, $\eta_{1}(\sigma(n))=1\cdot\eta_{1}(n)=1\cdot 1=1$. Te invitamos a identificar los argumentos que se ocuparon en cada paso

$\square$

La exponencial no conmuta ni asocia

Como la notación que ocupamos para las funciones $\eta_{m}$ no es tan simétrica como la que ocupamos para el producto o para la suma, uno puede esperar que esta operación no sea en general conmutativa. En efecto esto es cierto, solo basta notar que

$0^1\neq1^0$

Así mismo la exponenciación no es en general asociativa, es decir que existen casos en que

$(n^m)^l\neq n^{(m^l)}$

Encontrar un contraejemplo queda como un ejercicio moral.

Le exponenciación y otras operaciones.

Cuando estudiamos el producto de números naturales, vimos que esta operación se distribuye sobre la suma, entonces una buena pregunta es preguntarnos qué pasa cuando mezclamos la exponenciación con el producto y la suma. Quedará como ejercicio dar contraejemplos a todas las siguientes proposiciones:

  1. $n^{(l\cdot m)}=n^l\cdot n^l$
  2. $(l+m)^n=l^n+m^n$
  3. $n^{l+m}=n^l+n^m$

Sin embargo, probaremos dos teoremas conocidos usualmente como las leyes de los exponentes. El primero de ellos dice que por la izquierda, la exponenciación sí se distribuye sobre el producto.

Teorema: Si $a,b,n\in\mathbb{N}$, entonces $(a\cdot b)^n=a^n\cdot b^n$.

Demostración. Procedamos por inducción sobre $n$. De la definición de exponencial, tenemos que $(a\cdot b)^0=1=1\cdot 1= a^0\cdot b^0$, por lo que la base de inducción es cierta.

Supongamos que para algún $n$ se tiene que $(a\cdot b)^n=a^n\cdot b^n$ y probemos que $(a\cdot b)^{\sigma(n)}=a^{\sigma(n)}\cdot b^{\sigma(n)}$. Esto es cierto ya que

\begin{align*}
(a\cdot b)^{\sigma(n)}&=(a\cdot b)\cdot (a\cdot b)^n\\
&=(a\cdot b)\cdot (a^n\cdot b^n)\\
&=(a\cdot a^n)\cdot (b\cdot b^n)\\
&=a^{\sigma(n)}\cdot b^{\sigma(n)}
\end{align*}

A diferencia de las entradas anteriores ya ocupamos sin mención las propiedades ya demostradas o la hipótesis de inducción; sin embargo, sería bueno que detallaras las pruebas.

$\square$

Aunque vimos que en general no podemos hablar de que la exponencial se distribuya, sí hay importantes relaciones que notaremos en los siguientes dos teoremas.

Teorema: Si $a,b,n\in\mathbb{N}$, entonces $a^{b+n}=a^b\cdot a^n$

Demostración. De nuevo procederemos por inducción sobre $n$. Si $n=0$, entonces $a^{b+0}=a^b =a ^b \cdot 1=a^b \cdot a^0$, con lo que probamos la base de inducción.

Supongamos entonces que para algún $n$ se tiene que $a^{b+n}=a^b\cdot a^n$, y demostremos el caso para $\sigma(n)$. Sabemos que

\begin{align*}
a^{b+ \sigma(n)}=&a^{\sigma(b+n)}\\
=&a\cdot a^{b+n}\\
=&a\cdot (a^b\cdot a^n)\\
=&a^b\cdot (a \cdot a^n)\\
=&a^b\cdot a^{\sigma(n)}
\end{align*}

Con esto termina la prueba.

$\square$

El siguiente teorema queda como ejercicio de la tarea moral, para que puedas practicar.

Teorema: Si $a,b,n\in\mathbb{N}$, entoces $(a^b)^n=a^{b\cdot n}$.

El factorial

Hasta ahora, sólo hemos ocupado el teorema de recursión débil a la hora de definir las operaciones. A pesar de que antes demostramos que ambas versiones del teorema son equivalentes, la siguiente definición mostrará la naturalidad que tiene el ocupar el teorema de Recursión Fuerte para algunas cosas.

Definición: Se define la función factorial, $f:\mathbb{N}\to \mathbb{N}$, como la única función dada por el teorema de recursión fuerte que cumple que

  • $f(0)=1$
  • $f(\sigma(n))=p_{\sigma(n)}(f(n))$

Usaremos la notación $n!:=f(n)$. Así, la primer parte de la definición dice que $0!=1$ y la segunda dice que $(n+1)!=(n+1)\cdot n!$.

Notemos que en la definición anterior es necesario ocupar el teorema de Recursión Fuerte ya que en cada paso damos una función distinta. En concreto, para dar la definición en $\sigma(n)$ usamos a la función $p_{\sigma(n)}$.

El factorial es una función que jugará un papel importante en varios temas que verás en la facultad. Tiene una fuerte relación con contar cosas, el cual es un tema que posiblemente hayas estudiado en Álgebra Superior II. Aparece al contar las permutaciones de objetos, pero también como parte de la fórmula para los coeficientes binomiales $\binom{n}{k}$. También, lo encontraremos en este curso a la hora de enunciar el teorema de Wilson de teoría de números, pero necesitamos definir más cosas antes de llegar ahí.

Sin embargo, algo que sí podemos hacer ahora es demostrar una propiedad interesante que satisface el factorial.

Proposición: Para todo $n\in \mathbb{N}$, se tiene que $0\cdot 0!+1\cdot 1!+2\cdot 2!+…+n\cdot n!+1=(n+1)!$

Demostración. Procederemos por inducción, el caso base es claro ya que $0\cdot 0!+1= 0+1=1!.$

Supongamos que el resultado es cierto para alguna $n$ y con esta suposición probemos que

$0\cdot 0!+1\cdot 1!+2\cdot 2!+…+n\cdot n!+(n+1)\cdot(n+1)!+1=(n+2)!$.

Sabemos por nuestra hipótesis de inducción que

\begin{align*}
&0\cdot 0!+1\cdot 1!+2\cdot 2!+…+n\cdot n!+(n+1)\cdot(n+1)!+1\\
=&(0\cdot 0!+1\cdot 1!+2\cdot 2!+…+n\cdot n!+1)+(n+1)\cdot(n+1)! \\
=&(n+1)!+ (n+1)\cdot(n+1)!\\
=&(n+1)!(1+n+1)\\
=&(n+1)!(n+2)\\
=&(n+2)!
\end{align*}

En la primer igualdad estamos usando la conmutatividad y asociatividad de la suma. En la segunda igualdad, la hipótesis de inducción. Para la tercer igualdad estamos factorizando el término $(n+1)!$. El resto de igualdades se siguen de las definiciones.

$\square$

Resumen de las propiedades de los exponentes

Para finalizar con la entrada, hacemos un repaso de las propiedades que demostramos, posiblemente las conozcas como las leyes de los exponentes

  • Para todo $n$ número natural, se tiene que $n^0=1$
  • Si $n\neq 0$,entonces $0^n=0$
  • Para todo $n$ número natural, se tiene que $n^1=n$
  • Para todo $n$ número natural, se tiene que $1^n=1$
  • Para $l,m,n$ naturales, se tiene que $(l\cdot m)^n=l\n\cdot m^n$
  • Para $l,m,n$ naturales, se tiene que $n^{l+m}=n^l\cdot n^m$
  • Para $l,m,n$ naturales, se tiene que $n^{l\cdot m}=(n^l)^m$

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más a profundidad la teoría vista.

  1. Encuentra los contraejemplos que faltaron en la entrada
  2. Da la demostración de que $0^n=0$, para toda $n$
  3. Prueba que para todos los naturales $a,b,n$, se tiene que $(a^b)^n=a^{b\cdot n}$
  4. El factorial consiste en «multiplicar los primeros enteros». ¿Qué pasa si queremos hacer algo análogo para sumar los primeros enteros? Da una definición recursiva de una función $S(n)=0+1+2+…+n$, ¿por qué en realidad no es necesario dar una definición recursiva de esta función?
  5. Demuestra que si $n,m$ son naturales tales que existe $k\in\mathbb{N}$ tal que $n\cdot k=n^k=m$, entonces $n^m=m^n$. El regreso de esta afirmación es también verdadero, pero para verlo formalmente, necesitamos desarrollar más teoría

Más adelante…

Con esta entrada, acabamos con las definiciones de operaciones a través de los teoremas de Recursión; sin embargo, no podemos decir que no ocuparemos este teorema en futuras ocasiones, al menos de forma implícita, mucho menos nos olvidaremos del principio de Inducción, el cuál irá siempre adherido al concepto de número natural.

En las siguientes entradas, estudiaremos otro tipo de propiedades de los naturales, relacionadas con el orden y el tamaño que estos tienen. Sin embargo, aún ocuparemos las operaciones que definimos y las relacionaremos; por ejemplo, con el orden que les daremos.

Entradas relacionadas

Álgebra Superior II: Definición del producto y sus propiedades básicas

[latexpage]

Introducción

En la entrada anterior, nos dedicamos a buscar una definición apropiada para la suma de números naturales, y después nos dedicamos a probar las propiedades más elementales que esta operación satisface.

Ahora es el turno de la multiplicación o producto, que se definirá de forma similar a la suma, ya que ocuparemos el teorema de Recursión Débil, y para probar sus propiedades ocuparemos el principio de Inducción.

Te motivamos a releer la entrada anterior y pensar unos momentos en el ejercicio 5 de la entrada anterior.

Definición del producto.

Así como con la suma, recurriremos a una definición recursiva, la cual existe en virtud del teorema de Recursión.

Definición: Sea $m\in\mathbb{N}$, defnimos la función $p_{m}:\mathbb{N}\longrightarrow\mathbb{N}$, como la función que satisface las propiedades siguientes:

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

Denotaremos a $p_{m}(n)$ como $m\cdot n$, o simplemente como $mn$

Ejemplo: Para aclarar la definición anterior, consideremos $p_{7}$ y realicemos el diagrama conmutativo correspondiente a su definición recursiva.

Recordemos que las flechas indican a donde es mandado cada elemento bajo cada función, entonces las flechas verticales, justamente son las que nos indican los valores de $p_{7}$ en cada número natural, observemos que estos valores coinciden con la conocida tabla del $7$.

Aprendiendo a multiplicar por uno

En este momento, demostraremos las propiedades más importantes del producto. Tenemos la fortuna de que contamos con una buena cantidad de propiedades de las funciones $s_{n}$, las cuales ya podremos usar sin ningún problema, más aún, para simplificar la notación haremos uso de la notación $m+n$, en vez de la notación $s_{m}(n)$, cada vez que se pueda.

Siguiendo la idea anterior, mencionamos la siguiente identidad, que es solo una reformulación del punto (2) de la definición del producto, pero que nos servirá para esclarecer la mayor parte de las pruebas.

Observación: $a\cdot\sigma(n)=a+(a\cdot n)$

Para referir a esta observación en una demostración ocuparemos el símbolo $\overset{*}{=}$

Proposición: Para toda $n\in\mathbb{N}$, se tiene que $p_{1}(n)=n$, es decir, $1\cdot n=n$

Demostración. Como se esperaba, la prueba es por inducción sobre $n$.

Base inductiva: Por la definición de $p_{1}$, tenemos que $p_{1}(0)=0$

Hipótesis de inducción: Supongamos que para algún $n$, se tiene que $p_{1}(n)=n$

Paso inductivo: Debemos demostrar que $p_{1}(\sigma(n))=\sigma(n)$, esto se sigue por las siguientes igualdades

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

Donde la última igualdad se da recordando que en la entrad a anterior probamos que $s_{1}(n)=\sigma(n)$

$\square$

Con esto hemos aprendido a multiplicar por $1$.

Aprendiendo a multiplicar por cero

Proposición: Para toda $n\in\mathbb{N}$, se tiene que $p_{0}(n)=n$

Demostración. Procedamos por inducción sobre $n$, la base inductiva es directa de la definición, ya que $p_{0}(0)=0$.

Nuestra hipótesis de inducción consiste en suponer que para alguna $n$ se tiene que $p_{0}(n)=0$. Entonces queda demostrar que $p_{0}(\sigma(n))=0$. Esto se sigue de las siguientes igualdades.

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

$\square$

La propiedad distributiva izquierda

La siguiente propiedad es una de las más famosas, ya que nos permitirá relacionar la suma y el producto, además jugará un papel importante en la demostración de las siguientes propiedades.

Proposición (propiedad distributiva izquierda): Si $a,b,n$ son números naturales, entonces $p_{s_{a}(b)}(n)=s_{p_{a}(n)}(p_{b}(n))$, u ocupando la notación familiar $(a+b)\cdot n=(a\cdot n)+(b\cdot n)$.

Demostración: Procedamos por inducción, como podrás notar con todas estas demostraciones, la inducción será sobre la variable que aparezca más a la derecha de nuestras expresiones, es decir, la inducción será sobre $n$

Base inductiva: Por la definición del producto tenemos que, $(a+b)\cdot 0=0$, y por las propiedades que demostramos para la suma, concluimos que $0=0+0$, sin embargo; de nuevo por la definición del producto, $0=(a\cdot n)$ y $0=(b\cdot n)$, uniendo todas estas igualdades concluimos que $(a+b)\cdot 0=(a\cdot n)+(b\cdot n)$, justo como queremos.

Hipótesis de inducción: Supongamos que para algún $n$ se tiene que $(a+b)\cdot n=(a\cdot n)+(b\cdot n)$.

Paso inductivo: Debemos probar que $(a+b)\cdot\sigma(n)=(a\cdot\sigma(n))+(b\cdot\sigma(n))$. Por la observación que hicimos, tenemos

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

A partir de aquí, el resultado se seguirá usando la asociatividad y la conmutatividad de la suma, en la siguiente cadena de igualades detallamos la demostración paso a paso ¿Puedes identificar cómo ocupamos las propiedades de la suma?.

\begin{align*}
(a+b)+((a\cdot n)+(b\cdot n))&=a+(b+((a\cdot n)+(b\cdot n)))\\
&=a+((b+(a\cdot n))+(b\cdot n))\\
&=a+(((a\cdot n)+b)+(b\cdot n))\\
&=a+((a\cdot n)+(b+(b\cdot n)))\\
&=(a+(a\cdot n))+(b+(b\cdot n))\\
&\overset{*}{=}(a\cdot \sigma (n))+(b\cdot \sigma (n))
\end{align*}

$\square$

Aunque la prueba anterior fue un poco más confusa que las anteriores, las consecuencias que tendrá esta proposición serán sumamente importantes.

El producto es conmutativo

Como mencionamos, la asociatividad y la conmutatividad, serán una consecuencia de las propiedades distributivas, por el momento veamos que en efecto la suma conmuta.

Proposición (conmutativiad): Si $m,n\in \mathbb{N}$, entonces $m\cdot n=n\cdot m$

Demostración. Una vez más hagamos la prueba por inducción sobre $n$

Base inductiva: Por definición tenemos que $m\cdot 0 =0$, además $p_{0}(m)=0$ por lo demostrado antes, es decir que $m\cdot 0=0=0\cdot m$

Hipótesis de inducción: Supongamos que para alguna $n$, se tiene que $m\cdot n=n\cdot m$

Paso inductivo: Debemos probar que $m\cdot\sigma(n)=\sigma(n)\cdot m$. Esto se sigue ya que

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

Pero ya demostramos que $m=1\cdot m$, usando esto y la propiedad ditributiva, podemos concluir que

\begin{align*}
m+(n\cdot m)&=(1\cdot m )+(n\cdot m)\\
&=(1+n)\cdot m=\sigma(n)\cdot m
\end{align*}

$\square$

Con la conmutatividad, podemos probar de manera inmediata el siguiente resultado

Corolario (propiedad distributiva derecha): Si $a,b,n$ son números naturales, entonces $a\cdot(b+ n)=(a\cdot b)+(a\cdot n)$.

La prueba queda como un ejercicio moral, en parte porque su prueba no requiere Inducción. Con este resultado, podemos probar la propiedad asociativa del producto.

El producto es asociativo

Con la propiedad asociativa derecha , podemos dar la demostración de la propiedad asociativa del producto

Proposición (asociatividad): Si $a,b,n$ son números naturales, se tiene que $a\cdot(b\cdot n)=(a\cdot b)\cdot n$.

Demostración. De nuevo procedamos por inducción sobre $n$

Base inductiva: Notemos que por definición, para cualquier número natural $m$ se tiene que $0=p_{m}(0)=m\cdot 0$. Con esto en mente tenemos que, $(a\cdot b)\cdot(0)=0=a\cdot 0=a\cdot(b\cdot 0)$ que es justo la base de inducción.

Hipótesis de Inducción: Supongamos que para alguna $n\in \mathbb{N}$, tenemos que $(a\cdot b)\cdot n=a\cdot(b\cdot n)$

Paso Inductivo: Demostremos que $(a\cdot b)\cdot\sigma(n)=a\cdot(b\cdot \sigma(n))$. Como

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

la igualdad que no está justificada es la aplicación de la propiedad distributiva.

$\square$

Ley de la cancelación

Para concluir con las propiedades del producto, enunciamos la propiedad de la cancelación del producto, recordemos que esta propiedad también es válida para la suma. Para hacer esta prueba necesitamos trabajar un poco.

Recordemos el ejercicio 2 de la Tarea moral de la entrada Principio de inducción y teoremas de recursión, el cual ya hemos ocupado anteriormente:

Si $n\neq0$, entonces existe $a\in \mathbb{N}$ tal que $n=\sigma(a)$

De la misma forma, el ejercicio 1 de la Tarea moral de la entrada pasada dice que:

Si $a,b\in\mathbb{N}$ son tales que $a+b=0$, entonces $a=b=0$

Con estos resultados en mente probamos el siguiente lema.

Lema: Si $n\neq 0$ y $m\in \mathbb{N}$ es tal que $m\cdot n=0$, entonces $m=0$.

Demostración. Como $n\neq0$, entonces existe $a\in \mathbb{N}$, tal que $n=\sigma(a)$, entonces tenemos que

\begin{align*}
0&=m\cdot n\\
&=m\cdot\sigma(a)\\
\overset{*}{=}m+(m\cdot a).
\end{align*}

Entonces tenemos que $m\cdot a=0$ y que $m=0$ que es lo que debíamos probar

$\square$

Es común usar una equivalencia lógica del enunciado anterior, la cual dice:

Si $n,m\in \mathbb{N}\setminus\{0\}$, entonces $n\cdot m\in \mathbb{N}\setminus\{0\}$

Proposición (ley de cancelación): Si $m,n$ son números naturales y $a\neq0$ y cunplen que $a\cdot n=a\cdot m$, entonces, $n=m$

Demostración. De nuevo, procedamos por inducción sobre $n$

Base inductiva: Supongamos que $n=0$ y $a\neq0$, entonces $a\cdot m=a\cdot n=a\cdot0 =0,$ por el Lema tenemos que $m=0=n$.

Hipótesis de inducción: Supongamos que para algún $n$, tenemos que si $a\neq0$ y $a\cdot n=a\cdot m$, entonces $n=m$

Paso inductivo: Probemos para $\sigma(n)$, sea $a\neq 0$ y supongamos que $a\cdot\sigma(n)=a\cdot m$

Como $\sigma(n)\neq 0$, y por hipótesis, $a\neq0$, entonces por la equivalencia del lema, concluimos que $a\cdot\sigma(n)\neq 0$, de donde $a\cdot m\neq 0$, esto implica que $m\neq 0$, por lo que existe $b$ tal que $m=\sigma(b)$, entonces podemos escribir

\begin{align*}
a+a\cdot n& \overset{*}{=}a\cdot\sigma(n)\\
&=a\cdot m\\
&=a\cdot\sigma(b)\\
&\overset{*}{=}a+a\cdot b
\end{align*}

Ocupando la ley de cancelación de la suma, tenemos que $a\cdot n=a\cdot b$

Pero por hipótesis de inducción debemos de tener que $n=b$, esto quiere decir que $\sigma(n)=\sigma(b)=m$, justo como debíamos probar.

$\square$

Con esta prueba concluimos las propiedades más fundamentales del producto.

Resumen de las propiedades del producto

Para finalizar con la entrada, haremos un compendio de las propiedades que demostramos

  • Para todo $n$ natural, se tiene que $1\cdot n=n=n \cdot 1$
  • Para todo $n$ natural, se tiene que $0\cdot n=0=n \cdot 0$
  • Para $l,m,n$ naturales cualesquiera se tiene que $(l+m)\cdot n=(l\cdot n)+(m\cdot n)$
  • Para $m,n$ naturales se tiene que $m\cdot n=n\cdot m$
  • Para $l,m,n$ naturales cualesquiera se tiene que $l\cdot(m+n)=(l\cdot m)+(l\cdot n)$
  • Para $l,m,n$ naturales cualesquiera se tiene que $(l\cdot m)\cdot n=l\cdot(m\cdot n)$
  • Para $m,n$ naturales con $m\neq 0$, si $m\cdot n=0$, entonces $n=0$
  • Para $l,m,n$ naturales con $l\neq 0$, si $l\cdot n=l\cdot m$, entonces $n=m$

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más a profundidad la teoría vista.

  1. Prueba la Propiedad distributiva derecha
  2. Usando únicamente la ley de cancelación el producto, demuestra el Lema previo a la demostración de la ley de cancelación
  3. ¿Qué pasa si en el enunciado de la ley de la cancelación, no asumimos que $a\neq 0$?
  4. Demuestra usando el Lema previo a la demostración de la ley de cancelación que si $n,m\in \mathbb{N}\setminus\{0\}$, entonces $n\cdot m\in \mathbb{N}\setminus\{0\}$
  5. Da una definición recursiva de las funciones $\eta_{m} (n)=m^n$ y prueba las leyes de los exponentes.

Más adelante…

Con las propiedades de la suma y del producto en nuestra bolsa de herramientas, tenemos ya una rica teoría que desarrollar; nos falta aún definir una relación muy familiar en el conjunto $\mathbb{N}$, el orden, al cual ya hemos apelado en la demostración del teorema de la Recursión Débil.

Por el momento estudiaremos con mayor detalle los conjuntos infinitos, donde veremos la importancia de los naturales dentro de esta clase de conjuntos.

Entradas relacionadas

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

[latexpage]

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

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más a profundidad la teoría vista.

  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

Álgebra Superior II: La construcción de los naturales

[latexpage]

Introducción

En la entrada pasada presentamos los axiomas de Peano como una forma de abordar el problema de por qué los naturales se comportan como nuestra intuición nos indica. Sin embargo, también vimos que esta solución no respondía la pregunta de por qué existen los naturales dentro de la formalización matemática con la que estamos trabajando. Por esta razón, introdujimos la definición del sucesor de un conjunto arbitrario y empezamos a iterarla en el conjunto vacío para generar una lista de conjuntos, que relacionamos con los números naturales que conocemos.

Por último, notamos que ocupar esta idea, al menos de forma directa, nos llevaría al problema de nunca acabar de definir a todos los números naturales y, por lo tanto, no poder definir en sí el conjunto de los naturales.  Es por eso que en esta entrada acabaremos, de una vez por todas, con el problema de definir con precisión el conjunto de números naturales y ver que, en efecto, esta construcción que haremos se apega a no sólo a nuestra intuición, sino también a los axiomas de Peano.

Conjuntos inductivos

Antes de empezar con la tarea de definir a los números naturales, recordamos la definición del sucesor de un conjunto.

Definición: Si $A$ es un conjunto, definimos el sucesor de $A$, como $\sigma(A):=A\cup \{A\}$.

Como mencionamos en las notas pasadas, buscamos que \[\mathbb{N}=\{\emptyset,\sigma(\emptyset),\sigma(\sigma(\emptyset)),…\},\] por lo que $\mathbb{N}$, satisfaría dos propiedades que englobamos en la siguiente definición.

Definición: Diremos que un conjunto $S$ es inductivo si cumple que:

  1. $\emptyset\in\mathbb{N}$ y
  2. si $X\in S$, entonces $\sigma(X)\in S$.

Notemos que estas dos propiedades son muy similares a los dos primeros axiomas de Peano.

Hay que remarcar que aunque no sabemos que exista un conjunto tal que sus elementos son $\emptyset,\sigma(\emptyset),\sigma(\sigma(\emptyset)),…$, en caso de que sí existiera, sería un hecho que tal conjunto sería inductivo.

Otro posible ejemplo de un conjunto inductivo podría verse como \[\{…\sigma(\sigma(\{\{\emptyset\}\})), \sigma(\{\{\emptyset\}\}), \{\{\emptyset\}\},\emptyset,\sigma(\emptyset),\sigma(\sigma(\emptyset)),…\}.\] Intuitivamente podemos notar que si $S$ es un conjunto inductivo, entonces, $\mathbb{N}\subset S$, por lo que uno podría aventurarse y definir a los naturales como $\{x:  x \text{ está en todo conjunto inductivo}\}$. Sin embargo, los axiomas que de teoría de conjuntos que tenemos hasta ahora no nos permiten saber si existe un conjunto así.

A pesar de que como se dijo, el hacer esto no es correcto, la idea es muy interesante y útil, ya que motiva la siguiente proposición acerca de la intersección de conjuntos inductivos.

Proposición: Si $B\neq\emptyset$ es un conjunto tal que todos sus elementos son inductivos, entonces $\bigcap {B}$ es también un conjunto inductivo.

Demostración. Como $B\neq\emptyset$, sabemos que la intersección sí es un conjunto. Veamos que este conjunto es inductivo.

Antes de hacer esto recordemos que por definición, los elementos de $\bigcap{B}$ son precisamente, todos los $x$ tales que $x\in Y$ para todo $Y\in B$.

Para ver que $\bigcap B$ es inductivo, necesitamos verificar que cumpla las dos características de la definición:

  1. $\emptyset\in\bigcap B$: Sea $Y\in B$ arbitrario, como los elementos de $B$ son inductivos, $\emptyset\in Y$, y como $Y$ es arbitrario, podemos concluir que $\emptyset$ está en todos los elementos de $B$, pero esta es la definición de que $\emptyset\in \bigcap B$.
  2. $x\in \bigcap B \Rightarrow \sigma(x)\in \bigcap B$: Sea $x\in \bigcap B$, veamos que $\sigma(x)\in \bigcap B$. Sea $Y\in B$, como $x\in\bigcap B$, entonces $x\in Y$ y como $Y$ es inductivo, $\sigma(x)\in Y$. De nuevo, como $Y$ es arbitrario, se sigue que $\sigma(x)$ está en todos los elementos de B, por lo que $\sigma(x)\in\bigcap B$.

Con esto demostramos que $\bigcap B$ es inductivo.

$\square$

En otras palabras, «la intersección arbitraria de conjuntos inductivos es un conjunto inductivo».

El axioma del infinito

Por todo lo escrito anteriormente, y meditando el hecho de que si partimos de los primeros axiomas de la teoría de conjuntos, sólo podemos crear conjuntos con una cantidad finita de elementos, parece ser que la existencia de un conjunto como los naturales, no podrá ser deducida con las herramientas que tenemos. Esto en efecto es así. Por ello, debemos introducir un nuevo axioma de la teoría de conjuntos.

Axioma del infinito: Existe un conjunto inductivo.

El axioma del infinito no nos garantiza inmediatamente la existencia de $\mathbb{N}$, ya que como se vio en el ejemplo, $\mathbb{N}$ no es el único conjunto inductivo. Sin embargo, esta es la última pieza que necesitamos para poder construir a los naturales. Hacemos esto a continuación.

Sea $A$ algún conjunto inductivo (que nos garantiza el axioma del infinito), y consideremos $B=\{X\subset A \mid X \text{ es inductivo}\}$ (¿por qué B es un conjunto?). Notemos que $A\in B$ por lo que $B$ es no vacío, por lo tanto, podemos pensar en su intersección, $\bigcap B$. Como los elementos de $B$ son conjuntos inductivos, por la proposición anterior concluimos que $\bigcap B$ es inductivo. A esta intersección la denotaremos como $\mathbb{N}_{A}$. ¡Ya apareció por primera vez el símbolo de números naturales! Pero tiene algo adicional: usamos un subíndice $A$ ya que a primera vista, su construcción depende del conjunto inductivo $A$ con el que empezamos. Sin embargo, justamente, el paso siguiente será ver que $\mathbb{N}_{A}$ no depende de $A$.

Para ello, primero hacemos la observación de que si $Y\subset A$ es inductivo, entonces $\mathbb{N}_{A}\subset Y$, la cual te dejamos corroborar usando las propiedades de la intersección. Dicho esto, probamos lo siguiente.

Proposición: Si $C$ es otro conjunto inductivo, entonces $\mathbb{N}_{A}= \mathbb{N}_{C} $.

Demostración. Consideremos $\mathbb{N}_{A} \cap \mathbb{N}_{C} $, el cual sabemos que es un conjunto inductivo. Como $\mathbb{N}_{A} \cap \mathbb{N}_{C} \subset A$, por la observación anterior, concluimos que $\mathbb{N}_{A} \subset \mathbb{N}_{A} \cap \mathbb{N}_{C} $. Como la intersección está contenida en cada intersecando, $\mathbb{N}_{A} \subset \mathbb{N}_{A} \cap \mathbb{N}_{C}\subset\mathbb{N}_{A} $, por lo que $\mathbb{N}_{A} = \mathbb{N}_{A} \cap \mathbb{N}_{C} $. Haciendo las mismas observaciones para $\mathbb{N}_{C}$, concluimos que $\mathbb{N}_{A} = \mathbb{N}_{A} \cap \mathbb{N}_{C}= \mathbb{N}_{C} $, con lo que concluimos la prueba.

$\square$

Como sabemos ahora que el conjunto $\mathbb{N}_{A}$ no depende del conjunto $A$ inductivo con el que empecemos, finalmente podemos definir al conjunto de números naturales.

Definición: Si $A$ es algún conjunto inductivo, definimos $\mathbb{N}:=\mathbb{N}_{A}$, definimos $0:=\emptyset$ y la función sucesor como $\sigma:\mathbb{N}\to \mathbb{N}$ tal que $\sigma(n)=n\cup \{n\}$.

Un modelo para los axiomas de Peano

Para concluir esta entrada veremos que los números naturales que hemos construido en la sección anterior se comportan justo como dicen nuestra intuición y los axiomas de Peano. En realidad, la construcción de la función sucesor y del conjunto $\mathbb{N}$ fue siempre motivada por estas ideas, por lo que no deberá ser difícil probar que en verdad todo funciona como queremos.

Teorema: El conjunto $\mathbb{N}$ junto con $0$ y $\sigma$, satisfacen los cinco axiomas de Peano.

Demostración. Veamos que se verifican los cinco axiomas de Peano.

$0\in\mathbb{N}$: como $\mathbb{N}$ es inductivo, $0=\emptyset\in\mathbb{N}$.

Si $n\in \mathbb{N}$, entonces $\sigma(n)\in\mathbb{N}$: Si $n\in\mathbb{N}$, como $\mathbb{N}$ es inductivo, se sigue que $\sigma(n)\in\mathbb{N}$.

Para toda $n\in\mathbb{N}$ se tiene que $\sigma(n)\neq 0$: Como $\sigma(n)=n\cup\{n\}$, tenemos que $n\in\sigma(n)$ por lo que $\sigma(n)\neq\emptyset=0$.

Si $\sigma(n)=\sigma(m)$, entonces $n=m$: Como $\sigma(n)=\sigma(m)$ y $n\in\sigma(n)$, $n\in\sigma(m)= m\cup\{m\}$, de donde $n\in\{m\}$ o $n\in m$. Si $n\in \{m\}$, entonces $n=m$ y concluimos.

Si $n\in m$, veamos que podemos decir de m, procediendo análogamente, podemos notar que $m=n$ o $m\in n$, en el primer caso, llegamos a lo que queremos, si se da el segundo caso habremos demostrado que $n\in m\in n$ lo cual contradice el axioma de Regularidad.

Si $S\subset\mathbb{N}$ tal que $0\in S$ y $n\in S \Rightarrow \sigma(n)\in S$, entonces $S=\mthbb{N}$: Notemos que las hipótesis de $S$, implican que este es un conjunto inductivo, por lo que $\mathbb{N}=\mathbb{N}_{S}\subset S\subset \mathbb{N}$ por lo que en efecto, ambos conjuntos son iguales.

$\square$

Notemos que todos los axiomas salieron de forma casi inmediata de la definición de $\mathbb{N}$ o de la definición de $\sigma$, justo como esperábamos.

Tarea moral

  • Completa los detalles sobre por qué el conjunto $B$, de los conjuntos inductivos de $A$, sí existe. Necesitarás usar un axioma muy específico de la teoría de conjuntos.
  • Demuestra que si $x\subset y\subset\sigma(x) $, entonces $y=x$ o $y=\sigma(x)$.
  • Si aún no estás tan acostumbrado a las intersecciones arbitrarias, considera la definición de $\mathbb{N}’:=\{x\in A:  x \text{ está en todo conjunto inductivo}\}$ ¿Cómo se relaciona el axioma del Infinito, con el hecho de que esto sí es un conjunto?
  • Esboza una demostración de que $\mathbb{N}’=\mathbb{A}$.
  • Usa el Principio de Inducción para demostrar que si $n\neq 0$, entonces $n=\{0, 1, 2, …, n-1\}$.

Más adelante…

Ya que construimos a los números naturales, y vimos que en verdad funcionan como esperábamos, nuestro siguiente objetivo, será definir una suma, un producto y un orden en este conjunto. Así como lo hicimos con los axiomas de Peano, veremos que nuestras definiciones coincidirán con las propiedades que conocemos.

Para hacer esto seguiremos pensando en la definición conjuntista que hemos dado de los naturales y no sólo en los axiomas de Peano. Aunque sí nos basaremos fuertemente en ellos, sobre todo en el quinto axioma. A este lo conocemos como principio de inducción y tendrá su mayor aplicación a la hora de demostrar el teorema de la recursión, el cual a su vez la herramienta que tendremos para definir la suma y producto en los naturales.

Entradas relacionadas

Álgebra Superior II: Introducción al curso y a los números naturales

[latexpage]

Introducción

El curso de Álgebra Superior I tuvo como principal objetivo darte las herramientas necesarias para poder entender a grandes rasgos, la teoría que sustenta las primeras asignaturas con las que te encuentras a nivel universitario en tu trayectoria matemática. Por esta razón, en el temario se incluyeron los temas de lógica, teoría de conjuntos, inducción matemática y espacios vectoriales. Sin embargo, quedaron abiertas algunas preguntas, por ejemplo: ¿cómo sabemos que los conjuntos con los que trabajamos existen?, ¿qué es en el fondo el conjunto de números reales que usamos en los espacios vectoriales? o ¿por qué funciona el principio de inducción?

En este sentido, el curso de Álgebra Superior II es la continuación de Álgebra Superior I, ya que el objetivo de este curso será responder estas preguntas que el anterior semestre quedaron sin responder. Con esto en mente, usaremos las herramientas de la teoría de conjuntos que desarrollamos con anterioridad para estudiar qué son los números naturales, los enteros y hasta los complejos. Haremos una escala en cada tema para poder entender a profundidad las características con las que hemos estado familiarizados desde antes de la carrera y conocer otras propiedades que te servirán a lo largo de tu Licenciatura.

En la parte final del curso, introduciremos otras estructuras con las que seguramente ya estarás familiarizado gracias al curso de Cálculo Diferencial e Integral I: el anillo de polinomios con coeficientes reales (o complejos). Como en el caso de los temas anteriores, nos detendremos a estudiar las propiedades que caracterizan a este conjunto y las similitudes que podemos encontrar con algunos de los sistemas numéricos, como los números enteros.

La intuición detrás de formalizar a los números naturales

Seguramente, desde la primaria aprendiste a contar y con el pasar del tiempo, la idea de los números naturales y las características que se necesitan para contar “de uno en uno” se han hecho muy familiares en tu mente. A grandes rasgos, cuando contamos tenemos mente a los números $$0,1,2,3,4,5,6,7,\ldots.$$ De hecho, las propiedades de estos números probablemente son tan familiares que ya no reparas en ello a la hora de contar. Al cero le sigue el uno. Al uno le sigue el dos. Y así sucesivamente. Esto resulta práctico a la hora de contar, pero algo impráctico a la hora de establecer fundamentos matemáticos de los números naturales. Por esta razón, tomémonos un momento para pensar en las propiedades que satisface este sistema numérico.

La primera característica en la que podemos pensar es que los números naturales cuentan con un elemento especial de entre todos los demás números, el primero de todos ellos. Dependiendo del contexto, el $0$ (y no el $1$) es considerado como el primer número natural y coincide con la intuición de que podemos «tener cero cosas», es decir, ninguna. Es importante que sepas que en cierto contextos (por ejemplo, otros cursos o áreas de las matemáticas) podría no serlo. La recomendación es que siempre uses la convención del área o comunidad con la que estés trabajando. En este curso el número $0$ siempre será un número natural.

Otra característica con la que seguramente estamos muy familiarizados es que si bien los números naturales tienen un comienzo (en nuestro caso, el $0$), por otra parte nunca terminan. No importa hasta qué número podamos haber contado, siempre podemos dar un paso más y avanzar al siguiente número. Cuando tenemos un natural, decimos entonces que siempre tiene un sucesor a este último número. Sabemos que sólo hay un sucesor para cada número.

Otra característica clave de los números naturales es que, a la hora de contar, nunca regresamos a un número por el cual ya pasamos; es decir, bajo ninguna circunstancia contamos $107, 108, 109, 37,…$. Para enunciar esto formalmente, lo diremos en dos partes. Primero, el $0$ no es el sucesor de ningún número y segundo, en ninguna circunstancia, un número es el sucesor de dos números diferentes.

Existe una quinta propiedad, tal vez más sutil que las anteriores, y es que si empezamos a contar desde el cero y vamos contando de uno en uno, entonces podremos alcanzar cualquier número natural, siempre que el tiempo lo permita.

Resulta que estas propiedades intuitivas son suficientes para definir muchas otras operaciones en los números naturales y para obtener una gran cantidad de propiedades. Es por esta razón que conviene incluirlas en nuestra formalización de los naturales, como discutimos a continuación.

Los axiomas de Peano

 A finales del siglo XIX, los matemáticos empezaron a notar que a partir de algunas propiedades tan elementales como las que discutimos arriba, se podían probar las leyes de la aritmética que conocemos, y en 1889, Giuseppe Peano, basado en las propiedades que acabamos de enunciar, dio un conjunto de axiomas que usó para estudiar sistemáticamente a los números naturales. Estos axiomas son:

  1. $0$ es un número natural.
  2. Si $n$ es un número natural, entonces existe un único natural, denotado $\sigma(n)$ al que llamamos su sucesor.
  3. Para todo número natural, $\sigma(n)\neq0$.
  4. Si $n,m$ son números naturales, tales que $\sigma(n)=\sigma(m)$, entonces $n=m$.
  5. Si $S$ es un subconjunto de números naturales tal que: $0$ está en $S$, y para todo $n$ en $S$, se cumple que $\sigma(n)$ está también en $S$, entonces $S$ es el conjunto de todos los naturales.

Nota que cada una de las cinco propiedades coinciden con una de las propiedades intuitivas que mencionamos antes.

Encontrando los primeros naturales

El logro de Peano fue muy importante, ya que permitió reducir la teoría de los números naturales a solo cinco axiomas; sin embargo, aún quedan abiertas las preguntas ¿qué son los números naturales? y ¿cómo sabemos que existen? Aunque se hayan mencionado las propiedades de un objeto, no necesariamente tiene que existir tal objeto. Este fue el gran problema al que se enfrentaron los matemáticos cuanto intentaron definir a un conjunto al que pertenecen todos los conjuntos.

Es por esta razón que debemos fundamentar la construcción de los números naturales en teoría que ya tengamos desarrollada. Por esta razón, a partir de este punto se aparece la teoría de los conjuntos, la cual nos permitirá definir formalmente lo que significan los símbolos que diariamente ocupamos (como el $0$), para después ver que en efecto estos conjuntos satisfacen los axiomas de Peano.

Definición: $0:=\emptyset$.

Cuando ponemos $:=$, quiere decir que estamos definiendo algo, típicamente un símbolo. Cuando veas algo así aparecer, puedes pensar que significa «esta es la primera vez que usamos el símbolo $0$, y lo que querrá decir es el conjunto vacío». Podemos pensar en esta definición como una simple ocurrencia de notación; sin embargo, es curioso notar que, pensando intuitivamente, $\emptyset$ tiene en efecto cero elementos. Más adelante veremos que los demás números naturales también satisfacen esta intuitiva coincidencia.

Definición: Dado un conjunto $A$ arbitrario, definimos el sucesor de $A$ como $\sigma(A):=A\cup\{A\}$.

Notemos que en realidad $\sigma$ no es en el sentido estricto una función ¿por qué? Más bien, lo que estamos haciendo es explicar a qué nos referimos con el símbolo $\sigma(A)$.

Considerando que hemos construido el primer número natural (el $0$) y hemos dado una forma de construir sucesores, parece una buena idea considerar \[\sigma(0)=\sigma(\emptyset)=\emptyset\cup\{\emptyset\}=\{\emptyset\}\]

Y definir $1:= \{\emptyset\}$, análogamente podemos pensar que \[2:=\sigma(1)=\sigma(\{\emptyset\})=\{\emptyset\}\cup\{\{\emptyset\}\}=\{\emptyset,\{\emptyset\}\}\]

Y continuar así, efectivamente, estos conjuntos coinciden con la intuición de tener respectivamente $1$ y $2$ elementos.

Los «disfraces» de los números naturales

Actualmente usamos el sistema de numeración arábigo y sabemos exactamente qué quieren decir los «dibujos» $1$, $2$, $3$, $4$, etc. Si fueramos romanos, estaríamos usando los «dibujos» $I$, $II$, $III$, $IV$, etc. De manera estricta, los «dibujos» no son lo mismo que «el concepto que representan». Es decir, en el fondo, $2$ y $II$ son «disfraces distintos para el mismo concepto». Pero ninguno de esos «dibujos» es el concepto mismo, ni vive de manera formal en la teoría que estamos construyendo.

Lo que sí vive en la teoría que construimos es el $\{\emptyset,\{\emptyset\}\}$, pues a partir de los axiomas se puede garantizar su existencia. Por supuesto, en el curso usaremos los «disfraces» habituales de estos conceptos, de modo que casi siempre escribiremos $2$, $7$, $51$, etc. Sin embargo, es crucial que en todo momento tengas en cuenta que cuando escribimos esos «dibujos», en el fondo están las construcciones formales que hemos estado realizando.

Tarea Moral

  • Prueba a partir de sólo los axiomas de Peano, que $n\neq \sigma (n) $ para todo $n\in\mathbb{N}$.
  • ¿Qué axiomas de Peano satisface el conjunto $\sigma(\mathbb{N})$, es decir, el conjunto de los números a partir del $1$?
  • ¿Cómo será un conjunto y una función que satisfagan los axiomas 1), 2), 4) y 5) de Peano, pero que no satisfaga el 3)? ¿Puedes construir formalmente un conjunto y una función así?
  • A partir de la definición de $\sigma(n)$ que dimos, demuestra que para todo número natural $n$ se satisface que $n\in\sigma(n)$ y que $n\subset\sigma(n)$.
  • Demuestra que si $A$ es un conjunto, entonces $\sigma(A)$ es un conjunto. Para ello, tendrás que recordar los axiomas de teoría de conjuntos.

Más adelante

Hemos empezado a definir a los números naturales a partir del $0$ (el conjunto vacío) y la función sucesor $\sigma$; sin embargo, la realidad es que el proceso que hemos descrito debe ser refinado, ya que si continuamos así, jamás acabaremos de definir la infinidad de números naturales que queremos que existan. Incluso asumiendo que los podemos definir a todos, un segundo problema que se origina es el intentar unirlos en un solo conjunto, justamente el conjunto de los números naturales. Uno podría intentar ocupar el principio de inducción para resolver el problema; sin embargo, recordemos que por el momento sólo contamos con los axiomas de la teoría de conjuntos, y aún no sabemos que el principio de inducción (visto como en álgebra superior I, o como axioma de Peano) sea válido. Entonces, necesitaremos pensar cómo resolver el problema desde otra perspectiva.

Más aún, queda el problema de ver que los número naturales que definamos sí satisfagan los axiomas de Peano, para que a partir de ello podamos comenzar a introducir otras propiedades aritméticas y de orden.

Entradas relacionadas