Archivo de la etiqueta: teoría de conjuntos

Teoría de los Conjuntos I: Conjuntos infinitos

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta entrada definiremos qué es un conjunto infinito. Después, probaremos algunos resultados sobre la cantidad de elementos que poseen los conjuntos infinitos.

Conjuntos infinitos

Recordemos que para conjuntos $X$ y $Y$ decimos que $|X|\leq |Y|$ si existe una función inyectiva $f:X\to Y$.

Definición. Sea $A$ un conjunto. Decimos que $A$ es un conjunto infinito si no es finito, es decir, para todo $n\in \mathbb{N}$, no existe una función $f:A\to n$ que sea biyectiva.

Ejemplo.

El conjunto de los números naturales no es finito. En efecto, sea $n\in\mathbb{N}$ cualquier elemento. Ahora, si existiera una función biyectiva $f:n\to\mathbb{N}$, en particular, debería existir $B\subseteq n$ tal que $f[B]=s(n)$. Luego, podemos particionar a $n$ como $n=B\cup(n\setminus B)$, por lo que $s(n)=n\cup\set{n}=B\cup(n\setminus B)\cup\set{n}$ y, por la regla de la suma, tendríamos que $|s(n)|=|B|+|n\setminus B|+1$. Dado que $g:B\to s(n)$ definida por medio de $g(m)=f(m)$ es una biyección, entonces $|B|=|s(n)|$. De este modo, $|s(n)|=|s(n)|+|n\setminus B|+1$, por lo que $0=|n\setminus B|+1$ y esto último es imposible, pues el sucesor de cualquier número natural es distinto de $0$. Así pues, no existe función biyectiva de $n$ en $\mathbb{N}$ y, consecuentemente, $\mathbb{N}$ no es finito.

$\square$

A continuación mostraremos que dado cualquier número natural $n$, existe una función inyectiva de $n$ en cualquier conjunto infinito. Veamos la demostración.

Teorema. Si $X$ es infinito, entonces $|X|\geq n$ para cualquier $n\in \mathbb{N}$.

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

Base de inducción. Si $n=0$, por vacuidad la función $\emptyset:n\to X$ es inyectiva.

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

Paso inductivo. Veamos que $n+1\leq|X|$.

Dado que $n\leq|X|$, entonces existe $f:n\to X$ tal que $f$ es inyectiva. Luego, como $X$ es infinito, $f$ no puede ser suprayectiva y por lo tanto existe $y\in X$ tal que $y\notin Im(f)$.

Definimos $g: n+1\to X$ como $g=f\cup \set{(n,y)}$. Resulta que $g$ es inyectiva. En efecto, sean $n_1, n_2\in n+1$ tales que $g(n_1)=g(n_2)$.

Caso 1: Si $n_1, n_2\in n$, entonces $f(n_1)=g(n_1)=g(n_2)=f(n_2)$ y como $f$ es inyectiva se tiene que $n_1=n_2$.

Caso 2: Si $n_1,n_2=n$, entonces $n_1=n_2$.

No puede ocurrir que $n_1\in n$ y $n_2=n$, pues de ser así tendríamos que $g(n_1)=f(n_1)\not=y$ pues $y\notin Im(f)$, mientras que $g(n_2)=y$, lo cual contradice que $g(n_1)=g(n_2)$. Análogamente, no puede ocurrir que $n_2\in n$ y $n_1=n$.

Por lo tanto $g$ es inyectiva y así, $n+1\leq|X|$.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada:

  • Muestra que si $X$ es un conjunto tal que para cada natural $n$ existe una función inyectiva $f_n:n\to X$, entonces existe una función inyectiva $f$ de $\mathbb{N}$ en $X$.
  • Muestra que si $X$ es un conjunto infinito, entonces para cada subconjunto finito $A$ de $X$, el conjunto $X\setminus A$ es infinito.
  • Retomando el ejercicio anterior, si $X$ es infinito y $a\in X$, ¿existirá una función biyectiva entre $X$ y $X\setminus\set{a}$?
  • Muestra que si $A$ y $B$ son conjuntos tales que $A\cup B$ infinito, entonces alguno de los conjuntos $A$ o $B$ es infinito.

Más adelante…

El primer conjunto infinito que vimos fue el de los números naturales. En la siguiente entrada hablaremos acerca de conjuntos numerables. El primero de ellos será el de los naturales y veremos que existen muchos conjuntos que tienen la misma cantidad de elementos que el conjunto de números naturales.

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: Conjuntos numerables

Por Gabriela Hernández Aguilar

2 respuestas

Introducción

Ahora que hemos desarrollado una herramienta para comparar conjuntos que tienen más elementos que otros y hemos trabajado con conjuntos finitos e infinitos, hablaremos un poco más acerca de estos últimos, en especifico de aquellos que tienen la misma cantidad de elementos que el conjunto de los números naturales.

Conjuntos numerables

