11. Proof Strategies-II

In this lecture we will continue our discussion on the proof strategies that we started in the previous lecture.

We will start with how to disprove a universally quantified statement. So till now we were seeing various proof methods, where we wanted to prove universally quantified statements. But sometimes we also encounter statements where we want to prove that a universal statement, universally quantified statement, is not true. To disprove that a universally quantified statement is not true, we have to give what we call as a counterexample.

And, by counterexample we mean some element c from the domain such that the statement P is not true for the element c, because if the statement P is not true for the element c. Then the universal quantification for all x, P(x) will turn out to be false. So, very simple example of this is if I make a statement that every positive integer can be expressed as the sum of squares of 2 integers. So this property is my property P and I am making this statement for every x. So, now I have to verify whether the statement P is true for every integer x or not. Even if I can find one integer for which this property is not true, I can say that ꓯ x, P(x) is false here and a very simple counterexample is 3 here, you can check that 3 can never be expressed as a sum of squares of 2 integers.

To disprove a statement that claims something is true for all elements of a certain set, you can show that there is at least one exception. This is done by providing a counterexample, which is a specific instance where the statement fails to hold. In the example given, the statement claims every positive integer can be represented as the sum of two squares. By finding the integer 3, which cannot be expressed as such, we can conclusively say that the original statement is false.

Think of a claim like 'All birds can fly.' If you find just one bird that cannot fly, like a penguin, you have disproven the claim. Similarly, if someone claims that all students in a class passed the test, but you find one who failed, the claim becomes false. This shows how counterexamples work in everyday reasoning.

However, I would like to stress here that there is nothing called proof by example for proving universally quantified statements. If you want to prove that your statement P is true for every element in the domain, then you cannot say that okay, I am showing it for some x, where x is explicitly chosen by you, it is not arbitrary. You are not choosing your x arbitrary, you are just taking your x specifically and that is an example for you.

There is another proof mechanism which is called proof by cases. This is also called exhaustive proof. So if you want to prove an implication of the form p → q, where p and q are propositions, and if your proposition P can be decomposed into conjunction of various other propositions say n propositions, then p → q is logically equivalent to p → q, conjunction 1 p → q and so on.

So if you take the case n equal to 0 the statement is true, namely p → q is true. If you take the case when your arbitrarily chosen n is positive, then also this statement p → q is true and if your arbitrarily chosen n is negative, then you show that in that case also this p → q is true and since these are the three possible cases for your arbitrarily chosen n you can conclude that p → q is true.

Proof by cases involves dividing a problem into several distinct scenarios (or 'cases') and proving that the statement holds true for each scenario. This is particularly useful when you are dealing with statements that can be true under different conditions. For example, if you want to prove a mathematical statement for all integers, you could consider the cases where the integer is positive, negative, or zero. If the statement is confirmed true in each case, it is true for all integers.

Imagine you're planning a party and need to know how many snacks to get depending on whether there are kids, adults, or a mix of both attending. You could make a plan for each case: one plan for ages 0-12, another for ages 13-18, and a third for those 19 and older. If your snack plan works for each scenario, you can be confident it will be effective for the entire party. This is akin to proof by cases in mathematics.

There is also something called without loss of generality, which we very often encounter while writing the proof. In short form they call it as w.l.o.g. So let me demonstrate we have what exactly I mean by without loss of generality. So imagine I want to prove that if x and y are integers and both x, y and x + y are even, then x and y are both even.

Without loss of generality (w.l.o.g.) is used in proofs to simplify arguments by assuming a specific case that doesn’t limit the generality of what you are proving. For example, if you are proving a statement about two integers x and y, you can assume x is less than or equal to y without loss of generality. This means that you can simplify your proof without affecting the overall conclusion.

Imagine you are studying T-shirt sizes in a store—small, medium, and large. If you wanted to prove that everyone should try at least one size, you could just show that the small works. With w.l.o.g., you'd argue that if the small fits, so will the medium and large since they’re only larger. By proving that one size works, you’ve effectively demonstrated the point for all sizes without needing to try on each one.

--