CS 207 Discrete Mathematics – 2013-2014

(1)

CS 207 Discrete Mathematics – 2013-2014

Nutan Limaye

Indian Institute of Technology, Bombay nutan@cse.iitb.ac.in

Mathematical Reasoning and Mathematical Objects Lecture 1: What is a proof?

July 18, 2013

Nutan (IITB) CS 207 Discrete Mathematics – 2013-2014 May 2011 1 / 18

(2)

Credit Structure

Course credit structure

quizzes 25%

mid-sem 35%

end-sem 40%

Office hours: 11:00am to 1:00pm (Wednesday) Problem solving session: 1 hour per week (To be announced)

(3)

Important Announcements

Quiz 1: August 28, 2013 , Wednesday, 8:30am to 9:30am Quiz 2: September 4, 2013 , Wednesday, 8:30am to 9:30am

No classes on: July 22, 2013, July 23, 2013 and July 25, 2013 Next class: July 29, 2013

(4)

Important Announcements

Quiz 1: August 28, 2013 , Wednesday, 8:30am to 9:30am Quiz 2: September 4, 2013 , Wednesday, 8:30am to 9:30am No classes on: July 22, 2013, July 23, 2013 and July 25, 2013

Next class: July 29, 2013

(5)

Important Announcements

Quiz 1: August 28, 2013 , Wednesday, 8:30am to 9:30am Quiz 2: September 4, 2013 , Wednesday, 8:30am to 9:30am No classes on: July 22, 2013, July 23, 2013 and July 25, 2013 Next class: July 29, 2013

(6)

Course Outline

Mathematical reasoning and mathematical objects Combinatorics

Elements of graph theory Elements of abstract algebra

(7)

Course Outline

Mathematical reasoning and mathematical objects

I What is a proof? Types of proof methods

I Induction

I Sets, relations, functions, partial orders, graphs Combinatorics

(8)

Course Outline

Mathematical reasoning and mathematical objects

I What is a proof? Types of proof methods

I Induction

I Sets, relations, functions, partial orders, graphs

Text: Discrete Mathematics and its applictions, by Kenneth Rosen Chapter 2 : 2.1,2.2,2.3, Chapter 8 : 8.1,8.5,8.6

Class notes: will be uploaded on Moodle Combinatorics

(9)

What is a proposition?

A statement that is either true or false.

2 + 2 = 4, every odd number is a prime, there are no even primes other than 2;

8a,b2N,9c 2N:a²+b²=c; 8a,b2N,9c 2N:a² b²=c; 8a,b2N,9c 2Z:a² b² =c;

It is not always easy to tell whether a proposition is true or false.

(10)

What is a proposition?

8a,b2N,9c 2N:a²+b²=c; 8a,b2N,9c 2N:a² b²=c; 8a,b2N,9c 2Z:a² b² =c;

(11)

What is a proposition?

8a,b 2N,9c 2N:a²+b²=c;

8a,b2N,9c 2N:a² b²=c; 8a,b2N,9c 2Z:a² b² =c;

(12)

What is a proposition?

8a,b 2N,9c 2N:a²+b²=c;

8: for all, 9: there exists,

2, /2: contained in, and not contained in

N: the set of natural numbers, Z: the set of integers,

Q: the set of rationals,

Z⁺: the set of positive integers, R: the set of reals

(13)

What is a proposition?

8a,b 2N,9c 2N:a²+b²=c;

8: for all, 9: there exists,

2, /2: contained in, and not contained in N: the set of natural numbers,

Z: the set of integers, Q: the set of rationals,

Z⁺: the set of positive integers, R: the set of reals

(14)

What is a proposition?

8a,b 2N,9c 2N:a²+b²=c;

8a,b 2N,9c 2N:a² b²=c;

8a,b2N,9c 2Z:a² b² =c;

(15)

What is a proposition?

8a,b 2N,9c 2N:a²+b²=c;