Definición. Sea $A$ un conjunto, decimos que $A$ es numerable si es equipotente a $\mathbb{N}$, es decir, si existe una función biyectiva $f:\mathbb{N}\to A$. De ser así, lo denotaremos con $|A|=|\mathbb{N}|$.

Ejemplo.

En la entrada de equipotencia vimos que existe una función biyectiva entre el conjunto de los números pares y los números naturales, por lo que podemos concluir que $$|\{2k:k\in \mathbb{N}\}|=|\mathbb{N}|.$$

$\square$

Ejemplo.

El conjunto $\mathbb{Z}$ de los números enteros es un conjunto numberable. (Puedes revisar la construcción del conjunto de los números enteros en el siguiente enlace: Álgebra Superior II: Construcción de los enteros y su suma)

Consideremos $f:\mathbb{N}\to \mathbb{Z}$ dada por:

$f(n)= \left\{ \begin{array}{lcc}
             \overline{(k,0)} &   si  & n=2k\ \text{para algún}\ k\in \mathbb{N} \\
             \\ \overline{(0,k+1)} &  si & x=2k+1\ \text{para algún}\ k\in\mathbb{N}
             \end{array}
   \right.$

Resulta que $f$ es biyectiva. En efecto, veamos primero que $f$ es inyectiva.

Sean $x_1, x_2\in \mathbb{N}$ tales que $f(x_1)=f(x_2)$. Tenemos los siguientes casos:

Caso 1. Si $x_1=2k$ y $x_2=2m$ para algunos $k,m\in \mathbb{N}$, entonces $f(x_1)=\overline{(k,0)}$ y $f(x_2)=\overline{(m,0)}$ y así, $\overline{(k,0)}=\overline{(m,0)}$, por lo que $k+0=m+0$, es decir, $k=m$ y por lo tanto, $x_1=2k=2m=x_2$.

Caso 2. Si $x_1=2k+1$ y $x_2=2m+1$ para algunos $k,m\in \mathbb{N}$, entonces $f(x_1)=\overline{(0,k+1)}$ y $f(x_2)=\overline{(0,m+1)}$ y así, $\overline{(0,k+1)}=\overline{(0,m+1)}$, por lo que $0+(m+1)=0+(k+1)$ y así $m=k$. Por tanto, $x_1=2k+1=2m+1=x_2$.

El caso en el que $x_1=2k$ y $x_2=2m+1$ no puede ocurrir, pues de lo contrario se tendría que $\overline{(k,0)}=\overline{(0,m+1)}$ por lo que $k+(m+1)=0+0=0$, lo cual es imposible. De manera análoga, no puede ocurrir que $x_1=2m+1$ y $x_2=2k$ para algunos $m,k\in\mathbb{N}$.

Por lo tanto, $f$ es inyectiva.

Ahora veamos que $f$ es suprayectiva. Sea $y\in \mathbb{Z}$, tenemos los siguientes casos:

Caso 1. Si $y\in \mathbb{Z}^+\cup\set{\overline{(0,0)}}$, entonces $y=\overline{(k,0)}$ para algún $k\in\mathbb{N}$. Así, para $x=2k\in\mathbb{N}$ se tiene $f(x)=y$.

Caso 2: Si $y\in \mathbb{Z}^{-}$, entonces $y=\overline{(0,k)}$ para algún $k\in\mathbb{N}\setminus\{0\}$. Luego, existe $k’\in\mathbb{N}$ tal que $s(k’)=k$, es decir, $k’+1=k$. Luego, tomando $x=2k’+1$ se tiene $f(x)=\overline{(0,k’+1)}=\overline{(0,k)}=y$.

Concluimos que $f$ es suprayectiva.

Por lo tanto, $f$ es biyectiva y así, $|\mathbb{N}|=|\mathbb{Z}|$.

$\square$

Ejemplo:

$|\mathbb{Z}|=|\mathbb{Q}|$.

En los ejercicios probarás que existe una función biyectiva de $\mathbb{N}$ en $\mathbb{N}\times\mathbb{N}$.

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada.

  1. Si un conjunto $A$ es numerable y $x\in A$ es un elemento arbitrario, ¿será cierto que $A\setminus\set{x}$ es también numerable?
  2. Sea $\mathbb{N}_0:=\mathbb{N}\setminus\set{0}$. Muestra que $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}_0$ dada por $f(n,m)=2^n(2m+1)$ es una función biyectiva.
  3. Utilizando el ejercicio anterior, muestra que si $A$ y $B$ son conjuntos numerables, entonces $A\times B$ también es numerable.
  4. Sean $A$ y $B$ conjuntos ajenos y numerables. Muestra que $A\cup B$ es numerable . ¿Y si los conjuntos $A$ y $B$ no son ajenos?

Más adelante…

