Let f be an enumeration function of an enumerable set S. For each of the sets below,

Question

Let f be an enumeration function of an enumerable set S. For each of the sets below,

state whether it is enumerable or not. If it is, give a function that enumerates it and prove

that this function you give is indeed an enumeration of the set. If it is not enumerable,

prove why it is not enumerable or give a counterexample.

(a) The powerset of S, P(S).

(b) Set S \ T where T is an arbitrary set

Answer 1

(a) P(S) is not enumerable by the diagonal argument as follows.

Let f(n) be a function that enumerates S.

Assume that there is an enumeration function F(n) for P(S), and we will derive a contradiction.

Construct a subset S0 of S by specifying which elements of S belong to S0:

For each natural number i, f(i) ∈ S0 iff f(i) ∉ F(i).

For every n, F(n) ≠ S0 because F(n) and S0 disagree on whether f(n) belongs there.

Failure to include S0 contradicts the assumption that F enumerates P(S).

(b) If your definition of "enumerable" does not include finite sets then

S \ T might not be enumerable because it might be finite.

So let me just prove that S \ T is enumerable if it is infinite.

Let f(n) be an enumeration function for S.

We define an enumeration function g(n) for S \ T by induction.

Assume that g(i) has been defined for all natural numbers i < n.

Let k be the smallest integer satisfying:

- f(k) ∉ T, and

- f(k) ∉ {g(0), g(1), ..., g(n-1)}.

Such integer k must exist by our assumption that S \ T is infinite.

Then define g(n) = f(k).

Having defined g, we need to prove that the range of g include only the elements of S \ T;

that should be obvious by construction.

Secondly we need to prove that the range of g contains all of S \ T.

Suppose the contrary and we will derive a contradiction.

Let k be the smallest integer such that f(k) ∉ T and f(k) ∉ the range of g.

Case 1: For all i < k, f(i) ∈ T.

In that case g(0) = f(k) by construction of g.

Case 2: Otherwise let i be the largest integer satisfying

i < k

f(i) ∉ T.

Then by the minimality of k, f(i) = g(m) for some m.

By construction of g, g(m+1) = f(k).

This contradicts our supposition that the range of g does not include all of S \ T and

concludes the proof.