Archivo de la etiqueta: Cardinalidad

Álgebra Superior I: Varios tamaños de conjuntos infinitos

Por Guillermo Oswaldo Cota Martínez

2 respuestas

Introducción

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

Pensando en número grandes

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

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

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

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

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

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

$\square$

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

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

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

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

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

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

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

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

Por lo tanto, la función es biyectiva.

$\square$

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

Otros ejemplos de conjuntos con esta cardinalidad son:

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

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

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

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

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

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

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

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

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

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

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

Más adelante…

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

Tarea moral

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

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

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»

Álgebra Superior I: Cardinalidad de conjuntos finitos

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

Introducción

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

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

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

Cardinalidad de un conjunto

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

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

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

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

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

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

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

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

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

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

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

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

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

$\square$

El principio de las casillas

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

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

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

Supón tienes $9$ casillas para palomas:

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

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

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

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

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

Así hemos demostrado el principio de las casillas.

$\square$

La cardinalidad de dos conjuntos

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

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

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

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

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

Demostración.

$\Rightarrow$

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

$\Leftarrow$

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

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

$\square$

Algunas propiedades más de la cardinalidad

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

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

$\square$

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

$\square$

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

$\square$

Más adelante…

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

Tarea moral

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

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

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»

Probabilidad I: Principios de Conteo 1 – Suma y Producto

Por Octavio Daniel Ríos García

Deja un comentario

Introducción

En la entrada anterior abordamos el enfoque frecuentista de la probabilidad. El siguiente enfoque que veremos requiere de algunas herramientas adicionales. Por ello, el propósito de esta sección es hacer todos los preparativos para estudiar la siguiente medida de probabilidad importante: la probabilidad clásica. Este último enfoque se utiliza para el caso en el que $\Omega$, el espacio muestral, es finito, y se basa en la cardinalidad de $\Omega$ y la de sus subconjuntos. En consecuencia, es necesario que sepas contar la cantidad de elementos que tiene cualquier subconjunto de $\Omega$ que se te pida.

No demostraremos la validez de las propiedades para conjuntos en esta entrada, pues se trata de propiedades de conjuntos finitos. Por ello, puedes consultar nuestras notas de Álgebra Superior I en caso de que las necesites. Esta parte del curso está basada principalmente en el primer capítulo del libro Discrete and Combinatorial Mathematics: An Applied Introduction (5ᵃ edición) de Ralph P. Grimaldi.

El principio de conteo de la suma

Comenzaremos enunciando algunos principios de conteo asociados a la realización de tareas. Estos principios pueden expresarse en términos de cardinalidades de conjuntos.

Principio de la suma. Si una tarea puede realizarse de $m$ formas distintas, y otra tarea puede realizarse de $n$ formas distintas, y las dos tareas no se pueden hacer simultáneamente, entonces se puede realizar alguna de las dos tareas de $m + n$ maneras distintas.

En términos de conjuntos. Si $A$, $B$ son conjuntos finitos tales que $A \cap B = \emptyset$, entonces

\[ | A \cup B | = |A| + |B|. \]

Donde $|A|$ es la cardinalidad (número de elementos) del conjunto $A$.

Ejemplo. En la biblioteca de la Facultad de Ciencias hay $25$ libros sobre probabilidad y $15$ libros sobre álgebra moderna. Así, por el principio de la suma, un alumno de la Facultad de Ciencias puede elegir de entre $25 + 15 = 40$ libros para aprender sobre cualquiera de estos dos temas.

El principio de la suma puede extenderse a más de dos tareas, siempre y cuando se cumpla que ningún par de tareas pueda ocurrir simultáneamente. En términos de conjuntos, se tiene que para cualesquiera $A_{1}$, $A_{2}$, …, $A_{k}$ conjuntos que son ajenos dos a dos. Entonces se cumple que

\[ {\left| \bigcup_{i=1}^{k} A_{i} \right|} = \sum_{i=1}^{k} |A_{i}| \]

Precisamente, que los conjuntos sean ajenos dos a dos se interpreta como que ningún par de tareas puede realizarse simultáneamente.

Ejemplo. En la sección de ciencias de la computación de la biblioteca de la Facultad de Ciencias de la UNAM hay $7$ libros sobre C++, $6$ libros sobre Java, y $5$ libros sobre Python. En consecuencia, por el principio de la suma, una alumna de la facultad de ciencias tiene $7+6+5=18$ libros a elegir para comenzar a aprender algún lenguaje de programación.

También podemos precisar qué ocurre cuando $A$ y $B$ son finitos y no son ajenos. Primero, veamos cuando $B \subseteq A$. Como $B \subseteq A$, se cumple que $A = B \cup (A \smallsetminus B)$. Observa que $B$ y $A \smallsetminus B$ son conjuntos ajenos, por lo que

\[ |A| = |B \cup (A \smallsetminus B)| = |B| + |A \smallsetminus B|. \]

Y como la cardinalidad de un conjunto finito es un número natural, se tiene que $|B| \leq |A|$. En conclusión, si $A \subseteq B$, entonces $|B| \leq |A|$. Ahora, sabemos que para cualesquiera conjuntos finitos $A$ y $B$, los conjuntos $A$ y $B \smallsetminus A$ son ajenos, y que $A \cup B = A \cup (B \smallsetminus A)$, por lo que

\[ |A \cup B| = |A \cup (B \smallsetminus A)| = |A| + |B \smallsetminus A|, \]

y como $B \smallsetminus A \subseteq B$, se tiene que $|B\smallsetminus A| \leq |B|$, y así

\[ |A \cup B| = |A| + |B \smallsetminus A| \leq |A| + |B|. \]

En conclusión, la cardinalidad es subaditiva. De hecho, esta última propiedad se cumple para cualquier $n \in \mathbb{N}^{+}$ y cualesquiera $A_{1}$, $A_{2}$, …, $A_{n}$ conjuntos finitos:

\[ {\left| \bigcup_{i=1}^{n} A_{i} \right|} \leq \sum_{i=1}^{n} |A_{i}|. \]

Ejemplo. Una profesora de la facultad de ciencias tiene $8$ libros sobre Probabilidad en su colección, mientras que uno de sus colegas tiene $5$. Si denotamos por $m$ al número de libros diferentes sobre Probabilidad que tienen en su posesión, se cumple que

\[ 8 \leq m \leq 13, \]

