0 like 0 dislike
0 like 0 dislike
How can a theory be decidable and incomplete?

3 Answers

0 like 0 dislike
0 like 0 dislike
I believe "decidable" doesn't typically mean the algorithm assigns a *truth value* to every sentence - in fact, true/false don't even really apply when we're talking about sentences in a theory. Instead, the algorithm takes a sentence as input, and returns an output saying that either yes this sentence is a theorem, or no it is not. It is totally possible for both P and ~P to not be theorems.

For example, if you are working from the group axioms, neither "∀x,y: xy=yx" nor its negation "∃x,y: xy≠yx" is a theorem that can be proved from the axioms. If you know a little bit of group theory, it should be easy to see why!
0 like 0 dislike
0 like 0 dislike
The simple answer is that completeness is determined by the semantics and syntax of a logical system, while decidability is (usually) determined only by the semantics. So if we have a decidable system with a very unexpressive syntax, then that system could be decidable but incomplete.

For example, consider a logic identical to propositional logic, except we aren't allowed to infer b from {a, a->b}. This system is decidable since we can still check the truth value of any sentence with a truth table, but there will be many true statements that we cannot prove.
0 like 0 dislike
0 like 0 dislike
Godel's incompleteness theorem. You can read about it on wikipedia. Basically there is always a way to create true statements that cannot be proven within the current axioms.

It is (ELI5) something along the lines of the statement "this statement cannot be proven". So if it can, then it is false and if it cannot, then it is true.

No related questions found

24.8k questions

103k answers

0 comments

33.7k users

OhhAskMe is a math solving hub where high school and university students ask and answer loads of math questions, discuss the latest in math, and share their knowledge. It’s 100% free!