1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof by Contradiction and Contraposition

  1. Jul 29, 2009 #1
    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 [tex]q \in Z[/tex], then n is odd."

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

    2. Relevant equations

    3. The attempt at a solution


    The contrapositive of [tex]A \Rightarrow B[/tex] is [tex]\neg B \Rightarrow \neg A[/tex], so in this case:

    A:= If n=4q+1 or n=4q+3 for some [tex]q \in Z[/tex]
    B:= n is odd

    The contrapositive would be:

    If n is even then [tex]n \neq 4q+1[/tex] and [tex]n \neq 4q+3[/tex] for all [tex]q \in Z[/tex].

    Is this right?


    I have no idea how to answer this one.


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

    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:
    [tex](A \Rightarrow B) \Leftrightarrow \neg (A \wedge \neg B)[/tex]

    [tex]A \wedge \neg B[/tex] = n is odd and [tex]n \neq 4q+1[/tex] or [tex]n \neq 4q+3[/tex]

    Of course, n is odd [tex]\Leftrightarrow (\exists m \in Z)(2m+1)[/tex]

    So, I'm stuck here & I'm not sure exactly how to prove that [tex]A \wedge \neg B[/tex] is false. Any help is appreciated.
  2. jcsd
  3. Jul 29, 2009 #2
    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.
  4. Jul 29, 2009 #3
    About part (C), I need to prove this wrong:

    [tex]A \wedge \neg B[/tex] = "n is odd and [tex]n \neq 4q+1[/tex] or [tex]n \neq 4q+3[/tex]"

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

    Suppose A and [tex]\neg B[/tex] 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

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

    Is this right??
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook