Finite Sets

What It Means for a Set to Be Finite

The previous tutorial studied how inverses behave under composition. We now turn from functions to a basic property of sets: whether their elements can be listed using only finitely many entries. A list is a useful way to describe a set, but it is important to distinguish the list from the set it describes. A list can repeat an element or place the same elements in a different order without changing the set.

Definition (Finite Set). A set \(A\) is finite if there is some integer \(n\geq 0\) and there are distinct objects \(a_1,\ldots,a_n\) such that

A=\{a_1,\ldots,a_n\}.

When \(n=0\), the list has no entries and the set it describes is \(\varnothing\). A set that is not finite is called infinite.

The distinctness requirement means that no element is listed twice. It does not mean that the order of the elements matters: sets are determined by their members, not by the order in which those members are written. The definition also includes the empty set as a finite set.

This definition says that a finite set has at least one listing with distinct entries. It does not yet assert that all such listings have the same length. The number of elements in a finite set will be studied in the next tutorial, “Cardinality.” For now, we use only the existence of a distinct listing.

Worked Example: Removing Repetitions from a Description

Consider the set

A=\{4,7,4,9,7\}.

The displayed description repeats \(4\) and \(7\), so it is not a distinct listing. But its elements are exactly \(4\), \(7\), and \(9\). Thus

A=\{4,7,9\}.

The three entries on the right are distinct, so this listing verifies that \(A\) is finite. In particular, repetitions in one description do not make a set infinite; they simply provide a less economical way to write it.

Finite Lists and Their Sets of Entries

Sometimes a list contains repetitions, even when we want to use it to describe a finite set. The following result explains why repetitions cause no difficulty: the set of entries in any finite list is finite. The proof makes the process of removing repetitions precise.

Proposition (A Finite List Describes a Finite Set). For any integer \(n\geq 0\) and any objects \(x_1,\ldots,x_n\), the set \(\{x_1,\ldots,x_n\}\) is finite, whether or not the entries are distinct.

Proof. We use induction on \(n\). If \(n=0\), the set of entries is \(\varnothing\), which is finite by the definition. Now suppose that the set \(E=\{x_1,\ldots,x_n\}\) is finite. We consider the next entry \(x_{n+1}\). If \(x_{n+1}\in E\), then adding it to the description does not change the set, so \(\{x_1,\ldots,x_n,x_{n+1}\}=E\), which is finite. If \(x_{n+1}\notin E\), take a distinct listing \(a_1,\ldots,a_k\) of \(E\), which exists because \(E\) is finite. Then \(a_1,\ldots,a_k,x_{n+1}\) is a distinct listing of \(E\cup\{x_{n+1}\}=\{x_1,\ldots,x_n,x_{n+1}\}\). This set is finite as well. The induction proves the proposition for every \(n\geq 0\). \(\square\)

In the second case, the newly added object is different from every \(a_i\), because it is not in \(E\). Thus the extended listing really is distinct. This check is what allows the proof to use the definition of a finite set.

Worked Example: A List with Several Repetitions

Let \(x_1=5\), \(x_2=2\), \(x_3=5\), \(x_4=8\), and \(x_5=2\). The set of entries is

\{x_1,x_2,x_3,x_4,x_5\}=\{5,2,5,8,2\}=\{5,2,8\}.

The last description has distinct entries. It follows directly that the set is finite. The proposition gives the same conclusion without requiring us to find the distinct listing in advance.

Subsets of Finite Sets

A finite set may contain more elements than a particular subset of interest. The subset is still finite: take a distinct listing of the original set and retain exactly the entries that belong to the subset.

Theorem (Every Subset of a Finite Set Is Finite). Let \(A\) be a finite set and let \(S\subseteq A\). Then \(S\) is finite.

Proof. Since \(A\) is finite, write \(A=\{a_1,\ldots,a_n\}\), where the \(a_i\) are distinct and \(n\geq 0\). If \(n=0\), then \(A=\varnothing\). Since \(S\subseteq A\), \(S\) has no elements, so \(S=\varnothing\) and is finite.

Now suppose \(n\geq 1\). Consider the indices \(i\) for which \(a_i\in S\). If there are no such indices, then \(S=\varnothing\). Otherwise, list those indices in increasing order as \(i_1,\ldots,i_k\). Every element of \(S\) belongs to \(A\), so it equals some \(a_i\); because it also belongs to \(S\), that index is among \(i_1,\ldots,i_k\). Conversely, each \(a_{i_j}\) belongs to \(S\) by the choice of its index. Therefore

S=\{a_{i_1},\ldots,a_{i_k}\}.

The entries in this listing are distinct because the original \(a_1,\ldots,a_n\) are distinct and the selected indices are different. Hence \(S\) is finite. \(\square\)

Worked Example: Selecting a Subset

Let \(A=\{m,n,p,q,r\}\), with all five elements distinct, and let \(S\) be the subset consisting of \(n\), \(q\), and \(r\). The elements of \(S\) are selected from a distinct listing of \(A\), so

S=\{n,q,r\}\subseteq A.

The displayed listing of \(S\) is also distinct, and therefore \(S\) is finite. The subset theorem covers the same conclusion for every subset of \(A\), including \(\varnothing\) and \(A\) itself.

Unions of Finite Sets

To list the elements of a union, begin with a listing of the first set and follow it with a listing of the second. This combined list might repeat some elements, especially if the sets overlap. The result about finite lists then shows that the set described by the combined list is finite.

Theorem (A Union of Two Finite Sets Is Finite). If \(A\) and \(B\) are finite sets, then \(A\cup B\) is finite.

Proof. Since \(A\) and \(B\) are finite, there are distinct listings \(A=\{a_1,\ldots,a_m\}\) and \(B=\{b_1,\ldots,b_n\}\), where either \(m\) or \(n\) is allowed to be zero. The list

a_1,\ldots,a_m,b_1,\ldots,b_n

has finitely many entries. Its set of entries is exactly \(A\cup B\): every entry belongs to \(A\) or \(B\), and every member of either set occurs in the combined list. By the proposition that a finite list describes a finite set, \(A\cup B\) is finite. This proof also covers an empty set among \(A\) and \(B\), since an empty listing contributes no entries. \(\square\)

Worked Example: Combining Two Finite Sets

Take \(A=\{2,6,10\}\) and \(B=\{6,8\}\). Combining their listings gives the list \(2,6,10,6,8\), whose set of entries is

A\cup B=\{2,6,10,8\}.

The combined list repeats \(6\), but that repetition does not affect the union. Removing it gives a distinct listing, which verifies directly that \(A\cup B\) is finite.

Images of Finite Sets

A function sends each input in a set to an output. If the input set is finite, listing its inputs also gives a finite list of their outputs. Some different inputs may have the same output, so the outputs need not be distinct. The finite-list proposition handles those repetitions.

Theorem (The Image of a Finite Set Is Finite). Let \(f:D\to E\), and let \(S\subseteq D\) be finite. Then the image \(f[S]\) is finite.

Proof. Since \(S\) is finite, write \(S=\{a_1,\ldots,a_n\}\), where the \(a_i\) are distinct and \(n\geq 0\). By the definition of the image,

f[S]=\{f(a):a\in S\}=\{f(a_1),\ldots,f(a_n)\}.

The list \(f(a_1),\ldots,f(a_n)\) may contain repetitions, because \(f\) need not be injective. The proposition on finite lists applies whether or not its entries are distinct, so \(f[S]\) is finite. If \(n=0\), then \(S=\varnothing\), and the image is empty, which is finite as well. \(\square\)

Worked Example: A Function Can Identify Different Inputs

Let \(D=\{1,2,3,4\}\), and define \(f:D\to\mathbb R\) by \(f(x)=(x-2)^2\). Evaluating the function at every element of \(D\) gives

f(1)=1,\qquad f(2)=0,\qquad f(3)=1,\qquad f(4)=4.

Thus

f[D]=\{1,0,1,4\}=\{0,1,4\}.

The repeated output \(1\) comes from two different inputs, since \(f(1)=f(3)=1\). The image is nevertheless finite, as the theorem guarantees.

Why Distinct Listings Matter

The definition concerns whether a set can be represented by some finite distinct listing; it does not require every way of writing down its elements to be distinct. This distinction is especially useful when working with unions and function images, where repetitions can naturally appear. The finite-list proposition lets us work first with a convenient list and then conclude that its set of entries is finite.

The results proved here give several practical ways to establish finiteness. A direct distinct listing is enough. If a set is obtained by selecting elements from a finite set, use the subset theorem. If it is formed by joining two finite sets, use the union theorem. If it consists of outputs of a function on a finite domain, use the image theorem. These arguments do not require the function to be injective or the original sets in a union to be disjoint.

Key takeaway. A finite set has a distinct finite listing. Subsets, unions of two finite sets, and images of finite sets are finite; repetitions in an intermediate list do not change this conclusion.

Check Your Understanding

Use the definition and the results in this tutorial to answer the questions.

Why is the empty set finite under the definition of a finite set?
Does the list \(a,b,a,c\) give a distinct listing? What is the set of its entries?
If \(S\subseteq A\) and \(A\) is finite, which theorem guarantees that \(S\) is finite?
Why does the proof that a union of two finite sets is finite still work when the sets overlap?
Must a function be injective for the image of a finite set to be finite? Explain using the finite-list proposition.

What You'll Learn