There is no recursive function that counts sizes of finite sets

Question

I have the following problem:

Problem: Show that there is no total recursive function $f$ such that for any index $e$, if $\phi_e$ is the characteristic function of a finite set $F$, then $f(e)$ converges and $f(e) = |F|$.

I have been trying to use the recursion theorem to find a contradiction, but I don't see clearly how to define the function depending on the index the reach the conclusion, and I would appreciate any hint.

Answer 1

In fact, the solution below proves something slightly stronger: that there is no partial computable function with the desired property! If you only want to prove the weaker result, then things are easier: since $f$ needs to be total you can do away with [Thing Three], since you know a priori that [Thing One] will eventually happen.

By the recursion theorem, we can construct an $e$ such that $\varphi_e$ has the behavior, $$\mbox{"Wait until $f(e)$ [does Thing One], then [do Thing Two]; until then, keep [doing Thing Three]."}$$ This is generally how we use the recursion theorem in this kind of argument. Now:

• Thing One is usually the same in every construction like this. When you have a partial recursive function on some input, what do you usually wait for it to do?

• Thing Two is where the action is. Suppose $f(e)$ did Thing One. What should $\varphi_e$ do to "win"?

• Thing Three should be something that you can do "for free," i.e., a lot of Thing Three happening doesn't get in the way of doing thing two. In particular:

  • In order for $f$ to care about $\varphi_e$, what sort of function does $\varphi_e$ need to be?

  • OK, so Thing Three will involve deciding bits of $\varphi_e$ - at stage $n$, $\varphi_e(n)$ will converge. What should it converge to if $f(e)$ hasn't done Thing One? (HINT: we care about the size of the function $\varphi_e$ is a characteristic function for, so what kind of output is "noncommittal" in this regard?)

• Now put it all together. Based on the behavior of $\varphi_e$, why does $f$ need to do Thing One? (If it doesn't, then $\varphi_e$ does Thing Three forever . . .) And, why does $\varphi_e$ doing Thing Two mean $f$ fails to do its job?