Finite Mathematical Structures

Finite Sets and Counting

A recursive rule describes how to produce later terms from earlier ones. In many elementary arguments, we instead need to describe a collection of objects that can be listed and counted: for example, the possible outcomes of a finite procedure, or the elements assigned to a small number of categories. The basic language for this is the language of finite sets. Induction is useful here not only for proving formulas, but also for establishing general facts about how many objects can fit into a finite collection of categories.

A list can contain the same item more than once, but a set records only whether an element is present. Thus $\{a,a,b\}=\{a,b\}$, while the list $a,a,b$ has three entries. Keeping this distinction clear is essential when counting.

Definition (Finite set and cardinality). For $n\in\mathbb{N}_0$, define $[n]=\{1,2,\ldots,n\}$, with $[0]=\varnothing$. A set $A$ is finite if there is a bijection from $[n]$ to $A$ for some $n\in\mathbb{N}_0$. The number $n$ is called the cardinality, or size, of $A$, and is written $|A|=n$. A bijection pairs each element of one set with exactly one element of the other, with no elements left out.

This definition says that a finite set can be listed without repetition: the bijection assigns its first element to $1$, its second to $2$, and so on. We must also know that the number of entries does not depend on which listing we choose. We will establish that after proving a basic counting result.

The Pigeonhole Principle

Imagine assigning objects to boxes, with each object placed in exactly one box. If there are more objects than boxes, at least one box must receive more than one object. The point is not how the assignment is made; the conclusion follows just from the numbers of objects and boxes.

Theorem (Pigeonhole Principle). For every positive integer $n$, any function from $[n+1]$ to $[n]$ takes the same value at two distinct inputs. Equivalently, if $n+1$ distinct objects are assigned to $n$ categories, then some category contains at least two of the objects.

Proof. We use induction on $n$. When $n=1$, a function from $[2]$ to $[1]$ must send both $1$ and $2$ to $1$, so the result holds.

Suppose the result holds for some $n\geq1$, and let $f:[n+2]\to[n+1]$. We consider whether $n+1$ occurs as a value of $f$. If it does, choose an input $r$ such that $f(r)=n+1$. If some other input $r'\neq r$ also satisfies $f(r')=n+1$, then $r$ and $r'$ have the same image, so the desired conclusion holds. Otherwise, remove $r$ from the domain. There remain $n+1$ inputs, and none of their images is $n+1$. They therefore map into $[n]$. Relabeling these $n+1$ inputs as $[n+1]$, the induction hypothesis shows that two of them have the same image. They are distinct inputs of the original function as well.

If $n+1$ does not occur as a value, all inputs map into $[n]$. In particular, the first $n+1$ inputs map into $[n]$. The induction hypothesis again gives two distinct inputs with the same image. Both cases prove the assertion for $n+1$. By induction, the Pigeonhole Principle holds for every positive integer $n$. $\square$

The phrase “distinct objects” matters: the inputs being assigned are separate objects, even if they share other characteristics. Likewise, the result does not say that every category receives an object. It guarantees only that some category receives at least two.

Worked Example: Remainders of Seven Distinct Integers

Choose any seven distinct integers. Divide each by $6$ and assign it to the category corresponding to its remainder. The possible remainders are $0,1,2,3,4,5$, so there are six categories. By the Pigeonhole Principle, two of the seven distinct integers have the same remainder when divided by $6$.

For instance, the seven distinct integers $4,9,15,22,28,33,41$ have remainders $4,3,3,4,4,3,5$, respectively. The integers $9$ and $15$, for example, both have remainder $3$. The theorem guarantees a matching pair even when the particular integers are not known in advance.

The assumption that the integers are distinct cannot be dropped. Choosing the integer $0$ seven times gives only one distinct integer, not seven distinct objects; it does not provide the stated conclusion about a pair of distinct integers.

Why the Size of a Finite Set Is Well Defined

A set may have many different listings, but all listings must have the same number of entries. To see why, suppose a set $A$ is in bijection with both $[m]$ and $[n]$. If $m<n$, composing one bijection with the inverse of the other would give a bijection from $[n]$ to $[m]$. When $m\geq1$, restricting that bijection to the first $m+1$ elements of $[n]$ would give an injective function from $[m+1]$ to $[m]$. This contradicts the Pigeonhole Principle. When $m=0<n$, a nonempty set $[n]$ cannot be in bijection with the empty set $[0]$. Thus $m<n$ is impossible. The same reasoning rules out $n<m$, so $m=n$. This verifies that $|A|$ is unambiguous.

The same principle compares the sizes of different finite sets. An injection sends distinct inputs to distinct outputs, so it cannot fit a larger finite set into a smaller one.

Theorem (An injection bounds finite-set sizes). Let $A$ and $B$ be finite sets. If there is an injective function from $A$ to $B$, then $|A|\leq|B|$.

Proof. Write $|A|=m$ and $|B|=n$, and choose bijections from $[m]$ to $A$ and from $[n]$ to $B$. Composing these bijections with the given injection gives an injection from $[m]$ to $[n]$. Suppose, for a contradiction, that $m>n$. If $n=0$, then $m>0$, and there is no function from the nonempty set $[m]$ to the empty set $[0]$. If $n\geq1$, then $m\geq n+1$, so restricting the injection to the first $n+1$ inputs would give an injection from $[n+1]$ to $[n]$. The Pigeonhole Principle rules this out. Therefore $m\leq n$, as claimed. $\square$

