Computability Theory

A2 Countability

Often we want to know the size of a set. On the one hand, there are the finite sets. On

the other hand, there are the infinite sets. The infinite sets are bigger than the finite

sets.

There is more to it, of course. There is the zero-element set, the empty set. There

are the one-element sets, the singletons (like {8}). There are the two-element sets, the

doubletons (like {0, 8}). And so forth and so on. Finite sets come in all sizes.

Something similar happens with the infinite sets. All the infinite sets are big, but

some are bigger than others. We want to make sense of this idea, by extending some

concepts (that are familiar in the finite case) to infinite sets.

For sets A and B, say that A is the same size as B (written A ≈ B) if there is ...