Cardinalidad: Comprendiendo el Tamaño de los Infinitos

Comparando el Tamaño de Conjuntos

Definición Inicial

Cuando hablamos de “cardinalidad”, simplemente nos referimos al “tamaño” de un conjunto, es decir, a cuántos elementos tiene. Para conjuntos finitos, esto es trivial: el conjunto {1, 2, 3} es más pequeño que el conjunto {a, b, c, d} porque 3 es menor que 4. Pero, ¿cómo comparamos el tamaño de conjuntos infinitos? ¿Es el conjunto de todos los números pares (infinito) más pequeño que el conjunto de todos los números enteros (también infinito)?

Explicación Didáctica

Imagina que tienes dos salones de baile, el Salón A y el Salón B, y quieres saber cuál tiene más gente. Una forma es contarlos a todos, pero eso es difícil si la gente entra y sale. Una forma más inteligente es pedirles que busquen pareja.

Si puedes lograr que cada persona del Salón A encuentre una pareja única en el Salón B (nadie de A comparte pareja en B), sabes que el Salón B es al menos tan grande como el Salón A. A esto los matemáticos le llaman una función inyectiva: una asignación uno a uno donde B puede tener personas “sobrantes”.

Definición Formal

Decimos que la cardinalidad de un conjunto A es menor o igual que la cardinalidad de un conjunto B (denotado como $A \le B$) si existe una función inyectiva $f: A \rightarrow B$.

Para decir que la cardinalidad de A es estrictamente menor ($A < B$), debemos ser capaces de demostrar que $A \le B$ (existe una inyección de A a B) y que, al mismo tiempo, es imposible encontrar una inyección de B a A (es decir, $B \not\le A$).

Ejemplo Resuelto

Veamos si el conjunto $A = \{a, b, c\}$ es menor o igual que $\mathbb{N} = \{0, 1, 2, 3, ...\}$. Para demostrar que $A \le \mathbb{N}$, solo necesitamos encontrar una función inyectiva. Definimos $f: A \rightarrow \mathbb{N}$ como:

• $f(a) = 1$
• $f(b) = 2$
• $f(c) = 3$ Como cada elemento de A se asigna a un elemento único de $\mathbb{N}$, la función es inyectiva. Por lo tanto, $A \le \mathbb{N}$.

Resumen Rápido

Para comparar tamaños de conjuntos, especialmente infinitos, usamos funciones. Una función inyectiva de A a B demuestra que B es al menos tan grande como A.

---

Equinumerosidad: El Mismo Tamaño Infinito

Definición Inicial

Decir que dos conjuntos tienen exactamente el mismo tamaño (la misma cardinalidad) se llama “equinumerosidad”.

Explicación Didáctica

Volvamos a los salones de baile. Para saber si tienen exactamente el mismo tamaño, no basta con que el Salón A pueda encontrar pareja en el B. Necesitamos una “pareja perfecta”: cada persona en A tiene una pareja en B, y cada persona en B tiene una pareja en A. No sobra nadie en ninguno de los dos salones. Esta correspondencia perfecta, bidireccional y completa se llama función biyectiva.

Definición Formal

Dos conjuntos A y B son equinumerosos, o tienen la misma cardinalidad (denotado como $A \approx B$), si existe una función biyectiva $f: A \rightarrow B$.

Un teorema increíblemente útil es el de Schröder-Bernstein. Este teorema dice que si puedes encontrar una inyección de A a B ($A \le B$) y también puedes encontrar una inyección de B a A ($B \le A$), entonces debe existir una biyección entre ellos ($A \approx B$), incluso si es difícil construirla.

Ejemplo Resuelto

Demostremos que $\mathbb{N} = \{0, 1, 2, ...\}$ es equinumeroso al conjunto de las potencias de 2, $P = \{1, 2, 4, 8, 16, ...\}$ (o $\{2^i \mid i \in \mathbb{N}\}$ ). Buscamos una biyección $f: \mathbb{N} \rightarrow P$. Definimos $f(i) = 2^i$.

• $f(0) = 2^0 = 1$
• $f(1) = 2^1 = 2$
• $f(2) = 2^2 = 4$ …y así sucesivamente. Esta función es inyectiva (diferentes números naturales $i$ y $j$ dan diferentes potencias $2^i$ y $2^j$) y suryectiva (cada elemento en P es, por definición, una potencia de 2, por lo que tiene un $i$ correspondiente en $\mathbb{N}$). Como $f$ es una biyección, concluimos que $\mathbb{N} \approx P$.

Resumen Rápido

Dos conjuntos (finitos o infinitos) tienen el mismo tamaño si podemos establecer una correspondencia biyectiva perfecta entre sus elementos.

