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!

Proof involving a closed set of integers

  1. Aug 7, 2010 #1
    1. The problem statement, all variables and given/known data

    proove is either true of false

    let A be a set of integer closed under subtraction. if x and y are element of A, then x-ny is in A for any n in Z.

    2. Relevant equations

    n/a

    3. The attempt at a solution

    is there any proof, without induction?

    i suspect its true because any arbitrary positive integer n will satisfy,

    though if i try using induction also i stuck.

    when n=0, satisfied,

    assume it is true for some n>=0
    x-(n+1)y=(x-ny)-y, clearly it is inside A

    let n>0

    x-(-n)y and i don't know how to continue now,

    anyway, help me with this induction and also what are other ways without using proof by induction?
     
    Last edited: Aug 8, 2010
  2. jcsd
  3. Aug 8, 2010 #2

    Mark44

    Staff: Mentor

    Re: integer

    If x and y are in A, then x - y is in A, by assumption that A is closed under subtraction.

    Base case: n = 2
    Let y be in A. We know that x - y is in A, so since A is closed under subtraction, then (x - y) - y is in A, and x - y - y = x - 2y.

    Induction hypothesis: n = k
    Assume the statement is true for n = k. I.e., assume that x - ky is in A

    Now show that x - (k + 1)y is in A, using the induction hypothesis.
     
  4. Aug 8, 2010 #3
    Re: integer

    x-(k+1)y = x-ky-y, then x-ky is in A(from induction hypothesis), y is in A,

    so (y-ky)-y is also in A(closed under subtraction) ,

    conclusion, x-ny is in A, for all integer n greater or equal to 2

    but how to show the negative integer of n?

    let n>0

    x-(-n)y and i don't know how to continue now,
     
    Last edited: Aug 8, 2010
  5. Aug 8, 2010 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: integer

    Try something! Is 0 in A?
     
  6. Aug 8, 2010 #5
    Re: integer

    if A is closed under subtraction, let x be in A, then x-x=0 must be in A, so 0 is in A. is that correct?
    but i don't have idea why this is related to induction, T_T
     
  7. Aug 8, 2010 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: integer

    That's correct. Good. It's not related to the induction. It's related to solving your problem of why x-n*y being true for positive n is also true for negative n. x-(-n)y=x-n(-y). Now keep thinking.
     
    Last edited: Aug 8, 2010
  8. Aug 9, 2010 #7
    Re: integer

    hmm, maybe , but i realized, set of integer that is closed under subtraction is either set containing 0, or set of integer itself,
    ie; A = {0} or A = Z,
    is that correct??
     
  9. Aug 9, 2010 #8
    Re: integer

    huh, my i got counterexample for my statement, but i got some idea, lemme think some more
     
  10. Aug 9, 2010 #9
    Re: integer

    Use mathematical induction.
     
  11. Aug 9, 2010 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: integer

    Oh come on. You've already proved x-ny is in A using induction for n>=0. You want to prove x-(-n)y is in A for n>=0. x-(-n)y=x-n(-y)=x-n(0-y). I'm going to have to ask you to think again. If I have to get cute this is going to get ugly. I heard that in Futurama last night. Please see it. And by the way, the set of even numbers is closed under subtraction. So A isn't equal to either {0} or Z. I'm surprised you didn't see that either.
     
  12. Aug 10, 2010 #11
    Re: integer

    aha, you sound like you have high expectation on me.. but much misunderstanding here, which we don't bother to know, anyway



    if x and y is in A then -y in A (zero is in A), then x-n(-y) is in A (closed under subtraction),

    owho, i get it already, thank you very much^^
     
  13. Aug 10, 2010 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: integer

    There you go. You should also notice you can use that argument to show 'closed under subtraction' implies that it's also closed under addition.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof involving a closed set of integers
  1. Closed set proof (Replies: 57)

Loading...