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!

Prove no odd integer can be expressed as 4k+1 and 4j-1

  1. Jul 6, 2012 #1
    I am preparing for my Fall bridge to abstract math course and came across following problem:

    "Prove that there is no odd integer that can be expressed in the form 4j-1 and 4k+1 for integers j and k."

    If you let
    P(x) = "x is odd"
    Q(x) = ([itex]\exists[/itex]j[itex]\in[/itex][itex]Z[/itex])(x=4j-1)
    R(x) = ([itex]\exists[/itex]k[itex]\in[/itex][itex]Z[/itex])(x=4k+1)

    Then literally I understand the above statement as:
    [itex]\neg[/itex][[itex]\exists[/itex]x[itex]\in[/itex][itex]Z[/itex]][ P(x)[itex]\Rightarrow[/itex]( Q(x) [itex]\wedge[/itex] R(x) ) ]

    But is this the same thing as:
    [[itex]\forall[/itex]x[itex]\in[/itex][itex]Z[/itex]][ P(x)[itex]\Rightarrow[/itex]( Q(x) [itex]\vee[/itex] R(x) ) ]
    ??

    If you logically simplify both of these statements, they turn out to not be logically equivalent, but they both seem to equally fit the meaning of the initial statement. The latter just seems to have a simpler formal proof because it is equivalent to
    [[itex]\forall[/itex]x[itex]\in[/itex][itex]Z[/itex]][ P(x)[itex]\wedge\neg[/itex]Q(x)[itex]\Rightarrow[/itex]R(x) ) ] , so in the proof you can just assume P(x)[itex]\wedge\neg[/itex]Q(x) and use that to get to R(x)..
     
  2. jcsd
  3. Jul 6, 2012 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    That is how I understood the statement.

    No, they are not the same thing. Can you explain why you think they are the same think??
     
  4. Jul 6, 2012 #3
    Suppose not, suppose there IS some n where n=4k+1=4j-1
    then it stands to reason that (4j-1)-(4k+1)=0
    see what you can conclude from there :-)
     
    Last edited: Jul 6, 2012
  5. Jul 6, 2012 #4

    I realized that in [∀x∈Z][ P(x)⇒( Q(x) ∨ R(x) ) ] , for the 'or' I meant the exclusive or, so I actually mean:
    [∀x∈Z] { [ P(x)∧¬Q(x)]⇒R(x) ] ∧ [ P(x)∧Q(x)]⇒¬R(x) ] }
    For the given P,Q and R this can easily be proven true.

    So since P is true and P(x)⇒( Q(x) ∨ R(x) ) is true, then ( Q(x) ∨ R(x) ) must be true (again meaning exclusive or).

    So we know that exactly one of Q or R is true and exactly one is false, so Q(x) ∧ R(x) must always be false, and so assuming P is true, ¬[∃x∈Z][ P(x)⇒( Q(x) ∧ R(x) ) ] is always true.

    So since both statements are always true, they are equivalent...
     
  6. Jul 6, 2012 #5

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    why make it so complicated? :cry:

    i'm with tt2348's :smile: method …
     
  7. Jul 6, 2012 #6
    Then 2(j-k)=1, so j-k must be 1/2, so j and k cannot both be integers as required :)
    My question however was not how to prove, just how the statement to be proved could possibly be restated
     
  8. Jul 6, 2012 #7
    haha idk my book likes complications i guess lol. but guys i know how to prove this, im just more interested in how this statement can be equivalently restated and if i made any errors in my second post in trying to show that the literal logical translation of the initial statement is equivalent to my interpretation
     
    Last edited: Jul 6, 2012
  9. Jul 6, 2012 #8

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Because they're pure math people?? Their notion of a good time appears to involve things like self-inflicted use of torture devices straight out of the Inquisition. To have a truly jolly good time they have to go well beyond crude Torquemada-like torture devices. Inverting universal and existential quantifiers, now that's a good time.

    But that's not fun!
     
  10. Jul 6, 2012 #9
    Using logical restrictions.. you can drop the P(x) requirement.
    since regardless, even or odd, there is no integer such that x=4k-1=4j+1
    so it boils down to x is an integer=>~(Q(x)&R(x))
    =>(~q)v(~r)
     
  11. Jul 6, 2012 #10
    or it's converse, Q(x)&R(X)=> x isn't an integer
     
  12. Jul 6, 2012 #11
    Right, but every odd integer is either R or Q, but not both and not neither, am i right? That's what I was trying to prove in my second post.
     
  13. Jul 6, 2012 #12
    yes, it is indeed an exclusive or.
    But you need to be careful with your formulation
    F=>F
    is true
    also
    F=>T
    is true
    Generally, logical propositions alone are not enough to be mathematically rigorous, and most professors want something using significantly less notation.
     
  14. Jul 6, 2012 #13

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    That's certainly true, but wouldn't the original statement be true even if neither R nor Q were true? It seems like you're adding an additional condition by saying one of them has to be true.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook