# 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)=2n 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 2n, ..., 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.