Archivo del Autor: Guillermo Oswaldo Cota Martínez

Acerca de Guillermo Oswaldo Cota Martínez

Soy Guillermo. Soy pasante de la Licenciatura en Matemáticas en la Facultad de Ciencias de la UNAM, y estudiante de la Licenciatura en Ciencia de Datos del IIMAS, UNAM. Me interesan los problemas referente al análisis de datos y a la docencia.

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

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

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:

$S_0=0$
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:

$\phi(0)=a$
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:

$0!=1$
$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:

$a_0=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$

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.

Tarea Moral

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)$
Da una definición explícita de la función del inciso anterior.
Da una definición recursiva para las siguientes sucesiones:
- $a_n=2n$
- $a_n=2n+1$
- $a_n=2^n$
- $a_n=0$

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

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

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

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

Introducción

En esta entrada vamos a hablar de el principio de inducción que se deriva del quinto axioma de Peano. Veremos cómo es que nos ayudará a un nuevo tipo de demostraciones, lo que significa en términos simples y algunos ejemplos de su uso.

El efecto dominó

Pensemos un poco en cómo funciona la inducción matemática viendo un ejemplo con las fichas de dominó. Imaginamos tenemos tres fichas de domino y las paramos una detrás de otra:

Si nosotros tiramos la primera ficha, las otras dos caerán:

Lo que se necesita para que se caigan las fichas será que la primera ficha caiga. Esto es cierto bajo ciertas condiciones. Deberemos saber que las fichas están suficientemente juntas para que una tire a la otra. Si por ejemplo, la última pieza estuviera muy lejos, la segunda pieza no la tiraría:

Con esto en mente, podríamos decir que todas las piezas de dominó se caen si:

La primera pieza se cae.
Cada vez que una pieza se cae, la pieza que sigue igual se cae.

Ahora, supongamos que tenemos una sucesión infinita de piezas de dominó, y enumeremos las piezas según los números naturales:

En el caso de que nuestras piezas estén bien colocadas, si tiramos la pieza $0$, esperaremos que se caiga la ficha $1$, seguido de la $2,$ la $3$ y así sucesivamente. De hecho si por algún momento dejáramos de ver las piezas y volteamos a ver en algún momento cualquier ficha cayendo, sabremos que la siguiente igual se cae. Es decir, imagina que nos distraemos después de tirar la primera ficha, al momento de volver a voltear a ver las fichas cayendo, estaremos viendo que alguna pieza se va cayendo tirando la que sigue. Digamos que nombramos a esta pieza la ficha $n$, entonces observaremos a la pieza $n+1$ caer enseguida:

Lo que nos interesa para decir que todas las piezas se caen es que si una ficha se cae, la siguiente se cae. Es esta misma idea bajo las que se rige la inducción matemática, veamos la parte matemática de esta idea.

Sobre el quinto axioma de Peano

Veamos qué nos dice el último axioma que definimos con anterioridad:

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

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

Entonces $S=\mathbb{N}$

Y veamos cómo es que esto se une con lo que hemos dicho sobre las fichas de dominó. La primera condición la podemos traducir como

1.Se cae la primera pieza.

Mientras que la segunda condición del axioma nos diría que:

2. Siempre que se cae una ficha, se cae la ficha que se encuentra delante.

Finalmente si se cumplen estas dos condiciones, nuestro axioma nos diría que el conjunto $S$ es el conjunto de los números naturales, pero recordemos que esto en términos del dominó significa que todas las piezas se caen. Entonces lo que nos dice el quinto axioma es que para verificar que un conjunto de números naturales es de hecho el conjunto de los números naturales, deberemos de ver que el primer número natural está y cada vez que veamos que un número natural está en el conjunto, su sucesor también deberá estar. La razón por la que intuitivamente esto funciona es por el principio del dominó.

Cuando nosotros tenemos una proposición matemática $P(n)$ para la cual queremos comprobar que cualquier número natural $n$ la cumple, la técnica de demostración por inducción será útil porque en lugar de probar que cada número individualmente la cumple, bastará demostrar que se satisfacen las condiciones del principio de inducción para argumentar que todos los números naturales la cumplen.

Algoritmo de demostraciones por inducción

