Mathematical Proof and the Principles of Mathematics/Logic/Direct proofs for implication

We've talked about what kinds of statements are used in mathematics, so now we can talk about how to put these statements together to prove theorems. At this point we can only prove tautologies, so if this were a video game then this would be the training level. The statements we're proving here can't really be called theorems, so we'll call them propositions.

As before, $P$, $Q$, ... will stand for mathematical statements in this section.

Rules of inference

In mathematics, a proof must be based on logical deduction, in other words each step must be a logical consequence of previous steps. Just what, exactly, a logical consequence is is a matter of logic, which supplies us with 'rules of inference'. Each rule of inference is a rule for combining true statements which is guaranteed to produce another true statement. The simplest example is:

From $P$ deduce $P$.

This rule is is called 'iteration'; many of the rules of inference have names but in a mathematical proof it should be clear from the context which rule is being used.

There are several other rules which combine previous statements in a simple way, but it turns out you can't get very far with only them. One approach is add axioms of logic, for example

$P$ or $P$ implies $P$.

But while this is a valid approach, proofs in mathematics would be much longer and harder to follow if axioms of logic were to be used directly. So the approach used in mathematics is to allow the use of 'auxiliary hypotheses'.

The most commonly used example of this type of rule is

If by making the assumption $P$ one can derive $Q$, then deduce $P$ implies $Q$.

That's going to take a while to sink in so we'll give some examples of proofs which use this rule of inference.

Example proof #1

Our first example of a proof is for the statement

Prop. 1 $P$ implies $P$.

The first version of the proof will be in tabular format to make it clear how the rules of inference are being used.

Line	Statement	Justification
1	$P$	Hypothesis
2	$P$	Iterating line 1
3	$P$ implies $P$	From 1 and 2

In the table, the first line is indented to show that we're introducing a hypothesis or assumption and the next line is indented to show that we're operating under the assumption of line 1. The last line is not indented, meaning that the statement is valid without the assumption.

So let's examine how the rule of inference was applied in this case. First we made the assumption $P$. Then we derived $P$, which in this case was simply repeating $P$. Since by assuming $P$ we were able to derive $P$, the rule of inference says you can conclude $P$ implies $P$.

A tabular format for a proof is rarely used in mathematics. You could use it if you're being extraordinarily detailed and careful as we are now, or if you're just starting out with proofs, also as we are now. In mathematical literature you would use a more prose-like style. Our second version shows what the proof might look like in that format.

Prop. 1: $P$ implies $P$.

Proof: Assume $P$. Then $P$ by assumption. Therefore $P$ implies $P$.

In this version of the proof there is language to introduce the hypothesis. This is usually "Assume ..." or "Let ...". The second line draws a conclusion and gives the reason. The language for this is usually something like "Then ... because ...", "Hence ... by ...", "So ... since ...". The last line isn't really necessary since we already know which statement we're trying to prove. But since it is included, the word "therefore" is used to point out that this is an important point in the proof. In this case it's because we're removing the assumption to combine it with what we were able to derive from it.

Experienced mathematicians would normally be able to fill in the proof of the statement like this with little effort. So another acceptable proof might be:

Prop. 1: $P$ implies $P$.

Proof: Trivial.

But calling a statement "trivial", "obvious" or "clear" is a privilege you have to earn by doing enough proofs that you can fill in a logical proof automatically. It's not be used for statements which seem true according to your intuition. Keep in mind as well that what is trivial to some may not be trivial to others, so you have to keep your audience in mind when writing a proof, just as with all writing.

Q.E.D. and tombstones

The abbreviation 'Q.E.D.' is sometimes seen at the end of proofs but it rarely used in modern mathematics. It's an abbreviation for the Latin phrase quod erat demonstrandum which roughly means "which was to be proved." Latin is not as widely known as it once was, and the abbreviation was used at a time when writers could safely assume that their readers had a basic knowledge of it. There are several variations including 'Q.E.F.' for quod erat faciendum meaning "which was to be done". If the end of a proof is marked at all in modern texts, then a tombstone, or small rectangle or square, is used. But if you're the old-fashioned type who uses phases like mutatis mutandis in everyday speech then there's nothing actually wrong with using Q.E.D. if you want to.

Example Proof #2

The next example of a proof will be for the statement

Prop. 2: $P$ implies ($Q$ implies $P$).

This is a bit more complex, but we encourage you make an attempt at it before reading further, keeping in mind that it can be proved using only the two rules of inference we've given so far.

More complex proofs aren't so much written as constructed. In other words you don't really write them from start to finish. Just as seeing a finished house doesn't tell you how to build one, seeing a finished proof doesn't tell you how to write one. So we'll try to show the processes that were used to create the example proofs and not just the final result.

We start by assuming that we have a proof and then try to figure out what it would look like. The statement is an implication, so in order for the rule of inference to work we need to assume the part before the word 'implies' and derive the part after the word 'implies'. So in tabular form, the structure of the proof is

Line	Statement	Justification
1	$P$	Hypothesis
(something)
n	$Q$ implies $P$	?
n+1	$P$ implies ($Q$ implies $P$)	From 1 and n

Now we need a proof of

$Q$ implies $P$

