Proof by contradiction

Proof by contradiction in discrete mathematics.
Proof method

1. Proof By Contradiction An indirect proof method By: M. Anas Makki Roll No: 301 Abdul Rehman Roll No: 334 Arslan Roll No:315

2. What is Proof By Contradiction? In mathematics proof by contradiction is a technique that determine the truth value of a proposition/statement by showing that assuming the proposition to be false. A proof by contradiction is based on the fact that either a statement is true or it is false but not both. Hence the supposition, that the statement to be proved is false, leads logically to a contradiction, impossibility or absurdity, then the supposition must be false.

3. Steps involves in Proof By Contradiction: Assume that the statement to be proved be false. In next step we show that our supposition leads to logically contradiction.(Means our supposition is false) In next step we conclude that the our statement is true because our supposition in false.

4. Theorem #1:There is no greatest integer . In first step let us assume that the statement is false. Suppose there is a greatest integer N. Then n ≤ N for every integer n. Let M = N + 1 Now M is an integer since it is a sum of integers. Also M > N since M = N + 1 Thus M is an integer that is greater than the greatest integer, which is a contradiction. Hence our supposition is not true and so there is no greatest integer.

5. EXERCISE: Give a proof by contradiction for the statement: “If n 2 is an even integer then n is an even integer.” Solution : Suppose n 2 is an even integer and n is not even, so that n is odd. Hence n = 2k + 1 for some integer k. Now, taking the square of above equation, we get, n 2 = (2k + 1) 2 = 4k 2 + 4k + 1 taking “2” common, = 2·(2k 2 + 2k) + 1 = 2r + 1 (general form of odd where r = (2k 2 + 2k) ∈Z This shows that n 2 is odd, Which is a contradiction to our supposition that n2 is even. Hence the given statement is true.

6. EXERCISE: Prove that if n is an integer and n 3 + 5 is odd, then n is even using contradiction method. Solution : We assume that the our statement to be proved is false, Suppose that n 3 + 5 is odd and n is not even (odd). Since n is odd and the product of two odd numbers is odd, It means that n 2 is odd and and n 3 = n 2 .n is also odd Further, since the difference of two odd number is even, which is given 5 = (n 3 + 5) – n 3 Which is even. This is a contradiction, therefore our supposition is false, So our statement is true.

7. Exercise: Prove by contradiction method, the statement: If n and m are odd integers, then n + m is an even integer. Solution: In first step we suppose that n and m are odd and n + m is not even (odd i.e by taking contradiction). Now n = 2p + 1(General form of odd) for some integer p m = 2q + 1 for some integer q Adding above two equation we get, n + m = (2p + 1) + (2q + 1) = 2p + 2q + 2 (General Odd’s Form) = 2· (p + q + 1) Taking two common. This is a contradiction to our supposition, because when we multiply 2 with odd, we get even number….. e.g. 2(7)=14

8. Theorem No 2: The sum of any rational number and any irrational number is irrational. Proof: In our first step, we assume that the statement to be proved is false. Such as “We suppose that there is a rational number r and an irrational number s such that r + s is rational.” We know by the definition of rational, we have Also by adding r and s we get the rational number such as r+s =c/d