User:IssaRice/Computability and logic/List of possibilities for completeness and decidability

From Machinelearning
Jump to: navigation, search

Suppose we have an effectively axiomatized and consistent theory inside a complete logic.

Decidable logic? Decidable theory? Complete theory? (negation-completeness) Example or proof of non-existence
Yes Yes Yes Smith's example T_2.[1]
Yes Yes No Smith's example of T_1 with just \neg p as an axiom inside a propositional logic with propositional atoms p,q,r.[1]
Yes No Yes Assuming the theory is effectively axiomatized and consistent, this is not possible. To see why, suppose the theory is negation-complete. We could then computably enumerate all the theorems (since the theory is effectively axiomatized), and after a finite amount of time we will find exactly one of \phi or \neg \phi, which gives us an algorithm for deciding whether or not \phi is a theorem.
Yes No No I think the following is an example:[2] (but that page uses "decidable theory" to mean "effectively axiomatized", I think)
No Yes Yes First-order logic with two binary predicates R and S with the axiom \forall x \forall y (R(x,y)\wedge S(x,y)).[3]
No Yes No i think we can mimic T_1 by defining some predicate such that \neg P(c) is an axiom, with Q,R as additional predicates.
No No Yes Assuming the theory is effectively axiomatized and consistent, this is not possible. To see why, suppose the theory is negation-complete. We could then computably enumerate all the theorems (since the theory is effectively axiomatized), and after a finite amount of time we will find exactly one of \phi or \neg \phi, which gives us an algorithm for deciding whether or not \phi is a theorem.
No No No The theory of Robinson arithmetic inside first-order logic

References

  1. 1.0 1.1 Peter Smith. An Introduction to Gödel's Theorems (2nd ed). p. 32.
  2. https://math.stackexchange.com/a/245220/35525
  3. Carl Mummert. https://math.stackexchange.com/a/541680/35525