to fill in the middle. This is another implication so we need to assume the first part, $Q$, and prove the second part, $P$. This means making a second assumption within the first assumption and our current version of the proof is

Line	Statement	Justification
1	$P$	Hypothesis
2	$Q$	Hypothesis
(something)
n−1	$P$	?
n	$Q$ implies $P$	From 2 and n−1
n+1	$P$ implies ($Q$ implies $P$)	From 1 and n

At this point we need to prove $P$, but it's already one of the assumptions so it's just a matter of restating it. This gives the final version of the proof:

Line	Statement	Justification
1	$P$	Hypothesis
2	$Q$	Hypothesis
3	$P$	Iterating line 1
4	$Q$ implies $P$	From 2 and 3
5	$P$ implies ($Q$ implies $P$)	From 1 and 4

Let's translate into prose format.

Prop. 2: $P$ implies ($Q$ implies $P$)

Proof: Assume $P$. Now assume $Q$. We have $P$ by the original assumption. Therefore $Q$ implies $P$. From the original assumption $P$ it follows that $Q$ implies $P$, so we can conclude that $P$ implies ($Q$ implies $P$).

Example Proof #3

For this example we need a new rule of inference:

From $P$, $P$ implies $Q$ deduce $Q$.

In other words, if the statement $P$ and the statement $P$ implies $Q$ have both been proven, then you may add the statement $Q$.

You might consider this the inverse of the previous rule of inference since it uses an implication while the previous rules proves and implication.

Prop. 3: $P$ implies (($P$ implies $Q$) implies $Q$.

Again, we encourage you make an attempt at it before reading further, keeping in mind that it can be proved using only the three rules of inference we've given so far.

We leave it as an exercise to use the construction method discussed in the previous example to get to this point:

Line	Statement	Justification
1	$P$	Hypothesis
2	$P$ implies $Q$	Hypothesis
(something)
n−1	$Q$	?
n	($P$ implies $Q$) implies $Q$	From 2 and n−1
n+1	$P$ implies (($P$ implies $Q$) implies $Q$)	From 1 and n

We need to prove

$Q$

at this point, but we have

$P$

and

$P$ implies $Q$

as assumptions. So it's just a matter of applying our new rule of inference. The final form of the proof is then

Line	Statement	Justification
1	$P$	Hypothesis
2	$P$ implies $Q$	Hypothesis
3	$P$	Iterating line 1
4	$Q$	3,2
5	($P$ implies $Q$) implies $Q$	From 2 and 5
6	$P$ implies (($P$ implies $Q$) implies $Q$)	From 1 and 6

In prose format:

Prop. 3: $P$ implies (($P$ implies $Q$) implies $Q$)

Proof: Assume $P$. Now assume $P$ implies $Q$. We have $P$ by the original assumption, so $Q$. Therefore $Q$ implies ($P$ implies $Q$). From the original assumption $P$ it follows that ($Q$ implies $P$) implies $Q$), so we can conclude that $P$ implies (($Q$ implies $P$) implies $Q$)).

Quoting previous results

Mathematics wouldn't progress very far if everything had to be proved from scratch. Fortunately, every time a new result is proved it can be used as a shortcut in other proofs. Often it will be clear which result is being used, otherwise if it's a result proven earlier in the same document then point to it in the proof. It's handy to have some sort of labeling or numbering system to make this easier. If you're quoting from another source then use your favorite referencing style to make it clear where you're quoting from, and also make it clear where to find the result within that source. Note that any result of the form $P$ implies $Q$ can be combined with the previous rule of inference to create a new rule of inference 'From $P$ deduce $Q$'. For example Prop. 2 creates a new rule of inference

From $P$ deduce $Q$ implies $P$.

Prop. 4: $P$ implies ($Q$ implies ($R$ implies $P$)).

Proof: Assume $P$. Then $R$ implies $P$ by Prop. 2. Also, $Q$ implies ($R$ implies $P$) by by Prop. 2. Therefore $P$ implies ($Q$ implies ($R$ implies $P$)).

Note that in the first use of Prop. 2, the statement $R$ replaces $Q$ used in the proposition. In the second use the statement $R$ implies $P$ replaces $P$ used in the proposition.

Left to the reader

The following are left to the reader to prove:

Prop. 5: ($P$ implies $Q$) implies (($Q$ implies $R$) implies ($P$ implies $R$)).

Prop. 6: ($P$ implies ($Q$ implies $R$)) implies ($Q$ implies ($P$ implies $R$)).

Prop. 7: ($P$ implies ($P$ implies $Q$)) implies ($P$ implies $Q$).

Prop. 8: ($P$ implies ($Q$ implies $R$)) implies (($P$ implies $Q$) implies ($P$ implies $R$)).

Prop. 9: (($R$ implies $Q$) implies $P$) implies ($Q$ implies $P$)

Prop. 10: (($R$ implies $Q$) implies ($Q$ implies $P$)) implies ($Q$ implies $P$)

So far we've only dealt with implication, but that doesn't mean that we're done with it yet. There are some statements which, while true, can't be proved with the rules of inference we've given so far. One of these is

Prop. ??: (($P$ implies $Q$) implies $P$) implies $P$.

You might want to give this a try, remembering to only use the rules of inference on this page, to see how far you can get. If you do come up with a proof though then it means you're (probably) doing something wrong.