En la siguiente entrada concluiremos el contenido acerca de cardinalidad de conjuntos infinitos. Daremos cierre a esta unidad con el tema de aritmética cardinal.

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: Conjuntos finitos (parte II)

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta entrada daremos continuación al tema de conjuntos finitos. Probaremos más resultados que se satisfacen para los conjuntos finitos y veremos cuál es la cardinalidad del conjunto potencia de un conjunto finito dado.

Conjuntos finitos y contención

Teorema. Sean $A$ y $B$ conjuntos tales que $B$ es finito. Si $A\subseteq B$, entonces $A$ es finito. Más aún, $|A|\leq |B|$.

Demostración. (Por inducción sobre $|B|$).

Base de inducción. Supongamos que $|B|=0$. Entonces $B=\emptyset$, por lo que $A=\emptyset$ y así, $A$ es finito y $0=|A|\leq |B|=0$.

Hipótesis de inducción. Supongamos que para $|X|=n$ se cumple que si $Y\subseteq X$, entonces $Y$ es finito y $|Y|\leq |X|$.

Paso inductivo. Sea $B$ un conjunto finito tal que $|B|=n+1$. Veamos que si $A\subseteq B$, entonces $A$ es finito y $|A|\leq |B|$.

Si $A=B$, entonces $A$ es finito y $|A|=|B|\leq|B|$.

Si $A\not=B$, existe $x\in B\setminus A$. Luego, $A\subseteq B\setminus\set{x}$ y como $|B\setminus \set{x}|=n$, tenemos por hipótesis de inducción que $A$ es finito y $|A|\leq |B\setminus \set{x}|=n\leq n+1 =|B|$. En cualquier caso, $A$ es finito y $|A|\leq |B|$.

$\square$

Cardinalidad del conjunto potencia

Como parte de los ejercicios de la unidad de números naturales, definimos la operación binaria potencia en $\mathbb{N}$, que intuitivamente se realiza como sigue $m^{n}=\underbrace{m\cdot m\cdots m}_{n-veces}$.

Teorema. Si $X$ es finito, entonces $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=2^{|X|}$.

Demostración. (Por inducción sobre $|X|$).

Base de inducción. Si $|X|=0$, entonces $X=\emptyset$ y así, $\mathcal{P}(X)=\set{\emptyset}$, por lo que $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=1=2^0=2^{|X|}$.

Hipótesis de inducción. Supongamos que si $A$ es finito tal que $|A|=n$, entonces $\mathcal{P}(A)$ es finito y $|\mathcal{P}(A)|= 2^{|A|}$.

Paso inductivo. Sea $X$ un conjunto finito tal que $|X|=n+1$. Supongamos que $X=\set{X_1,X_2, \dots, X_n, X_{n+1}}$. Luego, consideremos $X’=X\setminus \set{X_1}$, entonces $|X’|=n$ y así, $|\mathcal{P}(X’)|=2^{|X’|}$. Veamos que $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=2^{|X|}$. Para ello veamos primero que $\mathcal{P}(X)=\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X): X_1\in Z}$.

Procederemos por doble contención.

$\subseteq$) Sea $Y\in \mathcal{P}(X)$, entonces $Y\subseteq X$. Si $X_1\in Y$, entonces $Y\in \set{Z\in \mathcal{P}(X): X_1\in Z}$ y por lo tanto, $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

Si $X_1\notin Y$, entonces $Y\subseteq X\setminus \set{X_1}=X’$, por lo que $Y\in \mathcal{P}(X’)$ y por lo tanto, $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

Concluimos que $\mathcal{P}(X)\subseteq \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

$\supseteq$) Sea $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X): X_1\in Z}$.

Caso 1: Si $Y\in \mathcal{P}(X’)$, entonces $Y\subseteq X’$ y como $X’\subseteq X$, entonces $Y\subseteq X$ y así, $Y\in \mathcal{P}(X)$.

Caso 2: Si $Y\in \set{Z\in \mathcal{P}(X):X_1\in Z}$, entonces $Y\in \mathcal{P}(X)$.

Por lo tanto, $\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}\subseteq \mathcal{P}(X)$.

Así, $\mathcal{P}(X)=\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

Luego, por hipótesis de inducción tenemos que $\mathcal{P}(X’)$ es finito y $|\mathcal{P}(X’)|=2^n$.

Resulta que $\set{Z\in \mathcal{P}(X)}$ es finito; más aún, afirmamos que $|\set{Z\in \mathcal{P}(X):X_1\in Z}|=|\mathcal{P}(X’)|$. Para probar este último hecho estableceremos una biyección entre $\mathcal{P}(X’)$ y $\set{Z\in \mathcal{P}(X):X_1\in Z}$.

Consideremos $f:\mathcal{P}(X’)\to \set{Z\in \mathcal{P}(X):X_1\in Z}$ dada por $f(Y)=Y\cup \set{X_1}$. Veamos que $f$ es biyectiva.

