# Homework Help: Proof involving a closed set of integers

1. Aug 7, 2010

### annoymage

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. Aug 8, 2010

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

3. Aug 8, 2010

### annoymage

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
4. Aug 8, 2010

### Dick

Re: integer

Try something! Is 0 in A?

5. Aug 8, 2010

### annoymage

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

6. Aug 8, 2010

### Dick

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
7. Aug 9, 2010

### annoymage

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

8. Aug 9, 2010

### annoymage

Re: integer

huh, my i got counterexample for my statement, but i got some idea, lemme think some more

9. Aug 9, 2010

### Dickfore

Re: integer

Use mathematical induction.

10. Aug 9, 2010

### Dick

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.

11. Aug 10, 2010

### annoymage

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

12. Aug 10, 2010

### Dick

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.

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