Worked Example: Comparing a Set with One of Its Subsets

Let $A=\{2,5,8,11\}$ and $B=\{2,8\}$. The inclusion map from $B$ to $A$, which sends each element to itself, is injective. The theorem therefore gives $|B|\leq|A|$. Indeed, listing the elements gives $|B|=2$ and $|A|=4$.

More generally, if $B\subseteq A$, the inclusion map $b\mapsto b$ is injective, so $|B|\leq|A|$. This argument also applies when $B$ is empty. It does not require the subset to be a proper subset; if $B=A$, the two sizes are equal.

Counting Unions and Pairs

Two useful constructions combine finite sets. A disjoint union joins sets that have no elements in common; a Cartesian product forms ordered pairs, taking one entry from each set. Their sizes are governed by addition and multiplication.

Theorem (Sizes of disjoint unions and Cartesian products). Let $A$ and $B$ be finite sets. If $A\cap B=\varnothing$, then $$ |A\cup B|=|A|+|B|. $$ For the Cartesian product $A\times B=\{(a,b):a\in A,\ b\in B\}$, the size is $$ |A\times B|=|A|\,|B|. $$

Proof. Write $|A|=m$ and $|B|=n$, and list the elements of each set without repetition as $a_1,\ldots,a_m$ and $b_1,\ldots,b_n$. If $A\cap B=\varnothing$, listing the $a_i$ first and then the $b_j$ lists every element of $A\cup B$ exactly once. The resulting list has $m+n$ entries, so $|A\cup B|=m+n$. This also works if either set is empty.

For the product, if $m=0$ or $n=0$, there are no ordered pairs, so $A\times B=\varnothing$ and $|A\times B|=0=mn$. Now suppose $m,n\geq1$. For each $i\in[m]$, the pairs with first coordinate $a_i$ are $(a_i,b_1),\ldots,(a_i,b_n)$. These are $n$ distinct pairs. The groups for different $i$ have no pairs in common, and every pair in $A\times B$ belongs to one of the groups. Thus the product is partitioned into $m$ groups of $n$ pairs each and has $mn$ elements. $\square$

Worked Example: Counting a Disjoint Union

Let $A=\{p,q,r\}$ and $B=\{u,v\}$, with no element in common. Then listing the union as $p,q,r,u,v$ shows that it has five elements. The disjoint-union formula gives the same result:

|A\cup B|=|A|+|B|=3+2=5.

If the sets overlap, adding their sizes counts each shared element twice. For example, $\{p,q,r\}$ and $\{r,s\}$ have sizes $3$ and $2$, but their union is $\{p,q,r,s\}$, which has size $4$, not $5$. The disjointness hypothesis in the theorem is therefore necessary.

Worked Example: Counting Fixed-Length Binary Strings

A binary string of length $3$ has three positions, each of which can contain either $0$ or $1$. Formally, such strings correspond to ordered triples in $\{0,1\}\times\{0,1\}\times\{0,1\}$. There are $2$ choices for the first entry; for each choice there are $2$ choices for the second, and for each resulting pair there are $2$ choices for the third. Repeated use of the Cartesian-product count gives

\bigl|\{0,1\}\times\{0,1\}\times\{0,1\}\bigr|=2\cdot2\cdot2=8.

The eight strings are $000,001,010,011,100,101,110,111$. The count depends on treating positions as distinct: $01$ and $10$ are different strings because their entries occur in different positions.

Using Counting Results Carefully

Finite counting arguments often have a simple structure: specify the objects, specify the categories or choices, and verify that the assignment or list has the properties required by the result. For the Pigeonhole Principle, the objects must be distinct and each must be assigned to one of the stated finite number of categories. For the disjoint-union formula, the sets must have no shared elements. For the Cartesian-product formula, the objects are ordered pairs, so changing the order of the coordinates can change the pair.

A count can fail even when the arithmetic is correct if the objects have been described incorrectly. Repeating one object in a list does not create additional elements of a set. Similarly, an argument that assigns seven entries to six categories proves a repeated category only when those seven entries are seven distinct objects. Checking these hypotheses before counting is part of the proof, not a technical afterthought.

Identify the objects.
State precisely what is being counted, and distinguish separate objects from repeated descriptions of the same object.

Identify the categories or choices.
For an assignment argument, count the available categories; for a product, identify each coordinate and its possible values.

Check the hypotheses.
Verify distinctness where required, and check disjointness before adding set sizes.

Apply the appropriate result.
Use induction-based pigeonhole reasoning for assignments, addition for disjoint unions, and multiplication for ordered pairs.

Key takeaway. A finite set can be listed without repetition, and its size is uniquely determined. Induction proves that more distinct objects than categories force a repeated category; injections, disjoint unions, and Cartesian products provide further ways to compare and calculate finite sizes.

Check Your Understanding

Use the definitions and counting arguments in this tutorial to answer the following questions.

Why does a list containing the same element twice not necessarily represent two elements of a set?
What does the Pigeonhole Principle guarantee when eight distinct objects are assigned to seven categories?
Why must the two sets be disjoint for the formula $|A\cup B|=|A|+|B|$ to apply?
If there is an injection from a finite set $A$ to a finite set $B$, what inequality follows for their sizes?
How many binary strings of length $4$ are there? Explain how the Cartesian-product count gives your answer.

What You'll Learn