# Countable Sets

The cardinality of a set is a measure of the "number of elements of the set".

A has the same cardinality as B iff there is a one-to-one correspondence between A and B.
(A one-to-one and onto function f from A to B)

A countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers.

```A set S is countable if there exists an injective function
f: S ---> N
from S to the natural numbers {0,1,2,3,4,5, ...}
```

## Theorem

Every subset of a countable set is countable. In particular, every infinite subset of a countably infinite set is countably infinite.

The union of countably many countable sets is countable.

Any subset of a countable set is countable.

The Cartesian product of two countable sets A and B is countable.

If A is a countable set, and B is an uncountable set, then the most we can say about (A intersect B) is that it is

The intersection of two countable sets is countable.

The intersection of a countable and an uncountable set is countable.