Why doesn't completeness imply decidability for first order logic?

First order logic is complete, which means (I think) given a set of sentences A and a sentence B, then either B or ~B can be arrived at through the rules of inference being applied to A. If B is arrived at, then A implies B in every interpretation. If ~B is arrived at, then A implies ~B in every interpretation.

First order logic is undecidable, which means (again, I think) that given a set of sentences A and a sentence B, there is no procedure for determining whether A implies B (i.e. it's not the case that A are true and B is false) in all interpretations.

Why doesn't this work: Enumerate all strings x. If x encodes the valid derivation of B from A, accept. If x encodes the valid derivation of ~B from A, reject.

Because of completeness, eventually this process will stumble across an x which is either a proof of B or ~B from A. If B, then A implies B in all interpretations. If ~B, then it is not the case that A implies B in all interpretations. So FOL is decidable. But it's not, so I must have the wrong definition of either completeness or decidability.

  • For some reason, I think that "It is not the case that B can be derived from A" implies "~B can be derived from A." I think that's where I'm misunderstanding completeness. That's clearly not true, because when A is {R(x)} and B is S(x), there there exists an interpretation in which A are true and B is false, and in which A are true and B is true. So neither B or ~B can be proven from A. – Taylor Hornby Aug 28 '14 at 15:26
  • So, is this a better understanding? There's a procedure that will tell us, supposing either (1) B is implied by A in every interpretation or (2) ~B is implied by A in every interpretation, which of (1) or (2) is the case, but in the case where neither (1) or (2) or true, there is no procedure for deciding if B is true in a specific interpretation. – Taylor Hornby Aug 28 '14 at 15:41
  • 1
    This is not an issue of philosophy but of mathematics. Therefore, this should be on Computer Science (because computability is part of CS) or maybe Mathematics. – Raphael Apr 1 '15 at 11:48
  • @Raphael Properties of logics are being discussed repeatedly in entries in the Stanford Encyclopedia or Philosophy, like here: The Completeness Theorem or in books like "The Blackwell Encyclopedia of Philosophical Logic". So, yes, "philosophy". – David Tonhofer Mar 11 '17 at 13:07
  • 1
    @DavidTonhofer Maybe I don't understand what Philosophy is, but I didn't think it included a lot of mathematical, rigorous definitions. Unlike this question and its answer, which are all about such definitions. – Raphael Mar 11 '17 at 13:33

NO, completeness of first-order logic does not imply decidability.

You are mixing two use of completeness.

The first use regards the completeness of "standard" proof systems for first-order logic.

This is Gödel's Completeness Theorem, that says :

The completeness theorem says that if a formula is logically valid then there is a finite deduction (a formal proof) of the formula.

Gödel's completeness theorem says that a deductive system of first-order predicate calculus is "complete" in the sense that no additional inference rules are required to prove all the logically valid formulas. A converse to completeness is soundness, the fact that only logically valid formulas are provable in the deductive system. Together with soundness (whose verification is easy), this theorem implies that a formula is logically valid if and only if it is the conclusion of a formal deduction.

It is easily generalized to the relation of logical consequence between a set Γ of first-order formulas and a formula φ, in symbols :

Γ ⊨ φ.

In this case we have that :

Γ ⊨ φ iff Γ ⊢ φ (i.e. φ is provable from Γ).

For simplicity, we will consider the case when Γ is the emptyset; in this case we have the previous version :

⊨ φ (i.e. φ is valid) iff ⊢ φ (i.e. φ is provable).

Your fallacy regards the "basic property" of validity :

it is not true that if φ is not valid then ¬φ is valid.

Consider the formula :

∃x∃y ¬(x = y).

It means : "there are at least two thing x and y such that they are not equal". This formula is not true in a universe with only a single element. Thus, it is not valid (validity means : true in every universe).

Its negation is :

¬∃x∃y ¬(x = y)

which amounts to :

∀x∀y (x = y).

It means "all things are equal". Neither this formula is valid, because it is not true in a universe with more than one element.

Compare with propositional logic, where a valid formula is called a tautology (the negation of a tautology is called a contradiction : a formula which is always false).

In this case, we have a decision procedure : the truth-table algorithm (it is highly "inefficient", but it works ...).

Apply it to a formula A whatever : if in its column you have all "T", then the formula is a tautology.

Also in this case there is a completeness theorem : if A is a tautology, we can find a proof of it in the "usual" proof systems, like Natural Deduction.

But note that also in this case it is not true that, for a formula A whatever, A is a tautology or ¬A is.

The formula :

p V q

is neither a tautology nor a contradiction.

The second meaning of completeness regards theories, and is the key to the famous Gödel's incompleteness theorems which says that :

The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an "effective procedure" (e.g., a computer program, but it could be any sort of algorithm) is capable of proving all truths about the relations of the natural numbers (arithmetic). For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system.

This (negative) result concerns another aspect of intuitive "completeness" (in the sense of adequacy) : for a mathematical theory, like arithmetic or set theory, it is a reasonable expectation that the axioms (formalized with first-order logic) are able to "capture" all the mathematical truth expressible in that theory.

For most of "little bit complex" mathematical theories, this is not possible.


Decidability is linked to the second meaning of completeness.

If a theory T is complete (in the second sense, plus a second "technical" condition : effectively axiomatized), i.e. T is able to prove all true sentences φ expressible in the language of the theory, due to the fact that either φ is true in T or ¬φ is true in T, then T is decidable.

[Note. If we consider the two formulae above, and we consider their meaning regarding the single arithmetical interpretation, now we have that one of them is true and the other is false. Due to the fact that there are infinite natural numbers (and so, more than one), we have that the formula : ∃x∃y ¬(x = y) is true in the arithmetical interpretation (consider e.g. 1 and 2), while its denial ∀x∀y (x = y) is obviously false (not all numbers are equal)].

Going back to decidability, why a complete theory is so ?

Exactly because the "procedure" described in your question works : start proving theorems in T. After a finite amount of time, if φ is true, you will find the proof of it; if it is not, then ¬φ is true and you will find a proof of it.

As said before, this "procedure" does not work for validity because it is not true that either a formula or its denial are valid.

Gödel's incompleteness theorem proves that formalized theories having enough "capability" for expressing arithmetical facts are not complete in the second sense : they are not able to "capture" all true arithmetical facts.

Thus the above theories are not decidable.

What is the "link" between the two uses of completeness ?

Consider a first-order theory T which include the language of arithmetic.

The "underlying" f-o logic is complete (first sense) : i.e. it is able to prove all logical consequences of the axioms of the theory T.

But the theory T is incomplete (according to Gödel's incompleteness theorem), i.e. there is a true arithmetical sentence φ not provable from the axioms of T.

So what ?

It is not a contradiction. Consider the def of logical consequence applied to T :

T ⊨ φ iff φ is true in every model of T.

Being φ true in the "intended model" of arithmetic (the "usual" numbers) we conclude that it is not true in some other model [see Francis Davey's comment]: there are non-standard model of arithmetic.

Being so, it is not a logical consequence of the axioms of T and this is the reason why its unprovability in T does not conflict with the completeness of the underlying logic.

| improve this answer | |
  • 2
    Does it follow that a Gödel sentence is true in some interpretations, but false in others? – Theodore Norvell Aug 28 '14 at 21:15
  • 5
    Yes, that is exactly right. It demonstrates that there are non-standard models of arithmetic. – Francis Davey Aug 28 '14 at 21:48
  • 2
    Thanks, it's starting to make a lot more sense. I was confusing the two different completenesses. So, the first means: if a formula is valid (true in every interpretation), then it is provable. Decidability is about whether a formula is true in a specific interpretation, which is possible without it being valid. The second meaning of "completeness" is used in a claim within a specific (but arbitrary, therefore generalizable) set of axioms. – Taylor Hornby Aug 28 '14 at 23:23
  • Is it possible for a system to be complete by the first meaning, but have interpretations which are incomplete by the second meaning? Or am I comparing apples to oranges by asking that question? – Taylor Hornby Aug 28 '14 at 23:26
  • 1
    The second meaning of 'complete' (that there exist closed sentences that are not provable and whose negations are also not provable) applies to theories, not to interpretations. – Theodore Norvell Sep 2 '14 at 18:34

Since Taylor Hornby already self-corrected the definition of completeness (thanks to Mauro ALLEGRANZA's first definition), I just want to point out where exactly his reasoning goes astray.

Why doesn't completeness imply decidability for first order logic? Taylor Hornby reasons as follows:

Why doesn't this work: Enumerate all strings x. If x encodes the valid derivation of B from A, accept. If x encodes the valid derivation of ~B from A, reject.

Because of completeness, eventually this process will stumble across an x which is either a proof of B or ~B from A. If B, then A implies B in all interpretations. If ~B, then it is not the case that A implies B in all interpretations. So FOL is decidable.

what is wrong here is the sentence:

Because of completeness, eventually this process will stumble across an x which is either a proof of B or ~B from A.

Completeness by definition means "If B is logically entailed, then B is provable." It is a conditional statement. Now, in general, we do not know whether a given B is logically entailed or not in advance. So we do not know whether there is a proof of B or not. So what really happens is this:

eventually this process will stumble across an x which is either a proof of B or ~B from A, OR this process will continue to run forever.

That is, this algorithm does not always determine whether B is logically entailed (or equivalently, whether B is provable, thanks to the properties of soundness and completeness of FOL). If either B or ~B is provable, we will eventually find its proof. But if neither B nor ~B is provable then we can never tell whether there is no proof or whether we just need to keep looking. So this algorithm does not give us an answer for every B, but we can ask whether there is a better algorithm that does give us an answer for every B. Turing's halting problem is used to show that there is no algorithm for determining whether B is logically entailed.

First-order logic is complete because all entailed statements are provable, but is undecidable because there is no algorithm for deciding whether a given sentence is or is not logically entailed.

| improve this answer | |

There are ultimate limits to machines, no matter how cleverly they are designed. In 1936, Turing proved mathematically that a general algorithm to solve the problem for all possible program-input pairs cannot exist, ever. That is, no algorithm can be written such that it will always correctly decide, for any given program-input pair, whether the program will or will not halt. In computer science, this is called the halting problem. Turing proved that any algorithm can be made to contradict itself and therefore cannot decide correctly. As an illustration, we may make use of a “pathological” program-input pair designed to do the opposite of what the algorithm predicts it will do.

Turing’s proof implies that it is impossible to predict if the Turing machine programmed to attack certain mathematical problems will ever succeed and come to a halt, or keep on running forever. Actually, an equivalent ultimate limit applies to humans: It is also impossible to predict if mathematicians will ever succeed with regard to solving these same problems.

The crucial question concerns completeness and decidability (as to whether a theorem is either true or false, but not both), which is equivalent to the halting problem in computing science. Incompleteness opens the door to the possibility of undecidability. A successful proof of a particular problem implies that it is not undecidable in the theory (or system) where it is formulated. But such a proof does not imply that the theory itself is complete or decidable. There may be other problems in the theory that are undecidable, in which case no solution exists. In an incomplete theory, there are theorems or equations, for instance, that appears to intuitively true but are unprovable. Therefore, it is impossible to predict if a particular problem formulated in an incomplete theory can ever be solved. Never before in the history of human knowledge has an ultimate limit to predictability been stated with such clarity, with the help of logician-mathematicians in the 20th century.

| improve this answer | |

I'm pretty sure this is correct, but not 100% confident:

One possible confusion is that we may think we are talking about a single model, when we're really talking about all possible models that satisfy a particular set of axioms. So if we are talking about one model, then P or NOT P is true, but if we are talking about multiple then P may be valid, NOT P may be valid or it may be mixed (here valid = always true).

Completeness means that if P is valid we'll prove it eventually and since NOT P is just another proposition, if it is valid same for that. However, this doesn't guarantee anything about the mixed propositions. We can never know that if we didn't just keep looking for longer that we wouldn't find a proof for P or for NOT P.

Or to clarify even more, the following two claims are different:

  • "NOT P" is valid
  • NOT "P is valid"

The later also includes P being mixed

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.