pues $m$ será $8$ si el colega de la profesora tiene los mismos libros que ella (y así, el número de libros distintos que tienen en su posesión es $8$). Por otro lado, por el principio de la suma, $m$ puede tomar un valor máximo de $8 + 5 = 13$ en el caso de que los libros de la profesora y de su colega son todos distintos.

En la entrada de propiedades de una medida de probabilidad vimos un resultado conocido como el principio de inclusión-exclusión. Resulta que este principio es cierto también para la cardinalidad de conjuntos finitos. Es decir, que para cualesquiera $A$ y $B$ conjuntos finitos se cumple que

\[ |A \cup B| = |A| + |B|− |A \cap B|. \]

Más aún, para cualquier $n \in \mathbb{N}^{+}$ y cualesquiera $A_{1}$, $A_{2}$, …, $A_{n}$ conjuntos finitos se cumple que

\[ {\left| \bigcup_{i=1}^{n} A_{i} \right|} = \sum_{i=1}^{n}|A_{i}| − \sum_{i<j}|A_{i} \cap A_{j}| + \sum_{i<j<k} |A_{i} \cap A_{j} \cap A_{k}| − \cdots + (-1)^{n+1}{\left|\bigcap_{i=1}^{n} A_{i} \right|}. \]

Por ejemplo, para $n=3$ y para cualesquiera $A_{1}$, $A_{2}$, $A_{3}$ conjuntos finitos, se tiene que

\[ |A_{1} \cup A_{2} \cup A_{3}| = |A_{1}| + |A_{2}| + |A_{3}| − |A_{1} \cap A_{2}| − |A_{1} \cap A_{3}| − |A_{2} \cap A_{3}| + |A_{1} \cap A_{2} \cap A_{3}|. \]

Ejemplo. Le pedimos a tres aficionados al rock progresivo que nos dijeran sus $5$ bandas favoritas de este género musical. Sus listas son las siguientes:

Aficionado 1 ($A_{1}$)

  • Pink Floyd.
  • Genesis.
  • Marillion.
  • Rush.
  • Riverside.

Aficionado 2 ($A_{2}$)

  • King Crimson.
  • Yes.
  • Genesis.
  • Rush.
  • Pink Floyd.

Aficionado 3 ($A_{3}$)

  • Jethro Tull.
  • King Crimson.
  • Änglagård.
  • Anekdoten.
  • Yes.

Si decides escoger una banda de las que mencionaron estas tres personas, ¿cuántas opciones distintas existen? En otras palabras, ¿cuál es la cardinalidad de $A_{1} \cup A_{2} \cup A_{3}$? Para verlo, podemos valernos del principio de inclusión-exclusión. Primero, veamos los elementos que tienen en común las listas al compararlas dos a dos:

$A_{1} \cap A_{2}$

  • Pink Floyd.
  • Genesis.
  • Rush.

$A_{1} \cap A_{3}$

No tienen elementos en común.

$A_{2} \cap A_{3}$

  • King Crimson.
  • Yes.

En consecuencia, $|A_{1} \cap A_{2}| = 3$, $|A_{1} \cap A_{3}| = 0$ y $|A_{2} \cap A_{3}| = 2$. Luego, observa que no hay elementos en común entre las tres listas, por lo que $|A_{1} \cap A_{2} \cap A_{3}| = 0$. Entonces tenemos que

\begin{align*} |A_{1} \cup A_{2} \cup A_{3}| &= |A_{1}| + |A_{2}| + |A_{3}| − |A_{1} \cap A_{2}| − |A_{1} \cap A_{3}| − |A_{2} \cap A_{3}| + |A_{1} \cap A_{2} \cap A_{3}| \\ &= 5 + 5 + 5 − 3 − 0 − 2 + 0 \\ &= 15 − 5 \\ &= 10. \end{align*}

Por lo tanto, existen $10$ opciones distintas a elegir entre las bandas que mencionaron las tres personas.

El principio de conteo del producto

Ahora, ¿qué pasa cuando tenemos dos tareas y queremos hacerlas de forma consecutiva, en orden? Por ejemplo, imagina que tienes $3$ camisas distintas y $4$ pantalones distintos. ¿De cuántas maneras posibles puedes ponerte primero una camisa y luego un pantalón? Por cada una de las $3$ de camisas habrá $4$ pantalones distintos a escoger.

Figura. Figura que ilustra las maneras posibles de ponerte primero una de las $3$ camisas y luego uno de los $4$ pantalones.

En consecuencia, a la primera camisa le corresponden $4$ pantalones, a la segunda también, y a la tercera lo mismo. Por ello, el número de maneras posibles de ponerte primero una camisa y luego un pantalón serían $4 + 4 + 4 = 3 \cdot 4 = 12$.

Podemos verlo en términos de conjuntos. Sean $C = \{ c_{1}, c_{2}, c_{3} \}$ el conjunto de las camisas y $P = \{ p_{1}, p_{2}, p_{3}, p_{4} \}$ el conjunto de los pantalones. Podemos representar la idea de tomar primero una camisa y luego un pantalón a través del producto cartesiano de estos dos conjuntos:

\begin{align} C \times D = \begin{Bmatrix} (c_1,p_1), & (c_1, p_2), & (c_1, p_3), & (c_1, p_4) \\ (c_2,p_1), & (c_2, p_2), & (c_2, p_3), & (c_2, p_4) \\ (c_3,p_1), & (c_3, p_2), & (c_3, p_3), & (c_3, p_4) \end{Bmatrix}, \end{align}

observa que cada par ordenado representa cada una de las combinaciones de camisa y pantalón que puedes escoger. Por ello, $|C \times D|$ es el número total de combinaciones de camisa y pantalón posibles, que resulta ser $|C \times D| = |C||D| = 3 \cdot 4 = 12$. Además, observa que $C \times D$ representa precisamente la idea de que primero se escoge una camisa, y en segundo lugar se escoge el pantalón. Por otro lado, el conjunto $D \times C$ representa la idea de escoger primero el pantalón y después la camisa. Observa que esto no afecta el número total de combinaciones posibles.

La discusión anterior da lugar a nuestro segundo principio básico de conteo.

Principio del producto. Si una tarea puede dividirse en dos etapas y hay $m$ resultados posibles para la primera etapa y para cada una de estas etapas hay $n$ resultados posibles para la segunda etapa, entonces la tarea puede ser realizada, en el orden acordado, de $m n$ maneras distintas.

