4 5 Proof by contradiction In this method to prove q is true we start by assuming that q is false i e q is true Then by a logical argument we arrive at a situation where a statement is true as well as false i e we reach a contradiction r r for some statement r This means that the truth of q implies a contradiction a staternent that is always false This can only happen when q is false also Therefore q must be true This method is called proof by contradiction It is also called reductio ad absurdum a Latin phrase because it relies on reducing a given assumption to an absurdity Let us consider an example of the use of this method Example 5 Show that 5 is irrational Solution Let us try and prove the given statement by contradiction For this we begin by assuming that 5 is rational This rneans that there exist positive integers a and b such that 5 where a and b have no common a b factors This implies a 5b a 5b 5 a 5 a Therefore by definition a 5c for some c E Z Therefore a 25c But a 5b also So 25c 5b2 5c b 5 b 5 b AD But now we find that 5 divides both a and b which contradicts our e assumption that a and b have no common factor Therefore we conclude that our assumption that 5 is rational is false i e 5 is irrational We can also use the method of contradiction to prove an implication r s Here we can use the equivalence rs rAs So to prove r s we can begin by assuming that r s is false i e r is true and s is false Then we can present a valid argument to arrive at a contradiction Consider the following example from plane geometry Example 6 Prove the following If two distinct lines L and La intersect then their intersection consists of exactly one point Solution To prove the given implication by contradiction let us begin by assuming that the two distinct lines L and L2 intersect in more than one point Let us call two of these distinct points A and B Then both L and L2 contain A and B This contradicts the axiom from geomctry that says Given two distinct points there is exactly one line containing them Therefore if L and L2 intersect then they must intersect in only one point The contradiction rule is also used for solving many logical puzzles by discarding all solutions that reduce to contradictions Consider the following example those Example 7 There is a village that consists of two types of people who always tell the truth and those who always li Suppose that you visit the village and two villagers A and B come up to you Further suppose A says B always tells the truth and B says A and I are of opposite types What types are A and B 8