Section The Cardinality of a Set
How big is a set? When a set is finite, we can count the number of elements in the set and answer the question directly. When a set is infinite, the question is a little more complicated. For example, how big is \(\Z\text{?}\) How big is \(\Q\text{?}\) Since \(\Z\) is a subset of \(\Q\text{,}\) we might think that \(\Q\) contains more elements than \(\Z\text{.}\) But \(\Z\) is infinite and how many more elements can we have than infinity? We won’t answer that question in this section, but it is an interesting one to consider.
If two finite sets have the same number of elements, then it should seem natural to say that the sets are of the same size. How do we extend this to infinite sets? If two finite sets have the same number of elements, then we can pair each element in one set with exactly one element in the other. This is exactly what a bijection does. So a set with \(n\) elements can be paired with the set \(\{1, 2, \ldots, n\}\text{,}\) where \(n\) is a positive integer. This is how we can define a finite set.
Definition 2.12.
A set \(A\) is a finite set if \(A = \emptyset\) or there is a bijection \(f\) mapping \(A\) to the set \(\{1,2,3, \ldots,
n\}\) for some positive integer \(n\text{.}\)
In the case that \(A = \emptyset\text{,}\) we say that \(A\) has cardinality \(0\text{,}\) and if there is a bijection from \(A\) to the set \(\{1,2, \ldots,
n\}\text{,}\) we say that \(A\) has cardinality \(n\text{.}\) If there is no positive integer \(n\) such that there is a bijection from set \(A\) to \(\{1,2, \ldots,
n\}\) we say that \(A\) is an infinite set and say that \(A\) has infinite cardinality. We use the word cardinality instead of number of elements because we can’t actually count the number of elements in an infinite set. We denote the cardinality of the set (the number of elements in the set) \(A\) by \(|A|\text{.}\) It is left to the homework to show that if \(A\) and \(B\) are sets with \(|A|=n\) and \(|B| = m\text{,}\) then \(n=m\) if and only if there is a bijection \(f: A \to B\text{.}\) This tells us that cardinality is well defined. Since composites of bijections are bijections with inverses that are bijections, if there is a bijection from set \(A\) to \(\{1,2, \ldots,
n\}\) and a bijection from a set \(B\) to \(\{1,2, \ldots,
n\}\) for some positive integer \(n\text{,}\) then there is a bijection between \(A\) and \(B\text{.}\) Using this idea, we say that two sets (either finite or infinite) have the same cardinality if there is a bijection between the sets. We will discuss cardinality in more detail a bit later.