Cardinality
Consider the following question:
Are there more Horsemen of the Apocalypse, or teams in the American Football Conference – East Division?
The standard way to answer this question would be to count each collection. First let’s do the Horsemen of the Apocalypse.
With the help of artist Viktor Vasnetsov, we form a bijection like
We can make a bijection to count the teams of the AFC – East, for example
So the two sets both have four elements, hence are the same size. This is one utility of cardinality: we can check whether two sets are the same size by counting each set, then comparing the resulting numbers.
But what if we didn’t know how to count? You may not remember what it was like not to be able to count (don’t worry, you’ll soon be experiencing that same feeling again), but there was a time when nobody could count.
Overview of Cardinality
- Counting without Counting (this page).
- Finite Sets and Infinite Sets
- Denumerable Sets
- Are All Sets Denumerable? (gosh, it sure seems like it!)
- Cantor’s Little Theorem and Cantor’s Big Theorem
One, Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, … One Hundred
Here are the ways to say some numbers in a few languages of the Indo-European language family:
French | Latin | Irish | Serbian | German | English | |
1 | un | unus | haon | jedan | ein | one |
2 | deux | duo | do | dva | zwei | two |
3 | trois | tres | tri | tri | drei | three |
4 | quatre | quattuor | ceahtair | četri | vier | four |
5 | cinq | quinque | cuig | pet | funf | five |
6 | six | sex | se | šest | sechs | six |
7 | sept | septem | seacht | sedam | sieben | seven |
8 | huit | octo | hocht | ossam | acht | eight |
9 | neuf | novem | naoi | devet | neun | nine |
10 | dix | decem | deich | deset | zehn | ten |
20 | vingt | viginti | fiche | dvadeset | zwanzig | twenty |
27 | vingt sept | viginti septem | fiche seacht | dvadeset sedam | siebenundzwanzig | twenty-seven |
81 | quatre-vingts un | octoginta unus | ochto a haon | ossamdeset jedan | einundachtzig | eighty-one |
100 | cent | centum | cead | sto | hundert | one hundred |
1000 | mille | mille | mile | hiljada | tausend | one thousand |
There are some interesting patterns here: the word for three is almost identical across all these languages, as are the words for four (sometimes the initial sound is k, sometimes ch, sometimes f, but it always ends in r) and seven. In fact, the numbers 1-10 are what linguists call cognate: they appear to all descend from the same word in the original Proto-Indo-European language, which was spoken somewhere in what’s now Iran or Afghanistan.
Another word that is common across all the languages is the word for one hundred. This one is a little less obvious, but the linguists tell us the Proto-Indo-European word was kmtom. (In some languages that k became a c or s; in others it became an h). So you might be tempted to think that the languages just all have basically the same ways to count.
. . . until you look at the words for 20. In English and German, the word for 20 is derived from the word for 2, but with some decoration. In Serbian, it’s just two tens. The Latin word viginta is derived from the word ginta, which means a group of 10 (which is different from the number 10, sort of like the difference between dozen and twelve), and vi, which is an old word for two (that sounds like the Serbian dva). French vingt is the same as in Latin. In Irish, the word for 20 is just its own thing unrelated to any other numbers.
When we get to 81, each language has its own completely different way to express the number:
French | quatre-vingt un | four-twenty one |
Latin | octoginta unus | eight-groups-of-ten one |
Irish | ochto a haon | eight+decoration and one |
Serbian | ossamdeset jedan | eight-ten one |
German | einundachtzig | one and eight+decoration |
English | eighty-one | eight+decoration one |
So what’s going on here? The linguists tell us that the Proto-Indo-Europeans knew how to count to ten, and had a word for one hundred, but didn’t have words for anything in between. The theory is that kmtom didn’t actually mean 100 anyway, just a big number, which the English word hundred sort of still does sometimes — I’ve told you a hundred times rarely means precisely 100. There are also other uses of the word hundred that don’t mean 100 of anything, just some kind of vaguely large number:
- In England and Wales, counties were divided into hundreds: administrative subdivisions which ranged from 50 to 200 households.
- Several units of measurement from medieval English law: a hundredweight is either 108 or 112 pounds, depending; a hundred of herring is 120 fish; a hundred of spices is 108 pounds; a hundred of garlic is 225 bulbs.
From archaeological evidence, we also know that this people-group were pastoralists: they herded sheep and/or goats. (Archaeologists can’t tell the difference between sheep bones and goat bones.) It takes a lot more than 10 sheep-goats to sustain a family. So how did the Proto-Indo-Europeans manage to keep track of their flocks without being able to count them?
They used bijections, in a way that’s still used to this day by shepherds all around the world. The equipment used is simple: a container and a pile of pebbles. In the morning, as the sheep-goats are leaving their pen, drop a pebble into the container every time a sheep-goat passes you. This is a bijection between the flock and the pebbles in the container. At the end of the day, as the sheep-goats come back into their pen, remove one pebble for each sheep-goat that passes you on its way in. If the container is empty, you know you haven’t lost any animals; if there’s still pebbles left in the container, you know you have lost one.
One needn’t use pebbles; one could instead make marks on a stick with a knife, for example (this method of recordkeeping persisted in Europe through the 1800s, though it ultimately resulted in the destruction of the Houses of Parliament). This is one theory of the origin of the Ishango Bone, one of the world’s oldest surviving mathematical artifacts (dating from before 18,000 BCE):
All of this is to say: if what we’re interested in is comparing the sizes of two sets, we don’t actually need to compute the size of each set and compare them; instead, we can look for bijections between the two sets.