Skip to content Skip to navigation

OpenStax_CNX

You are here: Home » Content » Understanding Infinity, Cardinality, and the Continuum

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Understanding Infinity, Cardinality, and the Continuum

Module by: Glenn Habibi. E-mail the author

Summary: Understanding infinity can be difficult. In this module, the reader will see the formal mathematical approach to infinite sets, and the two different varieties of infinite cardinalities that result.

Understanding Infinity, Cardinality, and the Continuum

Introduction and Motivation

To begin with, it is important to understand that in formal mathematics, there are essentially two different “sizes” of infinite sets. We generally think of them as “countable” or “uncountable” (sometimes also referred to as “denumerable” and “not denumerable”). There is a key difference between these two kinds of sets. First we will discuss some examples of countable sets, and how one can tell whether or not a given set is countable. Then, we will introduce a famous argument credited mostly to Georg Cantor from which we learn that there are such things as infinite sets which are “bigger” than countable; hence the term uncountable. We will then deal with well-known sets which are of this second type.

Please note that this module does expect some basic knowledge of mathematical notation, in particular that of set theory. A detailed description of what this notation means is beyond the scope of this particular module.

Countable Sets and Cardinality

When discussing sets and their sizes, the notion of cardinality can be used. By definition, the cardinality of a given set A, sometimes written as |A|, can be easily defined when A is a finite set. In that specific case, it is simply the total number of elements that A has. So, for example, the set:

A = { 1, 2, 3, 4, 5 } A = { 1, 2, 3, 4, 5 } A = lbrace 1, 2, 3, 4, 5 rbrace
(1)

would be said to have cardinality 5, quite simply because A is a finite set, and it has 5 elements. The cardinality of the empty set, namely the set which by definition has no elements, is simply 0.

So for finite sets, the reader will note that we do not have any problems with cardinality, namely that there is a very easy, well-defined procedure for finding it out. Additionally, in the finite case, we would say that those sets are countable; a fairly intuitive term to use, since we literally can count all of the elements in a finite or empty set.

Matters become slightly more complex when considering infinite sets, however. One may ask a straightforward question “Can a set be infinite, but still be countable?”. As it turns out, the answer to this question is surprisingly “yes”. But first we must introduce a particular set:

N = {1,2,3,4,5,.....}{1,2,3,4,5,.....}lbrace 1, 2, 3, 4, 5, ..... rbrace

This set is the natural numbers, i.e. the counting numbers greater than zero. By inspection, one can see that it is infinite, since, for any natural number up to which one could count, there is definitely a well-defined “next” or “successor” natural number; the one that comes after it. As a result, this is where we begin our foray into infinite sets.

The natural numbers are straightforward for us, since we do have a systematic way of “writing them all down”, even though this process would take an infinitely long time. As a result of this discrete, systematic approach to them, we do consider ℕ to be a countable set as well. Usually, to clear up confusion with finite sets, we consider it to be a countably infinite set, which still fits under our umbrella of countability. So, even though the natural numbers are infinite, we can still list them systematically, and thus we still consider them countable.

Now, what about other sets that are infinite? Are they all countable? Are some of them countable? How could we tell the difference between the two? These are all extraordinarily good questions, which will be explored as we continue. First let us define a new term:

Definition: A bijection is a function which is one-to-one, and onto. In other words, it is a function from one set to another that maps each element from the first set to one and exactly one element of the second. It would not suffice if it mapped one element to more than one in the target set, and it would likewise not suffice if there were an element in the target set which was mapped to by more than one element in the domain. (A more precise definition of some of the above terms is beyond the scope of this module).

The bijection is a remarkable tool for cardinality matters, because it allows us to construct this definition of equality of cardinality:

Definition: The cardinality of two sets is said to be equal if and only if there exists a bijection from one set to the other.

So if one wants to show that two sets are of the same cardinality (be it infinite or finite), all he/she must do is show that there is a one-to-one and onto function which maps one of the sets to the other. In plain English, this means that two sets have the same cardinality if one can literally match up each object from one set to exactly one object from the other.

For example, suppose one wanted to show that:

A = {1, 2, 3, 4, 5}

and

B = {A, B, C, D, E}

have the same cardinality. All that is required is to exhibit one bijection from A to B. In this case, the function which maps 1 to A, 2 to B and so on would be precisely that function. Note that this is not the only such example.

Now, to return to the notion of countably infinite sets, one could say that some arbitrary set A, for instance, has the same cardinality as the natural numbers if a bijection exists between Aand the natural numbers. In other words, if I can take the elements of Aand “number” them sequentially in some systematic way, then that set would also have to be countably infinite. To see how this works, let us demonstrate on Z, the set of integers:

Z = {…., -3, -2, -1, 0, 1, 2, 3,...}

Clearly this set is infinite. But it could be pondered as to “how big” it actually is. In other words, is it of the same cardinality as N? Bigger? Let us proceed thusly:

  1. Consider a function f: Z -----> N, which for every integer in Z, assigns a counting number from N, uniquely
  2. The issue is that for each element of N, i.e. for every positive counting number, Z has two such elements, because it has positive and negative counting numbers.
  3. It turns out this isn't a problem. Consider N, and think of it is being breakable into two halves, namely even counting numbers and odd counting numbers.
  4. Proceed by claiming that f will map all of the odd numbers in N to negative integers, and all of the even numbers in N to positive integers.
  5. f being defined in this way clearly makes it a bijection, and thus we have found a one-to-one correspondence between the natural numbers and the integers.

By the above argument, it is clear that in terms of cardinality, the natural numbers and the integers are equivalent, i.e., they are both countably infinite, according to our definitions.

A Less Intuitive Example

Since we can clearly see that another infinite set like the integers is countable (i.e. it has the same cardinality as N), it stands to reason to ask whether or not Q, which is the set of all rational numbers is also countable. When first contemplating this question, it is not always easy to intuit what the result may be. Consider the following number line (Figure 1):

Figure 1
Figure 1 (graphics1.gif)
Figure 1: A number line

Note that it contains markings for integers. When considering them in this diagram form, it is easy to see, once again, that our belief about Z being countable is intuitively true. But consider all the rational numbers between these integers. There are infinitely many such numbers between any pair of adjacent integers, of which there are also infinitely many. But does that mean that Q should be bigger than Z?

Consider the following argument:

  1. Create a standard, X-Y plot (Figure 2).
  2. For simplicity, consider only the positive rational numbers (If this makes the argument unconvincing, then apply the same reasoning that mapped N to Z bijectively, it will apply analogously here).
  3. Take each point in Quadrant I of the plot with integer coordinates, and think of it as though the point (x, y) were simply the rational number xyxyx over y. So the point (1, 1) is simply the rational number 1, the point (3, 2) would be 32323 over 2, and so on. Note that points on the x-axis are ineligible as rational numbers in this form, since that would cause division by zero.
  4. Agree that every positive rational number would appear somewhere in this Quadrant (Thus we have all of Q covered).
  5. Trace the path shown in Figure 2, and “number” each point with a natural number, starting with the point (0, 1) being numbered “1”, the point (1, 1) being numbered “2” and so on.
  6. Clearly there are the same number of these “points” as there are natural numbers, since by proceeding in this fashion, we could enumerate all the rational numbers, and we wouldn't ever “run out of” natural numbers with which to number them.
  7. Conclude that the cardinality of Q must be the same as the cardinality of Z. They are both countably infinite.

Figure 2
Figure 2 (graphics2.gif)
Figure 2: The “snake”

Sometimes this particular argument is called the “snake” argument, as our counting function spans all the positive rational numbers by side-winding through them like how a snake would slither. In any case, it is clear that this method would “count” all of the positive rationals, thus making Q countable.

