I am relatively new to logic, so forgive my ignorance. My question is: Are there any formal systems that are deemed complete? If so, how did we prove they were complete and which are they?
2026-03-27 21:16:53.1774646213
Are there complete formal systems?
386 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
Inconsistent theories are trivially complete, so I'm going to assume that you're looking for systems that are both consistent and complete.
One such system is Presburger Arithmetic (PreA), which resembles the usual Peano Arithmetic, but has no multiplication.
A common technique for showing completeness is quantifier elimination: a theory admits quantifier elimination if every quantified formula corresponds to a logically equivalent quantifier-free formula.
Strictly speaking, PreA does not admit quantifier elimination, but a finite extension does: the resulting procedure is Cooper's algorithm.
Quantifier elimination, by itself, does not mean that your theory is complete: you also need to show that all quantifier-free statements are either provable or refutable. In the case of PreA and its extension, this follows by a simple structural induction.