# Proof by Contradiction and Contraposition

1. Jul 29, 2009

### roam

1. The problem statement, all variables and given/known data

For any integer n, let A(n) be the statement:
"If n=4q+1 or n=4q+3 for some $$q \in Z$$, then n is odd."

(a) Write down the contrapositive of A(n).
(b) Is the contrapositive of A(n) true for all $$n \in N$$? Give brief reasons.
(c) Use proof by contradiction to show that the converse of A(n) is true for all $$n \in Z$$.

2. Relevant equations

3. The attempt at a solution

(a)

The contrapositive of $$A \Rightarrow B$$ is $$\neg B \Rightarrow \neg A$$, so in this case:

A:= If n=4q+1 or n=4q+3 for some $$q \in Z$$
B:= n is odd

The contrapositive would be:

If n is even then $$n \neq 4q+1$$ and $$n \neq 4q+3$$ for all $$q \in Z$$.

Is this right?

(b)

I have no idea how to answer this one.

(c)

The converse of the A(n) is: "If n is odd, then n=4q+1 or n=4q+3 for some $$q \in Z$$"

A:= n is odd
B:= n=4q+1 or n=4q+3

Now this is what I have to show for a proof by contradiction:
$$(A \Rightarrow B) \Leftrightarrow \neg (A \wedge \neg B)$$

$$A \wedge \neg B$$ = n is odd and $$n \neq 4q+1$$ or $$n \neq 4q+3$$

Of course, n is odd $$\Leftrightarrow (\exists m \in Z)(2m+1)$$

So, I'm stuck here & I'm not sure exactly how to prove that $$A \wedge \neg B$$ is false. Any help is appreciated.

2. Jul 29, 2009

### snipez90

a) Looks good
b) Search for a counterexample. If you can't, try proving that it's true based on the intuition gained from the search for the counterexample.
c) Any integer m is either even or odd.

3. Jul 29, 2009

### roam

About part (C), I need to prove this wrong:

$$A \wedge \neg B$$ = "n is odd and $$n \neq 4q+1$$ or $$n \neq 4q+3$$"

A:= n is odd
B:= n=4q+1 or n=4q+3

Suppose A and $$\neg B$$ are true; n is odd. n is odd if n=2m+1 and even if n=2m. However n=4q+1 and n=4q+3 are both odd since:

n=4q+1 = 2(2q)+1

And 4q+3= 2(2q+1)+1

$$2q+1 \in Z$$ and $$2q \in Z$$. Hence $$\neg B$$ doesn't imply A, so the converse of A(n) is true for all $$n \in Z$$.

Is this right??