Proof Patterns

Note that this chapter introduces us to the important concept of a proof that we will need throughout the entire course, so pay attention! We will also take some first steps in proving something even more meaningful than statements about logic (though those were also meaningful :)).

Where do proof patterns fit in our big picture of logic and mathematical statements? What is the reason for proof patterns?

Often, we want to prove certain mathematical statements such as $S \implies T$. However, sometimes there is no obvious way to show for example in this case, that if $S$ is true, then $T$ is true. We want to make life easier by showing an equivalent statement that is (not $T$) $\implies$ (not $S$). However, it is not obvious that these two statements are equivalent and it would actually be sufficient to prove the second implication. We need to prove this. A proof pattern is, therefore, just the way we choose to try to prove a certain mathematical statement. A proof pattern is called sound if we can actually prove our statement using it. Thus, in the sense of the equivalence above, the proof pattern would be sound if the equivalence does indeed hold. Obviously, we only want to use proof patterns that are sound. However, this soundness has to be proven first. To prove soundness, we can use propositional logic in easy cases.

After we know that a proof pattern is sound, we can sort of $\emph{use}$ the proof pattern to really prove a meaningful statement.

See the definition of the proof patterns in the script (Chapter 2.6). Here are some exercises about proof patterns (and basic set theory).

Proving Soundness of a proof pattern

Direct implication / Composition of Implications

As an exercise, you can also (easily) prove the above statement with an indirect proof.

Proof by Case Distinction

An example of a proof by case distinction is truth tables; to show that $F \equiv G$, we show that for all possible inputs, the output value of $F$ and $G$ are equivalent.

Indirect Proof of an Implication

To show that $S \implies T$ holds, we show that (correctness follows from the truth table from the previous exercise):

Proof by Counterexample

This is a very simple proof pattern. You only have to find a counterexample to show that a statement is false.

Existence Proof

A special type of an existence proof is the proof by Counterexample; to show that $F$ is not true, we show that "not $F$" is true for some input.

Proof by Contradiction

The proof pattern of a proof by contradiction might be a bit confusing when considering it exactly as stated in the script (we want to prove $S$):

1. Find a suitable statement $T$ and prove that $T$ is false.
2. Assume that $S$ is false and show from this assumption that $T$ is true.

When doing a real proof, we often don't know what our contradiction statement $T$ will be initially. We have some statement $S$, assume it is false, and then show that some incorrect statement follows. Usually, we continue until we have shown that something is obviously wrong - such as a statement like "$a = b$ and $a \neq b$". To relate this back to the proof pattern above, this incorrect statement at the end could now be called the statement $T$. We could now pretend that we found this statement initially, but this is rarely the case.