---

Conjuntos Enumerables: El Infinito “Contable”

Definición Inicial

El concepto de “enumerable” se refiere al tipo de infinito más pequeño que existe, el infinito que podemos, en teoría, “contar” o “listar”.

Explicación Didáctica

Un conjunto es enumerable (o “contable”) si puedes poner todos sus elementos en una lista infinita, uno tras otro, sin saltarte ninguno. Es como darle a cada elemento una etiqueta: “1ro”, “2do”, “3ro”, etc., usando todos los números naturales. El conjunto $\mathbb{N} = \{0, 1, 2, ...\}$ es el prototipo de un conjunto enumerable.

Definición Formal

Un conjunto infinito $A$ se dice enumerable si es equinumeroso con el conjunto de los números naturales $\mathbb{N}$, es decir, si $A \approx \mathbb{N}$.

Ejemplo Resuelto (Los Enteros $\mathbb{Z}$)

A primera vista, $\mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\}$ parece el doble de grande que $\mathbb{N}$, que solo tiene los positivos y el cero. Pero, ¿podemos “listarlos”? ¡Sí! Esta es la enumeración: $0, 1, -1, 2, -2, 3, -3, ...$ Podemos definir una biyección $f: \mathbb{N} \rightarrow \mathbb{Z}$ basada en esta lista. Esto demuestra que $\mathbb{Z} \approx \mathbb{N}$. Los enteros son enumerables.

Ejemplo Resuelto (Los Racionales $\mathbb{Q}$)

Esto es aún más sorprendente. Los números racionales $\mathbb{Q}$ (todas las fracciones) parecen muchísimo más grandes. Entre $0$ y $1$ hay infinitos racionales. Sin embargo, $\mathbb{Q}$ también es enumerable. La demostración formal es más compleja, pero la idea es que podemos organizar todos los pares de números naturales $(i, j)$ en una lista (demostrando que $\mathbb{N} \times \mathbb{N}$ es enumerable ). Si podemos listar todos los pares $(numerador, denominador)$, podemos listar todos los números racionales. Técnicamente, se demuestra que $\mathbb{Q} \le \mathbb{N}^3$ y que $\mathbb{N}^k \approx \mathbb{N}$ para cualquier $k$. Dado que $\mathbb{N} \le \mathbb{Q}$ (obvio) y $\mathbb{Q} \le \mathbb{N}$, por el teorema de Schröder-Bernstein, se concluye que $\mathbb{Q} \approx \mathbb{N}$.

Resumen Rápido

Un conjunto es enumerable si tiene la misma cardinalidad que $\mathbb{N}$. A pesar de la intuición, tanto el conjunto de los números enteros ($\mathbb{Z}$) como el de los números racionales ($\mathbb{Q}$) son enumerables.

---

Los Números Reales y el Infinito “No Enumerable”

Definición Inicial

Ya que $\mathbb{Z}$ y $\mathbb{Q}$ son enumerables, surge la pregunta: ¿son todos los conjuntos infinitos enumerables? La respuesta es un rotundo no. El conjunto de los números reales ($\mathbb{R}$), que incluye a los racionales e irracionales (como $\pi$, $e$, $\sqrt{2}$), representa un tipo de infinito fundamentalmente más grande.

Explicación Didáctica (La Diagonalización de Cantor)

La prueba de que $\mathbb{R}$ no es enumerable es una de las ideas más bellas de las matemáticas. Se llama el “argumento de la diagonalización”.

Imagina que alguien afirma tener una lista completa de todos los números reales entre 0 y 1 (es suficiente probarlo para este intervalo ). Su lista (que suponen una biyección $f: \mathbb{N} \rightarrow (0,1)$ ) se vería algo así:

1. $f(0) = 0, \textbf{1} 4 1 5 9 ...$
2. $f(1) = 0, 5 \textbf{0} 0 0 0 ...$
3. $f(2) = 0, 1 2 \textbf{3} 4 5 ...$
4. $f(3) = 0, 8 2 4 \textbf{6} 3 ...$ …y así para siempre.

Ahora, vamos a construir un número “villano”, $r$, que sabemos que no puede estar en su lista. Construimos $r$ dígito por dígito, asegurándonos de que sea diferente a cada número de la lista en al menos un lugar.

Para el primer dígito de $r$, miramos el primer dígito del primer número (un 1) y elegimos algo diferente (digamos, 4).

• $r = 0, \textbf{4} ...$

Para el segundo dígito de $r$, miramos el segundo dígito del segundo número (un 0) y elegimos algo diferente (digamos, 4).

• $r = 0, 4 \textbf{4} ...$

