Associated Topics || Dr. Math Home || Search Dr. Math

### Countable and Uncountable Infinities

```Date: 08/13/2009 at 03:33:36
From: Emir
Subject: Countable and Uncountable Infinities

Could you please elaborate the terms 'countable' and 'uncountable'
infinity?

Are uncountable infinities greater than countable? How does the
relation 'be greater of' work with such 'numbers'?

As an example of uncountable infinities, we could take the cardinality
of the continuum, but could you give me an example of a countable
infinity? Is the number of different positive integers, aleph-null a
countable inf.?

Also, e.g. in calculus, when we write infinity as the answer to, let's
say, [ lim(1/x) ; when x->0 ], what kind of infinity are we taking
into consideration?  Is that a countable or uncountable one? What's
the 'name' of such infinity?

I'm looking for some theoretical concepts to explain my questions.

```

```

Date: 08/13/2009 at 05:06:46
From: Doctor Jacques
Subject: Re: Countable and Uncountable Infinities

Hi Emir,

The word "infinity" corresponds to a concept that can have different
meanings depending on the context.  It is best to speak of countable
and uncountable (infinite) sets.

These concepts are related to the concepts of cardinality and
cardinal numbers.  The idea is to extend to infinite sets the notion
of "having the same size".

For finite sets, we say that two sets have the same size if they
contain the same number of elements.  This is obviously an
equivalence relation on the class of all finite sets: the equivalence
classes are:

the empty set
the sets of 1 element (singletons)
the sets of 2 elements
....

We could also put all the infinite sets in another class.  However,
as Cantor discovered, we can do a little more.

If we want to know if there are the same number of chairs and
students in a lecture room, we could count the students and chairs
separately, but we could also tell everybody to sit down: if there
are no empty chairs and nobody is left standing, we know that the
two sets have the same number of elements, without needing to count
these elements separately.

The advantage of that method is that we can extend it to infinite
sets. If A and B are two sets (finite or infinite), we say that A
and B are equipotent (or equipollent) if there is a bijection (a
one-to-one and onto function) between the two sets.  In that case, we
also say that the sets have the same cardinality, and we write:

card (A) = card (B)

or, more concisely,

#A = #B

Now, the identity function is a bijection, the inverse of a bijection
is a bijection, and the composition of two bijections is a bijection:
this shows that equipotence is an equivalence relation on the class
of all sets.  The equivalence classes are called cardinal numbers:
they consist of classes of sets equipotent to each other.  In
particular, for finite sets, we get the equivalence classes mentioned
above, corresponding to the natural numbers.  For that reason, the
natural numbers are sometimes called "finite cardinal numbers".

For example, we can think of "2" as meaning "the class of all sets of
2 elements", or, more correctly, "the class of all sets S such that
there exists a bijection for {a,b} to S".

The sets in the equivalence class of N (the natural numbers) are
called countable.  (Some authors also call the finite sets countable,
and use "countably infinite" or "denumerable" for the equivalence
class of N).

By definition, an infinite set S is countable if there is a bijection
between N and S.  This means that you can list all the elements of S
in sequential fashion: if you write f(n) for the nth element of the
list, f is the desired bijection from N to S.

Countable sets include:

N (the natural numbers) (by definition)
Z (the integers)
Q (the rational numbers)
The algebraic numbers
The set of finite words over a finite alphabet.

That last class is of particular interest, because it often gives a
practical way to prove that a set is countable.  If you can represent
all the elements of a set by finite strings over a finite alphabet,
you can arrange those strings as follows:

the empty string
the strings of 1 letter
the strings of 2 letters
....

and, within each class, you can arrange the strings in dictionary
order; note that some classes may be empty, we do not require that
every finite string correspond to an element of the set.  For
example, using that technique, you can easily prove that Q is
countable, because each rational number is a fraction with integer
terms, like -123456/789, and this can be written as a finite string
over the 12-letter alphabet {0,1,...,9,'-','/').

The cardinal number of N (the class of countable sets) is denoted by
aleph_0.

As the classical "diagonal" argument of Cantor shows, not every
infinite set is countable; in particular, the set R of real numbers
is not countable, or "uncountable".

Up to now, we have defined an equivalence relation between sets, but
this leaves open the question of comparing sets that are not
equipotent; as you put it, can we define a relation "greater than"
on cardinal numbers?

It turns out that this is indeed possible.  We say that the set A is
"smaller than or equal to" the set B if A is equipotent to a subset
of B; this agrees with intuition.  In that case, we write:

#A <= #B

This also means that there is an injective (one-to-one) function from
A to B.

This new relation is compatible with the previous equivalence: if
#A <= #B and #B = #C, then #A <= #C.

Beware that this is not "obvious", because we give a particular
meaning to the symbols '<=' and '='.  This should be proved from the
definition of these relations.  In this case, we have, by hypothesis,
two functions:

f : A -> B
g : B -> C

where g is a bijection and f is injective.  f is a bijection from A
to a subset B' of B, and (g o f) (the composite of f and g) is a
bijection between A and g(B'), a subset of C.  By definition, this
means that #A <= #C.

It would be nice if the relation "<=" was an order relation.  It is
easy to see that it is reflexive and transitive, and, in fact, it is
also antisymmetric, although this is far less obvious.  What we claim
here is that, if:

#A <= #B
#B <= #A

then

#A = #B

This is know as the Schroeder-Bernstein Theorem:

Schröder-Bernstein Theorem from MathWorld--A Wolfram Web Resource
http://mathworld.wolfram.com/Schroeder-BernsteinTheorem.html

As I said, this is far from obvious.  What the theorem states is
that, if there are injective functions:

f : A -> B
g : B -> A

then there is a bijective function:

h : A -> B

(write back if you would like a proof).

For example, this can be used to show that the closed interval
A = [0,1] is equipotent to the half-open interval [0,1), although a
bijection h : A -> B is not obvious (well, it is not very hard to
find...).

Another question is whether this relation "<=" is a total order.
Given two sets A and B, is it always true that at least one of the
relations #A <= #B or #B <= #A holds, i.e., are any two sets
"comparable"?  It turns out that the answer to this question requires
a special axiom of set theory, namely the axiom of choice:

Wikipedia: Axiom of Choice
http://en.wikipedia.org/wiki/Axiom_of_choice

This axiom is independent of the other axioms of set theory.  It is
possible to develop a (rather dull) set theory without the axiom of
choice.  In such a theory, you could not assume that any two sets are
comparable.

Regarding the use of "infinity" in the context of limits, this is a
completely different concept.  It is not related to the sizes of
sets, but rather to the natural order of the integer, rational, or
real numbers.  In fact, you could (although it would probably not be
very useful) define a similar concept with any infinite set on which
you can define a total order.  If S is an infinite set with an order
relation '<=' such that any two elements of S are comparable with
respect to '<=' (such a relation is called a total order), you can
say that a sequence of elements u[n] of S tends to infinity if, for
every element m of S, there is a natural number N (depending on m),
such that:

n >= N  implies u[n] >= m

As I pointed out, this does not depend on whether S is countable or
not: you can have sequence tending to infinity in the natural
numbers (a countable set) or in the real numbers (an uncountable
set) : this only depends on S being infinite and totally ordered.

Please feel free to write back if you want to discuss this further.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Logic

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search