Introduction
When mathematicians
consider a mathematical
object, they are typically interested in two different aspects of
it:
What
is it?
I want a conceptual
understanding of the object.
¨
How do I think about it?
¨
What properties does it
have?
¨
How is it different from other
math objects?
¨
How can I understand it so that I can see possible applications?
How
do I compute with it?
¨
How do I find a value of the object
(if that makes sense)?
¨
How to I tell how big it is (in some
sense of big)?
¨
How do I determine in an efficient way what properties it has?
Proofs
Proofs
can have a conceptual side and a computational side too.
¨
A conceptual proof helps you understand why
the statement is true.
¨
A computational or symbolic proof may be
easier to check systematically to see if it is correct, and to automate using
some suitable computer program.
Conceptual and computational
Below I give some examples of what people call conceptual
and symbolic or computational. Those are
not well defined
ideas. Conceptual presentations are commonly geometric, but
they don’t have to be. And if you understand
some technicalities really well, you might call something conceptual that looks
like a horrible bunch of symbolic manipulations to someone else.
Whether something
is conceptual or not depends on what concepts you understand!
Example: Derivatives
Conceptually, the derivative of a function f is another function 
whose value at a is the slope of the tangent line to f at a. (See here
for discussion and examples.) In
calculus class you may have learned many specific formulas for computing the
derivative of various functions. Those
formulas are all proved using the epsilon-delta definition of
derivative. The epsilon-delta
definition
has a (rather subtle) conceptual basis.
Epsilon-delta proofs
are usually longish
chains of symbolic transformations. Refer
to an example somewhere.
Example: An algebraic identity
Here is a simple
example that shows the distinction between concept and computation. You are no doubt familiar with the identity
which holds for all real numbers. (In fact it holds in any commutative ring.)
Computational proof
This proof shows
an explicit series of steps that verify the identity using basic laws of
algebra:
This diagram shows why
the identity is true geometrically (for b < a).
Note that the two rectangles marked “ ”
are congruent.
This conceptual proof
requires no algebraic laws or computations at all. On the other hand, it is not easy to see how
to generalize it to a commutative ring.
Example: Property of the ordering of the reals
The idea of “conceptual
proof” depends on your experience. If
you are not familiar with basic geometric facts, the preceding geometric proof
may not be conceptual!
Here is another example
that shows how “conceptual” depends on what you know about.
Theorem:
For all real numbers x, y, and z, if ,
then either or .
Geometric proof
Logical Proof
We know that for real numbers, if x > y and y > z,
then x > z (this is the transitive law).
The contrapositive of this statement is: If x is not greater than y and y is not greater than
z then x is not greater
than z. But for any real numbers r and s, saying that r is not greater
than s is the same as saying that . So, rewording the contrapositive and using
one of the DeMorgan laws, we get: if , then either or
, as was to be proved.
If you have some
experience with mathematical logic, you might react to the logical proof (as I
did) this way:
Why, the statement in the
theorem is nothing but the contrapositive of the transitive law!
When I realized that, I
felt that I had acquired
a new insight,
so I would call this statement conceptual.
The geometric proof gives you a different insight.
Another
point: The logical proof works in a much
more general setting: The statement is
true in any totally
ordered set. The geometric
proof gives you no clue that that is true.
TO BE FINISHED
Derivatives
Example
Let m and n be positive integers, and let r
be m mod n. One can prove that
by showing that the set of common divisors of m and n is the same as the set of common divisors of n and r (easy). The result follows
because the GCD of two numbers is the greatest common divisor, that is, the
maximum of the set of common divisors of the two numbers, and a set of numbers
has only one maximum.
I have shown my students this proof many times, but they almost
never reproduce it on an examination.
Example
Now I will provide
three proofs of a certain assertion, adapted from [].
The statement to prove is that for all x, y and z,
|
(x>z)((x>y)∨(y>z))
|
(1)
|
Conceptual proof
We may visualize x and z on the real line as
in this picture:
There are three different regions into which we can place y. In
the left two, x>y and in the right two, y>z. End of proof.
This proof is written in English, not in symbolic notation, and
it refers to a particular mental representation of the structure in question
(the usual ordering of the real numbers).
Symbolic Proof
The following proof
is due to David Gries (private communication) and is in the format advocated in
[]. The proof is based on these principles:
P
(Contrapositive)
The equivalence of PQ and ¬Q ¬P.
(DeMorgan) The equivalence of ¬(P∨Q)
and , ¬P¬Q.
The equivalence in any totally ordered set of
¬(x>y) and x≤y.
In this proof, " ¬" denotes negation.
Proof: ,,
which is true
by the transitive law.
This proof involves symbol manipulation using logical rules and
has the advantage that it is easy to check mechanically. It also shows that the
proof works in a wider context (any totally ordered set).
Another conceptual proof
The conceptual proof
given above provides a geometric visualization of the situation required by the
hypothesis of the theorem, and this
visualization makes the truth of the theorem obvious. But there is a sense of
"conceptual", related to the idea of conceptual definition given
under elementary, that does not have a geometric component.
This is the idea that a proof is conceptual if it appeals to concepts and
theorems at a high level of abstraction.
To a person familiar with the elementary rules of first order
logic, the
symbolic proof just given becomes a conceptual proof (this happened to me):
"Why, in a totally ordered set that statement is nothing but the
contrapositive of transitivity!" Although this statement is merely a
summary of the symbolic proof, it is enough to enable anyone conversant with
simple logic to generate
the symbolic proof. Furthermore, in my case at least, it provides an aha
experience. Citations: Rub89421, BieGro86425.
