We’ve seen several examples of equivalence relations already; in this section, we will explore one more: the equivalence of two sets if they have the same number of elements.
Equivalence relation has this ability to highlight important properties or characteristic of the objects being studied while ignoring unimportant ones. In this section, we will focus on the equivalence of sets that concerns with size, referred to as cardinality in mathematics, while forgetting all the other features of sets.
Sets that are equivalent (under the size feature) are sometimes said to be equinumerous.
Example:
[1] a singleton is a set with only one element
But you may ask: “This notion of equivalence isn’t all that interesting!!”. However, the notion of equivalence of sets becomes interesting when we are dealing with infinite sets.
To give you a taste of its importance, we will see that the set
Once we have the right definitions, we can prove some truly amazing results.
George Cantor was the first person to develop the modern notion of the equivalence of sets. When he developed the concept of one-to-one correspondences in an explicit way he was able to prove some amazing facts.
When you count the number of notes of the major scale in the music in this set,
We are in technical sense actually creating a one-to-one correspondence between the syllable sets and the special set,
Note that this correspondence is not unique because I could count in reverse or add some melody using each note once.
Another way of saying this is that there exists a one-to-one correspondence between the syllables and the special set.
In fact, there is a 7!=5040 different possible correspondence, but what we really want is the idea of “there exists”.
What exactly is a one-to-one correspondence then?
We have encountered a similar concept before – a one-to-one correspondence is really just a bijective function between two sets. One can say that the sets are equivalent iff there is a bijection between them.
We’re finally ready to introduce a definition George Cantor would approve of,
The most basic set of finite cardinality is given by,
It is traditional to denote the cardinality of sets having the same size as
Interestingly, it is actually the infinite sets that are countable. By countable, we mean “countable, in principle” or “countable if you’re willing to let me keep counting forever”. Here’s what makes it even more confusing – the term “countable” has come to be used for sets whose cardinalities are either finite or the size of the naturals.
To refer to an infinite sort of countable set most mathematicians us the term denumerable or countably infinite. Then there are sets whose cardinalities are bigger than the naturals – sets such that no one-to-one correspondence with N is possible.
What we mean when we say that there is no one-to-one correspondence is not manually trying to find the correspondence but that a one-to-one correspondence with the naturals can’t be done. What’s amazing is that we can prove that this can’t be done!
Disclaimer: this is a summary of section 8.1 from the book A Gentle Introduction to the Art of Mathematics: by Joe Fields, the content apart from rephrasing is identical, most of the equations are screenshots of the book and the same examples are treated.
Thank you for reading ...
