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: Varios tamaños de conjuntos infinitos

Por Guillermo Oswaldo Cota Martínez

Introducción

En la entrada pasada revisamos el concepto de cardinalidad de conjuntos finitos. Esto es la forma de «contar» los elementos en un conjunto que sabemos que «termina». Ahora veremos un primer acercamiento a la idea del infinito en el aspecto matemático,

Pensando en número grandes

¿Cuál es el número más grande que se te ocurre? Siempre que pienses en alguno, existe uno más grande, pues con solo sumarle a cualquier número $1$, resulta en uno más grande. Y es que en el caso finito, hablábamos de cómo un conjunto tenía un número definido de elementos. Ahora cuando estemos hablando de infinito, lo primero que se nos vendría a la mente es que no podremos «contar» cuántos elementos hay y acabar, pues siempre habrán más y más elementos. Así haremos el intento por primero definir una forma qué es el infinito.

Definición Diremos que un conjunto es infinito si no es finito, es decir, un conjunto $X$ será infinito si no existe algún $n$ número natural tal que sea biyectivo con $X$.

Para ver un ejemplo de esto, veremos los números naturales.

Proposición. Los números naturales son infinitos.

Demostración. Deberemos mostrar que para cualquier número $n$ y cualquier función $f:\mathbb{N} \rightarrow n$, no será biyectiva. Pero esto es resultado inmediato del principio de las casillas, pues $\{1,2,3,…,n,n+1\}$ es un subconjunto de $\mathbb{N}$ que tiene cardinalidad $|n+1|$ por lo tanto la función restringida solo a este conjunto no es inyectiva, y como este solo es un subconjunto de los números naturales, la función tampoco será inyectiva.

Como esto sucede para cualquier $f$ y cualquier $n$, no existirá una biyección entre $\mathbb{N}$ y algún número natural.

$\square$

Este es un conjunto infinito que es muy intuitivo, pues maneja la idea de que siempre podemos seguir pensando en números nuevos. Pero incluso este conjunto tiene subconjuntos infinitos, por ejemplo los números pares positivos (escrito en ocasiones como $2\mathbb{Z_+}$) y números impares positivos (escrito en ocasiones como $2\mathbb{Z_+}+1$), pues estos también son infinitos. Por ahora no te preocupes por la definición de $\mathbb{Z_+}$, pues simplemente nos estamos refiriendo a los números naturales, solo es convención escribir a los pares e impares en estos términos y en cursos siguientes tendrás más tiempo en ahondar en su significado.

Ahora para empezar a «comparar» los conjuntos infinitos, necesitaremos una definición de cuándo dos conjuntos tienen la misma cardinalidad infinita, y esta la definiremos muy similar a como lo hicimos en el caso finito.

Definición. Sean $X$ y $Y$ dos conjuntos. Diremos que tienen la misma cardinalidad si existe una biyección entre ellos y lo escribiremos como $|X|=|Y|$.

Verás que esa es una de las definiciones que manejamos en la entrada anterior. La única diferencia es que en el caso finito siempre decíamos que eran de cardinalidad $n$. Pero ahora como ya no manejamos el concepto en término de números naturales, por ahora solo lo escribiremos como en la definición.

Proposición $|\mathbb{N}| = |2\mathbb{Z_+}|$

Demostración. Para demostrar que estos dos conjuntos tienen la misma cardinalidad, deberemos de dar una biyección entre ellos. Propongamos la función $f: \mathbb{N} \rightarrow \mathbb{2Z_+}$ dada por $f(n)=2n$.

Es inyectiva pues si $n,m$ son números naturales distintos, alguno de los dos es mayor al otro, digamos que $n = m+k$ donde $k$ es un número natural distinto al cero. Entonces es claro que $f(n) = 2n = 2m+2k$ mientras que $f(m) = 2m$. Como $k$ no es cero, entonces $2m+2k \neq 2m$, por lo tanto es inyectica.

Además es suprayectiva, pues cualquier número par $m$ es de la forma «$2$ multiplicado por otro número». Es decir, $m$ es de la forma $2n$ para algún número $n$. Así, $f(n)=2n = m$.

Por lo tanto, la función es biyectiva.

$\square$

Así, hemos demostrado que «existe» la misma cantidad de número pares positivos que de números. Así que sin importar que nos hayamos «saltado» números, siguen teniendo la misma cantidad de números. De manera similar podemos demostrar que existe la misma cantidad de números impares positivos. Esto es posible considerando la función $f(n) = 2n+1$. Además también podríamos dar una biyección entre números pares e impares con la función $f(n)=n-1$. Es decir, los tres conjuntos comparten cardinalidad.

Otros ejemplos de conjuntos con esta cardinalidad son:

  • El conjunto de los números enteros.
  • El conjunto de los números racionales.
  • $\mathbb{N} \times \mathbb{N}$
  • $\mathbb{N} \times \mathbb{N} \times … \times \mathbb{N}$

Este aspecto de el infinito llamó mucho la atención de los matemáticos del siglo XX, pero hubo uno en particular que desarrolló la teoría de los conjuntos y de paso formalizó el concepto del infinito y de distintos tamaños de infinitos. Uno de los aspectos que más sorprenden a las personas ajenas a la materia es este hecho, que existan distintos infinitos, y en pocos renglones daremos introducción a uno que ya conoces. Para poder distinguir este tipo de infinitos uno del otro, usó una clase especial de números a los que llamó transfinitos.

El primer número transfinito es el aleph $0$, escrito como $\aleph_0$. Y este representa la cardinalidad de los números naturales, es decir $$ |\mathbb{N}| = \aleph_0.$$ Que es la misma cardinalidad que los números pares, impares, e incluso los números primos.