The observant reader is likely to note that some of the points in our “snake” argument actually are the same rational number. For instance, the point (1, 1) is the rational number 1, but so is (2, 2), (3, 3,) and so on. It turns out this does not create a problem for the argument, by the following reasoning:

  1. The rationals are certainly infinite, by sheer merit of the fact that it is so easy to construct any infinite sequence of rational numbers (for instance, 11,12,1311,12,13{1 over 1}, {1 over 2}, {1 over 3} ,.....)
  2. As a result, there are clearly as many rationals as natural numbers. The only thing that remained to be shown above is that there aren't somehow more rationals than natural numbers.
  3. Since the above argument covers that possibility, because the rationals can be systematically written down in a sequence just like the natural numbers, the bijection can clearly be constructed. The two sets are of the same cardinality.

To sum up, it doesn't matter that some rationals (all of them, in fact), will be counted more than once in this way; the only goal of this argument was to show that the rationals are not somehow “bigger” than the natural numbers.

So we may conclude that Q is indeed countably infinite, just like the natural numbers or the integers. This is a noteworthy fact, due to its counter-intuitive nature.

Uncountable Sets

The discussion so far on infinite sets has been confined to examples of such which are countably infinite. The reader should be able to see that for any set A, the following are equivalent:

  1. A is countably infinite
  2. A has a one-to-one correspondence (bijection) with N
  3. There exists a systematic way of “listing” all the elements of A

It is important for the reader to realize that not all infinite sets can fit into this classification. The discovery of this idea is primarily credited to Georg Cantor, for his famous diagonalization argument which follows:

  1. Suppose one had a list of all the decimal expansions of the numbers which are between '0' and '1'.
  2. For simplicity's sake, convert all of these decimal expressions into binary (that is, consisting only of the digits '0' and '1'. All numbers can still be expressed in this way, each place-value is a power of 2 as opposed to 10).
  3. There should be infinitely many items on this list, and each of them would be an infinite binary expansion (for numbers that would be finite, one may continue them with infinitely many 0s on the end). (Figure 3)
  4. It can be assumed that this infinite list of infinite binary expansions contains every possible binary expansion.
  5. Now consider only the digits along the diagonal, i.e. the first digit of the first number, the second digit of the second number, etc.
  6. Suppose one were to take each of those digits, and if it were a '0', replace it with a '1', if it were a '1', replace it with a '0'.
  7. Then create a “new” binary number, consisting of exactly these diagonal digits.
  8. By the way it was constructed, note how this new number cannot be one of the numbers on our list already. It can't be the first number on the list, since it has a different first digit. It cannot be the second number on the list, because it has a different second digit. In fact, in general, this new number cannot be the nth number on the list, since it differs in its nth binary digit.
  9. Thus, this new number is clearly not a number on our list.
  10. This contradicts the assumption that this list contains all binary expansions between 0 and 1.
  11. By this contradiction, the set of all real numbers between 0 and 1 is not countable.

Figure 3
Figure 3 (graphics3.png)
Figure 3: The Cantor Diagonalization Argument in a diagram.

Sets of this type are said to be uncountable, meaning they are in some sense “bigger” than the countably infinite sets. There is no way to assign an integer, or a natural number, or even a rational number to all of the real numbers between 0 and 1.

As the reader may have predicted, the set of all real numbers, commonly referred to as R is an uncountable set. In fact, any interval of R, i.e. any sets of the form:

A := { xxxϵ R | axbaxba <= x <= b}

(This is the set of all real numbers between a and b)

is also uncountable. The real numbers, as it turns out, is an extraordinarily special set, and this is one of the main reasons why. If one were to graph the real numbers on a line, any segment on that line contains the same cardinality of points as does the whole line itself. While this is true of dense sets (like Q) as well, the uncountability of R is ultimately responsible for some of its other properties which, though are beyond the scope of this module, are of utmost significance in terms of how mathematicians view the world.

Conclusion

Though infinity may be a very difficult thing to contemplate philosophically, the formal mathematical approach to the subject, as the reader may now see, is rich with content, and easy to grasp. Through the application of some straightforward logical reasoning, infinite cardinality can easily be broken down into the above two cases; of countable and uncountable sets. For more information on the significance of the differences between these two varieties of infinite sets, the field of real analysis offers an in-depth approach to the real numbers, uncountability, and why these ideas are so important.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks