O que é Conjunto finito, cardinalidade?

Exemplo 2.6 (A finitude é essencial)

Num conjunto finito, a Proposição 2.5 é um atalho poderoso: toda aplicação injetiva de $E$ em si mesmo é automaticamente uma permutação de $E$ — metade da bijetividade vem de graça. As duas implicações desmoronam em conjuntos infinitos: $n \mapsto n + 1$ é injetiva de $\N$ em $\N$, mas não atinge $0$, e a aplicação $\N \to \N$ que envia $0 \mapsto 0$ e $n \mapsto n - 1$ para $n \geq 1$ é sobrejetiva, mas não injetiva. Sempre que esta proposição é invocada, a hipótese de finitude está fazendo trabalho de verdade — tema que o problema de fim de semana do Capítulo 1 explora pelo outro lado, em que os conjuntos infinitos são precisamente os que admitem tais aplicações de si em si.

Exemplo 2.7 (Metade do trabalho, de graça)

Considere a aplicação $f$ em $\{0, 1, \dots, 6\}$ que envia $k$ ao resto da divisão de $3k$ por $7$; sua tabela de valores é

$f$ é uma bijeção? A injetividade sozinha basta (Proposição 2.5): se $3k$ e $3k'$ têm o mesmo resto, $7$ divide $3(k - k')$ e, como $7$ é primo e não divide $3$, ele divide $k - k'$ (lema de Euclides, usado aqui no nível do ensino médio e demonstrado no Capítulo 6); com $\abs{k - k'} \leq 6$ isso força $k = k'$. A sobrejetividade vem de graça — não é preciso resolver $3k \equiv c$ para cada $c$, embora a tabela confirme que todo valor aparece exatamente uma vez. O atalho é um cavalo de batalha: demonstra a invertibilidade da multiplicação modular (Capítulo 6), alimenta o emparelhamento do teorema de Wilson e reaparece em álgebra linear como “um endomorfismo de um espaço de dimensão finita é injetivo se, e somente se, é sobrejetivo” (Capítulo 19).

Exemplo 2.17

Duas especializações clássicas: $a = b = 1$ recupera $\sum_k \binom nk = 2^n$; $a = -1$, $b = 1$ dá $\sum_{k} (-1)^k \binom nk = 0$ para $n \geq 1$: entre os subconjuntos de um conjunto não vazio, exatamente metade tem cardinalidade par.