Proof Method: Contrapositive proof

Contrapositive proofs – part 2

Once I finished up the post on contrapositive proofs I spend the better part of an hour feeling I wasn’t quite finished with the topic. I still had a couple of things to explore. The first one is a contrapositive proof that puzzled me, the other thing is De Morgan’s Laws which tells us how to negate a statement.

De Morgan’s Laws

So let us start with the latter; De Morgan’s laws.  We have the following symbols (~ meaning “not”, meaning “and”, and not least  meaning “or”.  De Morgan’s laws are stated as

Let us see that in action:

Proposition: With , if , then and

Proof: First thing is to make sure we understand the problem. What is says is that if the product xy is not divisible ( means not divisible) with 5 then both x and y are not divisible by 5. Okay, easy to understand.

Next thing is to negate what follows from the first part of the proposition. It has the structure which we need to negate so we get

So let us assume that x or y is divisible by 5.  We need to prove both cases, so lets start by assuming that x is divisible by 5. Then we have that x = 5k for some and that means we have xy = 5ky, which is clearly divisible by 5. If y is divisible by 5 we have that y = 5l and then we get xy = 5xl which is also clearly divisible by 5.

The above case shows that if or , then , and thus proves that if , then and

QED.

I think you get the idea of using De Morgan’s laws to negate a composite statement. So I will jump to the second topic.

If P is rubbish then Q does not make sense

Something that actually kept me awake for a while until I figured out what was wrong.

Proposition: Assume that , if then

Proof: Assume that then it follows that since multiplying two positive numbers yield a positive number.

This proves that if then

QED.

At the same time I could prove that if then using the same argument. Yet we know perfectly well that both cannot be true and for a while I was puzzled  until a thing dawned on me.  Since the if part of the proposition can never be true since (where means “for all”), so proving what happens if that is true will always be rubbish.

You might say that is clear, but to me it was apparently a deep insight, so I thought I would share those two things with you.

Posted by Kristian

3 comments

You disproved the second proposition, right?
Because if x is an element of R, then x^2 >= 0.

Just making sure… Proofing is no easy-business.

And I think some of the < and > signs could be swapped?
Like the first line of the proof of the second proposition you write x < 0 and then say “since multiplying two positive numbers“.

But thanks.

First thing, yes you are right, I did made a mistake with the < sign, it is now corrected (I think). Thank you for noticing that. I don't know if I disproved anything. I just realised that what you ask needs to be sensible. I tried to make a proposition on the form of if P then Q, but in fact I would never be able to get P to be true, since negative numbers are outside the range of x2.

So the first sensible thing to test is if P is ever true. I think that was my main conclusion after spending an hour of time in my bed.

I hope that clears it up a bit.

Hehe. Thanks.

Leave a Reply