Archivo de la etiqueta: naturales

Teoría de los Conjuntos I: Conjuntos infinitos no numerables.

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

Al hablar de conjuntos infinitos, resulta natural pensar que entre cualesquiera dos de ellos debería existir una manera de «emparejar» sus elementos, es decir, establecer una biyección entre tales conjuntos, ya que, al fin y al cabo, ambos contienen infinitos elementos. Esta idea puede deberse a que, cuando uno piensa en conjuntos infinitos, lo primero que viene a la mente es el conjunto de los números naturales o el de los enteros, los cuales están ordenados de una manera bastante agradable y nos resulta «fácil» ubicarlos en una recta, como si fueran números colocados sobre una cinta métrica infinita.

Sin embargo, no todos los conjuntos infinitos poseen un orden tan agradable como el de estos dos conjuntos, y muchos de ellos presentan propiedades considerablemente diferentes. Por ejemplo, algunos conjuntos infinitos pueden no tener un buen orden como el de los naturales, o quizás exista tal orden pero nos resulte extremadamente difícil de identificar.

El teorema de Cantor demuestra que, efectivamente, la idea de que se pueden emparejar los elementos de cualesquiera dos conjuntos infinitos es incorrecta. Un ejemplo específico es el conjunto de los números naturales $\mathbb{N}$ y su conjunto potencia $\mathcal{P}(\mathbb{N})$; es imposible emparejar cada elemento de $\mathcal{P}(\mathbb{N})$ con uno y solo un elemento de $\mathbb{N}$. Este hecho muestra que existen conjunto infinitos más grandes que otros.

Esta entrada está dedicada precisamente a esta cuestión: exhibir conjuntos infinitos con «diferentes tamaños», específicamente, conjuntos que no sean numerables, es decir, que no sean equipotentes con $\mathbb{N}$. Como hemos venido haciendo, también emplearemos el muy importante teorema de Cantor-Schröder-Bernstein para probar ciertas equipotencias.

Conjuntos más grandes que $\mathbb{N}$

Por el teorema de Cantor sabemos que para cada conjunto $A$ se tiene $|A|<|\mathcal{P}(A)|$, es decir, que existe una función inyectiva de $A$ en $\mathcal{P}(A)$ pero no una función biyectiva. Así pues, por ejemplo, $\mathcal{P}(\mathbb{N})$ además de ser un conjunto infinito, tiene «más» elementos que $\mathbb{N}$, el cual es también infinito. Esto es una muestra de que existen conjuntos infinitos que no son equipotentes. En lo subsecuente exhibiremos algunos otros conjuntos infinitos que sí se pueden biyectar con $\mathcal{P}(\mathbb{N})$ y que por tanto no son numerables.

Comenzaremos proporcionando ejemplos que involucran conceptos que hemos visto en la entrada anterior.

Ejemplo.

El conjunto de sucesiones en $\mathbb{N}$, que denotaremos por $\mathbb{N}^{\mathbb{N}}$, es equipotente a $\mathcal{P}(\mathbb{N})$.

Demostración.

