Incompleteness of boundedly axiomatizable theories

Ali Enayat; Albert Visser

doi:10.48550/arXiv.2311.14025

Incompleteness of boundedly axiomatizable theories

Research output: Working paper › Preprint › Academic

Abstract

Our main result (Theorem A) shows the incompleteness of any consistent sequential theory T formulated in a finite language such that T is axiomatized by a collection of sentences of bounded quantifier-alternation-depth. Our proof employs an appropriate reduction mechanism to rule out the possibility of completeness by simply invoking Tarski's Undefinability of Truth theorem. We also use the proof strategy of Theorem A to obtain other incompleteness results (as in Theorems A+; B and B+).

Original language	English
Publisher	arXiv
Number of pages	6
DOIs	https://doi.org/10.48550/arXiv.2311.14025
Publication status	Published - 23 Nov 2023

Bibliographical note

6 pages; in this version reference to MathOverflow work of Emil Je\v{r}\'{a}bek has been added, and the author list of [AGLRZ] is now up-to-date

Keywords

math.LO
03F40

Access to Document

10.48550/arXiv.2311.14025Licence: CC BY

2311.14025v4Submitted manuscript, 163 KBLicence: CC BY

Cite this

@techreport{7cdc50c6cf604f93b99a9f159a0090b4,

title = "Incompleteness of boundedly axiomatizable theories",

abstract = " Our main result (Theorem A) shows the incompleteness of any consistent sequential theory T formulated in a finite language such that T is axiomatized by a collection of sentences of bounded quantifier-alternation-depth. Our proof employs an appropriate reduction mechanism to rule out the possibility of completeness by simply invoking Tarski's Undefinability of Truth theorem. We also use the proof strategy of Theorem A to obtain other incompleteness results (as in Theorems A+; B and B+). ",

keywords = "math.LO, 03F40",

author = "Ali Enayat and Albert Visser",

note = "6 pages; in this version reference to MathOverflow work of Emil Je\v{r}\'{a}bek has been added, and the author list of [AGLRZ] is now up-to-date",

year = "2023",

month = nov,

day = "23",

doi = "10.48550/arXiv.2311.14025",

language = "English",

publisher = "arXiv",

type = "WorkingPaper",

institution = "arXiv",

}

TY - UNPB

T1 - Incompleteness of boundedly axiomatizable theories

AU - Enayat, Ali

AU - Visser, Albert

N1 - 6 pages; in this version reference to MathOverflow work of Emil Je\v{r}\'{a}bek has been added, and the author list of [AGLRZ] is now up-to-date

PY - 2023/11/23

Y1 - 2023/11/23

N2 - Our main result (Theorem A) shows the incompleteness of any consistent sequential theory T formulated in a finite language such that T is axiomatized by a collection of sentences of bounded quantifier-alternation-depth. Our proof employs an appropriate reduction mechanism to rule out the possibility of completeness by simply invoking Tarski's Undefinability of Truth theorem. We also use the proof strategy of Theorem A to obtain other incompleteness results (as in Theorems A+; B and B+).

AB - Our main result (Theorem A) shows the incompleteness of any consistent sequential theory T formulated in a finite language such that T is axiomatized by a collection of sentences of bounded quantifier-alternation-depth. Our proof employs an appropriate reduction mechanism to rule out the possibility of completeness by simply invoking Tarski's Undefinability of Truth theorem. We also use the proof strategy of Theorem A to obtain other incompleteness results (as in Theorems A+; B and B+).

KW - math.LO

KW - 03F40

U2 - 10.48550/arXiv.2311.14025

DO - 10.48550/arXiv.2311.14025

M3 - Preprint

BT - Incompleteness of boundedly axiomatizable theories

PB - arXiv

ER -

Incompleteness of boundedly axiomatizable theories

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this