Define sets A and B as follows:

Question

$A = \{n ∈ Z\mid∃r ∈ Z n = 8r − 3\}$

$B = \{m ∈ Z\mid∃s ∈ Z m = 4s + 1\}$

(a) Is $A ⊆ B$ ?

(b) Is $B ⊆ A$ ?

I don't know how to begin this question, or finish it. I know that I either have to give a proof if the answer is yes, or a counterexample if the answer is no.

Answer 1

Let's consider part a) first. Suppose that $x \in A$. Then, there exists an $r \in \mathbb{Z}$ such that:

$$x = 8r-3$$

We need to show that either $x \in B$ or $x \notin B$. Let us rewrite the expression for $x$ above as follows:

$$x = 8r-3 = 8r-4+1 = 4(2r-1)+1$$

Define $s = 2r-1$. Since it is the case that $s \in \mathbb{Z}$, it follows that $x \in B$. The reason for that is simple: if $x \in B$, then we must find an $s \in \mathbb{Z}$ so that $x = 4s+1$. If we are able to do that, then we're gucci.

In this case, we were guaranteed the existence of $r \in \mathbb{Z}$ because we started off assuming that $x \in A$. So, we used the existence of $r$ to prove the existence of $s$. That's the crux of the reasoning used.

This proves that $A \subset B$.

Can you do part b) on your own?

Answer 2

$A\subseteq B$ is the case iff $a\in A$ implies $a\in B$ for all integers $a$. This is equivalent to saying that, for all $r\in\Bbb{Z}$ there exists some $s\in\Bbb{Z}$ such that

$8r-3=4s+1$

Well, if we set $s=2r-1$, which is clearly an integer, we get:

$8r-3=4(2r-1)+1=8r-4+1=8r-3$

Therefore $A\subseteq B$. To show that (b) is not the case, we can construct a counterexample, i.e., an $b\in B$ such that $b\notin A$. Consider the integer 9. We have

$9=4(2)+1 \iff 9\in B$.

But

$9=8r-3\iff 12=8r\iff r=1.5$.

As $1.5\notin \Bbb(Z)$, $1.5\notin A$. Hence, (b) cannot hold true.