Criticising proofs
In a nutshell
You need to be able to follow the logical steps in a proof, and identify where mistakes have been made in the proofs of others.
Implication notation
Given statements A and B, the following arrow symbols can be used to indicate ways in which they relate to each other:
A⟹B | "A implies B" - this means that if A is true, then B is also true. |
A⟸B | "B implies A" - this means that if B is true, then A is also true. |
A⟺B | "A if and only if B" - A and B are logically equivalent, i.e. one is true if and only if the other is true. |
Negating statements
Suppose you have a statement of the form: "for all x, P(x)" where P(x) is some statement dependent on x. The negation of this statement would not be of the form "for all x, ¬P(x)" (where ¬P(x) is the negation of P(x)). This is far stronger than is necessary to negate this; in fact, the negation would be "there exists an x such that ¬P(x)", as either P(x) is true for any x, or there exists an x such that ¬P(x).
Example 1
Identify the error in the following attempt to prove that the sum of all the proper divisors of any positive integer is not equal to the integer itself.
(A proper divisor of a positive integer is another integer which divides it that is not equal to the integer itself.)
The proof proceeds by contradiction; assume the negation of the statement, i.e. that the sum of the proper divisors of any proper integer is equal to the integer itself. Consider any prime number p. Its only proper divisor is 1, but p=1, so this is a contradiction, as you have assumed that the proper divisors of any number add to the number itself.
Therefore, the sum of the proper divisors of any integer is not equal to the integer itself.
The flaw in the proof comes at the point the negation is assumed: the negation of "the sum of all the proper divisors of any positive integer does not equal the integer itself" is "there exists an integer such that the sum of all its proper divisors does equal the integer". This statement cannot be used to derive a contradiction, as it is in fact true, e.g. 6, 28, 496, and many more.
Therefore, the error in the attempted proof is incorrectly negating the statement while trying to derive a contradiction.
Example 2
Identify the error in the following proof that 1=0:
Let x=1.
1⟺1−x2⟺(1−x)(1+x)⟺1+x⟺1=x=x−x2=x(1−x)=x=0
The error comes in dividing by 1−x - this is equal to 0, so you cannot divide by it.
Therefore, the error comes in dividing by zero.