Answer to Question #96376 in Discrete Mathematics for Amritpal Singh

Question

Let f : A → B and let X,Y be subsets of the domain A. For any Z ⊆ A, define the image of Z under f to be the set f[Z] = {b ∈ B|∃z ∈ Z(f(z) = b)}.

a. Show that f[X ∪Y] = f[X]∪f[Y].

b. Give an example of a function f and subsets X,Y of its domain to show that it is not always true that f[X ∩Y] = f[X]∩f[Y].

Answer 1

a)Since $X\subset X\cup Y$ and $Y\subset X\cup Y$, we have $f[X]\subset f[X\cup Y]$ and $f[Y]\subset f[X\cup Y]$ , that is $f[X]\cup f[Y]\subset f[X\cup Y]$ .

Now we prove that $f[X\cup Y]\subset f[X]\cup f[Y]$ .

Indeed, if $f[X\cup Y]=\varnothing$, then $f[X\cup Y]\subset f[X]\cup f[Y]$.

Else let $u\in f[X\cup Y]$ , then there is $v\in X\cup Y$ such that $u=f(v)$ . So if $v\in X$, then $u=f(v)\in f[X]$ , and if $v\in Y$, then $u=f(v)\in f[Y]$ . In both cases we have $u\in f[X]\cup f[Y]$ .

Therefore $f[X\cup Y]\subset f[X]\cup f[Y]$ .

Since $f[X\cup Y]\subset f[X]\cup f[Y]$ and $f[X]\cup f[Y]\subset f[X\cup Y]$ , we have $f[X]\cup f[Y]= f[X\cup Y]$ .

b)Since $X\cap Y\subset X$ and $X\cap Y\subset Y$ , we have $f[X\cap Y]\subset f[X]$ and $f[X\cap Y]\subset f[Y]$ , that is $f[X\cap Y]\subset f[X]\cap f[Y]$ , but there are examples where $f[X\cap Y]\not\supset f[X]\cap f[Y]$ (Indeed, if $a\in f[X]\cap f[Y]$, then there are $b\in X$ and $c\in Y$ such that $a=f(b)=f(c)$. But it does not imply that there is $d\in X\cap Y$ such that $a=f(d)$). One of these examples is $f\colon \{1,2,3\}\to\{1,2\}$, where $f(1)=f(3)=1$ and $f(2)=2$ . We have $f[\{2\}]=\{2\}$, but $f[\{1,2\}]\cap f[\{3,2\}]=\{1,2\}$.