### Archive

Archive for the ‘Functions’ Category

## 1.2 Exercise 6

This was a really easy problem, that ends the section on functions in Munkres's text.  The next fifteen problems deal with relations, and I am finding them immensely interesting.

"Let $f : \mathbb R \rightarrow \mathbb R$ be the function $f(x) = x^3 - x$.  By restricting the domain and range of $f$ appropriately, obtain from $f$ a bijective function $g$.  Draw the graphs of $g$ and $g^{-1}$. (There are several possible choices for $g$.) "

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 21.)

----------

SOLUTION

As an example, $g: (-\infty, -1) \rightarrow \mathbb{R}^{-}$ with rule $g(x) = x^3 -x$ is bijective.

Categories:

## 1.2 Exercise 5

After working on these problems all week, I'm not sure I can keep up 1 problem a day.  I'll try to post as many as possible in the span of a week, however.  I'm definitely taking a break over the weekend!

I really like this problem because it was an eye-opener when I first encountered it on the subtleties of inverse mappings.  I've seen it several places, it is a classic exercise on functions.  Here's the problem as taken from Munkres's text:

"In general, let us denote the identity function for a set $C$ by $i_C$.  That is, define $i_C : C \rightarrow C$ to be the function given by the rule $i_C(x) = x$ for all $x \in C$.  Given $f : A \rightarrow B$, we say that a function $g : B \rightarrow A$ is a left inverse for $f$ if $g \circ f = i_A$; and we say that $h : B \rightarrow A$ is a right inverse for $f$ if $f \circ h = i_B$.

(a) Show that if $f$ has a left inverse, $f$ is injective; and if $f$ has a right inverse, $f$ is surjective.

(b) Give an example of a function that has a left inverse but no right inverse.

(c) Give an example of a function that has a right inverse but no left inverse.

(d) Can a function have more than one left inverse? More than one right inverse?

(e) Show that if $f$ has both a left inverse $g$ and a right inverse $h$, then $f$ is bijective and $g=h=f^{-1}$."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 21.)

-----------

SOLUTION

(a)

$f$ not injective means that $f(a) = f(a')$ for $a \neq a'$.  The left inverse exists by hypothesis, and so when we apply it to $f(a)$, by definition $(g \circ f)(a) = a$, and on $f(a')$ it is $(g \circ f)(a') = a'$.  But, being a function, the left inverse must map $f(a) = f(a') = b \in B$ to the same single element in $A$, which would mean $a = a'$. We've reached a contradiction in the argument, so $f$ is injective.

Suppose $f$ is not surjective.  This means there exists a subset of elements $B_{*} \subset B$ that do not map back to themselves via $f$, but then this contradicts the fact that all elements of $B$ come back to themselves after applying $h$ and then $f$. Thus, $f$ must therefore be surjective.

(b)

Many functions are injective but not surjective, say $f: \mathbb{R}^{+} \rightarrow \mathbb{R}$ with rule $\{(x,x) \vert x \in \mathbb{R}\}$.

(c)

Likewise we can find many functions that are surjective but not injective, say $f : [0, \pi] \rightarrow [0,1]$ with rule $\{ (x, sin(x)) \vert x \in \mathbb{R}\}$

(d)

More than one left inverse: yes.  Here's an example: let $f : \{0,1\} \rightarrow \{0, 1, 2\}$ with rule $\{ (0,1) ; (1,2) \}$.  Define $g : \{0,1, 2\} \rightarrow \{0, 1 \}$ by $\{ (0,0) ; (1,0) ; (2,1) \}$.  Another could be $g': \{0,1, 2\} \rightarrow \{0, 1 \}$ by $\{(0,1) ; (1,0) ; (2,1)\}$.  The important thing to notice is that every element of the domain of $f$ is returned to itself after applying $f$ and then $g$ or $g'$.