Inyectividad. Sean $A,B\in \mathcal{P}(X’)$ tales que $f(A)=f(B)$, esto es $A\cup \set{X_1}=B\cup \set{X_1}$. Luego, $A$ y $\set{X_1}$ son ajenos pues $A\subseteq X’=X\setminus \set{X_1}$; asimismo, $B$ y $\set{X_1}$ son ajenos pues $B\subseteq X’=X\setminus \set{X_1}$. De este modo, debe ocurrir que $A=B$. Por lo tanto, $f$ es inyectiva.

Suprayectividad. Sea $Y\in \set{Z\in \mathcal{P}(X):X_1\in Z}$. Entonces $Y\subseteq X$ y $X_1\in Y$.

Veamos que existe $W\subseteq X\setminus \set{X_1}$ tal que $f(W)=Y$. Consideremos $W=Y\setminus \set{X_1}$. Tenemos que $f(W)=(Y\setminus \set{X_1})\cup \set{X_1}=Y$. Por lo tanto, $f$ es suprayectiva.

Así, $f$ es biyectiva y $|\set{Z\in \mathcal{P}(X): X_1\in Z}|=2^n$.

Por lo tanto, usando regla de la suma, tenemos que $|\mathcal{P}(X)|=|\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X)}|= 2^n+2^n=2(2^n)= 2^{n+1}$. Esto concluye nuestra prueba.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada.

  1. Demuestra que si $A$ es un conjunto finito, entonces $A$ no es equipotente a ninguno de sus subconjuntos propios.
  2. Demuestra que si $A\subseteq B$ y $B$ es finito, entonces $|B|=|B\setminus A|+|A|$.
  3. Sean $A$ y $B$ conjuntos finitos. Sea $\mathcal{F}$ el conjunto de todas las posibles funciones de $A$ en $B$. Muestra que $\mathcal{F}$ es finito. ¿Cuál es su cardinalidad en términos de las de $A$ y $B$?
  4. Sean $A$ y $B$ conjuntos finitos. Muestra que $A\times B$ es finito. ¿Cuál es su cardinalidad en términos de las de $A$ y $B$?
  5. Demuestra que para cualquier número natural $n$ se tiene que $n<2^n$.

Más adelante…

En la siguiente entrada abordaremos a los conjuntos infinitos. Esto nos acercará a una discusión importante sobre qué son en realidad los cardinales en teoría de los conuntos.

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: Conjuntos finitos

Por Gabriela Hernández Aguilar

2 respuestas

Introducción

Ahora que sabemos el concepto de equipotencia, en esta entrada definiremos qué son los conjuntos finitos y hablaremos de ellos. A grandes rasgos, serán aquellos que tengan tantos elementos como alguno de los números naturales que ya definimos. Además, veremos resultados acerca de la cardinalidad de la unión de dos conjuntos.

Conjuntos finitos

Definición. Sea $X$ un conjunto. Decimos que $X$ es un conjunto finito si y sólo si existe $n\in \mathbb{N}$ tal que $X\sim n$.

Ejemplo.

El conjunto $\emptyset$ es finito, pues existe una biyección entre el conjunto $\emptyset$ y $0$; a saber, la función vacía.

$\square$

Ejemplo.

El conjunto $A=\set{2,4,6,8,10}$ es finito pues $f:A\to 5=\set{0,1,2,3,4}$ definida por medio de $f=\set{(2,0), (4,1), (6,2), (8,3), (10, 4)}$ es una función biyectiva.

$\square$

Principio de las casillas y unicidad de natural equipotente

La definición dice que $X$ es finito cuando hay un natural al que es equipotente pero, ¿este natural es único? La respuesta es que sí. Demostraremos esto a través de algunos resultados auxiliares, que a la vez nos permitirán enunciar y demostrar un par de versiones del principio de las casillas.

Lema (principio de las casillas). No existe ninguna función inyectiva $f:n+1\to n$.

Demostración. Probaremos el resultado por inducción. Para $n=0$ el resultado es cierto pues no existe ninguna función (inyectiva o no) $f:1\to 0$, pues $0=\emptyset$ y $1\neq \emptyset$.

Supongamos que el resultado es cierto para el natural $n$, es decir, que no existe ninguna función inyectiva $f:n+1\to n$. Veremos que no existe ninguna función inyectiva $g:n+2\to n+1$. En busca de una contradicción, supongamos que sí existe tal $g$.

Si $Im(g)\subseteq n$, entonces la restricción de $g$ a $n+1$ es una función inyectiva de $n+1$ en $n$, lo que contradice la hipótesis inductiva. Así, existe un natural $k\leq n+2$ tal que $g(k)=n+1$. Si $k=n+2$, entonces $g\setminus\{(n+2,n+1)\}$ es una función inyectiva de $n+1$ en $n$, que contradice la hipótesis inductiva. Así, $k\leq n+1$. Como $g$ es inyectiva, $g(n+2)=l\neq k$. Pero entonces, $$(g\setminus\{(n+2,l),(k,n+1)\})\cup \{(k,l)\}$$ es una función inyectiva de $n+1$ en $n$, dando una contradicción final a la hipótesis inductiva.