Para el tercero, miramos el tercer dígito del tercer número (un 3) y elegimos algo diferente (digamos, 4).

• $r = 0, 4 4 \textbf{4} ...$

Continuamos este proceso, tomando el $i$-ésimo dígito del $i$-ésimo número (la diagonal) y eligiendo un dígito diferente para el $i$-ésimo dígito de $r$.

Este nuevo número $r$ (por ejemplo, $0,444...$) es un número real entre 0 y 1. Pero, ¿dónde está en la lista?

• No puede ser el 1er número (difieren en el 1er dígito).
• No puede ser el 2do número (difieren en el 2do dígito).
• No puede ser el 3er número (difieren en el 3er dígito).
• …no puede ser el $i$-ésimo número (difieren en el $i$-ésimo dígito).

El número $r$ que construimos no está en la lista. Esto significa que la lista original estaba incompleta, y cualquier lista que intentes hacer estará incompleta. Es imposible “listar” todos los números reales.

Definición Formal

El Teorema de Cantor (1891) establece que $\mathbb{N} < \mathbb{R}$. La prueba por contradicción, conocida como el argumento de la diagonalización, asume que existe una biyección $f: \mathbb{N} \rightarrow (0,1)$. Se construye un número real $r = 0.r_0r_1r_2...$ definiendo cada $i$-ésimo dígito $r_i$ para que sea diferente del $i$-ésimo dígito del $i$-ésimo número en la lista, $d_{i,i}$. (Para evitar la ambigüedad de $1,000...$ vs $0,999...$ , la prueba elige dígitos de forma segura, por ejemplo: $r_i = 5$ si $d_{i,i} \ne 5$, y $r_i = 4$ si $d_{i,i} = 5$ ). El número $r$ resultante no puede estar en la imagen de $f$, demostrando que $f$ no es suryectiva, lo que es una contradicción.

Resumen Rápido

El conjunto de los números reales $\mathbb{R}$ es no enumerable. Representa un infinito de un orden superior al de los números naturales y racionales. El “argumento de la diagonalización” de Cantor es la prueba formal de este hecho.

---

Consecuencias de la No Enumerabilidad

Definición Inicial

El descubrimiento de que existen diferentes tamaños de infinito (enumerable y no enumerable) tiene consecuencias profundas y extrañas. Revela que la gran mayoría de los números son, en cierto sentido, “incognoscibles”.

Explicación Didáctica

1. Números que no podemos “nombrar”: Piénsalo: ¿cuántas formas hay de “nombrar” o “describir” un número? Podemos usar strings finitos de texto, como “3.14159”, “pi”, “la raíz cuadrada de 2”, “la menor raíz del polinomio $3x^3 - 17x + 1$”. El conjunto de todos los posibles strings (usando un alfabeto finito como el ASCII) es enumerable. Tenemos un número innumerable de reales ($\mathbb{R}$) pero solo un número enumerable de nombres para ellos. Esto significa que la gran mayoría de los números reales no tienen descripción posible; son “in-nombrables”.

2. Números Trascendentes: Algunos números, como $\sqrt{2}$ o $5/3$, son “algebraicos” porque son la solución a un polinomio simple con coeficientes enteros ($x^2 - 2 = 0$ o $3x - 5 = 0$). Resulta que el conjunto de todos los números algebraicos es enumerable. Dado que $\mathbb{R}$ es no enumerable y los algebraicos son enumerables, el conjunto restante, los números trascendentes (como $\pi$ y $e$ ), debe ser no enumerable. Esto significa que “casi todos” los números reales son trascendentes, aunque sea muy difícil probarlo para un número específico.

3. Problemas no Decidibles: Una “propiedad” sobre los números naturales (como “es par” o “es primo”) es solo un subconjunto de $\mathbb{N}$. El conjunto de todas las propiedades es $\mathcal{P}(\mathbb{N})$, que es no enumerable. Un programa de computador (como en Python) es un string finito de texto. El conjunto de todos los programas de Python posibles es enumerable. Si tenemos un número no enumerable de problemas (propiedades) pero solo un número enumerable de programas (soluciones), debe haber problemas que ningún programa puede resolver. Estos se llaman problemas no decidibles.

Resumen Rápido

Existen más números reales que nombres para describirlos, y la mayoría son trascendentes. Esta brecha entre lo enumerable (programas, nombres) y lo no enumerable (reales, problemas) garantiza que existen problemas en matemáticas que las computadoras nunca podrán resolver.

---

El Teorema de Cantor y la Jerarquía de Infinitos

Definición Inicial

El argumento de la diagonalización no fue un truco de una sola vez. Cantor lo generalizó en un teorema que demuestra que no hay un infinito más grande, sino una jerarquía infinita de infinitos.

