domingo, 25 de marzo de 2012

¿Qué es contar?

Hoy trataremos de dar respuesta a esta pregunta tan interesante: ¿qué es contar? Un matemático, que se pasa los días contando cosas, no tendrá problema en dar la siguiente respuesta: contar los elmentos de un conjunto es establecer una biyección entre este conjunto y un subconjunto de los números naturales. Para entender bien qué significa esta frase necesitamos algunos conceptos previos.



Si tenemos dos conjuntos $A$ y $B$, una aplicación $f$ entre $A$ y $B$, que denotamos como $f:A \rightarrow B$ es una relación que asigna a cada elemento $x$ de $A$ un único elemento $f(x)$ de $B$. Por ejemplo, si $A = \{1, 2, 3, 4, 5, 6\}$ y $B = \{a, b, c, d\}$, una aplicación $f$ tiene la siguiente pinta:
Simbólicamente, tenemos que $f(1) = b, f(2) = a, f(3) = f(4) = f(5) = f(6) = d$. Para que $f$ sea una aplicación, no podemos poner las flechas de cualquier manera: la regla es que de cada elemento de $A$ tiene que salir una flecha, y sólo una, que llegue a algún elemento de $B$. No tiene por qué llegar una flecha a todos los elementos de $B$. Por ejemplo, en la $f$ anterior no hay ninguna flecha que llegue al elemento $c$. Remarcamos este hecho con la siguiente definición:

Definición. Sean $A$ y $B$ dos conjuntos y $f: A \rightarrow B$ una aplicación entre ellos. Decimos que $f$ es suprayectiva si para todo elemento $y$ de $B$ existe un elemento $x$ de $A$ tal que $f(x) = y$.

Es decir, una aplicación suprayectiva es una aplicación en la que a todos los elementos del conjunto $B$ llega alguna flecha. No es necesario que esta flecha sea única. En nuestro ejemplo al elemento $d$ llegan cuatro flechas. Por ello damos la siguiente definición:

Definición. Sean $A$ y $B$ dos conjuntos y $f: A \rightarrow B$ una aplicación entre ellos. Decimos que $f$ es inyectiva si no existen dos elementos de $A$ distintos que tengan la misma imagen por $f$.

Esto es, que no haya dos flechas que vayan a parar al mismo elemento de $B$. Una aplicación puede ser inyectiva y no suprayectiva, suprayectiva y no inyectiva, inyectiva y suprayectiva o ni inyectiva ni suprayectiva. La aplicación $f$ del ejemplo no es inyectiva (hay varias flechas que van a parar a $d$) y tampoco es suprayectiva (ninguna flecha va a parar a $c$).

Definición. Una aplicación se dice biyectiva si es inyectiva y suprayectiva.

En el caso de conjuntos finitos, las aplicaciones biyectivas nos sirven para compararlos según su número de elementos. Por ejemplo, si un conjunto $A$ tiene $7$ elementos y un conjunto $B$ tiene $6$, no puede existir una aplicación inyectiva entre ellos, porque suponiendo que ya se han asignado flechas para los $6$ primeros elementos de $A$ de modo que cada elemento de $A$ quede emparejado con un elemento de $B$, al intentar asignar una flecha al séptimo elemento de $A$ nos encontraremos con que todos los elementos de $B$ están ya "ocupados" y no habrá más remedio que mandar la flecha a un elemento que ya tenga flecha. Del mismo modo, si el conjunto $B$ tiene más elementos que el conjunto $A$, una aplicación de $A$ en $B$ no puede ser suprayectiva, no hay suficientes flechas para llenar todos los elementos de $B$. Así,

Teorema. Sean $A$ y $B$ dos conjuntos con un número finito de elementos. Entonces $A$ y $B$ tienen el mismo número de elementos si, y sólo si, existe una aplicación $f: A \rightarrow B$ biyectiva entre ellos.

No quiere decir esto que todas las aplicaciones deban ser biyectivas, sólo hace falta encontrar una que lo sea. Por ejemplo, si $A = \{1, 2, 3, 4\}$ y $B = \{a, b, c, d\}$, una aplicación biyectiva entre ellos es
Al haber encontrado una aplicación biyectiva, podemos asegurar, por el teorema, que los conjuntos $A$ y $B$ tienen el mismo número de elementos.

