10.2 Informal Proofs
Last section you learned that a proof is a step-by-step demonstration of validity or invalidity.
That means every proof has steps.
Consider a proof of this argument:
1. Pia and Quinn are guilty.
2. Pia is guilty.
How many steps does this proof have?
Proof: Since Pia and Quinn are both guilty, we know Pia must be.
The simplest sort of proof has a single step, like that one.
That inference was so obvious, we couldn't break it down into more steps. The proof just consisted of explaining why the simple inference of the argument is valid.
We said that every step of a proof must be obvious. But what if that inference still isn't obvious to your audience?
The answer is that there are certain baby steps that are maximally obvious, so if your audience doesn't follow them, that's the audience's fault, not yours.
This example proof is like that: if someone understands the word "and", they should be able to follow this proof.
Most proofs, though, will have more steps and require you to figure out how to make the inference obvious for your audience.
The steps of a proof often break the argument into smaller inferences, which combine to lead to the final conclusion.
When we make a smaller inference in the middle of a proof we create an intermediary conclusion, which is an inferred sentence different from the final conclusion that will be used to reach the final conclusion.
For example, recall the good proof from last section:
Proof: Every 3-by-3 box must have a 2, so the 3-by-3 box on the middle-right, where the question mark is, needs a 2 in it. We can see that the row above the question mark already has a 2 over on the left. And there are 2s in the columns to the left and right. That means a 2 cannot go in any of the other squares in the box, and thus 2 must go where the question mark is. Done.
Informal proofs can have other parts as well, besides intermediary conclusions. Here are the most common parts of a proof:
- Opening: stating "proof" at the start to clarify what you're doing.
- Restating a premise.
- Justifying an inference.
- Stating an intermediary conclusion.
- Stating the final conclusion.
- Closing: stating "done" or "Q.E.D." or ∎.
Not every proof has all of these parts. For example, declaring your intentions by starting with "proof" isn't always done.
But in this book we'll teach you to crate informal proofs in a consistent way: always start by saying "proof", and end by saying "done" (or one of the other closings).
"Q.E.D." is a fancy Latin way of saying "done", and ∎, called the tombstone symbol, is further shorthand for the same thing.
Let's look at a more complicated example, and see if you can identify the parts. Here's an argument based on a famous inference of Darwin's from 1862:
1. Every species of orchid has a pollinator.
2. Only a moth could pollinate Angraecum sesquipedale (AS, for short).
3. No known moth could pollinate AS.
4. AS is a type of orchid.
5. There exists an unknown moth that pollinates AS.
Here's a proof for this argument:
Proof: We know that AS is a type of orchid (premise 4), so AS must have a pollinator (from premise 1). Since it has a pollinator, the pollinator must be a moth (from premise 2). That moth cannot be known (from premise 3), so there must be an unknown moth pollinator for AS. Done.
Let's see if you can label the parts of this proof.
Lastly, another important fact about proofs can be seen by this example: let's say we augment Darwin's argument with one more premise:
0. AS is native to Madagascar.
And say we give the same proof as before.
The last fact is this: a proof does not need to use every premise in the argument.
Sometimes the conclusion follows from a subset of the premises. In that case, just ignore the premises you don't need.