Teorema. (Principio General de la Suma)
Sea
y , Supongamos que son conjuntos finitos ajenos por pares, es decir, tales que si . Entonces
Proof.
Por inducción sobre
.
Paso base: Si, tenemos dos conjuntos ajenos y . Entonces existen números naturales y y funciones biyectivas y tales que y . Así, y . Dado el lema, e . Definimos como: La función
está bien definida, pues , tenemos que o y se da sólo uno de estos casos, es decir, o o ; además, si , entonces , por lo que en este caso y está bien definido. Y si tambien se demuestra que es biyectiva. Paso Inductivo…
Corolario.
- Si
es inyectiva, entonces . - Si
es sobre, entonces
Proof.
…
Corolario. (Principio del Palomar)
Sea
un conjunto finito tal que y sea una partición de forma que si y son ajenos.