Define sets A and B as follows: A = {n ? Z | n = 8r ? 3 for some integer r} and B = {m ? Z | m = 4s + 1 for some integer s}.

Question

(a) Is A ? B?
(b) Is B ? A?

Answer 1

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