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”, \land meaning “and”, and not least \lor meaning “or”.  De Morgan’s laws are stated as

\sim (A \lor B) \Leftrightarrow \sim A \land \sim B

\sim (A \land B) \Leftrightarrow \sim A \lor \sim B

Let us see that in action:

Proposition: With x,y \in \mathbb{Z}, if 5\nmid xy, then 5\nmid x and 5\nmid y

Proof: First thing is to make sure we understand the problem. What is says is that if the product xy is not divisible (\nmid 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 \sim A \land \sim B which we need to negate so we get \sim (\sim A \land \sim B) = A \lor B

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 k \in \mathbb{Z} 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 5|x or 5|y, then 5|xy, and thus proves that if 5\nmid xy, then 5\nmid x and 5\nmid y

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 x \in \mathbb{R}, if x^2 < 0 then x < 0

Proof: Assume that x > 0 then it follows that x^2 > 0 since multiplying two positive numbers yield a positive number.

This proves that if x^2 < 0 then x < 0

QED.

At the same time I could prove that if x^2 < 0 then x > 0 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 x^2 \geq 0, \forall x \in \mathbb{R} (where \forall 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