8a,b 2N,9c 2N:a² b²=c;

8a,b 2N,9c 2Z:a² b² =c;

(16)

Theorems and proofs

Theorem

If0x 2,then x³+ 4x+ 1>0

*(scratchpad)* Proof.

As x³+ 4x=x(4 x²), which is in factx(2 x)(2 +x), the quantity is positive non-negative for 0x 2. Adding 1 to a non-negative quantity makes it positive. Therefore, the above theorem.

(17)

Theorems and proofs

Theorem

If0x 2,then x³+ 4x+ 1>0

*(scratchpad)*

Proof.

(18)

Theorems and proofs

Theorem

If0x 2,then x³+ 4x+ 1>0

*(scratchpad)*

Proof.

(19)

Theorems and Proofs

Given: a number n2N Check: Is n prime?

for i = 2 top n do if i|n then

output “no” end if

end for

Why is this algorithm correct? Theorem

If n is a composite integer, then n has a prime divisor less than or equal to pn

Proof.

As n is a composite, 9x,y2N,x,y <n :n=xy. If x >p

n andy >p n then xy >n. Therefore, one of x ory is less than or equal top

n. Sayx is smaller than p

n. It is either a composite or a prime. If it is a prime, then we are done. Else, it has prime factorization (axiom: unique factorization in N) and again, we are done.

(20)

Theorems and Proofs

output “no”

end if end for

Why is this algorithm correct? Theorem

Proof.

(21)

Theorems and Proofs

output “no”

end if end for

Why is this algorithm correct?

Is there a number n2Ns.t 8i :i 2{2,3, . . . ,p

n}i -n, but 9j >p

n s.t. j|n?

Is there a composite n 2Ns.t. all its prime factors are greater than p n?

Theorem

Proof.

(22)

Theorems and Proofs

n}i -n, but 9j >p

n s.t. j|n?

Theorem

Proof.

As n is a composite, 9x,y 2N,x,y <n :n=xy. If x>p

n andy >p n then xy >n. Therefore, one ofx ory is less than or equal top

(23)

Theorems and Proofs

n}i -n, but 9j >p

n s.t. j|n?

Theorem

Proof.

As n is a composite, 9x,y 2N,x,y <n :n=xy. If x>p

n andy >p n then xy >n. Therefore, one ofx ory is less than or equal top

(24)

Axioms

Euclid in 300BC invented the method of axioms-and-proofs.

Using only a handful of axioms called Zermelo-Fraenkel and Choice (ZFC) and a few rules of deductions the entire mathematics can be deduced!

Proving theorems starting from ZFC alone is tedious. 20,000+ lines proof for 2 + 2 = 4

We will assume a whole lot of axioms to prove theorems: all familiar facts from high school math.

(25)

Class problems

(CW1.1)Prove that for anyn 2N,n(n² 1)(n+ 2) is divisible by 4.

(what about divisible by 8?)

(CW1.2)Prove that for anyn 2N, 2ⁿ<(n+ 2)!

(26)

Bogus proofs

Theorem (Bogus) 1/8>1/4

Proof.

3>2

3 log₁₀(1/2)>2 log₁₀(1/2) log₁₀(1/2)³ >log₁₀(1/2)²

(1/2)³ >(1/2)²

(27)

Another bogus proof

Theorem

For all non-negative numbers a,b ^a+b₂ p ab

Proof.

a+b 2

?p ab a+b ^?2p

ab a²+ 2ab+b² ^?4ab a² 2ab+b² ^?0

(a b)² 0

(28)

Proof Methods

(29)

Proof by contrapositive

Theorem

If r is irrational then p

r is also irrational.

Proof. Supposep

r is rational. Then p

r =p/q forp,q2Z. Therefore, r =p²/q².

(30)

Proof by contrapositive

Theorem

Definition (Contrapozitive)

The contrapositive of “if P thenQ” is “if¬Q then ¬P”

Proof. Supposep

(31)