En términos de conjuntos. Para cualesquiera $A$ y $B$ conjuntos finitos se cumple que

\[ |A \times B| = |A||B|. \]

Ejemplo. Se lanzan dos dados distintos sobre una mesa. El primero tiene $6$ caras, y el segundo tiene $8$ caras. En consecuencia, esta actividad tiene $6 \cdot 8 = 48$ resultados posibles.

Ejemplo. El principio del producto puede extenderse a más de dos etapas en una misma tarea. Por ejemplo, considera la manufactura de placas para automóviles que consisten de $2$ letras seguidas de $4$ dígitos.

Figura. Ejemplo de placa de acuerdo con lo anterior. Esta placa consiste de la cadena de letras y dígitos $\textrm{A}\textrm{A}0000$.
  • Si no ponemos restricciones a la combinación de caracteres que lleva cada placa, entonces hay $26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 \cdot 10 = 6{,}760{,}000$ placas posibles, pues hay $26$ letras en el alfabeto (sin considerar a la ‘ñ’) y $10$ dígitos del $0$ al $9$.
  • Podemos restringir las combinaciones que admitimos en una placa. Si no permitimos que tenga letras repetidas, entonces la parte que corresponde a las letras tiene $26 \cdot 25$ combinaciones posibles. ¿Por qué $26 \cdot 25$ y no $26 \cdot 26$ como en el caso anterior? Precisamente porque al escoger la primera letra, la segunda no puede ser la misma, por lo que sólamente se puede escoger alguna de las $25$ restantes, que son distintas de la que ya se escogió. En consecuencia, hay $26 \cdot 25 \cdot 10 \cdot 10 \cdot 10 \cdot 10 = 6{,}500{,}000$ combinaciones de letras y dígitos en los que no se repiten las letras.
  • Por otro lado, ¿cuántas placas hay sin dígitos repetidos? En este caso, sí permitimos que las letras se repitan, así que la parte correspondiente a las letras es $26 \cdot 26$. Por otro lado, en los dígitos, queremos que no haya dígitos repetidos, así que el número de cadenas de dígitos admisibles es $10 \cdot 9 \cdot 8 \cdot 7$. Esto se debe a que para el primer dígito se tienen $10$ opciones para escoger. Luego, al haber fijado el primero, el segundo está limitado a no ser el mismo que el primero, por lo que se puede escoger alguno de $9$ dígitos restantes. Después, el tercer dígito debe de ser distinto de los dos primeros, por lo que se escoge alguno de $8$ dígitos restantes. Finalmente, el cuarto dígito debe de ser distinto de los otros tres, por lo que se debe de escoger alguno de $7$ dígitos que quedan. En conclusión, hay $26 \cdot 26 \cdot 10 \cdot 9 \cdot 8 \cdot 7 = 3{,}407{,}040$ placas en las que los dígitos son todos distintos.
  • Por último, ¿cuántas placas hay sin repeticiones? Es decir, que ninguno de los símbolos (letras o dígitos) se repite. En este caso, se tienen $26 \cdot 25 \cdot 10 \cdot 9 \cdot 8 \cdot 7 = 3{,}276{,}000$ placas posibles en las que no hay repeticiones de ningún tipo.

Ejemplo. Para guardar información, la memoria principal de una computadora contiene una colección grande de circuitos, cada uno de los cuales es capaz de almacenar un bit. Esto es, alguno de los dígitos binarios (binary digits) $0$ o $1$. Toda la información que se almacena en una computadora consiste de colecciones muy grandes de bits. Por ejemplo, los colores y las imágenes son comúnmente almacenados en forma de arreglos de bits. En el caso de las imágenes, formatos como el PNG (Portable Network Graphics) y el BMP (bitmap, «mapa de bits») son ejemplos de formatos de imagen que consisten de matrices de pequeños cuadraditos de colores llamados pixeles.

Figura. Ejemplo de una imagen digital, que consiste de una matriz de pixeles. Al hacer zoom se aprecian claramente los pixeles que constituyen a la imagen.

Aunado a esto, cada uno de los pixeles tiene un color, el cual es representado a través de un arreglo de bits. Uno de los modelos de color más utilizados en los dispositivos digitales es el modelo RGB (Red Green Blue), que combina los colores primarios rojo, verde y azul para obtener otros colores.

Sin embargo, una computadora tiene acceso a una cantidad limitada de espacios de memoria, por lo que no podemos representar todos los colores visibles. Por ello, hacemos lo posible por representar la mayor cantidad posible de colores con los recursos disponibles para la computadora. Antiguamente, las computadoras y las consolas de videojuegos tenían una cantidad muy limitada de recursos. En consecuencia, dedican una cantidad fija de bits al color. Esta cantidad es conocida como la profundidad de color. Por ejemplo, en la siguiente imagen se muestran todos los colores posibles en una profundidad de color de $6$-bits.

Figura. Todos los colores posibles que se obtienen con una profundidad de color de $6$ bits. A cada color primario se le dedican $2$ bits.

A cada color primario se le dedican $2$ bits, es decir, dos «casillas» en las que puede ir un $0$ o un $1$. Así, en cada «casilla» hay $2$ opciones a escoger, por lo que una cadena de $2$ bits tiene $2 \cdot 2 = 4$ combinaciones posibles de $0$’s o $1$’s.

Bit 1Bit 2
$0$$0$
$0$$1$
$1$$0$
$1$$1$

En la tabla anterior se ilustran todos los valores que puede tomar la lista de $2$ bits que se asigna a cada color: $00$, $01$, $10$ y $11$. Estos valores pueden pensarse como cifras en sistema binario. Así, $00_{2}$ es $0$, $01_{2}$ es $1$, $10_{2}$ es $2$ y $11_{2}$ es $3$. A cada color primario le corresponde un par de bits que representa la intensidad de rojo, verde y azul que contiene un color compuesto dado. Estos valores se combinan entre sí de manera aditiva. Por ejemplo, tener los valores $01$ en rojo, $00$ en verde y $10$ en azul resulta en un color morado como se muestra en la siguiente figura.

Figura. La cadena de dígitos $\textcolor{red}{01}\textcolor{green}{00}\textcolor{blue}{10}$ resulta en este color morado.

