Proof by Contradiction and Contraposition

[roam]

Homework Statement

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.

Homework Equations

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.

 

[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.

 

[roam]

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.

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??