A **countable set** is an infinite set that has a bijection with the natural numbers. Each natural number can be associated with an element of a countable set. Thus, any element in the set can be "reached" simply by counting long enough.

## Subsets, Supersets, Unions, and Intersections

A subset of a countable set is either finite or countable. A superset is not necessarily either finite or countable.

The intersection of a countable set and a finite set is at most finite. The intersection of two countable sets may be empty, finite, or countable.

The union of a countable set and another countable set or finite set is countable.

## Examples of Countable Sets

### Natural Numbers

The natural numbers are, by definition, a countable set, as each natural number corresponds with itself.

### Integers

Integers are countable. They can be counted in the following manner: (1,0) (2,1) (3,-1) (4,2) (5,-2).... any integer can be reached using this bijection.

### Rational numbers

The rational numbers, too, are countable. Each rational number, except zero is uniquely associated with an ordered pair of coprime integers. One way to order the rational numbers is to order them in increasing order of the absolute value of the sum of their numerator and denominator, skipping any pairs of numerators and denominators that are not coprime. e.g. (1,0) (2,1,1), (3,-1,1) (4,1,2) (5,-1,2) (6,2,1) (7,-2,1) (8,1,3) (9,-1,3) (10,3,1) (11,-3,1)...

### Algebraic numbers

Algebraic numbers are countable. Each algebraic number is a zero of a polynomial with integer coefficients, and each of these polynomials can be associated with a unique, finite string of coprime integers.The polynomials can be ordered by the sum of the sum of the absolute value of the coefficients and the degree of the polynomial. For example, they can be ordered like this: (1,0) (2,0,1) (3,0,-1) (4,0,0,1) (5,0,0,-1) (6,1,1) (7,1,-1) (8,-1,1)...Since polynomials have at most a finite number of zeros, the algebraic numbers are countable.

## Uncountable Sets

Not all sets are countable. The set of real numbers are uncountable, as shown by Cantor's Diagonal Theorem.