O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 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.

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 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

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required