Cardinality

From Finite Listings to Cardinality

The previous tutorial defined a finite set as a set that has a distinct finite listing. A listing gives us a way to exhibit finiteness, but there is a further question: could the same set have distinct listings of different lengths? To speak consistently about the number of elements in a finite set, we first need to show that its listing length is uniquely determined.

A useful way to make “same number of elements” precise is to compare sets by a bijection. A bijection pairs every element of one set with exactly one element of the other, using every element on both sides. We will use bijections with a standard finite set of integers as a measuring tool.

The set \([n]\) serves as a standard set containing \(n\) integers. In particular, \([0]\) has no elements, \([1]=\{1\}\), and \([3]=\{1,2,3\}\). A distinct listing \(a_1,\ldots,a_n\) of \(A\) gives a bijection from \([n]\) to \(A\) by sending \(i\) to \(a_i\). Conversely, a bijection from \([n]\) to \(A\) lists the elements of \(A\) as the distinct values of that function. So the definition connects cardinality to the distinct listings used to define finite sets.

Why the Number of Entries Is Unique

To justify the notation \(|A|=n\), we must rule out a bijection between two standard finite sets of different sizes. We first prove that an injection from \([m]\) into \([n]\) is possible only when \(m\leq n\). The argument accounts for the empty set as well as nonempty finite sets.

Proof. We use induction on \(n\), proving the claim for every integer \(m\geq 0\) at each stage. If \(n=0\), then \([n]=\varnothing\). There is no function from a nonempty set \([m]\) into \(\varnothing\), since an element of the domain would need an image. Thus an injection \([m]\to[0]\) requires \(m=0\), and the conclusion holds.

Now suppose the claim holds for \(n\), and consider an injection \(f:[m]\to[n+1]\). If \(m=0\), then \(m\leq n+1\) immediately. Suppose, therefore, that \(m\geq 1\). If \(n+1\) is not an output of \(f\), then every value of \(f\) belongs to \([n]\). We can regard \(f\) as an injection into \([n]\), so the induction hypothesis gives \(m\leq n\), and hence \(m\leq n+1\).

It remains to consider the case in which \(f(i)=n+1\) for some \(i\in[m]\). Since \(f\) is injective, no other input maps to \(n+1\). The remaining \(m-1\) inputs can be reindexed by \([m-1]\): define \(h:[m-1]\to[m]\setminus\{i\}\) by \(h(k)=k\) when \(k<i\), and \(h(k)=k+1\) when \(k\geq i\). This map lists every member of \([m]\setminus\{i\}\) exactly once. Consequently, \(f\circ h\) is an injection from \([m-1]\) into \([n]\). The induction hypothesis gives \(m-1\leq n\), so \(m\leq n+1\). This completes the induction. \(\square\)

Proof. Since \(A\) is finite, it has a distinct listing \(a_1,\ldots,a_m\) for some \(m\geq 0\). Sending \(i\in[m]\) to \(a_i\) gives a bijection from \([m]\) to \(A\). This also holds when \(m=0\): the empty function is a bijection from \([0]=\varnothing\) to \(A=\varnothing\).

For uniqueness, suppose there are bijections \(f:[m]\to A\) and \(g:[n]\to A\). Since a bijection has an inverse, \(g^{-1}\circ f\) is a bijection from \([m]\) to \([n]\), and in particular is an injection. The lemma gives \(m\leq n\). The inverse of this bijection is an injection from \([n]\) to \([m]\), so the lemma also gives \(n\leq m\). Therefore \(m=n\). \(\square\)

The theorem means that the length of a distinct listing is not an accidental feature of how the set was written. Every distinct listing of a given finite set has the same length, and that length is its cardinality.

Bijections and Injections Compare Sizes

A bijection between two finite sets shows that they have the same cardinality, even if their elements are entirely different. An injection gives a one-sided comparison: every element of its domain can be matched to a different element of its codomain, so the domain cannot be larger.

Proof. Write \(|A|=m\) and \(|B|=n\). By the definition of cardinality, there are bijections \(u:[m]\to A\) and \(v:[n]\to B\). The composition \(v^{-1}\circ f\circ u\) is an injection from \([m]\) to \([n]\): \(u\) and \(v^{-1}\) are bijections, and composing an injection with bijections preserves injectivity. The Injection Between Standard Finite Sets lemma gives \(m\leq n\). Hence \(|A|\leq |B|\). If \(f\) is a bijection, its inverse also gives an injection from \(B\) to \(A\), so the same result gives \(|B|\leq |A|\). Thus \(|A|=|B|\). \(\square\)

The Finite Pigeonhole Principle

The injection theorem has a useful contrapositive. If the domain of a function has greater cardinality than its codomain, the function cannot be injective. Therefore, at least two different inputs must have the same output. This is the finite pigeonhole principle: if more objects are assigned to fewer available positions, some position receives at least two objects.

Proof. Suppose instead that \(f(a_1)\ne f(a_2)\) whenever \(a_1\ne a_2\). Then \(f\) is injective. The Injections Compare Finite Cardinalities theorem would give \(|A|\leq |B|\), contradicting \(|A|>|B|\). Hence \(f\) is not injective, which means there are distinct \(a_1,a_2\in A\) such that \(f(a_1)=f(a_2)\). \(\square\)

What Cardinality Does—and Does Not—Say

For finite sets, cardinality turns the informal idea of “number of elements” into a precise integer. The central step is the well-definedness theorem: once a finite set has one distinct listing, every distinct listing has the same length. A bijection is the appropriate comparison because it matches the elements one-to-one, while an injection only guarantees that the first set can be matched into the second.

Be careful not to confuse equal cardinality with set equality. Sets with different elements can have the same cardinality, as the worked example with \(A\) and \(B\) demonstrates. Conversely, if two finite sets are equal, then they have the same elements and therefore the same cardinality. The cardinality comparison developed here applies to finite sets; later, countable sets will extend the study of how sets can be matched with standard sets.