In general, proofwriting is skimmed at best in high schools. Yet it's something you're going to encounter sooner or later -- if not in high school, then in college. This will be a basic lesson on proofwriting and three methods of argument: deduction, proof by contradiction, and induction.
Deduction has a broader scope than induction and proof by contradiction. Most proofs have a deductive anatomy but the more surgical parts can be inductive or done by contradiction. Here are succinct explanations of the three techniques, with examples given:
DeductionDeduction is a straightforward method of argument. It takes the form
"if A then B", or A=>B. Some arguments can work both ways,
A<=>B, and thus are
logically equivalent.
Example ProblemDerive the sum of squares by deduction.
We will use difference analysis and deduction to derive the sum of squares formula. Let S(n) be the sum of squares function.
We know that S(n) is a polynomial of some unknown order because if we keep differentiating it we will sooner or later get a constant (for those who don't know calculus, basically the slope of function of the slope of the function of the slope... will be constant).
Let's first do some difference analysis.
n | S(n)
1 | 1
> 4
2 | 5 > 5
> 9 > 2
3 | 14 > 7 > 0
> 16 > 2
4 | 30 > 9
> 25
5 | 55
We see that the fourth derivative results in 0. Thus S(n) is a 3rd order polynomial.
(http://latex.sidoh.org/?render=%5C%5CS%28n%29%20%3D%20an%5E%7B3%7D%20%2B%20bn%5E%7B2%7D%20%2B%20cn%20%2B%20d%0D%0A%5C%5C%0D%0A%5C%5CWhen%5C%20x%20%3D%200%2C%20S%28n%29%20%3D%20d.%5C%20Since%5C%20S%28n%29%5C%20is%5C%20clearly%5C%200%2C%5C%20d%20%3D%200.%0D%0A%5C%5C%0D%0A%5C%5CSince%5C%20the%5C%20third%5C%20derivative%5C%20is%5C%20S%27%27%27%28n%29%20%3D%202%2C%0D%0A%5C%5Cwe%5C%20can%5C%20solve%5C%20for%5C%20a%5C%20in%5C%20%5Cfrac%7Bd%5E%7B3%7DS%7D%7Bdn%5E%7B3%7D%7D%20%3D%202.%0D%0A%5C%5C%0D%0A%5C%5CWe%5C%20get%5C%206a%20%3D%202%5C%20and%5C%20thus%5C%20a%20%3D%20%5Cfrac%7B1%7D%7B3%7D.%0D%0A%5C%5C%0D%0A%5C%5CBy%5C%20using%5C%20a%5C%20system%5C%20of%5C%20equations%2C%20we%5C%20can%5C%20discern%5C%20that%5C%20b%20%3D%20%5Cfrac%7B1%7D%7B2%7D%20%5C%20and%5C%20c%20%3D%20%5Cfrac%7B1%7D%7B6%7D%0D%0A%5C%5C%0D%0A%5C%5CFactoring%5C%20out%5C%20the%5C%20%5Cfrac%7B1%7D%7B6%7D%5C%20gives%5C%20us%5C%20S%28n%29%20%3D%20%5Cfrac%7B1%7D%7B6%7Dn%28n%20%2B%201%29%282n%20%2B%201%29.%20)
Excercises:(1) The
contrapositive is derived by negating and permuting the terms of another proposition. If the proposition is true then the contrapositive is true.
What is the contrapositive of the proposition: "if you live in Massachusetts then you live in the USA?"
(2) The converse of a proposition is when the effect implies the cause. The converse of A=>B is B=>A.
What is the converse of the proposition: "if you are an alien then you are not human"? Is the converse true? Is the proposition logically equivalent, A<=>B.
(3) Derive the sum of cubes by deduction.
Proof by ContradictionBasically to argue something by contradiction you assume it is false and then show that it leads to some absurd conclusion. It is often the easiest route to proving something cannot happen, because if something is true then it has to be true in all cases.
Example Problem:Infinite Number of Primes Problem (http://www.x86labs.org:81/forum/index.php/topic,7670.15.html)
Example Problem:(http://latex.sidoh.org/?render=%5C%5CProve%5C%20that%5C%20%5Csqrt%7B2%7D%5C%20is%5C%20irrational.%0D%0A%5C%5C%0D%0A%5C%5CAssume%5C%20%5Csqrt%7B2%7D%5C%20is%5C%20rational.%5C%20Then%5C%20there%5C%20%5C%5Cexists%5C%20integers%5C%20a%2C%5C%20b%5C%20in%5C%20lowest%5C%20terms%5C%20such%5C%20%5C%5Cthat%5C%20%5Cfrac%7Ba%7D%7Bb%7D%20%3D%20%5Csqrt%7B2%7D.%0D%0A%5C%5C%0D%0A%5C%5Ca%5C%20and%5C%20b%5C%20cannot%5C%20both%5C%20be%5C%20even%2C%5C%20or%5C%20else%5C%20it%5C%20would%5C%20be%5C%20reducible%0D%0A%5C%5C%0D%0A%5C%5CWe%5C%20know%5C%20that%5C%20a%5E%7B2%7D%20%3D%202b%5E%7B2%7D.%5C%20Since%5C%20a%5C%20must%5C%20be%5C%20even%5C%2C%0D%0A%5C%5Cwe%5C%20can%5C%20conclude%5C%20a%20%3D%202t.%0D%0A%5C%5C%0D%0A%5C%5Cb%5E%7B2%7D%20%3D%20%5Cfrac%7B1%7D%7B2%7D%282t%29%5E%7B2%7D%20%3D%202t%5E%7B2%7D%0D%0A%5C%5C%0D%0A%5C%5Ctherefore%5C%20b%5C%20must%5C%20also%5C%20be%5C%20even.%0D%0A%5C%5C%0D%0A%5C%5CContradiction%21%5C%20%5Csqrt%7B2%7D%5C%20cannot%5C%20be%5C%20rational.%0D%0A%0D%0A)
Excercises:(1) Prove that sqrt(3) is irrational.
(2) Prove that sqrt(6) is irrational.
InductionI think that many high schools teach induction wrong. It is much easier to think of it as proving the if-then and then finding some anchor chase to create the domino effect. The key phrase in that is
proving the if-then. You assume the
if and then prove the
then based on that assumption. The
if is often "assume the argument is true for some n" and the
then is often "is the argument true for n + 1". When you show that it is true for some anchor case, n = c, then you can say it is true for n + 1, n + 2, n + 3..., and they topple like dominoes. Be aware that when n = c is an integer, this will only prove it true for the integers that are greater than or equal to c.
Example Problem:(http://latex.sidoh.org/?render=%5C%5CProve%5C%20the%5C%20sum%5C%20of%5C%20squares%5C%20formula%5C%20by%5C%20induction.%0D%0A%5C%5C%0D%0A%5C%5CHypothesis%3A%20%0D%0A%5C%5CS%28n%29%20%3D%20%5Cfrac%7B1%7D%7B6%7Dn%28n%20%2B%201%29%282n%20%2B%201%29%0D%0A%5C%5C%0D%0A%5C%5CTHE%20%22ANCHOR%22%3A%0D%0A%5C%5CS%281%29%20%3D%20%5Cfrac%7B1%7D%7B6%7D1%281%20%2B%201%29%282%5Ctimes1%20%2B%201%29%0D%0A%5C%5C%3D%201%0D%0A%5C%5Cwhich%5C%20is%5C%20what%5C%20we%5C%20wanted.%0D%0A%5C%5C%0D%0A%5C%5CTHE%5C%20%22IF%22%3A%20%0D%0A%5C%5CAssume%5C%20S%28n%29%20is%20true%20for%20some%20n.%0D%0A%5C%5C%0D%0A%5C%5CTHE%5C%20%22THEN%22%3A%20%0D%0A%5C%5CS%28n%2B1%29%20%3D%20%5Cfrac%7B1%7D%7B6%7D%28n%20%2B%201%29%28n%20%2B%202%29%282n%20%2B%204%29.%0D%0A%5C%5CMultiplying%5C%20this%5C%20out%2C%20we%5C%20get%5C%20%5Cfrac%7B1%7D%7B6%7D%282n%5E%7B3%7D%20%2B%20n%5E%7B2%7D%20%2B%203n%29%20%2B%20%5Cfrac%7B1%7D%7B6%7D%286n%5E%7B2%7D%20%2B%2012n%20%2B%206%29%0D%0A%5C%5C%20%3D%20S%28n%29%20%2B%20%28n%20%2B%201%29%5E%7B2%7D%0D%0A%5C%5CQED)
Excercises:(1) Derive the sum of cubes by induction.
Now that you know these three methods of argument, you may ask "where do I start?"
There are many lines of thought you can wander through in a proof. Like chess, there are many moves you can do, and so you must have a direction -- you must be able to narrow down a set of moves that are plausible. This doesn't mean you should sacrifice creativity; plausibility is not so much judged by numbers as it is judged by the thought process -- is it logically sound?
One strategy is to think of which method of argument is best suited to the proof and then tackle it with that. Oftentimes, you should get your hands dirty. In your first investigation you should not shoot for a formal proof – prod for patterns, make tables of values, try it for a specific case before generalizing it, etc.
Another strategy is to work with the
penultimate step. This is imagining the step which satisfies "if P then the proof is done". For instance, let's assume that all users on x86labs have visited the math board =P. To prove that someone has visited the x86 math board, the penultimate step could be "if someone is a member of x86labs.org then he or she has been to the x86 math board." Then you have to show that that person is a member of x86labs.org. You can even do this recursively and go "backwards" through a proof.
Problems:(1) First show, and then prove, that a set with n elements has 2^{n}
subsets, including the empty set and the set itself.
(2) Prove Bernoulli's Inequality, which states that if x > -1, x !=0, and n is a positive integer greater than 1, then: (1 + x)^n >= 1 + nx
(3) What is wrong with the proof that linked here (http://latex.sidoh.org/?render=%5C%5CProve%5C%20that%5C%20%5Csqrt%7B3%7D%5C%20is%5C%20irrational.%0D%0A%5C%5C%0D%0A%5C%5CAssume%5C%20%5Csqrt%7B3%7D%5C%20is%5C%20rational.%5C%20Then%5C%20there%5C%20exists%5C%20a%2C%5C%20b%5C%20such%5C%20that%5C%20%5Cfrac%7Ba%7D%7Bb%7D%20%3D%20%5Csqrt%7B3%7D.%0D%0A%5C%5C%0D%0A%5C%5Ca%5C%20and%5C%20b%5C%20must%5C%20be%5C%20opposite%5C%20in%5C%20parity%2C%20%5C%5Cfor%5C%20if%5C%20they%5C%20were%5C%20not%5C%20then%5C%20they%5C%20would%5C%20be%5C%20reducible.%0D%0A%5C%5C%0D%0A%5C%5CConsider%5C%20a%5E%7B2%7D%3D3b%5E%7B2%7D.%5C%20If%5C%20a%5C%20were%5C%20even%2C%20%0D%0A%5C%5Cb%5C%20must%5C%20be%5C%20even%2C%5C%20and%5C%20vice%5C%20versa.%5C%20Herein%5C%20lies%5C%20the%5C%20contradiction%3A%5C%20a%5C%20and%5C%20b%5C%20%0D%0A%5C%5Cmust%5C%20be%5C%20opposite%5C%20in%5C%20parity.%0D%0A%5C%5C%0D%0A%5C%5CTherefore%5C%20%5Csqrt%7B3%7D%5C%20is%5C%20irrational.).
(4) Prove the formula for the sum of a geometric series.
(5) Prove the Fibonacci sequence formula.
(6) Prove that log 2 is irrational.
(7) Prove that the product of any three consecutive numbers is divisible by 6.
(8) Prove that sqrt(2) + sqrt(3) is irrational.
(9) Determine a way to order the complex numbers. (For any two complex numbers you should be able to determine whether they are equal or not and if not then which is smaller.)
2. I don't see how the first formula is true. Assume an x of 0: 0 > -1; 0 == 0. Edited, thanks.
5. What's there to prove? I assumed you guys would look it up =p (The formula, not the proof.)
I just glanced at it, but it seems that you forgot the "if and only if" biconditional.
I don't believe so.
Consider this proposition:
"If and only if you live in Boston then you live in Massachusetts."
It is incorrect, and not the same as:
"If you live in Boston, then you live in Massachusetts."
To prove that someone lives in Massachusetts, there are many ways to do so. Proving that they live in Boston isn't the only way. But it's one way.
Obviously, that proposition isn't biconditional.
A better example:
If and only if you have an iPod, then you are cool.
Meaning, if you have an iPod you are automatically cool, or that if you are cool, you must have an iPod. Neither can be true while the either false.
Oh, good point.
I'll add that.
But, it doesn't say having an iPod will make you cool. It says you have to have an iPod in order to be cool.
Ender, it would probably be useful if you went over the formal notation or implications of the universal and existential quantifiers.
Quote from: Deuce on November 15, 2006, 08:26:43 PM
You can put this under the Contrapositive section:
(http://latex.sidoh.org/?render=%24%24%20%5Ctextbf%7BLaw%20of%20the%20Contrapositive%7D%20%5Cnewline%0D%0AA%20conditional%20%28%24p%20%5CRightarrow%20q%24%29%20and%20its%20contrapositive%20%28%24%5Cneg%7Bp%7D%20%5CRightarrow%20%5Cneg%7Bq%7D%24%29%20are%20either%20both%20true%20or%20both%20false.)
I believe your definition of the contrapositive is wrong. If
P => Q then the contrapositive is
not Q => not P, instead of
not P => not Q.
For instance:
(1) If you live in Massachusetts then you live in the USA (P => Q) -- correct
(2) If you do not live in Massachusetts then you do not live in the USA (not P => not Q) -- incorrect
(3) If you do not live in the USA then you do not live in Massachusetts (not Q => not P) -- correct
Statements (1) and (2) do not have to be either both true or both false, as shown above. Statements (1) and (3) do have to be either both true or both false, which is what I think you meant by the Law of the Contrapositive.