$\square$

Usualmente el principio de las casillas se piensa así: si $f:n+1\to n$ es una función, entonces deben existir $x,y\in n+1$ tales que $f(x)=f(y)$. En términos intuitivos, «si colocamos $n+1$ pelotas en $n$ casillas, entonces por lo menos en alguna casilla quedaron por lo menos dos pelotas». Si son todavía más pelotas, el resultado es cierto, como lo indica el siguiente corolario de manera formal.

Corolario. Sean $m,n$ naturales con $n<m$. Entonces no existen funciones inyectivas $f:m\to n$.

Demostración. Recordemos que si $n<m$, entonces $n\subset m$ y de hecho $n+1\subseteq m$. Si existiera una función inyectiva $f:m\to n$, entonces su restricción a $n+1$ sería una función inyectiva de $n+1$ en $n$, contradiciendo el principio de las casillas.

$\square$

En particular, si $X$ es un conjunto finito, entonces debe haber un único natural $n$ al cual es equipotente. Si hubiera dos distintos $m$ y $n$, sin pérdida de generalidad $n<m$. Tendríamos entonces que $m\sim X$ y $X\sim n$, pero entonces $m\sim n$ y existiría una función biyectiva de $m$ a $n$. En particular, sería una función inyectiva, lo cual contradice el corolario anterior.

Con esto en mente, es conveniente añadir la siguiente notación para conjuntos finitos.

Definición. Sea $X$ un conjunto finito y $n\in\mathbb{N}$ el natural tal que $X\sim n$. Definimos el cardinal de $X$ como $n$ y lo denotaremos por $|X|=n$.

La regla de la suma

La regla de la suma es un resultado muy versátil que nos permite entender exactamente la cardinalidad de la unión de dos conjuntos finitos disjuntos. Además, este resultado motivará posteriormente la definición de suma de cardinales infinitos, cuando hablemos de ellos.

Teorema (regla de la suma). Si $X$ y $Y$ son conjuntos finitos y disjuntos, con $|X|=m$ y $|Y|=n$, entonces $X\cup Y$ es finito y $|X\cup Y|=m+n$.

Demostración. Sean $f:X\to m$ y $g:Y\to n$ biyecciones. Definimos la función $h:X\cup Y \to m+n$ como sigue: $$h(x)= \begin{cases} f(x) & \text{si $x\in X$}\\ m+g(x) & \text{si $x\in Y$.}\end{cases}$$

Como $X$ y $Y$ son disjuntos, $h$ es una función de dominio $X\cup Y$. Como $f(x)\leq m-1 \leq m+n-1$ y $m+g(x)\leq m+ n-1$, entonces la imagen de $h$ está contenida en $m+n$. Afirmamos que $h$ es una biyección de $X\cup Y$ en $m+n$.

Veamos que $h$ es inyectiva. Supongamos que $x,y$ en $X\cup Y$ son tales que $h(x)=h(y)$. Es imposible que $x\in X$ y $y\in Y$ pues en ese caso $h(x)=f(x)\leq m-1$ y $h(y)=m+g(y)\geq m$. Análogamente, $x\in Y$ y $y\in X$ es imposible. Así, o bien ambos $x$ y $y$ están en $X$, o bien ambos están en $Y$. Si están en $X$, tenemos $f(x)=h(x)=h(y)=f(y)$ y como $f$ es inyectiva, obtenemos $x=y$. Si están en $Y$, tenemos $m+g(x)=h(x)=h(y)=m+g(y)$. Por ley de cancelación de la suma, se tiene $g(x)=g(y)$. Y por inyectividad de $g$ se tendría $x=y$.

Ahora, veamos que $h$ es suprayectiva. Tomemos $k\in m+n$. Si $k\leq m-1$, entonces como $f$ es suprayectiva, existe $x\in X$ tal que $f(x)=k$ y entonces $h(x)=f(x)=k$. Si $k\geq m$, entonces existe $l$ tal que $m+l=k$. Dicha $l$ debe cumplir $l\leq n-1$, pues en otro caso $m+n-1\geq k=m+l \geq m+n$, lo cual sería una contradicción. Como $g$ es biyectiva, existe $r$ tal que $g(r)=l$. Y entonces $h(r)=m+g(r)=m+l=k$.

Como $h$ es inyectiva y suprayectiva, obtenemos que es biyectiva, como queríamos.

$\square$

La regla de la suma tiene varios corolarios como consecuencia.

Corolario. Si $X$ es finito y $y\notin X$, entonces $X\cup\set{y}$ es finito y $|X\cup \set{y}|= |X|+1$.

Demostración. Aplicamos la regla de la suma y $|\set{y}|=1$.

$\square$

Corolario (principio de inclusión-exclusión). Sean $X$ y $Y$ conjuntos finitos. Entonces $X\cup Y$ es finito. Más aún, $|X\cup Y| + |X\cap Y| = |X| + |Y|$.

Demostración. Se tiene que $X=(X\cap Y) \cup (X\setminus Y)$ y que $(X\cap Y) \cap (X\setminus Y)=\emptyset$ (verifica ambas cosas). Así, por regla de la suma se tiene que $$|X|=|X\cap Y| + |X\setminus Y|.$$

De manera similar, se tiene que $X\cup Y = Y \cup (X\setminus Y)$ con $Y\cap (X\setminus Y)=\emptyset$ (verifíca ambas cosas). Así, por la regla de la suma se tiene que $$|Y| + |X\setminus Y| = |X\cup Y|.$$

Sumando las dos igualdades que obtuvimos, tenemos que $$|X|+|Y|+|X\setminus Y| = |X\cap Y| + |X\cup Y| + |X\setminus Y|.$$

Aplicando la ley de cancelación para eliminar $|X\setminus Y|$, obtenemos el resultado deseado.

$\square$

Corolario. Sean $X$ y $Y$ conjuntos finitos, entonces $X\cup Y$ es finito. Más aún, $|X\cup Y|\leq |X|+|Y|$.

Demostración. Por el principio de inclusión-exclusión, $$|X\cup Y| \leq |X\cup Y| + |X\cap Y| = |X| + |Y|.$$

$\square$

La regla de la suma por sí misma es muy versátil y tiene una versión más general.

Teorema (regla de la suma generalizada). Sea $n$ un natural y sean $A_1,\ldots,A_n$ conjuntos finitos y tales que $A_j\cap A_i=\emptyset$ para cualesquiera $i,j$ en $\{1,\ldots,n\}$. Entonces $A:=\bigcup \{A_i: i\in \{1,\ldots,n\}\}$ es finito.

En los ejercicios tendrás que probar esta versión.

Un último resultado que demostraremos es el siguiente.

Teorema. Si $\mathcal{F}$ es finito y para cualquier $X\in \mathcal{F}$ pasa que $X$ es finito, entonces $\bigcup\mathcal{F}$ es finito.

Demostración. (Por inducción sobre la cardinalidad de $\mathcal{F}$).

Base de inducción. Si $|\mathcal{F}|=0$, entonces $\mathcal{F}=\emptyset$. Así, se cumple por vacuidad, que si cualquier $X\in \mathcal{F}$ es finito, entonces $\bigcup \mathcal{F}$ es finito. Más aún, $\bigcup \mathcal{F}=\emptyset$ y $|\bigcup \mathcal{F}|=0$.

Hipótesis de inducción. Supongamos que si $|\mathcal{G}|=n$ y para cualquier $X\in \mathcal{G}$, $X$ es finito, se cumple que $\bigcup\mathcal{G}$ es finito.

Paso inductivo. Veamos que si $|\mathcal{F}|=n+1$ y para cualquier $X\in \mathcal{F}$, $X$ es finito, entonces $\bigcup\mathcal{F}$ es finito.

Como $|\mathcal{F}|$ es distinto de $0$, tomeos $X\in\mathcal{F}$ y definamos $\mathcal{F’}:=\mathcal{F}\setminus \{X\}$. Tenemos que cualquier elemento de $\mathcal{F’}$ es finito y que $|\mathcal{F}’|=n$, por lo que por hipótesis de inducción se cumple que $\bigcup\mathcal{F’}$ es finito.

Ahora, por el corolario del principio de inclusión-exclusión, tenemos que $\bigcup\mathcal{F}’\cup X$ es finito.

Afirmación. $\bigcup\mathcal{F}=\bigcup\mathcal{F}’\cup X$.

Demostración de la afirmación.

Sea $x\in\bigcup \mathcal{F}$, entonces existe $Y\in \mathcal{F}$ tal que $x\in Y$.

Caso 1: Si $Y=X$, entonces $x\in X$ y por lo tanto, $x\in \bigcup\mathcal{F}’\cup X$.

Caso 2: Si $Y\not=X$, entonces $Y\in \mathcal{F}’$ y así, $x\in \bigcup\mathcal{F}’$.

Los casos anteriores muestran que $\bigcup\mathcal{F}\subseteq \bigcup\mathcal{F}’\cup X$.

Ahora, como $\mathcal{F’}\subseteq\mathcal{F}$ y $X\in\mathcal{F}$, entonces $\bigcup\mathcal{F’}\cup X\subseteq\bigcup\mathcal{F}$.

Así, $\bigcup \mathcal{F}=\bigcup\mathcal{F}’\cup X$. Por lo tanto, $\bigcup\mathcal{F}$ es finito. Lo que concluye nuestra prueba.

$\square$

,

Tarea moral

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

  1. Sea $X$ un conjunto finito y $x\in X$. Si $|X|=n+1$, demuestra que $X\setminus\set{x}$ es finito y que $|X\setminus\set{x}|=n$.
  2. Sea $X$ es un conjunto finito. Prueba que si $A\subseteq X$, entonces, $A$ es un conjunto finito.
  3. Demuestra por inducción la regla de la suma generalizada. Como sugerencia, uno de los pasos intermedios es que enuncies formalmente y demustres que para todo natural $n$ se cumple que $(A_1\cup \ldots \cup A_n) \cap B = (A_1 \cap B) \cup \ldots \cup (A_n \cap B)$.

Más adelante…

En la siguiente entrada continuaremos con el contenido de esta sección, probaremos más propiedades sobre los conjuntos finitos y a su vez hablaremos acerca de la cardinalidad del conjunto potencia.

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: Equipotencia y dominancia

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta unidad daremos un par de definiciones que formalizarán la idea de que un conjunto sea más grande que otro, es decir, vamos a definir y formalizar la noción de que un conjunto tenga más elementos o la misma cantidad que otro, aún cuando no definamos formalmente qué es lo que entenderemos por cantidad de elementos de un conjunto.

Equipotencia

Definición. Sean $A$ y $B$ conjuntos. Decimos que $A$ es equipotente a $B$ si existe una función biyectiva $f:A\to B$. Denotaremos $A$ es equipotente a $B$ como $A\sim B$ o bien como $|A|=|B|$.

Si podemos establecer una función biyectiva entre $A$ y $B$, diremos que tienen la misma cantidad de elementos.

Ejemplo.

Sea $A=\mathbb{N}$ y $B=\set{2k:\ k\in\mathbb{N}}$.

Afirmación. $A$ y $B$ son equipotentes.

Demostración de la afirmación.

Sea $f:\mathbb{N}\to B$ la función dada por $f(n)=2n$. Veamos que $f$ es biyectiva.

  1. Inyectividad.
    Sean $x,y\in \mathbb{N}$ tales que $f(x)= f(y)$, esto es $2x=2y$. Luego, por ley de la cancelación para el producto tenemos que $x=y$ y, por lo tanto, $f$ es inyectiva.
  2. Suprayectividad.
    Si $y\in B$, entonces $y=2k$ para algún $k\in \mathbb{N}$. Así, existe $k\in \mathbb{N}$ tal que $f(k)=2k=y$ y, por consiguiente, $f$ es suprayectiva.

Por lo tanto, $f$ es biyectiva, de modo que $A\sim B$.

$\square$

El siguiente teorema seguro te recordará algunas cosas que discutimos cuando hablamos acerca de relaciones de equivalencia.

Teorema. Sean $A$, $B$ y $C$ conjuntos. Entonces se satisfacen los siguientes enunciados:

  1. $A$ es equipotente a $A$.
  2. Si $A$ es equipotente a $B$, entonces $B$ es equipotente a $A$.
  3. Si $A$ es equipotente a $B$ y $B$ es equipotente a $C$, entonces $A$ es equipotente a $C$.

Demostración.

  1. La función $Id_A$ es una función biyectiva, por lo que podemos concluir que $A\sim A$.
  2. Supongamos que $A\sim B$, entonces existe $f:A\to B$ biyectiva. Luego, $f^{-1}:B\to A$ es una función biyectiva y por lo tanto, $B\sim A$.
  3. Supongamos que $A\sim B$ y $B\sim C$, esto es, existe $f:A\to B$ biyectiva y $g:B\to C$ biyectiva. Luego, consideremos $g\circ f: A\to C$, como $f$ y $g$ son biyectivas, entonces $g\circ f$ es biyectiva.
    Así, $A\sim C$.

$\square$

De esta manera, la equipotencia se comporta «como una relación de equivalencia». Pero, estrictamente hablando, no es una relación de equivalencia, pues dicha relación tendría que darse en la colección de todos los conjuntos, pero ya sabemos que esta colección no es un conjunto.

Por la simetría, en vez de decir «$A$ es equipontente a $B$» podemos simplemente decir que $A$ y $B$ son equipotentes.

Dominancia

Hemos visto que para que un conjunto sea equipotente a otro se requiere que exista una función biyectiva. Esto «se comporta» como una relación de equivalencia. ¿Hay una noción que se comporte como un orden parcial o un orden estricto? Sí. La siguiente definición establece esta idea.

Definición. Sean $A$ y $B$ conjuntos. Decimos que $B$ domina a $A$ si existe $f: A\to B$ tal que $f$ es inyectiva, pero no existe una función biyectiva de $A$ en $B$. Lo denotaremos como $|A|\preceq|B|$.

Ejemplo.

Sean $A=\set{1,2,3}$ y $B=\mathbb{N}$. Tenemos que $|A|\preceq|B|$ pues $f=\set{(1,1), (2,2), (3,3)}$ es iuna función inyectiva. Sin embargo, no existe $h:A\to B$ tal que $h$ sea suprayectiva.