Supongamos tenemos una proposición en el conjunto de los números naturales $P(n)$. El segundo axioma de los conjuntos garantiza la existencia de un conjunto
$$S = \{n: P(n)\}$$.
Y el axioma 5 de Peano argumenta que si se cumplen las siguientes dos condiciones:

1. El $0$ pertenece al conjunto $S$
2. Si $n \in S$ entonces $n+1 \in X$

entonces $S = \mathbb{N}$. Es decir, todos los números naturales cumplen la condición $P(n)$
Veamos ahora estos dos pasos uno por uno:
1. Base inductiva: Probar que se cae la primera ficha. Este paso consistirá en demostrar que se cumple $P(0)$
2. Hipótesis de inducción: Suponer que un número $n$ cumple $P(n)$
3. Paso inductivo: Demostrar que la siguiente ficha se cae. En este paso debemos demostrar que se cumple también $P(n+1)$

Un ejemplo de inducción matemática

Proposición. La suma de los primeros $n$ números naturales es $\frac{n(n+1)}{2}$.

Esta proposición nos dice que si sumamos los primeros $n$ números n, el resultado será: $$ \sum_{i=0}^{n} i = 0+1+2+\dots+n-1+n = \frac{n(n+1)}{2}.$$ Para demostrar esto, seguiremos los pasos del algoritmo. Para ello, consideremos al conjunto $S=\{n \in \mathbb{N}: \sum_{i=0}^{n} i = \frac{n(n+1)}{2} \}$, es decir, $S$ es el conjunto de los números naturales $n$ para los cuales la suma de los primeros $n$ números naturales equivale a $ \frac{n(n+1)}{2} $. Lo que queremos demostrar es que este conjunto $S$ son todos los números naturales, es decir, que todos los números naturales cumplen esta condición. Para ello seguiremos los pasos del algoritmo.

Demostración. (por inducción sobre $n$).

Base inductiva. Demostraremos que $ \sum_{i=0}^{0} i = \frac{0(0+1)}{2} $. En efecto, notemos que $$ \sum_{i=0}^{0} i = 0= \frac{0(0+1)}{2} .$$ Así, ha quedado demostrada la base inductiva.

Hipótesis de inducción. Supongamos que $n \in \mathbb{N}$ es tal que $ \sum_{i=0}^{n} i = \frac{n(n+1)}{2} $.

Paso inductivo. Ahora demostraremos que $$ \sum_{i=0}^{n+1} i = \frac{(n+1)((n+1)+1)}{2}. $$ Para ello, basta notar que
$$\begin{align*}
\sum_{i=0}^{n+1} i &= \sum_{i=0}^{n} i + n+1 \\
&= \frac{n(n+1)}{2} + n+1 (\text{ esto por hipótesis de inducción}) \\
&= \frac{n(n+1)}{2} + \frac{2n+2}{2} \\
&= \frac{n(n+1)+2n+2}{2} \\
&= \frac{(n^2+n)+2n+2)}{2} \\
&= \frac{n^2+3n+2)}{2} \\
&= \frac{(n+1)(n+2)}{2} = \frac{(n+1)((n+1)+1)}{2} .
\end{align*}$$Quedando así demostrado el paso inductivo.

Así, hemos demostrado que el conjunto $S=\mathbb{N}$, es decir, que se cumple para todos los números naturales, quedando demostrada la proposición.

$\square$

Más adelante…

En la siguiente entrada daremos la definición de funciones recursivas que serán en pocas palabras, funciones en los números naturales las cuales son funciones que podemos definir solo diciendo cuánto valen en el $0$ y la evaluación en un término $\sigma(k)$ depende únicamente de la evaluación en $k$. También daremos un vistazo general al teorema de recursión.

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 la teoría vista.

Demuestra por inducción que la suma de los primeros $n$ números pares es $n(n+1)$.
Encuentra una fórmula para la suma de los primeros $n$ números impares usando el ejercicio anterior junto al ejemplo demostrado en la entrada.
Prueba que para cualquier número natural $n$, $$\sum_{i=1}^n(2i-1) = n^2 $$.

Entradas relacionadas

Ir a Álgebra Superior I
Entrada anterior del curso: Introducción a números naturales
Siguiente entrada del curso: Problemas de inducción

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

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

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

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:

