Lemma·L68
Provability is monotone in the theory
Anything provable from a theory stays provable from any larger theory - and appending one more justified formula to a proof still leaves a valid proof.
For a language
,
, and
: if
then
.
In words
For a theory contained in a larger one, anything the smaller theory proves the larger theory proves too - the same witnessing proof works unchanged.
Rests onno axioms yet
Never needed: F02 · F03 · F04 · F05 · F06 · F08 · F09 · F10 · F11 · F12 · F13 · F14 · A01 · A02 · A03 · A04 · A05 · A06 · A07 · A08 · A09 (computed from the citation graph, not asserted).
Proof
- 1Let be a proof of from . Every entry is justified by one of D104's four clauses: a logical axiom, a member of , modus ponens from earlier entries, or generalization from an earlier entry. The first, third, and fourth clauses do not mention at all, so they justify equally well as a proof from ; the second clause, , gives too, since .
- 2So is also a proof of from , i.e. .
∎
Remarks
The syntactic counterpart of monotonicity of semantic entailment under enlarging the theory (which holds for the same reason, one level up: a model of
is a model of every subset of
, in particular
). Used constantly - most immediately, to combine facts proved from a smaller theory with facts proved from a larger one that contains it, as in modus ponens as a derived rule on provability.