LinkBack URL
About LinkBacksAnyone here good at mathematical proofs and would be willing to help me understand them?
There are 5 types of proof, and I will give an example of each:Originally Posted by Possible actuary
The first type, and the strongest type, is Direct Proof. If you can directly prove it, then it is the best way to prove something.
Theorem. If a divides b and b divides c then a divides c.
Proof. By our assumptions, and the definition of divisibility, there are natural numbers k1 and k2 such that
b = a k1 and c = b k2. Consequently,
c = b k2 = a k1 k2. Let k = k1 k2. Now k is a natural number and c = a k, so by the definition of divisibility, a divides c
The second type, and probably the most used back in the ancient times, is proof by contradiction. We take a theorem that we assume is true, and in order to prove it by contradiction, we assume that our theorem is true when it is false and try to logically work it out that way. If we come up with a contradiction in the proof, then it is true when our original theorem is true and it is false when we assume that our theorem is true when it is false. The most famous proof is probably Eulid's proof that the sqrt(2) is an irrational number.
Theorem. √2 cannot = p/q
Proof. By contradiction we assume that our original Theorem is false:
√2 = p/q
2 = p^2/q^2
2q^2 = p^2
By this we see that p is positive so that:
p = 2r
Now we plug 2r into p^2
2q^2 = 4r^2
q^2/r^2 = 2
q/r = √2
√2 can't equal both p/q AND q/r, thus we have a contradiction, proving our original theorem true.
The third type of contradiction is Proof by Contrapositive. Where we take the contrapositive of a theorem and prove it.
The difference between the Contrapositive method and the Contradiction method is subtle. Let's examine how the two methods work when trying to prove "If P, Then Q".The method of Contrapositive has the advantage that your goal is clear: Prove Not P. In the method of Contradiction, your goal is to prove a contradiction, but it is not always clear what the contradiction is going to be at the start.
- Method of Contradiction: Assume P and Not Q and prove some sort of contradiction.
- Method of Contrapositive: Assume Not Q and prove Not P.
Definitions.
For the purpose of this example we will assume as proved that each integer is either even or odd. Theorem. If x and y are two integers for which x+y is even, then x and y have the same parity.
- An integer x is called even (respectively odd) if there is another integer k for which x = 2k (respectively 2k+1).
- Two integers are said to have the same parity if they are both odd or both even.
Proof. The contrapositive version of this theorem is "If x and y are two integers with opposite parity, then their sum must be odd." So we assume x and y have opposite parity. Since one of these integers is even and the other odd, there is no loss of generality to suppose x is even and y is odd. Thus, there are integers k and m for which x = 2k and y = 2m+1. Now then, we compute the sum x+y = 2k + 2m + 1 = 2(k+m) + 1, which is an odd integer by definition.
The fourth type of proof is If and only If Proofs. It is just proving two implications.
In this example we will use a very useful fact about integers, the so called Division Algorithm: If n and m are integers, then there are two other integers q and r, where 0 <= r < m, and such that n = qm + r. For example, if n = 103 and m = 15, then 103 = (6)(15) + 13. (That is, if we divide15 into 103, we get a quotient of q = 6, with a remainder of r = 13.) Theorem. If a is an integer, then a is not evenly divisible by 3 if, and only if, a2 -1 is evenly divisble by 3.
Proof. Since this is an "If, and Only If" theorem, we must prove two implications.
("If") We must prove "a is not evenly divisible by 3 if a2 -1 is evenly divisble by 3". So we assume that 3 evenly divides a2 -1 = (a-1)(a+1). Since 3 is a prime number, 3 must evenly divide either a-1 or a+1. In either case, it should be apparent that 3 cannot evenly divide a.
("Only If"). We must prove "a is not evenly divisible by 3 only if a2 -1 is evenly divisble by 3." This means "If a is not evenly divisible by 3, then a2 -1 is evenly divisble by 3". This is where we use the division algorithm stated above. We can write a = 3q + r, where r = 0, 1 or 2. Our assumption that a is not divisible by 3 implies r cannot be 0. If r =1, then a-1 = 3q and so 3 evenly divides a2 -1 = (a-1)(a+1). A similar argument works if r = 2.
The fifth type of proof, and probably the most common, is proof by Induction. It is taking something and then proving it and then proving it for the next consequtive situation using a basic assumption, thus proving it for all situations that follow the same criteria.
Theore. For any positive integer n, 1 + 2 + ... + n = n(n+1)/2.
Proof. (Proof by Mathematical Induction) Let's let P(n) be the statement "1 + 2 + ... + n = (n (n+1)/2." (The idea is that P(n) should be an assertion that for any n is verifiably either true or false.) The proof will now proceed in two steps: the initial step and the inductive step.
Initial Step. We must verify that P(1) is True. P(1) asserts "1 = 1(2)/2", which is clearly true. So we are done with the initial step.
Inductive Step. Here we must prove the following assertion: "If there is a k such that P(k) is true, then (for this same k) P(k+1) is true." Thus, we assume there is a k such that 1 + 2 + ... + k = k (k+1)/2. (We call this the Inductive Assumption.) We must prove, for this same k, the formula 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2.
This is not too hard: 1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k(k+1) + 2 (k+1))/2 = (k+1)(k+2)/2. The first equality is a consequence of the inductive assumption.
And that's about it for proofs, enjoy.
There is actually another type of proof, which my favorite mathemation used a lot and developed it.
It is called "Infinite Descent".
I am taking a university class titled "Algebraic Structures" and all we have done so far is proofs. I am having a hard time understanding when given something to prove where to start. I understand truth tables, implications and iff. I am having a little trouble stating negations.
An example: Let x be an integer. Prove that if 3 does not divide (x^2+x), then 3 does not divide x and 3 does not divide (x+1).
I am also having some trouble with the 3 (or 2 or whatever #) does or does not divide (something).
Thanks
so the negation rules are just rules you have to memorize. the negation of "and" is "or", the negation of "for all" is "there exists", the negation for "A=>B" is "A and ~B", among others, your text should tell you all of these. looking at the problem you gave, here are some general principles you want to follow. unlike with trig identities, which i always tell people to work on the most complicated side, with proofs, you usually want to start with the simpler side. if we do a direct proof with this question, we would have to worry about remainders, since 3 does not divide, and we would have to deal with 3 does not divide x^2 + x. that is not something we want to do, proofs are hard enough as they are, we dont want to make them harder by tackling the more complicated side. here, the contropositive is the best proof (read above for the details), the contropositive says we can prove A=>B (which is the kind of statement we have here, do you see that?) by proving ~B => ~A. this way we dont have to deal with remainders since "does not divide" becomes "divide" and we work with 3|x and 3|x+1 as opposed to working with the quadratic. here goes.
Proof:
Assume by way of the contropositive that 3|x + 1 or 3|x. then x = 3c for some integer c, or x + 1 = 3d for some integer d. thus we have 2 cases:
case 1: x = 3c
=> x^2 + x = (3c)^2 + 3c = 9c^2 + 3c = 3(3c^2 + c)
since 3c^2 + c is an integer, 3|x^2 + x
case 2: x = 3d - 1
=> x^2 + x = (3d - 1)^2 + 3d - 1 = 9d^2 - 6d + 1 + 3d - 1 = 9d^2 - 3d = 3(3d^2 - d)
since 3d^2 - d is an integer, 3|x^2 + x
so we see that in both cases of the contropositive, if 3|x or 3|x + 1 then 3|x^2 + x, and thus the contropositive is true, that is, if if 3 does not divide (x^2+x), then 3 does not divide x and 3 does not divide (x+1)
QED
so in general, when you have a problem with does not divide, it is usually better to use the contropositive to turn it into divides
I think that I just now got the 3 does or does not divide thing 3 l (x+2) is same as
3
----- = c, c is some integer
(x+2)
When you are doing a contrapositive proof, do you always do ~B=>~A when given A=>B? Would it be safe to say direct proof should be tried first, then contrapositive and then contradiction? Contradiction is what we just started on today.
For contrapositive proofs, if you are given ____ then prove by _____. :
A<=>B then prove by ~B<=>~A?
I can't think of any other cases/possibilities.
that's the other way around. that's (x + 2)|3, but in any case it is conventionally written as a product. so for (x + 2)|3, instead of 3/(x + 2) = c, we write 3 = c(x + 2)
yes, you always do this. this is what proving by contropositive means
When you are doing a contrapositive proof, do you always do ~B=>~A when given A=>B?
no. this is especially ill advised on tests. proofs can be very involved, it is not wise to try several proof techniques hoping one will work. you have to make an educated guess as to which proof to use, this requires more critical thinking than experience. experience helps when several ways of proving something involve pretty much the same amount of work, but one is preferable over the other. direct proofs are generally prefered, however there are other situations when other proof techniques are prefered, even required. for instance, when you want to DISPROVE something, a proof by contradiction is usually the way to go.
Would it be safe to say direct proof should be tried first, then contrapositive and then contradiction? Contradiction is what we just started on today.
you answered this question already. it's given A=>B then prove by ~B=>~A
For contrapositive proofs, if you are given ____ then prove by _____. :
A<=>B then prove by ~B<=>~A?
I can't think of any other cases/possibilities.
iff statements (that is statements described by <=>) are proven one implication at a time (in most cases) so the standard definition for contropositive still works
Okay how about proofs involving congruence of integers. How the book puts it: For integers a,b and n>or=2, we say that a is congruent to b modulo n. Don't know how to convey the congruent symbol. I have no idea what I am doing here. Could we start with the very basics on congruence and what (mod x) has to do with it?
The proof that she gave on a quiz: Let n be an integer. Prove that if n is not congruent to 0 (mod 3), then n^2 is congruent to 1 (mod 3).
Also, shouldn't I have written 3 l (x+1) as
(x+1)
----- = c therefore 3c=(x+1)
3
we say a is conguent to b (mod n) if n|(a - b). that is a - b = nc for some integer c. it's basically a way to categorize divisibility based on remainders. example 24 is congruent to 6 (mod 9). that is 9|(24 - 6) so 9|18, which is true
remainders occur when something is not congruent.
Let n be an integer. Prove that if n is not congruent to 0 (mod 3), then n^2 is congruent to 1 (mod 3).
Proof:
We employ a direct proof. assume n is not congruent to 0 (mod 3), then 3 does not divide (n - 0) = n. therefore, n = 3c + r, where r is the remainder when we divide by 3, thus r = 1 or 2 (note, if r is 0 it means the number was divisible by 3, if r is 3, it means the number is divisible by 3). thus we have 2 cases: (1) n = 3c + 1, and (2) n = 3c + 2
case 1: n = 3c + 1
if n = 3c + 1, then n^2 - 1= (3c + 1)^2 - 1 = 9c^2 + 6c + 1 - 1 = 3(3c^2 + 2c).
since 3c^2 + 2c is an integer, 3|n^2 - 1 and so n^2 is congruent to 1 (mod 3).
case 2: n = 3c + 2
if n = 3c + 2, then n^2 - 1 = (3c + 2)^2 - 1 = 9c^2 + 6c + 4 - 1 = 3(3c^2 + 2c + 1)
since 3c^2 + 2c + 1 is an integer, 3|n^2 - 1, and so n^2 is congruent to 1 (mod 3).
So we see in both cases where n is not congruent to 0 (mod 3), n^2 is congruent to 1 (mod 3).
QED
yes, that's correct. wasnt that what we had last time?Also, shouldn't I have written 3 l (x+1) as
(x+1)
----- = c therefore 3c=(x+1)
3
I am having some trouble getting a proof started by proving or disproving.
Given: For every positive irrational number b, there exists an irrational number a with 0<a<b.
I believe that this statement is true. The book suggests that to start the proof by: Let b be a positive irrational number. Consider a=b/2.
I am having a hard time getting this one started.
Thanks
  |
