Difference between revisions of "User:IssaRice/Computability and logic/List of possibilities for completeness and decidability"
From Machinelearning
Line 5: | Line 5: | ||
| Yes || Yes || Yes || Yes || Empty theory (theory with no non-logical axioms) inside propositional logic | | Yes || Yes || Yes || Yes || Empty theory (theory with no non-logical axioms) inside propositional logic | ||
|- | |- | ||
− | | Yes || Yes || Yes || No || | + | | Yes || Yes || Yes || No || Smith's example of <math>T_1</math> with just <math>\neg p</math> as an axiom inside a propositional logic with propositional atoms <math>p,q,r</math>.<ref>Peter Smith. ''An Introduction to Gödel's Theorems'' (2nd ed). p. 32.</ref> |
|- | |- | ||
| Yes || Yes || No || Yes || | | Yes || Yes || No || Yes || |
Revision as of 19:49, 20 February 2019
Decidable logic? | Complete logic? (semantic completeness) | Decidable theory? | Complete theory? (negation-completeness) | Example or proof of non-existence |
---|---|---|---|---|
Yes | Yes | Yes | Yes | Empty theory (theory with no non-logical axioms) inside propositional logic |
Yes | Yes | Yes | No | Smith's example of with just as an axiom inside a propositional logic with propositional atoms .^{[1]} |
Yes | Yes | No | Yes | |
Yes | Yes | No | No | |
Yes | No | Yes | Yes | |
Yes | No | Yes | No | |
Yes | No | No | Yes | |
Yes | No | No | No | |
No | Yes | Yes | Yes | |
No | Yes | Yes | No | |
No | Yes | No | Yes | Empty theory (theory with no non-logical axioms) inside first-order logic |
No | Yes | No | No | The theory of Robinson arithmetic inside first-order logic |
No | No | Yes | Yes | |
No | No | Yes | No | |
No | No | No | Yes | |
No | No | No | No |
- ↑ Peter Smith. An Introduction to Gödel's Theorems (2nd ed). p. 32.