En conclusión, cuando la profundidad de color es de $6$ bits se tiene un total de $(2^2) \cdot (2^2) \cdot (2^2) = 64$ colores disponibles. Para ilustrar lo limitada que resulta esa cantidad, observa la siguiente imagen.

Figura. Una fotografía del castillo de Lichtenstein. A la derecha se muestra una rendición de la misma fotografía utilizando nuestros $64$ colores disponibles.

Es por esto que las computadoras y consolas de videojuegos más antiguas tienen ese característico estilo de gráficos pixelados, pues sus capacidades de procesamiento eran tan limitadas que debían de limitar la cantidad de colores que podían presentar en la pantalla o televisión.

Para que te des una idea de cuánto ha avanzado la tecnología, prácticamente cualquier computadora y celular en la actualidad tiene una profunidad de color de $24$ bits, con $8$ bits dedicados a cada color primario. Esto es, se tienen disponibles $(2^8) \cdot (2^8) \cdot (2^8) = 16{,}777{,}216$ colores distintos para escoger.

Tarea moral

Los siguientes ejercicios son opcionales. Es decir, no formarán parte de tu calificación. Sin embargo, te recomiendo resolverlos para que desarrolles tu dominio de los conceptos abordados en esta entrada.

  1. En una heladería se venden $7$ sabores de helado distintos. A unas cuadras de distancia, hay otra heladería más grande que vende $12$ sabores de helado.
    1. Asumiendo que los sabores de helado que ofrecen ambas heladerías son todos distintos, ¿cuántos sabores distintos tienes para escoger?
    2. Si no sabes los sabores que ofrecen ambas heladerías, sea $h$ el número de sabores distintos que se ofrecen en ambas heladerías. ¿Entre qué valores se encuentra $h$?
  2. Retoma el ejemplo de las placas con $2$ letras y $4$ dígitos.
    1. Si permitimos repeticiones, ¿cuántas placas tienen únicamente vocales (A, E, I, O, U) y dígitos pares?
    2. Y si no permitimos repeticiones, ¿cuántas placas tienen únicamente vocales (A, E, I, O, U) y dígitos pares?
  3. El SNES (Super Nintendo Entertainment System) es una consola muy antigua que posee una profundidad de color de $15$-bits ($5$ bits para cada color primario). ¿Cuántos colores disponibles tiene esta consola?

Más adelante…

En la siguiente entrada abordaremos otras herramientas de conteo, las permutaciones y las combinaciones. Estos nuevos conceptos son resultados que se derivan a partir del principio del producto. Por ello, es recomendable que te quede bien claro este último principio.

Los dos principios vistos en esta entrada son fundamentales para el estudio de la probabilidad clásica. En particular, el principio del producto será de gran utilidad para calcular la cardinalidad de los espacios muestrales de los experimentos aleatorios que veremos en esta parte.

Entradas relacionadas

Cálculo Diferencial e Integral I: Conjuntos infinitos (Adicional)

Por Karen González Cárdenas

Deja un comentario

Introducción

En esta última entrada de la unidad veremos un poco sobre la cardinalidad de un conjunto, un par de definiciones para decir cuando un conjunto es infinito o finito y algunos teoremas útiles. Dado que se trata de un tema adicional varios de los teoremas y resultados sólo serán enunciados.

Cardinalidad de un conjunto

Definición (Cardinalidad): Sea $A$ un conjunto. Definimos a la cardinalidad de $|A|$ como una medida que indica el número de elementos en dicho conjunto $A$ y la denotaremos como:
$$|A|.$$

Ejemplo: Sea $A= \left\{ 1,2,3,g,y,b \right\}$ así tenemos que su cardinalidad sería:
$$|A|=6.$$

Definición: Decimos que $|A| \leq |B|$ si existe una función $f: A \rightarrow B$ inyectiva.

Misma cardinalidad

Definición: Sean $A,B$ conjuntos. Decimos que $A$ y $B$ tienen la misma cardinalidad $$|A|=|B|,$$ si existe una función $f: A \leftrightarrow B$ biyectiva.

Para los fines de esta entrada, daremos la definición de función biyectiva. Revisaremos esta definición con mayor detenimiento en la unidad 3, dedicada a las funciones, como parte de este curso.

Definición: Sea $f: A \rightarrow B$ una función. Decimos que $f$ es biyectiva si cumple con ser inyectiva y sobreyectiva.

Ejemplo: Si consideramos los intervalos $[0,1]$ y $(0,1)$. Vemos que:
$$|[0,1]| = |(0,1)|.$$
Primero tomamos los valores $0$ y $1$ en el intervalo $[0,1]$ y los enviamos a los valores $\frac{1}{3}$ y $\frac{1}{2}$ respectivamente en el intervalo $(0,1)$.

Ahora consideramos los valores de la forma $\frac{1}{n}$ con $n \in \mathbb{N}\setminus \left\{0\right\}$ y $n \geq 2$. A estos valores los enviaremos a los de la forma $\frac{1}{n+2}$. De este modo lo que haremos será enviarlos al $(0,1)$ como en el ejemplo de la siguiente imagen:

Y por último, a los valores restantes los enviamos a ellos mismos en el intervalo $(0,1)$.

Así la función biyectiva sería $f: [0,1] \leftrightarrow (0,1)$:
\begin{equation*}
f(x)=
\begin{cases}
x &\text{si $x \neq 0,1,\frac{1}{n}$ con $n\geq 2$}\\
\frac{1}{2} & \text{si $x= 1$}\\
\frac{1}{3} &\text{si $x=0$}\\
\frac{1}{x+2} &\text{si $x = \frac{1}{n}$ con $n\geq 2$}\\
\end{cases}
\end{equation*}

Conjuntos finitos e infinitos

Definición (1): Sea $A$ un conjunto.

  • $A$ es finito si existe una función biyectiva $f: A \leftrightarrow \left\{1,2, \cdots , N \right\}$ para algún $N \in \mathbb{N}\setminus \left\{0\right\}$.
  • $A$ es infinito si no es finito.

Definición (2): Sea $A$ un conjunto.

  • $A$ es infinito si existe $A’ \subset A$ subconjunto propio de A y una función biyectiva $f: A’ \leftrightarrow A$.
  • $A$ es finito si no es infinito.

Teorema: Sean $A,B$ conjuntos no vacíos. Si $A \subseteq B$ entonces
$$|A| \leq |B|.$$
Demostración: Proponemos a la función $f: A \rightarrow B$ como $f(x)=x$. Observamos que $f$ es inyectiva y cumple que para todo $x \in A$ se sigue que $x \in B$. Por definición se sigue que $|A| \leq |B|.$