$0 \in \mathbb{N}$
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:

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

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

$\emptyset \in X$
$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 curso¹.
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

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

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».

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 la teoría vista.

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

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

Álgebra Superior I: Funciones inyectivas, suprayectivas y biyectivas

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

Introducción

En la entrada anterior, hemos revisado la definición de las funciones matemáticas. Siguiendo con este tema, ahora vamos a estudiar tres tipos de funciones: las inyectivas, suprayectivas y finalmente las inyectivas. Hemos hablado anteriormente de las primeras dos, ahora estudiaremos algunas equivalencias de las definiciones vistas en un principio y algunos resultados interesantes.

Inyectividad entre funciones

Las definiciones que daremos al estar hablando de inyectividad y supreyactividad de funciones serán las mismas que dimos al hablar de los tipos de relaciones. Primero empezaremos hablando de la inyectividad.

Cuando estemos hablando de funciones, diremos que una función inyectiva es aquella que manda a elementos distintos en el dominio a elementos distintos en el contradominio.

Definición. Diremos que una función $f: X \rightarrow Y$ es inyectiva, si $f$ es una relación inyectiva. Es decir para cada elemento $y \in Im[f]$, existe un único $x$ tal que $(x,y) \in f$

Nota que esta es la definición de inyectividad que dimos anteriormente. El hecho de que $f$ sea una función, nos permitirá tener otra forma de ver la inyectividad, para darte cuenta de ello, observa la siguiente proposición:

Proposición. Sea $f: X \rightarrow Y$ una función. Entonces son equivalentes:

$f$ es inyectiva.
Para cualesquiera tres elementos $x,w \in X$ y $y \in Im[f]$ sucede que si $f(x) = y \land f(w) = y$ entonces $x=w$.

Demostración.

$1) \Rightarrow 2)$. Recordemos que una equivalencia de la inyectividad en relaciones es que si $(x,y) \in f$ y $(w,y) \in R$ entonces $x=w$. Usaremos esta equivalencia para nuestra demostración. Ahora nota que si $f(x)=y$ y $f(w)=y$ entonces $(x,f(x)) \in f$ y $(w,f(w)) \in f$. Como $f$ es inyectiva entonces $x=w$.

$2) \Rightarrow 1)$.Sean $(x,y) \in f$ y $(w,y) \in f$. Para demostrar el inciso, bastará demsotrar que $x=w$, para ello note que como $f$ es una función entonces $(x,y) = (x,f(x))$ y $(w,y) =(w,f(w))$. Ahora notemos que $f(x)=f(w)$, por hipótesis, esto significa que $x=w$.

$\square$

Esta última equivalencia deja más claro que una función inyectiva es aquella que envía a elementos distintos en el dominio a elementos distintos en el contradominio.

Ejemplos de funciones inyectivas son:

La función $f:\mathbb{Z} \rightarrow \mathbb{Z}$ donde $f(x)=x+1$, esto es debido a que si $f(x)=f(w)$ entonces $x+1=w+1$, lo que implicaría que $x=w$.
La función $f:\{1,2,3\} \rightarrow \{a,b,c,d,e\}$ dada por: $f=\{(1,e),(2,b),(3,c)\}$.
La función identidad entre cualquier conjunto $X$, dada por $f: X \Rightarrow X $ donde $f(x)=x$.

Suprayectividad entre funciones

Siguiendo con la lista de conceptos a revisar hoy, nos encontramos nuevamente con la suprayectividad, el concepto en donde todo el contradominio de la función coincide con su imagen:

Definición. diremos que una función $f:X \rightarrow Y$ es suprayectiva si $f$ es una relación suprayectiva. Es decir, si para cada $y \in Y$, existe un $x \in X$ tal que $f(x)=y$

Esta última definición es una derivación de una equivalencia que mostramos con anterioridad. Puesto que decir que para cada $y \in Y$, existe un $x \in X$ tal que $f(x)=y$, es equivalente a decir que para cada elemento $y \in Y$, existe un elemento $x \in X$ tal que $(x,y) \in f$, basta con notar que $f(x)=y$ produce la equivalencia deseada.

Algunos ejemplos de funciones suprayectivas son:

La función identidad $f: X \rightarrow X$. Para ello, nota que para cada $y \in X$, sucede que $(y,f(y)) \in f$, por lo que es suprayectiva, pues $f(y)=y$.
Sea $X =\{0\}$, entonces la función $f: \mathbb{Z} \rightarrow X$ dada por $f(n)=0$ es una función suprayectiva.
La función proyección $f: \mathbb{Z}^2 \rightarrow \mathbb{Z}$ dada por $f((x,y)) = x$ es suprayectiva.

Funciones biyectivas

El último concepto que revisaremos será el de funciones biyectivas. Estas funciones serán importantes porque en pocas palabras podrán «trasladar» un conjunto a otro. Definiremos a estas funciones como aquellas que son inyectivas y suprayectivas al mismo tiempo.

Definición. Sea $f: X \rightarrow Y$ una función. Diremos que $f$ es biyectiva si es inyectiva y suprayectiva.

Si una función es inyectiva, entonces manda distintos elementos del dominio a distintos elementos del contradominio. Mientras que si es suprayectiva, entonces todo el contradominio tiene su correspondencia. Así que si una función es biyectiva, entonces todo elemento del contradominio vendrá de uno y solamente un elemento del dominio. Esto significa que una función biyectiva «transforma» un conjunto en otro. A cada elemento del dominio lo vuelve uno del contradominio.

Por ejemplo, considera la función $f: X \rightarrow Y$ donde $X=\{1,2,3\}$ y $Y=\{a,b,c\}$ donde $f = \{(1,a),(2,b),(3,c)\}$. Nota que la función va de un conjunto $X$ y «traduce» cada uno de sus elementos a un elemento del conjunto $Y$. Esta es una forma en que las biyecciones nos dan información de cómo «traducir» un conjunto en otro.

Ahora considera la función $f: \mathbb{Z} \rightarrow \mathbb{Z}$ dada por $f(n)=n+1$. Esta es una función biyectiva. Y «traduce» cada número a su sucesor.

Otro ejemplo sería la función $f: \mathbb{R} \rightarrow \mathbb{R}$ dada por $f(x)=2x$. Nota que lo que hace esta función es «alejar» puntos del origen. Mientras que $f(0)=0$, a todos los números positivos los «aleja» más del origen del lado derecho, y a los número negativos los «aleja» del origen por la izquierda. Así que esta función biyectiva se podría pensar como una liga que pegamos a la mitad y jalamos por ambos lados hasta que cada lado mida el doble de lo que medía antes. Esta es una forma en que pasamos de una liga normal a una liga estirada, si cada punto de la recta real, fuera un pedazo de la liga, entonces «traducimos» ese punto estirando la liga.

Con estos ejemplos, vimos como una función biyectiva es una traductora de puntos, mandando cada punto del dominio a uno del contradominio, y cada punto del dominio tiene su propia traducción en el contradominio sin que otro punto del dominio comparta su traducción.

Así es como hemos revisado los tres tipos de funciones principales que usarás en muchas áreas de las matemáticas. La inyectividad nos dice que a cada elemento de la imagen de una función solo le corresponde una del dominio. La supreyactividad nos dice que la imagen de una función es igual al contradominio de la función. Mientras que la biyectividad nos habla de traducciones, o formas de ver un conjunto reflejado en otro conjunto.

Más adelante…

En la siguiente entrada daremos el paso de hablar de una función a más de una función, y esto lo haremos componiendo funciones. En un principio se pueden pensar las composiciones como mandar un elemento de un conjunto a otro conjunto mediante una función y después mandar este elemento a otro conjunto mediante otra función. Verás que será útil las composiciones cuando estemos hablando de distintas funciones entre conjuntos.

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 la teoría vista.

Da un ejemplo de una función inyectiva pero no suprayectiva.
Sea $X$ un conjunto y $Y$ un subconjunto de $X$. La función inclusión está dada por $f: Y \rightarrow X$ donde $f(y)=y$.
1. Demuestra que la función inclusión es inyectiva.
2. Da condiciones necesarias para que la función inclusión sea biyectiva.
Considera la función $f: \mathbb{Z} \rightarrow \mathbb{Z}$ dada por $f(n) = an +b$. ¿Para qué valores $a,b$ la función es biyectiva?
Demuestra que una función $f: X \rightarrow Y$ es biyectiva si y solo si para cualquier subconjunto $A \subset X$ sucede que $f[X \setminus A] = Y \setminus f[A] $.

