Papers on Weak First-Order Theories and Decidability Problems
Juvenal Murwanashyaka · NORA - Norwegian Open Research Archives · 2023
This thesis is motivated by the following questions: - Does there exist a weakest theory for which Gödel’s first incompleteness theorem holds? - Does there exist a weakest structure for which solvability of systems of equations with constraints is undecidable? We explore these questions by investigating different foundations for basic finitary mathematics and use interpretability to compare them. The concept of interpretation provides a framework for comparing theories by abstracting away arbitrariness in the choice of non-logical symbols and basic principles. If two theories are interpretable in one another, then they are of the same strength: inferences in one can be translated into inferences in the other.