\(\newcommand{\versionNum}{$3.2$\ } \renewcommand{\tabcolsep}{2.4pt} \def\savedlnot{\lnot} \renewcommand{\arraystretch}{.63} \renewcommand{\arraystretch}{1} \renewcommand{\Naturals}{{\mathbb Z}^{\mbox{\tiny noneg}} } \renewcommand{\arraystretch}{.9} \renewcommand{\arraystretch}{.77} \newcommand{\hint}[1]{ } \newcommand{\inlinehint}[1]{ } \newcommand{\sageprompt}{ \texttt{sage$>$} } \newcommand{\tab}{} \newcommand{\blnk}{\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}} \newcommand{\suchthat}{\; \;} \newcommand{\divides}{\!\mid\!} \newcommand{\tdiv}{\; \mbox{div} \;} \newcommand{\restrict}[2]{#1 \,_{\,#2}} \newcommand{\lcm}[2]{\mbox{lcm} (#1, #2)} \renewcommand{\gcd}[2]{\mbox{gcd} (#1, #2)} \newcommand{\Naturals}{{\mathbb N}} \newcommand{\Integers}{{\mathbb Z}} \newcommand{\Znoneg}{{\mathbb Z}^{\mbox{\tiny noneg}}} \newcommand{\Zplus}{{\mathbb N}} \newcommand{\Enoneg}{{\mathbb E}^{\mbox{\tiny noneg}}} \newcommand{\Qnoneg}{{\mathbb Q}^{\mbox{\tiny noneg}}} \newcommand{\Rnoneg}{{\mathbb R}^{\mbox{\tiny noneg}}} \newcommand{\Rationals}{{\mathbb Q}} \newcommand{\Reals}{{\mathbb R}} \newcommand{\Complexes}{{\mathbb C}} \newcommand{\relQ}{\mbox{\textsf Q}} \newcommand{\relR}{\mbox{\textsf R}} \newcommand{\nrelR}{\mbox{$\not${\textsf R}}} \newcommand{\relS}{\mbox{\textsf S}} \newcommand{\relA}{\mbox{\textsf A}} \newcommand{\Dom}[1]{\mbox{Dom}(#1)} \newcommand{\Cod}[1]{\mbox{Cod}(#1)} \newcommand{\Rng}[1]{\mbox{Rng}(#1)} \DeclareMathOperator{\caret}{$\scriptstyle\wedge$} \renewcommand{\arraystretch}{.77} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section8.1Equivalent sets

We have seen several interesting examples of equivalence relations already, and in this section we will explore one more: we'll say two sets are equivalent if they have the same number of elements. Usually, an equivalence relation has the effect that it highlights one characteristic of the objects being studied, while ignoring all the others. Equivalence of sets brings the issue of size (a.k.a. cardinality) into sharp focus while, at the same time, it forgets all about the many other features of sets. Sets that are equivalent (under the relation we are discussing) are sometimes said to be equinumerous  1 .

A couple of examples may be in order.

  • If \(A = \{1, 2, 3\}\) and \(B = \{a, b, c\}\) then \(A\) and \(B\) are equivalent.

  • Since the empty set is unique — \(\emptyset\) is the only set having 0 elements — it follows that there are no other sets equivalent to it.

  • Every singleton set 2  is equivalent to every other singleton set.

Hopefully these examples are relatively self-evident. Unfortunately, that very self-evidence may tend to make you think that this notion of equivalence isn't all that interesting — nothing could be further from the truth! The notion of equivalence of sets becomes really interesting when we study infinite sets. Once we have the right definition in hand we will be able to prove some truly amazing results. For instance, the sets \(\Naturals\) and \(\Rationals\) turn out to be equivalent. Since the naturals are wholly contained in the rationals this is (to say the least) counter-intuitive! Coming up with the “right” definition for this concept is crucial.

We could make the following:

Definition8.1.1

(Well . . . not quite.) For all sets \(A\) and \(B\), we say \(A\) and \(B\) are equivalent, and write \(A \equiv B\) iff \(|A| = |B|\).

The problem with this definition is that it is circular. We're trying to come up with an equivalence relation so that the equivalence classes will represent the various cardinalities of sets (i.e. their sizes) and we define the relation in terms of cardinalities. We won't get anything new from this.

Georg Cantor was the first person to develop the modern notion of the equivalence of sets. His early work used the notion implicitly, but when he finally developed the concept of one-to-one correspondences in an explicit way he was able to prove some amazing facts. The phrase “one-to-one correspondence” has a fairly impressive ring to it, but one can discover what it means by just thinking carefully about what it means to count something.

Consider the solmization syllables used for the notes of the major scale in music; they form the set \(\{\mbox{do, re, mi, fa, so, la, ti} \}\). What are we doing when we count this set (and presumably come up with a total of 7 notes)? We first point at `do' while saying `one,' then point at `re' while saying `two,' et cetera. In a technical sense we are creating a one-to-one correspondence between the set containing the seven syllables and the special set \(\{1, 2, 3, 4, 5, 6, 7\}\). You should notice that this one-to-one correspondence is by no means unique. For instance we could have counted the syllables in reverse — a descending scale, or in some funny order — a little melody using each note once. The fact that there are seven syllables in the solmization of the major scale is equivalent to saying that there exists a one-to-one correspondence between the syllables and the special set \(\{1, 2, 3, 4, 5, 6, 7\}\). Saying “there exists” in this situation may seem a bit weak since in fact there are \(7! = 5040\) correspondences, but “there exists” is what we really want here. What exactly is a one-to-one correspondence? Well, we've actually seen such things before — a one-to-one correspondence is really just a bijective function between two sets. We're finally ready to write a definition that Georg Cantor would approve of.

Definition8.1.2

For all sets \(A\) and \(B\), we say \(A\) and \(B\) are equivalent, and write \(A \equiv B\) iff there exists a one-to-one (and onto) function \(f\), with \(\Dom{f} = A\) and \(\Rng{f} = B\).

Somewhat more succinctly, one can just say the sets are equivalent iff there is a bijection between them.

We are going to ask you to prove that the above definition defines an equivalence relation in the exercises for this section. In order to give you a bit of a jump start on that proof we'll outline what the proof that the relation is symmetric should look like.

To show that the relation is symmetric we must assume that \(A\) and \(B\) are sets with \(A \equiv B\) and show that this implies that \(B \equiv A\). According to the definition above this means that we'll need to locate a function (that is one-to-one) from \(B\) to \(A\). On the other hand, since it is given that \(A \equiv B\), the definition tells us that there actually is an injective function, \(f\), from \(A\) to \(B\). The inverse function \(f^{-1}\) would do exactly what we'd like (namely form a map from B to A) assuming that we can show that \(f^{-1}\) has the right properties. We need to know that \(f^{-1}\) is a function (remember that in general the inverse of a function is only a relation) and that it is one-to-one. That \(f^{-1}\) is a function is a consequence of the fact that \(f\) is one-to-one. That \(f^{-1}\) is one-to-one is a consequence of the fact that \(f\) is a function.

The above is just a sketch of a proof. In the exercise you'll need to fill in the rest of the details as well as provide similar arguments for reflexivity and transitivity.

For each possible finite cardinality \(k\), there are many, many sets having that cardinality, but there is one set that stands out as the most basic — the set of numbers from \(1\) to \(k\). For each cardinality \(k > 0\), we use the symbol \(\Naturals_k\) to indicate this set: \begin{equation*} \Naturals_k \; = \; \{1, 2, 3, \ldots , k\}. \end{equation*}

The finite cardinalities are the equivalence classes (under the relation of set equivalence) containing the empty set and the sets \(\Naturals_k\). Of course there are also infinite sets! The prototype for an infinite set would have to be the entire set \(\Naturals\). The long-standing tradition is to use the symbol \(\aleph_0\) 3  for the cardinality of sets having the same size as \(\Naturals\), alternatively, such sets are known as “countable.” One could make a pretty good argument that it is the finite sets that are actually countable! After all it would literally take forever to count the natural numbers! We have to presume that the people who instituted this terminology meant for “countable” to mean “countable, in principle” or “countable if you're willing to let me keep counting forever” or maybe “countable if you can keep counting faster and faster and are capable of ignoring the speed of light limitations on how fast your lips can move.” Worse yet, the term “countable” has come to be used for sets whose cardinalities are either finite or the size of the naturals. If we want to refer specifically to the infinite sort of countable set most mathematicians use the term denumerable (although this is not universal) or countably infinite. Finally, there are sets whose cardinalities are bigger than the naturals. In other words, there are sets such that no one-to-one correspondence with \(\Naturals\) is possible. We don't mean that people have looked for one-to-one correspondences between such sets and \(\Naturals\) and haven't been able to find them — we literally mean that it can't be done; and it is has been proved that it can't be done! Sets having cardinalities that are this ridiculously huge are known as uncountable.

Subsection8.1.1Exercises

  1. Name four sets in the equivalence class of \(\{1, 2, 3\}\).

  2. Prove that set equivalence is an equivalence relation.

  3. Construct a Venn diagram showing the relationships between the sets of sets which are finite, infinite, countable, denumerable and uncountable.

  4. Place the sets \(\Naturals\), \(\Reals\), \(\Rationals\), \(\Integers\), \(\Integers \times \Integers\), \(\Complexes\), \(\Naturals_{2007}\) and \(\emptyset\); somewhere on the Venn diagram above. (Note to students (and graders): there are no wrong answers to this question, the point is to see what your intuition about these sets says at this point.)