Si |A| = |B| y |B| = |C|, entonces |A| = |C|.
Demostración. Para probar (a), utilizamos la función identidad 1A. Si existe una función biyectiva f : A → B, entonces f−1 es biyectiva, y (b) queda probado. Para probar (c), usamos que la composición de funciones biyectivas es biyectiva por el lema 1.3.
El lector debe ser consciente de que en el teorema anterior, no hemos escrito que tener el mismo cardinal establece una relación de equivalencia pues a continuación estaríamos obligados a añadir “en el conjunto de todos los conjuntos”, y como ya hemos dicho antes, no debemos tratar con conjuntos demasiado grandes. Al principio de este capítulo, habíamos definido |A| para un conjunto finito A, como el número de elementos de A. Los ejercicios 1.2 y 1.3 nos aseguran que la notación |A| = |B| es consistente.
Asociado a un conjunto A hay otro conjunto especial que hemos utilizado en el ejemplo 1.2 (e):
P (A) = {B | B ⊆ A}
que se llama el conjunto potencia de A (o partes de A). Lo más importante de P (A) es que tiene más elementos que A.
Teorema 1.8 Sea A un conjunto.
(a) La aplicación f : A → P (A) dada por f(a) = {a} es inyectiva.
(b) No existe ninguna aplicación g : A → P (A) suprayectiva.
Demostración. La primera parte es trivial. Sea ahora g : A → P (A) suprayectiva. Sea B = {a ∈ A | a ∉ g(a)} ⊆ A. Como g es suprayectiva, entonces existe a ∈ A tal que g(a) = B. Si a ∈ B, entonces a ∉ g(a) = B, lo cual no es posible. Si a ∉ B, entonces a ∈ g(a), y por tanto a ∈ B, lo cual tampoco es posible.
Según el teorema 1.8, P (ℕ) tiene más elementos que ℕ, y de hecho se puede probar que |P (ℕ)| = |ℝ|. No nos podemos resistir a mencionar la llamada hipótesis del continuo, establecida por George Cantor en 1878. Si A y B son conjuntos, escribimos |A| ≤ |B| si existe f : A → B inyectiva, y |A| < |B| si |A| ≤ |B| y |A| ≠ |B|. Por ejemplo, acabamos de probar que |A| < |P (A)| para todo conjunto A. La hipótesis del continuo, que constituye el primer problema de la famosa lista de problemas propuestos por Hilbert, afirma que no existe ningún conjunto A tal que |ℕ| < |A| < |ℝ|. En 1963 Paul Cohen probó que este enunciado es indemostrable. Este es otro concepto que no cabe en el presente libro. El autor sinceramente espera no haber interesado demasiado al lector en lógica para que renuncie al álgebra.
La siguiente propiedad de ℕ es fundamental: nos dice que en ℕ existe un buen orden.
Teorema 1.9 (teorema del buen orden en ℕ) Si A es un subconjunto no vacío de ℕ entonces existe a ∈ A tal que a ≤ b para todo b ∈ A. Este elemento a es único.
Demostración. Primero probamos la existencia de a. Como A no es vacío, sea a1 ∈ A. Si a1 ≤ b para todo b ∈ A, ya tendríamos el elemento que buscamos. En caso contrario, existe a2 ∈ A tal que a2 < a1. Si a2 ≤ b para todo b ∈ A, de nuevo lo tendríamos. Como entre 0 y a1 hay solo un número finito de elementos, este proceso no se puede repetir un número infinito de veces. Así, podemos llegar a encontrar a ∈ A tal que a ≤ b para todo b ∈ A.
A continuación probamos la unicidad de a. En efecto, si existiera otro elemento c ∈ A con la misma propiedad, tendríamos que a ≤ c y c ≤ a, con lo que a = c.
Al elemento a en el teorema 1.9 se le llama el menor elemento de A, y lo denotamos por min(A).
Decimos que un conjunto A es numerable si |ℕ×| = |A|, donde ℕ× = {1, 2, 3, …}. Algunos autores incluyen los conjuntos finitos entre los conjuntos numerables. Vemos que si A es numerable, entonces existe una aplicación biyectiva f : ℕ× → A, y así podemos escribir
A = {f(1), f(2), f(3), …}.
En definitiva, si A es numerable, entonces los elementos de A se pueden enumerar.
Teorema 1.10 Supongamos que A es un subconjunto infinito de ℕ. Entonces A es numerable.
Demostración. Como A no es vacío, sea a1 = min(A). Como A − {a1} no es vacío, sea a2 = min(A − {a1}). En general, si tenemos definidos a1, …, ak, como A − {a1, …, ak} no es un conjunto vacío (pues A es infinito), podemos definir
ak+1 = min(A − {a1, …, ak})
para k ≥ 0. Observamos pues que tenemos definidos
a1 < a2 < … < ak < ak+1 < …
una cadena de elementos de A. Definimos f : ℕ× → A con f(k) = ak. Como an < am si n < m, observamos que f es inyectiva.
Probamos finalmente que f es suprayectiva. Sea a ∈ A. Sea B = {n ∈ A | n < a}. Si B = ∅, entonces a = a1 = f(1). En otro caso, B es un conjunto finito no vacío, que por tanto se puede escribir B = {a1, …, at} para algún t. Entonces a = at+1 = f(t + 1), y el teorema queda probado.
Corolario 1.11 Si A es numerable y B ⊆ A, entonces B es finito o numerable.
Demostración. Supongamos que B es infinito. Sea f : A → ℕ× una aplicación biyectiva. Aplicamos el teorema 1.10 al conjunto infinito f(B).
En los problemas guiaremos al lector sobre cómo probar que el conjunto de los números racionales es numerable,
