Back to the on-screen lesson ·
Assuming an antecedent to derive a consequent, discharging the assumption, and the theorem that says why the finished conditional rests on the premises alone.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to lay out a conditional proof in order, say which lines rest on the assumption and which do not, state what discharging entitles you to write, test an argument with a conditional conclusion semantically, state the deduction theorem, and recognise when the chain rule reaches the same conclusion without an assumption.
You can plan a derivation from the shape of its conclusion. When that conclusion is a conditional and no two premises chain into it, the rules met so far have nothing to offer, and this lesson supplies what is missing.
An assumption is a line supposed rather than asserted, made in order to be given up. To discharge it is to give it up, writing a conditional whose antecedent is the assumption. A subproof is the stretch of lines while an assumption is in force. The deduction theorem is the fact that makes the move legitimate.
To prove $\phi \to \psi$: write $\phi$ as an assumption, derive $\psi$ using it and the premises, then discharge the assumption and write $\phi \to \psi$. Two things make this work. First, the bookkeeping: every line derived while the assumption is in force rests on it, and the discharged conditional is the only line that does not — which is why $\psi$ itself may not be carried outside. Second, the deduction theorem: $\Gamma \cup \{\phi\} \vdash \psi$ exactly when $\Gamma \vdash \phi \to \psi$. On the semantic side the same equivalence holds for $\models$, and it is easy to see why: restricting attention to the rows where $\phi$ is true is exactly what a conditional conclusion asks for. Assumptions may be nested — a conclusion with two arrows needs two of them — and each discharge removes one, in the reverse of the order they were made.
Another way: steps
Another way: example
Premises $P \to Q$ and $Q \to R$; goal $P \to R$. Assume $P$; modus ponens twice gives $R$; discharge to get $P \to R$. The chain rule does the same thing in one line, and is what conditional proof generalises.
The first error is carrying a line out of the subproof: $\psi$ was derived on a supposition and does not survive the discharge, only $\phi \to \psi$ does. The second is treating the assumption as a premise, so that the finished proof quietly claims something nobody granted. The third is discharging in the wrong order when assumptions are nested, which produces a conditional with its halves in the wrong places.
Goal $\neg P \to R$, premises $P \vee Q$ and $Q \to R$. Assume $\neg P$.
Assume the antecedent.
Disjunctive syllogism gives $Q$, and modus ponens gives $R$.
Work inside the subproof.
Discharge: $\neg P \to R$, resting on the two premises and on nothing else.
The assumption is given up.
Goal $P \to (Q \to R)$, premise $(P \wedge Q) \to R$. Assume $P$; the goal becomes $Q \to R$.
The goal is still a conditional.
Assume $Q$ as well. Now $P \wedge Q$ is available, and the premise gives $R$.
Assume again, inside.
Discharge $Q$ to get $Q \to R$; discharge $P$ to get $P \to (Q \to R)$.
Last assumed, first discharged.
Assume $P$. With the premise $Q$ also available, conjunction introduction gives $P \wedge Q$.
Discharge the assumption: $P \to (P \wedge Q)$, resting on $Q$ alone.
These are the six lines of a conditional proof, shuffled. Put them in order.
Number the steps in order (write the number in the box):
Here is a finished conditional proof. Mark every line that rests on the assumption.
This task has no paper form; do it on a device.
Inside a conditional proof you assumed $P$ and, using the premises, derived $R$. What does discharging the assumption entitle you to write?
Premises: P -> Q and R. Conclusion: Q -> P. Does the conclusion follow? If it does not, give a row that breaks it.
P -> Q
R
∴ Q -> P
valid invalid — countermodel:
Match each kind of line in a conditional proof to what it rests on.
| Granted throughout, and never given up | Supposed rather than asserted, and later given up | The premises together with the assumption | The premises alone | |
|---|---|---|---|---|
| A premise | ||||
| The assumption | ||||
| A line derived while the assumption is in force | ||||
| The line written at the discharge |
Premise: (P & Q) -> R. Conclusion: P -> (Q -> R). Does the conclusion follow? If it does not, give a row that breaks it.
(P & Q) -> R
∴ P -> (Q -> R)
valid invalid — countermodel:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
From the premises P -> R and R -> S, derive P -> S without assuming anything. Give one line at a time, with the rule and the lines it uses.
P -> R
R -> S
∴ P -> S
| # | Formula | Rule | Lines |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 |
You can build and read a conditional proof and say what each line rests on. Say in your own words why the formula derived under an assumption cannot be carried out of the subproof.
8. Your turn: from $Q$, prove $P \to (P \wedge Q)$, step 2