Consistency and Completeness
You've already invested a great deal of time and energy learning the
portion of Deductive Logic called Propositional Logic. We've covered enough
territory that we're now in a position to make some observations about logic
itself. In particular, logicians are very interested in the relationship
between semantics and proof theory. We emphasized that they are two
distinct branches of propositional logic. But it would be odd, at best, if they
were completely unrelated. Happily, there are important close
relationships between these two branches, expressed in terms of consistency and
completeness.
The only proofs we can construct in PL are proofs corresponding to valid arguments. If we attempt to prove an invalid argument, such as:
| (S ⊃ Q) |
| Q |
| S |
we will fail. There's no way to derive S from the premises. When all provable arguments are valid, a logic is said to be consistent. Another way of stating consistency is this: If a wff can be derived from a set of premises, then the corresponding argument is valid.
Completeness expresses the relationship between provability and validity in the other direction. A system of logic is said to be complete if and only if all valid arguments are provable. In a complete system, if an argument is valid, then there is a derivation of the conclusion of that argument from its premises.
What about theorems? Remember that a tautology can be understood as a valid argument with no premises. There's no way to make the premises all true and the conclusion false. A theorem is a wff which can be proved from no premises. So if our logic is consistent, any theorem must be a tautology. If our logic is complete, then all tautologies are theorems.
In texts in metalogic, the symbol "├ " is often used to express the relation of proof between premises and a conclusion. So the statement:
A1....An ├PL B
means "There is a proof of B from A1....An in PL
The phrase:
A1....An ╞PL B
means that the argument with A1....An as premises and B as conclusion is a valid argument in PL.
Now we can state consistency and completeness very succinctly:
A1....An ├PL B iff A1....An ╞PL B means "PL is consistent and complete."
We've boldly stated that PL is consistent and complete. We haven't proved that it is. In order to prove that PL has these two features, we would have to enter into a branch of logic called "metalogic." Metalogic is the logic of logic, where we actually prove things about logic itself! It's a grand and exciting field, but beyond the scope of this introductory course. Once you've worked through this text, however, you will be ready for a course in metalogic.
To test your knowledge of the metalogical notions of consistency and completeness, complete this exercise!
Need more practice with proofs? Here you are! and here!
 |
 |