El segundo número transfinito se define como aleph $1$, y a este lo escribimos como $\aleph_1$, este se define como el transfinito inmediatamente superior a $\aleph_0$. La propiedad de este número transfinito es que es estrictamente mayor a $\aleph_0$, lo que quiere decir que cualquier conjunto con esta cardinalidad no será biyectable con alguno que tenga cardinalidad aleph $0$.

Cuando dos conjuntos tengan distinta cardinalidad, lo escribiremos como $|X| \neq |Y|$ mientras que cuado sepamos que hay una función inyectiva de $X$ a $Y$ lo escribiremos como $|X|\leq |Y|$ mientras que si sabemos que hay una inyección pero no biyección entre los conjuntos lo escribiremos como $|X|<|Y|$. Con esto en mente, lo que se plantea con los alephs, es que $\aleph_0 < \aleph_1$. Sin embargo aún nos falta una herramienta más e hipótesis para pensar en este último.

Para hacerlo, será necesario el siguiente teorema que no probaremos en este curso:

Teorema (de Cantor). Sea $X$ un conjunto, entonces $|X|<|P(X)|$.

Con este teorema es que podemos hacer muchos conjuntos infinitos como por ejemplo la potencia de los naturales, pues $|\mathbb{N}|<|P(\mathbb{N})|$. De hecho al transfinito $|P(\mathbb{N})|$ en las matemáticas se ha propuesto la idea de que si $P(\mathbb{N})$ es el transfinito inmediatamente siguiente de $\aleph_0$, pues cae dentro de un área de las matemáticas en donde la teoría se vuelve inconsistente si se supone que sí pero también es inconsistente si se supone que no, por ahora se trata como una hipótesis el usarla o no usarla para llegar a distintos resultados matemáticos.

Hipótesis del continuo. $\aleph_1 = 2^{\aleph_0}$

Como mencionamos, esto no tiene una prueba y se supone o no según sea el caso de uso. Bajo esa suposición, podríamos considerar a $P(\mathbb{N})$ como un conjunto con cardinalidad $\aleph_1$. Más aún, otros conjuntos que tienen esta cardinalidad bajo esta hipótesis son:

  • El conjunto generado por puras secuencias de $1$ y $0$, como por ejemplo $00000…..$, $111111….$, $1010101….$, etc. es decir secuencias infinitas de números solo formadas de $0$ y $1$.
  • El conjunto de todos los números del 0 al 1.
  • El conjunto de números reales.
  • El producto cartesiano de los números reales consigo mismo, es decir $\mathbb{R}^2$.

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.

  1. Demuestra que $|\mathbb{N}| = |2\mathbb{Z_+}+1|$.
  2. Demuestra que el conjunto generado por puras secuencias de $1$ y $0$ tiene la misma cardinalidad que $|P(\mathbb{N})|$.
  3. Da un ejemplo de una función entre conjuntos infinitos cuya imagen no sea infinita.
  4. Encuentra la cardinalidad de la imagen de la función $f: \mathbb{N} \rightarrow \mathbb{N}$ dada por $f(n) = 5m + 3$

Más adelante…

Una vez que hemos hablado de la cardinalidad de los conjuntos, podemos seguir hablando de los números naturales, de sus propiedades y la inducción. Después volveremos a encontrarnos la idea de contar conjuntos específicos y de técnicas para encontrar la cardinalidad de conjuntos finitos de algunos conjuntos.

Entradas relacionadas

Álgebra Superior I: Cardinalidad de conjuntos finitos

Por Guillermo Oswaldo Cota Martínez

Introducción

¿Qué es lo que entiendes cuando alguien te dice: «En esta canasta hay cinco manzanas»? Probablemente te llegue a la mente una imagen similar a la siguiente:

Y es que para nosotros es muy natural el decir «cuántas» cosas hay dentro de un conjunto. De hecho los primeros usos que dieron lugar al nacimiento de las matemáticas datan de hace más de $5000$ años en mesopotamia con los primeros sistemas para contar. Esto remarca la necesidad de contar objetos que a su vez trata de diferenciar unos de otros.

Imagínate que te pidieran contar cuántos Pingüinos Rey hay en un zoológico. Para ello primero habría que saber distinguir a cuáles son este tipo de pingüinos y cuáles no. En un principio puede resultar fácil, y es que veremos que el distinguir elementos unos de otros puede llegar a complicarse cuando más consideraciones hacemos como el saber cuántos pingüinos hay que sean machos, o cuántos machos hay que no tengan más de un año, por ejemplo. Con este tipo de ejercicios los matemáticos fueron descubriendo con el tiempo que hacía falta poder estudiar un poco más a detalles este concepto de «diferenciar» y «contar» elementos de un conjunto. En las siguientes entradas vamos a desarrollar un poco más este concepto de diferenciar y contar.

Cardinalidad de un conjunto

Como todo en matemáticas, necesitaríamos hacer una definición de lo que significa que «un conjunto tenga $3$ elementos» y cómo es diferente a «un conjunto con $5$ elementos», por poner un ejemplo. Es con esto que damos la siguiente definición entre cardinalidad de un conjunto finito.

Definición. Sea $X$ un conjunto. Diremos que $X$ tiene cardinalidad finita o es finito si existe $n \in \mathbb{N}$ y una función biyectiva entre $X$ y $n$. En este caso escribiremos $|X|=n$.

Detengámonos un poco a analizar esta definición.

Recordemos que por ejemplo el número $2$ es escrito como conjunto como
$$ \{\emptyset,\{\emptyset\}\}$$

