Proof techniques: Difference between revisions
Content deleted Content added
No edit summary |
redirect to Mathematical proof per AFD |
||
| (25 intermediate revisions by 18 users not shown) | |||
| Line 1: | Line 1: | ||
#REDIRECT [[Mathematical proof]] |
|||
{{attention}} |
|||
{{accuracy}} |
|||
In analytical [[calculus]] (often times known as '''advanced calculus''', a specific subset of '''[[mathematical analysis]]'''), there are three important methods to determine that a given hypothesis is true or false. |
|||
==Technique #1: deductive proof== |
|||
Deductive proof, or [[direct proof]], is very straightforward. |
|||
Given some hypothesis: |
|||
There is a logical method to prove that the hypothesis is true through step by step operations and by using postulates, lemmas, and definitions in constructing the final conclusion. |
|||
Many mathematical hypothesis can be proven using deductive proof techniques. |
|||
'''Example''' |
|||
If <math>a \in R \ge 0</math> |
|||
Prove <math>a^2 \ge 0</math> |
|||
'''Proof:''' |
|||
Since <math>a \ge 0</math> then by multiplicative property of real number system, |
|||
<math>a \star a \ge a \star 0 </math> |
|||
<math>a^2 \ge 0 \mathcal{p}</math> |
|||
==Technique #2: proof by contradiction== |
|||
Given some hypothesis: |
|||
It is automatically assumed that the conclusion is wrong, and an antihypothesis must be proven. Then, deductive proof is used (stepwise operations and definitions) to reach a final conclusion. If this final conclusion contradicts the original hypothesis then it is said that the original conditions are proven to be true and correct. |
|||
More difficult mathematical hypothesis can be proved or disproved using [[proof by contradiction]] techniques. |
|||
'''Example''' |
|||
Extreme Value Theorem (proof by contradiction): |
|||
Assume <math>F(x)</math> is UNbounded on [a,b]. |
|||
i.e., there exists <math>{x_n}\subset[a,b]</math> such that <math>f(x_n)\rightarrow\infty</math>. |
|||
Since <math>x_n</math> is bounded, then Bolzano-Weirstrauss Theorem says: |
|||
There exists <math>{x_{nk}}\rightarrow C \in [a,b]</math> such that |
|||
<math>\lim_{n \to \infty}x _{nk} \rightarrow C</math> and |
|||
<math>\lim_{n \to \infty}f (x _{nk}) \rightarrow \infty</math>. |
|||
Since f is continuous at point C, then f(C) = <math>\lim_{k \to \infty}f{x_k} =\infty</math> |
|||
Because <math>x_{nk}</math> is bounded and f(C) is bounded, thsi conclusion is wrong. F(x) must be bounded on [a,b]. |
|||
==Technique #3: mathematical induction== |
|||
[[Mathematical induction]] is very powerful two step process, and can only be used for the natural number <math>n\ </math> |
|||
Prove <math>\sum_{k=1}^n\ 4k\ = \ 2(n+1)</math> for all k and n. |
|||
Step 1, consider case <math>k=1</math>. |
|||
Right hand side (of equation) equals 4. |
|||
Left hand side equals 4. |
|||
Equation satisfied for n = 1. |
|||
Assume equation true for some n. |
|||
Step 2, consider case <math>n+1</math>. |
|||
<math>\sum_{k=1}^n\ 4k\ = \ 2(n+1)\ = \sum_{k=1}^n\ 2n(n+1)\ +\ 4(n+1) = \ 2(n+1)\ \star\ 2(n+1)(n+1+1)</math> |
|||
Simplify left and right hand sides. |
|||
Left hand side equals 2(n+1)(n+2) |
|||
Right hand side equals 2(n+1)(n+2) |
|||
Both sides are equivalent. |
|||
Based on cases n=1 and n=n+1, mathematical induction tells us |
|||
equation true for all k,n, in N. <math>\mathcal{p}</math> |
|||
==See also== |
|||
# [[proof theory]] |
|||
# [[Mathematical proof]] |
|||
==Reference== |
|||
# Wade, William R. ''An Introduction to Analysis.'' Upper Saddle River, New Jersey: Pearson Prentice Hall, 2004. |
|||
[[Category:Mathematical analysis]] |
|||
Latest revision as of 18:51, 29 June 2006
Redirect to: