5.1. CONJUNTOS FINITOS Y MÉTODOS DE CONTEO
139
Observación 5.10. El principio de inclusión y exclusión se puede generalizar a un número
arbitrario de conjuntos. Por ejemplo, para cuatro conjuntos A, B, C y D se tiene que
|A ∪ B ∪ C ∪ D| = |A| + |B| + |C| + |D|
−|A ∩ B| − |A ∩ C| − |A ∩ D| − |B ∩ C| − |C ∩ D|
+|A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D|
−|A ∩ B ∩ C ∩ D|.
2
Si entre dos conjuntos A y B se puede definir una función biyectiva, entonces A y B tienen
el mismo número de elementos, como lo demostraremos a continuación. Este resultado es la
clave de muchos métodos de conteo.
Teorema 5.11. Sea A un conjunto finito y supongamos que existe un función biyectiva
f : A → B, entonces B es finito y además |A| = |B|.
Demostración: Sea n el número de elementos de A, es decir, |A| = n y sea g : {1, 2, · · · , n} →
A una biyección. Queremos encontrar una biyección h : {1, 2, · · · , n} → B. La función
compuesta f ◦ g : {1, 2, · · · , n} → B es la candidata natural para h. En efecto, ya hemos
visto en el teorema 4.37 que la composición de funciones biyectivas es biyectiva, así que f ◦ g
es la biyección buscada.
2
Ejemplo 5.12. Consideremos los conjuntos
A = {2, 5, 7, 8} , B = {a} × {2, 5, 7, 8}.
Es fácil ver que B tiene 4 elementos (¿cuáles son?). Podemos también definir una biyección
f : A → B entre A y B de la siguiente manera
f (x) = (a, x).
Es decir, a cada elemento x de A lo enviamos al par ordenado (a, x).
Para ilustrar lo que hicimos en la demostración del teorema 5.11 busquemos una biyección
g : {1, 2, 3, 4} → {2, 5, 7, 8}. Por ejemplo: g(1) = 2, g(2) = 5, g(3) = 7 y g(4) = 8. Ahora
podemos calcular la función compuesta f ◦ g : {1, 2, 3, 4} → {a} × {2, 5, 7, 8} y obtenemos
(f ◦ g)(1) = (a, 2), (f ◦ g)(2) = (a, 5), (f ◦ g)(3) = (a, 7) y (f ◦ g)(4) = (a, 8). La función
f ◦ g es biyectiva.
2
Observación 5.13. Si A y B tienen n elementos cada uno, ¿Cúantas biyecciones existen
entre A y B? La respuesta es que existen n! funciones biyectivas entre A y B 1 . El lector
interesado puede hacer la demostración de esta afirmación por inducción en n.
1
Recordemos que el factorial de un número natural se define por n! = n · (n − 1) · · · 2 · 1. Por ejemplo,
3! = 3 · 2 · 1 = 6