Ahora pensemos en un conjunto con un plátano y una manazana. Entonces podemos definir la siguiente función $f: X \rightarrow \mathbb{N}$ como $f(manzana)= \emptyset$ y $f(plátano)=\{\emptyset\}$:

Puedes comprobar que esta función es biyectiva, y es solo una forma de biyectar el conjunto $X$ con el $2$. Dicho esto, entonces podemos decir que $|X|=2$. Ahora ¿Qué pasa con un conjunto que también tenga cardinalidad $2$? Digamos el conjunto $Y$ de un perro y un gato.

Entonces podríamos decir que igual puede haber una biyección entre los dos conjuntos $X$ y $Y$.

Ahora ¿Qué pasa si unimos los conjuntos de animales con los de ls frutas? Pues nuestra razón nos dirá que si en un conjunto tenemos dos elementos y en el otro dos, si los combinamos tendremos cuatro elementos, y esto es justamente otra de las bondades de la cardinalidad, pues se comporta de acuerdo a lo que nuestra razón nos dice.

Proposición Sean $X,Y$ dos conjuntos disjuntos. Si $|X|=n, |Y|=m$ entonces $|X \cup Y| = n+m$.

Demostración. Por definición de cardinalidad, existen dos funciones $g:X \rightarrow n$ y $f: Y \rightarrow m$ biyectivas. Notemos ahora que la función $h: X \cup Y \rightarrow n+m $ dada por $$h(x) = \begin{cases} &f(x), x \in X \\ g(x) + n, x \in Y \end{cases} $$ es biyectiva. Para demostrar que esta función es biyectiva, demostraremos la inyectividad y suprayectividad.

Es inyectiva. Considera dos elementos $x,y$ distintos. Existen tres casos, el primero es que $x,y \in X$, en este caso, $h(x)=f(x), h(y)=f(y)$ y como $f$ es inyectiva, sus imágenes son distintas.
El segundo caso es $x , y \in Y$. En este caso, recordemos que $h(x)=n+g(x)$ y $h(y) = n + g(y)$ Si las imágenes fueran iguales entonces $g(x)=g(y)$ pero esto solo sucede si $x=y$, pues $g$ es inyectiva, y esto contradiciendo la hipótesis de que los elementos son distintos.
Finalmente en el caso de que un elemento pertenezca a $X$, digamos $x$ y el otro a $Y$, digamos $y$, sucede que $h(x)=f(x)$, mientras que $h(y)=n+g(y)$, ahora notemos que $f: X \rightarrow n$, entonces ningún elemento es más grande que $n$, mientras que $h(y)$ sí es más grande que $n$, pues estamos uniendo números naturales al más grande número natural que compone al conjunto $X$, es decir, siempre sucederá que $h(x)<h(y)$ y en particular $h(x) \neq h(y)$, siendo la función inyectiva.

Además la función es suprayectiva, ya que para cualquier elemento $k \in n+m$ se tienen dos casos: Si $k <= n$ entonces existe $x \in X$ tal que $h(x)=f(x)=k$, mientras que si$k>n$ existe $l \in. \mathbb{N}$ tal que $n+l=k$. Por otro lado, como $g$ es suprayectiva, existe $y \in Y$ tal que $g(y)=l$. Así $h(y)=n+g(y)=n+l=k$. Por lo tanto la función es biyetiva.

Y más aún, hemos demostrado que los conjuntos disjuntos tienen cardinalidad $n+m$.

$\square$

El principio de las casillas

Una de las propiedades más importantes sobre cardinalidad que es intuitiva es la siguiente:

Proposición. (El principio de las casillas). Sean $X,Y$ dos conjuntos tales que $|X|=s(n)$ y $|Y|=n$. Entonces si $f:X \rightarrow Y$, $f$ no es inyectiva.

A esta se le llama principio de las casillas o de los palomares y se explica con el siguiente ejemplo:

Supón tienes $9$ casillas para palomas:

Naturalmente, solo cabrá a lo más una paloma en cada una de las casillas, entonces si lega al menos una paloma más, forzosamente tendría que haber más de una paloma en alguna de las casillas. En general para $n$ casillas, caben a lo más $n$ paloma para que quede solo una paloma en cada casilla. Es decir, podríamos hacer una inyección entre el número de palomas y el de casillas siempre y cuando haya menos palomas que casillas.

Demostración. Para ello deberíamos mostrar que no existe una inyección entre un conjunto de $n$ elementos y otro de $s(n)$.

Base de inducción. Sea $|X|=s(0)$ y $|Y|=0$. Notemos entonces que $Y$ tiene que ser el vacío, pues $0$ es el vacío y si $Y$ no fuera vacío, entonces existiría una función $f$ y un elemento $y \in Y$ tal que $f(y) \in \emptyset$. Lo cual es una contradicción. Ahora notemos que por vacuidad el enunciado se cumple, pues de no ser así, existiría una función $g:X \rightarrow Y$ inyectiva, pero esto supondría que $Im[g] \subset \emptyset$ tiene al menos un elemento.

Hipótesis de inducción. Ahora supongamos que para cualesquiera dos conjuntos $|X|=s(n)$ y $|Y|=n$ se cumple la condición.

Paso inductivo. Consideremos ahora dos conjuntos $X,Y$ con $|X|=s(s(n))$ y $|Y|=s(n)$. Ahora consideremos cualquier función $f: X \rightarrow Y$, bastará probar que esta función no es inyectiva. Para ello, notemos que si le quitamos cualquier elemento $x \in X$ a $X$, su cardinalidad será $s(n)$. Además si quitamos el elemento $y \in Y$ tal que $f(x)=y$ entonces $Y$ tiene cardinalidad $n$. Así volvemos al caso de la hipótesis de inducción donde la función $f’: X/\{x\} \rightarrow Y/{y}$ definida como $f'(x)=f(x)$ no es inyectiva, esto significa que existen dos elementos $y,z \in X/\{x\}$ tales que $f'(x)=f'(y)$. Más aún, la función $f$ tampoco es inyectiva por la existencia de estos dos elementos.

