Countable Infinity
One of the more obvious features of the three number systems N, Z,
and Q that were introduced in the previous chapter is that each contains
infinitely many elements. Before defining our next (and last) number system,
R, we want to take a closer look at how one can handle 'infinity' in a
mathematically precise way. We would like to be able to answer questions like:
- Are there more even than odd numbers ?
- Are there more even numbers than integers ?
- Are there more rational numbers than negative integers ?
While most people would probably agree that there are just as many even than odd
numbers, it might be surprising that the answer to the last two questions is no
as well. All of the sets mentioned have the same number - albeit infinite - of
elements. The person who first established a rigorous 'theory of the infinite'
was G. Cantor.
The basic idea when trying to count infinitely large (or otherwise difficult
to count) sets can roughly be described as follows:
- Suppose you are standing in an empty classroom, with a lot of students
waiting to get in. How could you know whether there are enough chairs for
everyone? You can not count the students, because they walk around too much.
So, you simply let in the students, one by one, and take a seat. If all the
seats are taken, and no students are left standing, then there was the same
number of students as chairs.
This simple idea of matching two sets element by element is the basis for
comparing two sets of any size, finite or infinite. Since 'matching elements
from one set with those in another set ' seems related to the concept of a
function, we have arrived at the following definition:
Definition: Cardinality
- Let A and B be two sets. We say that A and B
have the same cardinality if there is a bijection f from A
to B. We write card(A) = card(B).
- If there exists a function f from A to B that is
injective (i.e. one-to-one) we say that card(A)
card(B).
- If there exists a function f from A to B that is
surjective (i.e. onto) we say that card(A)
card(B).
Please explain carefully what this definition has to do with the above idea of
counting students and chairs?
Examples:
-
We can now answer questions similar to the ones posed at the beginning:
- Let E be the set of all even integers, O be the set of
odd integers. Then card(E) = card(O). What is the
bijection ?
- Let E be the set of even integers, Z be the set of all
integers. Again, card(E) = card(Z). Can you find
the bijection ?
- Let N be the set of natural numbers, Z be the set of
all integers. Which set, if any, has the bigger cardinality ?
Definition: Countable and Uncountable
- If a set A has the same cardinality as N (the natural
numbers), then we say that A is countable. In other words, a
set is countable if there is a bijection from that set to N.
- An alternate way to define countable is: if there is a way to
enumerate the elements of a set, then the set has the same cardinality
as N and is called countable.
- A set that is infinite and not countable is called uncountable.
The second part of this definition is actually just rephrasing of what it means
to have a bijection from N to a set A:
- If a set A is countable, there is a bijection f from N
to A. Therefore, the elements f(1), f(2), f(3), ... are all in
A. But we can easily enumerate them, by putting them in the following
order: f(1) is the first element in A, f(2) is the
second element in A, f(3) is the third one, and so on...
- If a set A can be enumerated, then there is a first element, a
second element, a third element, and so on. Then the function that assigns
to each element of A its position in the enumeration process is a
bijection between A and N and thus A is countable by
definition.
By the above examples, the set of even integers, odd integers, all positive and
negative integers are all countable.
Note that there is a difference between finite and countable, but we will
often use the word countable to actually mean countable or finite (even though
it is not proper). However, here is a nice result that distinguishes the finite
from the infinite sets:
Theorem: Dedekind's Theorem
- A set S is infinite if and only if there exists a proper subset
A of S which has the same cardinality as S.
Examples:
-
Use Dedekind's Theorem to show that the set of integers Z and the
interval of real numbers between 0 and 2, [0, 2], are both infinite (which
is of course not surprising).
The surprising fact when dealing with countably infinite sets is that when
combining two countable sets one gets a new set that contains no more elements
than each of the previous sets. The next result will illustrate that.
Proposition: Combining Countable Sets
- Every subset of a countable set is again countable (or finite).
- The set of all ordered pairs of positive integers is countable.
- The countable union of countable sets is countable
- The finite cross product of countable sets is countable.
Think about these propositions carefully. It seems to be contrary to ones
beliefs. To see some rather striking examples for the above propositions,
consider the following:
Examples:
-
The set of all rational numbers is countable.
- The collection of all polynomials with integer coefficients is
countable. To prove this, follow these steps:
-
Show that all polynomials of a fixed degree n (with integer
coefficients) are countable by using the above result on finite cross
products.
-
Show that all polynomials (with integer coefficients) are countable by
writing that set as a countable union of countable sets.
|