$\square$

Observación: Si $A,B$ son conjuntos infinitos puede ocurrir que $A \subset B$ y que $|A|=|B|.$

Teorema: Sean $A,B$ conjuntos finitos.

  • Si $A \cap B = \emptyset$ entonces:
    $|A \cup B|= |A|+|B|.$
  • Si $A \cap B \neq \emptyset$ entonces:
    $|A \cup B|= |A|+|B|-|A \cap B|.$

Definición (3): Un conjunto $A$ es infinito si existe $B \subseteq A$ tal que
$$|B|=|\mathbb{N}|.$$

Conjuntos numerables

Definición: Sea $A$ un conjunto no vacío. Decimos que $A$ es numerable si $|A|=|\mathbb{N}|$ es decir si existe una función biyectiva:
$$f: A \rightarrow \mathbb{N}.$$

Teorema: Sean $A,B$ conjuntos. Si $A$ es finito y $B$ es infinito numerable entonces $A \cup B$ es numerable.
Demostración: Como $A$ es finito consideremos que tiene $m$ elementos.
$$A = \left\{ a_{1}, a_{2}, \cdots , a_{m} \right\}.$$
Y como $B$ es infinito y numerable entonces es de la forma:
$$B = \left\{ b_{1}, b_{2}, \cdots , b_{n}, \cdots \right\}.$$
Así al considerar la unión $A \cup B$ tendríamos:
$$A \cup B = \left\{ a_{1}, a_{2}, \cdots , a_{m}, b_{1}, b_{2}, \cdots , b_{n}, \cdots \right\}.$$
Tenemos los siguientes dos casos:

  • Si $A\cap B = \emptyset$ y consideramos la siguiente indización:
    $$A \cup B = \left\{ a_{1}, a_{2}, \cdots , a_{m}, b_{m+1}, b_{m+2}, \cdots , b_{m+n}, b_{m+n+1}, \cdots \right\}.$$
    Vemos $|A \cup B|=|\mathbb{N}|.$
  • Si $A\cap B \neq \emptyset$. Supongamos que tenemos $k$ elementos en la intersección, es decir:
    $$a_{1}= b_{1}, a_{2}= b_{2}, \cdots , a_{k}= b_{k}$$
    $$A = \left\{ a_{1}, a_{2}, \cdots ,a_{k}, a_{k+1}, \cdots, a_{m} \right\}.$$
    Así consideramos la siguiente indización para la unión:
    $$A \cup B = \left\{ a_{k+1}, a_{k+2}, \cdots , a_{m}, b_{1}, b_{2}, \cdots , b_{n}, \cdots \right\}.$$
    Observamos que $|A \cup B|=|\mathbb{N}|.$

$\square$

Teorema: Si $A$ y $B$ son conjuntos infinitos y numerables entonces $A \cup B$ es infinito y numerable.
Demostración: Primero vemos que $A \cup B$ es infinito ya que al ocurrir que:

  • $A \subseteq A \cup B$ con $A$ infinito y numerable.
  • $B \subseteq A \cup B$ con $B$ infinito y numerable.

por definición (3) concluimos que $A \cup B$ es infinito.

Nos falta ver qué $A \cup B$ es numerable, ya que $A$ es numerable podemos escribirlo de la siguiente manera:
$$A = \left\{ a_{1}, a_{2}, \cdots \right\}.$$
Análogamente para $B$:
$$B = \left\{ b_{1}, b_{2}, \cdots \right\},$$
por lo que la unión se vería como:
$$A \cup B= \left\{ a_{1}, b_{1},a_{2}, b_{2},a_{3},b_{3} \cdots, a_{n}, b_{n}, \cdots \right\}.$$
Observemos que si consideramos la siguiente indización:
$$A \cup B= \left\{ a_{1}, b_{2},a_{3}, b_{4},a_{5},b_{6} \cdots, a_{2n-1}, b_{2n}, \cdots \right\},$$

el conjunto tiene una relación biunívoca con el conjunto de los naturales.
Veamos qué sucede en los siguientes casos:

  • Si $A \cap B = \emptyset \Rightarrow |A \cup B|=|\mathbb{N}|.$
  • Si $A \cap B \neq \emptyset$. Consideremos que existen k elementos en la intersección, por lo que serían de la forma:
    $$a_{1}= b_{1}, a_{2}= b_{2}, \cdots , a_{k}= b_{k}.$$
    Por lo que ahora la unión se vería como:
    $$A \cup B= \left\{ a_{1}, a_{2}, a_{3}, \cdots,a_{k}, a_{k+1}, b_{k+1},a_{k+2}, b_{k+2} \cdots, a_{k+n}, b_{k+n}, \cdots \right\}$$
    y si consideramos la siguiente nueva indización:
    $$A \cup B= \left\{ a_{1}, a_{2}, a_{3}, \cdots,a_{k}, a_{k+1}, b_{k+2},a_{k+3}, b_{k+4} \cdots, a_{k+(2n-1)}, b_{k+2n}, \cdots \right\},$$
    tenemos que tiene una relación biunívoca con $\mathbb{N}$ por lo que también se cumple que $|A \cup B|=|\mathbb{N}|$.

$\square$

A continuación enunciaremos un teorema que generaliza el resultado sobre conjuntos numerables ya visto.

Teorema: Sean $A_{1}, A_{2}, \cdots, A_{N}, \cdots $ conjuntos no vacíos.

  • Si $A_{1}, A_{2}, \cdots, A_{N}$ son numerables $\Rightarrow \begin{multline*} \bigcup_{i=1}^{N} A_{i} \end{multline*}$ es numerable.
  • Si $A_{1}, A_{2}, \cdots$ son numerables $\Rightarrow \begin{multline*} \bigcup_{i=1}^{\infty} A_{i} \end{multline*}$ es numerable.

Más adelante

Ahora que hemos concluido con la unidad relacionada a los Números reales, en la próxima iniciaremos el tema de funciones definiendo qué es el dominio, rango y regla de correspondencia de una función.

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»

Álgebra Superior II: El tamaño de los naturales y de cada natural

Por Roberto Manríquez Castillo

Deja un comentario

Introducción