Así hemos demostrado el principio de las casillas

$\square$

La cardinalidad de dos conjuntos

Una definición ahora sobre la cardinalidad de dos conjuntos es consecuencia de

Definición Dos conjuntos $X$ y $Y$ tienen la misma cardinalidad si existe una función biyectiva $f: X \rightarrow Y$ y lo escribiremos como $|X|=|Y|$

Y ahora veamos cómo es que en el caso finito, esta es una definición que no contradice la primera definición que dimos

Proposición En el caso finito, Son equivalentes para cualesquiera dos conjuntos finitos $X,Y$ y cualquier número natural $n$:

  1. $|X| = n \land |Y| = n$
  2. $|X| = |Y|$

Demostración.

$\Rightarrow$

Supongamos primero que $|X| = n$ y $|Y|=n$. Ahora, notemos que existen dos funciones biyectivas $f: X \rightarrow n$ y $g: Y \rightarrow n$ Ahora consideremos la siguiente función $g^{-1} \circ f : X \rightarrow Y$. Y notemos que es una biyección, pues como $g$ es biyectiva, en particular es suprayectiva y eso significa que $Im[g] = n$ Siendo entonces la función $g{-1}: Im[g] =n \rightarrow Y$ con el mismo dominio que el contradominio de $f$, es decir la composición es una función bien definida. Además como $f$ también es biyectiva, entonces $g^{-1} \circ f$ también es biyectiva.

$\Leftarrow$

Demostremos ahora por contradicción que $|X| = n \land |Y| = n$ cuando $|X|=|Y|$.

Para ello supongamos primero que existen dos naturales distintos $n,m$ tales que $|X|=n$ y $|Y|=m $, y esto es posible pues $X,Y$ son finitos. Y también $|X|=|Y|$ Ahora sin perdida de la generalidad supongamos que $n>m$. Pero esto es una contradicción al principio de las casillas, pues toda función de $X$ a $Y$ no sería inyectiva, y en general tampoco será biyectiva. Cumpliéndose así la condición deseada.

$\square$

Algunas propiedades más de la cardinalidad

Veamos ahora otras propiedades sobre las cardinalidades de los conjuntos. Para ello supón que $X$ es finito de cardinalidad $n$ y $Y$ es finito de cardinalidad $m$.

  • Proposición. $|X /Y| = |X| – |X \cap Y|$
    Demostración. Esto es consecuencia del hecho de que $X/Y$ y $X \cap Y$ son conjuntos disjuntos, entonces:
    $$ |X/Y| + |X \cap Y| = |X/Y \cup (X \cap Y)| = |X|$$

$\square$

  • Proposición. $|X \cup Y| = |X| + |Y| – |X \cap Y|$
    Demostración. Por el inciso anterior, sabemos que $$ |X \cup Y| = |X/Y \cup Y| = |X|- |X \cap Y| + |Y|$$

$\square$

  • Proposición. $|P({X)|=2^{|X|}$
    Demostración. Por inducción sobre el número de elementos en el conjunto $X$.
    Base de inducción. Si $X$ tiene $0$ elementos, entonces es el vacío, mientras que $P(X)={\emptyset}$ el cuál tiene cardinalidad $1=2^{0}$.
    Hipótesis de inducción. Ahora supongamos que si $|X|=n$ para algún número $n$ natural, entonces $|P(X)|=2^{n}$.
    Paso inductivo. Sea $|X|=n+1$. Consideremos ahora un elemento $x$ de $X$ y notemos que el conjunto $X/\{x\}$ es un conjunto con $n$ elementos, por lo cual sabemos que $|P(X/\{x\})|=2^n$. Ahora veamos que este conjunto describe todos los posibles subconjuntos de $X$ en los que $x$ no está incluído, por lo que si definimos el conjunto $P(X/\{x\}) \cup x := {A \cup x : A \in P(X/\{x\})}$, se tiene que $$(P(X/\{x\}) \cup x) \cup P(X/\{x\}) = P(X) $$ Pues el primer conjunto son todos los subconjuntos de $X$ que sí tienen a $x$ y el segundo aquellos que no. Como estos dos son conjuntos disjuntos y tienen exactamente $n$ elementos, entonces $$|P(X)| = |(P(X/\{x\}) \cup x) \cup P(X/\{x\})| = 2^n + 2^n = 2^{n+1}$$

$\square$

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.

  1. Demuestra que $(P(X/\{x\}) \cup x) \cup P(X/\{x\}) = P(X)$
  2. Demuestra que $|X|=|Y|$ si y solo si $|Y|=|X|$
  3. Demuestra que la relación «tener la misma cardinalidad» es de equivalencia.
  4. ¿Cuál es la cardinalidad de |X \cup Y \cup Z|?

Más adelante…

Ahora que hemos introducido el concepto de cardinalidad, veremos cómo es que podemos escalar este concepto del caso finito al caso infinito. Es decir ¿Qué pasa cuando ya no podemos hablar de conjuntos que podemos «contar»?

Entradas relacionadas

Álgebra Superior I: Suma y producto de naturales y sus propiedades

Por Guillermo Oswaldo Cota Martínez

Introducción

La función suma

Usaremos el teorema de recursión que revisamos en la entrada pasada para definir la función suma entre números naturales.

Primero, recordemos qué nos menciona este teorema:

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)).$

