1.3: Cardinalidad

Uno de los rasgos establecidos que nos serán útiles para distinguir entre estructuras algebraicas es la cardinalidad.

Definición: Cardinalidad, Finita e Infinita

Un conjunto es finito si contiene un número finito de elementos; de lo contrario, es infinito. La cardinalidad de un conjunto finito\(S\) es el número de elementos en\(S\text{;}\) que denotamos la cardinalidad de\(S\) por\(|S|\text{.}\) Cuando\(S\) es infinito, podemos escribir\(|S|=\infty\text{.}\)

Nota

Por supuesto, las barras verticales se utilizan para denotar otros conceptos matemáticos; por ejemplo, si\(x\) es un número real,\(|x|\) generalmente denota el valor absoluto de\(x\text{.}\) Debe determinar a partir del contexto, y a partir de la naturaleza de la expresión dentro de las barras, qué significan las barras verticales en un particular contexto.

Obsérvese que en la definición anterior, omitimos la definición de la cardinalidad de un conjunto infinito. Esto se debe a que definir la cardinalidad de un conjunto infinito es un esfuerzo más complicado, y uno que está, en el contexto más general, más allá del alcance de esta clase. Para nosotros, bastará con distinguir entre dos tipos de conjuntos infinitos: conjuntos infinitos contables y conjuntos incontables (o incontables infinitos).

Definición: Contable e Incontable

\(S\)Se dice que un conjunto es contablemente infinito si existe una biyección de\(S\) a\(\mathbb{Z}\) (equivalentemente, si existe una biyección de\(\mathbb{Z}\) a\(S\)). Se dice que es contable si es finito o contablemente infinito, e incontable (o incontablemente infinito) si no es contable.

Aquí hay algunos ejemplos sencillos para comenzar:

Ejemplo\(\PageIndex{1}\)

1. \(|\{a,b\}|=2\text{.}\)
2. \(|\emptyset|=0\text{.}\)
3. Claramente,\(\mathbb{Z}\) en sí mismo es contablemente infinito.

Observación

Resulta que los conjuntos contablemente infinitos tienen la misma cardinalidad entre sí, mientras que un conjunto contablemente infinito y un conjunto incontable tienen diferentes cardinalidades. Intuitivamente, se puede pensar que dos conjuntos infinitos contables tienen el mismo “tamaño”, y un conjunto contable y un conjunto incontable como que tienen diferentes “tamaños”; sin embargo, esta es una forma arriesgada de enmarcar las cosas, ya que puede hacer que algunos resultados parezcan contrarios a la intuición cuando estás acostumbrado a tratar solo con conjuntos finitos (ver, por ejemplo, Ejemplo\(1.3.2\)). Por suerte, explorar la cardinalidad de los conjuntos infinitos no es el foco de esta clase.

Quizás sorprendentemente, un subconjunto propio de un conjunto puede tener la misma cardinalidad que su superconjunto, como muestra el siguiente ejemplo.

Ejemplo\(\PageIndex{2}\)

Afirmamos que\(\mathbb{Z}^+\) es contablemente infinito. En efecto, considere la función\(f:\mathbb{Z}^+ \to \mathbb{Z}\) definida por\(f(n)=(-1)^n \lfloor \frac{n}{2} \rfloor\text{,}\) donde\(\lfloor x \rfloor\) denota el mayor número entero menor o igual a\(x\text{,}\) para cada uno\(x\in \mathbb{R}\text{.}\) El hecho de que\(f\) es una bijección se demuestra (aunque no probado) por la siguiente representación visual, donde cada número se mapea vía \(f\)al valor directamente a la derecha del mismo:

\(\begin{array} &&1\;\;\;&0 \\&1\;\;\;&1 \\&2\;\;\;&-1 \\&3\;\;\;&2 \\&4\;\;\;&-2 \\&\vdots \;\;\;& \vdots \\ \end{array}\)

Tenga en cuenta que esto significa que\(\mathbb{Z}\) y su subconjunto propio\(\mathbb{Z}^+\) tienen la misma cardinalidad, es decir, ¡el mismo “tamaño”!

Resumimos aquí ejemplos de conjuntos contables e incontables infinitos. (En las pp. 5—6 de [1], Fraleigh esboza pruebas de los hechos que\(\mathbb{Q}\) es contable y que el intervalo\((0,1)\) en\(\mathbb{R}\) es incontable. La prueba entonces que\(\mathbb{R}\) es incontable se desprende del Teorema\(1.3.1\), a continuación.)

Conjuntos infinitos contables:\(\mathbb{Z}\text{,}\)\(\mathbb{Z}^+\text{,}\)\(\mathbb{Z}^-\text{,}\)\(\mathbb{Z}^*\text{,}\)\(\mathbb{Q}\text{,}\)\(\mathbb{Q}^+\text{,}\)\(\mathbb{Q}^-\text{,}\)\(\mathbb{Q}^*\text{,}\)\(\mathbb{N}\)

Incontables conjuntos infinitos:\(\mathbb{R}\text{,}\)\(\mathbb{R}^+\text{,}\)\(\mathbb{R}^-\text{,}\)\(\mathbb{R}^*\text{,}\)\(\mathbb{C}\text{,}\)\(\mathbb{C}^*\text{,}\) el intervalo\((0,1)\) en\(\mathbb{R}\)

La idea clave aquí para nosotros es que si dos conjuntos son esencialmente “iguales”, entonces deben tener el mismo “tamaño”. Así, vemos que existe alguna diferencia fundamental entre los conjuntos\(\mathbb{Z}\) y\(\mathbb{R}\) (de hecho, hay muchas diferencias de este tipo). Por otro lado, la cardinalidad por sí sola no nos permitirá distinguir estructuralmente entre los conjuntos\(\mathbb{Z}\) y\(\mathbb{Z}^+\text{.}\)

Terminamos nuestro capítulo preliminar con el siguiente teorema y un corolario del mismo (que se puede probar mediante inducción\(n\)). Omitimos las pruebas de las dos primeras declaraciones.

Teorema\(\PageIndex{1}\)

Dejar\(A\) y\(B\) ser conjuntos.

1. Si\(A\subseteq B\) y\(A\) es infinito [incontable] entonces así es\(B\text{.}\)

2. Si\(A\subseteq B\) y\(B\) es finito [contable] entonces así es\(A\text{.}\)

3. Si\(|A|=m\lt \infty\) y\(|B|=n\lt \infty\text{,}\) luego\(|A\times B|=mn\text{.}\) Más generalmente, si\(n>1\) es un entero y\(A_1, A_2, \ldots, A_n\) se establece con\(|A_i|=k_i\lt \infty\) para cada\(i=1,2,\ldots, n\text{,}\) entonces\(|A_1 \times A_2 \times \cdots \times A_n|=k_1k_2\cdots k_n\text{.}\)

4. Dejar\(A\) y\(B\) ser conjuntos contables. Entonces\(A \times B\) es contable. Más generalmente, si\(n>1\) ser un número entero y\(A_1,A_2,\ldots, A_n\) son conjuntos contables, entonces\(A_1\times A_2\times \cdots \times A_n\) es contable.

Prueba

Prueba la primera declaración en la Parte 3 en tu tarea. El segundo enunciado en la Parte 3 sigue utilizando la inducción en el número de conjuntos.

Para probar la primera afirmación en la Parte 4: Supongamos que\(A\) y ambos\(B\) son contablemente infinitos. Dado que\(\mathbb{Z}^+\) es contablemente infinito, podemos indexar los elementos de\(A\) y de\(B\) por\(\mathbb{Z}^+\), escribir

\(A=\{a_1,a_2,…\} \text{ and } B=\{b_1,b_2,…\}\).

Observe que la mesa

\(\begin{array} &&(a_1,b_1)\;\;\;&(a_1,b_2)\;\;\;&(a_1,b_3)\;\;\;&\cdots \\ &(a_2,b_1)\;\;\;&(a_2,b_2)\;\;\;&(a_2,b_3)\;\;\;&\cdots \\ &(a_3,b_1)\;\;\;&(a_3,b_2)\;\;\;&(a_3,b_3)\;\;\;&\cdots \\ &\vdots \;\;\;&\vdots \;\;\;&\vdots \;\;\;&\ddots \\ \end{array}\)

contiene todos los elementos de\(A \times B\). Luego podemos enumerar los elementos de\(A \times B\) enumerando los elementos en diagonales progresivas superior derecha a inferior izquierda, comenzando con\((a_1,b_1)\) y moviéndonos hacia la derecha a lo largo de la fila superior: es decir, podemos escribir

\(A×B=\{(a_1,b_1),(a_1,b_2),(a_2,b_1),(a_2,b_3),(a_2,b_2),(a_3,b_1, \cdots\}\).

Esto da implícitamente una bijección de\(\mathbb{Z}^+\) a\(A \times B\); así,\(A \times B\) es contablemente infinita, y por lo tanto contable.

La prueba en el caso de que una o ambas\(A\) y\(B\) sean finitas es similar; la tabla correspondiente en ese caso simplemente tendrá ya sea solo finitamente muchas filas o finitamente muchas columnas, o ambas.

El segundo enunciado en la Parte 4 sigue utilizando la inducción sobre el número de conjuntos.

contiene todos los elementos de\(A\times B\text{.}\) We can then list the elements of \(A\times B\) by listing the elements in progressive upper-right to lower-left diagonals, starting with \((a_1,b_1)\) and moving to the right along the top row: that is, we can write

\ begin {ecuación*} A\ veces B=\ {(a_1, b_1), (a_1, b_2), (a_2, b_1), (a_2, b_3), (a_2, b_2), (a_3, b_1),\ lpuntos\}. \ end {ecuación*}

Esto da implícitamente una bijección de\(\Z^+\) to \(A\times B\text{;}\) thus, \(A\times B\) is countably infinite, and hence countable.

La prueba en el caso de que uno o ambos\(A\) and \(B\) are finite is similar; the corresponding table in that case will simply have either only finitely many rows or finitely many columns, or both.

El segundo enunciado en la Parte 4 sigue utilizando la inducción sobre el número de conjuntos.

Observación

No es cierto que cualquier producto contable de conjuntos contables (o incluso finitos) sea contable. En efecto, incluso el conjunto\(\{0,1\}\times \{0,1\}\times \cdots\) es incontable. (Si quieres entrar en los detalles grandiosos de esto, la clave es que hay una biyección de este conjunto al conjunto de poder de los números naturales, lo que el Teorema de Cantor nos dice que es incontable. Eres bienvenido a saltar por esta madriguera del conejo buscando en Google “Teorema de Cantor”, si lo deseas, pero debes saber que no serás responsable de ese material en clase.)