2.4.1 Introduction

No one knows exactly when people first started counting, but a good guess might be when people started accumulating things. However, long before number systems were invented, two people might have determined whether they had the same number of goats and sheep as illustrated in Figure 2.20 by simply placing them in a one‐to‐one correspondence with each other.

Another person might have designated a stone for each goat, thus obtaining a one‐to‐one correspondence between the goats and a pile of stones. Today, we no longer use stones to enumerate things since we have symbolic stones in the form of 1, 2, …. To determine the number of goats, we simply “count,” 1, 2, … and envision the rocks R = {1, 2, 3, 4, 5} in our mind as illustrated in Figure 2.21.

Throughout the history of mathematics, the subject of infinity has been mostly taboo, more apt to be included in discussions on religion or philosophy. The Greek philosopher Aristotle (c. 384–322 BCE), was one of the first mathematicians to think seriously about the subject, said there were two kinds of infinity, the potential and actual. He said the natural numbers 1, 2, 3, … are potentially infinite since they can never be completed. The philosopher and theologian Thomas Aquinas (1225−1275) argued that with the exception of God, nothing is actual infinite.

In the seventeenth century, the Italian astronomer Galileo made an observation concerning the perfect squares 1, 4, 9, 16, 25, …. He said since they constitute a subset of the natural numbers, there should be “fewer” of them than the natural numbers, and Table 2.9 would seem to bear this out.

However, he also observed that when one lines up the perfect squares as in Table 2.10, it appears that both sets contain the same number of members.

His argument was that for every perfect square n², there is exactly one natural number n, and conversely for every natural number n, there is exactly one square n². Using this reasoning, he concluded terms like less than, equal, and greater than apply to the size of finite sets but not infinite sets.

2.4.1.1 Early Bouts with Infinity

To get an idea how difficult it is to think about infinity, the ancient Greek philosopher Zeno of Elea (fifth century BCE) argued that motion is an illusion since a person who wishes to travel a fixed distance must first travel half the distance, then half the remaining distance, and then half that remaining distance and so on. So how could a person travel an infinite number of distances in a finite amount of time? Surprisingly, the paradox was not satisfactorily resolved until the tools of calculus were rigorously developed in the nineteenth century. Today, we understand that an infinite number of objects can add ad infinitum and still yield a finite result, much like the one‐foot square in Figure 2.22, whose area is the union of an unending series of areas of smaller and smaller and smaller squares and rectangles, but yielding a total area of

The above discussion motivates the formal definitions related to Cantor's fundamental ideas.

2.4.2 Cardinality, Equivalence, Finite, and Infinite

We begin with several important definitions.

We now know there are two kinds of sets when it comes to size, finite and infinite. We know that some finite sets are larger, smaller, or equal in size to other sets. The cardinality of A = {a, b, c} is |A| = 3 and the cardinality of B = {a, b, c, d} is |B| = 4, and so we have |A| < |B|. But what about the cardinality of infinite sets, such as ℕ, ℤ, and ℚ? We know these sets have infinite cardinalities, but are the cardinalities the same, or is one cardinality larger than the others? And if that is so, exactly how many different cardinalities are there? Is there more than one infinity?

When it comes to comparing sizes of sets, finite or infinite, we have a good friend, and a friend the reader is no doubt familiar. It is the concept of a function, and although we do not formally introduce functions until the next chapter, the reader no doubt will have an adequate understanding of functions to understand the ideas presented here. We begin by introducing three important types of functions f : A → B that map a domain A into a set B; the one‐to‐one function, the onto function, and the one‐to‐one correspondence function.

The second type of function is onto function.

The third type of function we introduce is the one‐to‐one correspondence.

2.4.3 Major Result Comparing Sizes of Finite Sets

For finite sets A, B we know what is means when we say |A| < |B|, but this meaning breaks down for infinite sets when sets cannot be counted. However, the language of sets helps us overcome this difficulty. For finite sets, it is intuitively clear that |A| ≤ |B| when there is an injection (1–1) from A to B. We now use this motivation do define what it means by |A| ≤ |B| for infinite sets.

2.4.4 Countably Infinite Sets

We defined an infinite set as a set that is not finite. We now define a countably infinite (or denumerable) set.

Infinity can be tricky. If we add a new member to a finite set, we increase its cardinality by one, but things behave much differently for infinite sets. If we add “0” to the natural numbers ℕ = {1, 2, 3, …} getting ℕ ∪ {0}, do we increase the “size” of the set? The answer is no since we can relate the two sets with the one‐to‐one correspondence shown in Table 2.11.

Cantor was initially convinced that all infinite sets were countably infinite as suggested from |ℕ| = |ℤ| = |ℚ|. The next obvious question was what about the cardinality of the real numbers? What is |ℝ|? Cantor tried and tried to prove the real numbers are countably infinite by proving they could be put in a one‐to‐one correspondence with the natural numbers, but in the process discovered something amazing. What did he discover? Wait until the next section.