The Proof is in the...

by George E. Hrabovsky, President, MAST

Where We Have Been

The last column we explored the basic notions of sets and subsets. We even saw what it means to prove something.
Before moving on I need to explain a misconception that I germinated last week and must stampt it out in detail. At the beginning of the section on subsets I wrote,

If you think about it, you will eventually ask the question, "Can we consider a set to be an element of another set?" The answer is yes. If we say that the set is an element of the set , then we call a subset of . We can write this,

While we can (and will) consider sets to be elements of other sets, this is NOT the definition of a subset. The proper definition of a subset is, "If all elements of the set A are also elements of the set B then A is a subset of B."
Two unfortunate mistakes in two weeks, at least I am being consistent... Sigh!

Where Will We Go in This Column

In this column we will expand upon the rather informal introduction to proofs given last time and define three general strategies for writing proofs. To do this we will have to establish several rules of logic that produce tautologies. Once these rules have been established I will introduce the notions of direct proof, proof of the contrapositive, and proof by reductio ad absurdum.

Fundamental Rules of Logic

In this section I will present the fundamental rules of symbolic logic with a very brief discussion of each. I leave it as an exercise to the reader to develop their truth tables (it is really very straightforward to do this).
The first such rule is called the Law of the Excluded Middle,

This basically says that a proposition must either be true or it is false.
We also have the property of associativity, that is the order of connective does not matter,

and

We can also establish the properties of distributivity, these rules treat the problem of applying the conjunction and the disjunction,

and

The next rule states that a biconditional exists if and only if both propositions imply one another,

The next statement is a little more subtle,

Then we have the De Morgan Laws,

There is also the contradiction,

The transitive property states that if one thing implies another, and if that other implies a final thing, then the on thing implies the final thing,

There is also a rule that tells us that if we have established the truth of a proposition along with an implication based on the proposition, then the final proposition of the implication is true,

This is called the modus ponens rule.
This next one seems obvious, but then it is a tautology,

This is called the rule of tautology.
If we think about it for a while we will realize that a disjunction is true when any of its component propositions is true,

This is called the addition rule.
It also seems reasonable to conclude that the order of a disjunction is irrelevant,

This is called the permutation rule.
It also seems reasonable that if we apply a disjunction to an implication, the disjunction must be applied to both parts of the implication,

This is called the rule of summation.
It also seems reasonable that if we substitute a proposition for every occurence of a different proposition that we get another tautology. For example, if we substitute for q in (14),

This is called the substitution principle.
As a consequence of this we can expand this to sunstituting equivalent expressions; this is if we replace every occurance of an expression by its equivalent expression we get another tautology. At this point we must introduce another concept. We realize that in order to proceed logically we have to use terms without being able to define them, we noted this in the last column. It is also useful to build exact definitions of other terms out of the more primitive undefined terms. Here is an example of such a definition,

If we then substitute for in (16), we can then write,

This procedure is called the rule of definitional substitution.
Finally we can state the if we have two propositions that are true, then the conjunction is true, this is called the rule of adjunction.

Direct Proof

This is the best kind of proof in that there is no ambiguity if you can pull it off. You begin with a proposition called the hypothesis, and then by a series of logical arguments you arrive at another proposition called the conclusion. This is also the most difficult kind of proof to develop.
We will now directly prove a different form of the transitive property (11). We begin our proof by writing the hypothesis, . We then use the rule of summation (16) and write,

By the principle of substitution we can substitute for p,

By (18) we can rewrite this,

So, we can write,

Theorem 3-1:

It is more usual to begin with a statement of a proposed theorem and then develop the proof for it.

Theorem 3-2:

Proof: We begin by noting the addition rule (14). We know that by the substitution rule we can exchange p for q so (14) becomes,

This completes our proof.

Theorem 3-3:

Proof: We need to start somewhere so let's choose Theorem 3-1 as our starting point. We need to convert this to all ps. By the rule of substitution we can exchange for q, this gives us,

We can the substitute p for r.

By the principle of tautology we have , so we can rewrite (26) as,

By the transitive property we know that , so (27) becomes,

We can reapply the transitive property to get

This proves our theorem.
This last theorem may seem trivial, but it proves that a proposition always implies itself. This is called the reflexive property of implications. Also, if it seems like magic that I chose the exact expressions to yield the proofs, it is done thorugh trial and error.

Theorem 3-4:

Proof: We can begin by writing Theorem 3-3

By applying (18) and substituting p for q we have,

We can then apply the permutation rule (15) to get,

This proves the law of the excluded middle.
It is important to realize that often there is more than one way to prove a theorem. There are likely many different ways to directly prove each of the theorems noted above.

Proof of the Contrapositive

Not only are there many ways to directly prove a theorem, there are many other approaches than the direct proof. Recall from the first column ("Welcome to the Mathematics Corner") that there is a kind of implication called the contrapositive. If you did practice problem 9 you will know that the contrapositive is equivalent to the conditional. If adopt the symbol for equivalence we have

So, if we can prove that the negation of the conclusion of a theorem implies the negation of the hypothesis, then we have proven that the hypothesis implies the conclusion.
So the first step in a proof of this kind is to write the negation of the conclusion. Then you must show by a series of logical arguments that this leads to the negation of the hypothesis. Then you must state that by the equivalence of the contrapositive to the conditional that the theorem is proven.

Reductio Ad Absurdum

In this style of proof the goal is the assume the negation of the hypothesis, then show by a series of logical arguments that this leads to a contradiction.
The first step is the write the negation of the hypothesis. Then you show that this leads to both the conclusion and the negation of the conclusion, this is an absurd result (a contradiction). Then you state that by this contradiction the hypothesis must lead to the conclusion.

More of the Theory of Logic

I will now go through and develop the most useful theorems for logic.

Theorem 3-5:

Proof: By the principle of tautology we have . If we substitute for p, we get,

By (18) this is equivalent to,

This completes the proof. It is interesting, if you think about it a while this theorem is a simple form of reductio ad absurdum; this is it tells us that a proposition that implies its negation must be false.

Theorem 3-6:

Proof: We begin with p. Then we use Theorem 3-4, and then substitute for p,

By (18) we then have,

This completes the proof.

Theorem 3-7:

Proof: If we look at Theorem 3-6 and substitute for p, we get . Then we use Theorem 3-4 and we substitute the implication,

This proves our theorem.

Theorem 3-8:

Proof: We begin by writing Theorem 3-7, . If we apply the rule of permutation,

By (18) we have