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

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.