Why it works
The core ideas behind every proof. Read this first: once these make sense, the strategies stop being rules to memorise and become things you could work out yourself.
On this page
1What a proof promises
An argument is valid when there is no possible situation where all the premises are true and the conclusion is false. A proof is a way to show validity without checking every situation.
It works by taking small steps. Each rule is chosen so that it can never take you from true lines to a false one. So if every step follows a rule, the truth of the premises carries through, step by step, all the way to the conclusion.
This is why you can't skip steps or use a rule "almost right". The guarantee only holds if every link in the chain is one of the safe ones.
Check yourself
Why is there no rule "from A → B and B, infer A"?
Because it isn't safe. "If it rains, the street is wet" and "the street is wet" can both be true while it isn't raining (someone washed the street).
2Building and taking apart
Every connective has two kinds of rule:
- Elimination rules (E) use a sentence you already have, taking it apart. From A ∧ B, ∧E gives you A.
- Introduction rules (I) build a sentence you want. From A and B, ∧I gives you A ∧ B.
So a proof usually works from both ends at once: eliminate to see what your premises give you, and introduce to build the goal.
Check yourself
What is the main connective of (A ∨ B) → ¬C, and which rule would build it?
→, so →I.
3Assumptions are "what if" boxes
Some things can't be shown in one direct step. To show "if A then B", you need to say: suppose A were true; then B. That "suppose" is an assumption, and the lines that follow it sit in a subproof, drawn with its own vertical line.
Think of a subproof as a box labelled "what if". Inside the box you may use the assumption as if it were true, along with anything from outside the box that is still open. But nothing inside the box has been shown to be actually true. It's only true if the assumption is.
You can assume anything. Assuming isn't claiming. The real question is whether the assumption lets you close the box with a useful result. Only four rules close a box (next section), and each one fixes what the assumption must be. So choosing an assumption is really choosing which box-closing rule you will use.
Check yourself
Inside a box you assumed P and reached Q. After the box closes, can you write Q on its own?
No. You only showed Q if P. What you can write is P → Q.
4The four rules that close a box
→I: conditional proof
If supposing 𝒜 leads to ℬ, then "if 𝒜, then ℬ". That is simply what "if… then" means.
¬I: proof by contradiction
If supposing 𝒜 leads to a contradiction, 𝒜 can't be true. So ¬𝒜. The box shows that this exact assumption fails, so the result is the negation of exactly that assumption.
IP: indirect proof
The mirror image: if supposing ¬𝒜 leads to a contradiction, ¬𝒜 fails, so 𝒜. (¬I alone would only give ¬¬𝒜; IP lets you go straight to 𝒜.)
∨E: proof by cases
You know 𝒜 or ℬ, but not which. If 𝒞 follows either way, then 𝒞. "It's raining or snowing; either way I need a coat; so I need a coat."
Notice that each rule tells you exactly what to assume:
| To get… | use | so you must assume… | and reach… |
|---|---|---|---|
| 𝒜 → ℬ | →I | 𝒜 | ℬ |
| ¬𝒜 | ¬I | 𝒜 | ⊥ |
| 𝒜 | IP | ¬𝒜 | ⊥ |
| anything, from 𝒜 ∨ ℬ | ∨E | 𝒜, then ℬ (two boxes) | the same goal in both |
That table is the strategy card. It isn't a list of tricks; it falls out of what each rule needs.
Check yourself
You assumed ¬A and reached ⊥. You want ¬(A → B). Can ¬I give it to you?
No. ¬I gives the negation of the assumption, so here ¬¬A. To get ¬(A → B) by ¬I, the assumption must be A → B.
5⊥ and explosion
⊥ means "contradiction": you have a sentence and its negation, both in force (¬E). It's a sentence that can never be true.
X (explosion): from ⊥, you may write any sentence at all. That sounds like cheating, but remember what a rule promises (section 1): if the lines above are true, the new line is true. ⊥ is never true, so the promise can't be broken. Whatever you write, nothing can go from true to false.
Check yourself
Inside a box you have P and ¬P, and you need Q. How?
⊥ by ¬E, then Q by X.
6Why "if" behaves so oddly
In logic, 𝒜 → ℬ makes only one promise: it is never the case that 𝒜 is true and ℬ false. It is false in that one row, and true in every other.
| 𝒜 | ℬ | 𝒜 → ℬ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Two tricks follow directly from this table:
- Free conditional. If you already have ℬ, then 𝒜 → ℬ is true whatever 𝒜 is: the "false" row needs ℬ false. In a proof: assume 𝒜, reiterate ℬ, →I.
- Explosion conditional. If you have ¬𝒜, then 𝒜 → ℬ is true whatever ℬ is: the "false" row needs 𝒜 true. In a proof: assume 𝒜, clash with ¬𝒜, ⊥, X gives ℬ, →I.
Check yourself
You have ¬P. Is P → Q true?
Yes. P is false, so the only "false" row (P true, Q false) can't happen.
7How to find the first assumption
- Find the main connective of the goal.
- If the main connective is →, assume the antecedent. Use rule →I.
- If the main connective is ¬, assume the sentence after the ¬. Use rule ¬I.
- If the goal is a disjunction and you have one of its parts, use rule ∨I. You do not need an assumption.
- If the goal is a letter, or a disjunction without a part that you have, assume its negation. Use rule IP.
- Examine the premises. Find what each premise needs:
- A premise 𝒜 → ℬ needs 𝒜.
- A premise ¬𝒜 needs 𝒜. Together, they give ⊥.
- A premise 𝒜 ∨ ℬ needs two subproofs (rule ∨E).
- Make the sentence that the premise needs your new goal. Go back to step 1.
8Common misunderstandings
- "Assuming something means I believe it." No. It means "let's see what would follow". Many good proofs assume something false on purpose, to show that it fails.
- "¬I proves the opposite of whatever I was thinking about." No. It proves the negation of the exact sentence you assumed, nothing else.
- "Once I've written a line, I can use it anywhere." Only while its box is open. Lines in a closed box were only true "what if".
- "There's a rule for 'from A → B and ¬B, infer ¬A'." Not as a basic rule (that's modus tollens). You have to show it: assume A, use →E to get B, clash with ¬B, ¬I.
- "Every assumption should be used." Not always (the free conditional doesn't use its assumption). But if an assumption is never cited inside its box, ask whether the box is doing anything.