Cardinality of a finite set
Two descriptions of a set can look nothing alike. How do you say exactly how big a set is, and when can you tell that two sets are the same size without counting either one?
Where you are 15 in Sets
Why this exists
A set is decided by what belongs to it (elements and membership), and roster notation writes those elements down. Once a set is written down, the first question anyone asks about it is how big it is.
For a short roster the answer looks obvious: count the entries. But the entries of a roster are not always the elements. The roster \{3, 3, 7\} has three entries and only two elements, and \{\tfrac{1}{2}, 0.5\} has two entries naming one number. Many sets are not given by a roster at all but by a rule, such as “the integers whose square is less than 20” or “the solutions of x^3 = 16x”, and some are too long to list, such as the two-digit numbers that leave remainder 5 on division by 7.
So the size of a set needs a precise meaning: count each distinct element once, whatever the description. With that meaning settled, sizes can be compared, added and, in the lessons that follow, computed for sets far too large to list.
Definition
The cardinality of a finite set A is the number of distinct elements of A. It is written \lvert A\rvert, read “the cardinality of A” or “the size of A”. Some books write n(A) for the same number.
Counting a set means pairing its elements with 1, 2, 3, \dots in turn, using each element exactly once, until none are left. If the last number used is n, then \lvert A\rvert = n. The empty set has nothing to pair, so \lvert\varnothing\rvert = 0.
A one-to-one match between two sets A and B pairs every element of A with exactly one element of B in such a way that every element of B is paired with exactly one element of A. Nothing on either side is left out and nothing is used twice. Counting is a one-to-one match between A and the set \{1, 2, \dots, n\}.
In this lesson the whole numbers are 0, 1, 2, 3 and so on, and the integers are the whole numbers together with their negatives. The set-builder form \{x \in \mathbb{Z} : x^2 < 20\} reads “the set of integers x such that x^2 < 20” (set-builder notation); the symbol \mathbb{Z} is the set of integers and \mathbb{R} the set of real numbers.
Intuition
Think of a cloakroom. Each coat gets one ticket, and the tickets are numbered 1, 2, 3, \dots in order. When the last coat is hung, the number on the last ticket is the number of coats. Two coats belonging to the same person are still two coats, but a set is not a pile of coats: it records only which objects belong, so the same object written twice gets one ticket.
The cloakroom also shows why two sets can be compared without counting. If every seat in a theater holds exactly one person and nobody is standing, there are as many people as seats, and no one had to count either. That is a one-to-one match, and it is often easier to find than a count.
Results
Order and repeats do not change the cardinality. \lvert\{a, b, a, c, b\}\rvert = 3, because \{a, b, a, c, b\} = \{a, b, c\}.
The empty set is the only set of cardinality 0, and \lvert\{\varnothing\}\rvert = 1: its one element is the empty set.
A run of consecutive integers. For integers m \le n,
More generally, a run that starts at a, goes up in equal steps of d and ends at b has \displaystyle \frac{b - a}{d} + 1 elements.
Matching. Two finite sets have the same cardinality exactly when there is a one-to-one match between them.
Subsets are no larger. If A \subseteq B and B is finite, then \lvert A\rvert \le \lvert B\rvert, and if A is a proper subset of B, then \lvert A\rvert < \lvert B\rvert (subsets and equal sets).
Sets with nothing in common add. If A and B are finite and A \cap B = \varnothing, then
For any two finite sets, \lvert A \cup B\rvert \le \lvert A\rvert + \lvert B\rvert.
Why it is true
Repeats. Two sets are equal when they have the same elements, and \{a, b, a, c, b\} and \{a, b, c\} do. Counting pairs each element with one number, so an element written twice is still paired once.
The run of integers. Pair each k in \{m, m + 1, \dots, n\} with k - m + 1. Then m goes to 1, m + 1 to 2, and so on up to n, which goes to n - m + 1. Different k give different numbers, and every number from 1 to n - m + 1 is reached (the number j comes from k = m + j - 1). So this is a one-to-one match with \{1, 2, \dots, n - m + 1\}, which is a count. The difference n - m counts the steps from m to n; the elements are one more than the steps, since the first element comes before any step is taken. The run with step d is the same argument with a + (j - 1)d in place of m + j - 1.
Matching. If \lvert A\rvert = \lvert B\rvert = n, both sets can be matched with \{1, 2, \dots, n\}. Pair the element of A that got ticket j with the element of B that got ticket j; that is a one-to-one match. Going the other way, given a one-to-one match, count A, and give each element of B the ticket of its partner in A. Every element of B gets exactly one ticket, the same tickets are used, so \lvert B\rvert = \lvert A\rvert.
Subsets. To count B, first count the elements of B that are in A, which uses the numbers 1 to \lvert A\rvert, then carry on through the rest of B. The count ends at \lvert A\rvert or later. If A is a proper subset, at least one element of B is left after A is counted, so the count ends later.
Union. If A and B share no element, count A from 1 to \lvert A\rvert, then carry on through B, which takes the next \lvert B\rvert numbers. Every element of A \cup B is counted, and none twice because no element lies in both. When A and B do share elements, the same count reaches each shared element twice, so the total \lvert A\rvert + \lvert B\rvert can only be too large, never too small.
Worked examples
Counting distinct elements
Find the cardinality of each set.
(a) The set of letters used in the word COMMITTEE.
(b) \{x^2 : x \in \{-3, -2, -1, 0, 1, 2, 3\}\}, the set of squares of the integers from -3 to 3.
(c) \{\tfrac{1}{2}, \tfrac{2}{4}, 0.5, \tfrac{3}{6}, \tfrac{1}{3}\}
Solution(a) The word has nine letters, C, O, M, M, I, T, T, E, E, but the set records only which letters appear. M, T and E each appear twice and count once, so the set is \{C, O, M, I, T, E\}, and
Figure 1 shows the count as a match with \{1, 2, 3, 4, 5, 6\}.
(b) The seven inputs give 9, 4, 1, 0, 1, 4, 9. A number and its negative have the same square, so only four distinct values appear:
The set has 4 elements, although it was described using seven inputs.
(c) The entries \tfrac{1}{2}, \tfrac{2}{4}, 0.5 and \tfrac{3}{6} are four ways of writing one number, and \tfrac{1}{3} is a different number. So the set is \{\tfrac{1}{2}, \tfrac{1}{3}\} and its cardinality is 2. Counting a set means counting the objects, not the ways they are written.
Counting a run without listing it
Find \lvert A\rvert and \lvert B\rvert for
A is a run of consecutive integers from m = -8 to n = 30, so
The +1 is there because 30 - (-8) = 38 counts the steps between neighbors, and there is one more element than steps. A small case confirms it: \{-1, 0, 1\} has 1 - (-1) + 1 = 3 elements.
B starts at -20 and goes up in steps of 3. From -20 to 40 is a distance of 60, which is \tfrac{60}{3} = 20 steps, and 40 is reached exactly (-20 + 20 \cdot 3 = 40). So
Check. Pair each element b of B with \tfrac{b + 20}{3}. That sends -20 to 0 and 40 to 20, a one-to-one match with \{0, 1, \dots, 20\}, which has 20 - 0 + 1 = 21 elements.
Sets given by a rule
Find the cardinality of each set.
(a) The prime numbers between 100 and 130.
(b) \{x \in \mathbb{Z} : x^2 < 20\}
(c) \{x \in \mathbb{R} : x^2 < 20\}
(d) The set of real solutions of (x + 2)^2(x - 5) = 0.
(e) \{x \in \mathbb{Z} : x^2 < 0\}
Solution(a) Test each odd number from 101 to 129; the even ones have the factor 2. The odd numbers that are not prime are 105 = 3 \cdot 35, 111 = 3 \cdot 37, 115 = 5 \cdot 23, 117 = 3 \cdot 39, 119 = 7 \cdot 17, 121 = 11 \cdot 11, 123 = 3 \cdot 41, 125 = 5 \cdot 25 and 129 = 3 \cdot 43. The rest are prime:
so the set has 6 elements.
(b) An integer x belongs when x^2 < 20. Since 4^2 = 16 < 20 and 5^2 = 25 > 20, and squares grow as x moves away from 0 in either direction, the elements are the integers from -4 to 4:
By the run count, 4 - (-4) + 1 = 9, so the set has 9 elements.
(c) The same condition over the real numbers lets in every number between \displaystyle -\sqrt{20} and \displaystyle \sqrt{20}, including \tfrac{1}{2}, \tfrac{1}{3}, \tfrac{1}{4} and so on without end. This set is infinite and has no cardinality in the sense of this lesson. The rule alone does not decide the size; the kind of number it ranges over matters as much.
(d) A product is 0 exactly when one of its factors is 0 (the zero-product property). The factor (x + 2)^2 is 0 only at x = -2, and x - 5 is 0 only at x = 5. The solution set is \{-2, 5\}, with 2 elements. The factor x + 2 appears twice, but -2 is one number and is counted once.
(e) The square of any integer is at least 0, so no integer has x^2 < 0. The set is \varnothing, and \lvert\varnothing\rvert = 0.
Counting by a one-to-one match
How many two-digit whole numbers leave remainder 5 when divided by 7?
SolutionCall the set T. A number leaves remainder 5 on division by 7 exactly when it can be written as 7k + 5 for a whole number k. The smallest two-digit one is 12 = 7 \cdot 1 + 5, since 5 = 7 \cdot 0 + 5 has one digit. The largest is 96 = 7 \cdot 13 + 5, since the next, 103 = 7 \cdot 14 + 5, has three digits. So
Now match each n in T with \tfrac{n - 5}{7}, the k it was built from. This sends 12 to 1, 19 to 2, and 96 to 13. Different numbers in T give different values of k, and every k from 1 to 13 is reached, by n = 7k + 5. So the match is one-to-one between T and \{1, 2, \dots, 13\}, and
Check. The run formula from Example 2 gives \tfrac{96 - 12}{7} + 1 = 12 + 1 = 13.
The same size without counting
Let \mathcal{T} be the set of all 3-element subsets of \{1, 2, \dots, 10\}, and \mathcal{S} the set of all 7-element subsets. Show that \lvert\mathcal{T}\rvert = \lvert\mathcal{S}\rvert without finding either number.
SolutionMatch each 3-element subset X with the set of the numbers from 1 to 10 that are not in X. For example, \{2, 5, 9\} is matched with \{1, 3, 4, 6, 7, 8, 10\}. Taking away 3 of the 10 numbers leaves 7, so each X in \mathcal{T} is matched with a set in \mathcal{S}.
The match is one-to-one. Two different 3-element subsets leave behind different numbers, because whatever number is in one and not the other is missing from one leftover set and present in the other. And every 7-element subset Y is reached: the 3 numbers left out of Y form a set in \mathcal{T} whose leftover is exactly Y.
By the matching result, \lvert\mathcal{T}\rvert = \lvert\mathcal{S}\rvert. Nobody listed a single subset. A later lesson counts them (combinations): there are 120 of each.
Adding the sizes of two sets
(a) Let E be the set of even numbers from 1 to 15 and O the set of odd numbers from 1 to 15. Find \lvert E \cup O\rvert from \lvert E\rvert and \lvert O\rvert.
(b) Let A be the set of whole-number divisors of 63 and B the set of whole-number divisors of 84. Compare \lvert A \cup B\rvert with \lvert A\rvert + \lvert B\rvert.
Solution(a) E = \{2, 4, \dots, 14\} has \tfrac{14 - 2}{2} + 1 = 7 elements and O = \{1, 3, \dots, 15\} has \tfrac{15 - 1}{2} + 1 = 8. No number is both even and odd, so E \cap O = \varnothing, and the sizes add:
That is right, since E \cup O = \{1, 2, \dots, 15\}, which has 15 elements.
(b) Listing the divisors,
so \lvert A\rvert = 6, \lvert B\rvert = 12 and \lvert A\rvert + \lvert B\rvert = 18. The union takes every number in either list once:
which has 14 elements, 4 fewer than 18. The sets share the elements 1, 3, 7 and 21, and adding \lvert A\rvert and \lvert B\rvert counts each of those twice. Turning this into a formula for the size of any union is the next lesson, counting a union.
Boundaries
Cardinality as a counting number is for finite sets only. A set such as \{x \in \mathbb{R} : x^2 < 20\} or the set of positive multiples of 5 never runs out, and the count never ends. Sizes of such sets are compared by one-to-one matches instead, in infinite sets.
“A proper subset is smaller” needs the larger set to be finite. The match n \mapsto 2n pairs every positive whole number with an even one, so the even positive whole numbers can be matched one-to-one with all the positive whole numbers, though they are a proper subset of them. For finite sets this cannot happen.
A count needs the objects and the kind of number to be settled. Before counting, decide which entries name the same object (\tfrac{2}{4} and 0.5 are one number) and what the rule ranges over: \{x : x^2 < 20\} has 9 elements among the integers and infinitely many among the real numbers.
A match proves equal sizes only if it is one-to-one both ways. A pairing that sends two elements of A to the same element of B, or misses an element of B, does not show \lvert A\rvert = \lvert B\rvert.
The run formula needs equal steps and both ends in the set. \displaystyle \frac{b - a}{d} + 1 counts \{a, a + d, \dots, b\} only when b - a is a whole number of steps d.
Where this goes next
The next lesson, counting a union, finds \lvert A \cup B\rvert when A and B overlap, by correcting for the elements counted twice. Counting choices made in stages multiplies sizes, and the same idea gives the size of a Cartesian product, \lvert A \times B\rvert = \lvert A\rvert \cdot \lvert B\rvert. Counting the arrangements of a set, such as the 8! = 40{,}320 orders of 8 flags on a pole, is arranging all the objects, and the set of all subsets of a set of size n, the power set, has 2^n elements.
The one-to-one match becomes a function with a name, a bijection, in one-to-one, onto and bijective functions, and the same idea compares the sizes of sets that never end in infinite sets.
Exercises
Distinct elements
- Find each cardinality. (a) The set of letters used in the word BOOKKEEPER. (b) \displaystyle \{\sqrt{4}, 2, \tfrac{4}{2}, -2\}. (c) \{x^2 : x \in \{-2, -1, 0, 1, 2, 3\}\}. (d) \{\varnothing, 0, \{0\}\}.
- Which of these sets have cardinality 3? (a) \{7, 7, 8, 9\}, (b) \{\{1, 2, 3\}\}, (c) \{1, \{2, 3\}, \{3, 2\}\}, (d) \{-0, 0, 1, 2\}.
Runs
- Find each cardinality. (a) \{40, 41, \dots, 97\}, (b) \{-15, -14, \dots, 15\}, (c) \{5, 12, 19, \dots, 75\}, (d) \{100, 96, 92, \dots, 4\}.
- How many multiples of 9 lie between 200 and 500?
- A reader reads every page from page 37 to page 112 of a book, both included. How many pages is that?
Sets given by a rule
- Find \lvert\{x \in \mathbb{Z} : \lvert x - 3\rvert \le 5\}\rvert.
- How many whole numbers less than 40 leave remainder 1 when divided by 3 and also leave remainder 1 when divided by 4?
- Find the cardinality of the set of real solutions of each equation. (a) x^2 + 16 = 8x, (b) x^3 = 16x, (c) x^2 + 7 = 0, (d) (x - 2)^2(x + 5)^3 = 0.
- How many whole-number divisors does 72 have?
- How many perfect squares lie between 1 and 50, both included?
One-to-one matches
- Give a one-to-one match between \{17, 34, 51, \dots, 1700\} and \{1, 2, \dots, 100\}, and state the cardinality of the first set.
- Use a one-to-one match to count the whole numbers from 1 to 2000 whose last digit is 4.
- Explain why the set of 2-element subsets of \{a, b, c, d, e\} and the set of its 3-element subsets have the same cardinality, then find that cardinality by listing one of them.
- Use the match k \mapsto 2k - 1 to find \lvert\{1, 3, 5, \dots, 199\}\rvert.
Unions
- Let A be the set of multiples of 8 and B the set of multiples of 12, both from 1 to 100. Find \lvert A\rvert, \lvert B\rvert and, by listing, \lvert A \cup B\rvert. Say which elements make \lvert A\rvert + \lvert B\rvert too large.
- Let A = \{x \in \mathbb{Z} : -5 \le x < 0\} and B = \{x \in \mathbb{Z} : 0 \le x \le 5\}. Find \lvert A \cup B\rvert from \lvert A\rvert and \lvert B\rvert, and say why adding is allowed here.
Reasoning
- Without listing the primes, explain why fewer than 50 prime numbers are less than 100.
- Explain why \{m, m + 1, \dots, n\} has n - m + 1 elements and not n - m.
- The equation x^2 - 14x + 49 = 0 is a quadratic. Explain why its solution set has exactly one element.
- Suppose A \subseteq B, B is finite and \lvert A\rvert = \lvert B\rvert. Explain why A = B.
- The match n \mapsto 2n pairs every positive whole number with an even positive whole number. Explain why this does not contradict the result that a proper subset of a finite set has fewer elements than the set.
Answers
- (a) 6: the letters are \{B, O, K, E, P, R\}. (b) 2: \displaystyle \sqrt{4}, 2 and \tfrac{4}{2} are all the number 2, so the set is \{2, -2\}. (c) 4: the squares are 4, 1, 0, 1, 4, 9, giving \{0, 1, 4, 9\}. (d) 3: the empty set, the number 0 and the set \{0\} are three different objects.
- (a) and (d). (a) is \{7, 8, 9\}. (b) has the one element \{1, 2, 3\}. (c) is \{1, \{2, 3\}\}, with 2 elements, since \{2, 3\} = \{3, 2\}. (d) is \{0, 1, 2\}, since -0 = 0.
- (a) 97 - 40 + 1 = 58. (b) 15 - (-15) + 1 = 31. (c) \tfrac{75 - 5}{7} + 1 = 11. (d) going down by 4: \tfrac{100 - 4}{4} + 1 = 25.
- 33. The multiples are 207 = 9 \cdot 23 up to 495 = 9 \cdot 55, matched with \{23, \dots, 55\}, which has 55 - 23 + 1 = 33 elements.
- 112 - 37 + 1 = 76 pages.
- 11. The condition says x is within 5 of 3, so -2 \le x \le 8, and 8 - (-2) + 1 = 11.
- 4. A number leaves remainder 1 on division by both 3 and 4 exactly when n - 1 is a multiple of both, so a multiple of 12. The numbers are \{1, 13, 25, 37\}.
- (a) 1: the equation is (x - 4)^2 = 0, so the set is \{4\}. (b) 3: x(x - 4)(x + 4) = 0 gives \{-4, 0, 4\}. (c) 0: x^2 = -7 has no real solution. (d) 2: the set is \{-5, 2\}.
- 12: \{1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72\}. (Since 72 = 2^3 \cdot 3^2, a divisor is 2^i 3^j with 4 choices of i and 3 of j.)
- 7: \{1, 4, 9, 16, 25, 36, 49\}, matched with \{1, \dots, 7\} by k \mapsto k^2, since 7^2 = 49 \le 50 < 64 = 8^2.
- Match n \mapsto \tfrac{n}{17}, with k \mapsto 17k going back. The first set has 100 elements.
- 200. The numbers are 4, 14, 24, \dots, 1994. Match n \mapsto \tfrac{n - 4}{10}, which sends them one-to-one onto \{0, 1, \dots, 199\}, with 199 - 0 + 1 = 200 elements.
- Match each 2-element subset with the 3 letters it leaves out; this is one-to-one, as in Example 5. The 2-element subsets are \{a, b\}, \{a, c\}, \{a, d\}, \{a, e\}, \{b, c\}, \{b, d\}, \{b, e\}, \{c, d\}, \{c, e\} and \{d, e\}, so each set has 10 elements.
- 100. Solving 2k - 1 = 199 gives k = 100, and k \mapsto 2k - 1 matches \{1, \dots, 100\} one-to-one with the set.
- \lvert A\rvert = 12 (8 to 96), \lvert B\rvert = 8 (12 to 96). The union holds 8, 12, 16, 24, 32, 36, 40, 48, 56, 60, 64, 72, 80, 84, 88 and 96, with 16 elements. The sum 12 + 8 = 20 is 4 too large, because 24, 48, 72 and 96 are in both sets and are counted twice.
- \lvert A\rvert = 5 and \lvert B\rvert = 6, so \lvert A \cup B\rvert = 11. Adding is allowed because A holds only negative integers and B none, so A \cap B = \varnothing. Indeed A \cup B = \{-5, \dots, 5\} has 5 - (-5) + 1 = 11 elements.
- Every prime other than 2 is odd, and 1 is not prime, so the primes less than 100 form a subset of \{2\} \cup \{3, 5, \dots, 99\}. These two sets share nothing, so it has 1 + \left(\tfrac{99 - 3}{2} + 1\right) = 1 + 49 = 50 elements. It is a proper subset, since 9 is in it and is not prime. A proper subset of a finite set has fewer elements, so there are fewer than 50 primes below 100.
- The difference n - m counts the steps of size 1 from m to n. Each step lands on a new element, and m itself is an element reached before any step, so there are n - m + 1 elements. Formally, k \mapsto k - m + 1 is a one-to-one match with \{1, \dots, n - m + 1\}. The smallest case shows it: \{m\} has 1 element, while n - m = 0.
- The equation is (x - 7)^2 = 0, which holds only when x - 7 = 0, that is x = 7. The factor x - 7 appears twice, but a set counts each number once, so the solution set is \{7\}, with one element.
- If A \neq B, then A is a proper subset of B, so \lvert A\rvert < \lvert B\rvert, which contradicts \lvert A\rvert = \lvert B\rvert. So A = B.
- The set of positive whole numbers is infinite. The result about proper subsets holds only when the larger set is finite: the count of the subset ends before the count of the whole set does, and an infinite set’s count never ends at all. Matches like n \mapsto 2n are how infinite sets are compared, in infinite sets.