In logic and computer science, soundness and completeness are two fundamental properties of a formal system (a set of rules for proving things).
They describe the relationship between Provability (can the system prove it?) and Truth (is it actually true?).
Here is the simple breakdown:
1. Soundness: “Everything you prove is true.”
A system is sound if it never lies to you. If the system produces a proof for a statement, that statement must be valid.
- The Direction: Proof $\rightarrow$ Truth.
- The Fear: You don’t want False Positives. You don’t want the system to tell you something is true when it is actually false.
- Intuition: A sound system is an “honest” system. It might not know everything, but what it does tell you is correct.
2. Completeness: “Everything true can be proven.”
A system is complete if it doesn’t miss anything. If a statement is true, there exists a proof for it within the system.
- The Direction: Truth $\rightarrow$ Proof.
- The Fear: You don’t want False Negatives. You don’t want there to be a truth out there that your system is incapable of discovering.
- Intuition: A complete system is an “all-knowing” system. It is powerful enough to derive every single valid truth.
Formal Notation (Logic)
In formal logic, we use two symbols:
- $\vdash$ (Turnstile): Means “It is provable” (syntactic).
- $\vDash$ (Double Turnstile): Means “It is true/valid” (semantic).
Let $P$ be a proposition (a statement).
- Soundness: If $\vdash P$, then $\vDash P$.
- Completeness: If $\vDash P$, then $\vdash P$.
Why does this matter?
Ideally, we want logical systems that are both sound and complete. We want to trust our proofs (Soundness) and we want to be able to prove all truths (Completeness).
However, the famous Gödel’s Incompleteness Theorems proved that in any mathematical system complex enough to do basic arithmetic, you cannot have both. If the system is Sound (consistent), there will always be true statements that cannot be proven (it will be Incomplete).