How Large Is a Set?
Suppose
\[ A=\{2,4,6,8\}. \]There are four elements in \(A\), so we say the set has cardinality \(4\).
\[ |A|=4. \]For a small finite set, this is just counting.
But now consider
\[ \mathbb{N}=\{1,2,3,4,\ldots\}. \]There is no last natural number. The set keeps going forever.
How can we talk about the size of a set that never ends?
The key idea is not to finish counting the elements. Instead, we compare sets by asking whether their elements can be matched one-to-one.
This lets the familiar idea of “same number of elements” extend into the infinite.
Cardinality
The cardinality of a set is its number of elements.
For a set \(A\), cardinality is commonly written
\[ |A|. \]For example, if
\[ A=\{\text{red},\text{blue},\text{green}\}, \]then
\[ |A|=3. \]The vertical bars here do not mean absolute value. The surrounding context tells us that we are measuring the size of a set.
Repeated Entries Do Not Increase Cardinality
Because sets contain distinct elements,
\[ \{1,1,2,2,3\}=\{1,2,3\}. \]Therefore,
\[ |\{1,1,2,2,3\}|=3. \]The Empty Set
The empty set has no elements:
\[ \varnothing=\{\}. \]Therefore,
\[ |\varnothing|=0. \]Finite Sets
A set is finite if its elements can be completely counted and that counting ends at some whole number.
For example,
\[ B=\{5,10,15,20,25\} \]is finite because
\[ |B|=5. \]A set does not need to be small to be finite.
A database containing \(8{,}000{,}000\) customer records is still finite if there are exactly \(8{,}000{,}000\) records.
Finite Does Not Mean Easy to List
Suppose \(D\) is the set of all dates from January 1, 2000 through December 31, 2099.
Writing every date would be tedious, but the collection is still finite. There is a first date, a last date, and only finitely many dates in between.
So “finite” is a mathematical property of the size of a set, not a statement about whether listing the set is convenient.
Infinite Sets
A set is infinite if it is not finite.
The natural numbers provide the standard example:
\[ \mathbb{N}=\{1,2,3,4,5,\ldots\}. \]No matter how far we count, another natural number comes next.
Other familiar infinite sets include
\[ \mathbb{Z} = \{\ldots,-3,-2,-1,0,1,2,3,\ldots\}, \]the integers, and
\[ \mathbb{R}, \]the real numbers.
At this stage, it is enough to recognize that these sets do not contain some huge but final number of elements. Their size is genuinely infinite.
Comparing Sets by Matching
Suppose we have two finite sets:
\[ A=\{a,b,c\} \]and
\[ B=\{10,20,30\}. \]We could count both sets and observe that each has three elements.
But there is another way. Match each element of \(A\) with exactly one element of \(B\):
\[ a\leftrightarrow 10, \qquad b\leftrightarrow 20, \qquad c\leftrightarrow 30. \]No element is left unmatched, and no element is used twice.
This is called a one-to-one correspondence.
When two sets can be placed in one-to-one correspondence, they have the same cardinality.
\[ |A|=|B|. \]Why Matching Is Powerful
For finite sets, matching and ordinary counting agree.
For infinite sets, matching becomes much more useful because we cannot finish counting to infinity. Instead, we can describe a rule that pairs every element of one infinite set with exactly one element of another.
The Infinite-Set Surprise
With finite sets, a proper subset must have fewer elements than the whole set.
For example, if
\[ A=\{1,2,3,4\} \]and
\[ B=\{2,4\}, \]then
\[ B\subsetneq A \]and
\[ |B|<|A|. \]For infinite sets, this familiar rule can fail.
Consider the natural numbers
\[ \mathbb{N}=\{1,2,3,4,\ldots\} \]and the positive even numbers
\[ E=\{2,4,6,8,\ldots\}. \]Clearly,
\[ E\subsetneq\mathbb{N}. \]The even numbers form only part of the natural numbers.
Yet we can match every natural number \(n\) with the even number \(2n\):
\[ 1\leftrightarrow2, \qquad 2\leftrightarrow4, \qquad 3\leftrightarrow6, \qquad 4\leftrightarrow8, \qquad \ldots \]Every natural number receives one even number, and every positive even number appears exactly once.
Therefore,
\[ |\mathbb{N}|=|E|. \]An infinite set can have the same cardinality as one of its proper subsets. This is one of the first signals that infinity behaves differently from ordinary finite quantities.
Countably Infinite Sets
A set is countably infinite if its elements can be matched one-to-one with the natural numbers.
Informally, this means the elements can be placed into a list:
\[ a_1,a_2,a_3,a_4,\ldots \]The list never ends, but every element of the set eventually receives a position.
The natural numbers themselves are countably infinite.
The positive even integers are countably infinite because the rule
\[ n\mapsto2n \]matches the natural numbers with them.
The positive odd integers are also countably infinite because
\[ n\mapsto2n-1 \]matches
\[ 1,2,3,4,\ldots \]with
\[ 1,3,5,7,\ldots \]exactly once.
Why the Integers Are Countable
At first, the integers may seem larger than the natural numbers because they extend forever in two directions:
\[ \mathbb{Z} = \{\ldots,-3,-2,-1,0,1,2,3,\ldots\}. \]But we can arrange them in a list:
\[ 0,1,-1,2,-2,3,-3,4,-4,\ldots \]Now assign the natural numbers in order:
\[ 1\leftrightarrow0, \qquad 2\leftrightarrow1, \qquad 3\leftrightarrow-1, \qquad 4\leftrightarrow2, \qquad 5\leftrightarrow-2, \qquad \ldots \]Every integer eventually appears in the list.
Therefore,
\[ |\mathbb{Z}|=|\mathbb{N}|. \]The integers contain the natural numbers and infinitely many additional negative numbers, yet they still have the same cardinality in the infinite sense.
A Gentle Look at the Rational Numbers
The rational numbers are numbers that can be written as
\[ \frac{p}{q}, \qquad p,q\in\mathbb{Z}, \qquad q\neq0. \]There are infinitely many rational numbers between any two different real numbers, so it may seem impossible that the rationals could be countable.
Yet they are.
One way to see the basic idea is to arrange fractions in a grid according to numerator and denominator and then move through that grid in a systematic diagonal pattern.
Some fractions repeat the same rational number:
\[ \frac12=\frac24=\frac36. \]When duplicates are skipped, every positive rational number can still be reached after finitely many steps.
The negative rationals and \(0\) can then be woven into the same kind of list.
Thus the rational numbers satisfy
\[ |\mathbb{Q}|=|\mathbb{N}|. \]This is an advanced result, so the important takeaway here is conceptual: a set can be extremely dense and still be countably infinite.
Not Every Infinity Is the Same Size
The real numbers behave differently.
There is no way to list every real number so that each real number appears at some finite position on the list.
A set with this property is called uncountable.
The real numbers are uncountable:
\[ |\mathbb{R}|>|\mathbb{N}|. \]So infinity is not a single cardinality.
There are at least different sizes of infinity, including
- the countable infinity of \(\mathbb{N}\), \(\mathbb{Z}\), and \(\mathbb{Q}\), and
- the larger uncountable infinity of \(\mathbb{R}\).
A Preview of Cantor's Idea
Georg Cantor showed that no proposed list can contain every real number in an interval such as
\[ (0,1). \]The core strategy constructs a new real number that differs from the first listed number in one decimal place, the second listed number in another place, the third in another, and so on.
The newly constructed number cannot equal any number on the original list. Therefore the list was incomplete.
We will not develop the full diagonal argument here. The purpose of this preview is to show where the basic idea of cardinality eventually leads.
Cardinality and Power Sets
In the previous lesson, we learned that a finite set with \(n\) elements has
\[ 2^n \]subsets.
In cardinality notation,
\[ |\mathcal{P}(A)|=2^{|A|} \]when \(A\) is finite.
For example, if
\[ A=\{a,b,c,d\}, \]then
\[ |A|=4 \]and
\[ |\mathcal{P}(A)|=2^4=16. \]The Infinite Version
Cantor proved something even more powerful:
For every set \(A\), finite or infinite, its power set has strictly greater cardinality than \(A\) itself.
\[ |A|<|\mathcal{P}(A)|. \]That means there is no “largest infinity.” Starting with any infinite set, forming its power set produces a strictly larger cardinality.
This is another advanced result, but it grows naturally from the same power set concept introduced earlier.
Practical Applications
Database Size
If a database table contains \(125{,}000\) records, its set of records has cardinality
\[ 125{,}000. \]Cardinality provides the mathematical abstraction behind ordinary record counts.
Unique Customers
Suppose a transaction log contains \(10{,}000\) purchases but only \(3{,}400\) distinct customer IDs.
If \(T\) is the multiset-like transaction collection and \(C\) is the set of unique customers, then the cardinality relevant to unique customers is
\[ |C|=3400. \]This illustrates why sets ignore repetition: cardinality counts distinct members.
Computer Science
Many computing problems ask whether two collections can be paired or indexed. Arrays, identifiers, database keys, and enumerations all rely on controlled ways of associating positions with objects.
The idea of placing objects in one-to-one correspondence is therefore not merely abstract. It is closely related to indexing and unique assignment.
Combinatorics
Cardinality is also the foundation of counting problems.
If a set \(A\) contains \(n\) available objects, then questions about selections, arrangements, and combinations begin with the information
\[ |A|=n. \]Probability
For a finite sample space \(\Omega\) in which all outcomes are equally likely, probabilities often compare the cardinality of an event \(E\) with the cardinality of the entire sample space:
\[ P(E)=\frac{|E|}{|\Omega|}. \]Cardinality therefore becomes part of the language used to measure probability.
Worked Examples
Example 1: Cardinality of a Finite Set
Let
\[ A=\{-3,-1,0,2,7\}. \]There are five distinct elements, so
\[ |A|=5. \]Example 2: Repeated Entries
Find the cardinality of
\[ B=\{1,1,2,2,2,3,4,4\}. \]As a set,
\[ B=\{1,2,3,4\}. \]Therefore,
\[ |B|=4. \]Example 3: A Finite Solution Set
Let
\[ S=\{x\in\mathbb{Z}\mid x^2=9\}. \]The integer solutions are
\[ x=-3 \qquad\text{and}\qquad x=3. \]Thus
\[ S=\{-3,3\} \]and
\[ |S|=2. \]Example 4: A Finite Interval of Integers
Let
\[ A=\{x\in\mathbb{Z}\mid -4\leq x\leq5\}. \]The elements are
\[ -4,-3,-2,-1,0,1,2,3,4,5. \]There are ten integers, so
\[ |A|=10. \]Example 5: Matching Infinite Sets
Show that the positive multiples of \(3\),
\[ M=\{3,6,9,12,\ldots\}, \]have the same cardinality as \(\mathbb{N}\).
Use the correspondence
\[ n\mapsto3n. \]This gives
\[ 1\leftrightarrow3, \qquad 2\leftrightarrow6, \qquad 3\leftrightarrow9, \qquad \ldots \]Every natural number has one match, and every positive multiple of \(3\) appears exactly once.
Therefore,
\[ |M|=|\mathbb{N}|. \]Example 6: Power-Set Cardinality
Suppose
\[ |A|=6. \]Then
\[ |\mathcal{P}(A)|=2^6=64. \]So \(A\) has \(64\) distinct subsets.
Common Errors
1. Counting Repeated Entries More Than Once
In a set,
\[ \{1,1,1,2,2,3\}=\{1,2,3\}. \]Its cardinality is
\[ 3, \]not \(6\).
2. Confusing Cardinality with the Sum of Elements
If
\[ A=\{10,20,30\}, \]then
\[ |A|=3, \]not \(60\).
Cardinality counts elements. It does not add their values.
3. Assuming Every Proper Subset Must Be Smaller
That is true for finite sets but not for infinite sets.
The even numbers satisfy
\[ E\subsetneq\mathbb{N} \]while still having
\[ |E|=|\mathbb{N}|. \]4. Treating Infinity as an Ordinary Number
Infinity is not used here as though it were simply the next number after all finite numbers.
Infinite cardinality is studied through structural comparisons between sets.
5. Assuming All Infinite Sets Have the Same Cardinality
The natural numbers are countable, while the real numbers are uncountable.
\[ |\mathbb{N}|<|\mathbb{R}|. \]6. Thinking Dense Means Uncountable
The rational numbers are dense in the real numbers, yet
\[ |\mathbb{Q}|=|\mathbb{N}|. \]Density and cardinality describe different properties.
Practice
Finite Cardinality
Find the cardinality of each set.
- \(\{2,4,6,8,10\}\)
- \(\{a,a,b,c,c,c\}\)
- \(\varnothing\)
- \(\{x\in\mathbb{Z}\mid 2\leq x\leq8\}\)
Check Answers
- \[ 5 \]
- The distinct elements are \(a,b,c\), so \[ 3. \]
- \[ |\varnothing|=0. \]
- The integers are \[ 2,3,4,5,6,7,8, \] so the cardinality is \[ 7. \]
Finite or Infinite?
Classify each set as finite or infinite.
- The months of the year
- The positive multiples of \(5\)
- The integers between \(-100\) and \(100\)
- The real numbers between \(0\) and \(1\)
Check Answers
- Finite.
- Infinite.
- Finite.
- Infinite.
One-to-One Correspondence
Let
\[ S=\{7,14,21,28,\ldots\}. \]Give a rule matching \(\mathbb{N}\) one-to-one with \(S\).
Check Answer
Use
\[ n\mapsto7n. \]This produces
\[ 1\mapsto7, \quad 2\mapsto14, \quad 3\mapsto21, \quad \ldots \]so \(S\) is countably infinite.
Power-Set Cardinality
A finite set \(A\) has \(8\) elements. How many elements are in its power set?
Check Answer
\[ |\mathcal{P}(A)|=2^8=256. \]Therefore the power set contains
\[ \boxed{256} \]subsets.
The Deeper Idea
For finite sets, size is familiar:
\[ \text{count the elements}. \]For infinite sets, the deeper principle is:
\[ \text{compare the elements by one-to-one correspondence}. \]This shifts cardinality from a simple counting procedure into a structural idea.
The question is no longer only
“How far can I count?”
but rather
“Can every object in one set be paired uniquely with an object in the other?”
That idea will return when we study functions, because a one-to-one correspondence is a special kind of function called a bijection.
So cardinality builds a direct bridge:
\[ \boxed{ \text{sets} \longrightarrow \text{matching} \longrightarrow \text{functions} \longrightarrow \text{comparison of size} } \]The lesson begins with ordinary counting and ends at the doorway to modern set theory.
Summary
- The cardinality of a set \(A\) is written \[ |A| \] and describes how many elements the set contains.
- A finite set has a finite whole-number cardinality.
- An infinite set is not finite.
- Two sets have the same cardinality when their elements can be placed in a one-to-one correspondence.
- The natural numbers are countably infinite.
- The positive even numbers have the same cardinality as the natural numbers: \[ |\{2,4,6,\ldots\}|=|\mathbb{N}|. \]
- The integers are countably infinite: \[ |\mathbb{Z}|=|\mathbb{N}|. \]
- The rational numbers are also countably infinite: \[ |\mathbb{Q}|=|\mathbb{N}|. \]
- The real numbers are uncountable: \[ |\mathbb{N}|<|\mathbb{R}|. \]
- A finite set with \(n\) elements has \[ 2^n \] subsets.
- More generally, a power set always has strictly greater cardinality than the set from which it was formed.
Cardinality begins as ordinary counting, but it becomes a way of comparing entire mathematical structures. The central tool is one-to-one matching, which will soon connect naturally with relations and functions.
Sets, Relations, and Functions
- Previous: Union, Intersection, Difference, and Complement
- Sets, Relations, and Functions — return to the lesson directory.