Direct Proof

George E. Hrabovsky, President, MAST

A PDF version of this column is available here. Editor.

The Column So Far

Here are the columns that have been presented so far:

Column 2: "Math Project #2: How does the consistency requirement of the number system lead to the real numbers?" (24 February 2006). In this column I fully developed the number system up to and including complex numbers.

Math Project #3: How we prove a theorem directly?

Background

One task of any mathematician is to formulate and prove theorems. If you have developed an idea for a theorem it is called a conjecture. When this conjecture is proven it becomes a theorem. The question becomes, how do you prove such a conjecture to be true?

The most reliable proof, and usually the most difficult, is called a direct proof. It is called such because you proceed directly from the premise of the conjecture to its conclusion by a sequence of logical arguments. There are no ambiguities, the flow of logic is relentless and when completed there is no doubt about the validity of the theorem. It is the most difficult style because it is so direct. We do not often think out complicated arguments in such a linear fashion.

Necessary Principles

A mathematical proposition is a mathematical statement that can be either true of false. We can denote such propositions by the use of lower case letters .

Definition 1: Considering both of two propositions is called a conjunction, . Sometimes this is called, "and."

Definition 2: Considering either of two propositions is called a disjunction, . Sometimes this is called, "or."

Definition 3: Considering a proposition that changes the truth value of another is called a negation, . Sometimes this is called, "not."

Definition 4:  The statement if , then is called a conditional statement. This can be written .

Definition 5:  The statement that is true if and only if is true is called the biconditional. This can be written and is equivalent to saying .

Definition 6: Statements that are equivalent have the same truth value, they are denoted with the symbol .

Rule of Logic 1 (Law of the Excluded Middle): A proposition is either true or false, .

Rule of Logic 2 (Contrapositive): .

Rule of Logic 3 (Associativity of Conjunction and Disjunction): If we denote either conjunction or disjunction with the symbol □, then .

Rule of Logic 4 (Distribution): . Likewise .

Rule of Logic 5 (De Morgan's Laws): .

Rule of Logic 6 (Transitivity): .

Rule of Logic 7 (Modus Ponens): .

Rule of Logic 8: .

The Method of Direct Proof

To prove that we begin by assuming .

Then we have a sequence of logical arguments leading to the conclusion .

Thus, .

An Example of Direct Proof

Here I choose to give an example from vector algebra. Thus we have the following additional principles:

Definition 7: A coordinate system is an arbitrary representation of an n-dimensional space having n perpendicular coordinate axes.

Definition 8: A real vector is a collection of n ordered real numbers, each real number corresponding to a coordinate axis. We write a vector in bold face, thus for the n-dimensional space we have the vector .

Definition 9: We can add two vectors, =.

We seek to prove that addition of vectors is closed. For this purpose we say that the vectors belong to a set of vectors that we will call . We have two vectors belonging to , these vectors are and . Our assertion is that is also an element of .

Since the sum of two vectors is the collection of the sums of the components, then the task becomes one of showing that the sums of the components are closed. Since these components are real numbers by Definition 8, we know that they are closed by the properties of real numbers (see "Math Project #2: How does the consistency requirement of the number system lead to the real numbers?" and "A New Year," for details).

Since each member of the sum of the two vectors is closed, then the sum of the two vectors is closed. Thus, we have proven our theorem.

References

[2] Eric W. Weisstein et al., "Propositional Calculus" (1999). From MathWorld--A Wolfram Web Resource.

Created by Mathematica  (August 1, 2005)