Ahora, definamos la función suma como sigue: La función sumar $n$ unidades a un número estará dada por $s_n:\mathbb{N} \rightarrow \mathbb{N} $ dada por:

  • $s_n(0) = n$
  • $s_n(\sigma(m)) = \sigma(s_n(m))$

Notación: Para cada par de números naturales $n,m$, escribiremos $$s_n(m) = n+m. $$
Y por el teorema de recursión, esta es una función bien definida. Ahora veamos cuál es esta función. La primera condición nos dice que la función evaluada en el $0$ es $n$. Ahora veamos cómo es que esta función se define para los siguientes números, nota que si aplicamos la segunda condición, obtenemos que $$s_n(\sigma(0)) = \sigma(s_n(0)).$$ Recordando cómo definimos la función sucesora, sustituimos $\sigma(0)$ por $1$ para obtener que $$s_n(1) = \sigma(s_n(0)) = \sigma(n).$$ De tal manera que $$s_n(1) = n+1 .$$ De manera similar se puede comprobar que $$s_n(2)=n+2 .$$ Y de manera recursiva, podemos demostrar que $$\begin{align*}
s_n(3) &= n+3 \\
s_n(4) &= n+4 \\
s_n(5) &= n+5 \\
&\vdots \\
s_n(m) &= n+m \\
&\vdots
\end{align*}$$ Como podrás observar, la función $s_n$ corresponde a sumarle a un número $n$ unidades. Formalmente así es como se defina la suma entre dos números. Veamos a continuación algunas propiedades de la suma. Como dato adicional, nota que para todo número natural $n$, $s_n(1)=\sigma(n)$

Propiedades de la suma

Proposición. La suma es asociativa, esto quiere decir, para $n,m,k \in \mathbb{N}$ se cumple que: $$ s_n(s_m(k)) = s_{n+m}(k) .$$
Demostración. Sean $n,m,k \in \mathbb{N}$. Lo que queremos demostrar es que $$n+(m+k) = (n+m)+k.$$ Para ello, nota que bastará probar que $s_n \circ s_m = s_{n+m}$. Para ello notemos que

  1. $s_n(s_m(0)) = s_n(m) = m+n$
  2. $s_n(s_m(\sigma(k))) = s_n(\sigma(s_m(k))) = \sigma(s_n(s_m(k)))$

Por otro lado, por definición de la suma:

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

Esto quiere decir que tanto $s_n \circ s_m$ como $s_{n+m}$ cumplen las dos condiciones del teorema de recursión, y este nos asegura que $$s_{n+m} = s_n \circ s_m$$ pues el teorema asegura que la función que cumple dichas dos condiciones es única.

$\square$

Proposición. La suma es conmutativa. Es decir, para $n,m,k \in \mathbb{N}$ se cumple que: $$s_n(m) = s_m(n).$$

Demostración. Sea $n \in \mathbb{N}$ . Haremos la demostración por inducción sobre $m$.
Base inductiva. Notemos que $s_n(0) = n$. Por otro lado, se puede demostrar sin mucha dificultad que $s_0(n) = n$ (se deja como tarea moral la demostración de este enunciado). De esta manera $$s_n(0) = s_0(m). $$

Hipótesis de inducción. Supongamos que $m \in \mathbb{N}$ es tal que $$s_n(m) = s_m(n). $$

Paso inductivo. Ahora demostraremos que $$s_n(\sigma(m)) = s_{\sigma(m)}(n). $$Para ello notemos que $$s_n(\sigma(m)) = \sigma(s_n(m))$$Ahora, aplicando la hipótesis de inducción, tenemos que $$\sigma(s_n(m)) = \sigma(s_m(n)). $$ Ahora, nota que $$ \begin{align*}
\sigma(s_m(n)) &= s_m(\sigma(n)) \\

& = s_m(s_1(n))\\

&= s_{m+1}(n) \\

&= s_{\sigma(m)}(n)
\end{align*}$$

Estas últimas dos igualdades son válidas debido a la asociatividad de la suma. Es una vez concluido esto último que podemos seguir la cadena de igualdades. Esto resulta en que $s_n(\sigma(m)) = s_{\sigma(m)}(n). $ Como se quería demostrar.

$\square$

La multiplicación

Cuando apenas estamos aprendiendo a sumar, alguna vez nos encontramos con una abreviación de sumar los mismos términos. Por ejemplo, nos dicen que si tenemos tres grupos de perros, cada uno con cinco perros, entonces podríamos contar el número total de perros con la siguiente expresión:

$5+5+5$

$3$ grupos de perros con $5$ perros cada uno

Quizá no es tan tardado en escribir $5+5+5$, y llegaríamos a la conclusión de que hay $15$ perros en total. Pero ahora ¿Qué pasaría si tenemos trescientos grupos de perros con cinco perros cada uno? Pues la notación se complica, pues para escribirlo, deberíamos anotar $5+5\underbrace{+\dots+}_{296 \text{ veces}}5+5$, es decir, sumar $5$ unas $300$ veces.

$300$ grupos de perros con $5$ perros cada uno

Es por esto que se llega a la noción de multiplicación, pues al considerar la primera suma, bien podemos escribir: $$5+5+5 = 3 \times 5.$$ Y la segunda suma: $$5+5\underbrace{+\dots+}_{296 \text{ veces}}5+5 = 300 \times 5 .$$

Ahora, nota que la primera suma se puede expresar como $$(5+5)+5 = (2 \times 5) + 5 $$ De manera que sabemos que $$3 \times 5 = (s(1) \times 5) + 5 $$

De igual forma $$(s(298)\times 5) + 5 = 300 \times 5$$ Eso generalizando a cualquier número $n \in \mathbb{N}$ lo escribiríamos como $$s(n) \times 5 = (n \times 5) + 5 $$ Y para cualquier número $m \in \mathbb{N}$: $$s(n) \times m = (n \times m) + m $$

Definición de la multiplicación

Sean $n, m \in \mathbb{N}$, la multiplicación entre números naturales la definiremos como la función $\times : \mathbb{N} \rightarrow \mathbb{N}$ tal que:

$$\begin{align*}
0 &\times n = 0 \\
s(n) &\times m = (n \times m) + m
\end{align*} $$

Nota que esta es una definición recursiva, pues la definición de la multiplicación del sucesor de un elemento depende de la multiplicación del mismo elemento.

Usando el hecho de que sabemos que la multiplicación con el $0$ siempre es $0$, podemos obtener una propiedad interesante al ver qué pasa cuando multiplicamos cualquier elemento con el $1$, pues resultará que la multiplicación se comportará como la identidad cuando multiplicamos con el $1$.

Proposición. Para cualquier número natural $m$, $1 \times m = m$.

Demostración. Notemos que por definición $$0 \times m = 0$$, de manera que $$1 \times m = s(0) \times m $$

A su vez, podemos usar la otra propiedad de la multiplicación para sustituir el término $s(0)$: $$s(0) \times m = (0 \times m)+m=m $$ Llegando así al resultado deseado.

$\square$

Otra proposición interesante es que esta operación es conmutativa, y es algo que sabemos por sentido común, pues podríamos escribir que $$3 \times 5 = 5 +5+5 = 15=3+3+3+3+3=5\times 3 $$ Nuestro sentido común nos lo dice, sin embargo para demostrar esto, deberemos usar inducción matemática.

Proposición. La multiplicación de números naturales es conmutativa.

Demostración. Para esto notemos que podemos definir la multiplicación de cada número natural $m$ en términos de el teorema débil de recursividad como:
$$\begin{cases}
f_m(0) &= 0\\
f_m(n+1) &= m \times n + m
\end{cases}
$$
Ahora definamos la función $g_m(n) = n \times m$ y veamos que es la misma que $f$.
Notemos que cualquier suma de $0$ consigo misma es $0$, haciendo que $g_m(0)=0$ esto se puede demostrar por inducción y resulta una tarea que puede poner en práctica tus habilidades para este tipo de demostraciones.

Notemos que adicionalmente:
$$\begin{align*}
g_m(n+1) &= (n+1) \times m\\
&= (n \times m) + m \\
&= g_m(n)+m
\end{align*} $$
Demostrando que $g_m$ también cumple la definición de $f_m$. Como el teorema de recursión débil nos garantiza que $f_m$ es única, entonces $g_m=f_m$, esto quiere decir que $m \times n = n \times m$.

Como esto sucede para cualquier número natural $m$, entonces es cierta la siguiente afirmación: «$\forall m,n \in \mathbb{N}, m\times n = n \times m$»

$\square$

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.

  1. Demuestra que para todo número natural $n$, $s_n(1)=\sigma(n)$.
  2. Demuestra que para todo número natural $n$, $s_0(n)=n$.
  3. Demuestra que la multiplicación es asociativa.
  4. Demuestra que $0 \times n = n \times 0$.

Más adelante…

Ahora que hemos visto la suma y multiplicación de los números naturales, hablaremos un poco más de los conjuntos y su relación con los números naturales introduciendo «el tamaño de los conjuntos» o «cardinalidad»

Entradas relacionadas

Álgebra Superior I: Funciones invertibles

Por Guillermo Oswaldo Cota Martínez

Introducción

Anteriormente vimos el concepto de composición entre funciones, que nos permiten saltar entre varios conjuntos de manera sencilla, revisamos algunas de sus propiedades y dimos algunos ejemplos. Ahora nos toca profundizar un poco más en la composición de funciones analizando un caso particular de funciones: las invertibles. Que en términos simples nos permiten deshacer los efectos de las operaciones

Revirtiendo las cosas.

Pensemos por un momento en un cubo rubik, hay distintas técnicas para armarlo, pero por ahora nos enfocaremos en sus movimientos. La forma en que se usa el cubo, es moviendo sus caras hasta que todas las caras tengan un solo color. Imagina que tienes un cubo en tus manos, si mueves la cara que está hasta arriba, tienes dos formas de hacerlo, girar en sentido de las manecillas del reloj y girar en sentido contrario a las manecillas del reloj. No pasa nada si no estás seguro de tu movimiento, pues siempre puedes deshacer un movimiento rotando la misma cara que volteaste en sentido contrario. Incluso si mueves varias caras, podrás regresar al estado original si recuerdas exactamente las caras que volteaste y la dirección, pues para deshacer los movimientos, tendrás que empezar por la última cara que volteaste y deberás girarla al sentido contrario al que le diste vuelta. Por ejemplo esta imagen indica dos movimientos a las caras y la forma de «deshacer» los movimientos.

En la imagen también marcamos los movimientos de mover las dos caras como $f$, por ahora imagínate que ese movimiento de girar las dos caras como lo muestra la imagen, se llama el movimiento $f$. Mientras que el movimiento de deshacerlas se llama $f^{-1}$. Entonces si realizamos primero el movimiento $f$, el movimiento $f^{-1}$ revierte lo que hizo la primera, volviendo al estado inicial. Así es como vamos a pensar en la reversibilidad de las funciones, una manera de «volver a armar» el cubo.

