Expressar funções usando a aritmética de dicionário

Question

eu tenho visto na "lógica para cs" classe i take - um teorema que afirma:"cada recursiva (computável) função $f$ pode ser expresso usando a aritmética dicionário {$C_0, C_1, f_+(,), f_x(,), R_\le(,)$} com a estrutura {$D=\mathbb{N} ,C_0=0,C_1=1, f_+(a,b) =a+b, f_x(a,b)=ab, R_\le(a,b) = a\b le $}"

Mas nós não provar este teorema, porque uma parte dos alunos não tirar os "modelos computacionais", claro (eu fiz isso embora)

Onde posso encontrar uma prova deste teorema?Obrigado antecipadamente!

Answer 1

Não tenho certeza se este é exatamente o que você está procurando, mas você pode encontrar o que deseja no Teorema 3.2.1 Computability Teoria por S.Barry Cooper:

Todas as funções recursivas são representáveis no PA.

que é para qualquer função recursiva $f$, existe um predicado binário $F$ na linguagem da aritmética, tais que, para quaisquer números naturais $x$ e $y$ nós temos $$ f(x) = y ~ ightarrow~ \vdash_{PA} F(x,y) $$ e $$ f(x) eq y ~ ightarrow~ \vdash_{PA} \lnot F(x,y) $$ onde $\vdash_{PA}$ significa 'PA prova'.

Este teorema é central para Gödel famosos teorema da incompletude, assim você também pode querer dar uma olhada no pc.8 do mencionado livro, onde é discutido, e esta noção de "representatividade" é estendido para "semi-representatividade', para incluir a c.e.define bem.