Prove that if $A \subset B$ then $R[A] \subset R[B]$

Question

I have a question saying:

Prove that if $A \subseteq B$, then $R[A] \subseteq R[B]$

I am having some trouble getting a rigorous proof to me. Intuitively I can see how this is true, but I am struggling to prove this rigorously. So far I have:

$\forall x \in A$ it is true that $x \in B$. This implies that $(\forall y\in R[A]) x \in B$, as $(\forall y \in R[x] |x \in A)$ it is also true that $x\in B$. Therefore, $R[A] \subseteq R[B]$

I am aware there are probably many gaps in my logic but I am not sure where. Any hints or help would be greatly appreciated.

EDIT:

Thanks for your help. Is this now correct, or is there still more to do:

$\forall y \in R[A]$ there exist an $x$ such that $_xR_y$. This implies that $\forall y \in R[A]$ there exists an $x \in B$, as $\forall x\in A$ it is true that $x\in B$. Therefore, $y \in B$, and so $R[A] \subseteq R[B]$

Answer 1

Equivalent are:

• $y\in R[A]$
• $\langle x,y\rangle\in R$ for some $x\in A$

Since $A\subseteq B$ the second bullet implies that $\langle x,y\rangle\in R$ for some $x\in B$ or equivalently $y\in R[B]$.

Proved is not that $y\in R[A]\implies y\in R[B]$ or equivalently $R[A]\subseteq R[B]$.

Answer 2

I think you're misguided by all those $\forall$ symbols.

• $X$ is a set, $R$ is a relation on $X$;
• if $C$ is a subset of $X$, then $R[C]=\{y\in X: x\mathrel{R}y\text{, for some } x\in C\}$
• $A$ and $B$ are subsets of $X$.

Prove that, if $A\subseteq B$, then $R[A]\subseteq R[B]$.

Suppose $y\in R[A]$. Then there is $x\in A$ such that $x\mathrel{R}y$. Since $A\subseteq B$, we can say that $x\in B$. Therefore, by definition, $y\in R[B]$, because $x\mathrel{R}y$ and $x\in B$.

Answer 3

First off, to do this proof, you need to know and use what $\;y \in R[X]\;$, how it is defined.$% \require{begingroup} \begingroup \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\Ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} %$ Why is that? Because of the definition of $\;\subseteq\;$, which tells us that $$ \tag{0} R[A] \subseteq R[B] \;\equiv\; \langle \forall y :: y \in R[A] \;\then\; y \in R[B] \rangle$$so you need to know what $\;y \in R[X]\;$ means.

Since you say in a comment that $\;R[A]\;$ is "the image of the set $\;A\;$ under the relation $\;R\;$", presumably your definition is something like $$ \tag{1} y \in R[A] \;\equiv\; \langle \exists x :: x \in A \land (x,y) \in R \rangle $$ for every $\;y,R,A\;$.

Now we need to prove the right hand side of $\Ref{0}$, assuming $\;A \subseteq B\;$. Starting on the left of $\;\then\;$ and working towards the other side, we have for every $\;y,R,A,B\;$

$$\calc y \in R[A] \op\equiv\hint{definition $\Ref{1}$} \langle \exists x :: x \in A \;\land\; (x,y) \in R \rangle \op\then\hints{$\;x \in A \then x \in B\;$ by our assumption -- the only}\hint{way to use the only thing we know about $\;A\;$} \langle \exists x :: x \in B \;\land\; (x,y) \in R \rangle \op\equiv\hint{definition $\Ref{1}$} y \in R[B] \endcalc$$

And that completes the proof.

$% \endgroup %$