Cardinality in mathematics
In: 0
Basically, cardinality refers to the size of a set (i.e. how many elements, or “things”, are in a set). For example, suppose you have the set {A,B,C}. There are 3 elements in the set (A, B, and C), so the set’s cardinality is 3.
In this example, the cardinality is a finite number. However, cardinality doesn’t *have* to be finite. The set of all natural numbers — {1,2,3,4,…..} — has infinitely many numbers in it, so it’s cardinality is also infinite.
Waaaay back when numbers were first invented, we only had natural numbers. Not even 0 was included. The numbers represented a count of things. I have 5 apples. There are 16 people here. Things here is used as an abstract term. Even if I eat half an apple (or person), I don’t have half of a thing, I just have 4 apples and 1 half apple, I still have 5 things.
Cardinality is the measure of the number of elements of the set. Here we have to alter my earlier, simplistic definition of a thing. Modern mathematics is built on Zermelo-Fraenkel Set Theory. There, it is not allowed to repeat items within a set. If there are 2 identical items in a set, they are only considered to be one item. So cardinality is more like the number of unique elements in a set. In terms of apples and people, no two are alike, so as long as you can uniquely identify each element of the set, you can count their number. The value you end up with is the cardinality. For people, you can use names. Instead of 3 people, the set contains Andrew, Brenda, and Cherie.
We also introduce 0 here because a set can have no elements. This is how we get the whole numbers. Still no negative numbers or fractions because a set can’t have negative of parts of an element, it can only contain “whole” elements.
So the next part is not necessarily important to cardinality itself, but just an insight about the rigor that went into modern mathematics. Built on Zermelo-Fraenkel Set Theory, we have a list of axioms that are fundamental to modern math. One of the axioms basically says “0 exists.” We call it the null set or empty set, an its written like this: { }. Now, using the axiom of pairing and the axiom of union… probably one other, we can take a thing that exists and put it in a set. The set containing the empty set (written as { { } }) is a set with a cardinality of 1, because it contains 1 element.
And in fact, this is the strict definition of the number 1 in modern mathematics. It’s just that the average person never needs to know that there is a concrete, axiom-based definition of 1 because it’s so obvious that it doesn’t need one. Unfortunately, mathematics doesn’t accept “it’s just so obvious” as a formal proof. The successor to one is two. Can we make a set with two elements. And remember, they must be unique elements. Well, 1≠0 and we have proven that both 0 and 1 exist. So 2 looks like the set containing both the empty set and the set containing the empty set: { { } , {{ }} }. This set has 2 elements so its cardinality is 2.
Just one more and I’ll leave it. 3 is the set containing all three of the empty set as well as the set containing the empty set, and lastly, the set containing both the empty set and the set containing the empty set: { { } , {{ }} , { { } , {{ }} } }.
Cardinality is just a way to say that two sets have the same number of things.
Now, it is tempting to say that both of the sets {a,b,c} and {x,y,x} have 3 elements and, therefore, they have the same cardinality but this requires “3” to be a middle-man in this process. So we skip the middle man and determine equal cardinality by just making associations. {a,b,c} and {x,y,z} have the same cardinality because I can make the associations:
* a <-> x
* b <-> y
* c <-> z
And with this association 1.) Every element of the set {a,b,c} is used exactly once and 2.) Every element of the set {x,y,z} is used exactly once. So I can say that {a,b,c} and {x,y,z} both have the same cardinality without “3” having to even be a thing! In fact, we *define* the cardinal “3” as “Things with the same cardinality as {a,b,c}”.
This “not having to have numbers to compare size” thing is important because in math you frequently run out of numbers with which to count! If I only have numbers to compare sizes with, then how do I compare the size of the set {0,1,2,3,4,…} with the set {…-2,-1,0,1,2,…}? There’s not enough numbers for this, but I can still say that they have the same cardinality through the association
* 0 <-> 0
* 1 <-> 1
* 2 <-> -1
* 3 <-> 2
* …
This gets even more important when we find things *bigger* than the simple infinity of {0,1,2,3,…}. If I am restricted to using numbers, then I can’t really say that the set {0,1,2,3,…} is *smaller* than the points on the interval (0,1) but, through a clever argument, I can show that any association between these two sets will always fall short of including everything in the (0,1) interval and, therefore, (0,1) is bigger than {0,1,2,…}. Cardinality as associations is very powerful and flexible.
Cardinality is a way of measuring how big a collection of objects is. We say that two sets A and B have the same cardinality if you can pair up elements in A with elements in B in such a way that each element in A is paired with exactly on element in B, and each element in B is paired with exactly one element in A (this is called a bijection). For example the set {cat, dog, mouse} and the set {1, 2, 3} have the same cardinality because I can pair up
cat <–> 1
dog <–>2
mouse <–> 3.
Less intuitively, the set of all whole numbers {1, 2, 3, …} and the set of all even whole numbers {2, 4, 6, 8, …} have the same cardinality because I can pair up
1 <–> 2
2 <–> 4
3 <–> 6
…
An important fact about cardinality is that the set of all (real) numbers has a larger cardinality than the set of all whole numbers.
It a count of the number of elements in a set.
A set contain 3 items has a cardinality of 3. A set containing 10 items has a cardinality of 10.
Now, I am assuming that you are actually asking what it means with respect to infinities. And yes, there are different “sized” infinities.
If you look at the set of all integers, it is infinite. You can always just add 1 to the highest integer, or subtract 1 from the most negative integer and get a new member of the set. This is defined as having a cardinality of aleph-0 (which goes with the infamous drink song, Aleph-0 bottles of beer on the wall, Aleph-0 bottles of beer. You take one down, and pass it around Aleph-0 bottles of bear on the wall).
How can anything be larger than infinity?
Consider the set of real numbers. Are there more real numbers or integers? They’re both infinite so the sets must be the same size! Consider this, however…
Order both sets in increasing size (that is probably how you imagine the set being ordered anyways although technically order is not important in sets).
Between any two elements of the set of integers there is a finite number of elements. The number may be very large but if given enough time you could count them.
Let’s do the same thing with the set of real numbers. Houston, we have a problem! The number of elements between ANY two elements is infinite. We cannot count all the elements between ANY two elements. This is an uncountable infinity, and is a larger infinity than one with a cardinality of aleph-0. It’s cardinality is greater than aleph-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