4.5: Finite Cardinality

A finite set is one that has only a finite number of elements. This number of elements is the “size” or cardinality of the set:

Definition \(\PageIndex{1}\)

If A is a finite set, the cardinality of \(A\), written \(|A|\), is the number of elements in \(A\).

A finite set may have no elements (the empty set), or one element, or two elements, ... , so the cardinality of finite sets is always a nonnegative integer.

Now suppose \(R : A \rightarrow B\) is a function. This means that every element of \(A\) contributes at most one arrow to the diagram for \(R\), so the number of arrows is at most the number of elements in \(A\). That is, if \(R\) is a function, then

\[\nonumber |A| \geq \text{#arrows.}\]

If \(R\) is also surjective, then every element of \(B\) has an arrow into it, so there must be at least as many arrows in the diagram as the size of \(B\). That is,

\[\nonumber \text{#arrows} \geq |B|.\]

Combining these inequalities implies that if \(R\) is a surjective function, then \(|A| \geq |B|\).

In short, if we write \(A\) surj \(B\) to mean that there is a surjective function from \(A\) to \(B\), then we’ve just proved a lemma: if \(A\) surj \(B\) for finite sets \(A\), \(B\), then \(|A| \geq |B|\). The following definition and lemma lists this statement and three similar rules relating domain and codomain size to relational properties.

Definition \(\PageIndex{2}\)

Let \(A\), \(B\) be (not necessarily finite) sets. Then

1. \(A\) surj \(B\) iff there is a surjective function from \(A\) to \(B\).
2. \(A\) inj \(B\) iff there is a injective total from \(A\) to \(B\).
3. \(A\) bij \(B\) iff there is a bijective from \(A\) to \(B\).

Lemma 4.5.3. For finite sets \(A\), \(B\):

1. If \(A\) surj \(B\), then \(|A| \geq |B|\).
2. If \(A\) inj \(B\), then \(|A| \leq |B|\).
3. If \(A\) bij \(B\), then \(|A| =|B|\).

Proof. We’ve already given an “arrow” proof of implication 1. Implication 2. follows immediately from the fact that if \(R\) has the [\(\leq 1\) out], function property, and the [\(\geq 1\) in], surjective property, then \(R^{-1}\) is total and injective, so \(A\) surj \(B\) iff \(B\) inj \(A\). Finally, since a bijection is both a surjective function and a total injective relation, implication 3. is an immediate consequence of the first two. \(\quad \blacksquare\)

Lemma 4.5.3.1. has a converse: if the size of a finite set, \(A\), is greater than or equal to the size of another finite set, \(B\), then it’s always possible to define a surjective function from \(A\) to \(B\). In fact, the surjection can be a total function. To see how this works, suppose for example that

\[\begin{aligned} A &= \{a_0, a_1, a_2, a_3, a_4, a_5\} \\ B &= \{b_0, b_1, b_2, b_3.\} \end{aligned}\]

Then define a total function f W A ! B by the rules \(f : A \rightarrow B\) by the rules

\[\nonumber f(a_0) ::= b_0, f(a_1) ::= b_1, f(a_2) ::= b_2, f(a_3) = f(a_4) = f(a_5) ::= b_3\]

More concisely,

\[\nonumber f(a_i) ::= b_{min(i, 3)},\]

for \(0 \leq i \leq 5\). Since 5 \(\geq\) 3, this \(f\) is a surjection.

So we have figured out that if \(A\) and \(B\) are finite sets, then \(|A| \geq |B|\) if and only if \(A\) surj \(B\). All told, this argument wraps up the proof of a theorem that summarizes the whole finite cardinality story:

Theorem \(\PageIndex{4}\)

[Mapping Rules] For finite sets, \(A\), \(B\),

\[\label{4.5.1}|A| \geq |B| \textit{ iff } A \text{ surj } B,\]

\[\label{4.5.2} |A| \leq |B| \textit{ iff } A \text{ inj } B,\]

\[\label{4.5.3} |A| = |B| \textit{ iff } A \text{ bij } B.\]

How Many Subsets of a Finite Set?

As an application of the bijection mapping rule (\ref{4.5.3}), we can give an easy proof of:

Theorem 4.5.5. There are 2n subsets of an n-element set. That is,

Theorem \(\PageIndex{5}\)

There are \(2^n\) subsets of an n-element set. That is,

\[\nonumber |A| = n \textit{ implies } |\text{pow}(A)| = 2^n.\]

For example, the three-element set \(\{a_1, a_2, a_3\}\) has eight different subsets:

\[\nonumber \begin{array}{cccc} & \emptyset & \{a_1\} & \{a_2\} & \{a_1, a_2\} \\ & \{a_3\} & \{a_1, a_3\} & \{a_2, a_3\} & \{a_1, a_2, a_3\} \end{array}\]

Theorem 4.5.5 follows from the fact that there is a simple bijection from subsets of \(A\) to \(\{0 1\}^n\), the n-bit sequences. Namely, let \(a_1, a_2, \ldots, a_n\) be the elements of \(A\). The bijection maps each subset of \(S \subseteq A\) to the bit sequence \((b_1, b_2, \ldots, b_n)\) defined by the rule that

\[\nonumber b_i = 1 \textit{ iff } a_i \in S.\]

For example, if \(n = 10\), then the subset \(\{a_2, a_3, a_5, a_7, a_{10}\}\) maps to a 10-bit sequence as follows:

subset: { \(a_2\), \(a_3\), \(a_5\), \(a_7\), \(a_{10}\)}

sequence: (0, 1, 1, 0, 1, 0, 1, 0, 0, 1)

Now by bijection case of the Mapping Rules 4.5.4.(\ref{4.5.3}),

\[\nonumber |\text{pow}(A)| = |\{0, 1\}^n |.\]

But every computer scientist knows6 that there are \(2^n\) n-bit sequences! So we’ve proved Theorem 4.5.5!

 

⁶In case you’re someone who doesn’t know how many n-bit sequences there are, you’ll find the \(2^n\) explained in Section 14.2.2.