En la entrada anterior probamos que para cada $A\subseteq\mathbb{N}$ infinito, existe una única función biyectiva $F_A:\mathbb{N}\to A$ tal que $F_A(0)=\textnormal{min}(A)$ y que $F_A(n)<F_A(n+1)$ para cada $n\in\mathbb{N}$. Lo mismo mencionamos respecto a conjuntos finitos no vacíos, es decir, si $A\subseteq\mathbb{N}$ es un conjunto finito no vacío, digamos $|A|=n+1$ con $n\in\mathbb{N}$, existe una única función biyectiva $f_A:n+1\to A$ tal que $f_A(0)=\textnormal{min}(A)$ y que $f_A(m)<f_A(k)$ si y sólo si $m<k$ para cualesquiera $m,k\in n+1$.
Si $A\subseteq\mathbb{N}$ es finito, podemos extender la función $f_A$ a todo $\mathbb{N}$ de la siguiente manera: si $f_A:n+1\to A$ es la única función biyectiva que satisface $f_A(0)=\textnormal{min}(A)$ y $f_A(m)<f_A(k)$ si y sólo si $m<k$ para cualesquiera $m,k\in n+1$, definimos $F_A:\mathbb{N}\to A$ por medio de $$F_A(m)=\left\{\begin{array}{lcc}
f_A(m) & \textnormal{si}\ m\in n+1\\
\textnormal{min}(A) & \textnormal{si}\ m\notin n+1
\end{array}
\right.$$

Lo anterior nos permite asociar a cada elemento de $\mathcal{P}(\mathbb{N})\setminus\{\emptyset\}$ una única sucesión en $\mathbb{N}^{\mathbb{N}}$ por medio de la siguiente función: definamos $F:\mathcal{P}(\mathbb{N})\setminus\{\emptyset\}\to\mathbb{N}^{\mathbb{N}}$ como $F(A)=F_A$ para cada $A\in\mathcal{P}(\mathbb{N})$. Debido a la definición de las funciones $F_A$, en cualquier caso, ya sea que $A\subseteq\mathbb{N}$ es finito o infinito, se cumple que $F_A[\mathbb{N}]=A$; en consecuencia, si $A$ y $B$ son conjuntos no vacíos tales que $F(A)=F(B)$ tendríamos que para cada $k\in\mathbb{N}$, $F_A(k)=F_B(k)$ y, por ende, que $A=F_A[\mathbb{N}]=F_B[\mathbb{N}]=B$, lo cual muestra que $F$ es inyectiva.

Ahora bien, para cada $x\in\mathbb{N}^{\mathbb{N}}$ definamos $x+1:\mathbb{N}\to\mathbb{N}$ por medio de $(x+1)(n):=x(n)+1$ para cada $n\in\mathbb{N}$. La función $g:\mathbb{N}^{\mathbb{N}}\to\mathbb{N}^{\mathbb{N}}$ definida por medio de $g(x)=x+1$ es una función inyectiva, pues si $g(x)=g(y)$ para algunas $x,y\in\mathbb{N}^{\mathbb{N}}$, entonces, $x(n)+1=y(n)+1$ para cada $n\in\mathbb{N}$ y, por tanto, $x(n)=y(n)$ para cada $n\in\mathbb{N}$, es decir, $x=y$. Observemos además que $g(x)\not=x_0$ para cada $x\in\mathbb{N}^{\mathbb{N}}$, donde $x_0(n)=0$ para cada $n\in\mathbb{N}$; en efecto, si $x\in\mathbb{N}^{\mathbb{N}}$, entonces, $g(x)(n)=(x+1)(n)=x(n)+1\not=0$ para cada $n\in\mathbb{N}$ ya que $0$ no es sucesor de ningún número natural. Así, la función $g\circ F:\mathcal{P}(\mathbb{N})\setminus\set{\emptyset}\to\mathbb{N}^{\mathbb{N}}$ es inyectiva y $(g\circ F)(A)\not=x_0$ para cada $A\in\mathcal{P}(\mathbb{N})\setminus\{\emptyset\}$. Por tanto la función $h:\mathcal{P}(\mathbb{N})\to\mathbb{N}^{\mathbb{N}}$ definida como \[h(A)=\left\{\begin{array}{lcc}
(g\circ F)(A) & \textnormal{si}\ A\not=\emptyset\\
x_0 & \textnormal{si}\ A=\emptyset
\end{array}
\right.\] es inyectiva.

Para dar una función inyectiva de $\mathbb{N}^{\mathbb{N}}$ en $\mathcal{P}(\mathbb{N})$ retomaremos al conjunto de números primos $\mathbb{P}=\{p_n:n\in\mathbb{N}\}$ enumerado de tal forma que $p_n<p_{n+1}$ para cada $n\in\mathbb{N}$. Definamos ahora $T:\mathbb{N}^{\mathbb{N}}\to\mathcal{P}(\mathbb{N})$ por medio de $T(x)=\{p_n^{x(n)}:n\in\mathbb{N}\}$. Notemos que $T$ es una función inyectiva, pues si $T(x)=T(y)$, entonces, $\{p_n^{x(n)}:n\in\mathbb{N}\}=\{p_n^{y(n)}:n\in\mathbb{N}\}$ y así $p_n^{x(n)}=p_n^{y(n)}$ y $x(n)=y(n)$ para cada $n\in\mathbb{N}$, pues de otro modo se contradice al teorema fundamental de la aritmética. Por lo tanto, $x=y$ y $T$ es inyectiva.

Por el teorema de Cantor-Schröder-Bernstein concluimos que $|\mathcal{P}(\mathbb{N})|=|\mathbb{N}^{\mathbb{N}}|$.

$\square$

Al contrario de los conjuntos finitos, existen ejemplos de conjuntos infinitos que poseen subconjuntos propios equipotentes a ellos mismos, es decir, existe una biyección entre el subconjunto propio y el conjunto original. Un ejemplo de lo anterior es el conjunto de los números naturales, pues cualquier subconjunto propio de $\mathbb{N}$ que sea infinito resulta ser numerable. A continuación vamos a proporcionar otro de estos ejemplos, pero esta vez con un conjunto infinito no numerable.

Ejemplo.

El conjunto $2^{\mathbb{N}}:=\{f\in\mathbb{N}^{\mathbb{N}}:f(n)\in\{0,1\}\ \textnormal{para cada}\ n\in\mathbb{N}\}$ es equipotente a $\mathcal{P}(\mathbb{N})$.

Demostración.

Para demostrar la equipotencia de este ejemplo vamos a exhibir una biyección entre tales conjuntos. Para ello haremos lo siguiente, si $A\in\mathcal{P}(\mathbb{N})$ definimos $\chi_{A}:\mathbb{N}\to\mathbb{N}$ por medio de $\chi_{A}(n)=\left\{\begin{array}{lcc}
1 & \textnormal{si}\ n\in A\\
0 & \textnormal{si}\ n\in\mathbb{N}\setminus A
\end{array}
\right.$

Lo anterior nos permite establecer una función entre $\mathcal{P}(\mathbb{N})$ y $2^{\mathbb{N}}$, función que de hecho resulta ser biyectiva. Veamos primero la inyectividad. Si para $A,B\in\mathcal{P}(\mathbb{N})$ se cumple $\chi_A=\chi_B$, entonces $\chi_A(n)=\chi_B(n)$ para cada $n\in\mathbb{N}$. En consecuencia, si $n\in A$, $1=\chi_A(n)=\chi_B(n)$ y por ende $n\in B$; análogamente, si $n\in B$, $1=\chi_B(n)=\chi_A(n)$ y por tanto $n\in A$. Por consiguiente $A=B$, lo que demuestra la inyectividad de la función.
Resta probar la sobreyectividad. Consideremos $\chi\in 2^{\mathbb{N}}$ un elemento arbitrario. Definamos $A:=\{n\in\mathbb{N}:\chi(n)=1\}$ y veamos que $\chi_A=\chi$. Si $n\in A$, entonces $\chi(n)=1$ por definición del conjunto $A$ y, por otro lado, $\chi_A(n)=1$ por definición de la función $\chi_A$. Si ahora $n\in\mathbb{N}\setminus A$, $\chi(n)=0$ por definición del conjunto $A$ mientras que $\chi_A(n)=0$ por definición de la función $\chi_A$. Esto muestra que $\chi(n)=\chi_A(n)$ para cada $n\in\mathbb{N}$ y por ende que $\chi=\chi_A$. Así pues, la función $F:\mathcal{P}(\mathbb{N})\to2^{\mathbb{N}}$ definida por medio de $F(A)=\chi_A$ para cada $A\in\mathcal{P}(\mathbb{N})$ es una biyección y, por tanto, $|\mathcal{P}(\mathbb{N})|=|2^{\mathbb{N}}|$.

$\square$

Como lo mencionamos previamente, ahora contamos con un ejemplo de un conjunto infinito no numerable que posee un subconjunto propio equipotente a él, específicamente $\mathbb{N}^{\mathbb{N}}$ y $2^{\mathbb{N}}$ son equipotentes y $2^{\mathbb{N}}\subsetneq\mathbb{N}^{\mathbb{N}}$. Conjuntos de este tipo, es decir, conjuntos que poseen subconjuntos propios equipotentes a ellos, reciben un nombre particular que anotamos en la siguiente definición.

Definición. Un conjunto $X$ se llama infinito según Dedekind si existe una función inyectiva $f:X\to X$ tal que $f[X]\not=X$.

Que un conjunto sea infinito según Dedekind implica que dicho conjunto es infinito. Y ya que contamos con algunos ejemplos de conjuntos infinitos que también son infinitos según Dedekind, surge de manera natural la pregunta: ¿todo conjunto infinito es infinito según Dedekind? Dicha cuestión no la podemos responder con lo que hemos visto hasta ahora y es por eso que la dejaremos para más adelante.

Una consecuencia inmediata del último ejemplo es el siguiente corolario.

Corolario. Sean $a_0,a_1,\ldots,a_n\in\mathbb{N}$ naturales distintos con $n\geq1$. El conjunto $\{f\in\mathbb{N}^{\mathbb{N}}:f[\mathbb{N}]\subseteq\{a_0,a_1,\ldots,a_n\}\}$ es equipotente a $\mathbb{N}^{\mathbb{N}}$.

Demostración.

Dado que $j:\{f\in\mathbb{N}^{\mathbb{N}}:f[\mathbb{N}]\subseteq\{a_0,a_1,\ldots,a_n\}\}\to\mathbb{N}^{\mathbb{N}}$ definida por medio de $j(f)=f$ es una función inyectiva, basta exhibir una función inyectiva de $\mathbb{N}^{\mathbb{N}}$ en $\{f\in\mathbb{N}^{\mathbb{N}}:f[\mathbb{N}]\subseteq\{a_0,a_1,\ldots,a_n\}\}$.

Denotemos $A:=\{f\in\mathbb{N}^{\mathbb{N}}:f[\mathbb{N}]\subseteq\{a_0,a_1,\ldots,a_n\}\}$. Si denotamos $B:=\{f\in\mathbb{N}^{\mathbb{N}}:f[\mathbb{N}]\subseteq\{a_0,a_1\}\}$, entonces $B\subseteq A$. Para cada $\chi\in2^{\mathbb{N}}$ definamos $f_\chi:\mathbb{N}\to\mathbb{N}$ de la siguiente manera $f_\chi(n)=\left\{\begin{array}{lcc}
a_0 & \textnormal{si}\ \chi(n)=0\\
a_1 & \textnormal{si}\ \chi(n)=1
\end{array}
\right.$
A partir de la definición anterior tenemos que $f_{\chi}\in B$ para cada $\chi\in2^{\mathbb{N}}$, lo cual nos permite definir $F:2^{\mathbb{N}}\to B$ por medio de $F(\chi)=f_{\chi}$. Resulta que $F$ es una biyección. En efecto, por un lado es inyectiva ya que si $F(\chi)=F(\chi’)$, entonces $f_{\chi}(n)=f_{\chi’}(n)$ para cada $n\in\mathbb{N}$, de modo que si $\chi(n)=0$ se tiene que $a_0=f_{\chi}(n)=f_{\chi’}(n)$ y por tanto $\chi'(n)=0$; asimismo, si $\chi(n)=1$ se tiene que $a_1=f_{\chi}(n)=f_{\chi’}(n)$ por lo que $\chi'(n)=1$. Por tanto $\chi(n)=\chi'(n)$ para cada $n\in\mathbb{N}$ y así $\chi=\chi’$.
Ahora para mostrar que $F$ es sobreyectiva tomemos $f\in B$ elemento arbitrario y definamos $\chi:\mathbb{N}\to\mathbb{N}$ por medio de $\chi(n)=\left\{\begin{array}{lcc}
1 & \textnormal{si}\ f(n)=a_1\\
0 & \textnormal{si}\ f(n)=a_0
\end{array}
\right.$
Luego, $f_{\chi}=f$, pues si $n\in\mathbb{N}$ es tal que $f(n)=a_1$ se tiene que $\chi(n)=1$ por definición de $\chi$ y así $f_{\chi}(n)=a_1$; por otro lado, si $n\in\mathbb{N}$ es tal que $f(n)=a_0$ se tiene que $\chi(n)=0$ por definición de $\chi$ y por ende $f_{\chi}(n)=a_0$. Podemos concluir entonces que $F( \chi)=f_{\chi}=f$, lo que demuestra que $F$ es sobreyectiva. Por tanto $F$ es una biyección y $|2^{\mathbb{N}}|=|B|$.
Ahora, sean $h:\mathbb{N}^{\mathbb{N}}\to2^{\mathbb{N}}$ una función biyectiva (la cual sabemos que existe pues $|\mathbb{N}^{\mathbb{N}}|=|\mathcal{P}(\mathbb{N})|=|2^{\mathbb{N}}|$) y $\iota:B\to A$ la función inclusión, es decir, $\iota(f)=f$ para cada $f\in B$. Luego, $\iota\circ h:\mathbb{N}^{\mathbb{N}}\to A$ es una función inyectiva.
Por el teorema de Cantor-Schröder-Bernstein concluimos que $|\mathbb{N}^{\mathbb{N}}|=|A|$.

$\square$

Observemos que el corolario muestra que existen una infinidad de subcojuntos propios de $\mathbb{N}^{\mathbb{N}}$ equipotentes a él. Dado que $|\mathcal{P}(\mathbb{N})|=|\mathbb{N}^{\mathbb{N}}|$, entonces $\mathcal{P}(\mathbb{N})$ también posee una cantidad infinita de subconjuntos propios equipotentes a él. El siguiente ejemplo es uno de tales subconjuntos.

Ejemplo.

El conjunto $[\mathbb{N}]^{\mathbb{N}}:=\{A\subseteq\mathbb{N}:|A|=|\mathbb{N}|\}$ es equipotente a $\mathcal{P}(\mathbb{N})$.

Demostración.

Dado que $[\mathbb{N}]^{\mathbb{N}}\subseteq\mathcal{P}(\mathbb{N})$ lo único que hace falta es exhibir una función inyectiva de $\mathcal{P}(\mathbb{N})$ en $[\mathbb{N}]^{\mathbb{N}}$.

Consideremos al conjunto de números primos $\mathbb{P}=\{p_n:n\in\mathbb{N}\}$ donde $p_n<p_{n+1}$ para cada $n\in\mathbb{N}$. Definamos $g:\mathbb{N}^{\mathbb{N}}\to[\mathbb{N}]^{\mathbb{N}}$ como $g(x)=\{p_n^{x(n)+1}:n\in\mathbb{N}\}$. Dado que para cada $x\in\mathbb{N}^{\mathbb{N}}$, $x(n)+1\not=0$ para toda $n\in\mathbb{N}$, tenemos que $\{p_n^{x(n)+1}:n\in\mathbb{N}\}$ es un conjunto infinito, por lo que $g$ tiene el codominio adecuado. Por otro lado, $g$ es inyectiva ya que si $g(x)=g(y)$, entonces $p_n^{x(n)+1}=p_n^{y(n)+1}$ para cada $n\in\mathbb{N}$ por el teorema fundamental de la aritmética y, más aún, $x(n)+1=y(n)+1$ para cada $n\in\mathbb{N}$, lo que demuestra que $x=y$. Si $h:\mathcal{P}(\mathbb{N})\to\mathbb{N}^{\mathbb{N}}$ es una biyección se sigue que $g\circ h:\mathcal{P}(\mathbb{N})\to[\mathbb{N}]^{\mathbb{N}}$ es una función inyectiva. Por el teorema de Cantor-Schröder-Bernstein concluimos que $|\mathcal{P}(\mathbb{N})|=|[\mathbb{N}]^{\mathbb{N}}|$.

$\square$

Como un ejercicio para esta entrada dejaremos el siguiente ejemplo.

Ejemplo.

$\mathbb{N}^{\nearrow\mathbb{N}}:=\{f\in\mathbb{N}^{\mathbb{N}}:f(n)<f(n+1)\ \textnormal{para cada}\ n\in\mathbb{N}\}$ es equipotente a $[\mathbb{N}]^{\mathbb{N}}$, y por tanto equipotente a $\mathcal{P}(\mathbb{N})$.

Para finalizar con esta serie de ejemplos de conjuntos no numerables y equipotentes a $\mathcal{P}(\mathbb{N})$ hablaremos del conjunto de números reales.
Para lo que sigue vamos a suponer que ya conocemos todas las propiedades básicas del conjunto de números reales, y si no se conocen dichas propiedades o lo que es un número real, puedes consultar cualquier libro introductorio a la teoría de conjuntos como el de Hernández1, o también puedes consultarlo en un libro de cálculo como el de Spivak2.
Además de lo dicho en el párrafo precedente, estaremos haciendo un abuso de notación escribiendo las contenciones $\mathbb{N}\subseteq\mathbb{Z}\subseteq\mathbb{Q}\subseteq\mathbb{R}$.
Dicho lo anterior tenemos la siguiente proposición.

Proposición. El intervalo abierto $(0,1)=\{r\in\mathbb{R}:0<r<1\}$ es equipotente a $\mathbb{R}$.

Demostración.

Definamos $f:\mathbb{R}\to(0,1)$ por medio de $f(x)=\left\{\begin{array}{lcc}
\frac{4x+1}{4x+2} & \textnormal{si}\ x\geq0\\
\frac{1}{2(1-2x)} & \textnormal{si}\ x<0
\end{array}
\right.$
Lo primero que se debe observar es que la función $f$ tiene el codominio adecuado, es decir, $f(x)\in(0,1)$ para cada $x\in\mathbb{R}$. Si $x\geq0$, entonces, $0<4x+1<4x+2$ y por tanto $0<\frac{4x+1}{4x+2}<1$, es decir, $f(x)\in(0,1)$; por otro lado, si $x<0$, entonces $0<-2x$ y así $1<1-2x$, lo cual implica que $0<\frac{1}{1-2x}<1$ y que $0<\frac{1}{2(1-2x)}<\frac{1}{2}<1$, es decir, $f(x)\in(0,1)$. Por tanto, $f(x)\in(0,1)$ para cada $x\in\mathbb{R}$. Es importante notar que para $x<0$ vimos que no sólo se cumple $0<f(x)<1$, sino también que $0<f(x)<\frac{1}{2}$. Por otro lado, para $x\geq0$, tenemos que $0<1+2x\leq1+4x$ por lo que $1\leq\frac{4x+1}{2x+1}$ y por tanto $\frac{1}{2}\leq\frac{4x+1}{4x+2}$; de modo que para $x\geq0$ no sólo se cumple que $f(x)\in(0,1)$, sino también que $f(x)\in[\frac{1}{2},1)$.
Veamos ahora que $f$ es una función inyectiva. Sean $x,y\in\mathbb{R}$ con $x\not=y$. Debido a que $\mathbb{R}$ posee un orden lineal podemos suponer que $y<x$. Tenemos los siguientes casos.
Caso 1. $y<0\leq x$. En este caso se tiene que $f(y)\in(0,\frac{1}{2})$ mientras que $f(x)\in[\frac{1}{2},1)$, razón por la cual $f(x)\not=f(y)$.
Caso 2. $0\leq y<x$. En este caso se tiene que $f(y)=\frac{4y+1}{4y+2}$ y $f(x)=\frac{4x+1}{4x+2}$. Luego, si ocurriera que $\frac{4y+1}{4y+2}=\frac{4x+1}{4x+2}$, entonces $(4y+1)(4x+2)=(4x+1)(4y+2)$, lo cual implica $(4y+1)(2x+1)=(4x+1)(2y+1)$, es decir, $8xy+4y+2x+1=8xy+4x+2y+1$ y por ende $2y=2x$, lo cual contradice que $x\not=y$. Por tanto, $f(x)\not=f(y)$.
Caso 3. $y<x<0$. Si ocurriera que $f(x)=f(y)$, entonces $\frac{1}{2(1-2x)}=\frac{1}{2(1-2y)}$ y por ende, $1-2x=1-2y$, de donde $x=y$ y eso contradice la elección de $x$ y $y$. Por tanto $f$ es una función inyectiva.

Veamos ahora que $f$ es sobreyectiva. Sea $r\in(0,1)$. Si $r\in(0,\frac{1}{2})$, entonces $2<\frac{1}{r}$, lo cual implica $\frac{1}{2}<\frac{1}{4r}$ y así $x:=\frac{1}{2}-\frac{1}{4r}$ es un número real menor a $0$; luego, para tal $x$ tenemos que $f(x)=\frac{1}{2(1-2x)}=\frac{1}{2(1-(1-\frac{1}{2r}))}=\frac{1}{2\cdot\frac{1}{2r}}=r$. Si ahora $r\in[\frac{1}{2},1)$, entonces $2r-1\geq0$ y $1-r>0$, por lo que $x:=\frac{2r-1}{4(1-r)}$ es un número real mayor o igual a $0$ para el cual se cumple $f(x)=\frac{4x+1}{4x+2}=\frac{4(\frac{2r-1}{4(1-r)})+1}{4(\frac{2r-1}{4(1-r)})+2}=\frac{\frac{2r-1}{1-r}+1}{\frac{2r-1}{1-r}+2}=\frac{\frac{2r-1+1-r}{1-r}}{\frac{2r-1+2-2r}{1-r}}=\frac{r}{1}=r$. Lo anterior prueba que $f$ es sobreyectiva.

Por lo tanto $f$ es una biyección y $|\mathbb{R}|=|(0,1)|$.

$\square$

Una consecuencia de la proposición anterior es el siguiente corolario.

Corolario. El intervalo $[0,1]:=\{r\in\mathbb{R}:0\leq r\leq1\}$ es equipotente a $\mathbb{R}$.

Demostración.

Dado que $[0,1]\subseteq\mathbb{R}$, basta mostrar que existe una función inyectiva de $\mathbb{R}$ en $[0,1]$. Por la proposición anterior existe una función biyectiva $f:\mathbb{R}\to(0,1)$ y así la función $F:\mathbb{R}\to[0,1]$ definida como $F(x)=f(x)$ para cada $x\in\mathbb{R}$ es inyectiva. Por el teorema de Cantor-Schröder-Bernstein concluimos que $|\mathbb{R}|=|[0,1]|$.

$\square$

Si bien la demostración del corolario anterior fue muy rápida y utilizamos el importante teorema de Cantor-Schröder-Bernstein, siempre resulta interesante determinar una biyección explícita, y precisamente en el caso del corolario anterior lo podemos hacer.

Definamos $S:=\{\frac{1}{n}:n\in\mathbb{N}\setminus\set{0}\}\cup\{0\}$. Definamos $g:[0,1]\to(0,1)$ por medio de $g(x)=\left\{\begin{array}{lcc}
x & \textnormal{si}\ x\notin S\\
\frac{1}{n+2} & \textnormal{si}\ x=\frac{1}{n},\ n\in\mathbb{N}\setminus\{0\}\\
\frac{1}{2} & \textnormal{si}\ x=0
\end{array}
\right.$

La función anterior resulta ser una biyección entre $[0,1]$ y $(0,1)$. Primero veremos que $g$ es inyectiva. Sean $x,y\in[0,1]$ con $x\not=y$. Tenemos algunos casos.

Caso 1. $x,y\notin S$. En este caso $g(x)=x\not=y=g(y)$.
Caso 2. $x\in S$, $y\notin S$. Dado que para cada $z\in S$ se tiene $g(z)\in S$, entonces, $g(x)\in S$ mientras que $g(y)=y\notin S$. Por tanto $g(x)\not=g(y)$.
Caso 3. $x\notin S$, $y\in S$. Análogo al caso $2$.
Caso 4. $x,y\in S$. Si $x=0$ y $y=\frac{1}{n}$ con $n\in\mathbb{N}\setminus\{0\}$, entonces $g(x)=\frac{1}{2}$ y $g(y)=\frac{1}{n+2}$. Como $n\geq1$ se tiene que $n+2\geq3$ y por tanto $\frac{1}{2}\not=\frac{1}{n+2}$, es decir, $g(x)\not=g(y)$. Análogamente, si $y=0$ y $x=\frac{1}{n}$ con $n\in\mathbb{N}\setminus\{0\}$, $g(x)\not=g(y)$. Supongamos ahora que $x=\frac{1}{n}$ y $y=\frac{1}{m}$ con $n,m\in\mathbb{N}\setminus\{0\}$ con $n\not=m$.
Luego, $g(x)=\frac{1}{n+2}\not=\frac{1}{m+2}=g(y)$ pues de lo contrario tendríamos $n+2=m+2$ y $n=m$, lo cual contradice $n\not=m$.
Los cuatro casos anteriores muestran que $g$ es inyectiva.

Veamos ahora que $g$ es sobreyectiva. Sea $x\in(0,1)$. Si $x\in S$, entonces $x=\frac{1}{n}$ con $n\in\mathbb{N}$, $n\geq2$, por lo que existe $m\in\mathbb{N}$ tal que $m+2=n$; si $m=0$, entonces $x=\frac{1}{2}=g(0)$ y si $m>0$, entonces, $g(\frac{1}{m})=\frac{1}{m+2}=\frac{1}{n}=x$.
Si $x\notin S$, entonces $g(x)=x$. Por tanto, $g$ es sobreyectiva y en consecuencia una biyección. Esto muestra que $[0,1]$ y $(0,1)$ son equipotentes y, por tanto, $[0,1]$ y $\mathbb{R}$ son equipotentes. Más aún, contamos con una biyección explícita entre $[0,1]$ y $\mathbb{R}$.

Para exhibir la biyección entre $[0,1]$ y $(0,1)$ utilizamos el hecho de que $[0,1]$ contiene un conjunto numerable, específicamente el conjunto $S=\{\frac{1}{n}:n\in\mathbb{N}\setminus\{0\}\}\cup\{0\}$. Precisamente este hecho fue el que jugó un papel fundamental, pues como veremos en la siguiente proposición, si $X$ es un conjunto infinito que contiene un conjunto numerable, entonces, para cada $A\subseteq X$ conjunto finito, se cumple $|X\setminus A|=|X|$.

Proposición. Sea $X$ un conjunto infinito tal que existe una función inyectiva $f:\mathbb{N}\to X$. Entonces, para cada $A\subseteq X$ conjunto finito, $|X\setminus A|=|X|$.

Demostración.

Como lo mostrarás en los ejercicios de esta sección, basta mostrar que para cada $x\in X$, los conjuntos $X\setminus\{x\}$ y $X$ son equipotentes.

Sea pues $x\in X$. Sea $f:\mathbb{N}\to X$ una función inyectiva y denotemos por $N$ a la imagen de $f$, esto es $N:=im(f)=\{f(n):n\in\mathbb{N}\}$.

Si $x\notin N$, definamos $g:X\to X\setminus\{x\}$ por medio de $g(y)=\left\{\begin{array}{lcc}
y & \textnormal{si}\ y\notin N\cup\{x\}\\
f(0) & \textnormal{si}\ y=x\\
f(n+1) & \textnormal{si}\ y=f(n)
\end{array}
\right.$

Comprobar que esta función es biyectiva es análogo a como lo hicimos con la función biyectiva que exhibimos entre los intervalos $[0,1]$ y $(0,1)$, por lo que lo dejaremos como un ejercicio para esta entrada.

Supongamos ahora que $x\in N$ y sea $n\in\mathbb{N}$ tal que $x=f(n)$. Para este caso definamos $h:X\to X\setminus\{x\}$ por medio de $h(y)=\left\{\begin{array}{lcc}
y & \textnormal{si}\ y\notin N\setminus\{f(m):m<n\}\\
f(m+1) & \textnormal{si}\ y=f(m),\ m\geq n
\end{array}
\right.$

Nuevamente, comprobar que esta función es biyectiva es similar a lo que hemos hecho. Esto nos permite concluir que $|X\setminus\{x\}|=|X|$ para cada $x\in X$.

$\square$

Para culminar la entrada mostraremos que $(0,1)$ y $\mathcal{P}(\mathbb{N})$ son equipotentes y que por tanto $\mathbb{R}$ y $\mathcal{P}(\mathbb{N})$ lo son. Esto lo escribiremos como un teorema.

Teorema. $(0,1)$ y $\mathcal{P}(\mathbb{N})$ son equipotentes.

Demostración.

Primero vamos a mostrar la siguiente afirmación: para cada $r\in(0,1)$, existe una única función $\chi_r:\mathbb{N}\to\mathbb{N}$ que satisface $\chi_r(n)\in\{0,1,2,3,4,5,6,7,8,9\}$ para cada $n\in\mathbb{N}$ y tal que $0\leq x-\sum_{i=0}^{n}\frac{\chi_r(i)}{10^i}<\frac{1}{10^{n}}$.

Sea pues $r\in(0,1)$. Probaremos por inducción que para cada $n\in\mathbb{N}$ existe una única función $\chi^{(n)}_r:n+1\to\mathbb{N}$ tal que $\chi^{(n)}_{r}[n+1]\subseteq\{0,1,2,3,4,5,6,7,8,9\}$ y $0\leq x-\sum_{i=0}^{n}\frac{\chi^{(n)}_{r}(i)}{10^i}<\frac{1}{10^n}$.
Para $n=0$ definamos $\chi^{(0)}_r:1\to\mathbb{N}$ por medio de $\chi^{(0)}_r(0)=0$. Luego, $0\leq r=r-\frac{\chi^{(0)}_r(0)}{10^0}<1=\frac{1}{10^0}$. Si $y:1\to\mathbb{N}$ es otra función tal que $y(0)\in\{0,1,2,3,4,5,6,7,8,9\}$ y $0\leq r-\frac{y(0)}{10^0}<\frac{1}{10^0}$, entonces, $y(0)\leq r<1$ y por tanto $y(0)=0$, ya que el único natural menor a $1$ es $0$. Por tanto, $\chi^{(0)}_r=y$, lo que demuestra que para $n=0$ el enunciado es verdadero.
Supongamos que el resultado es válido para algún $n\geq0$. Sea $\chi^{(n)}_r:n+1\to\mathbb{N}$ la única función de la hipótesis. Primero vamos a demostrar la existencia de una función $\chi^{(n+1)}_r$ con las propiedades deseadas y luego probaremos su unicidad. Dado que $0\leq r-\sum_{i=0}^{n}\frac{\chi^{(n)}_r(i)}{10^i}<\frac{1}{10^{n}}$ se sigue que $0\leq10^n(r-\sum_{i=0}^{n}\frac{\chi^{(n)}_r(i)}{10^i})<1$. Si ocurriera que $ r-\sum_{i=0}^{n}\frac{\chi^{(n)}_r(i)}{10^i}=0$, definimos $\chi^{(n+1)}_r:n+2\to\mathbb{N}$ como $\chi^{(n+1)}_r(i)=\left\{\begin{array}{lcc}
\chi^{(n)}_r(i) & \textnormal{si}\ i\in n+1\\
0 & \textnormal{si}\ i=n+1
\end{array}
\right.$
Definida de esa manera la función $\chi^{(n+1)}_r$ se satisfacen las hipótesis deseadas. Supongamos ahora que $0<r-\sum_{i=0}^{n}\frac{\chi^{(n)}_r(i)}{10^i}$ y definamos $\hat{r}:=10^n(r-\sum_{i=0}^{n}\frac{\chi^{(n)}_r(i)}{10^i})$, número real que sabemos satisface $0<\hat{r}<1$. Consideremos el conjunto $A=\{m\in\mathbb{N}:m\leq 10\hat{r}\}$, el cual es no vacío ya que $0<\hat{r}$ y por tanto $0\leq 10\hat{r}$; además, $A$ es acotado superiormente ya que $\hat{r}<1$ y por tanto $10\hat{r}<10$, de modo que si $m\in A$, entonces $m<10$. Así, existe $a=\textnormal{max}(A)$, el cual es un natural dentro del conjunto $\{0,1,2,3,4,5,6,7,8,9\}$. Por la maximalidad de $a$ se tiene que $10\hat{r}<a+1$ y así $\frac{a}{10}\leq\hat{r}<\frac{a}{10}+\frac{1}{10}$, es decir, $0\leq\hat{r}-\frac{a}{10}<\frac{1}{10}$.
Luego, dado que $\hat{r}=10^n(r-\sum_{i=0}^{n}\frac{\chi^{(n)}_r(i)}{10^i})$ se sigue que $0\leq r-\sum_{i=0}^{n}\frac{\chi^{(n)}_r(i)}{10^i}-\frac{a}{10^{n+1}}<\frac{1}{10^{n+1}}$. Si definimos $\chi^{(n+1)}_r:n+2\to\mathbb{N}$ por medio de $\chi^{(n+1)}_r(i)=\left\{\begin{array}{lcc}
\chi^{(n)}_r(i) & \textnormal{si}\ i\in n+1\\
a & \textnormal{si}\ i=n+1
\end{array}
\right.$

entonces $\chi^{(n+1)}_r$ es una función que satisface las condiciones deseadas. Así, hemos demostrado la existencia de una función con las características requeridas. Veamos que ésta es única. Supongamos que $\eta:n+2\to\mathbb{N}$ es otra función que satisface las mismas propiedades que $\chi_r^{(n+1)}$.
Luego, en particular, $0\leq r-\sum_{i=0}^{n+1}\frac{\eta(i)}{10^i}<\frac{1}{10^{n+1}}$ y por tanto $0\leq r-\sum_{i=0}^{n}\frac{\eta(i)}{10^i}<\frac{1}{10^{n+1}}+\frac{\eta(n+1)}{10^{n+1}}\leq \frac{1}{10^{n+1}}+\frac{9}{10^{n+1}}=\frac{10}{10^{n+1}}=\frac{1}{10^n}$. De este modo, la función $\eta\upharpoonright_{n+1}:n+1\to\mathbb{N}$ satisface las mismas condiciones que la función $\chi^{(n)}_r$, y por la unicidad de esta última función se sigue que $\eta(i)=\chi^{(n)}_r(i)$ para cada $i\in n+1$. Así, la función $\eta$ coincide con la función $\chi^{(n+1)}_r$ en $n+1$, por lo que resta probar que $\eta(n+1)=\chi^{(n+1)}_r(n+1)=a$.
Sabemos que $0\leq r-\sum_{i=0}^{n}\frac{\chi^{(n+1)}_r(i)}{10^i}-\frac{\eta(n+1)}{10^{n+1}}<\frac{1}{10^{n+1}}$ y por tanto, $0\leq 10^{n+1}(r-\sum_{i=0}^{n}\frac{\chi^{(n+1)}(i)}{10^i})-\eta(n+1)<1$, es decir, $\eta(n+1)\leq10\hat{r}<\eta(n+1)+1$, de modo que $\eta(n+1)\in A$ y por tanto $\eta(n+1)\leq a=\chi^{(n+1)}_r(n+1)$. Podemos elegir $k\in\{0,1,2,3,4,5,6,7,8,9\}$ tal que $\eta(n+1)+k=a$ y tenemos $a=\eta(n+1)+k\leq10\hat{r}$, razón por la cual \[k\leq10\hat{r}-\eta(n+1)<(\eta(n+1)+1)-\eta(n+1)=1\] y en consecuencia, $k=0$. Por tanto, $\eta(n+1)=a=\chi^{(n+1)}_r(n+1)$. Esto demuestra la unicidad de $\chi^{(n+1)}_r$.

Por lo tanto, para cada $n\in\mathbb{N}$ existe una única función $\chi^{(n)}_r:n+1\to\mathbb{N}$ tal que $\chi^{(n)}_r[\mathbb{N}]\subseteq\{0,1,2,3,4,5,6,7,8,9\}$ y $0\leq r-\sum_{i=0}^{n}\frac{\chi^{(n)}_r(i)}{10^i}<\frac{1}{10^n}$. En el proceso de la demostración de la existencia y unicidad de tales funciones, mostramos además que si $\chi^{(n+1)}_r:n+2\to\mathbb{N}$ es la única función con tales propiedades, entonces, $\chi^{(n)}_r=\chi^{(n+1)}_r\upharpoonright_{n+1}$, lo que muestra que el conjunto de funciones $\mathcal{F}:=\{\chi^{(n)}_r:n\in\mathbb{N}\}$ es un sistema de funciones compatibles y, por tanto, $\chi_r=\bigcup\mathcal{F}:\mathbb{N}\to\mathbb{N}$ es la única función con las propieades que enunciamos en la afirmación.

Estamos entonces en condiciones de definir una función $F:(0,1)\to\{f\in\mathbb{N}^{\mathbb{N}}:f[\mathbb{N}]\subseteq\{0,1,2,3,4,5,6,7,8,9\}\}$ por medio de $F(r)=\chi_r$. Dicha función es inyectiva, ya que si $\chi_r=\chi_{r’}$, entonces, para cada $n\in\mathbb{N}$, \[|r-r’|=|r-\sum_{i=0}^{n}\frac{\chi_r(i)}{10^i}+\sum_{i=0}^{n}\frac{\chi_{r’}(i)}{10^i}-r’|\] \[\leq|r-\sum_{i=0}^{n}\frac{\chi_r(i)}{10^i}|+|\sum_{i=0}^{n}\frac{\chi_{r’}(i)}{10^i}-r’|\] \[<\frac{1}{10^n}+\frac{1}{10^n}=\frac{2}{10^n}\] lo cual muestra que $|r-r’|=0$, es decir, $r=r’$. Por tanto, existe una función inyectiva de $(0,1)$ en $\mathbb{N}^{\mathbb{N}}$, de modo que $|(0,1)|\leq|\mathbb{N}^{\mathbb{N}}|=|\mathcal{P}(\mathbb{N})|$.

Ahora vamos a definir una función inyectiva de $2^{\mathbb{N}}$ en $(0,1)$. Sea $f\in2^{\mathbb{N}}$ y veamos que la sucesión de números racionales $(\sum_{i=0}^{n}\frac{f(i)}{10^{i+1}})_{n\in\mathbb{N}}$ converge. Dado que $f(i)\in\{0,1\}$ para cada $i\in\mathbb{N}$, la sucesión $(\sum_{i=0}^{n}\frac{f(i)}{10^{i+1}})_{n\in\mathbb{N}}$ es no decreciente. Luego, para cada $n\in\mathbb{N}$, $0\leq\sum_{i=0}^{n}\frac{f(i)}{10^{i+1}}\leq\sum_{i=0}^{n}\frac{1}{10^{i+1}}=\sum_{i=1}^{n+1}\frac{1}{10^i}=\frac{1-\frac{1}{10^{n+2}}}{1-\frac{1}{10}}-1=\frac{1-\frac{1}{10^{n+2}}}{(\frac{9}{10})}-1<\frac{1}{(\frac{9}{10})}-1=\frac{10}{9}-1=\frac{1}{9}<1$, por lo que dicha sucesión está acotada inferiormente por $0$ y superiormente por $\frac{1}{9}$ y, por tanto, converge a algún número real en el intervalo $[0,\frac{1}{9}]$. Sea $r_f\in[0,\frac{1}{9}]$ el límite de dicha sucesión.
Si la función $f$ no es la constante cero, entonces, $r_f\in(0,\frac{1}{9}]$, ya que existe $N\in\mathbb{N}$ tal que $f(N)=1$ y por tanto, para cada $n\geq N$, $\frac{1}{10^{N+1}}\leq\sum_{i=0}^{n}\frac{f(i)}{10^{i+1}}\leq r_f$.
Dado que el número real $r_f$ es único para cada $f\in2^{\mathbb{N}}$, estamos en condiciones de definir la siguiente función: sea $G:2^{\mathbb{N}}\to[0,1)$ tal que $G(f)=\left\{\begin{array}{lcc}
r_f & \textnormal{si}\ f\not=0\\
0 & \textnormal{si}\ f=0
\end{array}
\right.$

Veamos que $G$ es inyectiva. Por la definición de $G$ sabemos que si $f\not=0$, entonces $G(f)\not=G(0)$. Ahora, sean $f,h\in2^{\mathbb{N}}$ funciones no cero tales que $r_f=G(f)=G(h)=r_h$. Veamos que $f(n)=h(n)$ para cada $n\in\mathbb{N}$.
Algo que será de utilidad para probar esto último es la desigualdad $\sum_{i=n+1}^{m}\frac{1}{10^i}<\frac{1}{2\cdot10^n}$, la cual es cierta para cualesquiera $n,m\in\mathbb{N}$ tales que $n<m$. En efecto, si $n,m\in\mathbb{N}$ con $n<m$, tenemos \[\sum_{i=n+1}^{m}\frac{1}{10^i}=\sum_{i=0}^{m}\frac{1}{10^i}-\sum_{i=0}^{n}\frac{1}{10^i}=\frac{1-\frac{1}{10^{m+1}}}{1-\frac{1}{10}}-\frac{1-\frac{1}{10^{n+1}}}{1-\frac{1}{10}}=\frac{\frac{1}{10^{n+1}}-\frac{1}{10^{m+1}}}{(\frac{9}{10})}=\frac{\frac{1}{10^n}-\frac{1}{10^m}}{9}\] y este número racional es menor que $\frac{1}{2\cdot10^n}$, pues $\frac{1}{10^n}-\frac{1}{10^m}<\frac{1}{10^n}<\frac{9}{2}\cdot\frac{1}{10^n}$, pues $1<\frac{9}{2}$. Por tanto, para cualesquiera $n,m\in\mathbb{N}$ con $n<m$, $\sum_{i=n+1}^{m}\frac{1}{10^i}<\frac{1}{2\cdot10^n}$.

Ahora sí, veamos que $f(n)=h(n)$ para cada $n\in\mathbb{N}$.
Dado que las sucesiones de números racionales $(\sum_{i=0}^{n}\frac{f(i)}{10^{i+1}})_{n\in\mathbb{N}}$ y $(\sum_{i=0}^{n}\frac{h(i)}{10^{i+1}})_{n\in\mathbb{N}}$ convergen al número real $r_f$, existe $m\in\mathbb{N}$ tal que para cada $n>m$, $0\leq r_f-\sum_{i=0}^{n}\frac{f(i)}{10^{i+1}}<\frac{1}{4\cdot10}$ y $0\leq r_f-\sum_{i=0}^{n}\frac{h(i)}{10^{i+1}}<\frac{1}{4\cdot10}$. Luego, $$|\sum_{i=0}^{m+1}\frac{f(i)}{10^{i+1}}-\sum_{i=0}^{m+1}\frac{h(i)}{10^{i+1}}|=|\sum_{i=0}^{m+1}\frac{f(i)}{10^{i+1}}-r_f+r_f-\sum_{i=0}^{m+1}\frac{h(i)}{10^{i+1}}|$$ $$\leq|\sum_{i=0}^{m+1}\frac{f(i)}{10^{i+1}}-r_f|+|r_f-\sum_{i=0}^{m+1}\frac{h(i)}{10^{i+1}}|<\frac{1}{4\cdot10}+\frac{1}{4\cdot10}=\frac{1}{2\cdot10}.$$ Por otro lado, $|\frac{f(0)-h(0)}{10}|-|\sum_{i=1}^{m+1}\frac{f(i)-h(i)}{10^{i+1}}|\leq|\sum_{i=0}^{m+1}\frac{f(i)-h(i)}{10^{i+1}}|<\frac{1}{2\cdot10}$ y así \[|\frac{f(0)-h(0)}{10}|<\frac{1}{2\cdot10}+|\sum_{i=1}^{m+1}\frac{f(i)-h(i)}{10^{i+1}}|\leq\frac{1}{2\cdot10}+\sum_{i=1}^{m+1}\frac{|f(i)-h(i)|}{10^{i+1}}.\] Dado que $|f(i)-h(i)|=\left\{\begin{array}{lcc}
1 & \textnormal{si}\ \{f(i),h(i)\}=\{0,1\}\\
0 & \textnormal{si}\ f(i)=h(i)=0\ \textnormal{o}\ f(i)=h(i)=1
\end{array}
\right.$ entonces, $|f(i)-h(i)|\leq1$ para cada $i\in\mathbb{N}$ y, como $\sum_{i=1}^{m+1}\frac{1}{10^{i+1}}=\sum_{i=2}^{m+2}\frac{1}{10^i}<\frac{1}{2\cdot10}$, se sigue que \[\frac{|f(0)-h(0)|}{10}\leq\frac{1}{2\cdot10}+\sum_{i=1}^{m+1}\frac{1}{10^{i+1}}<\frac{1}{10}\] lo cual implica que $|f(0)-h(0)|=0$, es decir, $f(0)=h(0)$. Supongamos que para algún $n\in\mathbb{N}$ hemos probado que $f(m)=h(m)$ para cada $m\leq n$ y veamos que $f(n+1)=h(n+1)$.
Sea $m\in\mathbb{N}$, $m\geq n+1$, tal que para cada $k>m$, $|r_f-\sum_{i=0}^{k}\frac{f(i)}{10^{i+1}}|<\frac{1}{4\cdot10^{n+2}}$ y $|r_f-\sum_{i=0}^{k}\frac{h(i)}{10^{i+1}}|<\frac{1}{4\cdot10^{n+2}}$.
Luego, $|\sum_{i=n+1}^{m+1}\frac{f(i)-h(i)}{10^{i+1}}|=|\sum_{i=0}^{m+1}\frac{f(i)-h(i)}{10^{i+1}}|\leq|r_f-\sum_{i=0}^{m+1}\frac{f(i)}{10^{i+1}}|+|r_f-\sum_{i=0}^{m+1}\frac{h(i)}{10^{i+1}}|<\frac{1}{2\cdot10^{n+2}}$. Por otro lado, \[\frac{|f(n+1)-h(n+1)|}{10^{n+2}}-|\sum_{i=n+2}^{m+1}\frac{f(i)-h(i)}{10^{i+1}}|\leq|\sum_{i=n+1}^{m+1}\frac{f(i)-h(i)}{10^{i+1}}|<\frac{1}{2\cdot10^{n+2}}\] por lo que $$\frac{|f(n+1)-h(n+1)|}{10^{n+2}}<\frac{1}{2\cdot10^{n+2}}+|\sum_{i=n+2}^{m+1}\frac{f(i)-h(i)}{10^{i+1}}|\leq\frac{1}{2\cdot10^{n+2}}+\sum_{i=n+2}^{m+1}\frac{|f(i)-h(i)|}{10^{i+1}}$$ \[\leq\frac{1}{2\cdot10^{n+2}}+\sum_{i=n+2}^{m+1}\frac{1}{10^{i+1}}=\frac{1}{2\cdot10^{n+2}}+\sum_{i=n+3}^{m+2}\frac{1}{10^i}<\frac{1}{2\cdot10^{n+2}}+\frac{1}{2\cdot10^{n+2}}=\frac{1}{10^{n+2}}\]
y en consecuencia, $|f(n+1)-h(n+1)|=0$, es decir, $f(n+1)=h(n+1)$. Por tanto, para cada $n\in\mathbb{N}$, $f(n)=h(n)$, lo que demuestra que $f=h$.
Así, la función $G$ es inyectiva y, por consiguiente, $|2^{\mathbb{N}}|\leq|[0,1)|$. Dado que $|[0,1)|=|(0,1)|$, se sigue que $|\mathcal{P}(\mathbb{N})|=|2^{\mathbb{N}}|\leq|(0,1)|$. Por el teorema de Cantor-Schröder-Bernstein concluimos que $|(0,1)|=|\mathcal{P}(\mathbb{N})|$.

$\square$

Concluimos la entrada con el siguiente corolario, cuya prueba es consecuencia del teorema anterior y el hecho que $|\mathbb{R}|=|(0,1)|$.

Corolario. $\mathbb{R}$ y $\mathcal{P}(\mathbb{N})$ son equipotentes.

$\square$

Tarea moral

  1. Demuestra que el conjunto $\mathbb{N}^{\nearrow\mathbb{N}}:=\{f\in\mathbb{N}^{\mathbb{N}}:f(n)<f(n+1)\ \textnormal{para cada}\ n\in\mathbb{N}\}$ es equipotente a $[\mathbb{N}]^{\mathbb{N}}$.
  2. Demuestra que para cualquier conjunto infinito $X$ que contenga un conjunto numerable se cumple que $|X\setminus A|=|X|$, para cada $A\subseteq X$ conjunto finito.
  3. Sean $a,b\in\mathbb{R}$ con $a<b$. Demuestra que $|(a,b)|=|(0,1)|$.
  4. Exhibe una biyección entre $\mathbb{R}$ y $[0,\infty):=\{r\in\mathbb{R}:r\geq0\}$.

Más adelante…

Entradas relacionadas

  1. Hernández, F., Teoría de Conjuntos, México: Aportaciones Matemáticas No.13,
    SMM, 1998 ↩︎
  2. Spivak, M., Cálculo Infinitesimal (2a ed). México: Reverté, 1998. ↩︎

Teoría de los Conjuntos I: Producto en los naturales

Por Gabriela Hernández Aguilar

4 respuestas

Introducción

Ahora que hemos definido a la suma en el conjunto de los naturales, podemos definir el producto, pues éste se refiere a sumar cierta cantidad de veces un mismo número. De este modo, el producto se definirá recursivamente en términos de la suma, así como la suma fue definida recursivamente en términos de la función sucesor.

Producto de naturales

Utilizando el teorema de recursión se puede mostrar, al igual que con la operación suma, que existe una única función $\cdot: \mathbb{N}\times\mathbb{N}\to \mathbb{N}$, denotada por $\cdot(m,n)=m\cdot n$, que satisface las siguientes condiciones:

  1. $0\cdot n=0$ para cualquier $n\in \mathbb{N}$,
  2. $s(m)\cdot n= (m\cdot n)+n$.

Dado que seguimos trabajando con conjuntos y hemos definido una nueva operación binaria, podemos preguntarnos si esta operación conmuta, es asociativa o si cumple alguna otra propiedad tal como lo hace el producto cartesiano y la suma en los naturales. Además veremos que esta operación se distribuye con la suma.

Distributividad del producto sobre la suma

Teorema. Para cualesquiera $m,n,k\in \mathbb{N}$, se tiene que $m\cdot(n+k)=m\cdot n+ m\cdot k$.

Demostración. Procederemos por inducción sobre $m$ y dejaremos fijos a $n$ y $k$.

Base de inducción. Si $m=0$, $0\cdot(n+k)=0=0+0=(0\cdot n)+(0\cdot k)$.

Hipótesis de inducción. Supongamos que se cumple para $m$, es decir, $m\cdot(n+k)= (m\cdot n)+(m\cdot k)$.

Paso inductivo. Veamos que se cumple para $m+1$, es decir, $(m+1)\cdot(n+k)=(m+1)\cdot n+(m+1)\cdot k$.

\begin{align*}
(m+1)\cdot (n+ k)&=m\cdot (n+ k)+(n+ k) \tag{Definición $\cdot$}\\
&= (m\cdot n+m\cdot k)+(n+ k) \tag{Hipótesis de inducción}\\
&= ((m\cdot n)+n)+((m\cdot k)+k)\tag{Conmutatividad y asociatividad de $+$}\\
&= (m+1)\cdot n+(m+1)\cdot k \tag{Definición $\cdot$}.
\end{align*}

Por lo tanto, $m\cdot(n+k)=m\cdot n+m\cdot k$ para cualesquiera $m, n, k\in \mathbb{N}$.

$\square$

Conmutatividad del producto

Para demostrar que el producto es conmutativo primero vamos a demostrar los siguientes lemas:

Lema 1. Para cualquier $n\in \mathbb{N}$, se tiene que $n\cdot 0=0$.

Demostración.

Procederemos por inducción sobre $n$.

Base de inducción. Si $n=0$, tenemos que $0\cdot 0=0$.

Hipótesis de inducción. Supongamos que para algún $k\in \mathbb{N}$ se satisface que $k\cdot 0=0$.

Paso de inductivo. Veamos que se cumple para $k+1$, es decir, $(k+1)\cdot 0=0$.

\begin{align*}
(k+1)\cdot 0 &=(k\cdot 0)+0\tag{Definición $\cdot$}\\
&= 0+0\tag{Hipótesis de inducción}\\
&= 0\tag{Propiedad $+$}.
\end{align*}

Por lo tanto, $n\cdot 0=0$, para cualquier $n\in \mathbb{N}$.

$\square$

Lema 2. Para cualquier $n\in \mathbb{N}$, se tiene que $n\cdot 1=n$.

Demostración.

Procederemos por inducción sobre $n$.

Base de inducción. Si $n=0$, tenemos que $0\cdot 1= 0$ por la definición de $\cdot$.

Hipótesis de inducción. Supongamos que para algún $k\in \mathbb{N}$ se satisface que $k\cdot 1=k$.

Paso de inductivo. Veamos que se cumple para $k+1$, es decir, $(k+1)\cdot 1=k+1$.

\begin{align*}
(k+1)\cdot 1&=(k\cdot 1)+1\tag{Definición $\cdot$}\\
&= k+1. \tag{Hipótesis de Inducción}
\end{align*}

Por lo tanto, para cualquier $n\in \mathbb{N}$, $n\cdot 1=n$.

$\square$

Teorema. Para cualesquiera $m,n\in \mathbb{N}$, $n\cdot m=m\cdot n$.

Demostración.

Por inducción sobre $m$.

Base de inducción. Si $m=0$, entonces $0\cdot n=0=n\cdot 0$, por el Lema 1.

Hipótesis de inducción. Supongamos que para $k$ se cumple que $n\cdot k=k\cdot n$.

Paso inductivo. Veamos que para $k+1$ se satisface que $n\cdot (k+1)= (k+1)\cdot n$.

\begin{align*}
(k+1)\cdot n&= (k\cdot n)+n\tag{Definición $+$}\\
&= (n\cdot k)+n\tag{Hipótesis de Inducción}\\
&= (n\cdot k)+(n\cdot 1) \tag{Lema 2}\\
&= n\cdot (k+1) \tag{Distributividad}.
\end{align*}

Por lo tanto, $\cdot$ es conmutativo.

$\square$

Asociatividad del producto

Teorema. Para cualesquiera $m,n,k\in \mathbb{N}$, se tiene que $m\cdot(n\cdot k)=(m\cdot n)\cdot k$.

Demostración. Procederemos por inducción sobre $m$ y dejaremos fijos a $n$ y $k$.

Base de inducción. Si $m=0$, $0\cdot(n\cdot k)=0=0\cdot k = (0\cdot n)\cdot k$.

Hipótesis de inducción. Supongamos que se cumple para $m$, es decir, $m\cdot(n\cdot k)= (m\cdot n)\cdot k$.

Paso inductivo. Veamos que se cumple para $m+1$, es decir, $(m+1)\cdot(n\cdot k)=((m+1)\cdot n)\cdot k$.

\begin{align*}
(m+1)\cdot (n\cdot k)&=(m\cdot (n\cdot k))+(n\cdot k) \tag{Definición $\cdot$}\\
&= ((m\cdot n)\cdot k)+(n\cdot k) \tag{Hipótesis de inducción}\\
&=(k\cdot(m\cdot n))+(k\cdot n) \tag{Conmutatividad del producto}\\
&=k\cdot(m\cdot n+n) \tag{Distributividad}\\
&= (m\cdot n+n)\cdot k\tag{Conmutatividad del producto}\\
&= ((m+1)\cdot n)\cdot k\tag{Definición $\cdot$}.
\end{align*}

Por lo tanto, $\cdot$ es asociativa.

$\square$

Ley de cancelación

En álgebra, cuando tenemos una ecuación como la siguiente #$x\cdot z=y\cdot z,$$ siempre que $z\not=0$, concluimos que $x=y$. Esto tiene una justificación y la llamaremos ley de cancelación para el producto. En los naturales se cumple esta ley.

Teorema. Sean $n, m, k\in \mathbb{N}$ con $k\not=0$. Si $n\cdot k=m\cdot k$, entonces $n=m$.

Para probar dicho teorema, utilizaremos la siguiente serie de resultados.

Proposición. Si $n,m\in\mathbb{N}$ son tales que $n\leq m$, entonces, existe $t\in\mathbb{N}$ tal que $n+t=m$.

Demostración (Proposición).

Mostraremos por inducción sobre $m$ que para todo $n\leq m$, existe $t_n\in \mathbb{N}$ tal que $n+t_n=m$.

Base de inducción. $k=0$. Si $n\leq 0$, entonces $n=0$, pues recordemos que dos números naturales $n$ y $m$ satisfacen $n\leq m$ si, y sólo si, $n\in m$ o $n=m$. Así, si $n\leq 0$, entonces $n\in 0$ o $n=0$, pero dado que el enunciado $n\in 0$ no puede ser cierto pues $0=\emptyset$ no tiene elementos, se sigue que $n=0$ tiene que ser verdadero. De este modo, si $n\leq 0$, entonces $n=0$ y tomando $t=0$ se tiene que $n+t=0+0=0$. Por lo tanto, para todo $n\leq 0$ existe $t_n\in\mathbb{N}$ tal que $n+t_n=0$. Por lo tanto, la proposición es cierta para $k=0$.

Hipótesis de inducción. Supongamos que para algún $k\in\mathbb{N}$ se satisface que para todo $n\leq k$, existe $t_n\in\mathbb{N}$ tal que $n+t_n=k$.

Paso inductivo. Veamos que se cumple para $s(k)$. Sea $n\leq s(k)$. Luego, $n\in s(k)$ o $n=s(k)$. Si $n=s(k)$, entonces tomamos $t=0$ y se tiene que $n+t=s(k)+0=s(k)$. Supongamos ahora que $n\in s(k)$.

Como $n\in s(k)$, entonces $n=k$ o $n\in k$, es decir, $n\leq k$. Luego, por hipótesis de inducción, existe $t_n\in\mathbb{N}$ tal que $n+t_n=k$. De este modo, si tomamos $s(t_n)\in\mathbb{N}$ se tiene que $n+s(t_n)=s(t_n)+n=s(t_n+n)=s(k)$.

En cualquier caso para $n$ hemos concluido que existe $t_n\in\mathbb{N}$ tal que $n+t_n=s(k)$.

Por lo tanto, la proposición es verdadera.

$\square$

Proposición. Si $n\in\mathbb{N}$, entonces $n\leq n+t$ para todo $t\in\mathbb{N}$.

Demostración (Proposición).

Sea $n\in\mathbb{N}$. Probaremos por inducción sobre $t$ que $n\leq n+t$ para todo $t\in\mathbb{N}$.

Base. $t=0$. Para $t=0$ tenemos que $n+t=n+0=n$, por lo que es verdad que $n\leq n+t$.

Hipótesis de inducción. Supongamos que para algún $t\in\mathbb{N}$, $n\leq n+t$.

Bajo esta hipótesis veamos que $n\leq n+s(t)$. Primero, notemos que $n+s(t)=s(t)+n$ por la conmutatividad de la suma. Luego, por definición de la suma, $s(t)+n=s(t+n)$. Dado que $s(t+n)=(t+n)\cup\set{t+n}$, entonces $n+t\in s(t+n)$. Ahora bien, por hipótesis de inducción, $n\leq n+t$, es decir, $n=n+t$ o $n\in n+t$. Si $n=n+t$, entonces $n\in s(n+t)$, ya que $n+t\in s(n+t)$, por lo que $n\leq s(n+t)=n+s(t)$.

Ahora, si $n\in n+t$, entonces, $n\in s(n+t)$ por transitividad de la pertenencia en los naturales, por lo que también se cumple que $n\leq n+s(t)$.

En cualquier caso concluimos que $n\leq n+s(t)$, lo que concluye la prueba de la proposición.

$\square$

El último resultado que veremos, antes de iniciar con la demostración de la ley de la cancelación del producto, dice lo siguiente:

Corolario. Si $n\in\mathbb{N}$ es distinto de $0$, entonces $n+t$ es distinto de $0$ para todo $t\in\mathbb{N}$.

Demostración (Corolario).

Sea $n\in\mathbb{N}$ distinto de $0$ y supongamos que $t\in\mathbb{N}$ es arbitrario. Por la proposición anterior, $n\leq n+t$, es decir, $n=n+t$ o $n\in n+t$. Si $n=n+t$, entonces $n+t$ es distinto de $0$ por la hipótesis sobre $n$. Si ahora $n\in n+t$, entonces $n+t$ es distinto de $0$, pues $n+t$ tiene un elemento, el cual es $n$, mientras que el $0$ no tiene elementos. Esto concluye la prueba.

$\square$

Ya que contamos con esta serie de resultados previos podemos dar la demostración de la ley de cancelación del producto.

Demostración (Ley de cancelación del producto).

Supongamos que $n\cdot k = m\cdot k$ con $k \neq 0$. Como el orden $\leq$ es un buen orden en $\mathbb{N}$, entonces es total. Así, $n\leq m$ o $m\leq n$. Haremos el caso $n\leq m$ pues el otro caso es análogo. Como $n\leq m$, existe un natural $t$ tal que $n+t=m$. Como $k\neq 0$, existe un natural $s$ tal que $k=s+1$. De esta manera,

\begin{align*}
ns+n &= n(s+1)\\
&=nk\\
&=mk\\
&=(n+t)(s+1)\\
&=ns+n+ts+t.
\end{align*}

En esta cadena de igualdades hemos usado las propiedades que ya hemos probado de la suma y el producto. Usando ahora la ley de cancelación de la suma, obtenemos que $0=ts+t$. Como aquí hay una suma de naturales igualada a cero, cada sumando es igual a cero. En particular, $t=0$ y por lo tanto $m=n+0=n$, como queríamos.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta sección:

  1. Demuestra que existe una única función $\cdot: \mathbb{N}\times\mathbb{N}\to \mathbb{N}$, denotada por $\cdot(m,n)=m\cdot n$, que satisface las siguientes condiciones:
    – $0\cdot n=0$ para cualquier $n\in \mathbb{N}$,
    – $s(m)\cdot n= (m\cdot n)+n$.
  2. Demuestra que para cualesquiera $m,n,l\in \mathbb{N}$ tal que $l\not=0$, si $m<n$, entonces $l\cdot m<l\cdot n$.
  3. Demuestra que para cualesquiera $m,n\in \mathbb{N}$, si $m\cdot n=0$, entonces $m=0$ o $n=0$.
  4. Usa el teorema de recursión para probar la existencia y unicidad de una función $F:\mathbb{N}\to \mathbb{N}$ que satisfaga lo siguiente:
    $F(0)=1$,
    $F(1)=1$,
    $F(2)=2\cdot 1$,
    $\vdots$
    $F(n)=n\cdot (n-1)\cdots 2\cdot 1$.
    A la función $F$ se le llama el factorial y la denotamos por $F(n)=n!$.
  5. Usa el teorema de recursión y unicidad para probar para cada natural $n$ la existencia de una función $w_n:\mathbb{N}\to \mathbb{N}$ que cumple $w_n(0)=1$ y $w_n(m+1)=n\cdot w_n(m)$. Usa las funciones $w_n$ para definir la exponenciación en $\mathbb{N}$ como la operación binaria de $\mathbb{N}$ en $\mathbb{N}$ denotada por $n^m=w_n(m)$. Prueba que la exponenciación cumple las siguientes propiedades:
    • Para todo natural $m>0$, se cumple que $0^m=0$ y $1^m=1$.
    • Para cualesquiera naturales $l,m,n$, se cumple que $(m\cdot n)^l=m^l\cdot n^l$, que $l^{m+n}=l^m\cdot l^n$ y que $(l^m)^n=l^{m\cdot n}$.
  6. Encuentra todas las soluciones en los naturales a la ecuación $m^2+n=n^2+m$. ¡Ten cuidado! En $\mathbb{N}$ todavía no hemos definido la resta, así que como primer paso no puedes «pasar restando». Todos tus argumentos tendrán que permanecer en lo que hemos construido de $\mathbb{N}$.

Más adelante…

Con esta entrada concluimos el contenido acerca de números naturales. Es lo único que haremos en este curso sobre la construcción de sistemas numéricos, pero todos estos conocimientos sirven para constuir a los enteros y los racionales. Puedes hacer clic en los enlaces para consultar el contenido de la construcción de los números enteros y de los números racionales que se encuentra en el curso de Álgebra Superior II.

Nuestro enfoque continuará siendo conjuntista, y ahora nos enfocaremos en la noción de que dos conjuntos «tengan la misma cantidad de elementos». Así, en la siguiente unidad hablaremos acerca de equipotencia, finitud, infinitud, dominancia y aritmética cardinal. El conjunto de los números naturales jugará un papel clave para esta teoría.

Entradas relacionadas

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»

Teoría de los Conjuntos I: Principio de inducción

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta entrada hablaremos acerca del principio de inducción. Será de gran importancia pues una vez que lo demostremos, se podrá utilizar como método de demostración para proposiciones cuyo enunciado depende de un número natural. En otras palabras, el principio de inducción nos ayudará a demostrar que ciertas proposiciones o propiedades se cumplen para cualquier natural $n$.

Principio de inducción1

El principio de inducción dice lo siguiente.

Teorema. Sea $P(n)$ una proposición (como las que se vieron en la primera unidad) que depende de un número natural $n$. Supongamos que las siguientes dos cosas son ciertas.

  1. $P(0)$ se cumple.
  2. Para cualquier $n\in \mathbb{N}$, si $P(n)$ es verdadero, entonces $P(s(n))$ también es verdadero.

Entonces, $\set{n\in \mathbb{N}:P(n)}=\mathbb{N}$, es decir, la proposición es cierta para cualquier número natural $n$.

Demostración.

Tomemos $P(n)$ una propiedad. Si se cumplen 1) y 2), entonces

$A=\set{n\in \mathbb{N}: P(n)}$

es un conjunto inductivo.

En la entrada anterior probamos que cualquier conjunto inductivo contiene a los naturales. Así, $\mathbb{N}\subseteq A$.

Además, $A\subseteq \mathbb{N}$ pues para cualquier $n\in A$, $n\in \mathbb{N}$ y por lo tanto, $A=\mathbb{N}$.

$\square$

Para entender este teorema, podemos imaginar una fila con tantas fichas de dominó como números naturales, como en la imagen. Hay una primera ficha. Para cualquier ficha hay una siguiente. ¿Qué necesitamos para garantizar que se caigan todas las fichas mediante el «efecto dominó»?

Por Leonardo Martínez con Stable Difussion

Podemos interpretar al teorema como sigue. Tomemos informalmente la proposición $P(n):$»el dominó $n$ cae». Lo que nos diría el punto 1) del principio de inducción es que la ficha correspondiente a cero. Lo que nos diría el punto 2) del principio de inducción es que tenemos la garantía de que para cualquier natural $n$ «si el dominó $n$ se cae, entonces el dominó $n+1$ también», por ejemplo, porque el dominó $n$ y $n+1$ están suficientemente cerca como para que el dominó $n$ empuje al $n+1$ al caer. Lo que garantizaría el principio de inducción es que todas las fichas caerán.

Orden de los naturales

A continuación definiremos una relación en el conjunto de números naturales, la cual resultará ser una relación de orden, pero esto último lo probaremos en la próxima entrada.

Definición. Sean $n,m\in \mathbb{N}$. Decimos que $n\leq m$ si y sólo si $n\in m$ o $n=m$.

Ejemplos.

  • $0=\emptyset$ y $1=\set{\emptyset}$ son números naturales. Luego, $0\leq 1$ pues $\emptyset\in \set{\emptyset}$.
  • $0=\emptyset$ y $2=\set{\emptyset, \set{\emptyset}}$ son números naturales. Luego, $0\leq 2$ pues $\emptyset\in \set{\emptyset, \set{\emptyset}}$.
  • $1=\set{\emptyset}$ y $2=\set{\emptyset, \set{\emptyset}}$ son números naturales. Luego, $1\leq 2$ pues $\set{\emptyset}\in \set{\emptyset, \set{\emptyset}}$.

$\square$

A continuación veremos un ejercicio en el que usaremos la relación que definimos arriba y el principio de inducción.

Proposición. $0\leq m$ para cualquier $m\in \mathbb{N}$.

Demostración.

Debemos probar que $\set{m\in \mathbb{N}: 0\leq m}=\mathbb{N}$. Procederemos usando el principio de inducción.

  • $0\leq 0$ pues $0=0$.
  • Ahora, si $0\leq m$ para algún $m\in \mathbb{N}$, veamos que $0\leq s(m)$. Dado que $0\leq m$, $0=m$ ó $0\in m$. Consecuentemente, $0\in s(m)$, es decir, $0\leq s(m)$.

Por lo tanto, $\set{m\in\mathbb{N}:0\leq m}=\mathbb{N}$.

$\square$

Tarea moral

  1. Demuestra que la relación $\leq$ que definimos en esta entrada es un orden parcial.
  2. Demuestra que cualesquiera naturales $n$ y $m$ son $\leq$-comparables, aplicando inducción sobre $n$. ¿Puedes dar una demostración alternativa que use un resultado de la entrada?
  3. Demuestra que para todo natural $n\not=0$, existe un natural $k$ tal que $n=s(k)$.
  4. Demuestra que para cualquier $n\in \mathbb{N}\setminus \set{0,1}$, existe $k\in \mathbb{N}$ tal que $n=s(s(k))$.
  5. Muestra que $\mathbb{N}$ no tiene máximo con el orden $\leq$ que hemos definido.

Más adelante…

En la siguiente entrada probaremos que el conjunto de los naturales con el orden que hemos definido en esta entrada es un buen orden.

Entradas relacionadas

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»

  1. Puedes consultar más contenido acerca del principio de inducción en el siguiente libro: Hrbacek, Karel y Jech, Thomas, Introduction to Set Theory, Marcel Dekker Inc. 1984, p. 42-44. ↩︎

Teoría de los Conjuntos I: Sucesor

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta nueva entrada hablaremos acerca del sucesor de un número natural. Este concepto nos permitirá definir un poco más adelante qué son los conjuntos inductivos, que simultáneamente nos dará un método de demostración muy versátil, y conectará nuestro estudio de los números naturales con el de los conjuntos infinitos.

Sucesor

La noción que estudiaremos ahora es la siguiente.

Definición. Sea $x$ un conjunto. Definimos al sucesor de $x$ como $s(x)=x\cup \set{x}$.

Ejemplos.

  • El sucesor de $\emptyset$ es $s(\emptyset)=\emptyset\cup \set{\emptyset}=\set{\emptyset}$.
  • El sucesor de $\set{\emptyset}$ es $s(\set{\emptyset})=\set{\emptyset}\cup \set{\set{\emptyset}}=\set{\emptyset, \set{\emptyset}}$.
  • Luego, el sucesor de $\set{\emptyset, \set{\emptyset}}$ es $s(\set{\emptyset, \set{\emptyset}})=\set{\emptyset,\set{\emptyset}}\cup \set{\set{\emptyset, \set{\emptyset}}}=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$.
  • El sucesor de $\set{\set{\emptyset}}$ es $s(\set{\set{\emptyset}})=\set{\set{\emptyset}}\cup \set{\set{\set{\emptyset}}}= \set{\set{\emptyset}, \set{\set{\emptyset}}}$.

$\square$

La noción de sucesor está definida para cualquier conjunto. Pero dado que en esta unidad únicamente estaremos trabajando con números naturales, prácticamente nos limitaremos a usar la definición de sucesor para conjuntos que son números naturales. En este caso sucede algo especial: si $n$ es un número natural, entonces $s(n)$ también lo es. Vamos a demostrar esto, pero antes demostraremos algunos lemas que nos serán de utilidad.

Unos lemas sobre la pertenencia

A continuación probaremos algunos resultados sobre la pertenencia de números naturales en sí mismos y de unos en otros. Cuando los leas, te darás cuenta de que ya habíamos demostrado resultados similares y más generales en la entrada del axioma de buena fundación. Sin embargo, nota que en las siguientes demostraciones no es necesario utilizar este axioma, pues la definición de número natural nos da todo lo que necesitamos.

Lema 1. Para cualquier número natural $n$, no es posible que $n\in n$.

Demostración.

Sea $n$ un número natural. Entonces $\in_n$ es un orden total estricto para $n$. Si sucediera que $n\in n$, entonces tendríamos una contradicción pues tendríamos $n\in_n n$ y $n\in_n n$, lo que contradice la asimetría de $\in_n$. Así, $n\not \in n$.

$\square$

Lema 2. Si $n$, $m$ son números naturales, entonces no es posible que $n\in m$ y $m\in n$ al mismo tiempo.

Demostración.

Sean $n$ y $m$ números naturales. Si $n\in m$ y $m\in n$, entonces $n\in n$ pues $n$ es conjunto transitivo. Esto contradice el lema anterior.

Por lo tanto, no es posible que $n\in m$ y $m\in n$ al mismo tiempo.

$\square$

Así, hemos logrado hacer estas demostraciones sin recurrir al axioma de buena fundación. Como comentario tangencial, en teoría de los conjuntos no sólo resulta de interés probar resultados que se deducen de los axiomas, sino que a veces también es interesante identificar realmente cuáles son los «axiomas suficientes» para tener algún resultado de la teoría. Nos encontraremos nuevamente con preguntas de este estilo cuando hablemos del axioma de elección.

El sucesor de un natural

Ahora que demostramos los lemas anteriores, estamos listos para probar que el sucesor de un número natural es un número natural.

Teorema. Si $n$ es un número natural, entonces $s(n)$ es un número natural.

Demostración.

Sea $n$ un número natural. Veamos que $s(n)$ es un número natural. Para ello tenemos que probar todo lo siguiente:

  • $s(n)$ es transitivo.
  • $\in_{s(n)}$ es un orden total estricto en $s(n)$.
  • Cualquier $B\subseteq s(n)$ no vacío tiene mínimo y máximo con respecto a $\in_{s(n)}$.

A continuación hacemos todo esto.

$s(n)$ es transitivo.

Sea $y\in s(n)=n\cup\set{n}$. Si $y\in n$, dado que $n$ es un número natural, entonces $n$ es transitivo y por lo tanto, $y\subseteq n$. Así, $y\subseteq n\cup\set{n}$. Si $y\in \set{n}$, entonces $y=n$ y en particular, $y\subseteq n$ y así, $y\subseteq n\cup\set{n}$. En cualquier caso, $y\subseteq s(n)$. Por lo tanto, $s(n)$ es un conjunto transitivo.

$\in_{s(n)}$ es un orden total estricto en $s(n)$.

Para esta parte debemos probar que $\in_{s(n)}$ es una relación asimétrica, transitiva y que cualquiera dos elementos de $s(n)$ son $\in_{s(n)}$ comparables.

Veamos que $\in_{s(n)}$ es asimétrica. Sean $y,z\in s(n)$. Como $y\in s(n)=n\cup \{n\}$, entonces o bien $y=n$, y entonces $y$ es natural, o bien $y\in n$, y entonces $y$ es natural por el teorema de la entrada anterior. De manera análoga, $z$ es natural. Por el Lema 2 de esta entrada, es imposible que $y \in_{s(n)} z$ y $z \in_{s(n)} y$ simultáneamente, por lo que $\in_{s(n)}$ es asimétrica.

Antes de ver que la relación es transitiva, veamos que cualesquiera dos elementos son comparables. Tomemos $y,z \in s(n)$ arbitrarios. Si ambos están en $n$, entonces como $\in_n$ es total, tenemos que o $y\in_n z$, o $y=z$, o $z\in_n y$. Respectivamente tendríamos que $y\in_{s(n)} z$, o $y=z$, o $z\in_{s(n)} y$. Si ambos están en $\{n\}$, entonces $y=n=z$ y así $y=z$. Si $y$ está en $n$ y $z$ está en $\{n\}$, entonces $z=n$ y por lo tanto $y\in z$, de donde $y\in_{s(n)} z$. Si $z$ está en $n$ y $y$ está en $\{n\}$, entonces $y=n$ y por lo tanto $z\in_{s(n)} y$, de donde $z\in_{s(n)} y$.

Para terminar de ver que $\in_{s(n)}$ es un orden total estricto, falta ver que es una relación transitiva. Para ello tomemos $w,y,z\in s(n)$ arbritarios tales que $w\in_{s(n)} y$ y $y\in_{s(n)} z$ y veamos que $w\in_{s(n)} z$. De acuerdo a en dónde están $w,y,z$ en $s(n)=n\cup \{n\}$, tenemos 8 casos. Pero podemos reducirlos a las siguientes tres posibilidades.

  • $w,y,z\in n$, en cuyo caso se da $w\in_n z$ por transitividad de $\in_n$, y así $w\in_{s(n)} z$.
  • Exactamente uno de $w,y,z$ es igual a $n$. No se puede $w=n$ pues llegamos a la contradicción $n=w\in y$ (por nuestra suposición) y $y\in n$ (pues exactamente hay uno igual a $n$). Análogamente, tampoco se puede $y=n$ pues llegamos a la contradicción $n\in z$ y $z\in n$. Así, sólo puede ser $z$, pero entonces $w\in n=z$, de donde $w\in_{s(n)} z$.
  • Al menos dos de $w,y,z$ es igual a $n$. Este caso es imposible pues lleva o bien a una contradicción del estilo $n\in n$ (cuando $w=n=y$ o $y=n=z$), o bien a la contradicción $n\in y \in n$.

Lo anterior cubre todos los casos para mostrar que la relación es transitiva. Hemos entonces mostrado que $\in_{s(n)}$ es un orden total y estricto para $s(n)$.

Cualquier $B\subseteq s(n)$ no vacío tiene mínimo y máximo con respecto a $\in_{s(n)}$.

Supongamos que $B$ conjunto no vacío es subconjunto de $s(n)$ y veamos que $B$ tiene máximo y mínimo.

Caso 1: Si $B\subseteq \set{n}$, como $B\not=\emptyset$ entonces $B=\set{n}$.

Luego, $n=\min (B)$ pues se satisface que para cualquier $y\in B\setminus \set{n}=\emptyset$, se tiene que $n\in y$ por vacuidad.

Finalmente, $n=\max (B)$ pues se satisface que para cualquier $y\in B\setminus \set{n}=\emptyset$, se tiene que $y\in n$ por vacuidad.

Caso 2: Si $B\subseteq n$, entonces $B$ es un subconjunto no vacío de $n$, así que tiene un mínimo $a$ y un máximo $b$ con respecto a $\in_n$, que son a la vez mínimo y máximo con respecto a $\in_{s(n)}$.

Caso 3: Si no pasa que $B\subseteq \set{n}$, ni $B\subseteq n$, entonces hay elementos de $B$ en $\set{n}$ y en $n$. Así, $n\in B$ y podemos definir $a$ como el mínimo de $B\cap n$. Afirmamos que $n=\max(B)$ y $a=\min(B)$.

En efecto, todo $y\in B\setminus\{n\}$ está en $n$ y por lo tanto $y\in_{s(n)} n$. Además, si tomamos $z\in B\setminus \{a\}$, entonces hay dos posibilidades. O bien $z=n$, que acabamos de ver que cumple $a\in_{s(n)} n$. O bien $z\in n$, pero entonces $z\in B\cap n$ y como $a$ es mínimo de $B\cap n$, tenemos entonces $a\in_n z$ y por lo tanto $a\in_{s(n)} z$.

Con esto terminamos de demostrar todo lo que necesitábamos para ver que $s(n)$ es un natural.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá aprender otras propiedades del sucesor de un número natural:

  1. Describe al sucesor del natural $\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}, \set{\emptyset, \set{\emptyset},\set{\emptyset, \set{\emptyset}}}}$.
  2. Sean $x$ y $y$ conjuntos cualesquiera. Demuestra que si $s(x)=s(y)$, entonces $x=y$.
  3. Prueba que para cualquier natural $n$ se cumple que $\bigcup s(n)=n$.
  4. Sea $x$ un conjunto. Demuestra que $x$ y $s(x)$ son conjuntos distintos. ¿Será siempre cierto que $x$ y $s(s(x))$ son conjuntos disintos? En caso de que sí, da una prueba. En caso de que no, da un contraejemplo.

Más adelante…

En la siguiente entrada definiremos a los conjuntos inductivos. Tales conjuntos nos darán la base para definir al conjunto de los números naturales. Además hablaremos de un nuevo axioma: el axioma del infinito.

Entradas relacionadas

En los siguientes enlaces podrás repasar el contenido acerca de 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 II: Introducción a estructuras algebraicas

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

Finalmente terminamos de construir a los números naturales, sus operaciones y su orden. El siguiente conjunto que nos interesa construir es $\mathbb{Z}$, el conjunto de los números enteros. Haremos esto en breve. Sin embargo, primero haremos un paréntesis para hablar de estructuras algebraicas.

Quizás hayas escuchado hablar de varias de ellas. En cálculo y geometría analítica se habla de los números reales y se comenta que es muy importante que sea un campo. En geometría moderna se habla de transformaciones geométricas y cómo algunas de ellas forman un grupo. También es común escuchar de los anillos de enteros o de polinomios (que estudiaremos más adelante). Y por supuesto, también están los espacios vectoriales, que están fuertemente conectados con resolver sistemas de ecuaciones lineales y hacer cálculo y geometría en altas dimensiones.

Todos estos conceptos (campos, grupos, anillos, espacios vectoriales, etc.) son ejemplos de estructuras algebraicas. Cada tipo de estructura algebraica es muy especial por sí misma y sus propiedades se estudian por separado en distintas materias, notablemente aquellas relacionadas con el álgebra moderna. La idea de esta entrada es dar una muy breve introducción al tema, para que te vayas acostumbrando al uso del lenguaje. Esto te servirá más adelante en tu formación matemática.

Intuición de estructuras algebraicas

De manera intuitiva, una estructura algebraica consiste de tomar un conjunto, algunas operaciones en ese conjunto, y ciertas propiedades que tienen que cumplir las operaciones. Eso suena mucho a lo que hemos trabajado con $\mathbb{N}$: es un conjunto, con las operaciones de suma y producto. Y ya demostramos que estas operaciones tienen propiedades especiales como la conmutatividad, la distributividad y la existencia de neutros.

En realidad podríamos tomar cualquier conjunto y cualquier operación y eso nos daría una cierta estructura.

Ejemplo. Consideremos el conjunto $\mathbb{N}$ con la operación binaria $\star$ tal que $$a\star b=ab+a+b.$$ Tendríamos entonces que $$3\star 1=3\cdot 1+3+1= 7,$$ y que $$10\star 10=10\cdot 10 + 10 + 10 = 120.$$

Es posible que la operación $\star$ tenga ciertas propiedades especiales, y entonces algunas proposiciones matemáticas interesantes consistirían en enunciar las propiedades de $\star$.

$\triangle$

Aunque tenemos mucha libertad en decidir cuál es el conjunto, cuáles son las operaciones que le ponemos y qué propiedades vamos a pedir, hay algunos ejemplos que se aparecen muy frecuentemente en las matemáticas. Aparecen de manera tan frecuente, que ameritan nombres especiales. Comencemos a formalizar esto.

Operaciones binarias y magmas

Dado un conjunto $S$, una operación binaria toma parejas de elementos de $S$ y los lleva a otro elemento de $S$. En símbolos, es una función $\star: S\times S\to S$. Cuando usamos la notación de función, tendríamos que escribir todo el tiempo $\times(a,b)$ para referirnos a lo que esta operación le hace a cada pareja de elementos $a$ y $b$ en $S$. Sin embargo, esto resulta poco práctico, y es por esta razón que se usa mucho más la notación $a\times b:=\times (a,b)$.

Ejemplo. En $\mathbb{N}$ ya definimos la operación binaria $+$, que toma dos enteros $a$ y $b$ y los manda a $s_a(b)$, donde $s_a:\mathbb{N}\to \mathbb{N}$ es la función que construimos usando el teorema de recursión estableciendo que $s_a(0)=a$ y $s_a(\sigma(n))=\sigma(s_a(n))$.

$\triangle$

Aquí lo único que nos importa es establecer una operación binaria. No nos importa si tiene otras propiedades adicionales.

Definición. Un magma consiste de un conjunto $S$ con una operación binaria $\ast$.

Otros ejemplos de magma son $\mathbb{N}$ con la operación que dimos en la parte de intuición, o bien $\mathbb{N}$ con el producto que ya definimos. También podemos tener magmas en conjuntos que no sea el de los enteros. Por ejemplo, si $P$ es el conjunto de subconjuntos de $\{0,1,2,3,4\}$, y le damos la operación que manda $A$ y $B$ a $A\cup B\cup \{0\}$, entonces también obtenemos un magma.

Conmutatividad

Cuando tenemos un conjunto $S$ y una operación binaria $\star$ en $S$, puede suceder que de lo mismo hacer $a\star b$ que $b\star a$. Esto ya es una propiedad especial que pueden cumplir las operaciones binarias, y tiene un nombre.

Definición. Decimos que una operación binaria $\star$ en un conjunto $S$ es conmutativa si para cualesquiera dos elementos $a$ y $b$ de $S$ se cumple que $a\star b=b\star a$.

Observa que la igualdad debe suceder para cualesquiera dos elementos. Basta con que falle para una pareja para que la operación ya no sea conmutativa.

Ejemplo. Una de las propiedades que demostramos de la operación de suma en $\mathbb{N}$ es que $s_a(b)=s_b(a)$, es decir, que $a+b=b+a$. En otras palabras, la operación binaria $+$ en $\mathbb{N}$ es conmutativa. Así mismo, vimos que el producto era conmutativo, es decir, que $p_a(b)=p_b(a)$, que en términos de la operación binaria $\cdot$ quiere decir que $a\cdot b=b\cdot a$.

$\triangle$

Más adelante veremos que otras funciones de suma y producto también son conmutativas, por ejemplo, las de los enteros, racionales, reales y complejos. Sin embargo, hay algunas operaciones binarias muy importantes en matemáticas que no son conmutativas. Un ejemplo de ello es el producto de matrices. Otro ejemplo es la diferencia de conjuntos.

Ejemplo. Si $P$ es el conjunto de subconjuntos de $\{0,1,2,3,4\}$ y le damos la operación binaria $\setminus$ tal que dados $A$ y $B$ en $P$ los manda a $A\setminus B$, entonces obtenemos un magma. Sin embargo, la operación $\setminus$ no es conmutativa pues, por ejemplo, $$\{1,2,3\}\setminus\{2,3,4\}=\{1\},$$ pero $$\{2,3,4\}\setminus\{1,2,3\}=\{4\}.$$

$\triangle$

En $\mathbb{N}$ no tenemos una operación de resta, como discutiremos en breve. Pero en el conjunto de los enteros sí, y ese sería otro ejemplo de una operación que no es conmutativa.

Asociatividad y semigrupos

Otra de las propiedades importantes que demostramos de la suma y producto de naturales es que son operaciones asociativas. En general, podemos definir la asociatividad para una operación binaria como sigue.

Definición. Sea $\star$ una operación binaria en un conjunto $S$. Decimos que $\star$ es asociativa si $a\star (b\star c)=(a\star b)\star c$ para cualesquiera tres elementos $a,b,c$ de $S$.

Tanto la suma como el producto de naturales dan una operación asociativa pues ya demostramos que si $a,b,c$ son naturales, entonces $a+(b+c)=(a+b)+c$ y $a(bc)=(ab)c$. Esta propiedad también la tendremos para la suma y producto de enteros, racionales, reales, complejos, polinomios, etc.

A partir de la asociatividad podemos definir la primer estructura algebraica que requiere un poco más de propiedades.

Definición. Un semigrupo es un conjunto $S$ con una operación asociativa $\star$.

Si además $\star$ es una operación conmutativa, entonces decimos que es un semigrupo conmutativo. En realidad, en cualquiera de las definiciones que daremos a continuación podemos agregar el adjetivo «conmutativo» y esto querrá decir que además de las propiedades requeridas, también se cumple que la operación es conmutativa.

En los semigrupos (y demás estructuras con asociatividad) tenemos la ventaja de que podemos «olvidarnos de los paréntesis» sin la preocupación de que haya ambigüedad. Por ejemplo, en los naturales la expresión $3+((2+4)+8)$ se puede escribir simplemente como $3+2+4+8$, pues cualquier otra forma de poner paréntesis, como $(3+2)+(4+8)$, debe dar exactamente el mismo resultado por asociatividad.

Ejemplo. Una operación que no es asociativa es la resta en los enteros. Aunque no hemos definido formalmente esta operación, es intuitivamente claro que $3-(2-1)$ no es lo mismo que $(3-2)-1$.

$\triangle$

Unidades y magmas unitales

A veces sucede que algunos elementos de un conjunto «no afectan a nadie» bajo una cierta operación binaria dada. Por ejemplo, en los naturales «sumar cero» no cambia a ningún entero.

Definición. Sea $\star$ una operación binaria en un conjunto $S$. Una unidad o neutro para $\star$ es un elemento $e$ en $S$ para el cual se cumple que para cualquier elemento $a$ de $S$ se tenga $a\star e = a$ y $e\star a = a$.

Observa que es muy importante pedir las dos igualdades de la definición. Si una se cumple, no necesariamente tiene que pasar la otra, pues no necesariamente la operación es conmutativa. Por supuesto, si ya se sabe que la operación es conmutativa, entonces basta con ver una de ellas.

En $\mathbb{Z}$ tenemos las operaciones de suma y producto. Para no confundir a sus neutros, a $0$ le llamamos el neutro aditivo para hacer énfasis que es el neutro de la suma. Y a $1$ le llamamos el neutro multiplicativo para hacer énfasis que es el neutro del producto. Entre las propiedades que probamos, en efecto vimos que $a+0=a=0+a$ y que $a\cdot 1 = a = 1\cdot a$ para cualquier entero $a$.

Definición. Un magma unital es un conjunto $S$ con una operación $\star$ que tiene un neutro.

El conjunto de naturales con la operación $\star$ que dimos en la sección de intuición también es un magma unital. ¿Puedes decir quién es su neutro?

Monoides

Se puede pedir más de una propiedad a una operación binaria y entonces obtenemos estructuras algebraicas más especiales.

Definición. Un monoide es un conjunto $S$ con una operación $\star$ que es asociativa y que tiene un neutro.

En otras palabras, un monoide es un magma unital con operación asociativa. O bien, un semigrupo cuya operación tiene unidad. Por supuesto, si la operación además es conmutativa entonces decimos que es un monoide conmutativo.

Ejemplo. Por todo lo que hemos visto en esta entrada, tenemos que $\mathbb{N}$ con la suma es un monoide conmutativo. Así mismo, $\mathbb{N}$ con el producto es un monoide conmutativo.

$\triangle$

Semianillos

La última idea importante para discutir en esta entrada es que una estructura algebraica puede tener más de una operación binaria, y además de pedir propiedades para cada operación, también se pueden pedir propiedades que satisfagan ambas operaciones en igualdades que las involucran a las dos.

Definición. Un seminanillo es un conjunto $S$ con dos operaciones binarias $\square$ y $\star$ que satisfacen las siguientes propiedades:

  • $\square$ es un monoide conmutativo
  • $\star$ es un monoide
  • Se cumple distributividad, es decir, que para cualesquiera tres elementos $a,b,c$ de $S$ se tiene $a\star(b\square c) = (a\star b)\square(a\star c)$ y $(a\square b)\star c = (a\star c)\square(b\star c)$.
  • El neutro $e$ de $\square$ aniquila a los elementos bajo $\star$, es decir, para cualquier elemento $a$ de $S$ se tiene que $a\star 0=0$ y $0\star a = 0$.

Un semianillo conmutativo es un semianillo en donde la operación $\star$ también es conmutativa. Las propiedades que hemos de los números naturales nos permiten enunciar el siguiente resultado.

Teorema. El conjunto $\mathbb{N}$ con las operaciones binarias de suma y producto es un semianillo conmutativo.

Más adelante…

Este sólo fue un pequeño paréntesis para comenzar a hablar de operaciones binarias y de estructuras algebraicas. Ahora regresaremos a seguir construyendo de manera formal los sistemas numéricos con los que se trabaja usualmente: los enteros, los racionales, los reales y los complejos.

Un poco más adelante haremos otro paréntesis de estructuras algebraicas, en el que hablaremos de otras propiedades más que puede tener una operación binaria. Una muy importante es la existencia de inversos para la operación binaria. Esto llevará a las definiciones de otras estructuras algebraicas como los grupos, los anillos, los semigrupos con inversos, los quasigrupos y los campos.

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. Encuentra el neutro de la operación $\star$ dada en la sección de intuición. Verifica que en efecto es un neutro.
  2. Demuestra que el conjunto de los naturales pares $\{0,2,4,6,\ldots\}$ sí tiene un neutro para la operación de suma, pero no para la operación de producto.
  3. Considera el conjunto $P(S)$ de subconjuntos de un conjunto $S$. Considera las operaciones binarias de unión e intersección de elementos de $P(S)$. Muestra que $P(S)$ con estas operaciones es un semianillo conmutativo.
  4. Da un ejemplo de un magma que no sea un magma unital. Da un ejemplo de un magma unital que no sea un monoide.
  5. Da o busca un ejemplo de un semianillo que no sea un semianillo conmutativo.

Entradas relacionadas

Agradecimientos

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