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

From Machinelearning
< User:IssaRice
Revision as of 20:40, 20 February 2019 by IssaRice (talk | contribs)
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 Empty theory (theory with no non-logical axioms) inside propositional logic
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
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. 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