Revision as of 05:55, 17 May 2013

Math Squad

↳ To Infinity and Beyond. Introduction

↳ Review of Set Theory

↳ Functions

↳ Countability

↳ Cardinality

↳ Hilbert's Grand Hotel

Countability

When we count the elements of a set, we usually list them as element one, two, three, etc and we carry on until all the elements have been listed. Essentially, we are creating a bijective mapping of a portion of the set of natural numbers to the elements of the set. If the set is such that the counting does not end, such as the set of natural numbers itself, then what we have on our hands is an infinite set.

Definition

(a) A set $ S $ is said to be denumerable (or countably infinite) if there exist a bijection of the set of natural numbers onto $ S $. (b) A set $ S $ is said to be countable if it is either finite or denumerable. (c) A set $ S $ is said to be uncountable if it is not countable.

So what the definition is telling us is that a set is countable if all its elements can be put in a one-to-one correspondence with the natural numbers (or a subset of the natural numbers for finite sets).

All finite sets are countable.

An infinite set $ A $ is countable is there is a one-to-one function whose domain is the set of natural numbers and whose range is $ A $.

Let us attempt a few exercises in detecting uncountable sets.

Even and Odd Numbers

Given that $ E $ is the infinite set of all even natural numbers, we have that

$ E := \{2n:n \in \mathbb{N} \} $

So we see that $ E $ is denumerable since the mapping of $ f: $ N → $ E $ defined by $ f(n) := 2n $ where $ n $ ∈ N, is a bijection of N onto $ E $.

Similarly, we could prove that the set $ O :=\{2n - 1 : n $ ∈ N} of odd numbers is denumerable.

The Set of All Integers

You can see one way of matching integers to whole numbers in figure one so that there is a one-to-one correspondence between them. This makes Z, the set of all integers, a countably infinite set.

Fig 1: One-to-one correspondence between the natural numbers and the integers

The Set of all Rational Numbers

Fig 2: Cantor's ordering of the rational numbers

Figure 2 shows Cantor's diagonal argument for the rationals being countabe. This is only an informal proof because the bijection is not defined precisely. His argument is essentially that the positive rational numbers can be placed in an array and counted in a ordered manner so that all of them are accounted for. Starting in the upper left corner and winding back and forth along each diagonal, a sequence is formed in which each element has a specific location. the duplicate elements in the sequence can be removed; these are shown in figure 2 as the ones that are crossed out. Similarly, the set of all negative rational numbers is also countable. We know that
$ \mathbb{Q} = \mathbb{Q}^- \cup \{0\} \cup \mathbb{Q}^+ $
Since the union of countable sets is countable, we conclude that the rationals form a countably infinite set. We will return to this method of ordering the rationals to solve Hilbert the Hilbert paradox of the Grand Hotel in a later section.

Another method to prove that the rationals are countable is to define the height of a rational number $ p/q $ as $ |p|+q $. Then we can list all the rational number as follows:

Height 1: 0/1
Height 2: -1/1, 0/2, 1/1
Height 3: -2/1, -1/2, 0/3, 1/2, 2/1
Height 4: -3/1, -2/2, -1/3, 0/4, 1/3, 2/2, 3/1
$ \vdots $

We see that each row is countable, in fact they are finite, and there are countably many rows. So we have just expressed the rationals as a countable union of countable sets. The result is yet another countable set. The above list contains many duplicates but a subset of a countable set is also countable so this is not an issue as we saw in the diagonal procedure.

The Set of Real Numbers

Conclusion

References

• R. G. Bartle, D. R. Sherbert, "Preliminaries" in "An Introduction to Real Analysis", Third Edition, John Wiley and Sons Inc. 2000 ch. 1, sect. 1.1, pp 16-18.

• R. G. Bartle, D. R. Sherbert, "The Real Numbers" in "An Introduction to Real Analysis", Third Edition, John Wiley and Sons Inc. 2000 ch. 2, sect. 2.5, pp 47.

• R. Kenney. MA 301. "An Introduction to Proof through Real Analysis", Lecture Notes. Faculty of the Department of Mathematics, Purdue University, Spring 2012.

• J. J. Wanko in Vol. 102, No. 7. "Mathematics Teacher" March 2009.

Questions and comments

If you have any questions, comments, etc. please post them below:

• Comment / question 1

Back to Math Squad page