Proof by contrapositive

Theorem

Ifp

r is rational then r is rational.

Proof.

Supposep

(32)

Proof by contradiction

Theorem p2 is irrational.

Proof.

Suppose not. Then there exists p,q2Zsuch that p

2 =p/q,wherep,q do not have any common divisors. Therefore, 2q² =p², i.e. p² is even. Ifp² is even, then p is even. Therefore, p = 2k for somek 2Z ) 2q²= 4k² ) q²= 2k² ) q² is even. Therefore, q is even. That is,p,q have a common factor. This leads to a contradiction.

(CW2.2)Prove that there are infinitely many primes.

(33)

Proof by contradiction

Proof.

2 =p/q,wherep,q do not have any common divisors. Therefore, 2q² =p², i.e. p² is even.

Ifp² is even, then p is even. Therefore, p = 2k for somek 2Z ) 2q²= 4k² ) q²= 2k² ) q² is even. Therefore, q is even. That is,p,q have a common factor. This leads to a contradiction.

(34)

Proof by contradiction

Proof.

(CW2.1)Ifp² is even, then p is even.

Therefore,p = 2k for somek 2Z ) 2q²= 4k² )q²= 2k² )q² is even. Therefore,q is even. That is, p,q have a common factor. This leads to a contradiction.

(35)

Proof by contradiction

Proof.

Ifp² is even, then p is even. (why?)

Suppose not, i..e p² is even but p is not. Then p= 2k+ 1 for some integerk. p²= (2k+ 1)² = 4k²+ 4k+ 1. As 4(k²+k) is even, 4k²+ 4k+ 1 is odd, which is a contradiction.

Therefore, p= 2k for somek2Z) 2q² = 4k² ) q² = 2k² ) q² is even. Therefore, q is even. That is, p,q have a common factor. This leads to a contradiction.

(36)

Proof by contradiction

Proof.

Ifp² is even, then p is even.

Therefore,p = 2k for somek 2Z ) 2q²= 4k² ) q²= 2k² ) q² is even. Therefore, q is even. That is,p,q have a common factor. This leads to a contradiction.

(37)

Proof by contradiction

Proof.

Ifp² is even, then p is even. Therefore, p = 2k for somek 2Z) 2q²= 4k² ) q²= 2k² )q² is even. Therefore,q is even. That is,p,q have a common factor. This leads to a contradiction.

(38)

Proof by contradiction

Proof.

Ifp² is even, then p is even. Therefore, p = 2k for somek 2Z) 2q²= 4k² ) q²= 2k² )q² is even. Therefore,q is even. That is,p,q have a common factor. This leads to a contradiction.

(39)

Well-ordering principle and Induction

Axiom (WOP)

Every nonempty set of non-negative integers has a smallest element.

Axiom (Induction)

Let P(n) be a property of non-negative integers. If

1 P(0)is true (Base case)

2 for all n 0, P(n))P(n+ 1)(Induction step) then P(n) is true for for all n2N.

Axiom (Strong Induction)

2 [8k 2{0,1, . . . ,n}:P(k)])P(n+ 1)(Induction step) then P(n) is true for for all n2N.

(40)

Well-ordering principle and Induction

Axiom (WOP)

Axiom (Induction)

(41)

Well-ordering principle and Induction

Axiom (WOP)

Axiom (Induction)

(42)

WOP ) Induction

Theorem

Well-ordering principle implies Induction Proof.

Let P(0) be true and for eachn 0, let P(n))P(n+ 1).

Let us assume for the sake of contradiction that P(n) is not true for all positive integers.

Let C ={i |P(i) is false}. AsC is non-empty and non-negative integers C has a smallest element (due to WOP), say i0.

Now, i06= 0. AlsoP(i0 1) is true, asi0 1 is not inC. But P(i0 1))P(i0), which is a contradiction.

Theorem

WOP , Induction, Strong Induction [HW]

(43)

WOP ) Induction

