Exprimant des fonctions à l'aide du dictionnaire arithmétique

Question

J'ai vu dans la classe "logique à cs", je prends - un théorème qui stipule: "Chaque fonction récursive (calculable) $ f $ peut être exprimée en utilisantLe dictionnaire arithmétique { $ C_0, C_1, F _ + (,), F_X (,), r_ \ le (,) $ } avec la structure { $ 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 $ } "

Mais nous n'avons pas prouvé ce théorème car une partie des étudiants n'a pas pris le cours "Modèles de calcul" (je l'ai pris si)

Où puis-je trouver une preuve pour ce théorème?Merci d'avance!

Answer 1

Je ne suis pas sûr que ce soit exactement ce que vous recherchez, mais vous pourriez trouver ce que vous voulez dans Theorem 3.2.1 de la théorie de la calculatrice par S. Barry Cooper:

Toutes les fonctions récursives sont représentables en PA.

qui est pour toute fonction récursive $ f $ , il existe un prédicat binaire $ f $ la langue d'arithmétique telle que pour tout nombre naturel $ x $ et $ y $ nous avons $$ f (x)= y ~ \ restard ~ \ vdash_ {pa} f (x, y) $$ et $$ f (x) \ neq y ~ \ rightarrow ~ \ vdash_ {pa} \ lnot f (x, y) $$ où $ \ vdash_ {pa} $ signifie "pa des prouve".

Ce théorème est au cœur du célèbre Theorem de Gödel , vous voudrez peut-être aussi jeter un coup d'œil à CH. 8 du livre mentionné où il est discuté et cette notion de «représentabilité» est étendue à la "semi-représentabilité", à inclure le C.E. Ensemble aussi.