The Central Idea
A set is finite if its elements can be completely counted and the counting process ends.
A set is countably infinite if it contains infinitely many elements but those elements can still be placed into a list
\[ a_0,\ a_1,\ a_2,\ a_3,\ldots \]so that every element appears at some finite position in the list.
The surprising idea is that an infinite set can have the same cardinality as one of its proper subsets. This cannot happen for finite sets.
What Is a Set?
A set is a collection of distinct objects considered as a single mathematical object.
For example,
\[ A=\{2,4,6,8\} \]is a set containing four elements.
The objects in a set are called its elements or members.
We write
\[ 4\in A \]to mean that \(4\) is an element of \(A\), while
\[ 5\notin A \]means that \(5\) is not an element of \(A\).
Order and Repetition Do Not Change a Set
Sets are determined by membership, not by the order in which their elements are written.
Therefore,
\[ \{1,2,3\}=\{3,2,1\}. \]Repeating an element also does not create a new member:
\[ \{1,1,2,2,3\}=\{1,2,3\}. \]This differs from lists and sequences, where order and repetition may matter. Those structures will be developed in the next lesson.
Finite Sets
A set is finite when it contains some fixed nonnegative whole number of elements.
For example,
\[ B=\{\text{red},\text{green},\text{blue}\} \]contains exactly three elements.
We can record this by writing
\[ |B|=3. \]The notation \(|B|\) denotes the cardinality of the set: the number of elements it contains.
Cardinality
Cardinality measures the size of a set.
If
\[ C=\{5,10,15,20,25\}, \]then
\[ \boxed{|C|=5}. \]For a finite set, cardinality is simply the result obtained by counting its distinct elements.
The Empty Set Is Finite
The empty set contains no elements. It is written
\[ \varnothing \]or sometimes
\[ \{\}. \]Its cardinality is
\[ \boxed{|\varnothing|=0}. \]Because zero is a finite number, the empty set is a finite set.
Finite Does Not Mean Small
A finite set may contain an enormous number of elements.
For example, the set
\[ D=\{1,2,3,\ldots,10^{100}\} \]is finite even though its cardinality is far too large to count manually.
What matters is not whether counting is practical. What matters is whether there is a final element after finitely many counting steps.
Infinite Sets
A set is infinite if it is not finite.
For example, the nonnegative integers continue forever:
\[ \{0,1,2,3,4,\ldots\}. \]No largest nonnegative integer exists. For every integer \(n\), another integer \(n+1\) follows it.
Therefore the set does not have a finite cardinality.
Our Convention for the Natural Numbers
In this lesson, we use
\[ \boxed{\mathbb{N}=\{0,1,2,3,\ldots\}}. \]Some books instead begin the natural numbers with \(1\). Both conventions are common.
Starting with \(0\) is especially convenient in discrete mathematics and computer science because list positions, sequence indices, and counting processes often begin at zero.
What Does Countably Infinite Mean?
A set \(S\) is countably infinite if its elements can be matched one-to-one with the natural numbers.
Symbolically, there must be a bijection
\[ f:\mathbb{N}\to S. \]That means every natural number identifies exactly one element of \(S\), and every element of \(S\) is reached by exactly one natural number.
Informally, a countably infinite set can be listed without omissions:
\[ s_0,\ s_1,\ s_2,\ s_3,\ldots \]Enumeration
An enumeration is a systematic listing of the elements of a set.
For \(\mathbb{N}\), the natural enumeration is
\[ 0,\ 1,\ 2,\ 3,\ 4,\ldots \]Each natural number appears at a finite position, and no natural number is omitted.
An enumeration provides concrete evidence that a set is countably infinite.
Example: The Positive Integers
Consider
\[ P=\{1,2,3,4,\ldots\}. \]Define
\[ f(n)=n+1. \]Then
\[ 0\mapsto1,\qquad 1\mapsto2,\qquad 2\mapsto3,\qquad 3\mapsto4,\ldots \]Every natural number maps to exactly one positive integer, and every positive integer appears.
Therefore,
\[ \boxed{P\text{ is countably infinite}.} \]An Infinite Set Can Match a Proper Subset
The positive integers are a proper subset of the nonnegative integers:
\[ P\subsetneq\mathbb{N}. \]Yet the correspondence
\[ n\mapsto n+1 \]matches every element of \(\mathbb{N}\) with exactly one element of \(P\).
Thus,
\[ |\mathbb{N}|=|P| \]in the sense of infinite cardinality.
This is one of the first major ways that infinite sets behave differently from finite sets.
Why This Cannot Happen for a Finite Set
Suppose a finite set has \(n\) elements.
Any proper subset must leave out at least one of those elements, so it can contain at most
\[ n-1 \]elements.
Therefore a finite set cannot have the same cardinality as one of its proper subsets.
Infinite sets can.
Example: The Even Nonnegative Integers
Consider
\[ E=\{0,2,4,6,8,\ldots\}. \]Define
\[ f(n)=2n. \]Then
\[ 0\mapsto0,\qquad 1\mapsto2,\qquad 2\mapsto4,\qquad 3\mapsto6,\ldots \]Every natural number corresponds to exactly one even nonnegative integer, and every even nonnegative integer appears.
Therefore,
\[ \boxed{|E|=|\mathbb{N}|}. \]There Are Just as Many Evens as Natural Numbers
At first, it may seem that the even numbers should be only half as numerous as the natural numbers because every other natural number is odd.
That intuition works for finite sets but not for infinite cardinalities.
The function
\[ f(n)=2n \]gives a complete one-to-one pairing.
For cardinality, the existence of the pairing matters more than the apparent density of one set inside another.
Example: Multiples of Five
Let
\[ M=\{0,5,10,15,20,\ldots\}. \]The function
\[ f(n)=5n \]produces
\[ 0,\ 5,\ 10,\ 15,\ 20,\ldots \]and reaches every member of \(M\) exactly once.
Therefore \(M\) is also countably infinite.
Example: The Integers
The integers extend infinitely in both directions:
\[ \mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}. \]It may seem impossible to list them starting from one end because there is no leftmost integer.
Instead, alternate around zero:
\[ 0,\ 1,\ -1,\ 2,\ -2,\ 3,\ -3,\ldots \]Every integer eventually appears at a finite position.
Therefore,
\[ \boxed{\mathbb{Z}\text{ is countably infinite}.} \]A Formula for Enumerating the Integers
One possible enumeration \(f:\mathbb{N}\to\mathbb{Z}\) is
\[ f(n)= \begin{cases} \frac{n+1}{2}, & n\text{ odd},\\[4pt] -\frac{n}{2}, & n\text{ even}. \end{cases} \]This gives
\[ f(0)=0,\quad f(1)=1,\quad f(2)=-1,\quad f(3)=2,\quad f(4)=-2,\ldots \]The exact formula is less important than the structural fact: there is a systematic list containing every integer exactly once.
Countability Is About the Possibility of Listing
A countably infinite set does not need to be naturally written in a single increasing order.
The integers show this clearly.
What matters is whether we can devise some systematic procedure that assigns each element a natural-number index:
\[ 0,\ 1,\ 2,\ 3,\ldots \]If such a one-to-one complete indexing exists, the set is countably infinite.
Example: Ordered Pairs of Natural Numbers
Consider the set
\[ \mathbb{N}\times\mathbb{N} = \{(a,b):a,b\in\mathbb{N}\}. \]This set contains an infinite grid of ordered pairs:
\[ (0,0),(0,1),(0,2),\ldots \] \[ (1,0),(1,1),(1,2),\ldots \]Although the grid is infinite in two directions, its pairs can be listed diagonally:
\[ (0,0), (0,1),(1,0), (0,2),(1,1),(2,0),\ldots \]Every pair eventually appears, so
\[ \boxed{\mathbb{N}\times\mathbb{N}\text{ is countably infinite}.} \]Why the Diagonal Method Matters
A naive listing might try to finish all pairs beginning with \(0\):
\[ (0,0),(0,1),(0,2),(0,3),\ldots \]But that row never ends, so the list would never reach \((1,0)\).
Diagonal enumeration avoids getting trapped inside one infinite part of the structure.
This technique will reappear when we study combinations of discrete objects, rational numbers, grids, state spaces, and algorithmic searches.
Example: The Rational Numbers
The rational numbers are numbers that can be written as
\[ \frac{p}{q} \]where \(p\in\mathbb{Z}\) and \(q\in\mathbb{Z}\setminus\{0\}\).
There are infinitely many rational numbers between any two distinct rational numbers, so they may appear far more numerous than the integers.
Nevertheless, rational numbers can be organized through integer numerator and denominator pairs and systematically enumerated while skipping repeated representations.
Therefore,
\[ \boxed{\mathbb{Q}\text{ is countably infinite}.} \]Repeated Representations Must Be Managed
Rational numbers often have many equivalent representations:
\[ \frac12=\frac24=\frac36=\frac48=\cdots \]A proper enumeration must avoid treating these as different rational numbers.
One approach is to list only fractions in lowest terms, with a positive denominator.
This illustrates a general discrete-mathematics principle: a listing procedure must account for duplicates, omissions, and the rules that define when two representations describe the same object.
Finite or Countably Infinite?
Consider the following examples.
- The days of the week form a finite set of cardinality \(7\).
- The letters of the English alphabet form a finite set of cardinality \(26\).
- The integers from \(1\) through \(1{,}000{,}000\) form a finite set.
- The natural numbers form a countably infinite set.
- The even integers form a countably infinite set.
- The prime numbers form a countably infinite set.
- The rational numbers form a countably infinite set.
The category depends on mathematical structure, not on whether the set is easy to write out explicitly.
Infinite Does Not Automatically Mean Countably Infinite
Some infinite sets are too large to be placed into one-to-one correspondence with \(\mathbb{N}\).
The real numbers provide the standard example:
\[ \mathbb{R}. \]The real numbers are uncountable.
A later lesson can develop the proof. For now, the important distinction is that infinity comes in different cardinalities:
\[ \text{finite} \quad\neq\quad \text{countably infinite} \quad\neq\quad \text{uncountable}. \]Finite, Countably Infinite, and Countable
Mathematical texts use the word countable in two related ways.
A common convention says a set is countable if it is either finite or countably infinite.
Under that convention,
\[ \text{countable} = \text{finite or countably infinite}. \]Because terminology can vary, this course will use countably infinite when infinitude is specifically intended.
One-to-One Correspondence
Two sets have the same cardinality when their elements can be paired so that each element of either set is matched with exactly one element of the other.
Such a pairing is called a one-to-one correspondence or bijection.
For finite sets, this agrees with ordinary counting.
For infinite sets, it becomes the central tool for comparing size.
Example: Matching Two Finite Sets
Let
\[ A=\{a,b,c\} \]and
\[ B=\{10,20,30\}. \]We can pair
\[ a\leftrightarrow10,\qquad b\leftrightarrow20,\qquad c\leftrightarrow30. \]Therefore,
\[ |A|=|B|=3. \]The same idea of pairing extends to infinite sets.
Injection, Surjection, and Bijection
Three kinds of mappings are especially useful when comparing sets.
- An injection never sends two different inputs to the same output.
- A surjection reaches every element of the target set.
- A bijection is both injective and surjective.
To prove that a set \(S\) is countably infinite, a standard strategy is to construct a bijection
\[ f:\mathbb{N}\to S. \]A Sequence Is an Enumeration Mechanism
A sequence can be viewed as a function whose domain is \(\mathbb{N}\):
\[ a:\mathbb{N}\to S. \]If the sequence lists every element of \(S\) exactly once, then it gives a bijection and proves that \(S\) is countably infinite.
For example,
\[ a_n=3n \]enumerates the nonnegative multiples of \(3\):
\[ 0,3,6,9,12,\ldots \]This connection between sets and sequences will become increasingly useful throughout discrete mathematics.
Subsets of Finite Sets
Every subset of a finite set is finite.
If
\[ |A|=n \]and
\[ B\subseteq A, \]then
\[ 0\le |B|\le n. \]A subset cannot contain more distinct elements than the finite set from which it is drawn.
Subsets of Countably Infinite Sets
A subset of a countably infinite set may be finite or countably infinite.
For example, inside \(\mathbb{N}\),
\[ \{0,1,2\} \]is finite, while
\[ \{0,2,4,6,\ldots\} \]is countably infinite.
No subset of a countable set can become uncountable.
Combining Countable Sets
Finite combinations of countable sets remain countable.
For example, the union of the even and odd integers is
\[ \mathbb{Z} \]and is still countably infinite.
More generally, even a countable union of countable sets can be enumerated when the pieces are organized systematically.
This principle helps explain why many complicated-looking discrete collections are still countable.
Why Countability Matters in Discrete Mathematics
Countability tells us whether objects can, at least in principle, be indexed and processed one at a time.
This matters when we:
- enumerate possible configurations;
- generate candidate solutions;
- index sequence terms;
- traverse graphs and state spaces;
- construct search procedures;
- count outcomes in probability;
- encode discrete objects;
- organize algorithmic inputs.
Countability does not guarantee that a computation is efficient, but it gives a basic form of discrete organization.
Finite State Spaces
A state space is a set of possible states of a system.
If a light switch has two states,
\[ S=\{\text{off},\text{on}\}, \]then
\[ |S|=2. \]If three independent switches each have two possible states, then the system has
\[ 2^3=8 \]possible configurations.
Finite state spaces appear throughout computing, probability, networks, games, and dynamical systems.
Countably Infinite State Spaces
Some systems have infinitely many possible states but can still be indexed.
A queue that may contain
\[ 0,1,2,3,\ldots \]customers has the state space
\[ S=\mathbb{N}. \]This state space is countably infinite.
Such models appear later in stochastic processes, Markov chains, queueing systems, and reliability analysis.
Finite Versus Countably Infinite Algorithms
Suppose an algorithm checks every element of a finite set.
If the set contains \(n\) elements and each element requires one step, the process can finish after \(n\) steps.
A procedure that attempts to check every member of a countably infinite set can enumerate elements one at a time,
\[ s_0,s_1,s_2,\ldots, \]but it cannot finish checking the entire infinite set in finitely many ordinary steps.
Countable does not mean finite.
A Common Source of Confusion: Listing versus Finishing
Saying that a set can be listed does not mean the list has a last entry.
The natural numbers can be listed as
\[ 0,1,2,3,\ldots \]but there is no final natural number.
Countable infinitude means that every individual element receives a finite index, not that the infinite enumeration eventually terminates.
Common Error: Treating a Very Large Finite Set as Infinite
Consider
\[ A=\{1,2,3,\ldots,10^{1000}\}. \]The set is unimaginably large, but it has a final element.
Therefore,
\[ |A|=10^{1000} \]and \(A\) is finite.
Size alone does not determine whether a set is infinite.
Common Error: Assuming Every Infinite Set Is Countably Infinite
The natural numbers, integers, and rational numbers are countably infinite.
The real numbers are not.
Therefore the implication
\[ \text{infinite}\Longrightarrow\text{countably infinite} \]is false.
Countable infinity is one particular type of infinite cardinality.
Common Error: Missing Elements in an Enumeration
Suppose we try to enumerate the integers as
\[ 0,1,2,3,4,\ldots \]This is not an enumeration of \(\mathbb{Z}\) because every negative integer is missing.
A valid enumeration must reach every element of the target set.
Common Error: Counting Duplicate Representations as New Elements
The fractions
\[ \frac12,\qquad\frac24,\qquad\frac36 \]are different expressions but represent the same rational number.
When enumerating mathematical objects, we must distinguish between representations and the objects represented.
Failing to remove duplicates can invalidate a claimed one-to-one correspondence.
Common Error: Confusing a Proper Subset with a Smaller Infinite Cardinality
For finite sets, a proper subset always has smaller cardinality.
For infinite sets, that conclusion may fail.
The even nonnegative integers satisfy
\[ E\subsetneq\mathbb{N}, \]yet
\[ |E|=|\mathbb{N}|. \]Infinite cardinality must be compared through mappings, not only through subset relationships.
A Reliable Procedure for Classifying a Set
- Identify what counts as a distinct element.
- Determine whether the set has a fixed finite number of elements.
- If so, compute or describe its finite cardinality.
- If not, ask whether the elements can be systematically enumerated.
- Try to construct a bijection with \(\mathbb{N}\).
- Check that no target elements are omitted.
- Check that no two indices represent the same element.
- If no such enumeration can exist, the set may be uncountable.
Example: Classifying Several Sets
Classify each set as finite or countably infinite.
First,
\[ A=\{2,4,6,8,10\}. \]This set has five elements, so
\[ \boxed{|A|=5}. \]Next,
\[ B=\{3,6,9,12,\ldots\}. \]The rule
\[ b_n=3(n+1) \]enumerates every positive multiple of \(3\). Thus \(B\) is countably infinite.
Finally,
\[ C=\{n^2:n\in\mathbb{N}\} = \{0,1,4,9,16,\ldots\}. \]The rule
\[ c_n=n^2 \]enumerates the perfect squares, so \(C\) is countably infinite.
Practice 1: Finite Cardinality
Find the cardinality of
\[ A=\{2,4,6,8,10,12\}. \]Practice 2: Repetition in a Set
Find the cardinality of
\[ B=\{1,1,2,2,2,3,3,4\}. \]Practice 3: A Large Set
Classify
\[ C=\{1,2,3,\ldots,10^9\} \]as finite or infinite.
Practice 4: Odd Nonnegative Integers
Consider
\[ O=\{1,3,5,7,\ldots\}. \]Give a formula that enumerates \(O\) using \(n\in\mathbb{N}\).
Practice 5: Integer Enumeration
Explain why
\[ 0,1,-1,2,-2,3,-3,\ldots \]demonstrates that \(\mathbb{Z}\) is countably infinite.
Practice 6: Proper Subset
Let
\[ E=\{0,2,4,6,\ldots\}. \]Is \(E\) a proper subset of \(\mathbb{N}\)? Does it nevertheless have the same cardinality as \(\mathbb{N}\)?
Practice 7: Multiples of Seven
Show that
\[ M=\{0,7,14,21,\ldots\} \]is countably infinite by giving a bijection from \(\mathbb{N}\) to \(M\).
Practice 8: Finite or Countably Infinite?
Classify each set.
- The months of a year.
- The prime numbers.
- The integers between \(-100\) and \(100\).
- The perfect cubes \(0,1,8,27,\ldots\).
Practice 9: Spot the Problem
A student attempts to enumerate \(\mathbb{Z}\) using
\[ 0,1,2,3,4,\ldots \]Explain why this does not prove that \(\mathbb{Z}\) is countably infinite.
Practice 10: Conceptual Comparison
Explain why the statement
\[ E\subsetneq\mathbb{N} \]does not imply
\[ |E|<|\mathbb{N}| \]when \(E\) is the set of even nonnegative integers.
Practice Answers
Practice 1
There are six distinct elements:
\[ \boxed{|A|=6}. \]Practice 2
Repetition does not create new set elements:
\[ B=\{1,2,3,4\}. \]Therefore,
\[ \boxed{|B|=4}. \]Practice 3
The set has a final element and exactly \(10^9\) members:
\[ \boxed{|C|=10^9}. \]Therefore it is finite.
Practice 4
One enumeration is
\[ \boxed{f(n)=2n+1}. \]This gives
\[ 1,3,5,7,\ldots \]for \(n=0,1,2,3,\ldots\).
Practice 5
Every integer appears exactly once in the alternating list
\[ 0,1,-1,2,-2,3,-3,\ldots \]and every item has a natural-number position. Therefore the list gives a bijection with \(\mathbb{N}\), so \(\mathbb{Z}\) is countably infinite.
Practice 6
Yes. \(E\) is a proper subset because odd natural numbers are not in \(E\). However,
\[ f(n)=2n \]is a bijection from \(\mathbb{N}\) to \(E\). Thus,
\[ \boxed{|E|=|\mathbb{N}|}. \]Practice 7
Define
\[ \boxed{f(n)=7n}. \]This pairs
\[ 0\mapsto0,\quad 1\mapsto7,\quad 2\mapsto14,\quad 3\mapsto21,\ldots \]so \(M\) is countably infinite.
Practice 8
- The months of a year: finite, cardinality \(12\).
- The prime numbers: countably infinite.
- The integers from \(-100\) through \(100\): finite, cardinality \(201\).
- The perfect cubes: countably infinite.
Practice 9
The list includes only nonnegative integers. It omits every negative integer, so it is not an enumeration of \(\mathbb{Z}\).
Practice 10
For infinite sets, a proper subset may have the same cardinality as the original set. The bijection
\[ n\mapsto2n \]pairs every natural number with exactly one even nonnegative integer. Therefore,
\[ \boxed{E\subsetneq\mathbb{N}\quad\text{but}\quad|E|=|\mathbb{N}|}. \]What to Remember
- A finite set contains a fixed finite number of distinct elements.
- The cardinality \(|A|\) records the size of a set.
- The empty set is finite and has cardinality \(0\).
- A countably infinite set can be put into one-to-one correspondence with \(\mathbb{N}\).
- An enumeration lists every element at some finite natural-number index.
- The integers and rational numbers are countably infinite.
- An infinite set can have the same cardinality as one of its proper subsets.
- Not every infinite set is countable; the real numbers are uncountable.
The central test for countable infinity is: Can the objects be organized into a complete one-to-one list indexed by the natural numbers?
Where We Go Next
Sets tell us which objects belong to a collection, but many discrete structures contain additional information about order, position, or repetition.
The next lesson, Tuples, Strings, Lists, and Sequences, develops these ordered structures and shows how they differ from ordinary sets.