Functions and cardinality

A function \( f : A \to B \) assigns to each element of \( A \) exactly one element of \( B \). It is injective (one-to-one) if different inputs give different outputs, surjective (onto) if every element of \( B \) is an output, and bijective if both. A bijection has an inverse \( f^{-1} : B \to A \), and the composition of two injections (or two surjections, or two bijections) is again one.

Between finite sets these properties are counted exactly. If \( |A| = a \) and \( |B| = b \), each of the \( a \) inputs independently chooses one of \( b \) outputs, so there are \( b^{a} \) functions; the example counts \( 5^3 = 125 \) functions from a 3-element set to a 5-element set. Injections must choose distinct outputs, giving \( b(b-1)\cdots(b-a+1) \) of them (and none if \( a > b \)). Surjections are harder and need inclusion-exclusion or Stirling numbers. The pigeonhole principle is the statement that there is no injection from a larger finite set into a smaller one.

For infinite sets, bijections define what "the same size" means. Two sets have the same cardinality if there is a bijection between them. A set is countable if it is finite or in bijection with \( \mathbb N \): its elements can be listed as a sequence. The even numbers are countable (\( n \mapsto 2n \)), so are the integers (list \( 0, 1, -1, 2, -2, \dots \)), and so are the rationals: list the positive fractions in order of numerator plus denominator, skipping repeats, and interleave 0 and the negatives. A proper subset of an infinite set can have the same size as the whole, which is what separates infinite sets from finite ones.

Not every infinite set is countable. Cantor's diagonal argument shows the real numbers in \( [0, 1) \) cannot be listed: given any list, build a decimal whose \( n \)-th digit differs from the \( n \)-th digit of the \( n \)-th number on the list (avoiding digits 0 and 9, so no number has two expansions). It differs from every listed number, so the list was incomplete. The same idea shows that no set is in bijection with its power set: for \( f : A \to \mathcal P(A) \), the set \( \{a : a \notin f(a)\} \) is not an output of \( f \).

Picture it: draw \( A \) and \( B \) as two columns of dots with an arrow from each dot of \( A \). Injective means no two arrows land on the same dot, surjective means every dot of \( B \) is hit, and bijective means the arrows pair the columns off perfectly.

Think it: to count a finite set, find a bijection with a set you already know how to count. To show two infinite sets have the same size, construct a bijection, or an injection each way (the Schröder-Bernstein theorem then supplies a bijection). To show a set is uncountable, assume a list and diagonalise.