Let $R$ be a relation. Suppose that $A$ and $B$ are two sets. Then $R[A] \setminus R[B]$ $\subseteq$ $R[A\setminus B]$

Question

I know how to prove something is a subset of another but I’m not sure how to use the properties of the image to prove $x$ is not in the image of $B.$

Answer 1

Assuming that Graham's clarification is correct, the left-hand side $R[A] \setminus R[B]$ is the set of all $x$ such that $x \mathrel{R} y$ for some $y$ in $A$, but $x \mathrel{R} z$ is true for no $z \in B$.

The right-hand side $R[A\setminus B]$ is the set of all $x$ such that $x \mathrel{R} y$ for some $y$ that is in $A$ but not in $B$.

Can you take it from there?

Answer 2

It's just symbols.

Let $A,B\subset X$ then $R[A]= \{x\in X| (x,a)\in R,$ for some $a\in A\}$

so if $m \in R[A]\setminus R[b]$ then $m\in R[a]$ but $m\not \in R[b]$.

$m\in R[a]$ so there is an $a_m\in A$ so that $(m,a_m) \in R$ while $m\not \in R[b]$ so there is no $b\in B$ so that $(m,b)\in R$. Which means, as $(m,a_m)$ is in $R$ than $a_m$ can not be in $B$.

So $a_m\in A$ but $a_m \not \in B$ so $a_m \in A\setminus B$.

So there is an $a_m\in A\setminus B$ so that $(m,a_m)\in R$ so $m\in R[A\setminus B]$.

So $R[A]\setminus R[b]\subset R[A\setminus B]$

Answer 3

The $\def\R{\mathop{\rm R}}\R$-relation image of $A$ is the set of elements related by some element in $A$.

$$\R[A]=\{y : \exists x\in A~. \langle x, y\rangle \in R\}\\ =\{y:\exists x\in A~.~xRy\}$$

So for any $c$, we have $c\in\R[A]$ if and only if $\exists x~.(x\in A\wedge x\R c)$

Likewise for any $c$, we have $c\notin\R[B]$ if and only if $\forall x~.(x\in B\to \neg x\R c)$

---

You seek to show that $\R[A]\smallsetminus\R[B]\subseteq\R[A\smallsetminus B]$

Thus you need to show that $\forall z~(z\in\R[A]\smallsetminus\R[B]\to z\in\R[A\smallsetminus B])$, by the definition for subset.

---

I’m not sure how to use the properties of the image to prove $x$ is not in the image of $B$.

The subproof is a Proof of Negation. Assume that it is in $B$ aiming to derive a contradiction.

Use the above to help fill out the rest of this proof.

• Begin
  • Take any $c$
    • Assume that $c\in\R[A]\smallsetminus\R[B]$
    • $c\in\R[A]$ and $c\notin\R[B]$
    • $\exists x~.(x\in A\wedge x\R c)$ and $\forall x~.(x\in B\to \neg x\R c)$
      • Take some $a$ such that $a\in A$ and $a\R c$
        • Assume $a\in B$
        • :
        • :
        • Contradiction!
      • Therefore $a\notin B$
      • :
    • :
    • :
    • Thus $c\in\R[A\smallsetminus B]$
  • $c\in\R[A]\smallsetminus\R[B]\to c\in\R[A\smallsetminus B]$
• $\forall z~.(z\in\R[A]\smallsetminus\R[B]\to z\in\R[A\smallsetminus B])$
• $\R[A]\smallsetminus\R[B]\subseteq\R[A\smallsetminus B]$
• End.