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 23500000-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. Definition. (Finite sets) A set A is finite iff it is either empty, or is in 1-1 correspondence with {x images images : xn}. 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 = images we say that “A has 0 elements”. If a set is not finite, then it is infinite. images Example. If A and B have n+1 elements, then A ~ B (cf. Exercise 1.8.31). Theorem. If X ⊂ {0,..., n}, then there is no onto function f ...

Get Theory of Computation now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.