You are here:

Advanced Math/Proofs in discrete mathematics

Advertisement


Question
I know what direct, contradiction, and contraposition are. I can't seem to figure this out for the life of me. I need direction.

a direct proof, a proof by contraposition, and a proof by contradiction of the statement: if n is even, then n+4 is even.

Answer
Although this seems like a homework question, I will answer this one because this is a very subtle question and some instruction and explanation will probably help. Of course, if you just copy your answer out of this and don't read, you won't really get the full benefit, so I caution you: Please read this answer and try to learn from it.


In mathematics, most statements that one wishes to prove are of the form:

If [something], then [something else].

Some statements may be more like:

All [something] have the property [something else].

Those two are really equivalent. If you look at some scenario, where the hypotheses which I called [something] are true, then you can form some conclusion which I called [something else].

In symbolic notation, if you let P be the hypotheses and Q be the conclusion, we write:

P ⇒ Q

Proof of such a statement is a series of deductions. There are three types of proof (well, there are more, but the three you mention are quite common). They are defined by how they begin and end.

Direct proof just assumes P is true, and from that deduces Q. The proof is:

Assume P.
[deduction]
[deduction]
...
[deduction]
Thus Q.

Some trail of deduction leads us from P to Q eventually.



Proof by contraposition is based on the notion that P⇒Q is logically equivalent to Q⇒P, where is the logical negation ("not"). So what you do in this case is prove P directly from Q.

Assume Q.
[deduction]
[deduction]
...
[deduction]
Thus P.



Finally, proof by contradiction treats P⇒Q as a single logical statement and asks "What if this is false?" The negation of a conditional statement is:

(P⇒Q) == P ∧ Q

Where ∧ is the "and" symbol (conjunction) and == means logical equivalence.


So proof by contradiction says to assume the opposite of what you want to be true, and from this, deduce any sort of contradiction. For example:

Assume (P⇒Q)
Same as P ∧ Q
[deduction]
[deduction]
...
[deduction]
[some contradiction]
Thus, (P⇒Q) cannot be true.
Thus P⇒Q is true.





Now, how does this all apply to your situation?

Well, try to begin and end a proof with each statement in the right way:

P = n is even
Q = n+4 is even


Direct proof:

Assume n is even.
Then there is some integer k so that n=2k.
Then n+4 = 2k+4 = 2(k+1).
Thus the integer k'=k+1 gives n+4=2k'.
Thus n+4 is even.



Contrapositive:

Assume n+4 is odd.
Then there is some integer k so that n+4 = 2k+1
Thus n = 2k-3 = 2(k-2)+1.
So the integer k' = k-2 gives n = 2k'+1.
Thus n is odd.


Conradiction:

Assume n is even, but n+4 is odd.
Then (n+4)-n is odd.
But n+4-n = 4 is even.
This implies 4 is odd and even! A contradiction.
Thus if n is even, n+4 must be odd.



And that's that.

Advanced Math

All Answers


Answers by Expert:


Ask Experts

Volunteer


Clyde Oliver

Expertise

I can answer all questions up to, and including, graduate level mathematics. I am more likely to prefer questions beyond the level of calculus. I can answer any questions, from basic elementary number theory like how to prove the first three digits of powers of 2 repeat (they do, with period 100, starting at 8), all the way to advanced mathematics like proving Egorov's theorem or finding phase transitions in random networks.

Experience

I am a PhD educated mathematician working in research at a major university.

Organizations
AMS

Publications
Various research journals of mathematics. Various talks & presentations (some short, some long), about either interesting classical material or about research work.

Education/Credentials
BA mathematics & physics, PhD mathematics from a top 20 US school.

Awards and Honors
Various honors related to grades, various fellowships & scholarships, awards for contributions to mathematics and education at my schools, etc.

Past/Present Clients
In the past, and as my career progresses, I have worked and continue to work as an educator and mentor to students of varying age levels, skill levels, and educational levels.

©2016 About.com. All rights reserved.