Theorem

Well-ordering principle implies Induction Proof.

Let P(0) be true and for eachn 0, let P(n))P(n+ 1).

Let us assume for the sake of contradiction that P(n) is not true for all positive integers.

Let C ={i |P(i) is false}. AsC is non-empty and non-negative integers C has a smallest element (due to WOP), say i0.

Now, i06= 0. AlsoP(i0 1) is true, asi0 1 is not inC. But P(i0 1))P(i0), which is a contradiction.

Theorem

WOP , Induction, Strong Induction [HW]

(44)

Using Induction to prove theorems

Theorem 2ⁿ(n+ 1)!

Proof.

Base case (n= 0): 2⁰= 1 = 1!

Induction hypothesis: 2ⁿ(n+ 1)!. 2ⁿ⁺¹= 2·2ⁿ

2·(n+ 1)! (by indiction hypothesis)

(n+ 2)·(n+ 1)!

(n+ 2)!

(45)

Using Induction to prove theorems

Theorem 2ⁿ(n+ 1)!

Proof.

Base case (n= 0): 2⁰= 1 = 1!

Induction hypothesis: 2ⁿ(n+ 1)!.

2ⁿ⁺¹= 2·2ⁿ

2·(n+ 1)! (by indiction hypothesis)

(n+ 2)·(n+ 1)!

(n+ 2)!

(46)

Using Well-ordering principle to prove theorems

Here is a slightly non-trivial example:

Theorem

The following equation does not have any solutions over N: 4a³+ 2b³=c³

It is not always as easy to prove such theorems. Conjecture (Euler, 1769)

There are no positive integer solutions over Zto the equation: a⁴+b⁴+c⁴ =d⁴

Integer values for a,b,c,d that do satisfy this equation were first discovered in 1986.

It took more two hundred years to prove it.

(47)

Using Well-ordering principle to prove theorems

Theorem

Proof.

Suppose (for the sake of contradiction) this has a solution over N. Let (A,B,C) be the solution with the smallest value of b in S.

Observe that C³ is even. Therefore,C is even. Say C = 2 . Therefore, 4A³+ 2B³ = 8 ³,i.e. 2A³+B³ = 4 ³.

Now, B³ is even and so isB. Say B = 2 . )2A³+ 8 ³ = 4 ³. And, now we can repeat the argument with respect to A. Therefore, if (A,B,C) is a solution then so is (↵, , ). But <B, which is a contradiction.

(48)

Using Well-ordering principle to prove theorems

Theorem

Proof.

(Such an s exists due to WOP.)

Observe that C³ is even. Therefore,C is even. Say C = 2 .

Therefore, 4A³+ 2B³ = 8 ³,i.e. 2A³+B³ = 4 ³.

(49)

Using Well-ordering principle to prove theorems

Theorem

Proof.

(50)

Using Well-ordering principle to prove theorems

Theorem

Proof.

Now, B³ is even and so isB. Say B= 2 . )2A³+ 8 ³= 4 ³.

And, now we can repeat the argument with respect to A. Therefore, if (A,B,C) is a solution then so is (↵, , ). But <B, which is a contradiction.

(51)

Using Well-ordering principle to prove theorems

Theorem

Proof.

Now, B³ is even and so isB. Say B= 2 . )2A³+ 8 ³= 4 ³. And, now we can repeat the argument with respect to A.

Therefore, if (A,B,C) is a solution then so is (↵, , ).

But <B, which is a contradiction.

(52)

Using Well-ordering principle to prove theorems

Theorem

Proof.

(53)

Using Well-ordering principle to prove theorems

Theorem

It is not always as easy to prove such theorems.

Conjecture (Euler, 1769)

There are no positive integer solutions over Zto the equation:

a⁴+b⁴+c⁴ =d⁴

(54)

CS 207 Discrete Mathematics – 2012-2013

Nutan Limaye

Mathematical Reasoning and Mathematical Objects Lecture 2: Well-ordering principle and Induction

July 29, 2013

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 July 2012 1 / 8

(55)

CS 207 Discrete Mathematics – 2012-2013

Nutan Limaye

Mathematical Reasoning and Mathematical Objects Lecture 2: Well-ordering principle and Induction

July 29, 2013

(56)

Last time

(57)

Recap

What are axioms, propositions, theorems, claims and proofs?

Various theorems we proved in class:

The well ordering principle, induction, and strong induction. You were asked to think about the following problem:

Is 2ⁿ< ⁿ₂!?

Try to also think about the following: (CW2.1)

For every positive integer n there exists another positive integerk such that n is of the form 9k,9k+ 1,or 9k 1.

(58)

Recap

I Ifnis a composite integer, thennhas a prime divisor less than or equal topn.

I Ifr is irrational thenpr is irrational.

I p

2 is irrational.

I Well-ordering principle implies induction.

I 2ⁿ<n!

Is 2ⁿ< ⁿ₂!?

(59)

Recap

I p

2 is irrational.

I 2ⁿ<n!

Is 2ⁿ< ⁿ₂!?

(60)

Recap

I p

2 is irrational.

I 2ⁿ<n!

Is 2ⁿ< ⁿ₂!?

(61)

Recap

I p

2 is irrational.

I 2ⁿ<n!

Is 2ⁿ< ⁿ₂!?

(62)

Recap

I p

2 is irrational.

I 2ⁿ<n!

Is 2ⁿ< ⁿ₂!?

(63)

Recap

I p

2 is irrational.

I 2ⁿ<n!

The well ordering principle, induction, and strong induction.

You were asked to think about the following problem: Is 2ⁿ< ⁿ₂!?

(64)

Recap

You were asked to think about the following problem:

Is 2ⁿ< ⁿ₂!?

(65)

Recap

You were asked to think about the following problem:

Is 2ⁿ< ⁿ₂!?

(66)

Using Well-ordering principle to prove theorems

Theorem

(67)

Using Well-ordering principle to prove theorems

Theorem

Proof.

Suppose (for the sake of contradiction) this has a solution over N. Let s = (A,B,C) be the solution with the smallest value ofb in S.

(68)

Using Well-ordering principle to prove theorems

Theorem

Proof.

Suppose (for the sake of contradiction) this has a solution over N. Let s = (A,B,C) be the solution with the smallest value ofb in S. (Such an s exists due to WOP.)

Observe that C³ is even. Therefore,C is even. Say C = 2 .

Therefore, 4A³+ 2B³ = 8 ³,i.e. 2A³+B³ = 4 ³.

(69)

Using Well-ordering principle to prove theorems

Theorem

Proof.

Suppose (for the sake of contradiction) this has a solution over N. Let s = (A,B,C) be the solution with the smallest value ofb in S. Observe that C³ is even. Therefore,C is even. Say C = 2 . Therefore, 4A³+ 2B³ = 8 ³,i.e. 2A³+B³ = 4 ³.

(70)

Using Well-ordering principle to prove theorems

Theorem

Proof.

Now, B³ is even and so isB. Say B= 2 . )2A³+ 8 ³= 4 ³.

And, now we can repeat the argument with respect to A. Therefore, if (A,B,C) is a solution then so is (↵, , ). But <B, which is a contradiction.

(71)

Using Well-ordering principle to prove theorems

Theorem

Proof.

(72)

Using Well-ordering principle to prove theorems

Theorem

Proof.

(73)

Using Well-ordering principle to prove theorems

Theorem

It is not always as easy to prove such theorems.

Conjecture (Euler, 1769)

There are no positive integer solutions over Zto the equation:

a⁴+b⁴+c⁴ =d⁴

(74)

A proof by induction

Theorem

For any n 2N,n 2prove that s

2 r

3 q

4. . .p

n 1p

n <3

Proof.

