Now we want to generalize a bit, because typically we see statements like this. If n is divisible by 4, then n is divisible by 2. What it actually means is that for all integers n, if n is divisible by 4, then n is divisible by 2. And this statement is actually true, how do we check it? For any number n either it is divisible by 4, and so the if part is true. But then it's also divisible by 2, because It is divisible by 4, if we divided by 4, we get an integer number. But then if we divided by 2, we get twice that integer number, so it is also an integer. So n is divisible by 2 whenever it is divisible by 4. So both the if pats and the then parts are true, and so the statement is true in this case. And the second case is that n is not divisible by 4, then the if part is false. But then, if the if part is false, then the if-then statement is always true. It doesn't matter whether n is divisible by 2 or not. So this general statement, if n is divisible by 4, then n is divisible by 2 is true. Here, we changed if and then part, we switch them and write, if n is divisible by 2, then n is divisible by 4. This statement is false, because for a particular n = 2, it is divisible by 2, but it is not divisible by 4. If we divide 2 by 4, we'll get 0.5, which is not an integer. So the if part is true, but the then part is false, so the if-then statement is false. Actually, we can call the first statement, if n is divisible by 4, then n is divisible by 2, the direct statement. When we switch the if and then parts, we call it the converse statement to the initial direct statement. So if n is divisible by 2, then n is divisible by 4 is a converse statement. And sometimes both direct statement and converse statements are true, this is not true in this case. Because the direct statement is true, but the converse statement is false. But sometimes, both direct statement, if P then Q, and converse statement, if Q then P, are true. And in this case we arrive that they're equivalent like this,P if and only if Q. This means that whenever P is true, Q is also true, whenever Q is true, P is also true, they're equivalent. Now, let's apply negation to the if-then statements. The negation of the phrase, if P then Q, is actually P and not Q. And you check for yourself, that this is true whenever the corresponding if-then statement is false, and vice versa. So just check, that by definition of negation, P and not Q is actually the negation of the phrase, if P then Q. A few more definitions, universal quantification is actually, I think that we've already routinely used for some time. Statements like, all swans are white, all integers ending with digit 2 are even, for all n, 2 times n equals n plus n, are examples of universal quantification. Fermat's last theorem states that for all integer n more than 3, equation a to the power of n plus b to the power of n equals to c to the power of n does not have solutions, with positive integers a, b, and c. Thus, as it starts with the phrase for all n, it is also an example of universal quantification. Another quantification is existential, and we've also used it routinely in the previous lectures, statements like, there are black swans. There is a way to get a change of 12 cents with 4-cents and 5-cents coins. There exist such positive integers, a, b, and c, that a to the fourth plus b to the fourth plus c to the fourth, is equal to d to the fourth. And there is a power of 2 starting with 65, are all examples of existential quantification. Any statements that state that something can be done, something exists, is an example of existential quantification. Now, we can make combinations of quantifiers, and most mathematical statements are usually combinations of universal and existential quantifications, in some combination. Here is a corollary from Fermat's last theorem. There exists such integer m, that for any integer n which is bigger than m, equation a to the n plus b to the n is equal to c to the n has no solutions with positive integers a, b, and c. Why is this a corollary from Fermat's last theorem? Well, because if we take m = 2, and then it follows from Fermat's last theorem..It goes, we just change m to 2 in this statement. And again, there exists an integer 2 such that for any integer n bigger than 2, the equation a to the n plus b to the n equals c to the n has no solutions, and this is exactly Fermat's last theorem. So this is a particular case of Fermat's last theorem. And so, we found that this is a corollary from Fermat's last theorem, because of the existential quantification. We found an example of m for which the existential quantification is true. And the statement itself is a combination of existential quantifier, there exists such an integer, and universal quantifier, for any integer n bigger than m. Now what do we do if we need to negate some quantification? Negation of universal quantification is a corresponding existential quantification, and vice versa. For example, negation of, for all n, statement A is true, the negation of it is there exists such n that statement A is false, and vice versa. Reverse hypothesis is a combination of two universal quantifications. For any n bigger than 3, for any positive integer a, it is impossible to represent a to the power of n as a sum of exactly n- 1 numbers which are also nth powers of positive integers. This negation of Euler's hypothesis is a statement that there exists such n integer bigger than 3, and such positive integer a, that a to the power of n can be represented as a sum of n- 1 numbers, which are nth powers of positive integers. And I'll show you an example which proves this negation, so Euler's hypothesis is actually false. Negation of combinations, things like all positive integers are either even or odd, is, there exists such a positive integer that is not even and not odd. So to negate, we switch universal quantification to existential, and vice versa, and we switch or to and, and vice versa. And examples and the counterexamples, for example, counterexample for Euler's hypothesis that we saw earlier, is an example for the negation of Euler's hypothesis. So examples and counterexamples are also dual as and and or, universal and existential. Examples and counterexamples are dual, by proving negation of Euler's hypothesis. By showing an example to it, we prove that Euler's hypothesis itself is false, and this example is just a counterexample to the initial Euler's hypothesis. And one popular way of proving mathematical statements is called reductio ad absurdum. Basically, proving that the negation of the initial statement is false, and so the statement itself is true. And you will learn this proof principle in the next lecture. In conclusion, in this lesson, we studied examples, counterexamples, and when just one example or counterexample is enough. We started basic logical operations, negation, logical and, logical or, and if-then statements. We also studied universal and existential qualifications, and we learned how to negate different combination of logical operations. And in the next lecture, you will study reductio ad absurdum principle, which is based on these constructions.
