Topics Logic

Question Hello. What exactly is completeness in logic? What makes some system of logic complete? And what is incompleteness?

Accepted:
November 26, 2009

Comments

The notion of completeness for logics links two notions: A notion of what is provable or deducible in some formal system of logic, and a notion of what is valid, which is itself defined in terms of a notion of interpretation. It's probably best to think of the latter as primary. We have some system of logical notation, and we have a way of interpreting it that gives rise to a class of "valid" formulas. What we'd like to have then is a proof-method that will be complete in the sense that, if a given formula is valid, then it will be provable by that method.

More generally, we can think not just of the class of valid formulas but of some notion of implication or entailment that relates formulas: So we say that some bunch of formulas A, B, C, ... entail some other formula Z. Then what we want is a proof-method that will be complete in the sense that, if Z really does follow from A, B, C, ..., then there is a way of deriving Z from A, B, C, ..., by the proof-method.

You can't always have a complete proof-method in this sense. But if you can have it, then it's a good thing to have.

Question Hello. What exactly is completeness in logic? What makes some system of logic complete? And what is incompleteness? Accepted:November 26, 2009

Question Hello. What exactly is completeness in logic? What makes some system of logic complete? And what is incompleteness?

Accepted:
November 26, 2009