(b) En el conjunto de habitantes de una ciudad, vivir en el mismo edificio establece una relación de equivalencia.
(c) En el plano ℝ2, decimos que (x1, y1) está relacionado con (x2, y2) si se tiene que
(d) Si f : A → B es una aplicación, definimos R = {(a1, a2) | f(a1) = f(a2)}. Entonces R es una relación de equivalencia.
(e) Si A es un conjunto, definimos una relación en el conjunto P (A) de todos los subconjuntos de A. Decimos que X e Y están relacionados si X ⊆ Y. Esto define una relación de orden en P (A).
Siempre que tengamos una relación de equivalencia R sobre un conjunto A, dicho conjunto queda partido en trozos disjuntos. (Dos conjuntos A y B son disjuntos si A ∩ B = ∅). Este es un hecho relevante. En el ejemplo 1.2 (b), los habitantes quedan distribuidos en edificios; en el ejemplo 1.2 (c), los elementos del plano quedan distribuidos en círculos de radio r para r ≥ 0. En general, cada elemento a ∈ A vive en su clase de equivalencia.
Una partición de un conjunto A es un conjunto P de subconjuntos no vacíos de A tales que
y B ∩ C = ∅ para todos B, C ∈ P distintos.
Si A es un conjunto con una relación de equivalencia R, para cada a ∈ A se define [a] = {b ∈ A | (a, b) ∈ R}, que se llama la clase de equivalencia de a. Observamos que a ∈ [a] ⊆ A.
Teorema 1.6 Sea A un conjunto con R una relación de equivalencia, y sea P = {[a] | a ∈ A} el conjunto de clases de equivalencia de A. Entonces P es una partición de A.
Demostración. Como a ∈ [a], está claro que [a] ≠ ∅ y que
Si c ∈ [a], probamos a continuación que [c] = [a]. Sea x ∈ [c]. Entonces (x, c) ∈ R. Como (c, a) ∈ R, tenemos que (x, a) ∈ R y x ∈ [a]. Recíprocamente, si x ∈ [a], entonces (x, a) ∈ R. Como (a, c) ∈ R, tenemos que (x, c) ∈ R y x ∈ [c], como queríamos. Finalmente, supongamos que [a] ∩ [b] ≠ ∅, y sea c ∈ [a] ∩ [b]. Por lo anterior, tenemos que [a] = [c] = [b].
4
¿Todos los conjuntos infinitos tienen el mismo número de elementos? ¿Hay algún conjunto infinito con menos elementos que ℕ? ¿Cómo comparamos infinitos?
Al principio, puede que la intuición no nos sea del todo útil. Es famoso el Hotel de Hilbert que tiene un número infinito de habitaciones numeradas {1, 2, 3, …}, todas ellas ocupadas.
Al llegar un huésped nuevo, el conserje del hotel, lejos de rechazarlo, traslada al ocupante de la habitación n a la n+1, y deja así la primera habitación libre para el huésped nuevo. Este conserje ni se inmuta cuando momentos después ve aparecer llegando a su hotel un autobús con infinitos turistas {1, 2, 3, …}: traslada al ocupante de la habitación n a la habitación 2n y al turista m a la habitación 2m − 1. Tampoco se preocupa el conserje cuando esta vez aparece un número infinito de autobuses {a1, a2, …, ak, …} cada uno de ellos cargado de infinitos turistas {ak1, ak2, …}… pero vamos a dejarlo aquí.
Para comparar infinitos, las funciones biyectivas son fundamentales. Si existe f : A → B biyectiva, decimos que A y B tienen el mismo cardinal (o son equipotentes), y lo escribimos |A| = |B|. En caso contrario, escribimos |A| ≠ |B|.
Teorema 1.7 Sean A, B y C conjuntos.
(a) |A| = |A|.
(b) Si |A| = |B|, entonces |B| = |A|.
(c) 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