# infinite

Recall that two sets are equivalent if they can be placed in one-to-one correspondence (so that each element of the first set corresponds to exactly one of the second). For finite sets this means they have the same number of elements.

An **infinite set** is a set which is equivalent
to a proper subset of itself. For example, the set of
integers is equivalent to the set of even integers--a
proper subset (to see this, just note f(*n*)=2*n*
is a one-to-one function from the integers to the even
integers).

This definition has some amusing consequences. For
example, suppose we had a hotel with an infinite number of
rooms numbered 1, 2, 3, 4, ..., and no vacancy (every room
is filled). We still have room for another person! All we
need to do is to have each person move over one room (1
goes to 2, 2 to 3, ..., *n* to *n*+1...). In
fact, even if it is full, it has room for as many folks as
are already in it (just send 1 to 2, 2 to 4, 3 to 6, ... ,
*n* to 2*n*, ..., this leaves 1, 3, 5, ...
empty). The moral is that "the number of" elements in an
infinite set (its cardinality) does not
behave like it does for a finite set.

Infinite sets are divided into two types: those which
are equivalent to a subset of the
integers (called **countable**) and those which are not (called
**uncountable**). The primes, composites, and positive
integers are clearly countable. But so are the rational
numbers, the set of polynomials with integer coefficients,
and hence the algebraic numbers. Uncountable sets include
the real and complex numbers, the irrational numbers, the
transcendental numbers, and the power set of any countably
infinite set.