Funciones reversibles

Diremos que una función es reversible si existe una función $f^{-1}:Im(f) \rightarrow X$ tal que $f ^{-1}\circ f = Id$ donde $Id$ es la función identidad, es decir, es la única función que asigna a cada elemento a sí mismo, es decir $Id(x)=x$.

Algunas observaciones de las funciones invertibles. Sea $f:X \rightarrow Y$ una función invertible, entonces:

  • $f$ es inyectiva.

Demostración. Supongamos que no es inyectiva, entonces existen $x_1,x_2 \in X$ distintos tales que $f(x_1) = f(x_2)$. Como $f$ es invertible, entonces existe su función inversa $f^{-1}:Im(f) \rightarrow X$, en donde $$x_1 = f^{-1} \circ f(x_1) = f^{-1} \circ f(x_2) = x_2 $$ Siendo esta una contradicción, pues supusimos que eran distintos elementos. Así, la función es inyectiva.

$\square$

  • $f^{-1}$ es inyectiva.

Demostración. De manera similar a la demostración anterior, si $y_1,y_2 \in Dom(f^{-1})$ son tales que $f^{-1}(y_1) = f^{-1}(y_2)$, se tiene que al ser $f$ inyectiva, $$f(f^{-1}(y_1)) = f(f^{-1}(y_2)) \Rightarrow y_1=y_2$$ Llegando a que $f^{-1}$ es inyectiva.

$\square$

Así, te puedes dar una idea de lo que significan las funciones invertibles. Con estas proposiciones hemos probado además que la función $f^{-1}: Im(f) \rightarrow X$ es una biyección. ¿Te imaginas porqué? Pues resulta que la función $f^{-1}$ también es suprayectiva.

  • $f^{-1} \circ f = f \circ f^{-1}$

Demostración. Sabemos que $f^{-1} \circ f = Id$, entonces bastará demostrar que $f \circ f^{-1} = Id$. Para ello consideremos $y \in Dom(f^{-1})=Im(f) \subset Y$. Supongamos que $$f \circ f^{-1}(y)=w$$. Entonces $$f^{-1}(f \circ f^{-1}(y)) = f^{-1}(w). $$ Como la composición es asociativa, entonces: $$f^{-1}(f \circ f^{-1}(y)) = (f^{-1} \circ f) \circ f^{-1}(y) = f^{-1}(y) = f^{-1}(w)$$ Como $f^{-1}$ es inyectiva, entonces $y=w$

$\square$

  • Sea $g:Im(f) \rightarrow Z$ una función invertible, entonces $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$

Demostración. Basta notar que por la asociatividad de las funciones:

$$ \begin{align*}
(g \circ f) \circ (f^{-1} \circ g^{-1}) &= g \circ (f \circ (f^{-1} \circ g^{-1})\\
&= g \circ ((f \circ f^{-1}) \circ g^{-1})\\
&= g \circ (Id \circ g^{-1}) \\
&= g \circ g^{-1} = Id
\end{align*}$$

$\square$

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.

  1. Demuestra que $f^{-1}$ es suprayectiva.
  2. Demuestra que $Dom(f^{-1})=Im(f)$.
  3. Demuestra que $(f \circ (g \circ h))^{-1} = h^{-1} \circ (g^{-1} \circ f^{-1})$.
  4. Da una condición suficiente para que una función no sea invertible.

Más adelante…

Habiendo pasado por las funciones, su composición, sus propiedades y la inversa, utilizaremos estas definiciones para hablar de el tamaño de los conjuntos. Pues esta definición de funciones nos ayudan a decir «Cuántos elementos tiene un conjunto».

Entradas relacionadas

Álgebra Superior I: Composición de funciones

Por Guillermo Oswaldo Cota Martínez

Introducción

Siguiendo la conversación de las funciones, esta vez hablaremos de la composición de funciones. Este es el concepto que nos permitirá combinar más de una función para crear nuevas funciones siempre que ciertas condiciones se cumplan.

Composiciones en relaciones

Anteriormente ya hemos mencionado que sobre tres conjuntos $X,Y,Z$ se puede definir una relación composición entre dos relaciones $R$ de $x$ en $Y$ y $T$ de $Y$ en $Z$. De manera que la relación $T \circ R$ es aquella que está compuesta de elementos de la forma $(x,z) \in X \times Z$ siempre y cuando exista alguna $y$ de manera que $(x,y) \in R$ y $(y,z) in T$. Así, la relación composición está formada de elementos que pueden ir de $X$ a $Y$ mediante la relación $R$ y de ahí pueden llegar a $Z$ mediante la relación $T$. Veremos a continuación cómo podemos traducir esto a las funciones.

Composiciones en funciones

La composición de funciones será una composición de relaciones, no cambiará la definición, pues las funciones siguen siendo relaciones y hemos establecido toda una base sobre lo que son las relaciones para llegar a hablar de las funciones de forma gradual.

Piensa en el siguiente ejemplo. Supongamos tenemos una máquina $f$ que transforma las horas en minutos y otra máquina $g$ que transforma los minutos en segundos. Cuando a la máquina $f$ le pasamos de entrada «$1$ hora», nos regresará «$60$ minutos». Mientras que cuando le pasamos la entrada «$1$ minuto» a la máquina $g$ esta nos devuelve «60 segundos». Ahora nos preguntamos ¿Hay una forma de convertir las horas en segundos? O dicho de otra forma, ¿Cómo podemos construir una máquina $h$ que convierta las horas en los segundos? Nota que no tenemos directamente la máquina que nos toma las horas y las convierte en segundos, pero sí tenemos una máquina que convierte las horas en minutos y después los minutos en segundos.

Supongamos que tenemos la entrada «1 hora» entonces con la máquina $f$ podemos saber que una hora equivale a $60$ minutos. Enseguida podemos usar la máquina $G$ para saber que que los $60$ minutos equivalen a $3600$ segundos, de manera que esa es la duración de una hora. A esta máquina $h$ le llamamos la composición de $f$ con $g$.

Pensemos a estas máquinas como funciones, si consideramos $H$ como al conjunto de número de horas a considerar ($H=\{1 hr, 2 hrs, 3 hrs, \dots\}$) a $M$ como el conjunto de los minutos ($M =\{1 min, 2 mins, 3 mins, \dots\}$) y a $S$ como el conjunto de los segundos a considerar ($S=\{1 seg, 2 segs, 3 segs, \dots\}$) entonces $f:H \rightarrow M$ y $g: M \rightarrow S$ son funciones que convierten una unidad de tiempo en otra. La función $h : H \rightarrow S$ buscada es justamente la composición de las funciones $g \circ f: H \rightarrow S$.

Nota que si queremos convertir un número de horas $n \in H$ a segundos entonces bastará con notar que $n$ horas son $f(n)$ minutos, y estos a su vez son $g(f(n))$ segundos. Veamos el primer ejemplo. Nota que $f(1 hr)=60 mins$. Entonces $g(f(1hr))=g(60min)=3600segs$. Por lo cual la función que convierte las horas a segundos es componer $f$ con $g$.

Composición de funciones

Gráficamente lo que significa la composición de funciones es la siguiente imagen:

||||

Aquí podemos visualizar la función $g \circ f$ que es la función que va de $X$ a $Z$. En ella, vemos cómo es que la función $f$ va de X a Y, siendo que el dominio de $f$ queda dentro de $Y$, pues por definición, si la función $f$ va de $X$ a $Y$, entonces para cada elemento $x \in X$ sucede que existe $y \in Y$ tal que $f(x)=y$, significando que siempre $Im(f) \subset Y$ , y en nuestro caso en particular, $Y= Dom(g)$, siendo $g$ una función que va de $X$ a $Z$. Quizá lo que no es inmediato es la siguiente contención: $Im(g \circ f) \subset Im(g) \subset Z$.

Proposición. Si $f:X \rightarrow Y $ y $g: Y \rightarrow Z$ entonces $Im(g \circ f) \subset Im(g) \subset Z$

Demostración. Para esta demostración, consideremos $w \in Im(g \circ f) $ y veamos que $w \in Im(g)$. Para ello, notemos que por definición de la composición de funciones, si $w \in. Im(g \circ f)$ entonces existe $x \in X$ tal que $g \circ f(x) = w$. Es decir, $g(f(x))=w$ a su vez, como $f(x) \in Dom(g)$ entonces existe $y$ tal que $f(x)=y$ y $g(y)=w$. Ahora notemos que $y \in Dom(g)$ entonces $g(y) \in Im(g)$, es decir, $w=g(y) \in Dom(g)$. Por otro lado, por definición de función, la imagen de $g$ está contenida en $Z$. De esta manera, se tiene la contención buscada.

$\square$

Vamos a hacer algunas observaciones de esta composición de funciones.

  1. Para componer funciones, la imagen de una función debe estar contenida en el dominio de la otra. Esto significa que si queremos componer $f$ con $g$, debemos saber que todo elemento convertido por $f$ puede ser pasado a $g$. Dicho de otra manera, si queremos convertir horas a segundos, la máquina $f$ convierte las horas a minutos, y la $g$ minutos a segundos, entonces siempre tiene que pasar que $f$ devuelva minutos para poder componerse con $g$, pues acepta nada más minutos como entrada, si $f$ convirtiera horas a días, $g$ lo rechazaría, pues un día no está expresado en términos de minutos.
  2. La composición de funciones es asociativa, es decir, $(g\circ f) \circ h = g \circ (f \circ h)$.

Demostración. Consideremos $f : X \rightarrow Y$, $g : Y \rightarrow Z$ y $h : W \rightarrow X$. Para demostrar que la función es asociativa, deberíamos demostrar que apra algún $x$ arbitrario en el dominio de la composición $(W)$, se cumple que

$$ (g\circ f) \circ h(x) = g \circ (f \circ h)(x) $$

Para ello, llamemos $f \circ h = F$, $g \circ f = G$,$h(x)=y$ y $f(y)=z$. Ahora, nota por un lado que $$ g \ circ (f \circ h)(x) = g \circ F(x) = g(F(x)) = g(z)$$

Por otro lado, $(g \circ f) \circ h(x) = G \circ h(x) = G(y) = g \circ f(y) = g(z)$

Llegando a los mismos resultados, lo que debe significar que las funciones son iguales para $x$, pudiéndose generalizar para cada elemento del dominio de la composición.

$\square$

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.

  1. Demuestra que si $f$ es suprayectiva, entonces $Im(g \circ f) = Im(g)$.
  2. Sea $f: \mathbb{R} \ rightarrow \mathbb{R}$ dada por $f(x)=\frac{3x+1}{2}$:
    1. Encuentra $g: \mathbb{R} \ rightarrow \mathbb{R}$ tal que $g \circ f (x)= x$
    2. Demuestra que $g \circ f = f \circ g$
  3. Da condiciones suficientes y necesarias para que $g \circ f$ sea biyectiva.

Más adelante…

Habiendo visto la composición de funciones, estamos listos para dar el siguiente paso y encontrar una clase muy particular de funciones: funciones invertibles, que serán aquellas funciones que podemos «deshacer».

Entradas relacionadas