Cardinality in mathematics
In: 0
Cardinality is one way of encoding the idea of “how big” a set is. For a set S, we write it |S|, using the same symbol as absolute value (though the two are only loosely related).
We say that |A| <= |B| if we can match up everything in A with one thing in B, so that we’re not reusing anything in B. For example, the set {A, B, C} has a cardinality <= than the set {1, 2, 3, 4} because we can match (say) A to 1, B to 2, and C to 3, without reusing anything from the second set. To put this in more formal language, we’re defining a function f: A->B such that *f* is *injective* (it doesn’t repeat outputs).
Similarly, we say |A| = |B| if you can match up every element of A with exactly one element of B *and use every element of B in the process*. The examples from the previous paragraph don’t have the same cardinality, because while you can map everything in A to one thing in B, you don’t use everything in B (and in fact, you can’t do so). (To again be more formal: |A| = |B| if and only if there exists a function f: A->B that is a *bijection*.)
It’s [complicated to prove this](https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem), but it turns out that |A| = |B| if and only if |A| <= |B| and |B| <= |A|, as you’d hope if we’re going to use <= as a symbol.
—–
Now, you might say “well, obviously {A,B,C} is smaller than {1,2,3,4}, because the first set has 3 elements and the second has 4 elements”. But what do we *mean* by “has 3 elements”? Well, we *mean* “has the same cardinality as the set {1,2,3}”, and in that sense, we can write |A| = 3. Anytime we write |S| = some number, we mean “S has the same cardinality as the set {1, 2, 3, … that number}”.
All of this should feel pretty obvious, and you might wonder why we’d care. After all, we all know how to count long before we know any set theory.
—–
The reason is that for infinite sets, things get weirder. Is |Z| (the cardinality of the set of integers, so {… -3, -2, -1, 0, 1, 2, 3, …}) bigger than |N| (the set of positive integers, so {1, 2, 3, 4, …})? Intuitively, you might say it must be, since Z contains elements N doesn’t *and* contains all of N. But it turns out that you can create a function that maps every integer to exactly one natural number and vice versa, and so |N| = |Z|.
“Okay,” you might say, “so all infinite sets are the same size?” But it turns out that’s not true either, because |N| < |R| (where R is the set of all real numbers).
The formal definitions of cardinality from the earlier paragraphs give us a solid foundation from which to start talking about which sets are “bigger” or “smaller” than others, and that’s why we worry about formalizing the idea at all. It’ll turn out, as you progress in math, that lots of things are true for “small enough” sets that stop being true for “bigger” sets, and you use cardinality to formalize that idea.
Latest Answers