$\square$

El siguiente teorema formaliza la idea de que $\preceq$ «se comporta» como un orden parcial.

Teorema. Sean $A$, $B$ y $C$ conjuntos. Entonces, se satisfacen los siguientes enunciados:

  1. $A\preceq A$.
  2. Si $A\preceq B$ y $B\preceq C$, entonces $A\preceq C$.

Demostración.

  1. La función $Id_A$ es una función biyectiva, en paticular es una función inyectiva por lo que podemos concluir que $A\preceq A$.
  2. Supongamos que $A\preceq B$ y $B\preceq C$, esto es, existe $f:A\to B$ inyectiva y $g:B\to C$ inyectiva. Luego, consideremos $g\circ f: A\to C$, como $f$ y $g$ son inyectivas, entonces $g\circ f$ es inyectiva. Así, $A\preceq C$.

$\square$

A continuación probaremos un teorema importante en este curso. Dicho resultado muestra que, dado un conjunto $A$, no existe una función biyectiva de $A$ en el conjunto potencia de $A$, $\mathcal{P}(A)$. Como consecuencia de este teorema, obtenemos que existen conjuntos infinitos que no son equipotentes. Es cierto que no hemos dicho qué es un conjunto infinito, pero de momento puedes entenderlo (de manera informal) como un conjunto que tiene un subconjunto con $n$ elementos para cada $n\in\mathbb{N}$.

Teorema de Cantor. Sea $A$ un conjunto, entonces $A\preceq \mathcal{P}(A)$ pero $A\not\sim \mathcal{P}(A)$.

Demostración.

Sea $A$ un conjunto. Si $A=\emptyset$, entonces, $\emptyset$ es una función inyectiva de $A$ en $\mathcal{P}(A)$, por lo que $A\preceq\mathcal{P}(A)$. Supongamos ahora que $A\not=\emptyset$. Luego, $f:A\to \mathcal{P}(A)$ dada por $f(a)=\set{a}$ es una función inyectiva y, por tanto, $A\preceq\mathcal{P}(A)$.

Veamos ahora que no existe una biyección entre $A$ y $\mathcal{P}(A)$. Sea $f:A\to\mathcal{P}(A)$ una función. Para mostrar que $f$ no es una biyección, veamos que no es sobreyectiva. Sea $B=\{x\in A: x\notin f(x)\}$. El conjunto $B$ es un elemento en $\mathcal{P}(A)$, pero no es un elemento en la imagen de $f$. En efecto, supongamos que existe $y\in A$ tal que $f(y)=B$. Dado que $y\in A=B\cup(A\setminus B)$, entonces, $y\in B$ o $y\in A\setminus B$. Si $y\in B$, entonces, $y\notin f(y)=B$, de modo que $y\in B$ y $y\notin B$, lo cual es imposible. Ahora bien, si $y\in A\setminus B$, entonces, $y\notin B=f(y)$ y por consiguiente $y\in B$, lo cual, nuevamente, es imposible. Por lo tanto, $B$ no está en la imagen de $f$ y, en consecuencia, $f$ no es sobreyectiva.

$\square$

Lo siguiente que podemos probar es que si $A$ y $B$ son conjuntos tales que $A\preceq B$ y $B\preceq A$, entonces $A\sim B$. Este resultado corresponde al teorema de Cantor-Schröder-Bernstein que demostraremos en la próxima entrada.  

Tarea moral

Los siguientes ejercicios te permitirán aprender más resultados acerca de equipotencia y dominancia.

  1. Sean $n$ y $m$ números naturales. Muestra que $n\leq m$ si y sólo si $n \preceq m$.
  2. Demuestra que si $n$ y $m$ son números naturales distintos, entonces, o bien $n$ domina a $m$ o bien $m$ domina a $n$.
  3. Demuestra que si $A\subseteq B$, entonces $A\preceq B$.
  4. Enuncia formalmente un resultado que diga por qué la noción de «domina a» se comporta como un orden estricto.
  5. De entre las siguientes afirmaciones, decide cuáles son siempre verdaderas y para cuáles hay contraejemplos.
    • Si $|A|=|B|$ y $|C|=|D|$, entonces $|A\cup B|=|C\cup D|$.
    • Si $|A|=|B|$ y $|C|=|D|$, entonces $|A\cap B|=|C\cap D|$.
    • Si $|A|=|B|$ y $|C|=|D|$, entonces $|A\times B|=|C\times D|$.

Más adelante…

En la siguiente entrada probaremos el teorema de Cantor-Schröder-Bernstein. Este teorema nos será de gran utilidad para averiguar si dos conjuntos tienen la misma cantidad de elementos sin tener que exhibir una función biyectiva, tan sólo bastará con dar dos funciones inyectivas.

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»