Let X = {l ? Z | l = 5a + 2 for some integer a}, Y = {m ? Z | m = 4b + 3 for some integer b}, and Z = {n ? Z | n = 4c ? 1 for some integer c}.

Question

(a) Is X ? Y ?
(b) Is Y ? Z?
Justify your answers carefully. (In other words, provide a proof if the statement is true or a
disproof if the statement is false.)

Answer 1

a. X * Y
Counterexample:
2 ? X because 2 = 5 · 0 + 2, but 2 /?
Y because if 2 were in Y , then there would exist an
integer, say b, such that 2 = 4b + 3. But if this were the case, then 4b = ?1, and so b = ?1/4,
which is not an integer.
b. Y ? Z
Proof:
Suppose x is a particular but arbitrarily chosen element of Y .
[We must show that x is in Z. By denition of Z, this means that we must show that
x = 4·(some integer) ? 1.]
By definition of Y , x = 4b + 3 for some integer b.
[Scratch work: Is there an integer, say c, such that x = 4c?1? If so, then 4b+3 = 4c?1,
which implies that 4c = 4b+4, or, equivalently, that c = b+1. So give this value to c and see
if it works.]
Let c = b+1. Then c is an integer and so 4c?1 is in Z by definition of Z. Also, by substitution,
4s + 1 = 4(2r ? 1) + 1 = 8r ? 4 + 1 = 8r ? 3 = x, and hence x satisfies the definition to be in
Z [as was to be shown].