Basic Logic, Lecture 2
Luca Incurvati
[email protected]
Luca Incurvati ([email protected]) Basic Logic 2 1 / 36
Outline
1 Proof by mathematical induction
2 Beyond number theory
3 Strong Induction
4 Induction on complexity of sentences
Luca Incurvati ([email protected]) Basic Logic 2 2 / 36
Proof by mathematical induction
The Principle of Mathematical Induction
Principle of Mathematical Induction
Let P be any property such that:
0 has P;
for every natural number n, if n has P, then n + 1 has P.
Then every natural number has P.
The domino example.
Luca Incurvati ([email protected]) Basic Logic 2 3 / 36
Proof by mathematical induction
On the justification of induction
Suppose you have proved P(0) and that for all n, if n has P, then so
does n + 1.
Then, pick a natural number m. You’d be justified in writing down:
0 has P
if 0 has P then 1 has P
...
if m − 1 has P, then m has P.
By m-many applications of modus ponens, you can conclude that m
has P.
Since m was arbitrary, the point generalizes: every number has P.
(Will this convince the sceptic?)
Luca Incurvati ([email protected]) Basic Logic 2 4 / 36
Proof by mathematical induction
Proof by mathematical induction
Mathematical Induction
Goal: Something of the form ∀n ∈ NP(n).
Strategy:
1 Prove P(0). [This is called the base case or base clause.]
2 Prove ∀n ∈ N(P(n) → P(n + 1)). [This is called the induction step or
inductive clause.]
The property P is called the induction property.
Luca Incurvati ([email protected]) Basic Logic 2 5 / 36
Proof by mathematical induction
Proof by mathematical induction
Scratch work
Before using strategy:
Givens Goal
— ∀n ∈ NP(n)
—
After using strategy:
Givens Goal
— P(0)
— ∀n ∈ N(P(n) → P(n + 1))
Luca Incurvati ([email protected]) Basic Logic 2 6 / 36
Proof by mathematical induction
Proof by mathematical induction
Form of final proof
Proof.
Base case: Proof of P(0).
Induction step: Proof of ∀n ∈ N(P(n) → P(n + 1)).
Luca Incurvati ([email protected]) Basic Logic 2 7 / 36
Proof by mathematical induction
Proof by mathematical induction
Scratch work
One of the goals in the Scratch work above is a universally quantified
statement. To prove it, we typically let n be an arbitrary number and
suppose that P(n) holds. Doing this we go from:
Givens Goal
— ∀n ∈ N(P(n) → P(n + 1))
—
to:
Givens Goal
n ∈ N P(n + 1)
P(n)
The supposition that P(n) holds is sometimes called the induction
hypothesis.
Luca Incurvati ([email protected]) Basic Logic 2 8 / 36
Proof by mathematical induction
Mathematical Induction: Example
Theorem
Every natural number is either even or odd.
Luca Incurvati ([email protected]) Basic Logic 2 9 / 36
Proof by mathematical induction
Mathematical Induction: Example
Theorem
Every natural number is either even or odd.
Scratch work
Our induction property is, of course, x is either even or odd.
To say that a natural number n is even is to say that there is a k such
that n = 2k.
And to say that n is odd is to say that there is a k such that
n = 2k + 1.
The base case is obvious; to prove the induction step, we let n be an
arbitrary number and suppose that it has the induction property. We
then show on this basis that n + 1 also has the induction property.
And, in this case, that’s easy!
Luca Incurvati ([email protected]) Basic Logic 2 9 / 36
Proof by mathematical induction
Mathematical Induction: Example
Proof.
By mathematical induction.
Base case: Clearly, 0 = 2 · 0, so 0 has the induction property.
Induction step: Let n be an arbitrary natural number and suppose that n
has the induction property. There are two cases to consider.
Suppose n is even, i.e. n = 2k for some k. Then n + 1 = 2k + 1, i.e.
n + 1 is odd.
Suppose n is odd, i.e. n = 2k + 1 for some k. Then
n + 1 = 2k + 2 = 2(k + 1). i.e. n + 1 is even.
Either way, n + 1 has the induction property, as required.
Luca Incurvati ([email protected]) Basic Logic 2 10 / 36
Proof by mathematical induction
Mathematical Induction: Example 2
Theorem
n2 +n
For all n ∈ N, 0 + 1 + 2 + · · · + n = 2 .
Luca Incurvati ([email protected]) Basic Logic 2 11 / 36
Proof by mathematical induction
Mathematical Induction: Example 2
Theorem
n2 +n
For all n ∈ N, 0 + 1 + 2 + · · · + n = 2 .
Scratch work
The base case is easy. To prove the induction step, we consider that
we have the following givens and goal:
Givens Goal
n∈N 0 + 1 + 2 + · · · + n + (n + 1) =
n2 +n (n+1)2 +(n+1)
0 + 1 + 2 + ··· + n = 2 2
Luca Incurvati ([email protected]) Basic Logic 2 11 / 36
Proof by mathematical induction
Mathematical Induction: Example 2
Scratch work continued
We now observe that the left-hand side of the goal is the same as the
left-hand side of the induction hypothesis, but with n + 1 added on.
So we try and add this to both sides of the induction hypothesis.
Expanding the right-hand side of the equation, thinking about our
2
goal, we eventually get (n+1) 2+(n+1) .
Luca Incurvati ([email protected]) Basic Logic 2 12 / 36
Proof by mathematical induction
Mathematical Induction: Example 2
Proof.
By mathematical induction.
2
Base case: Clearly, 0 = 0 2+0 , so 0 has the induction property.
Induction step: Let n be an arbitrary natural number and suppose that n
has the induction property, that is
n2 + n
0 + 1 + 2 + ··· + n =
2
Then, we have
n2 +n
0 + 1 + 2 + · · · + n + (n + 1) = 2 + (n + 1)
n2 +n+2(n+1)
= 2
(n2 +2n+1)+(n+1)
= 2
(n+1)2 +(n+1)
= 2 .
Luca Incurvati ([email protected]) Basic Logic 2 13 / 36
Proof by mathematical induction
Mathematical Induction: Example 3
Example
n(n+1)(n+2)
Prove that for all n ∈ N, 0 · 1 + 1 · 2 + 2 · 3 + · · · + n(n + 1) = 3 .
Luca Incurvati ([email protected]) Basic Logic 2 14 / 36
Proof by mathematical induction
Mathematical Induction: Example 3
Example
n(n+1)(n+2)
Prove that for all n ∈ N, 0 · 1 + 1 · 2 + 2 · 3 + · · · + n(n + 1) = 3 .
Scratch work
We proceed as before. The base case is easy. To prove the induction
step, we consider that we have
n(n + 1)(n + 2)
0 · 1 + 1 · 2 + 2 · 3 + · · · + n(n + 1) =
3
as the induction hypothesis and
(n + 1)(n + 2)(n + 3)
0·1+1·2+2·3+· · ·+n(n+1)+(n+1)(n+2) =
3
as our goal.
Luca Incurvati ([email protected]) Basic Logic 2 14 / 36
Proof by mathematical induction
Mathematical Induction: Example 3
Scratch work continued
We now observe that the left-hand side of the goal is the same as the
left-hand side of the induction hypothesis, but with (n + 1)(n + 2)
added on.
So we try and add this to both sides of the induction hypothesis.
Expanding the right-hand side of the equation, thinking about our
goal, we eventually get (n+1)(n+2)(n+3)
3 .
Luca Incurvati ([email protected]) Basic Logic 2 15 / 36
Proof by mathematical induction
Mathematical Induction: Example 3
Proof.
By mathematical induction.
Base case: Clearly, 0 · (0 + 1) = 0(0+1)(0+2)
3 .
Induction step: Let n be an arbitrary natural number and suppose
n(n + 1)(n + 2)
0 · 1 + 1 · 2 + 2 · 3 + · · · + n(n + 1) =
3
Then, we have
0 · 1 + 1 · 2 + 2 · 3 + ···+
n(n+1)(n+2)
+n(n + 1) + (n + 1)(n + 2) = 3 + (n + 1)(n + 2)
n(n+1)(n+2)+3(n+1)(n+2)
= 3
(n+1)(n+2)(n+3)
= 3 .
Luca Incurvati ([email protected]) Basic Logic 2 16 / 36
Beyond number theory
1 Proof by mathematical induction
2 Beyond number theory
3 Strong Induction
4 Induction on complexity of sentences
Luca Incurvati ([email protected]) Basic Logic 2 17 / 36
Beyond number theory
Mathematical Induction: Example 4
Theorem
For every set A, if A has n elements, then P(A) has 2n elements.
Luca Incurvati ([email protected]) Basic Logic 2 18 / 36
Beyond number theory
Mathematical Induction: Example 4
Theorem
For every set A, if A has n elements, then P(A) has 2n elements.
Scratch work
Our induction property is for every set A, if A has x elements, then
P(A) has 2x elements.
The base case is easy. To prove the induction step, we consider that
our induction hypothesis is: for every set A, if A has n elements, then
P(A) has 2n elements; and our goal is: for every set A, if A has
(n + 1) elements, then P(A) has 2(n+1) elements.
Luca Incurvati ([email protected]) Basic Logic 2 18 / 36
Beyond number theory
Mathematical Induction: Example 4
Scratch work continued
We first consider an arbitrary A, so that our goal becomes: if A has
(n + 1) elements, then P(A) has 2(n+1) elements.
This is a conditional statement, so we suppose the antecedent and try
to prove the consequent.
Now, what can we do with the suppposition that A has (n + 1)
elements? Our induction hypothesis tells us something about sets
with n elements. . .
The thought suggests itself to remove an element a from A, so that
we can somehow use the induction hypothesis.
It turns out that this thought actually works!
Luca Incurvati ([email protected]) Basic Logic 2 19 / 36
Beyond number theory
Mathematical Induction: Example 4
Proof.
By mathematical induction.
Base case: If A has 0 elements, then A = ∅, and P(∅) = {∅}, which has
1 = 20 elements.
Induction step: Let n be an arbitrary natural number and suppose that n
has the induction property, that is suppose that for every set A with n
elements, P(A) has 2n elements. Now suppose that A has n + 1 elements.
Let a be any element of A and let B = A \ {a}. Since B has n elements,
P(B) has, by the induction hypothesis, 2n elements. Now there are two
kinds of subsets of A: those that contain a as an element and those that
do not. The latter are just the subsets of B, and so there are 2n of these,
since P(B) has 2n elements. The former are sets of the form X ∪ {a},
where X ∈ P(B), and there are 2n of these as well, since P(B) has 2n
elements. So P(A) has 2n + 2n = 2n+1 elements.
Luca Incurvati ([email protected]) Basic Logic 2 20 / 36
Strong Induction
1 Proof by mathematical induction
2 Beyond number theory
3 Strong Induction
4 Induction on complexity of sentences
Luca Incurvati ([email protected]) Basic Logic 2 21 / 36
Strong Induction
The Principle of Strong Induction
Principle of Strong Induction
Let P be any property. Suppose that for every natural number n, if all the
natural numbers less than n have P, then n itself has P. Then, every
natural number has P.
Luca Incurvati ([email protected]) Basic Logic 2 22 / 36
Strong Induction
On the justification of strong induction
The idea is the following. Suppose you have proved the supposition.
Then, if you instantiate the supposition with 0, you get that if all
numbers less than 0 have P, then 0 itself has P.
But (trivially) all numbers less than 0 have P (for there are none), so
P(0).
Now instantiate the supposition with 1. Then you get that if all
numbers less than 1 have P, then 1 itself has P.
There is only one number less than 1, namely 0, and we know that 0
has P. So P(1).
And you know how this continues. . .
Luca Incurvati ([email protected]) Basic Logic 2 23 / 36
Strong Induction
On the justification of strong induction
But we can in fact prove the Principle of Strong Induction from the
Principle of Mathematical Induction (and the converse can also be
done):
Theorem
The Principle of Mathematical Induction implies the Principle of Strong
Induction.
Luca Incurvati ([email protected]) Basic Logic 2 24 / 36
Strong Induction
On the justification of strong induction
Proof.
Suppose that for every n, if all the numbers less than n have P, then n
itself has P. We want to show that every number has P. To this end, we
let Q be the property every number less than x has P. We can now
establish the claim by mathematical induction.
Base case: 0 has Q vacuously, since 0 is the smallest number.
Induction step: Let n be an arbitrary number and suppose that n has Q.
That is, suppose that every number less than n has P. But our initial
supposition was that for every n, if all numbers less than n have P, then n
itself has P. So we can conclude that n has P. Hence, every number less
than n + 1 has P, that is to say n + 1 has Q.
Luca Incurvati ([email protected]) Basic Logic 2 25 / 36
Strong Induction
Proof by strong induction
Strong Induction
Goal: Something of the form ∀n ∈ NP(n).
Strategy:
1 Prove ∀n((∀k < nP(k)) → P(n)), where n and k range over natural
numbers.
Typically, what we do is let n be an arbitrary natural number, assume
that ∀k < nP(k) (in this case, this is what we call the induction
hypothesis) and then prove P(n).
Luca Incurvati ([email protected]) Basic Logic 2 26 / 36
Strong Induction
Proof by strong induction
Scratch work
Thus, typically we go from:
Givens Goal
— ∀n ∈ NP(n)
—
to:
Givens Goal
— P(n)
—
n∈N
∀k < nP(k)
Luca Incurvati ([email protected]) Basic Logic 2 27 / 36
Strong Induction
Strong Induction: Example
Theorem
Every number greater than 1 is either prime or a product of primes.
Luca Incurvati ([email protected]) Basic Logic 2 28 / 36
Strong Induction
Strong Induction: Example
Theorem
Every number greater than 1 is either prime or a product of primes.
Proof.
We use strong induction. Let n be an arbitrary number greater than 1 and
suppose that for every k, if 1 < k < n, then k is either prime or a product
of primes. If n is prime, then we are done. If n is not prime, then n = ab
with both n > a and n > b. Since n = ab > a, it must be the case that
b > 1, and similarly for b. Thus, by the induction hypothesis, each of a
and b is either prime or a product of primes. But then n = ab is also a
product of primes.
Luca Incurvati ([email protected]) Basic Logic 2 28 / 36
Induction on complexity of sentences
1 Proof by mathematical induction
2 Beyond number theory
3 Strong Induction
4 Induction on complexity of sentences
Luca Incurvati ([email protected]) Basic Logic 2 29 / 36
Induction on complexity of sentences
Proof by induction
We can use induction to establish claims about entities other than
natural numbers.
We do this by associating each of those entities with a natural
number.
For instance, in the proof of strong completeness (for both
propositional logic and first-order logic) we’ll establish that each item
in a list Γ0 , Γ1 , . . . of sets of sentences is consistent by establishing:
Base clause: that Γ0 is consistent.
Inductive clause: that for all natural numbers n, if Γn is consistent, so
is Γn+1 .
Luca Incurvati ([email protected]) Basic Logic 2 30 / 36
Induction on complexity of sentences
Complexity
Proposition
Every sentence of LPL has as many instances of ‘(’ as instances of ‘)’.
We want to use induction, but the property x has as many instances
of ‘(’ as instances of ‘)’ is a property of sentences, not of numbers.
The easiest way to associate sentences with natural numbers this is
by considering the complexity of sentences, where the complexity of
a sentence ϕ of LPL is the number n of instances of connectives that
ϕ contains.
Luca Incurvati ([email protected]) Basic Logic 2 31 / 36
Induction on complexity of sentences
Induction on complexity of sentences
We could now prove Proposition 5.1 by induction on numbers, taking
these to represent the complexity of sentences.
But it will easier if we introduce the following inductive principle,
which concerns sentences of LPL in a more direct manner.
Luca Incurvati ([email protected]) Basic Logic 2 32 / 36
Induction on complexity of sentences
Induction on complexity of sentences
Principle of Induction on the Complexity of Sentences of LPL
Let ϕ and ψ be sentences of LPL and let P be any property such that:
(i) Each atomic sentence of LPL has P.
(ii) If ϕ has P, then ¬ϕ has P.
(iii) If ϕ and ψ have P, then (ϕ ∧ ψ) has P.
(iv) If ϕ and ψ have P, then (ϕ ∨ ψ) has P.
(v) If ϕ and ψ have P, then (ϕ → ψ) has P.
Then every sentence of LPL has P.
(i) is the base clause of the induction. Typically, we show that (ii)
holds by supposing that ϕ has P (induction hypothesis) and showing
that ¬ϕ has P under this supposition. Similarly for cases (iii)–(v).
Induction on the complexity of sentences of LPL can be proved by
using ordinary induction.
Luca Incurvati ([email protected]) Basic Logic 2 33 / 36
Induction on complexity of sentences
Example
Proof of Proposition 5.1.
By induction on the complexity of sentences of LPL .
(i) ϕ is atomic.If ϕ is atomic, it contains no brackets. So it has exactly
as many instances of ‘(’ as instances of ‘)’.
(ii) ϕ is ¬ψ. Suppose that ψ has exactly as many instances of ‘(’ as
instances of ‘)’. Then clearly so does ¬ψ.
(iii) ϕ is (ψ ∧ χ). By induction hypothesis, ψ contains exactly as many
instances of ‘(’ as instances of ‘)’, say i; and χ contains exactly as
many instances of ‘(’ as of ‘)’, say j. Hence ϕ contains i + j + 1
instances of ‘(’ , and i + j + 1 instances of ‘)’.
(iv) Similar to case (iii).
(v) Similar to case (iii).
Luca Incurvati ([email protected]) Basic Logic 2 34 / 36
Induction on complexity of sentences
Induction on the complexity of sentences
Induction on the complexity of sentences can be justified by appealing
to ordinary induction by applying induction on the property every
sentence of complexity x has P. The proof proceeds as follows.
If each atomic sentence has P, then every sentence of complexity 0
has P.
We can build more complex sentences from simpler ones in one out of
four possible ways, one for each connective.
If we can show that for each possible way, if every sentence of
complexity n has P, then every sentence of complexity n + 1 has P,
then we will have shown this in general.
But then, by ordinary induction, we can conclude that every sentence
has P.
Luca Incurvati ([email protected]) Basic Logic 2 35 / 36
Induction on complexity of sentences
Induction and recursion
We have used an inductive principle to prove something which
concerns a class of entities which is recursively defined.
This is not uncommon, and should be expected: recursive definitions
tell us how to construct objects stage-by-stage; proofs by (strong)
induction involve showing that something holds at later stages if it
has held at every stage so far.
Luca Incurvati ([email protected]) Basic Logic 2 36 / 36