More than one right inverse: yes.  Consider $f : \{0,1\} \rightarrow \{0\}$ with rule $\{ (0,0) ; (1,0) \}$, and define $h: \{0\} \rightarrow \{0,1\}$ with rule $\{ (0,0) \}$ or $h': \{0\} \rightarrow \{0,1\}$ with rule $\{ (0,1) \}$.  Notice that starting from the domain $B$, applying $h$ or $h'$ on zero, then $f$, returns us to zero: the composition of either function does not move the element in its path to $A$ and back.

(e)

Since $f$ has both a left inverse and a right inverse, it is both injective and surjective, and hence bijective.

To show that $g = h$, pick any element $b \in B$ and apply $h$$h$ is defined on all $B$ (in fact on the image of $f$ by surjectivity, and specifically never outside it).  Furthermore, since $f$ is injective, there is only one way to reach the element $h(b) = a \in A$.  Next pick the same element $b \in B$ and apply $g$.  Since $f$ is surjective, there is no risk of picking a $b$ that is defined to map back to $A$ in the same way as another $b'$-not-in-the-image-of-$f$ under $g$. There is only one way $g$ can map that $b$ into $A$ by the injectivity of $f$, so $g(b) = a$. Since $h$ and $g$ both map to the same element in $A$ for all $b \in B$, $g = h$.  Call this the inverse of $f$, and denote it by $f^{-1}$.  (Note this is different than the preimage of f which uses the same symbol).

Alternatively, by the identity property of equality, $g \circ f \circ h = g \circ f \circ h$.  By associativity of composition of functions, $(g \circ f) \circ h = g \circ (f \circ h)$.  This in turn reduces to $(i_A) \circ h = g \circ (i_B)$, and so $h = g$.

Categories:

## 1.2 Exercise 4

I've skipped Exercise 3 because it was basically a repeat of Exercise 2, only requiring induction.  There are plenty of induction-related proofs in the next section, but perhaps I'll return to it if the more interesting problems are depleted.

"Let $f : A \rightarrow B$ and $g : B \rightarrow C$.

(a) If $C_0 \subset C$, show that $(g \circ f)^{-1}(C_0) = f^{-1}g^{-1}(C_0)$.

(b) If $f$ and $g$ are injective, show that $g \circ f$ is injective.

(c) If $g \circ f$ is injective, what can you say about injectivity of $f$ and $g$?

(d) If $f$ and $g$ are surjective, show that $g \circ f$ is surjective.

(e)  If $g \circ f$ is surjective, what can you say about surjectivity of $f$ and $g$?

(f) Summarize your answers to (b)-(e) in the form of a theorem."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 21.)

--------------

SOLUTION

(a)

Pick a $c \in C_0$ with defined preimage in $A$ under $(g \circ f)^{-1}$.  In other words, a $c$ such that $(g \circ f)^{-1}(c) \in (g \circ f)^{-1}(C_0)$ (we need a defined preimage since $(g \circ f)$ may not be surjective).  Now, such a $c$ must have arrived at set $B$, and therefore must have a defined preimage in $B$, as $g^{-1}(c)$.  In turn this $g^{-1}(c)$ must arrive in $A$ via $f^{-1}$, as $(f^{-1} \circ g^{-1}) (c) \in (f^{-1} \circ g^{-1})(C_0)$.  This shows the first inclusion, that $(g \circ f)^{-1}(C_0) \subset (f^{-1} \circ g^{-1})(C_0)$.

Pick a $c$ with defined preimage in $B$ and in $A$ via $g^{-1}$ and $f^{-1}$ respectively. I.e., pick $c \in C_0$ so that $(f^{-1} \circ g^{-1})(c) \in (f^{-1} \circ g^{-1})(C_0)$.  This $c$ will have a preimage in $A$ via $(g \circ f)^{-1}$, since if it were undefined in this inverse map, it would have been undefined at either the map $g^{-1}$ or the map $f^{-1}$, but this is not the case.  In other words, $(g \circ f)^{-1}(c) \in (g \circ f)^{-1}(C_0)$.  This shows the second inclusion, that $(g \circ f)^{-1}(C_0) \supset (f^{-1} \circ g^{-1})(C_0)$.

