0

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.

fbg
  • 861

1 Answers1

2

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

Jukka
  • 78
  • really thanks now I know F is nondenumerable since it is a set of every functions about Z>0 thus cardinality is $2^{\aleph_0}$ – fbg Sep 24 '15 at 16:31
  • @fbg: Yes, the set of all total or partial functions from the positive integers to positive integers is nonenumerable; however, the $F$ in my post denotes only those functions associated with finite strings. – Jukka Sep 24 '15 at 16:39
  • I'm having trouble understanding the meaning of "associate" in this context. The problem states that a function associates "to the string". Doesn't this mean that more than one function can associate to the same string? And if so, can't we define the association to say that any function f, where f(1) = 1, or f(1) = 2, is immediately associated to the string "foo"? And if so, doesn't this mean that any function taking values only of 1 or 2 is associated with a string? – redfish64 Nov 30 '17 at 08:23