Funktionen mit dem arithmetischen Wörterbuch ausdrücken

Question

Ich habe in der "Logic to cs" -Klasse-I-Klasse gesehen - ein Satz, der heißt: "Jede rekursive (rechnungsfähige) Funktion $ F $ kann mit ausgedrückt werdenDas arithmetische Wörterbuch { $ c_0, c_1, f _ + (,), f_x (,), r_ \ le (,) $ } mit der Struktur { $ d=mathbb {n}, c_0= 0, c_1= 1, f _ + (a, b)= a + b, f_x (a, b)= ab, r_ \ le (a,b)= a \ le b $ } "

aber wir haben diesen Satz nicht bewiesen, weil ein Teil der Schüler den Kurs "Computational Models" nicht mitgenommen hat (ich habe es jedoch genommen)

Wo finde ich einen Beweis für diesen Theorem?Vielen Dank im Voraus!

Answer 1

Ich bin nicht sicher, ob das genau das ist, wonach Sie suchen, aber Sie finden möglicherweise das, was Sie in Theorem 3.2.1 von ccccess theory von S. Barry Cooper:

Alle rekursiven Funktionen sind in pa darstellbar.

das ist für eine beliebige rekursive Funktion $ F $ , gibt es ein binäres Prädikat $ F $ in die Sprache der Arithmetik, so dass für jede natürliche Anzahl $ x $ und $ y $ wir haben $$ F (x)= y ~ \ Rightarrow ~ \ VDASH_ {PA} f (x, y) $$ und $$ F (x) \ neq y ~ \ Rightarrow ~ \ VDASH_ {PA} \ lnot f (x, y) $$ Wo $ \ vdash_ {pa} $ bedeutet, dass 'PA erweist'.

Dieser Theorem ist zentral für Gödels berühmtes unvollmächtiger theorem , so dass Sie auch einen Blick auf ch ersehen möchten. 8 des genannten Buches, in dem er diskutiert wird, und dieser Begriff der "Repräsentabilität" wird auf die "Semi-Repräsentabilität" erweitert, um die C.E. Setzt auch.