Finally, $(g \circ f)^{-1}(C_0) = (f^{-1} \circ g^{-1})(C_0)$ $\Box$.

(b)

Suppose not (indirect proof), that $g \circ f$ is not injective.  This means that there exists $a$ and $a' \in A$ such that $(g \circ f)(a) = (g \circ f)(a')$.  But this means that we arrived at such element of $C$ by landing on the same element at $B$, meaning $f(a) = f(a')$ (which contradicts the injectivity of $f$), or by a different element of $B$, but no question at the same element after applying the map $g$, so that $g(f(a)) = g(f(a'))$.  But this contradicts the injectivity of $g$.  We must have been wrong that $(g \circ f)(a)$ is not injective, and so it must be  $\Box$.

(c)

Rephrasing the question, we want to find out  $g \circ f$ injective $\Rightarrow$ $f$ injective and, or, neither $g$ injective.  Suppose $f$ is not injective (indirect proof), and so there are elements $a$ and $a' \in A$ that map to the same element in $B$, as $f(a) = f(a')$.  Next apply $g$, so that $g(f(a)) = g(f(a'))$.  We started from two different elements in $A$, and we've now shown the map $g \circ f$ cannot be injective, a contradiction.  $f$ must therefore be injective.  Next suppose $g$ is not injective, and pick $b \neq b' \in B$, so that $g(b) = g(b')$.  If such $b, b'$ are in the image of $f$, and since $f$ is injective by the previous argument, then $b = f(a)$ and $b' = f(a')$ with $a \neq a' \in A$.  Starting from two different elements of $A$, the map $g \circ f$ cannot be injective, a contradiction. However, if, say, $b$ is not in the image of $f$, $g \circ f$ can still be one-to-one.  Thus we cannot tell that $g$ is or is not injective.

(d)

Arguing this by contradiction (indirect proof) makes the proof a very simple task.  If the map $g \circ f$ is not surjective, either $g$  is not surjective because all the elements of $B$ do not hit all elements of $C$, or if $g$ is surjective, then $f$ is not, hitting elements of $B$ for which the image under $g$ is a proper subset of $C$. (Note that those elements not in the image of $f$ in $B$ could still hit all the rest of $C$, making $g$  surjective) $\Box$.

(e)

Rephrasing, we want to find out $g \circ f$ surjective $\Rightarrow$ $f$  surjective and, or, neither $g$  surjective.  It's easiest if we start with the map $g$.  If $g$ is not surjective, there is no way $g \circ f$ can be, because we've got to stop at $B$ and take the map $g$ on our way to $C$.  Thus, $g \circ f$  surjective $\Rightarrow$  $g$ surjective. $f$  not surjective means only the image of $f$ in $B$ will map to $C$ under composition of functions. But then either such image under $g$ hits all of $C$ (no contradiction), or it doesn't (contradiction), we cannot tell.  So the behavior of $f$ is not particularly illuminating. $\Box$.

(f)

Summarizing:

$f$ and $g$ injective $\Rightarrow$  $g \circ f$ injective

$f$ and $g$ surjective $\Rightarrow$  $g \circ f$ surjective

$g \circ f$ injective $\Rightarrow$ $f$ injective

$g \circ f$ surjective $\Rightarrow$  $g$ surjective

Categories:

## 1.2 Exercise 2

"Let $f : A \rightarrow B$  and let $A_i \subset A$  and $B_i \subset B$  for $i = 0$  and $i = 1$.  Show that $f^{-1}$  preserves inclusions, unions, intersections, and differences of sets:

(a) $B_0 \subset B_1 \Rightarrow f^{-1}(B_0) \subset f^{-1}(B_1)$

(b) $f^{-1}(B_0 \cup B_1) = f^{-1}(B_0) \cup f^{-1}(B_1)$

(c) $f^{-1}(B_0 \cap B_1) = f^{-1}(B_0) \cap f^{-1}(B_1)$

(d) $f^{-1}(B_0 \setminus B_1) = f^{-1}(B_0) \setminus f^{-1}(B_1)$

Show that $f$  preserves inclusions and unions only:

(e) $A_0 \subset A_1 \Rightarrow f(A_0) \subset f(A_1)$

(f)  $f(A_0 \cup A_1) = f(A_0) \cup f(A_1)$

(g) $f(A_0 \cap A_1) \subset f(A_0) \cap f(A_1)$ ; show that equality holds if $f$  is injective.

(h) $f(A_0 \setminus A_1) \supset f(A_0) \setminus f(A_1)$ ; show that equality holds if $f$  is injective."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 20.)

NB:  A word about notation.  $f^{-1}(B_i)$ in this context is the preimage of the subset $B_i$ of $B$, and can therefore return a set (i.e., it is not a function), as will be seen presently.

-------------

SOLUTION

(a)

Case $B_0 \subsetneq B_1$

Pick $b \in B_0$ such that the preimage in the domain $A$ is defined ($f$ may not be surjective or even one-to-one).  Apply $f^{-1}$ on such, and then $f^{-1}(b) \in f^{-1}(B_0)$.  Since $b \in B_0$, and it also belongs to $B_1$ by (proper) inclusion, $f^{-1}(b) \in f^{-1}(B_1)$.  Now pick $b \notin B_0, b \in B_1$, with defined preimage in $A$.  Apply $f^{-1}$.  Then $f^{-1}(b) \notin B_0, f^{-1}(b) \in B_1$.  Thus $f^{-1}B_0 \subsetneq f^{-1}(B_1)$.

Case $B_0 = B_1$

It is easy to see that, by arguing similarly, $f^{-1}(B_0) = f^{-1}(B_1)$.

Thus $B_0 \subset B_1 \Rightarrow f^{-1}(B_0) \subset f^{-1}(B_1)$. $\Box$

(b)

Case $f^{-1}(B_0 \cup B_1) \subset f^{-1}(B_0) \cup f^{-1}(B_1)$

Pick a $b \in B_0$, for which the preimage is deifned in $A$$f^{-1}(b) \in f^{-1}(B_0) \in f^{-1}(B_0) \cup f^{-1}(B_1)$.  Pick $b \in B_1$$f^{-1}(b) \in f^{-1}(B_1) \in f^{-1}(B_0) \cup f^{-1}(B_1)$.  We have covered every $b$ in $B_0 \cup B_1$, which preimage is $f^{-1}(B_0 \cup B_1)$.

Case $f^{-1}(B_0) \cup f^{-1}(B_1) \subset f^{-1}(B_0 \cup B_1)$

Pick a $b \in B_0$, well defined in $A$.  This element, under $f^{-1}$, belongs to $f^{-1}(B_0)$ and is therefore in $f^{-1}(B_0) \cup f^{-1}(B_1)$.  Since $b \in B_0$, it also belongs to $B_0 \cup B_1$, and has a preimage in $f^{-1}(B_0 \cup B_1)$.

Pick $b \in B_1$, well defined in $A$$f^{-1}(b) \in f^{-1}(B_1)$.  Such $b$ also belongs to $B_0 \cup B_1$, and therefore $f^{-1}(b) \in f^{-1}(B_1 \cup B_0)$.

We've now covered every $b$ in $f^{-1}(B_0) \cup f^{-1}(B_1)$, and we are done.

Thus $f^{-1}(B_0 \cup B_1) = f^{-1}(B_0) \cup f^{-1}(B_1)$. $\Box$

(c)

Case $f^{-1}(B_0 \cap B_1) \subset f^{-1}(B_0) \cap f^{-1}(B_1)$

Pick $b \in B_0 \cap B_1$ with a defined preimage in $A$.  Since it is in $B_0 \cap B_1$, the preimage lies in $f^{-1}(B_0 \cap B_1)$.

Such a $b$ belongs to $B_0$, and so its preimage is in $f^{-1}(B_0)$.  It also lies in $B_1$, and so its preimage lies also in $f^{-1}(B_1)$.  In other words, its preimage lies in $f^{-1}(B_0) \cap f^{-1}(B_1)$.

Case $f^{-1}(B_0) \cap f^{-1}(B_1) \subset f^{-1}(B_0 \cap B_1)$

Pick $b \in B_0$, with defined preimage in $f^{-1}(B_0)$.  Pick $b' \in B_1$ with defined preimage in $f^{-1}(B_1)$.  take the intersection $f^{-1}(B_0) \cap f^{-1}(B_1)$.

A $b$ mapping to the intersection has a preimage that maps both to $f^{-1}(B_0)$ and $f^{-1}(B_1)$.  In other words, such a $b \in B_0$ and $b \in B_1$, or $B_0 \cap B_1$, so the preimage of $b$ lies also in $f^{-1}(B_0 \cap B_1)$.

Thus $f^{-1}(B_0 \cap B_1) = f^{-1}(B_0) \cap f^{-1}(B_1)$. $\Box$

(d)

Case $f^{-1}(B_0 \setminus B_1) \subset f^{-1}(B_0) \setminus f^{-1}(B_1)$

Pick $b \in B_0, b\notin B_1$, with well defined preimage in $f^{-1}(B_0 \setminus B_1)$.  Since $b \in B_0$, its preimage lies in $f^{-1}(B_0)$.  But it cannot lie in $B_1$, so therefore its preimage cannot lie in $f^{-1}(B_1)$.  In other words, the preimage of such a $b$ is in $f^{-1}(B_0) \setminus f^{-1}(B_1)$.

Case $f^{-1}(B_0) \setminus f^{-1}(B_1) \subset f^{-1}(B_0 \setminus B_1)$

Pick a $b$ with preimage in $f^{-1}(B_0) \setminus f^{-1}(B_1)$.  Such a $b$ has a preimage in $f^{-1}(B_0)$, but not in $f^{-1}(B_1)$.  This means that such a $b$ must belong to $B_0$, but not $B_1$: $b \in B_0, b \notin B_1$, or, in other words, $b \in B_0 \setminus B_1$.  Such a $b$ has a preimage in $f^{-1}(B_0 \setminus B_1)$.

Thus $f^{-1}(B_0 \setminus B_1) = f^{-1}(B_0) \setminus f^{-1}(B_1)$. $\Box$

(e)

Case $A_0 \subsetneq A_1$

Pick $a \in A_0$ and apply $f$.  Such $f(a) \in f(A_0)$. By inclusion, $a \in A_1$, and therefore $f(a) \in f(A_1)$.  Pick $a \notin A_0$ but $a \in A_1$.  Apply $f$.  Then $f(a) \notin f(A_0)$ but $f(a) \in f(A_1)$.  Thus $f(A_0) \subsetneq f(A_1)$.

Case $A_0 = A_1$

Pick $a \in A_0$ (and $a \in A_1$).  Then $f(a) \in f(A_0)$ and $f(a) \in f(A_1)$.  Thus $f(A_0) = f(A_1)$.

Therefore $f(A_0) \subset f(A_1)$. $\Box$

(f)

Same as (b) but arguing form the domain side.

(g)

Case $f(A_0 \cap A_1) \subset f(A_0) \cap f(A_1)$

Pick $a \in A_0 \cap A_1$ (with image $f(a) \in f(A_0 \cap A_1)$).  Now $a \in A_0$ means that $f(a) \in f(A_0)$, and $a \in A_1$ means $f(a) \in f(A_1)$, so such an $a$'s image is in $f(A_0) \cap f(A_1)$.

Case $f(A_0) \cap f(A_1) \subset f(A_0 \cap A_1)$ if $f$ is injective

$f$ is injective means that there is a unique $a$ that yields $b \in B$, in other words $f(a) = b$.  So pick $f(a) \in f(A_0) \cap f(A_1)$.  The $a$ that was picked necessarily belongs to $A_0$ in order that $f(a)$ be in $f(A_0)$ (i.e., there isn't another $a'$ outside or inside $A_0$ whose image is $f(A_0)$, due to injectivity), but it also must belong to $A_1$ so that $f(a)$ be in $f(A_1)$ (same argument here).  Therefore $a \in A_0 \cap A_1$, and the image of this $a$ belongs to $f(A_0 \cap A_1)$.

If the argument above isn't crystal clear, the contrapositive is also insightful: if $f(A_0) \cap f(A_1) \nsubseteq f(A_0 \cap A_1)$, $f$ is not injective.  Pick $b \in f(A_0) \cap f(A_1)$ that is not also in the image $f(A_0 \cap A_1)$.  In particular this means $f^{-1}(b) = a'$ and such $a' \in A_1, a' \notin A_0$, say.  But such a $b \in f(A_0)$ and $b \in f(A_1)$, in other words, $b = f(a) \in f(A_0), f(a)\in f(A_1)$ and this means that such an $a \in A_0$ and $a \in A_1$, or $a \in A_0 \cap A_1$. The only way to resolve this apparent contradiction is by letting $b = f(a') = f(a)$, and $f$ is not injective. $\Box$

(h)

Case $f(A_0 \setminus A_1) \supset f(A_0) \setminus f(A_1)$, or $f(A_0) \setminus f(A_1) \subset f(A_0 \setminus A_1)$

Pick $f(a) \in f(A_0), f(a) \notin f(A_1)$.  Since $f(a)$ belongs to the image $f(A_0)$, there exist elements collectively $a \in A_0$, and focus on them (other elements are not of interest because they are not in $A_0$).  Since $f(a)$ does not belong to $f(A_1)$, these $a \notin A_1$. Such $a$ exactly belong to $A_0 \setminus A_1$, and therefore $f(a)$ to $f(A_0 \setminus A_1)$.

Next we want to show that if $f$ is injective, $f(A_0 \setminus A_1) \subset f(A_0) \setminus f(A_1)$.  Since all $a$s uniquely map into $f(A)$, pick any $a \in A_0 \setminus A_1$, and apply $f$.  Such will lie in $f(A_0 \setminus A_1)$.  Since $a \in A_0$, and $a \notin A_1$, this implies $f(a) \in f(A_0)$ and $f(a) \notin f(A_1)$. $\Box$

Categories:

## 1.2 Exercise 1

"Let  $f : A \rightarrow B$. Let  $A_0 \subset A$  and  $B_0 \subset B$.

(a) Show that  $A_0 \subset f^{-1}(f(A_0))$  and that equality holds if  $f$  is injective.

(b) Show that  $f(f^{-1}(B_0)) \subset B_0$  and that equality holds if  $f$  is surjective."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 20.)

NB:  A word about notation.  $f^{-1}(B_i)$ in this context is the preimage of the subset $B_i$ of $B$, and can therefore return a set (i.e., it is not a function), as will be seen presently.

-----------------

SOLUTION

(a)

Case  $f$  is not injective

$f$  not injective over the domain $A$  implies there exist at least two  $a \in A$  for some  $b \in f(A)$. More to the point, for some $b \in f(A)$$f^{-1}(b) = \{a_1, a_2, ...\}$ where the cardinality of $\{a_1, a_2, ...\}$  is at least 2.

$\mathit{I.}$  Pick  $A_0 \subset A$  in such a way that  $A_0 \cap \{a_1, a_2, ...\}$ contains at least one element but not all.  Apply  $f$ on $A_0$, and then $b \in f(A_0)$.  Apply $f^{-1}$ on $f(A_0)$, but in so doing we are sure to apply  $f^{-1}$ on $b$.  Since $f^{-1}(b) = \{a_1, a_2, ...\}$ for which  $A_0$ contains some, but not all elements (the others which lie in  $A$), $f^{-1}(f(A_0)) \supset A_0$.  Here it is important to remember that we did not restrict  $f$  or  $r$ (the rule of f) to $A_0$, just $A$ to $A_0$.

* $\mathit{II.}$  Pick  $A_0 \subset A$  such that  $A_0 \cap \{a_1, a_2, ...\} = \{\}$ .  Then (a multivalued)  $b \notin f(A_0)$  and  $f$  is "locally" one-to-one.  In this case,  $f^{-1}(f(A_0)) = A_0$ .  (See  $f$  is injective below).

* $\mathit{III.}$  Pick  $A_0 \subset A$  such that  $A_0 \cap \{a_1, a_2, ...\} = \{a_1, a_2, ...\}$ .  In this case,   $f^{-1}(f(A_0)) = A_0$  also.

* $\mathit{IV.}$  Lastly, pick  $A_0 = A$ .    $f^{-1}(f(A_0)) = A_0$  in this case too because the function returns the whole domain.

NOTES: Starred statements (*) make sense because the inclusion " $\subset$ " is not a proper inclusion (we need to be careful with notation and follow Munkres's convention), and therefore both sets on either side of the symbol may be equal (in other words,  $f^{-1}(f(A_0)) = A_0$ ). For  $\mathit{III, IV}$, any multivalued  $b \in B_0$  falls via  $f^{-1}$  on  $A_0$.

Case $f$ is injective: If  $f$  is injective, then  $f^{-1}(f(A_0))=A_0$

Since there doesn't exist a  $b \in f(A) \vert f^{-1}(b) = \{a_1, a_2, ...\}$  for  $\Vert \{a_1, a_2, ...\} \Vert \geq 2$ , this implies that  $\forall b \in f(A)$$f^{-1}(b) = a$  and this  $a$  is unique.

Well, surjectivity is established vacuously because  $f(A_0)$  is defined as that set in the range  $B$  which is made to correspond with all elements of  $A_0$  (call it  $B_0$ ).

Thus  $f$  becomes bijective:  $\exists$  only one  $b \in B_0$  that corresponds to only one  $a\in A_0$ , and vice versa by definition of the rule of  $f$ .  So there exists an inverse function to  $f$ , and  $f(a) = b \iff a = f^{-1}(b)$.  Thus

$f(A_0) = B_0$

$f^{-1}(f(A_0)) = f^{-1}(B_0)$

$f^{-1}(f(A_0)) = A_0$     $\Box$.

(b)

Case $f$  is not surjective

$f$  not surjective over  $B$  means there is at least one  $b \in B$  such that  $f^{-1}$  is not defined (is null).  Let's denote this set by  $\{b_1, b_2, ... \}$  with cardinality  $\geq 1$.

$\mathit{I.}$  Pick  $B_0 \subset B$  in such a way that  $B_0 \cap \{b_1, b_2, ...\}$  contains at least one element and  $B_0 \setminus \{b_1, b_2, ...\}$  likewise contains at least one element.  Upon applying  $f^{-1}$  on  $B_0$ , we obtain elements in  $A_0$  (sometimes for some elements  $b \in B_0$  there may be many  $a \in A_0$  that correspond, since  $f^{-1}$  is not one-to-one), except for those elements  $B_0 \cap \{b_1, b_2, ...\}$  which by definition are undefined in  $A$ .  Applying  $f$  on such  $A_0$  returns those elements   $B_0 \setminus \{b_1, b_2, ...\}$ .  It seems clear that   $B_0 \setminus \{b_1, b_2, ...\} \subset B_0$  by definition of difference of sets, since   $B_0 \setminus \{b_1, b_2, ...\} = \{b \vert b \in B_0$ and $b \notin \{b_1, b_2, ...\}\}$.  Therefore  $f(f^{-1}(B_0)) \subset B_0$.

$\mathit{II.}$  As above, except  $B_0 \setminus \{b_1, b_2, ...\}$  can be empty.  Then the argument is as before, with  $B_0 \setminus \{b_1, b_2, ...\} = \{\} = f(f^{-1}(B_0))$  and  $\{\} \subset B_0$ is vacuously true.

Case $f$ is surjective

This argument is likewise as before, except the set of undefined values in  $B$  is null.  Then  $f(f^{-1}(B_0)) = B_0 \setminus \{\} = B_0$ , and the equality is established.   $\Box$

Categories: