aritmética recursiva primitiva - Primitive recursive arithmetic

Aritmética recursiva primitiva , ou PRA , é um quantificador formalização -livre dos números naturais . Foi proposto pela primeira vez por Skolem como uma formalização de sua finitista concepção dos fundamentos da aritmética , e é amplamente aceito que todo o raciocínio do PRA é finitista. Muitos também acreditam que todos finitismo é capturado por PRA, mas outros acreditam finitismo pode ser estendido para formas de recursão além recursão primitiva, até £ ₀ , que é o ordinal prova da teoria da aritmética de Peano . Ordinal teórica prova do PRA é ω ^ω , onde ω é o menor ordinal transfinito . PRA é às vezes chamado Skolem aritmética .

O idioma de ARP pode expressar proposições aritméticas envolvendo números naturais e qualquer função recursiva primitivo , incluindo as operações de adição , multiplicação , e exponenciação . PRA não pode quantificar explicitamente sobre o domínio dos números naturais. PRA é frequentemente visto como o básico metamatemática sistema formal para a teoria da prova , em particular para as provas de consistência , como prova a consistência do Gentzen da aritmética de primeira ordem .

Linguagem e axiomas

A linguagem do PRA é composto por:

• Um contavelmente infinito número de variáveis x , y , z , ....
• Os proposicional conectivos;
• O símbolo de igualdade = , o símbolo constante 0 , eo sucessor símbolo S (que significa acrescentar uma );
• Um símbolo para cada função recursiva primitiva .

Os axiomas lógicos de PRA são:

• Tautologias do cálculo proposicional ;
• Axiomatization usual de igualdade como uma relação de equivalência .

As regras lógicas de PRA são modus ponens e substituição de variáveis .
Os axiomas não-lógicos são:

• ${\ Displaystyle S (x) \ neq 0}$;
• ${\ Displaystyle S (x) = S (y) ~ \ a ~ X = Y,}$

e recursiva definindo equações para cada função recursiva primitiva como desejado. Por exemplo, a caracterização mais comum dos função recursiva primitiva é que a função 0 constante e sucessor fechada sob projecção, composição e recursão primitiva. Assim, para uma ( n 1) função -Place f definida por recursão primitiva ao longo de um n função de base -Place g e ( n + 2) -Place função iteração h haveria que definem as equações:

• ${\ Displaystyle f (0, Y_ {1}, \ ldots, Y_ {n}) = g (Y_ {1}, \ ldots, Y_ {n})}$
• ${\ Displaystyle f (S (x), Y_ {1}, \ ldots, Y_ {n}) = h (x, f (x, y_ {1}, \ ldots, Y_ {n}), Y_ {1} , \ ldots, Y_ {n})}$

Especialmente:

• ${\ DisplayStyle x + 0 = x \}$
• ${\ DisplayStyle X + S (y) = S (X + Y) \}$
• ${\ Displaystyle x \ cdot 0 = 0 \}$
• ${\ Displaystyle x \ cdot S (y) = x \ cdot y + x \}$
• ... e assim por diante.

PRA substitui o esquema de axioma da indução para a aritmética de primeira ordem com a regra da indução (free-quantificador):

• A partir e , deduzir , por qualquer predicado${\ Displaystyle \ varphi (0)}$${\ Displaystyle \ varphi (x) \ a \ varphi (S (x))}$${\ Displaystyle \ varphi (y)}$${\ Displaystyle \ varphi.}$

Em aritmética de primeira ordem , as únicas função recursiva primitiva que necessitam de ser explicitamente axiomatizada são adição e multiplicação . Todos os outros predicados recursivas primitivas podem ser definidos utilizando estas duas funções recursivas primitivas e quantificação sobre todos os números naturais . Definindo função recursiva primitiva dessa maneira não é possível em PRA, porque carece de quantificadores.

cálculo livre-Logic

É possível formalizar PRA, de tal forma que ele não tem conectivos lógicos em tudo-uma sentença de PRA é apenas uma equação entre dois termos. Neste cenário um termo é uma função primitiva recursiva de zero ou mais variáveis. Em 1941 Haskell Curry deu o primeiro sistema deste tipo. A regra da indução no sistema de Curry era incomum. Um refinamento mais tarde foi dada por Reuben Goodstein . A regra da indução no sistema de Goodstein é:

${\ Displaystyle {F (0) = G (0) \ quad F (S (x)) = H (x, F (x)) \ quad L (S (x)) = H (x, G (x) ) \ sobre F (x) = G (x)}.}$

Aqui x é uma variável, S é a operação sucessor, e F , G , e H estão qualquer função recursiva primitiva que podem ter outros do que os que são apresentados parâmetros. As únicas outras regras de inferência do sistema de Goodstein são regras de substituição, como segue:

${\ Displaystyle {F (x) = G (x) \ sobre F (A) = G (A)} \ qquad {A = B \ sobre F (A) = M (B)} \ qquad {A = B \ quad A = C \ por cima de B = C}.}$

Aqui A , B , e C são os termos (função recursiva primitiva de zero ou mais variáveis). Finalmente, há símbolos para qualquer função recursiva primitiva com equações definem correspondente, tal como no sistema de Skolem acima.

Desta forma, o cálculo proposicional pode ser descartada completamente. Os operadores lógicos pode ser expressa inteiramente aritmeticamente, por exemplo, o valor absoluto da diferença de dois números podem ser definidos por recursão primitiva:

${\ Displaystyle {\ {começar alinhados} P (0) = 0 \ quad & \ quad P (S (x)) = x x \\ {\ dot {-}} 0 = x \ quad & \ x {quad \ mathrel {\ dot {-}}} S (y) = P (x {\ mathrel {\ dot {-}}} y) \\ | xy | = & (x {\ mathrel {\ dot {-}}} y) + (y {\ mathrel {\ dot {-}}}. x) \\\ final {alinhados}}}$

Assim, as equações x = y e | x - y | = 0 são equivalentes. Por conseguinte, as equações e expressar a lógica conjunto e disjunção , respectivamente, das equações x = y e u = v . Negação pode ser expressa como . ${\ Displaystyle | xy | + | uv | = 0}$${\ Displaystyle | xy | \ cdot | uv | = 0}$${\ Displaystyle 1 {\ dot {-}} | xy | = 0}$

Veja também

• aritmética recursiva elementar
• Heyting aritmética
• aritmética de Peano
• aritmética de segunda ordem
• função recursiva primitiva
• lógica finito de valor

Referências

leitura adicional

• Rose, HE (1961), "Por consistência e de indecisão aritmética recursivo", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 7 : 124-135, MR  0.140.413.

• Feferman, S (1992) O que repousa sobre o quê? A análise à prova de teórico da matemática . Palestra convidado, 15 Int'l Symposium Wittgenstein.