Lecture Overview L4−P. 1

Induction, Strong Induction, and Well-Ordering L4−P. 2

Induction, Strong Induction, and Well-Ordering Structural induction Induction and Recursive Algorithms Sets You may state the predicate of the Induction such that it includes all i’s

Q(n) ∀i, 2 ≤ i ≤ n i can be factored, and prove Q(n) using ordinary induction.

The induction and strong induction have “identical power”

Well-ordering:

Axiom: Every nonempty subset S ⊆ N has a smallest element

Theorem: Any tournament that contains a cycle contains a 3-cycle.

Let n be the smallest cycle length in a tournament. n must be at least 3. Suppose n ≥ 4. Consider the arrow between p_{1} and p_{3}. Either close a 3-cycle or yields a shorter cycle contradicting the assumption that n is smallest...

Structural induction L4−P. 4

Not only induction over N, Proofs for data types that are defined recursively

Fully parenthesized Boolean algebra

Definition: the set of fully parenthesized boolean expressions F

1. 0 and 1

2. if e, e′ ∈ F then (e ∧ e′) ∈ F.

3. if e, e′ ∈ F then (e ∨ e′) ∈ F.

4. if e ∈ F then (¬e) ∈ F.

5. F contains nothing else.

Theorem Every Boolean expression has the same number of left and right parentheses.

Base: 0 and 1

Inductive step: steps 1-4 preserve the assertion (if e and e′ satisfy the assertion so does the result).

Structural induction, Binary trees L4−P. 5

Definition: the set of binary trees T

1. A single node is in T

2. if t is in T, then an addition of a root node r and an arrow connecting t to be the left child (subtree) of the root is also in T

3. if t is in T, then an addition of a root node r and an arrow connecting t to be the right child (subtree) of the root is also in T

4. if t and t′ are in T, then an addition of a root node r and two arrows, where t is the left child and t′ is the right child is also in T Theorem: The number of edges in any binary tree is exactly one fewer than the number of nodes.

Base: a single-node tree

Inductive step: Steps 2 and 3 of the construction preserves the assertion: —- t has n − 1 edges and a node and an edge are added. Steps 4 of the construction preserves the assertion: —- t and t′ has n − 1 and n′ − 1 edges, respectively. 1 node is added (total n + n′ + 1) and 2 edges are added (total (n − 1) + (n′ − 1) + 2 = n + n′ edges).

Structural induction, Strings over alphabet A L4−P. 7

Definition: the set S of (finite length) strings over alphabet A:

1. λ, the empty string, is in S.

2. If s is in the set S and a ∈ A, then sa is in S.

3. S contains nothing else.

To prove a property P (s) for strings over alphabet A = {0, 1}:

Prove: ∀s ∈ S(P (s))

1. (Base) P (λ)

2. (Inductive step) ∀s ∈ S (P (s) ⇒ P (s0))

3. (Inductive step) ∀s ∈ S (P (s) ⇒ P (s1))

4. QED Structural induction on strings.

Theorem: In a string of 0s and 1s, the number of occurrence of the pattern 01 num(01, s) is less than or equal to the number of occurrence of 10 num(10, s), plus one.

It turned out that it is better to have a stronger induction predicate. (Adding 1 at the end may increase num(01, s))

num(01, s) ≤ num(10, s) + 1, and If s ends in 0 then num(01, s) ≤ num(10, s) (Thus, addition of 1 at the end will not violate our main predicate).

Base: λ Step:

1. (*(Inductive step) ∀s ∈ S (P (s) ⇒ P (s0))*)

1a. if s ends in 0 then num(01, s0) = num(01, s) and num(10, s0) = num(10, s) o.k.

1b. if s ends in 1 then num(01, s0) = num(01, s) and num(10, s0) = num(10, s) + 1 We should show that num(01, s0) ≤ num(10, s0) given num(01, s) ≤ num(10, s) + 1, replacing terms we get num(01, s0) ≤ num(10, s0) as needed.

2. (*(Inductive step) ∀s ∈ S (P (s) ⇒ P (s1))*)

2a. if s ends in 0 then num(01, s1) = num(01, s)+ 1 and num(10, s1) = num(10, s) We should show that num(01, s1) ≤ num(10, s1)+ 1 given num(01, s) ≤ num(10, s), replacing terms we get num(01, s1) − 1 ≤ num(10, s1) as required

2b. if s ends in 1 then num(01, s1) = num(01, s) and num(10, s1) = num(10, s) o.k.

Induction and Recursive Algorithms L4−P. 10

Why use induction? Induction and computation is one step at a time.

Can any 2^{n} by 2^{n} board be tiled with Ls ? the inductive proof is actually a procedure: break the board to four, tile each piece, and merge the tiling.

This is a recursive algorithm — it calls itself on smaller subproblems.

The ranking B, L and x is similar.

Induction and Recursive Algorithms – RSA and Exponentiation L4−P. 11

RSA is used in secure communication protocols SSH, SSL, etc.

Computes remainder r of x^{a} on division by b, where a and b are specially constructed large numbers.

If you know the right secret about the origin of a and b then you get x.

We will try to calculate the Exponentiation:

x^{0} = 1 x^{n} = x · x^{n−1}

Procedure Exp(x, n)

if n = 0 return 1 else return x ∗ Exp(x, n − 1)

Induction and Recursive Algorithms – Exponentiation L4−P. 12

Theorem: For all x, n ∈ N, a call to Exp(x, n) returns x^{n}

We should prove that the algorithm does not run forever

The algorithm returns the right value

By induction on n Base: Exp(x, 0) = x^{0} = 1 Step: Assume Exp(x, n) returns x^{n} and prove for Exp(x, n + 1) the else is chosen calling Exp(x, n), which returns x^{n}, thus we return x^{n+1}.

Induction and Recursive Algorithms – Fast Exponentiation L4−P. 13

n has 128 bits, we should call the procedure 2^{128} times........ if x^{a} = x^{2c} (a is even) then compute y = x^{c} and then y^{2}.

Otherwise, (a is odd) then compute y = x^{a−1} and then y · x.

Procedure F astExp(x, n)

if n = 0 return 1 else if n is even

let y = F astExp(x, n/2)

return y^{2}

else

let y = F astExp(x, (n − 1)/2)
return x ∗ y^{2}

Theorem: For all x, n ∈ N, a call to F astExp(x, n) returns x^{n}

Base: n = 0 Step: (strong induction) true for every k < n and prove for n n is even, say n = 2m then we call F astExp(x, m), by strong induction y = x^{m}, thus we return (x^{m})^{2} = x^{n} as required. n is odd, say n = 2m+1 then we call F astExp(x, m), by strong induction y = x^{m}, thus we return x · (x^{m})^{2} = x^{2m+1} Proof works for all cases.

Induction and Recursive Algorithms – Fast Exponentiation Cont. L4−P. 15

no more than 256 multiplications ...

Theorem: If n > 1 has b bits, then F astExp(x, n) performs at most 2b multiplications.

Base: b = 2 then n = 0, n = 1, n = 2, n = 3 if n = 0 then we do not multiply if n = 1 we multiply 3 < 4 times (x · 1^{2}) if n = 2 we multiply 2 < 4 times (y^{2}) if n = 3 we multiply 3 < 4 times (x · x^{2})

Induction and Recursive Algorithms – Greatest Common Divisor L4−P. 16

Step: we assume b and prove for b + 1 We execute recursive call with n/2 or (n − 1)/2 both have b bits, by induction 2b multiplications. Then we do either 1 (even case) or 2 more (odd case) multiplications. Thus overall at most 2b + 2 Given 2 positive natural numbers, a, b ∈ N^{+}, their greatest common divisor (GCD) is the largest number that divides both without remainder.

Euclid’s algorithm

Lemma: Given x > y, let r = x − y. Then any common divisor of x and y is also a common divisor of y and r, and vice versa.

Proof: Suppose d|x and d|y. So x = zd and y = wd. Thus, r = x − y = d(z − w). Suppose d|y and d|r then x = y + r = wd + ud = (w + u)d.

Corollary: GCD(x, y) =GCD(y, r)

Proof: Since (x, y) and (y, r) have exactly the same set of divisors, the biggest number in each set is identical.

So?

Procedure Euclid(x, y)

if x = 0 return y else if y = 0 return x else if x > y return Euclid(y, x − y) else return Euclid(x, y − x))

Example: Find GCD(112, 84) = ? Step 1: 112 − 84 = 28, reduce to (28, 84). Step 2: 84 − 28 = 56, reduce to (28, 56). Step 3: 56 − 28 = 28, reduce to (28, 28). Step 4: 28 − 28 = 0, reduce to 28, 0 Now done, answer is 28.

First prove that the algorithm terminates

Lemma For any natural number inputs x and y, Euclid(x, y) returns a value.

Induction on x + y

if x + y = 0 then we return immediately Assume for x + y < n and prove for x + y = n We either return (when x or y equal 0) or call with smaller x + y.

Lemma For any natural number inputs x and y, Euclid(x, y) returns GCD(x, y).

Induction on x + y

Base: GCD(0,0)=0 (*in fact we need GCD(x,0)=x*) Step: x+y = n > 0, assume without loss of generality x ≥ y. Return the result on Euclid(y, x− y) (strong induction) and lemma complete the proof.

Sets L4−P. 19

A set is a collection of objects.

Order is not important {1, 2} and {2, 1} are the same set.

Element is included once {a, a, b} and {a, b} are the same set.

Examples of sets: {1,2,3} ∅ the empty set. { ∅ } a set with one element, which is a set. {1,{1,2}} an element is included only once {n ∈ N|n is even}, in general domain D and predicate P over D, {x ∈ D|P (x)} the set of all x in D that satisfy P

a ∈ A in words a is an element of A, (∀x)x ∉ ∅.

Subsets L4−P. 20

A ⊆ B (“A is a subset of B” or “A is contained in B”) if every element of A is also an element of B (∀x)(x ∈ A → x ∈ B)). A is a proper subset of B (A ⊂ B) if A ⊆ B and A ≠ B.

Note (∀X)∅ ⊆ X, i.e. the empty set is contained in any other set.