Explicación Didáctica

El Teorema de Cantor proporciona una “receta para crear un infinito más grande”. La receta es simple: dado cualquier conjunto $A$, el conjunto de todos sus subconjuntos (llamado su conjunto potencia, o $\mathcal{P}(A)$) es siempre estrictamente más grande que $A$ mismo.

Si $A = \{1, 2\}$, $\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$. El tamaño 2 es menor que el tamaño 4. Cantor demostró que esto siempre es cierto, incluso para $A = \mathbb{N}$. El conjunto $\mathcal{P}(\mathbb{N})$ (el conjunto de todos los subconjuntos de números naturales) es un infinito más grande que $\mathbb{N}$. De hecho, $\mathcal{P}(\mathbb{N})$ tiene la misma cardinalidad que los números reales $\mathbb{R}$.

Definición Formal

El Teorema de Cantor establece que para cualquier conjunto $A$, $A < \mathcal{P}(A)$.

La prueba es una generalización de la diagonalización:

1. $A \le \mathcal{P}(A)$: Es fácil mostrar una inyección. La función $f(a) = \{a\}$ (que toma un elemento y lo envuelve en un conjunto) es inyectiva.
2. $A \not\approx \mathcal{P}(A)$: Debemos probar que ninguna función $g: A \rightarrow \mathcal{P}(A)$ puede ser una biyección (específicamente, no puede ser suryectiva).
3. Asumimos por contradicción que $g$ es una biyección.
4. Construimos un conjunto “villano” $B$, que contiene a todos los elementos de $A$ que no están en el subconjunto al que $g$ los asigna: $B = \{a \in A \mid a \notin g(a)\}$
5. Como $B$ es un subconjunto de $A$ (es decir, $B \in \mathcal{P}(A)$) y $g$ es suryectiva, debe existir algún $b \in A$ tal que $g(b) = B$.
6. La contradicción: ¿Está $b$ en $B$?
   • Caso 1: Si $b \in B$, entonces por la definición de $B$, $b \notin g(b)$. Pero $g(b) = B$, así que esto significa $b \notin B$. Contradicción.
   • Caso 2: Si $b \notin B$, entonces por la definición de $B$, $b$ debe estar en $g(b)$. Pero $g(b) = B$, así que esto significa $b \in B$. Contradicción.

Ambos casos conducen a una contradicción, por lo que la suposición de que $g$ era una biyección es falsa.

Resumen Rápido

El Teorema de Cantor ($A < \mathcal{P}(A)$) es la máquina de generar infinitos. Demuestra que existe una jerarquía infinita de tamaños: $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < ...$ y así sucesivamente, para siempre.

---

La Hipótesis del Continuo

Definición Inicial

Sabemos que $|\mathbb{N}|$ (enumerable) es el primer infinito, y $|\mathbb{R}|$ (que es igual a $|\mathcal{P}(\mathbb{N})|$) es un infinito más grande. La pregunta más obvia es: ¿existe algún infinito de tamaño intermedio?

Explicación Didáctica

Sabemos que la “talla” de $\mathbb{Q}$ es la misma que la de $\mathbb{N}$. Sabemos que la “talla” de $\mathbb{R}$ es más grande. ¿Existe un conjunto A cuya “talla” esté entre $\mathbb{N}$ y $\mathbb{R}$? ¿Un infinito de tamaño “mediano”?

La Hipótesis del Continuo (HC) es la conjetura de que no, no existe tal conjunto intermedio.

Definición Formal

La Hipótesis del Continuo (HC) postula que no existe ningún conjunto $A$ tal que $|\mathbb{N}| < |A| < |\mathbb{R}|$.

Ejemplo Resuelto (El Estado de la Hipótesis)

Este es quizás el resultado más alucinante de la lógica moderna.

• En 1940, Kurt Gödel demostró que la HC es consistente con los axiomas estándar de la matemática (ZFC). Es decir, no puedes refutarla (no puedes probar que es falsa).
• En 1963, Paul Cohen demostró que la negación de la HC también es consistente con ZFC. Es decir, no puedes demostrarla (no puedes probar que es verdadera).

El resultado combinado es que la Hipótesis del Continuo es independiente de los axiomas ZFC. No se puede probar ni refutar dentro del sistema matemático estándar. Es, en esencia, una pregunta cuya respuesta es “indecidible”.

Resumen Rápido

La Hipótesis del Continuo pregunta si existe un infinito de tamaño entre el de los naturales y el de los reales. Sorprendentemente, Gödel y Cohen demostraron que esta pregunta no puede ser respondida (ni probada como verdadera ni como falsa) usando los fundamentos actuales de las matemáticas.