ISSN: 2251-1253. Vol. 4(4), pp. 702-707, June 30th, 2014
© Prime Journals
Communication
Theorem Proving: An Algorithmic Pedagogical Strategy
Marion G. Ben-Jacob, Ph.D.
Mercy College, Department of Mathematics and Computer Sciences. 555 Broadway, Dobbs Ferry, New York 10522.
E-mail: . Tel.: 914-674-7524; Fax: 914-674-7528
Accepted 17th June, 2014
Many students of mathematics find theorem proving difficult. To facilitate the art and science of mathematical theory, we present an algorithmic approach to proving theorems that is easily integrated into the use of common technological tools, for example, Blackboard and Iclickers. Examples from different areas of mathematics are demonstrated in detail.
Key words: mathematics, theorem proving; pedagogical strategy; technology
INTRODUCTION
Advances in recent technologies in communication and computing affectPedagogy and learning. The influence of technology on the learning environment of this millennium cannot be over emphasized. There are courses of study that are completely online, hybrid, blended and even those onsite rely to some degree on technology, be it via research assignments or online tutorials. Online learning platforms, for example,Blackboard, allow for asynchronous learning supported via the posting of lecture notes, a discussion area, and a synchronous chat room. One is able to post announcements, interact via email and make use of tools for the facilitation of grading and tracking of student posts (Blackboard 2009). Clickers are another popular technology tool that has been integrated into the pedagogical environment.Using clickers students can select their answers to multiple choice questions. These answers can be identified with each student individually or just collected as group responses. Clickers can be used for surveys, multiple choice tests, and recently, for formative assessment of student learning (Iclicker 2008).With the integration of technology into pedagogy we have to insure that the same material is covered in all types of learning environments.
There is a strong need for mathematics majors to be facile with theorem proving. It is an integral part of the discipline that reinforces the beauty of the field in addition to the inherent logic and critical thinking.Many undergraduate major programs today focus on the applied aspects of the subject matter and students find proving of the theory rather difficult.They tend to gloss over the material never fully understanding it, let alone being able to produce a proof on their own.We contend that with the proper material students can be become adept at theorem proving, enhancing their comprehension of mathematics.
This paper presents an algorithmic approach to the pedagogy. We will introduce the concepts of hypotheses and conclusion, necessary and sufficient conditions and how to identify the aforementioned when attempting to prove a theorem.We will use examples from different mathematics fields and present the material in an interactive fashion.As a matter of fact, we will develop slides to reinforce the interactive aspect of our approach and so that the material can easily be incorporated into the use of clickers or Blackboard if the course is online, hybrid, or integrates the use of Blackboard in any way.Our presentation here will be in terms of slides.
Pedagogy
Slide 1
What are hypotheses?
Hypotheses are the given information. They are the assumptions that are assumed true. They are the starting point for proving the conclusion of the theorem.
When given a hypothesis, it is common to ask, what the hypothesis means, usually in terms of its mathematical definition.
Slide 2
What is the conclusion?
The conclusion is the logical implication of the given hypotheses. It is the truth or goal we want to establish by means of the accepted assumptions, that is, the
703 Prim. Res. Edu.
hypotheses. Before beginning an actual proof, it oftentimes helps to consider the relationship between the given information and the conclusionin terms of definitions.
Slide 3
Consider the following theorem from first year calculus:
Theorem: If f is differentiable at a point a in its domain, then f is continuous at the point a.
Slide 4
In this case, it is not hard to identify the hypothesis as there is only one given condition, namely that f is differentiable at a point ain its domain.Notice that this theorem says nothing about the points that are outside the function's domain.We point this out because mathematics is a very precise discipline.
Slide 5
Which form of the hypothesis is the best one to use for the proof?
f'(a) exists
f'(a) exists for a point a belonging to the domain of f
f'(a) =lim f(a+h) -f(a)
h0 h
d) f'(a) =lim f(a+h)- f(a) for a point a belonging to the domain of f
h0 h
Slide 6
The correct answer is d because it is the most specific (as opposed to c) and it involves the definition of f’(a) (as opposed to aand b).
Slide 7
Let's examine the conclusion. Based on our analysis of the hypothesis which penultimate form of the conclusion do you think is the best one to work with? Keep in mind there should be some relationship between the form of the hypothesis and the form of the conclusion.
a) f is continuous
b) limf(a+h) - f(a)=0
h0
c)f is continuous at a point a in its domain
d)lim f(a+h) - f(a)=0 for a point in its domain
h0
Slide 8
Once again the correct response is d because it is specific and involves the definition.
Slide 9
Let us continue with the proof itself.We want to take the given information and logically arrive at the conclusion.
Given: f'(a) = lim f(a+h) - f(a)
h0 h
We want to arrive at an equation involving just the
numerator of the expression.
Slide 10
What should our next step be?
a) Multiply both sides of the equation by h
b) Divide both sides of the equation by h
c) Add h to both sides of the equation
d) Subtract h from both sides of the equation
Slide 11
The correct answer is a.If we multiply both sides of the equation by h, we arrive at
limf(a+h) -f(a) = limf(a+h) -f(a) .h = f'(a).0 =0
h0 h0 h
This is the conclusion we were looking for.
Slide 12
We need to be able to justify every step we take in the proof.
Why are we able to multiply both sides of the equation by h?
- h is it just a letter so it does not make a difference
- h is like 0 so it is ok
- h is going to 0 but not zero and so as in algebra if we multiply both sides of an equation by the same non-zero quantity, - the results are still equal.
Slide 13
The correct answer is c.We note that h is not 0, merely approaching it so we are allowed to multiply both sides of the equations by h.
Slide 14
Another mathematical fact we used in this proof is that the limit of products is the product of limits.This was used to determine that
limf(a+h) -f(a).h = f'(a). 0 = 0
h0 h
Slide 15
We now have determined that limf(a+h)- f(a)=0:
h0
a) The proof is concluded.
b) We need to add f(a) to both sides of the equation without justification.
c) We need to add f(a) to both sides of the equation and state we can do this because the limit of a sum =the sum of the limits.
Slide 16
The correct answer is c because we need to make things explicit in a proof with justification.
Slide 17
We want out final statement to match the definition of continuity, that is, lim f(x) = f(a). xa
In order to do this we need to make a substitution. Which of the following is the correct one?
a) Let x be a+h then h= x-a and our result can be written as limf(x)= f(a)
x-a0
b) Let x be a-h then h=x-a and our result can be written as limf(x)= f(a)
x-a0
c) Let x be a-h then h= x-a and our result can be written as limf(x)=f(a)
x-a0
Slide 18
The correct answer is a. it is the only substitution that will lead to the necessary conclusion.
Slide 19
Take a moment and write the entire proof beginning with the statement and justify each line along the way.
Slide 20
The entire proof should look something like the following:
Theorem: If f is a differentiable function at a pointa on an interval, I, in its domain, then f is continuous at the point.
Given that f is differentiable.This means that
f'(a) = limf(a+h) -f(a)exists.h0 h
h is not zero. It is going to zero. We can multiply both sides of the equation by h and
take the limit of both sides as h0, to obtainlim .
f'(a). h= lim f(a+h) - f(a).h
h0 h0 h
If you take the same limit on both sides of an equation, the equation remains true.
Now, the limit of the product is the product of the limits, lim f'(a) = f'(a) and the h's on the h0right side cancel each other. Remember this is ok because h is not 0. It is approaching 0.
We get 0 = limf(a+h) - f(a),or adding f(a) to both sides
ho
we get f(a) = limf(a+h). Now
h0
make the substitution h= x-a so h0 => x-a->0 or x a to obtain f(a) = limf(x).
xa
QED
Slide 19
At the end of many proofs we see the letters QED. This stands for Quod Erat Demonstratum, Latin for "that which was to be demonstrated."
Also note that we have not proven anything about the converse of the theorem, that is, if a function is continuous, it is differentiable.As a matter of fact this is not true in general. To prove something false, one needs to provide only one counterexample.
Marion 704
Example 1
Slide 1
Let's try and prove another theorem from calculus, namely that to compute the derivative of the product of two functions, we need to hold the first one constant and multiply by the derivative of the second then, add the second function multiplied by the derivative of the first.More explicitly
Given f(x) and g(x) defined and differentiable on an interval I,
[f(x).g(x)]' = f(x).g'(x) + g(x).f(x)'
Slide 2
Which form of the hypotheses should we use?
f' and g' exist
f'(x) and g'(x) exist for all x in the interval I
f'(x) = lim f(x+h)-f(x)and
h0 h
g'(x)= limg(x+h)- g(x)exist for all x in the interval I
h0 h
Slide 3
The correct answer is c.It goes back to the definition and that is almost always necessary for a mathematics proof.
Slide 4
Which form of the conclusion will we arrive at, at the penultimate step of the proof?
a) the derivative of the product of two functions exist
b)[f(x).g(x)]' = f(x).g(x)' + g(x).f(x)'
c)[f(x).g(x)]'=f(x).limg(x+h) - g(x) +g(x). lim f(x+h) - f(x
h0 h h0 h
Slide 5
It is c, the option with the most detail.We will use the form of the hypotheses with the most detail and so we will deduce a comparable form.We note that once we arrive at choice c, the stated conclusion follows as c is equivalent to
[f(x).g(x)]' = f(x).g(x)' + g(x).f(x)'
Slide 6
Is the following the correct definition of [f(x).g(x)]’ ?
[f(x).g(x)]' = limf(x+h).g(x+h) - f(x).g(x)
h0 h
a) True
b) False
Slide 7
It is true.Yet when we look at slide 4, we see that we need to manipulate the right hand side of the equation to match the right hand side on slide 6.We are going to add and subtract the same quantity on the right hand side of option c, slide 4. (If you are concerned about how we know to do this, it is experience and now that you have
seen this technique once, you will consider using it when you prove another theorem when necessary)
705 Prim. Res. Edu.
Slide 8
Our "working equation" becomes
[f(x).g(x)]' =limf(x+h).g(x+h) - f(x).g(x)–
h0 h
limf(x).g(x+h)+lim f(x).g(x+h)
h0 h h0 h
Slide 9
Rearranging our terms we get
[f(x).g(x)]' = limf(x).g(x+h)-limf(x).g(x) +
h0 h h0 h
limf(x+h).g(x+h)- limf(x).g(x+h)
h0 h h0 h
= lim f(x).g(x+h) - f(x).g(x)+lim f(x+h).g(x+h) - f(x).g(x+h)
h0 h h0 h
Slide 10
In order to justify the rearrangement of our terms which reason is the one we must use?
a) The limit of the sum is the sum of the limits
b) The limit of the product is the product of the limit
c) Both of the above
d) Neithera) nor b)
Slide 11
‘a’ is the correct answer because all we did was add and subtract the terms involving limits.
Slide 12
If we factor out f(x) from our first two terms and g(x+h) from the latter two terms we get
[f(x).g(x)]' = f(x). limg(x+h)-g(x)+limg(x+h).
h0 h h0 h
limf(x+h) -f(x)
h0h
Slide 13
What is the justification for the last result?
a) The limit of the sum is the sum of the limits
b) The limit of the product is the product of the limits
c) Both of the above
d) Neither of the above
Slide 14
The correct answer is b as we are dealing with products.We note that limf(x) = f(x)
h0
as there is no h involved in the argument of this term.
Slide 15
We have arrived at our penultimate step,that is,
[f(x).g(x)]' = f(x). limg(x+h) -g(x)+ g(x). limf(x+h) -f(x)
h0 h h0 h
using the fact that
limg(x+h) =g(x)
h0
Slide 16
We rewrite the results in the form the theorem was originally stated (and for the "sticklers" add QED at the end).
[f(x).g(x)]' = f(x).g(x)' + g(x).f(x)'
Slide 17
You try to rewrite the entire proof now, justifying each step or logical inference that you make.
Slide 18
Theorem: Given that f(x) and g(x) are defined and differentiable on an interval I, then the derivative of the product exists and
[f(x).g(x)]' = f(x).g(x)' + g(x).f(x)'
Proof: We are given that f(x)' = limf(x+h) - f(x)andg'(x)=limg(x+h)-g(x)exist
h0 h h 0 h
We want to show that [f(x).g(x)]' = f(x).g'(x) + g(x).f(x)'
It will suffice to show that [f(x).g(x)]' = f(x).lim g(x+h)-g(x)+g(x).limf(x+h) -f(x)
h0h h0 h
by the definition of the derivative.
Consider the definition of the derivative of the product
[f(x).g(x)]' =limf(x+h).g(x+h)- f(x).g(x)
h0 h
Add and subtractlimf(x).g(x+h)to the right side of the equation and rearrange the
h0 h
order of the terms to get
[f(x).g(x)]' = limf(x) .g(x+h) -g(x)+ limg(x+h). f(x+h)-f(x)
h0 h h0 h
We can do this because adding and subtracting the same value to one side of an
equation is adding zero and does not change the value. Also, addition is commutative
and so we can change the order of the terms.
Now, using the facts that the limit of the product of terms is the product of the limits and
that limf(x) = f(x) and that the limg(x+h) = g(x) we get
h0 h0
[f(x).g(x)]' = f(x).limg(x+h)-g(x)+ g(x). limf(x+h) -f(x)
h0 h h0 h
QED
Example 2
Slide 1
We take this example from abstract algebra to 'change the flavor' of the mathematics a bit.We note, the strategy is the same.List the hypotheses in the form of their definitions and logically arrive or deduce the conclusion.We remark that we will need to use all the hypotheses or most of the hypotheses if they are part of a definition;
otherwise the assumptions in the proof would have been
relaxed (reduced).
Slide 2
Theorem: If G is a group with binary operation *, then the left and right cancellation laws hold in G, that is, a*b = a*c implies b= b, and b*a = c*a implies b=c for all a,b,c in G.
Slide 3
The characteristics of a group will be our hypotheses. Consider the following characteristics:
A group (G, *) is a non-empty set, G, with a binary operation *such that the following hold:
i) Closure: If a and b belong to G then a*b is an element in G as well.
ii) Associativity:If a, b, and c belong to G, then (a*b)*c = a*(b*c).
iii) Identity: There exists an element e in G such that for every element a in G we havea*e = e*a =a.
iv) Inverses: For every a in G, there exists a-1 such that a*a’ = a’*a = e.
Slide 4
Which of the aforementioned four conditions are part of the definition of a group (G, *)?
a) i, ii, i
b) ii,iii, iv
c) i, ii,iii,iv
d) i,ii,iii,ivand one more that is not listed
Slide 5
The correct answer is c.If it does not look familiar to you, please refer to your textbook to confirm.
Slide 6
If a and b belong to G, a*b belongs to G.Why is this true?
a) Closure property
b) Associativity property
c) Identity property
d) Inverse property
Slide 7
The correct answer is a.This is exactly what closure means.
Slide 8
Suppose that a*b = a*c. Then there exists a’, the inverse of a such that;
a’*(a*b) = a’*(a*c).
This istrue by:
a) Closure property
b) Associativity property
c) Identity property
d) Inverse property
Slide 9
The answer is d.
Marion 706
Slide 10
The last step leads us to(a’*a)*b = (a’*a)*c because of the:
a) Closure property
b) Associativity property
c) Identity property
d) Inverse property
Slide 11
The correct answer is c.
Slide 12
But, (a’*a) = e because:
a) Closure property
b) Associativity property
c) Identity property
d) Inverse property
Slide 13
The correct answer is c.
Slide 14
We conclude b = c.
QED
Slide 15
1) Starting with b*a = c*a one can deduce that b= c upon multiplication on the right by a’ using the same axioms.
2) Note that we used all the hypotheses in the proof.
Slide 16
Try to reproduce the entire proof now, with justification for each step.
Slide 17
Theorem: If G is a group with binary operation*, then the left (and right) cancellation laws hold in G, that is, a*b = a*c (and b*a = c*a) implies b= c for all a, b, c in G.
Proof: For any two elements a,b in G, the product of the elements is in G as well because of closure.Thus, we have a*b and a*c are in G.We are given that a*b=a*c.
Every element in G has an inverse; in particular, let a’ be the inverse of a.
We get a’*(a*b) = a’*(a*c) by closure.Using the associative law we get
(a’*a)*b = (a’*a)*c.Using the identity property we find that a’*a= e and so we get
e*b= e*c which implies b=c, using the identity property again.
QED
CONCLUSION
Our contention is that by breaking down a mathematical proof into small pieces or bits of information, and reinforcing the step-by-step approach, we will help
707 Prim. Res. Edu.
students learn to prove theorems.Our examples in this paper are just that, examples.The first two are from first semester calculus, a course taken by every math major and other students who want to further their study of mathematics.The third example comes from a mathematics elective, algebraic structures or abstract algebra, to illustrate that our approach to the pedagogy holds for higher level courses as well.
REFERENCES
Blackboard. (2009). Blackboard Inc. (Accessed 10 September 2013). <
Iclicker. (2008).iclicker. (Accessed 11 September 2013). <