G7. Can insufficiently strong formal systems be both consistent and complete?
Yes1. We’ve actually already seen an example of this. The Add system first introduced in G1. What is a formal system? and analyzed more thoroughly in G5. Soundness, Consistency, and Completeness . However, I can come up with an even more trivial example. Consider the following system:
The True system:
- Alphabet: \(True\), \(False\)
- Grammar:
- The only valid formulas are either \(True\) and \(False\)
- Transformation rules: None
- Axioms: - \(True\)
I think you can guess my intended interpretation for these “symbols”. This system is so incredibly trivial that we can enumerate all formulas (\(True\), and \(False\)) as well as all theorems (\(True\)).
Is this system sound? Unquestionably yes. All theorems are “true” in the standard interpretation. The only theorem is literally the symbol \(True\), which stands for true.
Is this system consistent? Yes. I am quite certain that this system cannot derive a contraction, as there is only one theorem.
Is this system complete? Again, yes. Every true formula that is expressible in the system (which is just the formula \(True\)) is a theorem.
Hopefully this trivial example makes it clear that weak formal systems can quite easily be sound, consistent, and complete.
Are there more interesting examples of systems that are sound, consistent, and complete? Yes, many. You may not know that before Godel proved his incompleteness theorem, he first proved Godel’s completeness theorem which proved that propositional logic is, in fact, (semantically) complete!
-
A rare exception to Betteridge’s law of headlines ↩