En la entrada pasada, demostramos que todo número natural es el conjunto formado por los elementos $\{0,1,…,n-1\}$. Esto nos dice intuitivamente que cada número natural $n$, tiene exactamente $n$ elementos. Pero, de modo formal, ¿qué quiere decir que un conjunto tenga $n$ elementos? Esto lo precisaremos en esta entrada. Más aun, siguiendo esta idea, definiremos que quiere decir que un conjunto sea infinito. Después, veremos las propiedades que los conjuntos finitos e infinitos tienen.

El tamaño de los conjuntos

A la hora de pensar en determinar el tamaño de un conjunto, uno podría aventurarse y empezar a contar los elementos de este uno por uno. Esta forma de aproximar el problema no sólo parece muy laboriosa, sino que también presenta el problema de que no todos los conjuntos tienen la propiedad de que se pueda enlistar a sus elementos (aunque no lo definimos aún, seguramente has escuchado que el conjunto $\mathbb{R}$ de números reales no cumple esta propiedad).

De entrada, parecería que el problema de catalogar a los conjuntos por su tamaño es más complicado de lo que parece. Sin embargo, hay una idea famosa que viene a salvar la situación.

Imagina que eres el acomodador de una sala de cine con una cantidad desconocida de asientos (incluso posiblemente infinita) y que quieres sentar en ellos a un cierto conjunto de espectadores (cuya cantidad también se desconoce). Como dijimos anteriormente, la labor de contar todos los asientos de la sala podría ser demasiado complicada. ¿Cómo podríamos cerciorarnos de que cada espectador podrá tener un asiento?

La respuesta es inusualmente sencilla. La mejor forma de cerciorarse de que todos puedan sentarse, es pidiéndoles que se sienten. Si logran hacerlo de modo que a cada asistente le toque exactamente un asiento y no sobren asientos, podremos decir que hay el mismo número de personas que de lugares.

Notemos que de esta forma no necesitamos saber de forma explícita cuántas sillas hay, ni cuantas personas asistieron a la función, para saber que hay la misma cantidad de personas que de sillas. Formalmente hablando, hemos dado una relación entre el conjunto de personas y el de asientos.

Recordemos que a una relación entre conjuntos se le llama función si a cada elemento de nuestro dominio le corresponde uno y solo un elemento del codominio. Más aún, si a todo elemento del codominio, está relacionado con uno del dominio, la función se llamará suprayectiva. Si una función satisface que los elementos del codominio se relacionan con a lo más un elemento del dominio, se le llama función inyectiva. Cuando ambas condiciones se satisfacen, diremos que la función es biyectiva.

Nota que en el ejemplo de la sala de cine, si logramos hacer que todos los asistentes se sienten sin que sobre alguna silla, entonces la función que damos es una función biyectiva. Con estas observaciones, introducimos la siguiente definición.

Definición. Diremos que dos conjuntos $A$ y $B$ tienen la misma cantidad de elementos, o la misma cardinalidad, si existe una función biyectiva entre ellos. En este caso escribimos $\vert A\vert=\vert B \vert$.

El tamaño del conjunto $\mathbb{N}$

Aunque los conjuntos finitos parecen ser más cercanos a nuestra realidad, será más interesante definir primero qué son los conjuntos infinitos. Para ello usaremos una de las propiedades «raras» que estos tienen.

Definición. Diremos que un conjunto $X$ es infinito si existe un subconjunto propio $Y$ de $X$ y una función $f:X\to Y$ biyectiva entre ambos conjuntos.

Recuerda que un subconjunto propio es cualquier subconjunto que no sea el conjunto original. En otras palabras, un conjunto es infinito si tiene el mismo tamaño que alguno de sus subconjuntos propios.

Definición. Diremos que un conjunto es finito si no es infinito.

La propiedad que usamos para caracterizar a los conjuntos infinitos fue muy novedosa cuando se enunció por primera vez. Incluso con los años fue el origen de aparentes paradojas al sentido común. Si el tema te parece interesante, puedes leer o ver algún vídeo sobre el famoso Hotel de Hilbert.

Con nuestra definición lista, empezaremos a catalogar los conjuntos que ya conocemos en finitos e infinitos.

Teorema. El conjunto $\mathbb{N}$ de números naturales es infinito.

Demostración. Para demostrar esto, consideraremos el conjunto $\mathbb{N}\setminus\{0\}$. Este es un subconjunto propio de $\mathbb{N}$. Tomemos la función $\sigma:\mathbb{N}\to \mathbb{N}\setminus\{0\}$. De acuerdo con la definición de conjunto infinito hay que demostrar que $\sigma$ es biyectiva, es decir, que es inyectiva y suprayectiva.

El hecho de que el codominio esté bien definido y que $\sigma$ sea inyectiva, fue demostrado en la entrada La construcción de los naturales, a la hora de probar los axiomas de Peano. La prueba de la suprayectividad se dejó como un ejercicio moral en la entrada de Principio de inducción y teoremas de recursión, ya que se usó para la prueba del teorema de Recursión débil. De cualquier forma, a continuación damos esa prueba.

Demostraremos que $\{0\}\cup \sigma(\mathbb{N})$ es inductivo. Evidentemente $0\in\mathbb{N}$ , y si $n\in \{0\}\cup\sigma(\mathbb{N})$, entonces es trivial que $\sigma(n)\in\sigma(\mathbb{N})$. Entonces $\{0\}\cup \sigma(\mathbb{N})=\mathbb{N}$, por lo que $\sigma(n)$ sí es suprayectiva y por lo tanto biyectiva. Con esto se concluye la prueba.

$\square$

La idea de determinar si dos conjuntos tienen la misma cantidad de elementos usando funciones se puede extender un poco más. La usaremos a continuación para definir cuándo un conjunto tiene al menos tantos elementos como otro.

Definición. Decimos que un conjunto $A$ tiene a lo más tantos elementos como un conjunto $B$ si existe una función inyectiva $f:A\to B$. En este caso, escribimos $\vert A\vert\leq \vert B \vert$.

Todo número natural es finito

Como hemos visto, los conjuntos infinitos se comportan de forma inesperada. Sin embargo los conjuntos finitos sí se comportarán de una forma más intuitiva. El teorema siguiente ejemplifica esto.

Teorema. Si $A$ es un conjunto finito, y $f:A\to A$, entonces son equivalentes las siguientes tres afirmaciones:

  1. $f$ es biyectiva
  2. $f$ es inyectiva
  3. $f$ es suprayectiva

