enumerability exercise in boolos book

Question

problem 2.2 of Computability and Logic written by Boolos(p.20, fifth edition)

Show that if for some or all of the finite strings from a given finite or enumerable alphabet we associate to the string a total or partial function from positive integers to positive integers, then there is some total function on positive integers taking only the values 1 and 2 that is not associated with any string.

I've been thinking about this for almost 2 hours, but I don't have any idea.. If you have some knowledge, please give me guidelines how to prove this.

Answer 1

An earlier result in Computability in Logic (Chapter 1, Enumerability) asserts the enumerability of the set of finite strings from a finite or enumerable alphabet (the "for some" case follows from the enumerability of any subset of an enumerable set). Then the set $F$ of all total or partial functions $f_i\colon \mathbb Z_{>0} \to \mathbb Z_{>0}$ associated with such finite strings is enumerable also, i.e. the functions can be listed as $f_1, f_2, \ldots$.

Now use diagonalization to construct a total function $f$ that is not any $f_n$ in the enumeration of $F$. One such function is under a spoiler below:

$$f(n) = \begin{cases}1 & \text{if $f_n(n)=2$} \\ 2 & \text{if $f_n(n) \ne 2$ or $f_n(n)$ is undefined}\end{cases}$$

Now suppose towards a contradiction that $f$ is associated with some finite string. Then $f = f_m$ is in the enumeration of $F$. But this is absurd:

If $f_m(m) = 2$, then $f(m) = 1 = f_m(m)$, and if $f_m(m) \ne 2$ or is undefined, then $f(m) = 2 = f_m(m)$.