Theory of Computation

1.3   BIG AND SMALL INFINITE SETS; DIAGONALIZATION

Two broad distinctions of sets by size are finite vs. infinite. Intuitively, we can count the elements of a finite set and come up with a (natural) number at some distinct point in (future) time. No such possibility is open for infinite sets. Just as finite sets come in various sizes, a 5-element set, vs. a 0-element set, vs. a 2^3500000-element set, Cantor has taught us that infinite sets also come in various sizes. The technique he used to so demonstrate is of interest to us, as it applies to computability, and is the key topic of this section.

1.3.0.34 Definition. (Finite sets) A set A is finite iff it is either empty, or is in 1-1 correspondence with {x : x ≤ n}. We prefer to refer to this “normalized” finite set by the sloppy notation {0,..., n}.

In this case we say that “A has n + 1 elements”. If A = we say that “A has 0 elements”. If a set is not finite, then it is infinite.

1.3.0.35 Example. If A and B have n+1 elements, then A ~ B (cf. Exercise 1.8.31).

1.3.0.36 Theorem. If X ⊂ {0,..., n}, then there is no onto function f ...