Entradas relacionadas

Ir a Álgebra Superior I
Entrada anterior del curso: Introducción a funciones
Siguiente entrada del curso: Problemas introductorios a funciones y funciones inyectivas, suprayectivas y biyectivas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

Álgebra Superior I: Introducción a funciones

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

Introducción

En esta entrada empezaremos a estudiar un tipo de relación muy específica, que son las funciones. Este concepto es fundamental en casi todas las áreas de las matemáticas, y aprender su uso será fundamental a partir de ahora.

La importancia de las funciones

Antes de empezar a hablar de las funciones, es importante que desde ahora entiendas que el concepto de la función es un concepto casi omnipresente en la tarea de estudiar las matemáticas. Para tener idea de la profundidad de esto, observa los siguientes ejemplos:

La base del cálculo son las funciones en una variable.
La base del cálculo en varias variables son las funciones de distintas variables.
En análisis se estudian las funciones entre espacios numéricos.
En probabilidad, se trabaja con las funciones entre espacios de probabilidad.
Las secuencias numéricas son funciones.
En álgebra moderna, el concepto de grupo es un tipo de función.
En topología muchas veces se estudian familias de funciones.

Los ejemplos podrían seguir y seguir, y es que nosotros al estudiar las matemáticas, es muy importante entender que la mayor parte de estudiarla será el analizar funciones.

La primera noción que daremos de lo que son las funciones son unas máquinas que reciben una entrada y devuelven una salida.

Un ejemplo de esto es una función que toma de entrada cualquier número entero y devuelve el número multiplicado por dos. Para traducir cómo escribiremos esto, recordemos que al principio hemos dicho que las funciones van a ser relaciones, entonces la forma en que definirimos esta función será con una pareja ordenada $(x,y)$. Como tenemos la idea de que las funciones son máquinas que reciben una entrada y arrojan una salida, entonces diremos que $x$ es la variable de entrada y $y$ la de salida. De manera que podemos representar a la función que toma cualquier número entero y devuelve el número multiplicado por dos, es de la siguiente manera: $$f = \{(x,y) \in \mathbb{Z}^2: y = 2x\} $$ En donde al mencionar que $y=2x$, estamos diciendo que la salida es dos veces la entrada.

Algunos de los elementos que pertenecen a la función son $$\{(0,0),(1,2),(-1,-2),(5,10),(-7,-14), \dots\}.$$

Cuando hablemos de funciones habrán dos cosas importantes que tendrá que cumplir la relación:

Deberemos de usar todo el dominio para crear la relación. Esto quiere decir que si estamos hablando de una función entre números enteros, entonces no importa de qué número entero estemos hablando, siempre podrá tener su correspondencia según la función. En nuestro ejemplo, nota que dijimos que la función toma «cualquier número entero», no estamos diciendo que solo toma algunos números enteros.
Cada elemento del dominio tendrá uno y solo un correspondiente del contradominio. Esto quiere decir que si $(x,y)$ pertenecen a la función, entonces no existe otra pareja distinta $(x,w)$ en la función. En nuestro ejemplo, nota que las parejas son de la forma $(x,2x)$, y esto implica que cada elemento del dominio solo aparece una vez, si no fuera así, habría dos elementos $(x,2x),(x,w)$ en la función en donde $2x \neq w$, lo cual es imposible, puesto que los elementos del contradominio son los elementos del dominio multiplicados por $2$, es decir $w = 2x$, generando una contradicción.

Estas serán las propiedades que le pediremos a una relación para ser función.

Definición. Sea $f$ una relación entre dos conjuntos $X,Y$. Diremos que $f$ es una función si cumple las siguientes propiedades:

$Dom(f) = X$
Si $(x,y) \in f$ y $(x,w) \in f$, entonces $y=w$.

Esta última propiedad quiere decir que solo existe una pareja que tenga a $x$ en el lugar de los elementos del dominio.

Como hemos dicho antes, una función será una correspondencia entre elementos de $X$ con elementos de $Y$ de manera que a cada elemento de $X$ le corresponderá uno y únicamente un elemento del contradominio.

