the decimal system was in common use in the Islamic
world, and from there it was quickly transmitted to
Europe. Arab scholars maintained a keen interest in the
work of Indian mathematicians for the centuries that
followed and took an active role in preserving and
translating many Indian texts.
See also A
RABIC MATHEMATICS
;
BASE OF A NUMBER
SYSTEM
.
indirect proof (proof by contradiction, reductio ad
absurdum) Most claims made in mathematics are
statements of the form:
If the premise Ais true, then the conclusion B
is true.
An indirect proof of such a statement attempts to
establish the validity of the claim by assuming that the
premise Ais true and showing, consequently, that the
conclusion Bcannot be false. One does this by explor-
ing the logical consequences of assuming Aand “not
B” until, at some point, a contradiction (such as, 1 + 1
= 3, for instance) is reached. Based on the belief that
mathematics should be free from absurdities, mathe-
maticians generally accept this approach as sufficient
for establishing the validity of B.
As an example, we prove: for a natural number n,
if n2is even, then n is even. We base the proof on
known facts about even and odd numbers, and the
standard algebraic manipulations.
Proof: assume that n2is even, and assume, to
the contrary, that nis not.
Then it must be the case that nis odd.
Consequently, nis one more than a multiple of
2 and can be written in the form 2k+ 1, for
some number k.
This means that n2is given by n2= (2k+
1)2= 4k2+ 4k+ 1 = 2(2k2+ 2k) + 1 and so is
also one more than a multiple of 2.
We conclude that n2is both even and
odd—clearly a contradiction.
It cannot be the case, then, that nis odd.
It must therefore be even.
Notice in this proof that we assumed premise Ato
be true, and arrived at the contradiction that “not A”
also holds. An indirect proof that arrives at a contra-
diction of this type is usually called a “proof using the
contrapositive”: we established the validity of “A
implies B” by demonstrating that the
CONTRAPOSITIVE
“not Bimplies not A” holds. E
UCLID
’
S PROOF OF THE
INFINITUDE OF PRIMES
is an example of an indirect
proof that does not rely on the contrapositive. E
UCLID
(300–260
B
.
C
.
E
.) was the first mathematician to exten-
sively employ the technique of indirect proof.
A
DIRECT PROOF
attempts to establish the validity
of a proposition “if A, then B” by assuming that the
premise Ais true and following its logical consequences
until statement Bis established. Not all propositions,
however, are amenable to a direct approach. For exam-
ple, given that a squared number n2is even (that is, n2
= 2m, say) it is not immediate how one should proceed
to establish directly that nis consequently even.
Any indirect proof relies on the assumption that a
statement that cannot be false must be true. Some
philosophers and mathematicians who study the
LAWS
OF THOUGHT
seriously question this assumption.
See also
CONTRADICTION
;
DEDUCTIVE
/
INDUCTIVE
REASONING
;
PROOF
;
QED
;
THEOREM
.
induction (complete induction, finite induction, math-
ematical induction) The method of proof known as
mathematical induction has been used by scholars since
the earliest times, but it was not until 1838, thanks to
the work of English logician and mathematician
A
UGUSTUS
D
E
M
ORGAN
, that the principle was prop-
erly identified and described. In a formal context, the
principle of mathematical induction asserts:
If a set Sof numbers satisfies the following two
properties:
i. The number 1 belongs to S.
ii. If a number kbelongs to S, then so
does its successor k+ 1.
then it must be the case that Scontains all the
natural numbers 1, 2, 3,…
(This principle appears as an
AXIOM
in G
IUSEPPE
P
EANO
’s set of postulates for the construction of the
natural numbers.) Often the set Sis taken to be a set of
natural numbers nfor which some property or formula
P(n) is true: S= {n: P(n) holds}.
To illustrate the principle of induction, we shall
prove that, for every natural number n, we have that
1 + 2 + 3 +…+ nequals n(n+ 1). Let P(n) represent
1
–
2
induction 265