＞岩波の応用数学講座のやつ
[基礎11]論理と計算　萩谷昌己著

上の本は難しいというよりも肝心なところが書いてない。
もっとも関数proof(x,y)が原始帰納的関数になる、という
肝心なところを詳しく書いた本はなかなかない。

そうではなくて対角線論法のところを理解したいなら
ゲーデル・エッシャー・バッハが分かりやすい。
詳しくはクワイン化のところを読め