A es un conjunto, una relación en A es un subconjunto
R ⊆ A × A.
Decimos que a está relacionado con b si (a, b) ∈ R. Podemos pensar que una relación es sencillamente una función f : A × A → {sí, no}, donde R = {(a, b) ∈ A × A | f(a, b) = sí}.
Por ejemplo, en el conjunto A = {1, 2, 3}, definimos la relación
R = {(1, 1), (1, 2), (3, 2)}.
En este caso, 1 está relacionado con 1 y con 2, 2 no está relacionado con ningún elemento, y 3 está relacionado con 2. Muchas veces, en lugar de especificar R, es más sencillo describir cuándo dos elementos están relacionados. Por ejemplo, en el conjunto A de los habitantes de una ciudad, podemos decir que dos elementos de A están relacionados si viven en el mismo edificio. En este caso, observamos que cualquier a ∈ A está relacionado consigo mismo, entre otras propiedades que analizamos a continuación. Necesitamos cierto lenguaje para hablar de relaciones.
Definición 1.5 Sea A un conjunto y R ⊆ A × A una relación en A.
(a) Decimos que R es reflexiva si (a, a) ∈ R para todo a ∈ A.
(b) Decimos que R es simétrica si siempre que (a, b) ∈ R, entonces (b, a) ∈ R.
(c) Decimos que R es antisimétrica si siempre que (a, b) ∈ R y (b, a) ∈ R, entonces a = b.
(d) Decimos que R es transitiva si siempre que (a, b), (b, c) ∈ R, entonces (a, c) ∈ R.
Muy pocas relaciones en un conjunto A son interesantes. De hecho, las relaciones interesantes son esencialmente de dos tipos. Una relación R es de equivalencia si R es reflexiva, simétrica y transitiva. Una relación R es una relación de orden si R es reflexiva, antisimétrica y transitiva.
Ejemplo 1.2
(a) En el conjunto ℝ de los números reales, definimos la relación (a, b) ∈ R si y solo si a ≤ b. Esta es una relación de orden.
(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)
