Finite set, cardinality কী?

Example 2.6 (Finiteness is essential)

On a finite set, Proposition 2.5 is a powerful shortcut: any injective map from $E$ to itself is automatically a permutation of $E$ — half of bijectivity comes for free. Both implications collapse on infinite sets: $n \mapsto n + 1$ is injective from $\N$ to $\N$ but misses $0$, and the map $\N \to \N$ sending $0 \mapsto 0$ and $n \mapsto n - 1$ for $n \geq 1$ is surjective but not injective. Whenever this proposition is invoked, the finiteness hypothesis is doing real work — a theme that the weekend problem of Chapter 1 explores from the other side, where infinite sets are precisely those admitting such self-maps.

Example 2.7 (Half the work, for free)

Consider the map $f$ on $\{0, 1, \dots, 6\}$ sending $k$ to the remainder of $3k$ upon division by $7$; its table of values is

Is $f$ a bijection? Injectivity alone suffices (Proposition 2.5): if $3k$ and $3k'$ have the same remainder, $7$ divides $3(k - k')$, and since $7$ is prime and does not divide $3$, it divides $k - k'$ (Euclid’s lemma, used at High School level here and proved in Chapter 6); with $\abs{k - k'} \leq 6$ this forces $k = k'$. Surjectivity comes free — no need to solve $3k \equiv c$ for each $c$, though the table confirms every value appears exactly once. The shortcut is a workhorse: it proves the invertibility of modular multiplication (Chapter 6), powers the pairing in Wilson’s theorem, and returns in linear algebra as “an endomorphism of a finite-dimensional space is injective iff surjective” (Chapter 19).

Example 2.17

Two classical specializations: $a = b = 1$ recovers $\sum_k \binom nk = 2^n$; $a = -1$, $b = 1$ gives $\sum_{k} (-1)^k \binom nk = 0$ for $n \geq 1$: among the subsets of a nonempty set, exactly half have even cardinality.