Mathematical Systems

A mathematical system consists of the following:

1. a set of undefined concepts,
2. a universal set,
3. a set of relations,
4. a set of operations,
5. a set of logical axioms,
6. a set of non-logical axioms-these axioms pertain to the elements being studied, the relations, and the operations; and not to the logic being used,
7. a set of theorems,
8. a set of definitions,
9. an underlying set theory.

In plane geometry the undefined concepts are those of point and line. The universal set is the set of points in the plane. The relations are such concepts as equality, perpendicularity, and parallelism. We have mentioned the logical axioms. A non-logical axiom would be of the form:

Two different points are on exactly one line.

Proof

Definition: Suppose are all the axioms and previously proved theorems of a mathematical system. A formal proof, or deduction, of a sentence P is a sequence of statements , where

1. S_n is P, and one of the following holds
   1. S_i is one of , or
   2. S_i follows form the previous statements by a valid argument using the rules of reasoning.

A theorem is any sentence deduced from the axioms and/or the previous theorems. The same is true of lemma and proposition. For some mathematicians there is a hierarchy of lemma, proposition, and theorem; with lemma being the easiest to prove and theorem the most difficult, or longest. Other mathematicians make little or no distinction between these objects, and will call everything a theorem.

Example: Suppose a mathematical system contains just the following axioms:

1. A₁:
2. A₂: .

The following is a formal proof of x<y.

S₁: by A₁

S₂: by A₂

S₃: by modus ponens on S₁, S₂

S₄: x<y by the tautology

In practice mathematicians do not write formal proofs. They write informal proofs. An informal proof is an argument which shows the existence of a formal proof. As such it gives enough of the formal proof so that another person becomes convinced. Thus we might call an informal proof a convincing argument. Mathematicians try to convince other mathematicians. You will try to convince your fellow students and me, your professor.

An informal proof of the above example runs as follows:

From A₁ and A₂ it follows that . Thus, x<y.

Henceforth, we will be writing only informal proofs. The art of mathematics is creating proofs. Just as every other artisan, the mathematician has some basic modes of proof. We will now consider a few of these.

Proving Conditionals

You usually prove a sentence of the type in plane geometry by assuming P and deducing Q. You consider Q the conclusion. In actually, was the conclusion. It was what you were trying to prove.

To prove first assume P to be true. Then using P and all other theorems and axioms try to deduce Q. Once Q is deduced in this manner you have completed a proof of . You have not shown that Q is true; you have only shown that Q is true if P is true. Whether P is true is another question; whether Q is true is another question. What you have shown to be true is .

This technique is called the Rule of Conditional Proof or the Deduction Theorem. More formally, suppose that are the axioms and previously proved theorems. To prove is to show that

From we can deduce

is a valid argument. To do this temporarily assume P to be an axiom and show that

From ,P we can deduce Q

is a valid argument.

A second technique of proving is by the contrapositive. We can prove by proving . Often the rule of conditional proof is used to prove the contrapositive.

Proving Biconditionals

There are three modes of proof for biconditional sentences.

1. Prove and .
2. Prove and .
3. Provide an iff-string.

A word about the iff-string. We produce a string of equivalent sentences from P to Q. This is the Law of Syllogism from the list of tautologies.

Proving

To prove let x represent an arbitrary element of the universal set and prove that P(x) is true. Then since x was arbitrary element of the universal set, we may generalize that is true. The justification is Logical Axiom 2.

Proof by Cases

Proof by cases is used several ways and involves the connective or. We will be trying to prove a sentence of the type . This type of proof utilizes the tautology

The proof is accomplished by proving the antecedent of this sentence, . Hence, and must be proved. Any mode of proof for conditional sentences can be used.

Similarly, a proof by cases of is accomplished by proving .

The art of producing a proof by cases lies in the discovery of what set of exhaustive cases is appropriate.

Mathematical Induction

This is a technique that is all too often overlooked in geometry. I include it here for completeness. Suppose P(n) is a sentence which is a statement for any , then the Principle of Mathematical Induction is . If we can prove the antecedent of this statement, , then by Modus ponens we can deduce . Thus there are two steps in the proof of :

