# 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

SuprDewd

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.

Kristian

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.

SuprDewd

Hehe. Thanks.