# Notes II: Sets and Functions: problems and solutions

Let $f: X \rightarrow Y$, let $A \subseteq X$, let $B \subseteq Y$. Then,

$f(A) = \{f(x): x \in A \}$

$f^{-1}(B) = \{ x: f(x) \in B\}$

I. The main properties of the first set mapping are:

1a) $f(\phi) = \phi$, $f(X) \subseteq Y$

1b) $A_{1} \subseteq A_{2} \Longrightarrow f(A_{1}) \subseteq A_{2}$

1c) $f(\bigcup_{i}A_{i}) = \bigcup_{i}f(A_{i})$

1d) $f(\bigcup_{i}A_{i}) \subseteq \bigcap_{i} f(A_{i})$

1a: obvious by definition of f(A) or f.

1b: obvious by definition of f

1c: Let $x_{0} \in \bigcup_{i}A_{i}$ so that for some one i we have $f(x) \in f(A_{i})$. That is, $f(\bigcup_{i}A_{i}) \subseteq \bigcup_{i}f(A_{i})$. Reversing the arguments, we get the other subset relation. So that $f(\bigcup_{i}A_{i}) = \bigcup_{i}f(A_{i})$. The image of the union is the union of images.

1d: Let $x_{0} \in \bigcap_{i}A_{i}$ so that $x_{0}$ belongs to each $A_{i}$. So that LHS is clearly a subset of $\bigcap_{i}f(A_{i})$.

II) Now, we want to verify the following useful/famous relations of the second set mapping:

2a) $f^{-1}{(\phi)} = \phi$, $f^{-1}(Y) = X$

2b) $B_{1} \subseteq B_{2} \Longrightarrow f^{-1}(B_{1}) \subseteq f^{-1}(B_{2})$

2c) $f^{-1}(\bigcup_{i}B_{i}) = \bigcup_{i}f^{-1}(B_{i})$

2d) $f^{-1}(\bigcap_{i}B_{i}) = \bigcap_{i}f^{-1}(B_{i})$

2e) $f^{-1}(B^{'}) = f^{-1}(B)^{'}$

Answer 2c: Let $y_{0}$ belong to at least one $B_{i}$ so that $x_{0} = f^{-1}(y_{0}) = f^{-1}(B_{i})$ for some i. In other words, $f^{-1}(\bigcup_{i}B_{i}) = \bigcup_{i}f^{-1}(B_{i})$

TPT: $f^{-1}(B^{'}) = f^{-1}(B)^{'}$.

Let $y_{0} \in f^{-1}(B^{'})$.

Hence, $f(y_{0}) \in B^{'}$.

Hence, $f(y_{0}) \in U-B$, where U is the universal set

Hence, $f(y_{0}) \in U-f(A)$

Hence, $f(y_{0}) \in U-B$

Hence, $f(y_{0}) \in U-f(A)$

Hence, $f(y_{0}) \in (f(A))^{'}$

Hence, $y_{0} \in f^{-1}(B)^{'}$. Hence, $f^{-1}(B^{'}) \subseteq f^{-1}(B)^{'}$

Reversing the arguments proves the other subset inequality.

Hence, $f^{-1}(B^{'}) = f^{-1}(B)^{'}$. QED.

More Problems :

A) Two mappings $f: X \rightarrow Y$ and $g: X \rightarrow Y$ are said to be equal (and we write them as f=g) if $f(x) = g(x)$ for every x in X. Let f, g, and h be any three mappings of a non-empty set X into itself, and now prove that the multiplication of mappings is associative in the sense that $(fg)h = f(gh)$.

Solution A:

Let $f: X \rightarrow X$, $g: X \rightarrow X$, and $h: X \rightarrow X$ be any three mappings of X into itself. Let $x_{0} \in X$ and let $h(x_{0}) = x_{1} \in X$. Now, we know that $((fg)h)(x)= (fg)(h(x))$. So that now we want to find $(fg)(x_{1}) = f(g(x_{1})) = f(x_{2})$ assuming $g(x_{1}) \in x_{2} \in X$.

Now, on the other hand, $(f(gh))(x)$ means $(f)((gh)(x)) = f(g(h(x_{0})) = f(g(x_{1}))=f(x_{2})$ just as in LHS. QED.

B) Let X be a non-empty set. The identity mapping $i_{X}$ on X is the mapping of X onto itlsef defined by $i_{X}(x)=x$ for every x. Then, $i_{X}$ sends each element of the set X to itself; that is, leaves fixed each element of X. Prove that $fi_{X}= i_{X}f=f$ for any mapping f of X into itself. If f is one-to-one onto, so that its inverse $f^{-1}$ exists, show that $ff^{-1} = f^{-1}f=i_{X}$. Prove further that $f^{-1}$ is the only mapping of X into itself which has this property; that is, show that if g is a mapping of X into itself such that $fg=gf=i_{X}$, then $g=f^{-1}$. Hint: $g=gi_{X}=g(ff^{-1})=(gf)f^{-1} = i_{X}f^{-1}=f^{-1}$, or

$g=i_{X}g=(f^{-1}f)g=f^{-1}(fg) = f^{-1}i_{X}=f^{-1}$

B(i) TPT: $fi_{X}=i_{X}f=f$ for any mapping f of X into itself. Proof: Consider $x_{0}\in X$ and such that $f(x_{0}) = x_{1}$. Hence, $fi_{X}(x_{0}) = f(i_{X}(x_{0}))=f(x_{0}) = x_{1} \in X = f(x_{0})$. Now, on the other $(i_{X}f)(x_{0}) = i_{X}(f(x_{0}))=i_{X}(x_{1})= x_{1}$ also. QED.

B(ii): Let f be one-to-one onto such that $f: X \rightarrow X$. Hence, $f^{-1}$ exists. Also, $f^{-1}: X \rightarrow X$. Let $f(x_{0}) = x_{1} \in X$. Hence, by definition and because $f^{-1}$ is also one-to-one and onto, $f^{-1}(x_{1})=x_{0}$. Hence, clearly, $ff^{-1} = f^{-1}f=i_{X}$. QED.

B(iii) : Prove that such a $f^{-1}$ is unique.

Solution to B(iii): Let there be another function g such that $gf=fg=i_{X}$. Also, we have $ff^{-1}=f^{-1}f=i_{X}$. Use the hint ! 🙂 QED.

Question C:

Let X and Y be non-empty sets and f a mapping of X into Y. Prove the following: (i) f is one-to-one if and only if there exists a mapping g of Y into X such that $gf=i_{X}$ (ii) f is onto if and only if there exists a mapping h of Y into X such that $fh=i_{X}$.

Solution C(i) : Given $f: X \rightarrow Y$ such that if $x_{0} \neq x_{1}$, then $f(x_{0}) \neq f(x_{1})$. Now, we want a mapping $g: Y \rightarrow X$ such that $gf=i_{X}$. Let us construct a g such that $g(y_{0})=x_{0}$ and $g(y_{1}) = x_{1}$. Then, $(gf)(x_{0}) = g(f(x_{0}))=g(y_{0})=x_{0}$. Similarly, $gf(x_{1})=x_{1}$. Here, we have assumed that $f(x_{0})=y_{0}$ and $f(x_{1})=y_{1}$. So, knowing f to be one-to-one, we can explicitly construct a mapping g such that $g: Y \rightarrow X$ and $gf=i_{X}$. QED. On the other hand, let it be given that X and Y are two non-empty sets, that $f: X \rightarrow Y$ and $g: Y \rightarrow X$ such that $gf=i_{X}$. That is, if some $x^{'} \in X$, then we have $(gf)(x^{'}) = i_{X}(x^{'})=x^{'}$. That is, $g(f(x^{'})) = x^{'}$. This forces, if $f(x^{'}) = y^{'}$, then $g(y^{'})=x^{'}$. Now, if there be an element $x^{''} \neq x^{'}$, it will force $f(x^{''})=y^{''} \neq x^{'}$. Hence, different inputs give rise to different outputs and so f is one-to-one. QED.

Solution C(ii) : Given $f: X \rightarrow Y$ and f is onto, that is, $f(X) = Y$. We want to show a function $h: Y \rightarrow X$ such that $fh=i_{X}$. Since $f(X)=Y$, with X as domain, Y as codomain equal to range, f is one-to-one, onto. So $h=f^{-1}$. QED.

Question D:

Let X be a non-empty set and f a mapping of X into itself. Show f is one-to-one onto if and only there exists a mapping g of X into itself such that $gf=fg=i_{X}$. If there exists a mapping g with the property, then there is one and only one such mapping. Why?

Solution D: From previous question, C we are done.

Question E:

Let X be a non-empty set, and let f and g be one-to-one mappings of X onto itself. Show that fg is also a one-to-one mapping of X onto itself and that $(fg)^{-1}=g^{-1}f^{-1}$.

HW. Hint: consider the action of the functions on each element.

Question F:

Let X and Y be non-empty sets and f a mapping of X into Y. If A and B are, respectively, subsets of X and Y, prove the following:

(a) $ff^{-1}(B) \subseteq B$, and $ff^{-1}(B)=B$ is true for all B if and only if f is onto.

(b) $A \subseteq f^{-1}f(A)$, and $A = f^{-1}f(A)$ is true for all A if and only if f is one-to-one.

(c) $f(A_{1} \bigcap A_{2}) = f(A_{1}) \bigcap f(A_{2})$ is true for all $A_{1}$ and $A_{2}$ if and only if f is one-to-one.

(d) $f(A)^{'} \subseteq f(A^{'})$ is true for all A if and only if f is onto.

(e) If f is onto — so that, $f(A)^{'} \subseteq f(A^{'})$ is true for all A — then, $f(A)^{'}=f(A^{'})$ is true for all A if and only if f is also one-to-one.

Solution Fa: Put $B=Y$, so that f is onto. To prove the other subset relationship, simply reverse the arguments.

Solution Fb:

We need to apply the definition that different inputs give rise to different outputs.

;

😦 I hope to blog later)

:

Solution Fc:

It certainly implies that $A_{1} \bigcap A_{2} \neq \phi$.

:

(I hope to blog later).

Solution Fd:

Given that $f: X \rightarrow Y$ and $A \subseteq X$ and $B \subseteq Y$. Then, $f(A)^{'}$ is $Y-f(A)$, that is, $Y-B$, that is $B^{'}$, that is, $f(B^{'})$. Put $A=X$, then f is onto. Now, $f(X)^{'} \subseteq f(X^{'})$, that is, $Y-f(X) \subseteq f(\phi)$. This implies $Y=f(X)$. To prove the other subset relationship, simply reverse the arguments. QED.

Regards,

Nalin Pithwa.

This site uses Akismet to reduce spam. Learn how your comment data is processed.