Basic Step. Prove P(1).

Inductive Step. Prove .

Note that its name is misleading. Mathematical induction} is deductive reasoning not inductive reasoning. Inductive reasoning is making a conjecture or guess based on observations and your previous mathematical experience.

Proof by Contradiction

A contradiction is a statement which is false no matter what the truth value of its constituent parts. It can usually be expressed symbolically in the form . A proof by contradiction of a statement P is a proof that assumes ~P and yields a sentence of the type , where R is any sentence including P, an axiom, or any previously proved theorem. This is justified by the tautology . Intuitively, P can only be true or false (since we are assuming only a two-valued logic). If we assume its negation true and this yields another sentence both true and false, then ~P cannot be true, so P must be true.

The phrases reductio ad absurdum and indirect proof both refer to proof by contradiction. The importance of being able to form sentence negations is realized when doing proofs by contradiction. To begin such proofs you must know how to form negations.

Comparing proof techniques we see that with the Rule of Conditional Proof we assume P with the explicit intention of deducing Q. With the contrapositive we assume ~Q with the explicit intention of deducing ~P. But in using Proof by Contradiction we assume both P and ~Q and try to deduce any sentence R and its negation ~R.

Proofs of Existence and Uniqueness

The sentence

is denoted by . The sentence

is denoted by .

There are two parts to proving a sentence of this form.

Existence Part. Prove that there is an x such that P(x) is true.

Uniqueness Part. Here you must prove that if there are two elements x and z such that P(x) and P(z) are each true, then x=z. Symbolically, .

Proof Creativity

In the previous part of this chapter you learned several modes of proof. The intent is that these will become part of your mathematical toolbox. Just because you have the tools does not guarantee that you can create a proof. There are some helpful procedures to follow as aids in creating a proof.

Translate to Symbolic Logic. A typical comment made when proofs are attempted is

This statement is made with a great gnashing of teeth and wringing of hands. One procedure to follow is comparable to that of solving a problem in basic algebra.

First, translate what you are requested to prove into symbolic logic. Then seeing the structure of the translated sentence you can select a mode of proof. Still, knowing a mode of proof that could be used does not guarantee success. Suppose you want to attempt to prove a sentence of the type by using the Rule of Conditional Proof. You want to assume P and deduce Q. A question often asked is

There is no certain way. No one way will always work. Certainly, knowing to assume P and deduce Q is a step in the right direction. The mode of proof provides the structure for the proof; building this structure is usually a more creative task. I can give a few hints.

Analogy. An important aid in carrying out proofs is to get ideas from other proofs. This is supposed by comments of mathematicians who argue that to be good at mathematics you need lots of practice; lots of exposure to different proofs.

Analytic Process. This is known as working backwards. You want to prove . Start with Q and try to find an R such that . Then try to find and S such that . Then look to see if . If not, try to fill in another step. Continue this until you find a sentence R_n such that and . Do not be surprised if you do not see this process outlined in a text or reference book. It is rare for this processed to be used. It is then explicitly mentioned. Usually the proof will be given as .

Something Approach. This is simply trial-and-error. You want to prove by assuming P and deducing Q. You have no particular way to get from P to Q; but start out, get involved, do something, try different approaches, prove all that you can. You do not have to show all of this in your final version of your proof, but it can help you get started. When reading proofs in mathematics texts and journals, you are not aware of the blind alleys and unsuccessful attempts preceding a successful proof. This leads you to think the established mathematician never follows a wrong path or makes a mistake. Trial and error is very much a part of mathematical creativity.

Use of Definitions. Another helpful procedure is to recall all relevant definitions. It is a tendency to read a definition and ignore its importance in later proofs.

Use of Previously Proved Theorems. It is helpful-nay, it is essential in starting a proof to examine all previously proved theorems for results which might be relevant to the proof.

This site is best viewed with Netscape Navigator.
Download Netscape Now!

Last updated 8/30/96 by