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 AXIOMs, and follow
a sequence of deductions that establish that the final
statement presented—the conclusion—is true. Alternatively, 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 n is a natural number such that n
2 is
odd, then n itself is odd.
Proof: It cannot be the case that n is even,
for then n would be of the form 2k, making n
2
= (2k)
2 = 4k
2 = 2(2k
2
) 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. Generally, 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 confirmed), 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 established solely on experience and observation.
Observation, alone, however, does not constitute
proof in mathematics, and can lead to erroneous conclusions. For example, one may be tempted to argue
that the equation
= a + b is 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 + b does 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 conclusion, 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, unfortunately, has the means to check the details of the work
and be personally convinced of the validity of the argument. The question of whether or not the work of Appel
and Harken constituted a “proof” caused great controversy 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 REASONING; THEOREM.
proof by contradiction (reductio ad absurdum)
See INDIRECT PROOF.
proof by contraposition See CONTRAPOSITIVE.
proportional Two quantities x and y are said to be
directly proportional if their RATIO is always constant.
This means
= k, or y = kx, for some nonzero constant
k called the constant of proportionality. For example,
Hooke’s law in physics asserts that the force F exerted
by a spring extended a small length x is directly proportional to that length: F = kx. Here k is called the
spring constant.
If y is directly proportional to x, we write y ∝ x and
say that y varies directly as x. Of course it also follows
that x ∝ y. When the values of y are plotted against the
corresponding values of x, the graph obtained is a
straight line through the origin.
y
–
x
√a
2 + b
2
√a
2 + b
2
420 proof
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 AXIOMs, and follow
a sequence of deductions that establish that the final
statement presented—the conclusion—is true. Alternatively, 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 n is a natural number such that n
2 is
odd, then n itself is odd.
Proof: It cannot be the case that n is even,
for then n would be of the form 2k, making n
2
= (2k)
2 = 4k
2 = 2(2k
2
) 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. Generally, 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 confirmed), 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 established solely on experience and observation.
Observation, alone, however, does not constitute
proof in mathematics, and can lead to erroneous conclusions. For example, one may be tempted to argue
that the equation
= a + b is 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 + b does 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 conclusion, 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, unfortunately, has the means to check the details of the work
and be personally convinced of the validity of the argument. The question of whether or not the work of Appel
and Harken constituted a “proof” caused great controversy 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 REASONING; THEOREM.
proof by contradiction (reductio ad absurdum)
See INDIRECT PROOF.
proof by contraposition See CONTRAPOSITIVE.
proportional Two quantities x and y are said to be
directly proportional if their RATIO is always constant.
This means
= k, or y = kx, for some nonzero constant
k called the constant of proportionality. For example,
Hooke’s law in physics asserts that the force F exerted
by a spring extended a small length x is directly proportional to that length: F = kx. Here k is called the
spring constant.
If y is directly proportional to x, we write y ∝ x and
say that y varies directly as x. Of course it also follows
that x ∝ y. When the values of y are plotted against the
corresponding values of x, the graph obtained is a
straight line through the origin.
y
–
x
√a
2 + b
2
√a
2 + b
2
420 proof