For all 2i j,i,j 2N letf(i,j) = q

ip

i+ 1. . .p j. We prove (⇤) by induction onj i.

Base case: j i = 1. f(i,i+ 1) =p ip

i+ 1<i + 1. Induction:

f(i,j + 1) =p

i·f(i+ 1,j+ 1)

<p

i·(i+ 2) (by Induction Hypothesis)

i+ 1 (by AM-GM inequality)

(75)

A proof by induction

Theorem

2 r

3 q

4. . .p

n 1p

n <3

*scratch pad*

a slightly stronger induction hypothesis is required Proof.

ip

f(i,j + 1) =p

i·f(i+ 1,j+ 1)

<p

(76)

A proof by induction

Theorem

2 r

3 q

4. . .p

n 1p

n <3

*scratch pad*

a slightly stronger induction hypothesis is required

Proof.

ip

i+ 1. . .p j. We will prove a slightly more general statement:

For all 2i j,i,j 2N,f(i,j)<i+ 1 We prove (⇤) by induction onj i. Base case: j i = 1. f(i,i+ 1) =p

ip

f(i,j + 1) =p

i·f(i+ 1,j+ 1)

<p

(77)

A proof by induction

Theorem

2 r

3 q

4. . .p

n 1p

n <3

Proof.

For all 2i j,i,j 2Nlet f(i,j) = q

ip

i+ 1. . .p j. We will prove a slightly more general statement:

For all 2i j,i,j 2N,f(i,j)<i+ 1

This is more general than the theorem statement we wanted to prove.

We prove (⇤) by induction onj i.

f(i,j + 1) =p

i·f(i+ 1,j+ 1)

<p

(78)

A proof by induction

Theorem

2 r

3 q

4. . .p

n 1p

n <3 ( 82i <j,i,j 2N,f(i,j)<i+ 1 (⇤)

Proof.

ip

i+ 1. . .p j.

We prove (⇤) by induction onj i. Base case: j i = 1. f(i,i+ 1) =p

ip

f(i,j + 1) =p

i·f(i+ 1,j+ 1)

<p

(79)

A proof by induction

Theorem

2 r

3 q

4. . .p

n 1p

n <3 ( 82i <j,i,j 2N,f(i,j)<i+ 1 (⇤)

Proof.

ip

f(i,j + 1) =p

i·f(i+ 1,j+ 1)

<p

(80)

A proof by induction

Theorem

2 r

3 q

4. . .p

n 1p

n <3 ( 82i <j,i,j 2N,f(i,j)<i+ 1 (⇤)

Proof.

ip

i+ 1<i + 1.

Induction:

f(i,j + 1) =p

i·f(i+ 1,j+ 1)

<p

(81)

A proof by induction

Theorem

2 r

3 q

4. . .p

n 1p

n <3 ( 82i <j,i,j 2N,f(i,j)<i+ 1 (⇤)

Proof.

ip

i+ 1<i + 1.

Induction:

f(i,j + 1) =p

i·f(i+ 1,j+ 1)

<p

(82)

A Bogus Inductive proof

Theorem (Bogus, CW2.2)

a2R, a>0. Then,8n 2N, aⁿ= 1.

By Strong Induction. Base case: n= 0. Soaⁿ= 1. Induction: n!n+ 1.

aⁿ⁺¹ = aⁿ·aⁿ

aⁿ ¹ = 1·1 1 = 1

???

(83)

A Bogus Inductive proof

a2R, a>0. Then,8n 2N, aⁿ= 1.

By Strong Induction.

Base case: n= 0. Soaⁿ= 1.

Induction: n!n+ 1.

aⁿ ¹ = 1·1 1 = 1

???

(84)

A Bogus Inductive proof

a2R, a>0. Then,8n 2N, aⁿ= 1.

By Strong Induction.

Base case: n= 0. Soaⁿ= 1.

Induction: n!n+ 1.

aⁿ ¹ = 1·1 1 = 1