0
$\begingroup$

I came across the following three statements about relations. I understand why the statements are true, but I am not sure how to demonstrate them mathematically.

In the following, $A,B$ are sets and $R$ is a relation.

(i) $R[A \cup B] = R[A] \cup R[B]$

Proof: $A \cup B$ consists of elements both in $A$ and $B$, and thus $R[A \cup B]$ consists of the image of $A \cup B$ under the relation $R$. Both common and uncommon elements of $A$ and $B$ will be present in $A \cup B$, and thus their corresponding images will appear in $R[A \cup B]$.

On the other hand, $R[A] \cup R[B]$ will consists of the elements of $R[A]$ and $R[B]$.

Since the union operation does not lead to loss of elements in a set, we will end up retaining all the common and uncommon elements of the images of sets $A, B$ and $A \cup B$. Thus, ensuring that the left and right hand sides are equal.

(ii) $R[A \cap B] \subseteq R[A] \cap R[B]$

Proof: The intersection operation can lead to loss of elements, i.e. elements that are not common in the two sets. Thus the $A \cap B$ can be an empty set. But the images of $R[A]$ and $R[B]$ can have common elements even whem $A$ and $B$ themselves do not have common elements. Thus the set $R[A] \cap R[B]$ will have elements that are images of the common elements of $A$ and $B$, and also the common images of the uncommon terms of $A$ and $B$. Thus, $R[A \cap B]$ will be a subset of $R[A] \cap R[B]$.

(iii) $R[A - B] \supseteq R[A] - R[B]$

Proof: The operation can lead to loss of elements. Thus the $A - B$ can be an empty set. But the images of $R[A]$ and $R[B]$ can have common elements even when $A$ and $B$ themselves do not have common elements. Thus the set $R[A] - R[B]$ will not have elements that are the common images of the uncommon elements of $A$ and $B$. On the other hand $R[A-B]$ will maintain those common images of the uncommon elements of $A$. Thus, $R[A] -R[B]$ will be a subset of $R[A-B]$.

For (ii) and (iii) the "subset of" and "superset of" relations will become equality when the $R$ becomes mapping.

I would like to be able to write the above proofs mathematically. How could I do so?

$\endgroup$
3
  • $\begingroup$ Is R a function? $\endgroup$ Commented Jul 29, 2014 at 15:28
  • $\begingroup$ Based on the title, I think we can safely take $R$ to be a relation on the respective sets. $\endgroup$ Commented Jul 29, 2014 at 15:31
  • $\begingroup$ Sorry about that. I have edited the question to make it more clear. Hope this helps. $\endgroup$ Commented Jul 29, 2014 at 15:34

1 Answer 1

Reset to default
2
$\begingroup$

To show $R[A \cup B] = R[A] \cup R[B]$ for a relation $R \subset X \times Y$, $A,B \subset X$, we have to show two inclusions.

So take any $y \in R[A \cup B]$; this means that there exists $x \in A \cup B$ such that $(x,y) \in R$. Then either $x \in A$, and then $y \in R[A]$, or $x \in B$ and then $y \in R[B]$. In either case $y \in R[A] \cup R[B]$, as required. So $R[A \cup B] \subseteq R[A] \cup R[B]$.

Reversely, take $y \in R[A] \cup R[B]$. Then $y \in R[A]$ or $y \in R[B]$. In the former case there is some $x \in A$ with $(x,y) \in R$, and in the latter there is some $x \in B$ with $(x,y) \in R$. In either case, $x \in A \cup B$, so $y \in R[A \cup B]$. So $R[A] \cup R[B] \subseteq R[A \cup B]$.

The other cases are handled similarly, but we only have to show one inclusion..

$\endgroup$
1
  • $\begingroup$ Thank you. That is very clear. $\endgroup$ Commented Jul 29, 2014 at 18:01

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.