Incompleteness and undecidability of theories consistent with R

2022/11/28 by Taishi Kurahashi, Kurahashi, Taishi
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge

paper · pdf · doi:10.48550/arxiv.2211.15455

openalex publication_date 2022/11/28 · openalex created_date 2022/12/10 · openalex updated_date 2026/07/28

Abstract

We prove the following version of the first incompleteness theorem that simultaneously strengthens Mostowski's theorem and Vaught's theorem: For any c.e. family \ T_i \_{i ∈ ω} of consistent extensions of Tarski, Mostowski and Robinson's arithmetic R, there exists a sentence φ of arithmetic such that φ\vdash R and for all i ∈ ω, T_i \nvdash φ and T_i \nvdash ¬ φ.

Related

• Incompleteness of boundedly axiomatizable theories
• Theorems of Tarski's Undefinability and Godel's Second Incompleteness-Computationally
• An incompleteness theorem via ordinal analysis
• The Mostowski Bridge
• The limitless First Incompleteness Theorem