4Counting and integers
IA Numbers and Sets
4.3 Well-ordering and induction
Several proofs so far involved “take the least integer such that”, e.g. division
algorithm; or involved a sequence of moves “and so on. . . ” e.g. Euclid’s algorithm,
every number is a product of primes. We rely on the following:
Theorem
(Weak Principle of Induction)
.
Let
P
(
n
) be a statement about the
natural number n. Suppose that
(i) P (1) is true
(ii) (∀n) P (n) ⇒ P (n + 1)
Then P (n) is true for all n ≥ 1.
Example (Tower of Hanoi). Referring to the image below,
n
.
.
.
3
2
1
A B C
The objective is to move the
n
rings on peg A to peg B, with the constraints
that you can only move one ring at a time, and you can never place a larger ring
onto a smaller ring.
Now claim that this needs exactly 2
n
− 1 moves.
Let
P
(
n
) be “
n
rings needs 2
n
−
1 moves”. Note that this statement contains
two assertions — (1) we can do it in 2
n
− 1 moves; (2) We can’t do it in fewer.
First consider P (1). We simply have to move the ring from A to B.
Suppose we have
n
+ 1 rings. We can move the top
n
rings to peg C, then
move the bottom ring to peg B, then move the
n
rings from
C
back to
B
.
Assuming P (n) is true, this needs at most 2 × (2
n
− 1) + 1 = 2
n+1
− 1 moves.
Can we do it in fewer moves? To succeed, we must free the bottom ring,
so we must shift the top
n
rings to another pe.g. This needs
≥
2
n
−
1 moves
by
P
(
n
). Then we need to shift the bottom ring. Then we need to shift the
n
smaller rings to the big one. This needs
≥
2
n
−
1 moves by
P
(
n
). So this needs
≥ 2
n+1
− 1 moves altogether.
So we showed that
P
(
n
)
⇒ P
(
n
+ 1) (we used
P
(
n
) four times). By the WPI,
P (n) is true for all n.
Example.
All numbers are equal. Let
P
(
n
) be “if
{a
1
, ···a
n
}
is a set of
n
numbers, then
a
1
=
a
2
=
···a
n
”.
P
(1) is trivially true. Suppose we have
{a
1
, a
2
···a
n+1
}
. Assuming
P
(
n
), apply it to
{a
1
, a
2
···a
n
}
and
{a
2
, ··· , a
n+1
}
,
then
a
1
=
···
=
a
n
and
a
2
=
a
3
=
···
=
a
n+1
. So
a
1
=
a
2
=
···
=
a
n+1
. Hence
P (n) ⇒ P(n + 1). So P (n) is true for all n ∈ N.
Theorem. Inclusion-exclusion principle.
Proof.
Let
P
(
n
) be the statement “for any sets
A
1
···A
n
”, we have
|A
1
∪ ···∪
A
n
| =
P
i
|A
i
| −
P
i<j
|A
i
∩ A
j
| + ··· ± |A
i
∩ A
2
∩ ···∩ A
n
|”.
P
(1) is trivially true.
P
(2) is also true (see above). Now given
A
1
···A
n+1
,
Let B
i
= A
i
∩ A
n+1
for 1 ≤ i ≤ n. We apply P (n) both to the A
i
and B
i
.
Now observe that
B
i
∩ B
j
=
A
i
∩ A
j
∩ A
n+1
. Likewise,
B
i
∩ B
j
∩ B
k
=
A
i
∩ A
j
∩ A
k
∩ A
n+1
. Now
|A
1
∪ A
2
∪ ···∪ A
n+1
| = |A
1
∪ ···∪ A
n
| + |A
n+1
| −|(A
1
∪ ···∪ A
n
) ∩A
n+1
|
= |A
1
∪ ···∪ A
n
| + |A
n+1
| −|B
1
∪ ···∪ B
n
|
=
X
i≤n
|A
i
| −
X
i<j≤n
|A
i
∩ A
j
| + ··· + |A
n+1
|
−
X
i≤n
|B
i
| +
X
i<j≤n
|B
i
∩ B
j
| −···
Note
P
i≤n
|B
i
|
=
P
i≤n
|A
i
∩A
n+1
|
. So
P
i<j≤n
|A
i
∩A
j
|
+
P
i≤n
|B
i
|
=
P
i<j≤n+1
|A
i
∩A
j
|
,
and similarly for the other terms. So
=
X
i≤n+1
|A
i
| −
X
i<j≤n+1
|A
i
∩ A
j
| + ···
So P (n) ⇒ P (n + 1) for n ≥ 2. By WPI, P (n) is true for all n.
However, WPI is not quite what we want for “every number is a product of
primes”. We need a different form of induction.
Theorem
(Strong principle of induction)
.
Let
P
(
n
) be a statement about
n ∈ N
.
Suppose that
(i) P (1) is true
(ii) ∀n ∈ N, if P (k) is true ∀k < n then P (n) is true.
Then P (n) is true for all n ∈ N .
Note that (i) is redundant as it follows from (ii), but we state it for clarity.
Example.
“Evolutionary trees” Imagine that we have a mutant that can produce
two offsprings. Each offspring is either an animal or another mutant. A possible
evolutionary tree is as follows:
mutant
mutant
pig
mutant
slug
man
mutant
gnu
ibex
Let
P
(
n
) be the statement
n −
1 mutants produces
n
animals. Given some tree
with
n
animals, remove the top mutant to get two sub-trees, with
n
1
and
n
2
animals, where
n
1
+
n
2
=
n
. If
P
(
k
) is true
∀k < n
, then
P
(
n
1
) and
P
(
n
2
) are
true. So the total number of mutants is 1 + (
n
1
−
1) + (
n
2
−
1) =
n −
1. So
P
(
n
)
is true. Hence by strong principle of induction, P (n) is true for all n.
Theorem.
The strong principle of induction is equivalent to the weak principle
of induction.
Proof.
Clearly the strong principle implies the weak principle since if
P
(
n
)
⇒
P (n + 1), then (P (1) ∧ P (2) ∧ ···∧ P (n)) ⇒ P (n + 1).
Now show that the weak principle implies the strong principle. Suppose that
P
(1) is true and (
∀n
)
P
(1)
∧ P
(2)
∧ ··· ∧ P
(
n −
1)
⇒ P
(
n
). We want to show
that P (n) is true for all n using the weak principle.
Let
Q
(
n
) = “
P
(
k
) is true
∀k ≤ n
”. Then
Q
(1) is true. Suppose that
Q
(
n
) is
true. Then
P
(1)
∧P
(2)
∧···∧P
(
n
) is true. So
P
(
n
+ 1) is true. Hence
Q
(
n
+ 1)
is true. By the weak principle,
Q
(
n
) is true for all
n
. So
P
(
n
) is true for all
n.
While strong and weak induction are practically equivalent, they are rather
distinct conceptually. Weak induction is expressed in terms of “adding 1”, while
strong induction is based on the ordering of natural numbers.
It turns out that there is another statement about the natural numbers that
can be stated in terms of orders. We first formally define what it means to be
an order.
Definition
(Partial order)
.
A partial order on a set is a reflexive, antisymmetric
((aRb) ∧ (bRa) ⇔ a = b) and transitive relation.
Example.
The ordinary ordering of
N a ≤ b
is a partial order of
N
. Also,
a | b
on N is also a partial order.
Definition
(Total order)
.
A total order is a partial order where
∀a 6
=
b
, exactly
one of aRb or bRa holds. This means that every two things must be related.
Definition
(Well-ordered total order)
.
A total order is well-ordered if every
non-empty subset has a minimal element, i.e. if
S 6
=
∅
, then
∃m ∈ S
such that
x < m ⇒ x 6∈ S.
Example. Z
with the usual order is not well-ordered since the set of even
integers has no minimum. The positive rationals are also not well-ordered under
the usual order.
Theorem
(Well-ordering principle)
. N
is well-ordered under the usual order,
i.e. every non-empty subset of N has a minimal element.
Theorem.
The well-ordering principle is equivalent to the strong principle of
induction.
Proof.
First prove that well-ordering implies strong induction. Consider a
proposition P (n). Suppose P (k) is true ∀k < n implies P (n).
Assume the contrary. Consider the set
S
=
{n ∈ N
:
¬P
(
n
)
}
. Then
S
has a
minimal element
m
. Since
m
is the minimal counterexample to
P
,
P
(
k
) is true
for all
k < m
. However, this implies that
P
(
m
) is true, which is a contradiction.
Therefore P (n) must be true for all n.
To show that strong induction implies well-ordering, let
S ⊆ N
. Suppose
that
S
has no minimal element. We need to show that
S
is empty. Let
P
(
n
) be
the statement n 6∈ S.
Certainly 1
6∈ S
, or else it will be the minimal element. So
P
(1) is true.
Suppose we know that
P
(
k
) is true for all
k < n
, i.e.
k 6∈ S
for all
k < n
.
Now
n 6∈ S
, or else
n
will be the minimal element. So
P
(
n
) is true. By strong
induction, P (n) is true for all n, i.e. S is empty.
The well-ordering principle enables us to show that
P
(
n
) is true as follows:
if
P
(
n
) fails for some
n
, then there is a minimal counterexample
m
. Then we
try to show that this leads to a contradiction.
Example.
Proof that every number is a product of primes by strong induction:
Assume the contrary. Then there exists a minimal
n
that cannot be written as a
product of prime (by the well-ordering principle). If
n
is a prime, then
n
is a
product of primes. Otherwise, write
n
=
ab
, where 1
< a, b < n
. By minimality
of n, both a and b are products of primes. Hence so is n. Contradiction.
Example.
All numbers are interesting. Suppose that there are uninteresting
numbers. Then there exists a smallest uninteresting number. Then the property
of being the smallest uninteresting number is itself interesting. Contradiction.
Example.
Consider a total order on
N × N
by “lexicographic” or “dictionary”
order, i.e. (a, b) ≤ (c, d) if a < c or (a = c ∧ b ≤ d).
The Ackermann function is a function a : N
0
× N
0
→ N is defined by
a(m, n) =
n + 1 if m = 0
a(m −1, 1) if m > 0 and n = 0
a(m −1, a(m, n − 1)) if m > 0 and n > 0.
We want to show that this is well-defined.
Note that
a
(
m, n
) is expressed in terms of
a
at points (
x, y
)
<
(
m, n
). So
a
is well-defined if lexicographic order is well-ordered, i.e. every non-empty subset
has a minimal element (if
a
were not well-defined, then would be a smallest place
where the definition is bad. But definition of that point is defined in terms of
smaller points which are well defined).
We can see that
N
0
× N
0
is well-ordered: if
S ⊆ N
0
× N
0
is non-empty,
let
S
x
be the set of
{x ∈ N
: (
∃y
) (
x, y
)
∈ S}
, i.e. the set of all
x
-coordinates
of
S
. By the well-ordering principle,
S
x
has a minimal element
m
. Then let
S
y
=
{y ∈ N
0
: (
m, y
)
∈ S}
. Then
S
y
has a minimal element
n
. Then (
m, n
) is
the minimal element of S.