What exactly is the value of completeness and decidability in logic?

Question

I understand why consistency and soundness are important. It would undermine the purpose of reasoning if we can make conclusions that contradict our assumptions. At some level, when we desire to formalize our arguments, we are looking to make sure that we are treating the same forms of reasoning the same way.

With soundness, we just want to ensure that, based on the model, that every conclusion that we may derive according to the system is true. I don't really understand what it means for a formal system to be unsound though: Either it means that it is the wrong model for the proof calculus, or it means that there can be no consistent model for the proof calculus. Any clarification here would be appreciated.

But I don't really understand the value, at least for philosophical logic, of completeness and decidability. An incomplete formal system would have truths that can't be proven. This seems sensible to me, for the same reason that there are truths about the world that we will never be able to prove, like the existence of a flower in a forest fire.

Similarly for decidability. What I've been able to pull up online seems concerned about decidability in the context of theorem proving software and artificial intelligence. Yet, first order predicate logic seems to be used very heavily, even in philosophy, yet it is known to be undecidable. I would think that second-order logic would be even more useful for philosophy, as many propositions, like the identity of indiscernibles and the principle of sufficient reason, can really only be expressed in second order logic.

So why is it so important that formal logic systems be complete and decidable?

Answer 1

But I don't really understand the value, at least for philosophical logic, of completeness and decidability. An incomplete formal system would have truths that can't be proven. This seems sensible to me, for the same reason that there are truths about the world that we will never be able to prove, like the existence of a flower in a forest fire.

As you point out it's obvious that there truths that you can't prove. Gödel's achievement was to introduce formal methods that prove that. In fact what he showed is that there are statements which cannot be shown to be either true or false, which is a little different from the 'obvious' statement. It's the introduction of new methods and new questions into mathematics that was important.

Decidability is important in the context of computation - when one can think that time has been introduced into logic - one obviously wants an answer to a question in a finite amount of time.

There is another notion of decideability that is used in Gödel's incompleteness theorem, which would be better named Gödel's undecidability theorem - that a statement is undecidable if we cannot show it has a proof or disproof.

So why is it so important that formal logic systems be complete and decidable

It's important that a formal logical system be both sound and complete. That is what we can prove is always true, and what is true we can always prove. This seems like a good property for a formal system to have, on a commonsense level - but one should also understand what are the consequences that follow of having this property, that, unfortunately I can't say.

It follows from Godels undecidability/incompleteness theorem that useful formal systems will always be undecidable.

Second order logic is not complete with standard semantics, but it can be made to be so with Henkin semantics. It is of philosophical interest, for example the SEP has entry on it - it's just not as popular as first-order. In fact because the power-set operation is expressible, Quine argued that 2nd order logic is simply set theory in disguise, and additional evidence for this is that typed higher intuitionistic logic is the internal language of a generalised set theory, and that higher classical logic can be coded into second order logic. So, if you are going to study 2nd-order logic you may as well study set theory, unless of course you're really interested in the minutiae of 2nd-order logic.

Answer 2

Assume you have a machine that works with some logic, you can make questions and get answers, similarly to this site.

Soundness is the most important property, it means you won't get wrong or misleading answers, that's good.

Decidability means you will get your answers at some point, at least an answer of the type "I don't know", "nobody knows" or "42". You can still die waiting to get an answer, but at least that machine is not working for nothing.

That's very important for computers and AI as you already point out, but it's also important for people. Imagine a PhD student trying to solve an undecidable problem, that may be a level in hell. That's why it's important to know if a problem is decidable and not to try to solve undecidable problems.

Completeness is also an interesting property. Actually Bertrand Russell was kind of trying to do the job of the PhD student I mentioned when he was working on Principia Mathematica and Gödel avoided a life of hell and madness with his theorems. Completeness provides safety in the work of the logician.

It's specially interesting in the case of machines, because an incomplete answer may be a wrong or misleading answer (still sound, but misleading). Think about some health problem and you ask your phone where is the closest hospital, it will search for hospitals in the area and then give you the closest in that list, an incomplete answer means some hospitals may be missing on that list, and those may actually be the closest hospitals. The logic may be sound, those items may be listed as "clinics" and not "hospitals", but people may die because of that.

For all these examples and reasons, soundness, decidability and completeness are important for computers and also for machines.