Definition 1:

A proof of a result is a sequence of statements which demonstrates that the result is a logical consequence of prior results.

A proof arranges selected prior results into a form that assures that the new result follows logically from them. When you want to prove something, which results are prior? 

Definition 2:

Imagine an ordered list of true mathematical results, one after another. To prove any given result, only results earlier on the list, which we call prior results, may be used. Prior results consist of axioms, definitions (which include notations), and previously proven results. 

 

Use scratch paper. Write down ideas and definitions on scratch paper without expecting that what you write will be the final organization. After you have written enough that you can see the final proof, create a final copy by selecting and organizing the useful parts from all that you have written. 

(All your steps must be prior results. If you have a good idea and it is true, it does not belong in a proof unless it is already known to be true as a prior result you can cite.)

Proofs of generalizations.

Many theorems are conditionals. If it is a conditional, 

Analyze the conclusion.

Translate new terms in the conclusion into more-primitive terms (using definitions in sentence-form)

  • "Translate, work with the older terms, translate back."

If the translated form fits one of our logical equivalences, it may be proved in the alternative form, and often is. 
If the conclusion is itself a conditional, use "A Hypothesis in the Conclusion":

"H => (A => B)" is logically equivalent to "(A and H) => B" where "A" is intentionally given first. Usually, beginning with "A" is a good idea.

Example:

Suppose the problem is to prove f(x) = 2x + 3 is one-to-one.

  1. Look up what "one-to-one" means.  "f is one-to-one iff f(x1) = f(x2) => x1 = x2."
  2. Use the sentence-form definition to replace the sentence with a new term with its definition in more-primitive terms.
  3. It is a conditional, so begin with its hypothesis.
  4. Use a representative-case proof and begin with "Let f(x1) = f(x2)." 
  5. Work from there, intending to end with "x1 = x2."

If a direct proof does not seem to work, try using the contrapositive.

If you don't have an idea about how to do the proof, start in the place suggested by our logical equivalences and see where that takes you.
If it does not seem to be working, the conjecture may be false.

Begin with a general, arbitrary case (not a constructed case). 
Look for prior results that might be similar and helpful.

If the variable is integer-valued, induction might work
Memorize and use definitions in sentence-form.  (Because proofs are sequences of sentences.)

 

Existence statements are usually proved in two stages:

  1. Exhibit a candidate, and
  2. Show it has the desired properties.

Example: 

Prove: If y > 10 there exists x > 5 such that 2x < y.
It is a generalization, so begin with a representative case:
"Let y > 10."
Now it has become an existence proof. Use scratch work to find an x that has two properties: 1) x > 5 and 2) 2x < y.
Proof:  Let y > 10.
Choose x = 5 + (y - 10)/ 4.   [This is one possible candidate--not the only one that will work.]
Since y > 10, x = 5 + (y - 10)/4 > 5   [That did one property]
Also, 2x = 2(5 + (y - 10)/4) = 10 + (y - 10)/2 = 5 + y/2 < y/2 + y/2 = y.  [That does the other property.]

About a conjecture 

Decide if it is true. Try examples to test its truth. Look for possible counterexamples. If you can't find one, then seek a proof.
If it is true, prove it. 
If it is false, give a particular counterexample.
Counterexamples should assign particular values to all of the letters. 
Simpler counterexamples are better.  (because they are more memorable and more likely to illustrate the key idea without unnecessary complications.)

 

When you are stuck:

  • Use the hypotheses. If a conditional is true it is likely you will need to use all the hypotheses.
  • Review the definitions. Often the key is in knowing precisely and then using the definition of some term.
  • If you try a proof and can't complete a step, look for a counterexample in which that step is false.

If you mean to assert something exists, mention existence explicitly.

Uniqueness proofs: Give the thing(s) two names and show they must be two names for the same thing.

Advice for harder problems:

  • If the problem is abstract, construct a simple example (emphasis on "simple") to make sure you know what the problem says.
  • Also, construct simple examples of immediately prior results to make sure you know what they say.

 

To prove a result:

  • you must assemble prior results, so you must know the prior results. That is,
  • know the formal definitions of the new terms in the result, and
  • be familiar with related previous results. (For example, often the proof of Theorem 10 uses Theorem 9.)

Here is a page on some things to avoid in proofs.

Return the the main page of  Math 242 or of Math 383.