This post will be the first in a series of post regarding Countability and Cardinality of Infinite Sets. I do not intend to make this post too mathematically formal.
Along the end of the 19th century, mathematicians struggled with the concept of infinity. They had trouble figuring out its exact nature. Was it just another number, but extremely large; or was it something else entirely? As we will find out later on, it is more of the latter than the former.
The traditional way that mathematics gets done is by one mathematician modifying and expanding on the work of others who came before. This model, however does not seem to apply to Georg Cantor (1845-1918), at least with regard to his work on the theory of infinite sets. One wouldn’t be exaggerating if he said that Cantor single-handedly developed the foundations of this theory. The neat thing about Cantor’s work is that it is very simple and easy to understand. On studying this theory, one begins to appreciate the fact that perspective makes all the difference when it comes to solving a problem. If one finds the right way (whatever that means) to look at the problem, he is half-way there. Cantor’s perspective was (and still is) beautiful, and very intuitive. What once eluded even the best minds is now within the reach of any lay-man. This feat is worthy of appreciation.
We begin the study of Cantor’s work, with the notion of something called Cardinality of Sets.
Very simply speaking, Cardinality of a set is a measure of the size of the set. For a finite set (a set having only a finite number of elements), it is pretty straight-forward. The cardinality of the set is 4. All we need to do is attach a natural number to each set. Although this seems to be a clumsy way of looking at it, the notion of attachment or correspondence is what makes our job a lot easier when dealing with cardinalities of infinite sets.
How do we define the Cardinalities of Infinite Sets, then? Well, as you may have noticed, this is the title of the post, and this is what we will be focusing on in this series of posts.
What Cantor had in mind was to see if he could extend the notion of order (idea of something being bigger or smaller than something) of the cardinality of finite sets to cardinality of infinite sets. This means that he wanted to see if some infinities were bigger/larger than the others. This is a valid concern too. Normally, it is very unclear whether the cardinality of is the same as the cardinality of the closed interval . To a normal person, it seems that the open interval is smaller than . We’ll see if this is true.
The Larger Set: Defining Order in Cardinality
The set of planets in the solar system (its cardinality being 8) is definitely larger than the set of basketball players in a starting line-up of a team (its cardinality being 5). As far as finite sets are concerned, the order of natural numbers is sufficient enough to define order in cardinality. Since , the set of planets in the solar system is larger than the set of basketball players in a starting line-up of a team. But this method doesn’t seem to work for infinite sets. So, we need to change few things to our approach so that it will work for infinite sets and along with that, should still hold true for finite sets (like a universal law, or something of that sort).
As I mentioned earlier, the notion of correspondence seems to be the key. When we say that the set of planets in the solar system is larger than the set of basketball players in a starting line-up of a team, what we do is, we try to put the sets into some kind of 1 to 1 correspondence with each other. From now on, it should be noted the set of planets is larger than the set of players because, if the planets were removed from the orbit and replaced by the players, then there would still be 3 empty spots in the solar system, , not just because . In other words, when the players were “assigned” to the planets, some of the planets had no partners. But if we consider the set of Ivy league colleges (there are eight of them) instead of the basketball players, then the correspondence between each Ivy league college and the planets would have no unpaired member (or, there would be no “empty spots”). This correspondence is said to be 1-1 and onto (or a bijection).
The correspondence could be something like:
As you can see, this is a perfect (and onto) correspondence and thus we say that these two sets have the same cardinality. So, we have a formal definition with us
Definition Two sets and have the same cardinality if there exists that is and onto. In this case, we write
Extending the Definition to Infinite Sets
Now that we have defined order and equivalence in cardinality of sets, we will see how this method works for infinite sets too.
Consider the sets (the set of natural numbers) and (the set of even numbers). Which one should be the “larger” set?
On first glance (and many glances after that, if you have no idea about what we are discussing now!) it seems that cardinality of is greater than that of and that seems logical too. After all,
However, if we really think about it, we will come to realize that they have the same cardinality. Strange?
For us to prove that , all we nee to do is define a suitable correspondence. A defined correspondence is often called a function. Do note that the function that we desire should be a bijection (1 to 1 and onto).
Before moving on any further, I’d encourage the reader to try and define, by himself/herself, such a function (mapping) that is one to one and onto.
After some thinking, the reader should have figured it out that the function is defined by .
From the definition of equivalence, it thus follows that . This is something that is very odd to digest, especially to those who are to new to this field of study. But I read this on the internet that helped me when I was just learning all these.
It is certainly true that is a proper subset of , and for this reason, it may seem logical to say that E is a “smaller” set than N. This is one way to look at it, but it represents a point of view that is heavily biased from an over exposure to finite sets.
The definition is quite specific, and according to it, and are equivalent (they have the same cardinality.
Note: Some good exercises would be to try and show that or to show that (where be the set of odd numbers)
While this is all neat and pretty straight-forward, one often wonders what good does it do to us? What use is showing the equivalence between the cardinalities of two sets? What do we get out of knowing if two sets have the same “size” or not?
Well, this is where the concept of Countability comes in.
Countability of Sets
Mathematics is believed to have evolved from counting. Early cattle rearers somehow learnt how to count their cattle even though they did not know any numbers. Their method of counting heavily relied on the concept of 1-1 correspondence, just like the one we discussed earlier (but a little less advanced).
Say that the cattle rearer left home with 20 cows to graze in the grasslands. He had to make sure that all the cows returned back home, or else he would be at a loss. How did he do that? Well, he used a very simple trick. He put up 20 wooden posts, one for each cow to be tied to. At the end of the day, he would tie each cow back to its post. If any of the posts were empty, this would mean that some of the cows were missing. There did not exist a bijection (few post did not map to a cow at all) and hence the two sets have different cardinality. Obviously, the rearer did not think of the situation in terms of cardinality or bijections, but essentially they are the same thing.
Cantor realized that when it came to the notions of infinity, he was in no better position than the early cattle rearers. We humans seemed to struggle with counting infinity, just as the cattle rearer struggled with counting the 1s,2s and 3s; . So Cantor thought that it was best if he adopted the principle of one-one correspondence to understand such infinite collections. And it definitely paid off.
All Cantor needed to do was to figure out the exact meaning of a countable set that is powerful enough for finite as well as infinite collections. We will attempt to do the same.
If we think about it, it makes perfect sense to say that a set (or a collection) is countable if it is possible to look at any member of the collection and say that this is the 3 element, or this is the 227 element (or generally speaking, the n element), that it is possible to count the elements. Or, in other words, if it is possible to assign a number (or a natural number, to be more precise) to each and every element of the set.
So, we formally define a countable set as follows:
Definition A set is countable iff
So naturally, an infinite set that is not countable is called an uncountable set. We will see in later posts what it truly means for a set to be uncountable, but for now, know this that a set is uncountable if no bijective mapping is possible between the set and .
From our definition, it follows that the set of even numbers is countable. From the exercises suggested above, the reader should be able to deduce that as well as (set of odd numbers) are both countable. We will deal with uncountable set in the next post as it requires a little more elaborating , but for now, I would suggest the readers to think if all infinite sets are countable or not. Given some infinite sets such as or , it might seem as though, with some amount of ingenuity, we should be able to fit all the elements of our set into a single list (if it is possible to enlist all the elements of the set, then it should definitely be countable since the bijection would then be pretty straight-forward). After all, this list is infinitely long so there ought to be plenty of room. This is something to think about.
I would like to pause here for now. We will continue our discussion in the future posts.
PS: I would really value constructive feedbacks on this post. Please do comment in the comment section below.