You are here:

- Home
- Science
- Mathematics
- Advanced Math
- Proofs in discrete mathematics

Advertisement

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.”

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.

- Add to this Answer
- Ask a Question

Rating(1-10) | Knowledgeability = 10 | Clarity of Response = 10 | Politeness = 10 |

Comment | You are appreciated! Actually it was a study guide not actual homework. You explained this so much better than a textbook or instructor! I learned a lot from this little bit and am grateful you could help me understand it! You air are a perfect 10!! Thanks again so much! |

Advanced Math

Answers by Expert:

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.

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.