Learning to Count
Let's return to kindergarten! Today we are going to learn how to count. Maybe you haven't question yourself enough about this seemingly trivial activity.
Hello, Hypers!
Do you know how to count? Let’s do a test!
Tennis tournaments run on a knockout basis. This means that after each match, the winner advances to the next round while the loser is eliminated. How many matches are played in a tennis tournament with N players enrolled?
Note: We are considering tournaments in the single modality in which the matches are between two players.
In this post, we’ll answer this question. But we’ll also explore an entire field of Mathematics called Combinatorics a.k.a the Math behind counting.
What exactly is counting?
We are so used to counting that this question seems quite stupid. But after thinking a bit about it, we realize we don’t have a clear definition for counting. It is the activity that allows us to discover how many items a set has, but what is the exact definition of this activity?
For example, if we have a bag of potatoes, we can count how many potatoes are in the bag. This way, we say we have ten potatoes in the bag. I could count them one by one, or in any other fashion. But, what is the mathematical definition of this process of counting?
We’ll need two mathematical abstractions to define what counting is. First of all, we need numbers. Specifically, natural numbers (1, 2, 3, …). These are the first numbers we learn, they are very familiar to us. We won’t say too much about them for now.
The other important concept could be more complex but it’s equally familiar to us: bijective relations. A bijective relation, also known as a one-to-one correspondence, is a mathematical relationship between two sets where each element in the first set is uniquely paired with exactly one element in the second set, and vice versa. This means that there's a perfect matching between the elements of both sets, with no repetitions or gaps.
For example, the following is a representation of a bijection between two sets A and B.
These are other relationships between two sets that are not bijections.
Mathematically speaking, counting is just finding a bijection between some set and a subset of natural numbers. To find how many elements are in set A, we create a bijection between this set and a subset of the natural numbers as shown in the following figure.
So, when we say that we have ten potatoes in our bag, that means that there is one bijection relationship between the set of potatoes in our bag and the subset of the first ten natural numbers.
If we can define a bijection between set A and a subset of the natural numbers, then we say that A is a countable set. Note that the set of natural numbers is a subset of itself, so we can have a countable infinite set, it just has to be as infinite as the set of natural numbers.
Note: In an upcoming post we’ll talk about the different infinites that we can find in Math.
For example, the set of prime numbers is infinite. However, we can assign a natural number to each prime number, so this set is still countable.
Maybe you think this counting concept is interesting but is not too practical. You’re right! Nobody counts creating bijections in their heads. Now that we know the basics, we can move to the cool stuff.
The Art of Counting
There is one cool property of bijections: transitivity. This means that if there is a bijection between set A and set B, and there is a bijection between set B and set C, then there is also a bijection between set A and set C.
This is the property that makes counting so easy. Now we don’t need a subset of natural numbers to count, we just need any known countable set. If we define a bijection between a set A and any countable set, then we prove that A is countable, and it has the same number of items as the countable set.
Let’s recall our problem! How many matches are played in a tennis tournament with N players enrolled?
It is tempting to think that in the first round, they play N/2 matches, in the second round N/4, in the third one N/8, and so on. This only works if N is a power of two, but in this problem, we don’t specify what N is. As it is referring to the number of players we know it is a natural number but nothing more. It doesn’t have to be a power of two.
You can think about the problem for a while and draw the possible scenarios and probably you’ll find the answer after some time. But I’m going to show you a shortcut!
Let’s find a clever bijection to count the number of matches. On one hand, we have the set of matches, we don’t know how many items are there. Now, we need to find another set that is easier to count such that we can define a bijection between this set and the set of matches.
Let’s note that after each match, one player loses. We can define the set L of players that lose a match in the tournament. As in each match there is exactly one loser, and a player can only lose once in a tennis tournament, we have a bijection between the set of matches and the set L.
Now we only need to know how many players are in the set L. But this is easy, all the players lose a match except the winner of the tournament! So, L has N - 1 items. Thus, the number of matches in a tennis tournament of N players is N - 1.
That was way easier!
Conclusions
Counting is about finding bijections between sets. As bijections are transitive, once we find a countable set, we can use it to find more countable sets. These bijections tell us how many items a set has. Following the definition of counting we talked about in this post, we can have countable sets that are infinite. They just need to be as infinite as the natural numbers.
But the most important take from this post is that counting is far from being a trivial activity. Knowing the number of items in a set is not always easy. Actually, there is an entire field in Math that studies this: Combinatorics.
If you’d like me to write more posts about Combinatorics and interesting counting problems tell me so by reacting or replying to this post. I hope you have enjoyed the issue of this week. Thank you very much for reading!
See you next Tuesday!
I thoroughly enjoyed your post. The break down of the concept flowed naturally.
On the "counting isn't trivial" front, my mind was fairly recently blown by the concept of the invention of "correspondence counting."
Felix Martin introduced this to me in "Money: the Unauthorized Biography", and I haven't really been able to stop thinking about this.