Effective computability, decidability and enumerability

In Chapter 2, Smith covers familiar ground. So this post will be short. Here is a quick summary, section by section.

Section 1 reviews terminology pertaining to functions, namely the notions of domain and range, as well as special cases of functions, namely injective (or one-to-one) functions, surjective (or onto) functions and bijective functions (or one-to-one correspondences).

Section 2 defines effective computation. A function is effectively computable if there exists a mechanical procedure (or algorithm) to compute the value of the function for every element in its domain.

A property is effectively decidable if there exists a mechanical procedure (or algorithm) that, given any element, will determine whether or not the element has the property. Similarly, an n-ary relation is effectively decidable if there exists a mechanical procedure (or algorithm) that, given any n-tuple, will determine whether or not the relation holds among the n elements of the tuple.

To get a sense of what an algorithm is (since it is not a concept that can be defined mathematically), Smith briefly discusses the Church-Turing thesis, which defines algorithms as Turing machines.

Section 3 defines enumerable sets. A set S is enumerable if either S is empty or there exists a surjective function from the set of natural numbers ℕ (including zero) to S. Equivalently, the elements of an enumerable set can be listed (or enumerated) in some order, as in: element number 0, element number 1, element number 2, etc., in such a way that each element in the set is indexed by at least one integer.

Clearly, ℕ is enumerable (using the identity function, which is bijective). Similarly, any subset of ℕ is enumerable. For example, the set E of even natural numbers is enumerable, using the function f₁: ℕ → E with f₁(n) = 2n. As another example, the finite set S = {1,2,3} is enumerable, using the function f₂: ℕ → S with f₂(0) = 1, f₂(1) = 2, f₂(2) = 3, f₂(3) = 3, f₂(4) = 3, etc. Note that the function does not have to be injective (that is, repetitions are allowed in the enumeration).

Then Smith uses Cantor's classic diagonalization proof technique to prove that the following sets are indenumerable, that is, NOT enumerable:

• the set of infinitely-long bit strings
• the set of real numbers between 0 and 1
• the set of subsets of ℕ
• the set of functions from ℕ → {0,1}

Section 4 defines effective enumerability. A set S is effectively enumerable if either S is empty or there exists an effectively computable surjective function from the set of natural numbers ℕ (including zero) to S.

So, according to this taxonomy, a set can be:

1. effectively enumerable (e.g., the empty set, all finite sets, ℕ), or
2. enumerable but not effectively so (no example yet), or
3. not enumerable (e.g., ℝ).

Section 5 concludes the chapter by going over the well-known enumeration of the set of pairs of natural numbers by traversing the 2D table of pairs in a zigzag pattern along the anti-diagonals, thereby proving that ℕ² is effectively enumerable.