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 ARABIC 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 A is 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 A is true and showing, consequently, that the
conclusion B cannot be false. One does this by exploring the logical consequences of assuming A and “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, mathematicians generally accept this approach as sufficient
for establishing the validity of B.
As an example, we prove: for a natural number n,
if n
2 is 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 n
2 is even, and assume, to
the contrary, that n is not.
Then it must be the case that n is odd.
Consequently, n is one more than a multiple of
2 and can be written in the form 2k + 1, for
some number k.
This means that n
2 is given by n
2 = (2k +
1)
2 = 4k
2 + 4k + 1 = 2(2k
2 + 2k) + 1 and so is
also one more than a multiple of 2.
We conclude that n
2 is both even and
odd—clearly a contradiction.
It cannot be the case, then, that n is odd.
It must therefore be even.
Notice in this proof that we assumed premise A to
be true, and arrived at the contradiction that “not A”
also holds. An indirect proof that arrives at a contradiction 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 B implies not A” holds. EUCLID’S PROOF OF THE
INFINITUDE OF PRIMES is an example of an indirect
proof that does not rely on the contrapositive. EUCLID
(300–260 B.C.E.) was the first mathematician to extensively 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 A is true and following its logical consequences
until statement B is established. Not all propositions,
however, are amenable to a direct approach. For example, given that a squared number n
2 is even (that is, n
2
= 2m, say) it is not immediate how one should proceed
to establish directly that n is 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, mathematical 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
AUGUSTUS DE MORGAN, that the principle was properly identified and described. In a formal context, the
principle of mathematical induction asserts:
If a set S of numbers satisfies the following two
properties:
i. The number 1 belongs to S.
ii. If a number k belongs to S, then so
does its successor k + 1.
then it must be the case that S contains all the
natural numbers 1, 2, 3,…
(This principle appears as an AXIOM in GIUSEPPE
PEANO’s set of postulates for the construction of the
natural numbers.) Often the set S is taken to be a set of
natural numbers n for 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 +…+ n equals n(n + 1). Let P(n) represent
1
–
2
induction 265
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 ARABIC 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 A is 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 A is true and showing, consequently, that the
conclusion B cannot be false. One does this by exploring the logical consequences of assuming A and “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, mathematicians generally accept this approach as sufficient
for establishing the validity of B.
As an example, we prove: for a natural number n,
if n
2 is 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 n
2 is even, and assume, to
the contrary, that n is not.
Then it must be the case that n is odd.
Consequently, n is one more than a multiple of
2 and can be written in the form 2k + 1, for
some number k.
This means that n
2 is given by n
2 = (2k +
1)
2 = 4k
2 + 4k + 1 = 2(2k
2 + 2k) + 1 and so is
also one more than a multiple of 2.
We conclude that n
2 is both even and
odd—clearly a contradiction.
It cannot be the case, then, that n is odd.
It must therefore be even.
Notice in this proof that we assumed premise A to
be true, and arrived at the contradiction that “not A”
also holds. An indirect proof that arrives at a contradiction 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 B implies not A” holds. EUCLID’S PROOF OF THE
INFINITUDE OF PRIMES is an example of an indirect
proof that does not rely on the contrapositive. EUCLID
(300–260 B.C.E.) was the first mathematician to extensively 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 A is true and following its logical consequences
until statement B is established. Not all propositions,
however, are amenable to a direct approach. For example, given that a squared number n
2 is even (that is, n
2
= 2m, say) it is not immediate how one should proceed
to establish directly that n is 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, mathematical 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
AUGUSTUS DE MORGAN, that the principle was properly identified and described. In a formal context, the
principle of mathematical induction asserts:
If a set S of numbers satisfies the following two
properties:
i. The number 1 belongs to S.
ii. If a number k belongs to S, then so
does its successor k + 1.
then it must be the case that S contains all the
natural numbers 1, 2, 3,…
(This principle appears as an AXIOM in GIUSEPPE
PEANO’s set of postulates for the construction of the
natural numbers.) Often the set S is taken to be a set of
natural numbers n for 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 +…+ n equals n(n + 1). Let P(n) represent
1
–
2
induction 265