Ejemplos de funciones

Algunos ejemplos de funciones son:

La función identidad. Esta función de un conjunto $X$ en sí mismo, es el conjunto $$\{(x,y) \in X^2:x=y\}.$$ Y son las parejas de la forma $(x,x)$.
Si $X = \{1,2,3\}, Y=\{a,b\}$, entonces $\{(1,a),(2,a),(3,b)\}$ es una función.
La función que corresponde a cada persona de la tierra con su cumpleaños, es una función.
La función proyección. Supongamos que tenemos dos conjuntos $X,Y$, la proyección es la función entre el producto cartesiano $X \times Y$ y el conjunto $X$ que asocia cada pareja ordenada $(x,y)$ con el primer elemento de la pareja $x$. Esto quiere decir que la función «se olvida» del elemento $y$. De esta forma, $f$ toma elementos del producto $X \times Y$ y su contradominio es el conjunto $X$ que manda cada pareja ordenada a su proyección sobre la primer entrada, esto quiere decir que $f((x,y)) = x$. Así, observa que los elementos de esta función son de la forma $((x,y),x).$ Esta es una función que se utiliza en áreas como la geometría analítica, cuando se tiene el plano cartesiano y se define la proyección de un vector sobre algún eje o incluso sobre la dirección de otro vector.

Un ejemplo de una relación que no es función es la función entre $X = \{1,2,3\}$ y $Y=\{a,b\}$, donde la relación es $\{(1,a),(2,a),(1,b)\}$. Esto es por dos razones: Se utiliza más de una vez el elemento del dominio $1$, aparecen las parejas $(1,a),(1,b)$, pero no es cierto que $a=b$, además nota que no se utiliza el elemento $3$ del dominio, por lo que se rompen las dos condiciones que pedimos para que fuera función.

Más sobre funciones

Al momento de estar hablando de una función $f$ entre dos conjuntos $X$ y $Y$ , es común hacer uso de la notación $f:X \rightarrow Y$ que se lee como «$f$ es una función que va de $X$ a $Y$». Y si $x \in X$, al único elemento $y$ tal que $(x,y) \in f$, lo podremos denotar por $f(x)$ de manera que las parejas serán de la forma $(x,f(x))$.

A continuación definiremos algunos conceptos que usaremos al hablar de funciones.

Definición. Diremos que dos funciones $f: X \rightarrow Y$ y $g: W \rightarrow Z$ son iguales si las relaciones son la misma, es decir si $X=W$ y $Y=Z$ y para cada elemento $x \in X$, $f(x)=g(x)$.

Esto nos quiere decir que si dos funciones son iguales, entonces mandan a todo elemento $x$ al mismo elemento en el contradominio.

Con esto, hemos cubierto la noción de las funciones. Lo importante que recuerdes ahora es que las funciones son un tipo de relación que usan todo el contradominio y que mandan cualquier elemento del dominio a uno y solamente un elemento del contradominio. Verás que conforme avances en distintas ramas de la matemática, serán muy importante saber qué son las funciones.

Más adelante…

Hasta ahora hemos hablado únicamente de la definición de las funciones y cuándo dos funciones son iguales. En las siguiente entrada platicaremos acerca de las funciones inyectivas, suprayectivas y biyectivas. Que si recuerdas los términos, alguna vez definimos los dos primeros en el contexto de relaciones. Volveremos a explorar estos términos pero ahora desde el punto de vista de las funciones.

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 la teoría vista.

Demuestra que la relación «ser menor o igual» en los números enteros no es una función.
Dado cualquier conjunto $X$ no vacío, ¿Cuál es la única función que es relación de equivalencia?
Demuestra que no existe ninguna función $f:X \rightarrow \emptyset$ .
Sean $f: \mathbb{Z} \rightarrow \mathbb{Z}$ y $g: \mathbb{Z} \rightarrow \mathbb{Z}$. Definamos $f(x) = x ^2$ y $g(x) = (x+1)(x-1)+1$. Demuestra que $f=g$.

Entradas relacionadas

Ir a Álgebra Superior I
Entrada anterior del curso: Problemas de órdenes parciales y relaciones de equivalencia
Siguiente entrada del curso: Funciones inyectivas, suprayectivas y biyectivas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»