Sets – Definitions L4−P. 21

A = B if and only if A ⊆ B and B ⊆ A.

To prove that the sets {n ∈ N|2 divides n} and {2n|n ∈ N} are equal we show containment in both ways:

⊆: Assume x ∈ N and 2 divides x and show that ∃y ∈ N s.t. x = 2y. ⊇: Assume x = 2y then x is divisible by 2.

The size of a set A — the number of elements in A is |A|. |{a, b, c}| = 3, |∅| = 0, the size of an infinite set is ∞.

|A ∪ B| ≤ |A| + |B| (equal when A ∩ B = ∅) holds for infinite sets when x + ∞ = ∞.

Basic set operations L4−P. 22

Union — A ∪ B = {x|x ∈ A or x ∈ B}. ∪_{i=1}^{n}A_{i} i = 0 results in ∅ Intersection — A∩B = {x|x ∈ A and x ∈ B}. ∩_{i=1}^{n}A_{i} i = 0 results in U the universal set. Difference — A − B = {x|x ∈ A and x ∉ B}. (or A \ B) Complement — A^{c} = {x|x ∉ A}. (or Ā). A^{c} = U − A. Symmetric difference — A⊕B = A∪B−A∩B. Venn diagrams Predicates and sets L4−P. 23

Given predicates p and q, P = {x | p(x)}, Q = {x | q(x)}. Then P ∪ Q = {x | p(x) ∨ q(x)}. P ∩ Q = {x | p(x) ∧ q(x)}. Etc.

Power set (set of all subsets) L4−P. 24

P(A) the set of all subsets of A. In other words, P(A) = {x|x ⊆ A}.

∅ ∈ P(A) and A ∈ P(A).

If A = {1, 2} then P(A) = {∅, {1}, {2}, {1, 2}}.

If A has n elements, then P(A) has 2^{n} elements.

Induction on n Base: n = 0 P(A) = {∅}. Step: let a be the “new” element P(A) contains all subsets without a which are 2^{n−1} subsets for each such subset a subset that includes a. 2^{n−1} · 2. (the number of binary words with n bits).

P(A) can be denoted 2^{A}.

Set identities L4−P. 25

(Distributivity: Union distributes over intersection) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

We show that each is contained in the other

1. A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C).

Suppose x ∈ A ∪ (B ∩ C). Then, x ∈ A or x ∈ (B ∩ C). We argue by cases.

If x ∈ A, then x ∈ A ∪ B and similarly x ∈ A ∪ C. By definition of intersection x is in the intersection of these two sets.

On the other hand, if x ∈ (B ∩ C), then x ∈ B and x ∈ C. By definition of union, x ∈ A ∪ B and x ∈ A ∪ C. It again follows that x is in the intersection.

2. A ∪ (B ∩ C) ⊇ (A ∪ B) ∩ (A ∪ C).

Suppose x ∈ (A ∪ B) ∩ (A ∪ C). It follows that x ∈ A ∪ B and x ∈ A ∪ C. We argue by cases.

If x ∈ A, then certainly x ∈ A ∪ (B ∩ C).

If x ∉ A, then since x ∈ A ∪ B, we know x ∈ B. Similarly, x ∈ C. Therefore, x ∈ B ∩ C. It follows that x ∈ A ∪ (B ∩ C).

Set identities – De Morgan’s rule L4−P. 27

(A ∪ B)^{c} = A^{c} ∩ B^{c}.

We have to show that (A ∪ B)^{c} ⊆ A^{c} ∩ B^{c} and that A^{c} ∩ B^{c} ⊆ (A ∪ B)^{c}.

1. (A ∪ B)^{c} ⊆ A^{c} ∩ B^{c}.

Let x ∈ (A ∪ B)^{c}. By definition of complement, x ∉ A ∪ B. (proof by contradiction) x ∉ A and x ∉ B. By definition of complement, x ∈ A^{c} and x ∈ B^{c}. Then by definition of intersection, x ∈ A^{c} ∩B^{c}.

2. A^{c} ∩ B^{c} ⊆ (A ∪ B)^{c}.

Let x ∈ A^{c} ∩ B^{c}. Then x is in A^{c} and in B^{c}. Therefore, x is in neither A nor B and therefore not in A ∪ B. We conclude that x ∈ (A ∪ B)^{c}.

Dual holds, swapping ∪ with ∩ and ∅ with U.

Cartesian products L4−P. 28

A × B = {(a, b)|a ∈ A and b ∈ B}. (a, b) is an ordered pair ≠ (b, a).

A = {0, 1} and B = {x, y} then {A × B} = {(0, x), (0, y), (1, x), (1, y)}.

Generalize Cartesian products A_{1}×⋯×A_{n} = ∏_{i=1}^{n} A_{i} = {(a_{1}, ⋯, a_{n})|a_{i} ∈ A_{i} for 1 ≤ i ≤ n}. Also, A^{n} is ∏_{i=1}^{n} A.

Examples: {0, 1}^{n} is the set of all n-tuples of 0’s and 1’s. Or, length n strings of 0’s and 1’s.

ℜ^{2} = ℜ × ℜ is the real plane.