Soundness in logic is the property that formal derivations preserve semantic correctness: whenever a conclusion can be proved from given premises, it is true in every interpretation in which those premises are true. Soundness connects the syntactic rules of a formal system with the meanings assigned to its expressions. In a related but distinct usage, an individual argument is called sound when it is logically valid and all its premises are true.
Formal definition
Let be a set of premises and a formula. Write
to mean that there is a formal proof of from in a specified deductive system. Write
to mean that is a semantic consequence of : every interpretation satisfying all formulas in also satisfies .
The deductive system is sound for its semantics if, for every appropriate and ,
Thus, syntactic derivability never exceeds semantic consequence. A sound system cannot derive a conclusion that is false in an interpretation satisfying its premises.
For propositional logic, interpretations are assignments of truth values to propositional variables. For first-order logic, interpretations are structures specifying a domain and interpretations of the nonlogical symbols. When formulas contain free variables, satisfaction also depends on an assignment of domain elements to those variables.
Soundness is therefore always relative to a specified semantics. A collection of inference rules is not sound or unsound independently of how its formulas and consequence relation are interpreted.
Weak and strong soundness
The premise-sensitive condition above is often called strong soundness. Weak soundness concerns only theorems, which are formulas derivable without premises:
Here means that is logically valid: it is true in every interpretation admitted by the semantics.
Strong soundness implies weak soundness by taking to be empty. The converse is not automatic for an arbitrary proof system, although standard systems often provide ways to connect the two. Terminology varies, and many presentations simply use “soundness” for the premise-sensitive result.
Sound arguments and sound proof systems
The soundness of an argument must be distinguished from the soundness of an entire deductive system.
An argument is valid if there is no interpretation in which all its premises are true and its conclusion is false. It is sound if it is valid and its premises are in fact true.
For example:
- Every integer divisible by is even.
- is divisible by .
- Therefore, is even.
This is a sound argument under the usual interpretation of integers and divisibility.
By contrast:
- Every prime number is odd.
- is prime.
- Therefore, is odd.
The second argument has a valid form, but it is not sound because its first premise is false: is a prime number that is not odd. Its conclusion nevertheless happens to be true.
A sound deductive system does not guarantee the actual truth of arbitrary premises supplied to it. It guarantees that its derivations do not introduce a false conclusion when the premises are true. Consequently, a false premise used in an otherwise correct proof does not show that the underlying proof system is unsound.
How soundness is proved
A soundness theorem is proved in a metatheory: a mathematical setting in which formulas, derivations, and interpretations can be studied as objects. It is a central result connecting proof theory with model theory.
For many proof systems, the proof has two main components:
- Show that every logical axiom or axiom instance is valid.
- Show that each rule of inference preserves the relevant semantic consequence relation.
An application of mathematical induction to the length or structure of a derivation then establishes soundness for all derivations.
Example: modus ponens
The rule of modus ponens is
Under classical semantics, if and are both true in an interpretation, then must be true in that interpretation. Thus, if both premises are semantic consequences of , so is .
A proof system consisting of valid logical axioms and sound rules such as modus ponens can therefore be shown sound by checking every line of a proof.
Assumptions, discharge, and side conditions
In natural deduction, some rules discharge assumptions. Their soundness must be formulated in terms of the relationship between open assumptions and conclusions, rather than simply as truth preservation between displayed formulas.
For example, implication introduction moves from a derivation of under an additional assumption to a derivation of with that assumption discharged.
Quantifier rules require particular care. A standard universal-introduction rule permits an inference of the form
only when is not free in any undischarged assumption in . Without this restriction, one could move illegitimately from a premise to : the fact that one assigned object has a property does not imply that every object has it.
Comparable soundness proofs for sequent calculi proceed by induction on derivation trees. The details depend on the meanings of sequents and on the structural and logical rules available.
Relation to completeness
Soundness and completeness concern opposite directions of the connection between proof and semantics:
| Property | Formal condition | Meaning |
|---|---|---|
| Soundness | Everything derivable is semantically warranted. | |
| Completeness | Every semantic consequence is derivable. |
When both hold,
Standard classical propositional calculi are sound and complete for truth-value semantics. Standard classical first-order calculi are sound and complete for ordinary first-order semantics; the completeness direction is established by Gödel’s completeness theorem, first proved in 1929 and published in 1930.
A system may be sound without being complete. For example, a propositional calculus with no axioms and no rules beyond allowing premises derives only formulas already among its premises. It is sound, but it cannot prove even elementary valid formulas from no premises.
Soundness and completeness also depend on the chosen class of interpretations. The same calculus may have different properties when evaluated against different semantics.
Relation to consistency and satisfiability
A theory is syntactically consistent, in a common classical formulation, if it does not derive a contradiction. It is satisfiable if it has at least one model.
If a sound proof system is used and a theory has a model, then is consistent. Otherwise, soundness would require that model to satisfy a contradiction.
However, the soundness of the proof system does not imply that every possible set of premises is consistent. In classical logic, a contradictory set of premises has no model. Consequently,
holds for every when is unsatisfiable: there is no interpretation satisfying that could serve as a counterexample. This is why deriving arbitrary conclusions from contradictory premises does not, by itself, violate classical soundness.
Consistency is also weaker than truth in an intended interpretation. A theory may have models while containing statements false in the particular structure it was intended to describe.
Soundness of a theory in an intended model
When a theory is called sound, the intended claim is often that all its theorems are true in a particular intended structure.
For an arithmetic theory , soundness in the standard structure means
for every sentence .
This requires more than the soundness of first-order logic. Logical soundness guarantees truth in every model of ; it does not independently establish that the standard natural numbers form such a model. If the axioms of are true in , logical soundness ensures that its theorems are true there as well.
Soundness and incompleteness
Gödel’s incompleteness theorems do not contradict the soundness or completeness of first-order logic. The results concern different distinctions:
- Logical completeness concerns truth in every model of a set of premises.
- Arithmetical completeness would require a theory to decide every sentence in its language.
- Soundness in standard arithmetic concerns truth in one particular structure, .
A consistent, effectively axiomatized theory sufficiently strong for arithmetic cannot decide every arithmetical sentence. If such a theory is sound in , it therefore leaves some truths about unproved. This is compatible with first-order completeness: a sentence true in need not be true in every model of the theory.
Soundness proofs are also relative to their metatheoretic assumptions. For sufficiently strong arithmetical theories satisfying the usual hypotheses of the second incompleteness theorem, the theory cannot prove its own standard consistency statement if it is consistent. A suitably formulated internal soundness assertion would imply consistency, so it faces a corresponding limitation.
Other logics and computational uses
Soundness is not restricted to classical truth-value semantics. Intuitionistic logic has soundness results for suitable algebraic and relational semantics. A rule valid under classical semantics may fail under those semantics; the law of excluded middle, for example, is not generally valid intuitionistically.
In formal verification, soundness establishes that properties derived by a verification calculus hold under the mathematical semantics assigned to a program or system. This remains distinct from whether the mathematical model accurately represents a physical implementation.
For an automated theorem prover, soundness means that every claimed theorem is justified by the relevant logic. Completeness is a separate issue: a sound prover may fail to find some proofs. A sound and complete first-order calculus also does not provide an algorithm that always terminates with the correct answer to every first-order validity question. Soundness controls correctness of conclusions, not termination or computational cost.