proof A demonstration that one statement follows
from another via a process of pure logical reasoning is
called a proof. All proofs are based on a set of
premises, that is, statements that have been previously
established as valid, or are taken as
AXIOM
s, and follow
a sequence of deductions that establish that the final
statement presented—the conclusion—is true. Alterna-
tively, one can think of a proof as a written piece
demonstrating logical reasoning that convinces all
readers of the absolute validity of the result—given the
assumptions made as premises.
As an example, the following argument is a proof.
It assumes that the basic principles of algebra are
understood, and that two basic facts about natural
numbers are known, namely, that every natural number
is either even or odd, and that every even number is a
multiple of 2.
Claim: If nis a natural number such that n2is
odd, then nitself is odd.
Proof: It cannot be the case that nis even,
for then nwould be of the form 2k, making n2
= (2k)2= 4k2= 2(2k2) even, not odd. Thus n
must also be odd.
The use of the term proof in mathematics differs
from the use of the word in the scientific method. Gen-
erally, a scientist will put forward a hypothesis to
explain a physical phenomenon, and then perform
experiments to test that hypothesis. If the results of the
investigation consistently conform to the hypothesis
(and moreover, if the hypothesis leads to predictions
about other physical phenomena that are later con-
firmed), a scientist may say that a physical principle has
been proved. For example, that matter is composed of
fundamental elements as listed in a periodic table is a
proven scientific theory. It is, however, a result estab-
lished solely on experience and observation.
Observation, alone, however, does not constitute
proof in mathematics, and can lead to erroneous con-
clusions. For example, one may be tempted to argue
that the equation = a+ bis a valid algebraic
identity since, after all, it works for a= 1 and b= 0, for
instance. After testing all the numbers from 1 to 1,000,
for instance, one might conclude that all numbers are
smaller than 1 million. (One thousand instances that
support a statement surely make it convincing.) Both
claims are, of course, absurd. For example, =
a+ bdoes not hold for a= b= 1, and 1,000,001 is not
smaller than 1 million. These examples illustrate why a
mathematician will only accept justifications based on
logical reasoning and not on observation alone.
There are several different methods of proof. A
DIRECT PROOF
proceeds linearly from premises to con-
clusion, whereas an
INDIRECT PROOF
(also called a
PROOF BY CONTRADICTION
, or reductio ad absurdum)
assumes the falsehood of the desired conclusion and
shows that to be impossible. Many claims in
NUMBER
THEORY
and
GRAPH THEORY
are also established by the
method of mathematical
INDUCTION
.
In 1976 two mathematicians Kenneth Appel and
Wolfgang Haken presented a computer-generated
“proof” of the famous
FOUR
-
COLOR THEOREM
. Relying
on 1,200 hours of computer computation to verify
nearly 2,000 special clauses. No individual, unfortu-
nately, has the means to check the details of the work
and be personally convinced of the validity of the argu-
ment. The question of whether or not the work of Appel
and Harken constituted a “proof” caused great contro-
versy in the mathematics community. For ease of mind,
mathematicians today still seek a purely mathematical
proof of the result, avoiding computer help altogether.
See also
BRUTE FORCE
;
DEDUCTIVE
/
INDUCTIVE REA
-
SONING
;
THEOREM
.
proof by contradiction (reductio ad absurdum)
See
INDIRECT PROOF
.
proof by contraposition See
CONTRAPOSITIVE
.
proportional Two quantities xand yare said to be
directly proportional if their
RATIO
is always constant.
This means = k, or y= kx, for some nonzero constant
kcalled the constant of proportionality. For example,
Hooke’s law in physics asserts that the force Fexerted
by a spring extended a small length xis directly pro-
portional to that length: F= kx. Here kis called the
spring constant.
If yis directly proportional to x, we write y∝xand
say that yvaries directly as x. Of course it also follows
that x∝y. When the values of yare plotted against the
corresponding values of x, the graph obtained is a
straight line through the origin.
y
–
x
√a2+ b2
√a2+ b2
420 proof