Rule of Substitution

From ProofWiki
Jump to: navigation, search

Theorem

Let $S$ be a sequent that has been proved.

Then a proof can be found for any substitution instance of $S$.


Proof

This is apparent from inspection of the proof rules themselves.

The rules concern only the broad structure of the propositional formulas involved, and this structure is unaffected by substitution.

By performing the substitutions systematically throughout the given sequent, all applications of proof rules remain correct applications in the sequent.



Also known as

Some sources amplify the name to rule of uniform substitution.


Applications

This proof leads on to the Rule of Sequent Introduction.


Technical Note

When invoking the Rule of Substitution in a tableau proof, use the {{Substitution}} template:

{{Substitution|line|pool|statement|depends|instance 1}}
{{Substitution|line|pool|statement|depends|instance 1|substitution 1}}
{{Substitution|line|pool|statement|depends|instance 1|substitution 1|instance 2|substitution 2}}
{{Substitution|line|pool|statement|depends|instance 1|substitution 1|instance 2|substitution 2|instance 3|substitution 3}}

where:

line is the number of the line on the tableau proof where the Rule of Substitution is to be invoked
pool is the pool of assumptions (comma-separated list) of the statement on which the Rule of Substitution is to be used
statement is the statement of logic that is to be displayed in the Formula column, without the $ ... $ delimiters
depends is the line of the tableau proof of the statement on which the Rule of Substitution is to be used
instance 1 is that which is being substituted
substitution 1 is what it is being replaced with

Optionally you can perform up to $3$ substitutions:

instance 2 is that which is being substituted: instance 2
substitution 2 is what it is being replaced with: instance 2
instance 3 is that which is being substituted: instance 3
substitution 3 is what it is being replaced with: instance 3.


Sources