Ahora ya podemos entender la definición de contar que dábamos al principio. Cuando tenemos un saco con $n$ canicas, por ejemplo, y queremos contarlas, lo que hacemos es ir sacándolas una a una mientras pensamos "una, dos, tres, cuatro, ...". Sin ser conscientes de ello, estamos construyendo una biyección entre el conjunto de canicas y el conjunto $\{1, 2, 3, ..., n\}$. A la primera canica que sacamos la aplicamos sobre $1$, a la segunda sobre $2$, a la tercera sobre $3$, ... y la última canica sobre $n$.

¿Qué hacemos ahora si el conjunto que queremos contar es infinito? Entonces debemos ampliar el concepto de "número de elementos", porque podríamos decir simplemente "el conjunto tiene infinitos elementos" y punto. Pero, como veremos, si hiciéramos esto nos perderíamos un concepto muy interesante como es el de cardinal de un conjunto.

Definición. Sean $A$ y $B$ dos conjuntos (finitos o infinitos). Decimos que $A$ y $B$ tienen el mismo cardinal si existe una aplicación biyectiva entre ellos, y lo denotamos como $card(A) = card(B)$. Decimos que el cardinal de $A$ es menor o igual que el cardinal de $B$ si existe una aplicación inyectiva de $A$ en $B$. Lo denotamos como $card(A) \leq card(B)$.

El concepto de cardinal coincide, en el caso de conjuntos finitos, con el concepto de número de elementos. Dos conjuntos finitos tienen el mismo cardinal si, y sólo si, tienen el mismo número de elementos. Además la relación "tener el mismo cardinal" es una relación de equivalencia:
  1. Reflexiva: todo conjunto tiene el mismo cardinal que él mismo: la aplicación identidad $f:A \rightarrow A$ dada por $f(x) = x$ es biyectiva. (Esto es una bobada)
  2. Simétrica: si $card(A) = card(B)$, entonces existe una aplicación $f$ biyectiva de $A$ en $B$. Como $f$ es biyectiva, existe la inversa $f^{-1}$ de $B$ en $A$, que también es biyectiva, luego $card(B) = card(A)$.
  3. Transitiva: si $card(A) = card(B)$ y $card(B) = card(C)$, entonces existen aplicaciones biyectivas $f:A \rightarrow B$ y $g:B \rightarrow C$, por lo que la composición $g \circ f:A \rightarrow C$ es biyectiva, de donde $card(A) = card(C)$.

De estas propiedades es interesante que nos quedemos con la última, que viene a decir que si sabemos que $card(A) = card(B)$ y $card(B) = card(C)$, no es necesario encontrar una biyección entre $A$ y $C$ para saber que su cardinal es el mismo.

Ejemplo. El conjunto de los números naturales $\mathbb{N}$ y el conjunto de los números pares $2\mathbb{N} = \{2k : k \in \mathbb{N}\} = \{2, 4, 6, 8, ...\}$ tienen el mismo cardinal. Para ver esto, observamos que la aplicación

$f: \mathbb{N} \rightarrow 2\mathbb{N}$

$n \longmapsto 2n$

es biyectiva: es inyectiva porque si $n, m$ son dos números naturales distintos, entonces $f(n) = 2n$ y $f(m) = 2m$ son dos pares distintos, y es suprayectiva porque dado un número par de la forma $2k$, consideramos el número natural $k$ y entonces $f(k) = 2k$.

Visto este ejemplo, no es difícil demostrar que $367\mathbb{N}$ (el conjunto de los múltiplos de $367$) y el conjunto de números naturales $\mathbb{N}$ tienen el mismo cardinal. De hecho, para cualquier número natural $a \in \mathbb{N}$, los conjuntos $\mathbb{N}$ y $a\mathbb{N}$ tienen el mismo cardinal, sin más que considerar la aplicación $f:\mathbb{N}\rightarrow a\mathbb{N}$ dada por $f(n) = a\cdot n$.

El concepto de cardinal para conjuntos infinitos nos da una idea de cómo de grande es el infinito del conjunto. En este sentido, el infinito de los números naturales y el infinito de los naturales pares es "del mismo tamaño".

Ejemplo. El conjunto de los números racionales $\mathbb{Q}$ y el conjunto de números naturales $\mathbb{N}$ tienen el mismo cardinal. La idea para construir la biyección podemos verla con el siguiente dibujo:

Intruitivamente vemos que esto es una manera de ir recorriendo todos los racionales (al menos los positivos, luego veríamos cómo extenderlo a los racionales negativos) de uno en uno. Empezando por $f(1) = 1/1$, $f(2) = 2/1$, $f(3) = 1/2$, etc. Habría que ver cómo escribir esto formalmente, pero no lo vamos a hacer aquí.

Esto es un poco contraintuitivo, porque un conjunto como el de los racionales parece bastante grande. De hecho los racionales es un conjunto denso en la recta real, siempre podemos partir un segmento de longitud racional en trocitos y seguir encontrando racionales y más racionales por todas partes, pero lo cierto es que hay tantos números racionales como naturales, ya que podemos emparejarlos.

Definición. Si un conjunto finito tiene $n$ elementos, diremos que su cardinal es $n$. Si es infinito y tiene el mismo cardinal que el conjunto de números naturales, diremos que su cardinal es $\aleph_0$ (se lee "aleph sub cero").

¿Será que todos los conjuntos infinitos tienen cardinal $\aleph_0$? Pues no.

Teorema. El conjunto de los números reales $\mathbb{R}$ tiene un cardinal estrictamente mayor que el de los números naturales. Es decir, no existe una aplicación biyectiva entre $\mathbb{N}$ y $\mathbb{R}$.

La demostración de este resultado se basa en el argumento diagonal de Cantor.

En particular, como $\mathbb{R}$ se puede separar en el conjunto de números racionales y el conjunto de irracionales, se sigue que hay muchos (muchísimos) más números irracionales que números racionales. Incluso se puede demostrar que el conjunto de números algebraicos (números que son raíz de algún polinomio con coeficientes en $\mathbb{Z}$, como $1, 67, 4/7, \sqrt{2}, \sqrt{3+\sqrt{17}}$ es numerable (tiene el cardinal de $\mathbb{N}$), por lo que el conjunto de números trascendentes (los que no son algebraicos) como $e$ o $\pi$, que son irracionales "raros" es mucho más grande, tiene el cardinal de $\mathbb{R}$, que denotamos por $\frak{c}$.

Relacionado con todo esto está la hipótesis del continuo, uno de los problemas que propuso Hilbert a principios del siglo XX:

Problema. ¿Existe un conjunto $A$ cuyo cardinal esté estrictamente entre el cardinal de $\mathbb{N}$ y el cardinal de $\mathbb{R}$? Es decir, $\aleph_0 < card(A) < \frak{c}$.

La respuesta es que esta afirmación es independiente de los axiomas $ZFC$. Es decir, las matemáticas funcionan bien tanto si suponemos que existe ese conjunto, como si suponemos que no existe. Sabiendo esto, podemos suponer que $\frak{c}$ el "el cardinal siguiente" a $\aleph_0$ y poner $\frak{c} = \aleph_1$. Así, tenemos una sucesión de cardinales de conjuntos, de tamaños de infinitos, cada vez más grandes: $\aleph_0 < \aleph_1 < \aleph_2 < ...$. Por ejemplo, el conjunto $\mathcal{F}(\mathbb{R},\mathbb{R}) = \{f:\mathbb{R} \rightarrow \mathbb{R} : f$ es aplicación$\}$ de todas las aplicaciones posibles de $\mathbb{R}$ en $\mathbb{R}$ tiene cardinal $\aleph_2$, que es estrictamente más grande que el cardinal de $\mathbb{R}$. Más en general: si $A$ es un conjunto no vacío cualquiera, $card(\mathcal{F}(A,A)) > card(A)$.



4 comentarios: