A carregar...
Publicação
On Notions of Provability
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 4.97 MB | Adobe PDF |
Orientador(es)
Resumo(s)
In this thesis, we study notions of provability, i.e. formulas B(x,y) such that a formula
ϕ is provable in T if, and only if, there is m ∈ N such that T ⊢ B(⌜ϕ⌝,m) (m plays the
role of a parameter); the usual notion of provability, k-step provability (also known as
k-provability), s-symbols provability are examples of notions of provability.
We develop general results concerning notions of provability, but we also study in
detail concrete notions. We present partial results concerning the decidability of kprovability
for Peano Arithmetic (PA), and we study important problems concerning
k-provability, such as Kreisel’s Conjecture and Montagna’s Problem:
(∀n ∈ N.T ⊢k steps ϕ(n)) =⇒ T ⊢ ∀x.ϕ(x), [Kreisel’s Conjecture]
and
Does PA ⊢k steps PrPA(⌜ϕ⌝)→ϕ imply PA ⊢k steps ϕ? [Montagna’s Problem]
Incompleteness, Undefinability of Truth, and Recursion are different entities that
share important features; we study this in detail and we trace these entities to common
results.
We present numeral forms of completeness and consistency, numeral completeness
and numeral consistency, respectively; numeral completeness guarantees that, whenever
a Σb
1(S12
)-formula ϕ(⃗x ) is such that ⃗Q
⃗x .ϕ(⃗x ) is true (where ⃗Q
is any array of quantifiers),
then this very fact can be proved inside S12
, more precisely S12
⊢ ⃗Q
⃗x .Prτ (⌜ϕ(
•⃗
x )⌝). We
examine these two results from a mathematical point of view by presenting the minimal
conditions to state them and by finding consequences of them, and from a philosophical
point of view by relating them to Hilbert’s Program.
The derivability condition “provability implies provable provability” is one of the main
derivability conditions used to derive the Second Incompleteness Theorem and is known
to be very sensitive to the underlying theory one has at hand. We create a weak theory
G2 to study this condition; this is a theory for the complexity class FLINSPACE. We also
relate properties of G2 to equality between computational classes.
O tema desta tese são noções de demonstração; estas últimas são fórmulas B(x,y) tais que uma fórmula ϕ é demonstrável em T se, e só se, existe m ∈ N tal que T ⊢ B(⌜ϕ⌝,m) (m desempenha o papel de um parâmetro). A noção usual de demonstração, demonstração em k-linhas (demonstração-k), demonstração em s-símbolos são exemplos de noções de demonstração. Desenvolvemos resultados gerais sobre noções de demonstração, mas também estudamos exemplos concretos. Damos a conhecer resultados parciais sobre a decidibilidade da demonstração-k para a Aritmética de Peano (PA), e estudamos dois problemas conhecidos desta área, a Conjectura de Kreisel e o Problema de Montagna: (∀n ∈ N.T ⊢k steps ϕ(n)) =⇒ T ⊢ ∀x.ϕ(x), [Conjectura de Kreisel] e PA ⊢k steps PrPA(⌜ϕ⌝)→ϕ implica PA ⊢k steps ϕ? [Problema de Montagna] A Incompletude, a Incapacidade de Definir Verdade, e Recursão são entidades que têm em comum características relevantes; nós estudamos estas entidades em detalhe e apresentamos resultados que são simultaneamente responsáveis pelas mesmas. Além disso, apresentamos formas numerais de completude e consistência, a completude numeral e a consistência numeral, respectivamente; a completude numeral assegura que, quando uma fórmula-Σb 1(S12) ϕ(⃗x ) é tal que ⃗Q ⃗x .ϕ(⃗x ) é verdadeira, então este facto pode ser verificado dentro de S12, mais precisamente S12 ⊢ ⃗Q ⃗x .Prτ (⌜ϕ( •⃗ x )⌝). Este dois resultados são analisados de um ponto de vista matemático onde apresentamos as condições mínimas para os demonstrar e apresentamos consequências dos mesmos, e de um ponto de vista filosófico, onde relacionamos os mesmos com o Programa de Hilbert. A condição de derivabilidade “demonstração implica demonstrabilidade da demonstração” é uma das condições usadas para derivar o Segundo Teorema da Incompletude e sabemos ser muito sensível à teoria de base escolhida. Nós criámos uma teoria fraca G2 para estudar esta condição; esta é uma teoria para a classe de complexidade FLINSPACE. Também relacionámos propriedades de G2 com igualdades entre classes de complexidade computacional.
O tema desta tese são noções de demonstração; estas últimas são fórmulas B(x,y) tais que uma fórmula ϕ é demonstrável em T se, e só se, existe m ∈ N tal que T ⊢ B(⌜ϕ⌝,m) (m desempenha o papel de um parâmetro). A noção usual de demonstração, demonstração em k-linhas (demonstração-k), demonstração em s-símbolos são exemplos de noções de demonstração. Desenvolvemos resultados gerais sobre noções de demonstração, mas também estudamos exemplos concretos. Damos a conhecer resultados parciais sobre a decidibilidade da demonstração-k para a Aritmética de Peano (PA), e estudamos dois problemas conhecidos desta área, a Conjectura de Kreisel e o Problema de Montagna: (∀n ∈ N.T ⊢k steps ϕ(n)) =⇒ T ⊢ ∀x.ϕ(x), [Conjectura de Kreisel] e PA ⊢k steps PrPA(⌜ϕ⌝)→ϕ implica PA ⊢k steps ϕ? [Problema de Montagna] A Incompletude, a Incapacidade de Definir Verdade, e Recursão são entidades que têm em comum características relevantes; nós estudamos estas entidades em detalhe e apresentamos resultados que são simultaneamente responsáveis pelas mesmas. Além disso, apresentamos formas numerais de completude e consistência, a completude numeral e a consistência numeral, respectivamente; a completude numeral assegura que, quando uma fórmula-Σb 1(S12) ϕ(⃗x ) é tal que ⃗Q ⃗x .ϕ(⃗x ) é verdadeira, então este facto pode ser verificado dentro de S12, mais precisamente S12 ⊢ ⃗Q ⃗x .Prτ (⌜ϕ( •⃗ x )⌝). Este dois resultados são analisados de um ponto de vista matemático onde apresentamos as condições mínimas para os demonstrar e apresentamos consequências dos mesmos, e de um ponto de vista filosófico, onde relacionamos os mesmos com o Programa de Hilbert. A condição de derivabilidade “demonstração implica demonstrabilidade da demonstração” é uma das condições usadas para derivar o Segundo Teorema da Incompletude e sabemos ser muito sensível à teoria de base escolhida. Nós criámos uma teoria fraca G2 para estudar esta condição; esta é uma teoria para a classe de complexidade FLINSPACE. Também relacionámos propriedades de G2 com igualdades entre classes de complexidade computacional.
Descrição
Palavras-chave
Notions of Provability k-provability Kreisel’s Conjecture Incompleteness Theory of Arithmetic Numeral Completeness