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:

• and are said to be equivalent
• Empty set is unique since no other sets is equivalent to it
• Every singleton_[1] set is equivalent to every other singleton set.

^{[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 and turns out to be equivalent. This is counter-intuitive since the naturals are contained in the rationals, the key to this is a “right” definition.

Once we have the right definitions, we can prove some truly amazing results.

George Cantor

---

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.

One-to-one correspondence

---

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,

Finite and Infinite Cardinalities

---

The most basic set of finite cardinality is given by,

The finite cardinalities are the equivalence classes containing the empty set and the sets . For infinite cardinalities, the best prototype for such sets is the entire set .

It is traditional to denote the cardinality of sets having the same size as with the symbol , read as “aleph naught” (a Hebrew letter). Such sets are known as “countable”. Sets having cardinalities that are ridiculously huge are known as uncountable.

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.}

1. A Gentle Introduction to the Art of Mathematics by Joe Field

---

Thank you for reading ...