Direct Deductive Proofs

Logical Proofs

One of the turning points in the development of mathematics was the introduction by the Greeks of the concept of a logical proof. The statements of mathematics have a certainty that will always be lacking in the sciences because mathematics actually refers to a restricted artificial world where strict rules of logic are required. What is incredible is that the statements of mathematics often have powerful applications in describing the real world. One of the sources of this power is the purity of the logical process by which mathematics is built.

In a particular field of mathematics, and there are many fields, a small set of terms are taken as undefined and a set of axioms relating to these terms is accepted. New terms may be introduced via definitions as the theory is developed. Statements involving these terms, called Theorems, Propositions, Corollaries, or Lemmas depending on their importance or context, are deduced and proven. The basic idea is: If you accept that the axioms are true about the undefined terms, then every statement that has been so deduced is also true. It is this flow of inevitable truth from the axioms through the huge structures built upon the axioms that is the essence of mathematics.

We will use the word Theorem as a generic term for a statement that is to be proven. Almost any theorem can be put into the form "If P, then Q" or is made up of two or more statements that can put into that form. So we will concentrate on strategies for proving "If P, then Q".

There are five basic strategies to prove a statement of the form P ==> Q: 1) Direct proof; 2) Direct proof of the contrapositive; 3) Proof by contradiction; 4) Mathematical induction; 5) Case by case analysis.

Direct Proof

A direct proof consists of an initial statement connected to a statement to be proven by a finite number of intermediate statements, P₁, P₂, ... , P_n, such that P₁ is P, P_n is Q and each of the implications P_i ==> P_i+1 is an application of an axiom or a result that had been established earlier. There might be auxiliary comments made to clarify points or to bring in a new term or symbol, but the main structure looks as follows:

THEOREM: P ==> Q

PROOF: (Note that P₁ is P and P_n is Q.)

P1	==> P2	(by *****)
	==> P3	(by *****)
	.
	.
	.
	==> Pn-1
	==> Pn	(by *****)
___	__________	____________

The *****'s represent references to the axiom or previous result which justifies the implication. Some examples of axioms and properties which can be used can be found in the Real Numbers and Symbol Manipulation sections. Sometimes a brief calculation is done on the side as such a justification. Once a direct proof of P ==> Q is constructed, the logic of it is completely transparent.

The concept of a logical proof is better illustrated through an example(Note: For this example, we will assume the axioms of the field of real numbers R):

THEOREM: If a and b are in R satisfy a > 0, b > 0 and a > b, then a² > b².

PROOF:

a > 0, b > 0 and a > b	==> a + b > 0 and a - b > 0	(by "a and b in P imply a + b is in P" and the definition of a > b)
	==> (a + b)(a - b) > 0	(by "a and b in P imply ab is in P")
	==> a2 - b2 > 0	(since (a + b)(a - b) = a2 - b2)
	==> a2 > b2

Usually the proof will be written less formally and with a less "direct" line of presentation. For example:

ALTERNATE WRITING OF THE PROOF:

Since the sum of two positive numbers is positive, a > 0 and b > 0 implies a + b > 0.

Also, a > b means a - b > 0.

Multipling these two positive numbers together gives a² - b² = (a + b)(a - b) > 0.

Thus, a² > b².

---