3 ms·
Isn't the underlying question proved impossible by Godel's incompletness theorem?
by dooglius 2mo ago
Isn't the underlying question proved impossible by Godel's incompletness theorem?
- deleted 2mo ago[deleted]
- LegionMammal978 2mo agoNo, Gödel's incompleteness theorem applies to theories that can interpret first-order arithmetic, which includes quantified statements like "for all x, there exists a prime p > x". In this case, we have the much simpler equational theory of positive integers under addition, multiplication, and exponentiation, which does not include any quantifiers. In fact, Gurevič showed that this theory is decidable [0]. On the other hand, Gurevič later showed that this theory is not finitely axiomatizable [1], so an infinite (but still computable) set of axioms is needed to fully characterize the theory. [0] R. Gurevič, Equational theory of positive numbers with exponentiation, 1985, https://doi.org/10.2307/2044966 https://doi.org/10.2307/2044966 [1] R. Gurevič, Equational theory of positive numbers with exponentiation is not finitely axiomatizable, 1990, https://doi.org/10.1016/0168-0072(90)90049-8 https://doi.org/10.1016/0168-0072(90)90049-8
- cubefox 2mo agoNot finitely axiomatizable using first-order logic, I assume.
- LegionMammal978 2mo agoNot using a set of axioms written in the original signature, of equations using the three operations and the constant 1. It's certainly possible to come up with a finite description of the true sentences in the theory, but only by extending the signature or using some method of description other than a set of axioms.
- cubefox 2mo agoUsually when people say "not finitely axiomatizable" they just mean first-order logic. For example, Peano arithmetic is finitely axiomatizable using second-order logic, which allows quantification of predicate variables, which is required for the axiom of induction.
- deleted 2mo ago[deleted]