Math Is Fun Forum

Kazy

Member

Registered: 2006-01-24

Posts: 37

Should be easy proof

I need to prove or disprove the following:

Let P(n,m) be the open sentence "n and m are odd integers" and Q(n,m) be the open sentence "nm is an odd integer".

a) For all integers n and m, P(n,m) -> Q(n,m)          **-> means implies**
b) For all integers n and m, Q(n,m) -> P(n,m) 
c) For all integers n and m, P(n,m) <-> Q(n,m) 

I'm not sure how to go about proving these, any help would be much appreciated.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Should be easy proof

What class are you in?  Do you wish to do a formal proof?  Formal proofs just mean you follow a certain structure in writing your proof.  I can help you on writing a formal one if you need it.  But if you're in high school, I doubt that you will.  That being said, the below is not formal:

There are two main ways you prove positive statements (if X, then Y).  One is a direct proof, and if you can do it this way, it is recommended you do so.

In a direct proof, you assum the "if" part, and try to show that this means the "then" part is true.

For all integers n and m, P(n,m) -> Q(n,m)

This means if P(n, m) is true, then Q(n, m) is true.  That's the same meaning as implies, as you wrote.

So we consider P(n, m) to be true.  That is, let n and m be odd integers.

What does this mean about n and m?  What is the definition of odd?  The offical definition is any integer n is odd when n = 2k + 1, where k is any integer.  Lets do the same for m: m = 2l + 1.  Note, you can't use k for both, as that would imply that n and m are both the same odd integers.

n = 2k+ 1, m = 2l + 1

Now we wish to show that nm is an odd integer.

nm = ?
nm = (2k + 1)(2l + 1)
nm = 4kl + 2k + 2l + 1

Is that number odd?  It should be apparent that it is.  This is because we can factor out a 2:

nm = 2(2kl + k + l) + 1

What is 2kl + k + l?  Why, that's an integer!  Let 2kl + k + l = x, where x is an integer.

nm = 2x + 1

Isn't that what we said our defintion of odd was?  So nm must be odd.

You try the second one, it should be easy.  The reason?  All you have to do is work the first one in reverse.  Start from the conclusion, and work your way back up.

For the thrid one, P(n,m) <-> Q(n,m), all you need to show is that P(n, m) -> Q(n, m) and Q(n, m) -> P(n, m).  And that's exactly what the first two are.  So once you've done these, all you have to do is state that the third is therefore true.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Should be easy proof

Oh heck, why not.  The below is a formal proof of the first one.

Prove that for all odd integers n and m, that nm is also odd.

Proof: Let n and m be odd integers. 

This means that n = 2k + 1, where k ∈ Z, and m = 2l + 1, where l ∈ Z.

Then, n*m = (2k + 1)(2l + 1) = 4kl + 2k + 2l + 1 = 2(2kl + k + l)
Since 2kl + k + l must be an integer, let 2kl + k + l = x, where x ∈ Z.
Thus, n*m = 2x + 1.

∴ n*m must be an odd number.  QED.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."