Conjunto finito, cardinal কী?

Ejemplo 2.6 (La finitud es esencial)

Sobre un conjunto finito, la Proposición 2.5 es un atajo poderoso: toda aplicación inyectiva de $E$ en sí mismo es automáticamente una permutación de $E$ — la mitad de la biyectividad sale gratis. Las dos implicaciones se derrumban en los conjuntos infinitos: $n \mapsto n + 1$ es inyectiva de $\N$ en $\N$ pero no alcanza $0$, y la aplicación $\N \to \N$ que envía $0 \mapsto 0$ y $n \mapsto n - 1$ para $n \geq 1$ es sobreyectiva pero no inyectiva. Siempre que se invoca esta proposición, la hipótesis de finitud está haciendo un trabajo real — un tema que el problema del fin de semana del Capítulo 1 explora desde el otro lado, donde los conjuntos infinitos son precisamente los que admiten tales aplicaciones de un conjunto en sí mismo.

Ejemplo 2.7 (La mitad del trabajo, gratis)

Considérese la aplicación $f$ en $\{0, 1, \dots, 6\}$ que envía $k$ al resto de la división de $3k$ por $7$; su tabla de valores es

¿Es $f$ una biyección? Basta con la inyectividad (Proposición 2.5): si $3k$ y $3k'$ dejan el mismo resto, $7$ divide a $3(k - k')$ y, como $7$ es primo y no divide a $3$, divide a $k - k'$ (lema de Euclides, usado aquí al nivel del volumen anterior y demostrado en el Capítulo 6); con $\abs{k - k'} \leq 6$ esto obliga a $k = k'$. La sobreyectividad sale gratis — no hace falta resolver $3k \equiv c$ para cada $c$, aunque la tabla confirme que cada valor aparece exactamente una vez. El atajo es un caballo de batalla: demuestra la invertibilidad de la multiplicación modular (Capítulo 6), sostiene el emparejamiento del teorema de Wilson y vuelve en álgebra lineal como «un endomorfismo de un espacio de dimensión finita es inyectivo si y solo si es sobreyectivo» (Capítulo 19).

Ejemplo 2.17

Dos especializaciones clásicas: $a = b = 1$ recupera $\sum_k \binom nk = 2^n$; $a = -1$, $b = 1$ da $\sum_{k} (-1)^k \binom nk = 0$ para $n \geq 1$: entre los subconjuntos de un conjunto no vacío, exactamente la mitad tienen cardinal par.