Herbrand consistency and bounded arithmetic

• Autorzy: Zofia Adamowicz
• Języki publikacji: EN

Abstrakty

EN

We prove that the Gödel incompleteness theorem holds for a weak arithmetic Tₘ = IΔ₀ + Ωₘ, for m ≥ 2, in the form Tₘ ⊬ HCons(Tₘ), where HCons(Tₘ) is an arithmetic formula expressing the consistency of Tₘ with respect to the Herbrand notion of provability. Moreover, we prove $Tₘ ⊬ HCons^{Iₘ}(Tₘ)$, where $HCons^{Iₘ}$ is HCons relativised to the definable cut Iₘ of (m-2)-times iterated logarithms. The proof is model-theoretic. We also prove a certain non-conservation result for Tₘ.

Kategorie tematyczne

• 03F30: First-order arithmetic and fragments

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Fundamenta Mathematicae
• Rocznik: 2002
• Tom: 171
• Numer: 3
• Strony: 279-292

Daty

wydano

2002

Twórcy

autor

Zofia Adamowicz

• Institute of Mathematics, Polish Academy of Sciences, Śniadeckich 8, 00-950 Warszawa, Poland

Identyfikatory

DOI

10.4064/fm171-3-7