# Set Theory, Can you check to see if this is right, Is AoA3 a parition of Z?

1. Oct 7, 2006

### mr_coffee

Hello everyone.

I think i have this right but im' not 100% sure due to the last set, $$A_3$$

Here is the problem:
http://suprfile.com/src/1/3m5fyjg/lastscan.jpg [Broken]

Yes. By the quotient-remainder theorem, every integer n can be represented in exactly one of the three forms.
n = 4k or n = 4k+1 or n = 4k+2, for some integer k.
This implies that no integer can be in any two of the sets A0, A1, A2, or A3. So A0, A1, A2, and A3 are mutually disjoint. It also implies that every integer is in one of the sets A0, A1, A3, and A4. So $$Z = A_0 \bigcup A_1 \bigcup A_2 \bigcup A_3.$$

But what makes me question myself is they have $$A_3$$ such that n = 4k+3, which is just another odd integer....meaning if all integers can be expressed by n = 4k or n = 4k+1 or n = 4k+2, does that mean n = 4k+3 is redudnant and it will contain a duplicated number that n = 4k or n = 4k+1 or n = 4k+2 has already formed? If this is the case then this false because for
$$Z = A_0 \bigcup A_1 \bigcup A_2 \bigcup A_3.$$
to be true, none of the partions are allowed to have duplicated numbers.

Any help would be great, thanks!

Last edited by a moderator: May 2, 2017
2. Oct 7, 2006

### StatusX

I'm not sure what you're asking. All numbers of the form 3k+3 are also of the form 3k. But this doesn't happen with 4k+3.

3. Oct 7, 2006

### mr_coffee

Oops i accidently had 3k's where I wanted 4k's. I edited it now.

I'm trying to figure out, if n = 4k, n = 4k+1, n = 4k+2, n = 4k+3, if any of these numbers would repeat themsevles in a set, if they would then this statemnt would be false, if not then it would be true.

such as...
let k = 0;
n = 4k, n = 4k+1, n = 4k+2, n = 4k+3,
n = 0, n = 1, n = 2, n = 3
k = 1
n = 4, n = 5, n = 6, n = 7
k = 2
n = 8, n = 9, n = 10, n = 11

So it looks like these are going to keep going and never duplicate a number, So thats what i'm checking to see if my answer is right up there when i said:

Yes. By the quotient-remainder theorem, every integer n can be represented in exactly one of the three forms.
n = 4k or n = 4k+1 or n = 4k+2, for some integer k.
This implies that no integer can be in any two of the sets A0, A1, A2, or A3. So A0, A1, A2, and A3 are mutually disjoint. It also implies that every integer is in one of the sets A0, A1, A3, and A4.

4. Oct 7, 2006

### StatusX

Ok. Another way is just assume, say, n=4k+1=4l+3. Then 4(k-l)=2, a contradiction, since 4 doesn't divide 2.

5. Oct 7, 2006

### mr_coffee

I don't have to prove this byinduction, so could I write what you said and just add alittle more like...

Let n = 4k+1 = 4l+3, where k and l are integers.
Then 4(k-l) = 2 = (k-l) = 1/2. 1/2 is not an integer which is a contradiction therefore, $${A_0, A_1, A_2, A_3}$$ is not a parition of Z.

I do see this contradicts the orginal statemnt because they said n is in Z which is all integers, and 1/2 is not an integer is that what your saying?

I was thinking they would want me to prove this by it violating some rule of sets, like all sets must be different if they are paritioned, meaning you can;t have A1 = {1,2,3,4} A2={5,6,7,8}, A3 ={8,9,10,11} But they never told me to prove it that way so this will work too, if i'm understanding you correctly.

6. Oct 7, 2006

### StatusX

All I was showing was that the sets A1 and A3 are disjoint. The contradiction was based on the assumption that the k in the defintion of these sets was an integer, and has nothing to do with whether the sets form a partition of Z. What exactly is the quotient-remainder theorem, and how have you tried to use it?

7. Oct 10, 2006

### mr_coffee

Status, Sorry about the delayed responce,
The quotient-remainder theorem states given any inteer n and postive integer d, there exists unique integers q and r such that
n = dq + r and 0 <= r < d

if u let d = 4, this implies that here exists an integer quotient q and a remainder r such that
n = dq + r and 0 <= r < 4, but the only nonnegative remainders r that are less than 4 are 0, 1, 2, and 3. Hence
n = 4q or n = 4q + 1 or n = 4q + 2 or n = 4q+3

for some integer q.

So wouldn't this make it true?