Demostración. Evidentemente, $1)\Rightarrow 2)$ y $1)\Rightarrow 3)$. Si logramos demostrar la equivalencia entre $2)$ y $3)$ terminaremos, pues al tener uno, tendríamos el otro y por lo tanto tendríamos ambas partes de la definición de biyectividad.

$2)\Rightarrow 3)$ Supongamos que $f$ es inyectiva y supongamos que $f$ no es suprayectiva. Entonces $f:A\to f(A)$ es una biyección de $A$ con un subconjunto propio, lo cual diría que $A$ es infinito. Esto es una contradicción, así que $f$ debe ser suprayectiva.

$3)\Rightarrow 2)$ Si $f$ es suprayectiva, entonces tiene inversa derecha, es decir, existe $g:A\to A$ tal que $f\circ g=Id_A$. A partir de esta igualdad se puede probar que $g$ es inyectiva. En efecto, si $g(a)=g(b)$, entonces $f(g(a))=f(g(b))$, pero entonces $a=b$. Por la implicación del párrafo anterior, $g$, también es suprayectiva. Pero con esto se puede mostrar que $f$ es inyectiva. Si tenemos $a$ y $b$ tales que $f(a)=f(b)$, tomemos $c$ y $d$ tales que $g(c)=a$ y $g(d)=b$. De aquí, $c=f(g(c))=f(g(d))=d$ y por lo tanto $a=g(c)=g(d)=b$.

$\square$

Sigamos estudiando propiedades de los conjuntos infinitos. El siguiente resultado es bastante intuitivo: si le quitamos un elemento a un conjunto infinito, sigue siendo infinito. La demostración es algo elaborada pues debemos hacerla a partir de nuestras definiciones.

Lema 1. Si $X$ es un conjunto infinito y $x\in X$, entonces $X\setminus \{x\}$ también es un conjunto infinito.

Demostración. Sea $f:X\to A $ una biyección de $X$ a un subconjunto propio $A$. Tenemos que considerar dos casos: que $x\notin A$ o que $x\in A$. Comencemos con el caso $x\notin A$.

Para mostrar que $X\setminus \{x\}$ es infinito, utilizaremos como subconjunto a $A\setminus\{f(x)\}$ y como función a la restricción de $f$ a $X\setminus\{x\}$. Debemos demostrar que $A\setminus\{f(x)\}$ es un subconjunto propio de $X\setminus \{x\}$ y que dicha restricción es una biyección.

Lo primero sucede ya que $$A\setminus\{f(x)\}\subsetneq A\subseteq X\setminus \{x\}.$$ El hecho de que $f:X\setminus \{x\}\to A\setminus\{f(x)\}$ sea una biyección es consecuencia directa de que originalmente $f:X\to A $ era una biyección. Los detalles quedan como tarea moral.

Si por el contrario $x\in A$, como $A\subsetneq X$ debe existir $x’\in X\setminus A$. Consideremos la función

\begin{align*}
&g: & &X & &\longrightarrow & (A\cup \{x’&\})\setminus \{x\}& \\
& & &y & &\mapsto & f(&y) &\text{ si } y\neq f^{-1}(x) \\
& & f^{-1}&(x) & &\mapsto & &x’ &
\end{align*}

Veamos que $g$ es una biyección entre $X$ y $(A\cup \{x’\})\setminus \{x\}$. Lo primero que notamos es que el codominio está bien definido ya que para todo $y\in X$ se tiene que $g(y)\neq x$ (¿por qué?).

Además es inyectiva, ya que si $g(y)=g(z)$, con $y\neq f^{-1}(x)\neq z$, entonces se tiene que $f(y)=g(y)=g(z)=f(z)$, y por la inyectividad de $f$ se tiene que $y=z$. Mientras que si $y=f^{-1}(x)$, tenemos que $g(y)=x’=g(z)$ si $z\neq f^{-1}(x)$, tendríamos que $x’=f(z)$, por lo que $x’\in A$ lo cual es absurdo, entonces $z=f^{-1}(x)=y$, así $g$ es efectivamente inyectiva.

Para probar que es suprayectiva, consideremos $z\in(A\cup \{x’\})\setminus \{x\}$. Si $z=x’$, entonces $g(f^{-1}(x))=x’$, mientras que si $z\in A\setminus \{x\}$, por la suprayectvidad de $f$, debe de existir $y$ tal que $f(y)=z$. Además $y\neq f^{-1}(x)$ ya que si lo fuera $f(f^{-1}(x))=x=z$, lo cual sería absurdo. Se tiene entonces que $g(y)=f(y)=z$.

Con esto probamos que $g$ es una biyección de $X$ a un subconjunto propio al que no pertenece $x$. Para concluir, aplicamos el primer caso.

$\square$

Usando el lema anterior es fácil dar un corolario importante sobre conjuntos finitos, cuya prueba queda como un ejercicio.

Corolario. Si $X$ es un conjunto finito, y $x$ es un conjunto arbitrario, entonces $X\cup \{x\}$ es también un conjunto finito.

Armados con este corolario, podemos dar uno de los teoremas importantes de esta entrada.

Teorema. Si $n$ es un natural, entonces $n$ es un conjunto finito.

Demostración. Procedamos por inducción. Si $n=0$, entonces $n=\emptyset$, entonces $n$ no tiene subconjuntos propios con los que pueda biyectarse, ya que no tiene subconjuntos propios. Entonces por vacuidad el vacío es finito.

Supongamos que $n$ es un natural finito. Debemos demostrar que $\sigma(n) $ es también finito. Pero como $\sigma(n)=n\cup\{n\}$, el paso inductivo es consecuencia del corolario anterior. Con esto concluimos la inducción.

$\square$

Caracterizando los conjuntos finito e infinitos

Ya probamos que cada número natural es finito y que el conjunto de todos los naturales es infinito. Lo siguiente que haremos es ver que estos conjuntos nos sirven para catalogar a todos los demás conjuntos en finitos o infinitos. Comenzamos con un lema bastante intuitivo: si con conjunto tiene un subconjunto infinito, entonces es infinito.

Lema 2. Si $X$ es infinito y $X\subset Y$ entonces $Y$ también es infinito.

Demostración. Como $X$ es infinito, existe una biyección $f$ entre $X$ y uno de sus subconjuntos propios $A$. Consideremos entonces $(Y\setminus X)\cup A\subsetneq Y$, y demos una biyección entre $Y$ y este conjunto dada por

\begin{align*}
&g: & &Y & &\longrightarrow &(Y\setminus &X)\cup A & \\
& & &y & &\mapsto & &y &\text{ si } y\notin Y\setminus X\\
& & &x & &\mapsto & f(&x) &\text{ si } x\in X
\end{align*}

Probaremos que esta función es una biyección. Primero, veamos que es inyectiva. Esto se debe a que si $g(x)=g(y)$ y $x\in X$, entonces $g(y)=g(x)=f(x)\in A\subset X$, entonces $g(y)$ está en $X$, y como $Y\setminus X$ es enviado en si mismo, debe pasar que $y$ también está en $X$, por lo que $f(y)=g(y)=f(x)$ y por la inyectividad de $f$, tenemos que $y=x$. Por el contrario, si $x\notin X$, se tiene que $g(x)=x=g(y)$ entonces $g(y)\notin X$, por lo que $y$ tampoco puede estar en $X$, así, $g(y)=y=x$.

Veamos ahora que la función es suprayectiva. Si $z\in(Y\setminus X)\cup A$, consideremos dos casos: $z\in Y\setminus X$ en cuyo caso $g(z)=z$, o $z\in A$, por lo que por la suprayectividad de $f$, debemos tener que existe $x\in X$ tal que $z=f(x)=g(x)$. Así, $g$ es suprayectiva y por lo tanto es una biyección..

$\square$

Ahora sí, pasamos a demostrar los teoremas con los que concluiremos la entrada.

Teorema. El conjunto de números naturales es el conjunto infinito más pequeño, es decir, que si $X$ es un conjunto infinito, entonces $\vert\mathbb{N}\vert\leq\vert X\vert$.

Demostración. Como $X$ es infinito, debe ser distinto del vacío. Así, existe $x_0\in X$. Consideremos el conjunto $X\setminus \{x_0\}$, por el lema 1 que demostramos, este es de nuevo infinito. Una vez más, no es vacío, entonces existe $x_1\in X\setminus \{x_0\}$, y el conjunto $X\setminus\{x_0,x_1\}=(X\setminus \{x_0\})\setminus\{x_1\}$ será de nuevo infinito. Procediendo de manera recursiva, podemos dar una función

\begin{align*}
h: &\mathbb{N} \to X \\
& n \mapsto x_n
\end{align*}

tal que todos los $x_n$ son distintos entre sí (esto se puede demostrar inductivamente). Pero entonces $h$ es una función inyectiva de $\mathbb{N}$ al conjunto $X$, que es precisamente nuestra definición de que $\vert\mathbb{N}\vert\leq \vert X\vert $.

$\square$

El regreso del teorema anterior es evidentemente cierto, es decir que si un conjunto $X$ cumple que $\vert\mathbb{N}\vert\leq \vert X\vert $, entonces $X$ es infinito. Queda como ejercicio demostrarlo.

Para finalizar la entrada, damos un resultado análogo al anterior, para conjuntos finitos.

Teorema. Si $X$ es un conjunto finito, entonces existe $n\in\mathbb{N}$ tal que $\vert X\vert =\vert n\vert$.

Demostración. Si $X=\emptyset$, entonces $\vert\emptyset\vert= \vert X\vert $. Si $X$ no es vacío, entonces existe $x_0\in X$. Consideremos entonces $X\setminus \{x_0\}$. Si este conjunto es vacío, significa que $X=\{x_0\}$ y claramente podríamos biyectarlo con el conjunto $\sigma(0)=\{0\}$. Si por el contrario, $X\setminus \{x_0\}\neq \emptyset$, podemos elegir $x_1\in X\setminus \{x_0\}$ y verificar la misma condición.

Necesariamente debemos de terminar en algún momento pues, de otro modo, podremos usar el teorema de recursión para construir una función inyectiva de $\mathbb{N}$ a $X$. Esto diría que $X$ sería infinito, lo cual sería absurdo.

Entonces debe ocurrir que existe una $n$ tal que $X\setminus\{x_0,x_1,…,x_n\}$ es vacío, por lo que $X=\{x_0,x_1,…,x_n\}$, y por lo tanto podemos biyectarlo con $\sigma(n)$.

$\square$

Más adelante…

Así como los conjuntos transitivos, la teoría que se desarrolla al estudiar las cardinalidades de los conjuntos es un área de estudio importante en la teoría de conjuntos. Aunque no lo veremos a profundidad, la teoría que acabamos de desarrollar es suficiente para comparar la cardinalidad de la mayoría de los conjuntos que veamos con total precisión. Esto será cierto para, conjuntos como $\mathbb{Z}$ (el de los números enteros) o $\mathbb{Q}$ (el de los números racionales). No será sino hasta que definamos el conjunto de números reales que tendremos un conjunto con una cardinalidad estrictamente mayor que la de $\mathbb{N}$.

En la siguiente entrada definiremos el orden de los naturales, para lo cual de nuevo pensaremos a los números naturales como conjuntos. Más aún, las propiedades que estudiamos en la entrada pasada, serán de suma importancia a la hora de definir el buen orden de un conjunto. Esta es una propiedad que usamos anteriormente sin prueba, cuando demostramos el teorema de Recursión.

Tarea moral

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

  1. Supón que diriges un hotel con tantas habitaciones como números naturales. Supón que todas tus habitaciones se encuentran ocupadas, y de repente llega una persona solicitando un cuarto. ¿Cómo puedes hospedarlo sin desalojar a ningún cliente? Supón ahora que después llega un camión con tantas personas como números naturales, todas buscando un cuarto. ¿De qué forma puedes acomodarlos a ellos y a todos los clientes ya hospedados?
  2. Completa los detalles de la prueba del lema 1.
  3. Demuestra el corolario de la entrada: Si $X$ es un conjunto finito, y $x$ es un conjunto arbitrario, entonces $X\cup \{x\}$ es también un conjunto finito.
  4. Demuestra que si $X$ es tal que $\vert\mathbb{N}\vert\leq \vert X\vert $, entonces $X$ es infinito.
  5. Demuestra por inducción que si $X$ es infinito y $A$ es un subconjunto con $k$ elementos, entonces $X\setminus A$ es infinito. Si $A$ tiene tantos elementos como naturales, ¿el resultado sigue siendo cierto?

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»