Aritmética de primeira ordem - First-order arithmetic

Na teoria dos conjuntos e na lógica matemática, a aritmética de primeira ordem é uma coleção de sistemas axiomáticos que formalizam os naturais e os subconjuntos dos números naturais. É uma escolha pela teoria axiomática como base para muitos matemáticos, mas não todos. O axioma primário de primeira ordem é a aritmética de Peano , criada por Giuseppe Peano :

• ${\ displaystyle 0 \ in \ mathbb {N}}$: 0 é um número natural.
• ${\ displaystyle \ forall x (x = x)}$: A igualdade é reflexiva .
• ${\ displaystyle \ forall x \, \ forall y (y = x \ rightarrow x = y)}$: A igualdade é simétrica .
• ${\ displaystyle \ forall x \, \ forall y \, \ forall z (x = y \ land y = z \ rightarrow x = z)}$: A igualdade é transitiva .
• ${\ displaystyle \ forall x \, \ forall y (x \ in \ mathbb {N} \ land x = y \ rightarrow y \ in \ mathbb {N})}$: Os números naturais são fechados por igualdade.
• ${\ displaystyle \ forall x \ in \ mathbb {N} (S (x) \ in \ mathbb {N})}$: Os números naturais são fechados em S (a operação sucessora).
• ${\ displaystyle \ forall x, y \ in \ mathbb {N} (x = y \ leftrightarrow S (x) = S (y))}$: S é uma injeção .
• ${\ displaystyle \ forall x \ in \ mathbb {N} (S (x) \ neq 0)}$: Não há número natural cujo sucessor seja zero.
• ${\ displaystyle \ forall X (0 \ in X \ land \ forall x \ in \ mathbb {N} ((x \ in X) \ rightarrow (S (x) \ in X))) \ rightarrow \ mathbb {N} \ subseteq X}$: Se K é um conjunto tal que 0 está em K, e para todo número natural n, sendo n em K implica que S (n) está em K, então K contém todos os números naturais.

A aritmética de Peano tem um ordinal teórico da prova de . ${\ displaystyle \ varepsilon _ {0} = \ varphi (1,0) = \ psi _ {0} (\ Omega)}$

Mais sobre a aritmética de Peano

As várias axiomatizações da aritmética de Peano são muito diferentes, mas equivalentes. Enquanto algumas axiomatizações, como a descrita recentemente (a definição original) usam uma assinatura contendo apenas símbolos de 0, sucessor, adição e multiplicação, outras axiomatizações usam a linguagem de semi-anel ordenado, incluindo um símbolo de relação de ordem extra. Uma dessas axiomatizações começa com os seguintes axiomas que descrevem uma semifiação discretamente ordenada:

1. ${\ displaystyle \ forall x, y, z \ ((x + y) + z = x + (y + z))}$, ou seja, a adição é associativa .
2. ${\ displaystyle \ forall x, y \ (x + y = y + x)}$, ou seja, a adição é comutativa .
3. ${\ displaystyle \ forall x, y, z \ ((x \ cdot y) \ cdot z = x \ cdot (y \ cdot z))}$, ou seja, a multiplicação é associativa.
4. ${\ displaystyle \ forall x, y \ (x \ cdot y = y \ cdot x)}$, ou seja, a multiplicação é comutativa.
5. ${\ displaystyle \ forall x, y, z \ (x \ cdot (y + z) = (x \ cdot y) + (x \ cdot z))}$, ou seja, a multiplicação distribui sobre a adição.
6. ${\ displaystyle \ forall x \ (x + 0 = x \ land x \ cdot 0 = 0)}$, ou seja, zero é uma identidade para adição e um elemento absorvente para multiplicação.
7. ${\ displaystyle \ forall x \ (x \ cdot 1 = x)}$, ou seja, um é uma identidade para multiplicação.
8. ${\ displaystyle \ forall x, y, z \ (x <y \ land y <z \ Rightarrow x <z)}$, ou seja, o operador '<' é transitivo .
9. ${\ displaystyle \ forall x \ (\ neg (x <x))}$, ou seja, o operador '<' é irreflexivo .
10. ${\ displaystyle \ forall x, y \ (x <y \ lor x = y \ lor y <x)}$, ou seja, o pedido satisfaz a tricotomia .
11. ${\ displaystyle \ forall x, y, z (x <y \ rightarrow x + z <y + z)}$, ou seja, a ordem é preservada com a adição do mesmo elemento.
12. ${\ displaystyle \ forall x, y, z (0 <z \ land x <y \ rightarrow x \ cdot z <y \ cdot z}$, ou seja, a ordem é preservada sob a multiplicação pelo mesmo elemento positivo.
13. ${\ displaystyle \ forall x, y (x <y \ rightarrow \ exists z (x + z = y))}$, isto é, dados quaisquer dois elementos distintos, o maior é o menor mais outro elemento.
14. ${\ displaystyle 0 <1 \ land \ forall x \ in \ mathbb {N} (x> 0 \ rightarrow x \ geq 1)}$, ou seja, zero e um são distintos e não há nenhum elemento entre eles.
15. ${\ displaystyle \ forall x \ (x \ geq 0)}$, ou seja, zero é o elemento mínimo.

Esses axiomas são conhecidos como PA ^- ; a teoria PA é obtida adicionando o esquema de indução de primeira ordem . Uma característica importante do PA ^- é que qualquer estrutura que satisfaça esta teoria tem um segmento inicial (ordenado por ) isomorfo a . Os elementos nesse segmento são chamados de elementos padrão, enquanto outros elementos são chamados de elementos não padronizados. ${\ displaystyle \ forall X (0 \ in X \ land \ forall x \ in \ mathbb {N} (x \ in X)) \ rightarrow \ mathbb {N} \ subseteq X}$${\ displaystyle M}$${\ displaystyle \ leq}$${\ displaystyle \ mathbb {N}}$

Robinson aritmética Q

A aritmética de Robinson é um fragmento de primeira ordem finitamente axiomatizado da aritmética de Peano (PA), produzido pela primeira vez em 1950 por RM Robinson . É muitas vezes referido como Q. Q é quase idêntico ao PA sem o esquema matemático axioma de indução (PA ^- ). Q é mais fraco do que PA, mas sua linguagem é a mesma e as duas teorias estão incompletas . A lógica de fundo de Q é a lógica de primeira ordem com identidade, denotada pelo infixo '='. Os indivíduos, chamados de números naturais, são membros de um conjunto denominado N com um membro distinto 0, denominado zero. Existem três operações em N:

• Uma operação unária chamada sucessora e denotada pelo prefixo S;

• Duas operações binárias, adição e multiplicação, denotadas por infixo + e ·, respectivamente.

Os axiomas são:

• ${\ displaystyle \ forall x \ in \ mathbb {N} (S (x) \ neq 0)}$: 0 não é o sucessor de nenhum número.
• ${\ displaystyle S (x) = S (y) \ rightarrow x = y}$: Se o sucessor de x for idêntico ao sucessor de y, então xey são idênticos.
• ${\ displaystyle \ forall x (x = 0 \ lor \ exists y (S (y) = x))}$Cada número natural é 0 ou o sucessor de algum número.
• ${\ displaystyle \ forall x (x + 0 = x)}$
• ${\ displaystyle \ forall x, y (x + S (y) = S (x + y))}$
• ${\ displaystyle \ forall x (x \ cdot 0 = 0)}$
• ${\ displaystyle \ forall x, y (x \ cdot S (y) = (x \ cdot y) + x)}$

A aritmética de Robinson tem um ordinal teórico da prova de . ${\ displaystyle \ omega = \ varphi (0,1) = \ psi _ {0} (1)}$

Definições indutivas iteradas

As definições indutivas iteradas do sistema de vezes é uma hierarquia de fortes sistemas matemáticos desenvolvidos pelo matemático alemão Wilfried Buchholz, conhecido por criar a função psi de Buchholz . ID _ν estende PA por ν pontos menos fixos iterados de operadores monótonos. Se ν = ω, os axiomas são: ${\ displaystyle \ nu}$

• Os axiomas da aritmética de Peano

• ${\ displaystyle \ forall y \ forall x ({\ mathfrak {M}} _ {y} (P_ {y} ^ {\ mathfrak {M}}, x) \ rightarrow x \ in P_ {y} ^ {\ mathfrak {M}})}$
• ${\ displaystyle \ forall y (\ forall x ({\ mathfrak {M}} _ {y} (F, x) \ rightarrow F (x)) \ rightarrow \ forall x (x \ in P_ {y} ^ {\ mathfrak {M}} \ rightarrow F (x)))}$para cada fórmula L _ID F (x)
• ${\ displaystyle \ forall y \ forall x_ {0} \ forall x_ {1} (P _ {<y} ^ {\ mathfrak {M}} x_ {0} x_ {1} \ leftrightarrow x_ {0} <y \ land x_ {1} \ em P_ {x_ {0}} ^ {\ mathfrak {M}})}$

Para ν ≠ ω, os axiomas são:

• Os axiomas da aritmética de Peano

• ${\ displaystyle \ forall y \ forall x ({\ mathfrak {M}} _ {y} (P_ {y} ^ {\ mathfrak {M}}, x) \ rightarrow x \ in P_ {y} ^ {\ mathfrak {M}})}$
• ${\ displaystyle \ forall x ({\ mathfrak {M}} _ {u} (F, x) \ rightarrow F (x)) \ rightarrow \ forall x (P_ {u} ^ {\ mathfrak {M}} x \ rightarrow F (x))}$para cada fórmula L _ID F (x) e todos u <ν
• ${\ displaystyle \ forall y \ forall x_ {0} \ forall x_ {1} (P _ {<y} ^ {\ mathfrak {M}} x_ {0} x_ {1} \ leftrightarrow x_ {0} <y \ land x_ {1} \ em P_ {x_ {0}} ^ {\ mathfrak {M}})}$

${\ displaystyle {\ widehat {\ mathsf {ID}}} _ {\ nu}}$é uma versão enfraquecida de . No sistema de , um conjunto é denominado indutivamente definido se, para algum operador monotônico , for um ponto fixo de , em vez do menor ponto fixo. Esta diferença sutil torna o sistema significativamente mais fraco:, enquanto . ${\ displaystyle {\ mathsf {ID}} _ {\ nu}}$${\ displaystyle {\ widehat {\ mathsf {ID}}} _ {\ nu}}$${\ displaystyle I \ subseteq \ mathbb {N}}$${\ displaystyle \ Gamma: P (N) \ rightarrow P (N)}$${\ displaystyle I}$${\ displaystyle \ Gamma}$${\ displaystyle PTO ({\ varejhat {\ mathsf {ID}}} _ {1}) = \ varphi (\ varepsilon _ {0}, 0) = \ psi _ {0} (\ Omega ^ {\ \ psilon _ { 0}})}$${\ displaystyle PTO ({\ mathsf {ID}} _ {1}) = \ psi _ {0} (\ varepsilon _ {\ Omega +1})}$

${\ displaystyle {\ mathsf {ID}} _ {\ nu} \ #}$está ainda mais enfraquecido. Em , ele não apenas usa pontos fixos em vez de, pelo menos, pontos fixos, mas também tem indução apenas para fórmulas positivas. Esta diferença sutil, mais uma vez, torna o sistema ainda mais fraco:, enquanto . ${\ displaystyle {\ widehat {\ mathsf {ID}}} _ {\ nu}}$${\ displaystyle {\ mathsf {ID}} _ {\ nu} \ #}$${\ displaystyle PTO ({\ mathsf {ID}} _ {1} \ #) = \ varphi (\ omega, 0) = \ psi _ {0} (\ Omega ^ {\ omega})}$${\ displaystyle PTO ({\ varejhat {\ mathsf {ID}}} _ {1}) = \ varphi (\ varepsilon _ {0}, 0) = \ psi _ {0} (\ Omega ^ {\ \ psilon _ { 0}})}$

${\ displaystyle {\ mathsf {W-ID}} _ {\ nu}}$é a mais fraca de todas as variantes de , com base em W-types. A quantidade de enfraquecimento em comparação com as definições indutivas iteradas regulares é idêntica à remoção da indução da barra, dado um determinado subsistema de aritmética de segunda ordem . , enquanto . ${\ displaystyle {\ mathsf {ID}} _ {\ nu}}$${\ displaystyle PTO ({\ mathsf {W-ID}} _ {1}) = \ psi _ {0} (\ Omega \ times \ omega)}$${\ displaystyle PTO ({\ mathsf {ID}} _ {1}) = \ psi _ {0} (\ varepsilon _ {\ Omega +1})}$

${\ displaystyle {\ mathsf {U (ID}} _ {\ nu} {\ mathsf {)}}}$é um fortalecimento "revelado" de . Não é exatamente um sistema aritmético de primeira ordem, mas captura o que se pode obter pelo raciocínio predicativo baseado em definições indutivas generalizadas iteradas por ν vezes. A quantidade de aumento na força é idêntica ao aumento de a :, enquanto . ${\ displaystyle {\ mathsf {ID}} _ {\ nu}}$${\ displaystyle \ varepsilon _ {0}}$${\ displaystyle \ Gamma _ {0}}$${\ displaystyle PTO ({\ mathsf {ID}} _ {1}) = \ psi _ {0} (\ varepsilon _ {\ Omega +1})}$${\ displaystyle PTO ({\ mathsf {U (ID}} _ {1} {\ mathsf {)}}) = \ psi _ {0} (\ Gamma _ {\ Omega +1})}$

${\ displaystyle {\ mathsf {Aut ({\ widehat {\ mathsf {ID}}})}}}$é um automorfismo de . , mas ainda é mais fraco do que . ${\ displaystyle {\ mathsf {\ widehat {ID}}} _ {\ nu}}$${\ displaystyle {\ mathsf {PTO (Aut ({\ widehat {\ mathsf {ID}}}))}} = \ psi _ {0} (\ Omega ^ {\ Omega \ times 2}) = {\ mathsf { PTO ({\ widehat {\ mathsf {ID}}}}} _ {<\ Omega})}$${\ displaystyle {\ mathsf {Aut ({\ widehat {\ mathsf {ID}}})}}}$${\ displaystyle {\ mathsf {ID}} _ {1}}$

${\ displaystyle {\ mathsf {Aut ({\ mathsf {ID}})}}}$é um automorfismo de . , mas ainda é mais fraco do que . ${\ displaystyle {\ mathsf {ID}} _ {\ nu}}$${\ displaystyle {\ mathsf {PTO (Aut ({\ mathsf {ID}}))}} = \ psi _ {0} (\ Omega _ {\ Omega}) = {\ mathsf {PTO ({\ mathsf {ID }}}} _ {<\ Omega})}$${\ displaystyle {\ mathsf {Aut ({\ mathsf {ID}})}}}$${\ displaystyle {\ mathsf {KPi}}}$

${\ displaystyle {\ mathsf {Aut ({\ mathsf {ID \ #}})}}}$é um automorfismo de . , onde está a hierarquia de Veblen com menos pontos fixos iterados contáveis. ${\ displaystyle {\ mathsf {ID}} _ {\ nu} \ #}$${\ displaystyle {\ mathsf {PTO (Aut ({\ mathsf {ID \ #}}))}} = \ psi _ {0} (\ Omega ^ {<\ Omega}) = {\ mathsf {PTO ({\ mathsf {ID _ {<\ Omega} \ #}})}}}$${\ displaystyle \ psi _ {0} (\ Omega ^ {<\ Omega}) = \ varphi ({\ mathsf {<}} \ Omega, 0)}$

Outros sistemas de primeira ordem

PA ^-

PA ^- é a teoria de primeira ordem da parte não negativa de um anel ordenado discretamente. Um anel é um conjunto equipado com duas operações binárias: (adição) e (multiplicação) que satisfaz os três conjuntos de axiomas a seguir, chamados de axiomas de anel: ${\ displaystyle R}$${\ displaystyle +}$${\ displaystyle \ cdot}$

• ${\ displaystyle +}$é associativo, é comutativo, é a identidade aditiva e é o inverso aditivo de .${\ displaystyle +}$${\ displaystyle 0}$${\ displaystyle -a}$${\ displaystyle a}$
• ${\ displaystyle \ cdot}$é associativa e é a identidade multiplicativa .${\ displaystyle 1}$
• ${\ displaystyle a \ cdot (b + c) = (a \ cdot b) + (a \ cdot c)}$para todos , e em .${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle c}$${\ displaystyle R}$
• ${\ displaystyle (b + c) \ cdot a = (b \ cdot a) + (c \ cdot a)}$para todos , e em .${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle c}$${\ displaystyle R}$

PA ^- tem um ordinal teórico da prova de . ${\ displaystyle \ omega = \ varphi (0,1) = \ psi _ {0} (1)}$

RFA

RFA é uma função aritmética rudimentar . Uma função rudimentar é uma função que pode ser obtida a partir das seguintes operações:

• ${\ displaystyle F (x_ {1}, x_ {2}, ...) = x_ {j}}$ é rudimentar
• ${\ displaystyle F (x_ {1}, x_ {2}, ...) = \ {x_ {i}, x_ {j} \}}$ é rudimentar
• ${\ displaystyle F (x_ {1}, x_ {2}, ...) = x_ {i} -x_ {j}}$ é rudimentar
• Qualquer composição de funções rudimentares é rudimentar
• ${\ displaystyle \ bigcup \ limits _ {z \ in y} G (z, x_ {1}, x_ {2}, ...)}$ é rudimentar

Para qualquer conjunto M, seja rud ( M ) o menor conjunto contendo M ∪ { M } fechado sob as operações rudimentares. RFA é uma versão da aritmética baseada em funções rudimentares. RFA tem um ordinal teórico da prova de ω ² .

IΔ ₀ / IΣ ₁

IΔ ₀ e IΣ ₁ são aritmética básica com indução para Δ ₀ - e Σ _{1 -} predicados, respectivamente. Observe que quando as pessoas se referem a IΔ ₀ , IΔ ₀ é aritmética básica com indução para Δ _0- predicados, mas sem um axioma afirmando que a exponenciação é total , enquanto IΔ ₀ com tal axioma é referido como IΔ ₀ ⁺ . IΔ ₀ ⁿ para 1 <n <ω é IΔ ₀ ⁺ aumentado por um axioma garantindo que cada elemento do n- ésimo nível da hierarquia de Grzegorczyk seja total. IΔ ₀ tem um ordinal teórico da prova de ω ² . IΔ ₀ ⁺ . tem um ordinal teórico da prova de ω ³ . IΔ ₀ ⁿ tem um ordinal teórico da prova de ω ⁿ . IΣ ₁ tem um ordinal teórico da prova de ω ^ω . ${\ displaystyle {\ mathcal {E}} ^ {n}}$

EFA

EFA é aritmética de função elementar. Seu idioma contém:

• duas constantes 0, 1,
• três operações binárias +, ×, exp, com exp ( x , y ) geralmente escrito como x ^y ,
• um símbolo de relação binária <(Isso não é realmente necessário, pois pode ser escrito em termos de outras operações e às vezes é omitido, mas é conveniente para definir quantificadores limitados).

Quantificadores limitados são aqueles da forma ∀ (x <y) e ∃ (x <y) que são abreviações para ∀ x (x <y) → ... e ∃x (x <y) ∧ ... no usual caminho. Os axiomas do EFA são

• Os axiomas da aritmética de Robinson para 0, 1, +, ×, <
• Os axiomas para exponenciação: x ⁰ = 1, x ^{y +1} = x ^y × x .
• Indução para fórmulas cujos quantificadores são limitados (mas que podem conter variáveis ​​livres).

PRA

PRA é aritmética recursiva primitiva, uma formalização livre de quantificador dos números naturais . A linguagem da PRA consiste em:

• Um número infinito de variáveis x , y , z , ....
• Os conectivos proposicionais ;
• O símbolo de igualdade = , o símbolo constante 0 e o símbolo sucessor S (significando adicionar um );
• Um símbolo para cada função recursiva primitiva .

Os axiomas lógicos de PRA são:

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

As regras lógicas do PRA são o modus ponens e a substituição de variáveis .

Os axiomas não lógicos são:

• ${\ displaystyle \ forall x (S (x) \ neq 0)}$
• ${\ displaystyle \ forall x \, \ forall y (S (x) = S (y) \ rightarrow x = y)}$

e equações de definição recursivas para cada função recursiva primitiva conforme desejado.

Referências