Tao Analysis I - 3.4.5

Exercise 3.4.5

Let $f : X \to Y$ be a function from one set $X$ to another set $Y$ . Show that $f(f^{-1}(S))=S$ for every $S \subseteq Y$ if and only if $f$ is surjective. Show that $f^{-1}(f(S))=S$ for every $S \subseteq X$ if and only if $f$ is injective.

Show $f(f^{-1}(S))=S$ if and only if $f$ is surjective.

We need to prove both:

• $f(f^{-1}(S))=S \implies f$ is surjective.
• $f$ is surjective $\implies f(f^{-1}(S))=S$.

Let's start with $f(f^{-1}(S))=S \implies f$ is surjective. 

This is a statement of the form $A \implies B$, which we'll prove by showing the logically equivalent contrapositive $\neg B \implies \neg A$.

So, let's consider that $f$ is not surjective. This means there exists an $s \in S$ for some $S \subseteq Y$, such that $f(x) \neq s$ for all $x \in X$.

The inverse image $f^{-1}(S)$ is, by definition, the set $\{x \in X : f(x) \in S\}$.

If we apply $f$ to the elements of this set, we obtain the set $\{f(x) \in S\}$. However, this set cannot contain $s$ because $f(x) \neq s$ for all $x \in X$.  Therefore the set $\{f(x) \in S\}$ is not always $S$.

Therefore, $f$ not surjective implies $f(f^{-1}(S)) \neq S$.

This is logically equivalent to $f(f^{-1}(S))=S \implies f$ is surjective.

Now let's show $f$ is surjective $\implies f(f^{-1}(S))=S$.

To do this we need to show that under the assumption $f$ is surjective, both of the following are true:

• $f(f^{-1}(S)) \subseteq S$
• $S \subseteq f(f^{-1}(S))$

Let's start with the first $f(f^{-1}(S)) \subseteq S$. 

If $y \in f(f^{-1}(S))$ then $y=f(x)$ for some $x \in f^{-1}(S)$. By definition $f^{-1}(S)$ is the set $\{x \in X: f(x) \in S\}$. 

So if $f(x) \in S$ then $y=f(x) \in S$. That is, $y \in f(f^{-1}(S)) \implies y \in S$. This is equivalent to $f(f^{-1}(S)) \subseteq S$. Note we didn't need $f$ to be surjective for this.

Now let's consider $S \subseteq f(f^{-1}(S))$. 

Since $f$ is surjective, for every $y \in S$ there exists an $x \in f^{-1}(S)$ such that $f(x)=y$. 

Here, $x \in f^{-1}(S)$ gives us $y = f(x) \in f(f^{-1}(S))$. Hence, $y \in S \implies y \in f(f^{-1}(S))$. This is equivalent to $S \subseteq f(f^{-1}(S))$. 

Having shown both $f(f^{-1}(S)) \subseteq S$, and $S \subseteq f(f^{-1}(S))$, we can conclude $f(f^{-1}(S))=S$. This was under the assumption that $f$ is surjective, so we have $f$ is surjective $\implies f(f^{-1}(S))=S$.

Finally, having shown $f(f^{-1}(S))=S \implies f$ is surjective, and $f$ is surjective $\implies f(f^{-1}(S))=S$, we can say $f(f^{-1}(S))=S \iff f$ is surjective. $\square$

Show $f^{-1}(f(S))=S$ if and only if $f$ is injective.

We need to prove both:

• $f^{-1}(f(S))=S \implies f$ is injective.
• $f$ is injective $\implies f^{-1}(f(S))=S$.

Let's start with $f^{-1}(f(S))=S \implies f$ is injective.

This is a statement of the form $A \implies B$, which we'll prove by showing the logically equivalent contrapositive $\neg B \implies \neg A$.

So, let's consider $f$ is not injective. This means there exists an $x_1 \in X$ and $x_2 \in X$, where $x_1 \neq x_2$, such that $f(x_1)=f(x_2)$.

Let's consider the case $S=\{x_1\}$. If $f(x_1) = y \in Y$, then $f(S)=\{y\}$. Since $f(x_1)=f(x_2)$, we also have $y = f(x_2)$.

Now, the inverse image $f^{-1}(f(S))$ is the set $\{ x \in X : f(x) \in f(S) \}$, which here is $\{ x \in X : f(x) \in \{y\} \}$. 

Both $x=x_1$ and $x=x_2$ satisfy the membership condition of this set, and so this set is not $S=\{x_1\}$. 

We have shown that $f$ is not injective implies $f^{-1}(f(S)) \neq S$ for all $S \subseteq X$. This is logically equivalent to $f^{-1}(f(S))=S \implies f$ is injective.

Now let's show $f$ is injective $\implies f^{-1}(f(S))=S$.

To do this we need to show that under the assumption $f$ is injective, both of the following are true:

• $f^{-1}(f(S)) \subseteq S$
• $S \subseteq f^{-1}(f(S))$

Let's start with the first $f^{-1}(f(S)) \subseteq S$.

By definition of inverse images, $f^{-1}(f(S))$ is the set $\{x \in X: f(x) \in f(S)\}$. If $x'$ is a member of this set then $f(x') \in f(S)$.

But $f(S)$ is the set $\{f(x_s): x_s \in S\}$. This means there is an $x_s \in S$ such that $f(x_s) = f(x')$. 

Because $f$ is injective, this implies $x_s=x'$. This $x'$ is also in $S$.

We have shown $x \in f^{-1}(f(S)) \implies x \in S$. That is, $f^{-1}(f(S)) \subseteq S$. 

Now let's consider $S \subseteq f^{-1}(f(S))$.

By definition of inverse images, $f^{-1}(f(S))$ is the set $\{x \in X: f(x) \in f(S)\}$. 

If $x \in S$, then $f(x) \in f(S)$, and so $x$ meets the membership conditions of this set. That is, $x \in S  \implies x \in f^{-1}(f(S))$. This is equivalent to $S \subseteq f^{-1}(f(S))$. Note that we don't need $f$ to be injective for this.

By showing both $f^{-1}(f(S)) \subseteq S$ and $S \subseteq f^{-1}(f(S))$ under the assumption $f$ is injective, we have proven $f$ is injective $\implies f^{-1}(f(S))=S$.  $\square$

Tao Analysis I - 3.4.4

Exercise 3.4.4

Let $f:X \to Y$ be a function from one set $X$ to another set $Y$, and let $U$, $V$ be subsets of $Y$. Show that $f^{-1}(U \cup V)= f^{-1}(U) \cup f^{-1}(V)$, that $f^{-1}(U \cap V)= f^{-1}(U) \cap f^{-1}(V)$, and that $f^{-1}(U \setminus V)= f^{-1}(U) \setminus f^{-1}(V)$.

Before we attempt the exercise, let's remind ourselves of Definition 3.4.5 for inverse images. If $U$ is a subset of $Y$, we define the set $f^{-1}(U)$ to be the set

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

That is, $f^{-1}$ consists of all the elements of $X$ which map into $U$:

$$f(x) \in U \iff x \in f^{-1}(U)$$

We call $f^{-1}(U)$ the inverse image of $U$.

Show $f^{-1}(U \cup V)= f^{-1}(U) \cup f^{-1}(V)$

Let's apply Definition 3.4.5 to $f^{-1}(U \cup V)$,

$$f^{-1}(U \cup V) := \{x \in X: f(x) \in U \cup V\}$$

This is the set of $x$ such that either $f(x) \in U$ or $f(x) \in V$, or both, using the definition of union.

Let's consider both cases:

• $f(x) \in U$. Definition 3.4.5 tells us $f(x) \in U \iff x \in f^{-1}(U)$
• $f(x) \in V$. Definition 3.4.5 tells us $f(x) \in U \iff x \in f^{-1}(V)$

Since either or both of these are true, we have either or both of the following are true:

• $x \in f^{-1}(U)$
• $x \in f^{-1}(V)$

This is equivalent to $x \in f^{-1}(U) \cup f^{-1}(V)$.

Thus, we have shown $f^{-1}(U \cup V)= f^{-1}(U) \cup f^{-1}(V)$. $\square$

Note that we didn't have to show inclusion in both directions because the definitions we used are bidirectional $\iff$.

Show $f^{-1}(U \cap V)= f^{-1}(U) \cap f^{-1}(V)$

Let's apply Definition 3.4.5 to $f^{-1}(U \cap V)$,

$$f^{-1}(U \cap V) := \{x \in X: f(x) \in U \cap V\}$$

This is the set of $x$ such that $f(x) \in U$ and $f(x) \in V$, using the definition of intersection.

Let's consider the two cases, both of which must be true:

• $f(x) \in U$. Definition 3.4.5 tells us $f(x) \in U \iff x \in f^{-1}(U)$
• $f(x) \in V$. Definition 3.4.5 tells us $f(x) \in U \iff x \in f^{-1}(V)$

Since both of these are true, then both of the following are true:

• $x \in f^{-1}(U)$
• $x \in f^{-1}(V)$

This is equivalent to $x \in f^{-1}(U) \cap f^{-1}(V)$.

Thus, we have shown $f^{-1}(U \cap V)= f^{-1}(U) \cap f^{-1}(V)$. $\square$

Note that we didn't have to show inclusion in both directions because the definitions we used are bidirectional $\iff$.

Show $f^{-1}(U \setminus V)= f^{-1}(U) \setminus f^{-1}(V)$

Let's apply Definition 3.4.5 to $f^{-1}(U \setminus V)$,

$$f^{-1}(U \setminus V) := \{x \in X: f(x) \in U \setminus V\}$$

This is the set of $x$ such that $f(x) \in U$ and $f(x) \notin V$. 

Let's consider the two cases, both of which must be true:

• $f(x) \in U$. Definition 3.4.5 tells us $f(x) \in U \iff x \in f^{-1}(U)$
• $f(x) \notin V$. Definition 3.4.5 tells us $f(x) \in U \iff x \notin f^{-1}(V)$

Since both of these are true, then both of the following are true:

• $x \in f^{-1}(U)$
• $x \notin f^{-1}(V)$

This is equivalent to $x \in f^{-1}(U) \setminus f^{-1}(V)$.

Thus, we have shown $f^{-1}(U \setminus V)= f^{-1}(U) \setminus f^{-1}(V)$. $\square$

Note that we didn't have to show inclusion in both directions because the definitions we used are bidirectional $\iff$.

Tao Analysis I - 3.4.3

Exercise 3.4.3

Let $A$, $B$ be two subsets of a set $X$, and let $f:X \to Y$ be a function. Show that $f(A \cap B) \subseteq f(A) \cap f(B)$, that $f(A) \setminus f(B) \subseteq f(A \setminus B)$, $f(A∪B)= f(A) \cup f(B)$. For the first two statements, is it true that the $\subseteq$ relation can be improved to $=$?

Before we dive into the exercise, let's draw a picture to aid our thinking.

Show that $f(A \cap B) \subseteq f(A) \cap f(B)$

We need to show that

$$y \in f(A \cap B) \implies y \in f(A) \cap f(B)$$

If $y \in f(A \cap B)$ then there exists an $x \in (A \cap B)$ such that $y = f(x)$. 

Now, 

$$x \in (A \cap B) \iff (x \in A) \land (x \in B)$$

So,

$$ y \in f(A \cap B) \implies (y \in f(A)) \land (y \in f(B))$$

Note, this is a one-way implication because for a function, given an element of the domain, we can only say there is only one element in the co-domain. For an element in the co-domain, we can't say there is only one corresponding element of the domain.

Thus, we have shown that if $y \in f(A \cap B)$ then $y \in f(A) \cap f(B)$. 

This is equivalent to $f(A \cap B) \subseteq f(A) \cap f(B)$. $\square$

Can $\subseteq$ be strengthened to $=$?  All we need is a counter-example to show this can't be done.

Consider $X=Y=\mathbb{Z}$, $A=\{-1\}$, $B=\{1\}$, with $f:x \mapsto x^2$. Here:

• $f(A \cap B) = f(\emptyset) = \emptyset$, the empty set.
• $f(A) \cap f(B) = \{1\} \cap \{1\} = \{1\}$.

Here $f(A) \cap f(B) \nsubseteq f(A \cap B)$, a counter-example showing that equality is not possible for general $f$. $\square$

As an extra exercise, let's ask if $f$ injective would enable equality? If $f$ is injective, by definition that means $f(s) = f(t) \implies s=t$.

So if $y \in f(A) \cap f(B)$ then $y \in f(A) \land y \in f(B)$. So both of the following must be true:

• There exists an $a \in A$ such that $y=f(a) \in f(A)$.
• There exists a $b \in B$ such that $y=f(b) \in f(B)$.

We have $y=f(a)=f(b)$, which, if $f$ is injective, means $a=b$. Now this $x=a=b$ is in both $A$ and $B$, that is $x \in (A \cap B)$. This gives us $y=f(x) \in f(A \cap B)$. 

So we have shown that if $f$ is injective, $f(A) \cap f(B) \subseteq f(A \cap B)$. This, combined with the previous result that $f(A \cap B) \subseteq f(A) \cap f(B)$, gives us equality $f(A \cap B) = f(A) \cap f(B)$. $\square$

Show that $f(A) \setminus f(B) \subseteq f(A \setminus B)$

We need to show that $y \in f(A) \setminus f(B) \implies y \in f(A \setminus B)$.

The meaning of $y \in f(A) \setminus f(B)$ is that $y \in f(A) \land y \notin f(B)$. 

This means both of the following are true:

• There exists an $x \in A$ such that $f(x) = y$.
• For all $x \in B$ it is the case that $f(x) \neq y$. (see note at bottom)

This, $x \in A \land x \notin B$. That is, $x \in (A \setminus B)$. This implies $f(x) = y \in f(A \setminus B)$. 

Thus we have shown that $f(A) \setminus f(B) \subseteq f(A \setminus B)$.

Can $\subseteq$ be strengthened to $=$?  All we need is a counter-example to show this can't be done.

Consider $X=Y=\mathbb{Z}$, $A=\{-1\}$, $B=\{1\}$, with $f:x \mapsto x^2$. Here:

• $f(A) \setminus f(B) = \{1\} \setminus \{1\} = \emptyset$, the empty set.
• $f(A \setminus B) = f(\{-1\} \setminus\{1\}) = f(\{-1\}) = \{1\}$.

Here $f(A \setminus B) \nsubseteq f(A) \setminus f(B)$, a counter-example showing that equality is not possible for general $f$. $\square$

Show that $f(A∪B)= f(A) \cup f(B)$

We need to show both:

• $y \in f(A \cup B) \implies y \in f(A) \cup f(B)$
• $y \in f(A) \cup f(B) \implies y \in f(A \cup B)$

If $y \in f(A \cup B)$ then there exists an $x \in A \cup B$ such that $y = f(x) \in f(A \cup B)$. That $x$ could be in $A$ or it could be in $B$, or both. That means $(x \in A) \lor (x \in B)$. Let's consider both cases:

• $x \in A \implies y = f(x) \in f(A) \in f(A) \cup f(B)$
• $x \in B \implies y = f(x) \in f(B) \in f(A) \cup f(B)$

This means $y = f(x) \in f(A) \cup f(B)$. 

We have shown $y \in f(A \cup B) \implies y \in f(A) \cup f(B)$.

If $y \in f(A) \cup f(B)$ that means $y \in f(A)$ or $y \in f(B)$, or both. Let's consider both cases.

• If $y \in f(A)$ then there exists an $x \in A$ such that $y = f(x) \in f(A) \in f(A) \cup f(B)$.
• If $y \in f(B)$ then there exists an $x \in B$ such that $y = f(x) \in f(B) \in f(A) \cup f(B)$.

This $x$ is in $A$ or $B$, or both. And both cases imply $y = f(x) \in f(A \cup B)$.

We have shown $y \in f(A) \cup f(B) \implies y \in f(A \cup B)$.

By showing both implications, we have shown $f(A∪B)= f(A) \cup f(B)$. $\square$

Note: Negation of Quantifiers

Above we said that the meaning of $y \in f(A) \setminus f(B)$ is that $y \in f(A) \land y \notin f(B)$. We then said this means both of the following are true:

• There exists an $x \in A$ such that $f(x) = y$.
• For all $x \in B$ it is the case that $f(x) \neq y$. 

For the second bullet point we used negation of quantifiers - we "swap the quantifiers and negate the predicate".

$$ \neg [\exists x: f(x)=y] \quad \iff \quad \forall x [f(x) \neq y]$$

You can read more here: (pdf) and (pdf).

Tao Analysis I - 3.4.2

Exercise 3.4.2

Let$ f:X \to Y$ be a function from one set X to another set $Y$, let $S$ be a subset of $X$, and let $U$ be a subset of $Y$.

(i) What, in general, can one say about $f^{-1}( f (S))$ and $S$?

(ii) What about $f ( f^{-1}(U))$ and $U$?

(iii) What about $f^{-1}( f ( f^{-1}(U)))$ and $f^{−1}(U)$?

Let's draw a picture to aid our thinking.

The first thing to note is that $f$ hasn't been defined as injective, so we can't assume it is invertible in the sense that it has an inverse function. We can still discuss an inverse image.

The second thing to say is that $S$ and $U$ are not defined as being related, $U$ is not the image of $S$ under $f$.

(i) What, in general, can one say about $f^{-1}( f (S))$ and $S$?

Since $f$ is defined as a function from $X$ to $Y$, and since $S \subseteq X$, then $f(S)$ is defined, and is a subset of $Y$. 

Now, by Definition 3.4.5, $f^{-1}(f(S))$ is the inverse image of $f(S)$ where 

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

If $x \in S$, then $f(x) \in f(S)$. This means such $x$ belong in the set $\{x \in X: f(x) \in f(S)\}$, which is $f^{-1}(f(S))$.

So we can say $S \subseteq f^{-1}( f (S))$. $\square$

Note, we can't say $f^{-1}( f (S)) \subseteq S$, and so we can't say the two sets are equal.

(ii) What about $f ( f^{-1}(U))$ and $U$?

We have to be careful here. Every $x \in X$ has an $f(x) \in Y$. However, not every $y \in Y$ has an $x$ such that $f(x) \in Y$. This is an asymmetry in the definitions of domain and codomain.

The most we can say about $U$ is that some $x \in X$, and possibly no $x \in X$, are such that $f(x) \in U$. We are not given any facts that tell us every $y \in Y$ has an antecedent in $X$.

Now, Definition 3.4.5 tell us that

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

In words, this inverse image is a set of $x$ such that $f(x) \in U$. So if we apply $f$ to this set we have

$$f(f^{-1}(U) \subseteq U$$

We can say $f ( f^{-1}(U)) \subseteq U$, where that subset could be the empty set. $\square$

We can't say the sets are equal because there may be only some, or no, $y \in U$ such that $f(x) = y$.

(iii) What about $f^{-1}( f ( f^{-1}(U)))$ and $f ^{−1}(U)$?

We can use the result from (i), $S \subseteq f^{-1}( f (S))$ and set $S=f ^{−1}(U)$ to give,

$$f ^{−1}(U) \subseteq f^{-1}( f (f ^{−1}(U)))$$

Now let's use the result from (ii), $f(f^{-1}(U) \subseteq U$ and take the inverse image of both sides to give,

$$f^{-1}(f(f^{-1}(U)) \subseteq f^{-1}(U)$$

This uses the fact that $A \subseteq B \implies f^{-1}(A) \subseteq f^{-1}(B)$, see below for proof.

By showing inclusion in both directions, we have shown the two sets are equal, $f^{-1}( f ( f^{-1}(U))) = f ^{−1}(U)$. $\square$

Show $A \subseteq B \implies f^{-1}(A) \subseteq f^{-1}(B)$

The definition of inverse image $𝑓^{−1}$ applied to $A$ is

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

Similarly for $B$

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

Since $A \subseteq B$, then $f(x) \in A \implies f(x) \in B$.

Thus,

$$f^{-1}(A) \subseteq f^{-1}(B) \; \square$$

Tao Analysis I - 3.4.1

Exercise 3.4.1

Let $f : X \to Y$ be a bijective function, and let $f^{−1} : Y \to X$ be its inverse. Let $V$ be any subset of $Y$. Prove that the forward image of $V$ under $f^{−1}$ is the same set as the inverse image of $V$ under $f$; thus the fact that both sets are denoted by $f^{−1}(V)$ will not lead to any inconsistency.

There are two, sufficiently different, definitions of inverse; that of an inverse function, and the inverse image. Let's remind ourselves of the difference.

Inverse function. If $f:X \to Y$ is bijective, then for every $y \in Y$, there is exactly one $x \in X$ such that $f(x)=y$. This value is denoted $f^{-1}(y)$, where $f^{-1} : Y \to X$ is the inverse of $f$.

Definition 3.4.5 (Inverse images). If $U$ is a subset of $Y$, we define the set $f^{-1}(U)$ to be the set

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

In other words, $f^{-1}(U)$ consists of all the elements of $X$ which map into $U$:

$$f(x) \in U \iff x \in f^{-1}(U)$$

We call $f^{-1}(U)$ the inverse image of $U$.

The key difference is that inverse images don't require a function to be bijective. For example, $f:\mathbb{Z} \to \mathbb{N}$ where $f(x)=x^2$ is not bijective because both $f(2)=4$, and $f(-2)=4$. This function has no inverse, but we can define an inverse image. Consider $U=\{0, 1, 4\}$, then the inverse image $f^{-1}(U)=\{-2, -1, 0, 1, 2\}$.

Let's proceed with the exercise by starting with a picture to help us think.

We need to show that the following two sets are the same:

• the image of $V$ under the function $f^{-1}$
• the inverse image of $V$ under $f$

Let's start with the image $f^{-1}(V)$. This is the set $\{f^{-1}(v): v \in V\}$. Now, because $f$ is bijective, it is invertible. By definition of inverse functions, for every $v \in V$, there is a single $x = f^{-1}(v)$ such that $f(x)=v$. We can therefore substitute $f^{-1}(v)$ with $x$, and $v$ with $f(x)$ in the set definition to give $\{x: f(x) \in V\}$.

By Definition 3.4.5, the inverse image of $V$ under $f$ is that set of $x$ such that $f(x) \in V$. This set is defined as $\{x: f(x) \in V\}$.

The two sets have the same membership condition, and so are the same. $\square$

Note that this equivalence between the two definitions hinges on $f$ being bijective. If $f$ were not bijective, then the two sets are not necessarily the same.

Alternative Solution

ProFatXuan's solution takes the standard approach of proving two sets, $A$ and $B$, are the same by showing that an element of one is an element of the other, $A \subseteq B$, and $B \subseteq A$. Let's develop a proof using that approach.

Let's define the two sets, $A$ and $B$:

• $A$ is the forward image of $V$ under $f^{-1}$. So $A=\{f^{-1}(v): v\in V\}$
• $B$ is the inverse image of $V$ under $f$. So $B=\{x \in X: f(x) \in V\}$

Now, if $x \in A$ then $x=f^{-1}(v)$ for $v \in V$. By definition of an inverse function, applicable since $f$ is bijective, every $v \in V$ has a single $x=f^{-1}(v)$ such that $f(x)=v$. This is the definition of $B$ so $A \subseteq B$.

If $x \in B$, then it is because those $x$ are such that $f(x)=v$ for $v \in V$. Again, by definition of an inverse function, we have $x=f^{-1}(v)$ for $v \in V$. This is the definition of $A$, so $B \subseteq A$.

By showing elements of one set are members of the other, we have proved the sets are the same. $\square$

Tao Ananlysis I - 3.3.8

Exercise 3.3.8

If $X$ is a subset of $Y$, let $\iota_{X \to Y} : X → Y$ be the inclusion map from $X$ to $Y$, defined by mapping $x \mapsto x$ for all $x∈X$, that is, $\iota_{X→Y}(x):=x$ for all $x∈X$. The map $\iota{X \to X}$ is in particular called the identity map on $X$.

(a) Show that if $X \subseteq Y \subseteq Z$ then $\iota_{Y \to Z} \circ \iota_{X \to Y}=\iota_{X \to Z}$.

(b) Show that if $f: A \to B$ is any function, then $f = f \circ \iota_{A\to A} =\iota_{B \to B} \circ f$.

(c) Show that, if $f:A \to B$ is a bijective function, then $f \circ f^{−1}=\iota_{B \to B}$ and $f^{−1} \circ f= \iota_{A \to A}$.

(d) Show that if $X$ and $Y$ are disjoint sets, and $f : X \to Z$ and $g: Y \to Z$ are functions, then there is a unique function $h: X∪Y \to Z$ such that $h \circ \iota_{X \to X \cup Y} =f$ and $h \circ \iota_{Y\to X \cup Y} =g$.

(e) Show that the hypothesis that $X$ and $Y$ are disjoint can be dropped in (d) if one adds the additional hypothesis that $f(x)=g(x)$ for all $x \in X \cap Y$.

By the way, that symbol $\iota$ is the greek letter iota.

(a) Show that if $X \subseteq Y \subseteq Z$ then $\iota_{Y \to Z} \circ \iota_{X \to Y}=\iota_{X \to Z}$

Let's first explain the meaning of $X \subseteq Y \subseteq Z$. It says that every $x \in X$ is also in $Y$, and that every $y \in Y$ is also in $Z$, resulting in every $x \in X$ also being in $Z$.

Now, let's consider $\iota_{X \to Y}$. This is a function from $X$ to $Y$, mapping $x \mapsto x$.

Similarly, $\iota_{Y \to Z}$ is a function from $Y$ to $Z$, mapping $y \mapsto y$.

So, the composition $\iota_{Y \to Z} \circ \iota_{X \to Y}$ is a function $X \to Y \to Z$, mapping $x \mapsto x$, then $y \mapsto y$. That second mapping is equivalent to $x \mapsto x$ because the first one maps $x \mapsto x$, where $x \in Y$.

Thus, $\iota_{Y \to Z} \circ \iota_{X \to Y}$ is a function $X \to Z$, mapping $x \mapsto x$. This is the definition of $\iota_{X \to Z}$. $\square$

(b) Show that if $f: A \to B$ is any function, then $f = f \circ \iota_{A\to A} =\iota_{B \to B} \circ f$.

Let's first consider $\iota_{A to A}$.  This is a function $A \to A$ mapping $a \mapsto a$, where $a \in A$.

The composition $f \circ \iota_{A to A}$ is therefore a function $A \to A \to B$, mapping $a \mapsto a$ then $a \mapsto f(a)$, where $f(a) \in B$. This is equivalent to a function $A \to B$, mapping $a \mapsto f(a)$. This is the definition of $f$. 

So we have shown $f = f \circ \iota_{A\to A}$. $\square$

Let's now consider the function $\iota_{B \to B}$. This is a function $B \to B$ which maps $b \mapsto b$, for $b \in B$. 

The composition $\iota_{B \to B} \circ f$ is a function $A \to B \to B$, which first maps $a \mapsto f(a)$ then $b \mapsto b$. Since $f(a) \in B$, the second mapping is $f(a) \mapsto f(a)$. The composition is therefore a function $A \to B$, mapping $a \mapsto f(a)$. This is the definition of $f$.

So we have shown $f = \iota_{B \to B} \circ f$. $\square$

(c) Show that, if $f:A \to B$ is a bijective function, then $f \circ f^{−1}=\iota_{B \to B}$ and $f^{−1} \circ f= \iota_{A \to A}$.

Let's first consider $f \circ f^{-1}$. This composition is a function $B \to A \to B$. Because $f$ is bijective, it is invertible, and for every $b \in B$ there is a unique $a \in A$ such that $f(a)=b$. That $a$ is $f^{-1}(b)$. 

And so we have $f \circ f^{-1}(b) = f(a) = b$.

The composition is equivalent to a function $B \to B$ which maps $b \mapsto b$. This is the definition of $\iota_{B \to B}$. $\square$

The argument for the second equivalence is very similar.

Consider $f^{-1} \circ f$. This composition is a function $A \to B \to A$. Because $f$ is bijective, it is invertible, and for every $b \in B$ there is a unique $a \in A$ such that $f(a)=b$. That $a$ is $f^{-1}(b)$.  

And so we have $f^{-1} \circ f(a) = f^{-1}(b) = a$.

The composition is equivalent to a function $A \to A$ which maps $a \mapsto a$. This is the definition of $\iota_{A \to A}$. $\square$

(d) Show that if $X$ and $Y$ are disjoint sets, and $f : X \to Z$ and $g: Y \to Z$ are functions, then there is a unique function $h: X∪Y \to Z$ such that $h \circ \iota_{X \to X \cup Y} =f$ and $h \circ \iota_{Y\to X \cup Y} =g$.

Our aim is to show that $h$ is indeed a function, and that it is unique. Let's draw a picture to aid our thinking.

For $h$ to be a function, it needs to have a defined domain, codomain, and map elements from the domain to a single element of the codomain. The domain is $X \cup Y$, and the codomain is $Z$. 

Does $h$ map elements from the domain to a single element of the codomain? Well, an element of the domain is either in $X$ or in $Y$ but not both since $X$ and $Y$ are disjoint. 

If an element is in $X$ then $\iota_{X \to X \cup Y}$ maps $x \mapsto x$ where $x \in X$, but expands the domain $X$  to $X \cup Y$ as the codomain. Importantly, if the input is a particular $x$, the output is the same $x$. So the composition $h \circ \iota_{X \to X \cup Y}$ maps $x \in X$ to $z \in Z$, and we are given this is $f(x)$. Since $f$ is a function, this means $h$ maps each element of $X$ to a single element of $Z$. The same argument applies for $Y$ and $h \circ \iota_{X \to X \cup Y}$, which tells us that $h$ maps each element of $Y$ to a single element of $Z$.

Because $X$ and $Y$ are disjoint, there is no element of $X \cup Y$ which could map to two different elements of $Z$, via $f$ and $g$.

So $h$ has a defined domain, codomain, and we have shown it maps elements of $X \cup Y$ to a single element of $Z$. This means $h$ is a function. $\square$

Let's now show it is unique. Let's assume $h: X∪Y \to Z$ and $h': X∪Y \to Z$ are different functions, subject to the same constraints:

• $h \circ \iota_{X \to X \cup Y} = f$ and $h' \circ \iota_{X \to X \cup Y} = f$
• $h \circ \iota_{Y\to X \cup Y} = g$ and $h' \circ \iota_{Y\to X \cup Y} = g$

The domain of $h'$ is $X \cup Y$. An element of this domain is either in $X$ or $Y$ but not both. Let's consider both cases:

• For $x \in X$, we have $h'( \iota_{X \to X \cup Y}(x))=h'(x)=f(x)$. We also have $h( \iota_{X \to X \cup Y}(x))=h(x)=f(x)$. So $h(x) = h'(x)$ for $x \in X$.
• For $y \in Y$, we have $h'( \iota_{Y \to X \cup Y}(y))=h'(y)=g(y)$. We also have $h( \iota_{Y \to X \cup Y}(y))=h(y)=g(y)$. So $h(y) = h'(y)$ for $y \in Y$.

So $h=h'$ over the entire domain $X \cup Y$. We have shown that $h$ is unique. $\square$

(e) Show that the hypothesis that $X$ and $Y$ are disjoint can be dropped in (d) if one adds the additional hypothesis that $f(x)=g(x)$ for all $x \in X \cap Y$.

Let's draw a picture to help our thinking.

If we drop the requirement for $X$ and $Y$ to be disjoint, we need another way to ensure that $h$ is a function that maps each element of $X \cup Y$ to a single element of $Z$.

We can see that elements in $X \cap Y$ can be mapped by both $f$ and $g$. To ensure the mapping is unique, we need $f(x)=g(x)$ for all $x \in X \cup Y$. $\square$

Tao Analysis I - 3.3.7

Exercise 3.3.7

Let $f : X \mapsto Y$ and $g: Y \mapsto Z$ be functions. Show that if $f$ and $g$ are bijective, then so is $g \circ f$, and we have $(g \circ f)^{−1} = f^{−1}  \circ g^{−1}$.

Show $g \circ f$ is Bijective 

To show $g \circ f$ is bijective, we need to show it is injective and surjective.

For the purpose of contradiction, let's assume $g \circ f$ is not injective. That means there exists $x, x' \in X$, where $x \neq x'$, such that

$$g (f(x)) = g(f(x'))$$

Since $g$ is injective, by Definition 3.3.17, we have 

$$g (f(x)) = g(f(x')) \implies f(x)=f(x')$$

Again, since $f$ is injective, by Definition 3.3.17, we have

$$f(x)=f(x') \implies x=x'$$

This contradicts our assertion that $x \neq x'$.  We have shown that $g \circ f$ is injective.

Again, for the purpose of contradiction, let's assume $g \circ f$ is not surjective. This means there exists a $z' \in Z$ such that

$$g(f(x)) \neq z'$$

We are given that $g$ is surjective, which means every $z \in Z$ has a $y \in Y$ such that $z=g(y)$.  Similarly, we are given that $f$ is surjective, which means that every $y \in Y$ has an $x \in X$ such that $y=f(x)$. 

Together this means every $z \in Z$ has an $x \in X$ such that $z = g(f(x))$. This contradicts our assertion that $g \circ f$ is not surjective. We have shown that $g \circ f$ is surjective.

By showing $g \circ f$ is both injective and surjective, we have shown it is bijective. $\square$

Show $(g \circ f)^{−1} = f^{−1}  \circ g^{−1}$

Let's consider $(g \circ f)^{−1}$. We have just shown it is bijective, so it is invertible.

Using the textbook's definition, $x=(g \circ f)^{−1}(z)$ is the unique value of $x$ such that

$$g(f(x))=z$$

We can apply $g^{-1}$ to both sides,

$$g^{-1}(g(f(x)))=g^{-1}(z)$$

And then simplify using the cancellation law from Exercise 3.3.6,

$$f(x) = g^{-1}(z))$$

Again, applying $f^{-1}$ to both sides, and using the cancellation law, gives us

$$x = f^{-1}(g^{-1}(z))$$

We have shown $x=(g \circ f)^{−1}(z) = f^{−1}  \circ g^{−1}(z)$, which means $(g \circ f)^{−1} = f^{−1}  \circ g^{−1}$. $\square$

Tao Analysis I - 3.3.6

Exercise 3.3.6

Let $f : X \mapsto Y$ be a bijective function, and let $f^{−1} : Y \mapsto X$ be its inverse. Verify the cancellation laws $f^{−1}(f(x))=x$ for all $x∈X$ and $f(f^{−1}(y))=y$ for all $y∈Y$. Conclude that $f^{−1}$ is also invertible and has $f$ as its inverse (thus $( f^{−1})^{−1} = f$).

Let's first remind ourselves of what the inverse of a function is according to the textbook:

If $f$ is bijective, then for every $y \in Y$, there is exactly one $x$ such that $f(x)=y$. This value of $x$ is denoted $f^{-1}(y)$; thus $f^{-1}$ is a function from $Y$ to $X$. We call $f^{-1}$ the inverse of $f$.

Show  $f^{−1}(f(x))=x$

Let's first consider $f(x)$.

Since $f$ is injective, for every $x$ there is a unique $y=f(x) \in Y$. And since $f$ is surjective, for every $y \in Y$, there is an $x$ such that $y=f(x)$. Together, this means every $y$ has a unique $x$ such that $y=f(x)$. We can therefore denote this $x$ as $f^{-1}(y)$, as per the textbook's definition:

$$f^{-1}(y) = x$$

And since $y=f(x)$, we have

$$f^{-1}(f(x)) = x$$

Thus, we have verified the cancellation law $f^{−1}(f(x))=x$. $\square$

Show  $f(f^{−1}(y))=y$

Let's first consider $f(x)=y$.

Since we have shown that $x=f^{-1}(x)$ for all $x \in X$, we can write

$$f(f^{-1}(x)) = y$$

Thus, we have verified the cancellation law $f(f^{−1}(y))=y$. $\square$

Show $f^{−1}$ is Invertible

To show that a function $f$ is invertible, we need to show it is bijective:

• If $f$ is not injective, then the inverse would not be unique. 
• If $f$ is not surjective, then some elements of its codomain $Y$ are not invertible. 

For the purpose of contradiction, let's assume $f^{-1}$ is not injective. That would mean there exist $y, y' \in Y$, where $y \neq y'$, such that

$$f^{-1}(y)=f^{-1}(y')$$

Now, let's use $y=f(x)$ and $y'=f(x')$, to give us

$$f^{-1}(f(x))=f^{-1}(f(x'))$$

We can apply the first cancellation law above,

$$x=x'$$

Because $f$ is given as injective, this means $f(x)=f(x')$, that is $y=y'$. This is a contradiction, because we set $y \neq y'$ earlier.

Thus we have shown $f^{-1}$ is injective.

Now we need to show $f^{-1}$ is surjective.

For the purpose of contradiction, let's assume $f^{-1}$ is not surjective. That means there exists an $x' \in X$ such that

$$f^{-1}(y) \neq x'$$

Applying $f$ to both sides gives us

$$f(f(^{-1}(y)) \neq f(x') = y'$$

Using the second cancellation law gives us

$$y \neq f(x') = y'$$

This is a contradiction because $f$ is surjective, and for every $y \in Y$, including this $y'$,  there exists an $x$ such that $f(x)=y$.

Thus we have shown $f^{-1}$ is surjective.

Having shown $f^{-1}$ is both injective and surjective, that is bijective, we can say it is invertible. $\square$

Show $f$ is the inverse of $f^{-1}$

Let's use the description of an inverse given in the textbook.

If $f^{-1}: Y \mapsto X$ is bijective, then for every $x \in X$, there is exactly one $y$ such that $f^{-1}(y)=x$. This value of $y$ is denoted $(f^{-1})^{-1}(x)$, thus $(f^{-1})^{-1}$ is a function from $X$ to $Y$, and is the inverse of $f^{-1}$.

Let's apply $f$ to both sides of $f^{-1}(y)=x$

$$f(f^{-1}(y))=f(x)$$

Applying the second cancellation law gives,

$$y=f(x)$$

That is, $y$, which is $(f^{-1})^{-1}(x)$, is $f(x)$. That means the inverse of $f^{-1}$ is $f$. $\square$

Tao Analysis I - 3.3.5

Exercise 3.3.5

Let $f:X \mapsto Y$ and $g:Y \mapsto Z$ be functions. Show that if $g \circ f$ is injective, then $f$ must be injective. Is it true that $g$ must also be injective? Show that if $g \circ f$ is surjective, then $g$ must be surjective. Is it true that $f$ must also be surjective?

In the following, $x \in X$ and $y \in Y$.

Injectivity

We are given that $g \circ f$ is injective. Using Definition 3.3.17 for injectivity, this means

$$g(f(x)) = g(f(x')) \implies x=x'$$

For the purpose of contradiction, let's assume $f$ is not injective. This means that there is an $x$ and an $x'$, where $x \neq x'$, such that

$$f(x)=f(x')$$

That is, two different inputs for $f$ give the same output, due to $f$ not being injective. Because $g$ is a function, the same input gives the same output,

$$g(f(x))=g(f(x'))$$

This contradicts the given fact that $g \circ f$ is injective, $g(f(x))=g(f(x')) \implies x=x'$.

Thus, we have shown that if $g \circ f$ is injective, then $f$ must be injective. $\square$

We can show that $g$ doesn't have to be injective with a counter-example. Consider:

• $X=\{1,2\}$, $Y=\{1,2,3\}$, and $f(x)=x$. Here $f$ is injective.
• $Z=\{1,2\}$, and $g(1)=1$, $g(2)=2$, $g(3)=2$. Here $g$ is not injective.

Here, the composition $g \circ f$ is injective, even though $g$ is not.

Surjectivity

We are given that $g \circ f$ is surjective. By Definition 3.3.20, this means that for every $z \in Z$ there is an $x \in X$ such that $g(f(x))=z$.

Intuitively, it is clear that if $g$ is not surjective, then it doesn't hit some elements of $Z$ which contradicts the definition that $g(f(x))$ must hit every element of $Z$.

For the purpose of contradiction, let's assume $g$ is not surjective. That means there is an element $z' \in Z$ where $g(y) \neq z'$, which is true for all $y \in Y$. Now $f(x) \in Y$, so we have $g(f(x)) \neq z'$. This contradicts the given statement that $g \circ f$ is surjective.

Thus, we have shown that if $g \circ f$ is surjective, then $g$ must be surjective. $\square$

We can show that $f$ doesn't have to be surjective with a counter-example. Consider:

• $X=\{1,2,3\}$, $Y=\{1,2,3\}$, and $f(1)=1$, $f(2)=2$, $f(3)=2$. Here $f$ is not surjective.
• $Z=\{1,2\}$, and $g(x)=x$. Here $g$ is surjective.

Here, the composition $g \circ f$ is surjective, even though $f$ is not.

Tao Analysis I - 3.3.4

Exercise 3.3.4

In this section we give some cancellation laws for composition. Let $f : X \mapsto Y$, $\tilde{f}: X \mapsto Y$, $g : Y \mapsto Z$, and $\tilde{g}: Y \mapsto Z$ be functions. Show that if $g \circ f = g \circ \tilde{f}$ and $g$ is injective, then $f = \tilde{f}$. Is the same statement true if $g$ is not injective? Show that if $g \circ f = \tilde{g} \circ f$ and $f$ is surjective, then $g = \tilde{g}$. Is the same statement true if f is not surjective?

Injective Cancellation Law

Let's look at the first part of the question. We are given

$$g \circ f = g \circ \tilde{f}$$

and $g$ is injective.

If $g$ is injective, then by Definition 3.3.17, $g(x)=g(x') \implies x=x'$ for $x, x' \in X$, which here means

$$g(f(x))=g(\tilde{f}(x)) \implies f(x)= \tilde{f}(x)$$

That is, $f(x)$ and $\tilde{f}(x)$ map $x \in X$ to the very same values, and are thus, equal functions.

We have shown that if $g \circ f = g \circ \tilde{f}$ and $g$ is injective, then $f = \tilde{f}$. $\square$

If $g$ is not injective, then the statement is not always true. A counter-example is sufficient to prove this. Consider $f(x)=x$, $\tilde{f}=-x$, and $g(x)=x^2$. Here $g \circ f = g \circ \tilde{f}$ but $f \neq \tilde{f}$.

Surjective Cancellation Law

We are given

$$g \circ f = \tilde{g} \circ f$$

and $f$ is surjective.

If $f$ is surjective, then by Definition 3.3.20, every value of $y=f(x) \in Y$ has an $x \in X$. This means the full domain $Y$ is available to the function $g$, a requirement of the definition of $g$.

If we consider

$$g(y) = \tilde{g}(y)$$

This tells us that $g$ and $\tilde{g}$ both map $y\in Y$ to the same values, and we have already seen the surjectivity of $f$ provides for the full $Y$ as a domain for $g$.

Thus, we have shown that if $g \circ f = \tilde{g} \circ f$ and $f$ is surjective, then $g=\tilde{g}$. $\square$

If $f$ is not surjective then the domain available to $g$ is not the full $Y$. Consider an example, $f(x)=|x|$ which is not surjective, $g(x)=|x|$ and $\tilde{g}(x)=x$. Here $g \circ f = \tilde{g} \circ f$ but $g \neq \tilde{g}$.

Tao Analysis I - 3.3.3

Exercise 3.3.3

When is the empty function into a given set X injective? surjective? bijective?

Let's remind ourselves that an empty function $f: \emptyset \mapsto X$ maps from the empty set to a given set X. Since the empty set has no elements, we do not need to specify what $f$ does to any input. Note that each and every set $X$ has only one empty function from $\emptyset$ to that $X$.

When is the empty function injective?

Any function must map an input to only one output, but an injective function also requires that different inputs don't map to the same output. This is Definition 3.3.17.

$$x \neq x' \implies f(x) \neq f(x')$$

Since the empty function has no elements, the condition for an empty function $f: \emptyset \mapsto X$ to be injective is vacuously true. $\square$

When is the empty function surjective?

A function $f: A \mapsto X$ is surjective if every element $x$ of the codomain $X$ has an $a$ in the domain $A$ such that $f(a)=x$. This is Definition 3.3.20.

$$x \neq x' \implies f(x) \neq f(x')$$

Since the domain $A=\emptyset$ of an empty function has no elements, then the definition can't apply. The only exception is when the codomain is empty $X=\emptyset$, in which case the defining condition is vacuously true.

An empty function is surjective if the codomain $X$ is the empty set $\emptyset$. $\square$.

When is the empty function bijective?

A function is bijective if it is both injective and surjective. A bijective function is also called invertible. This is from Definition 3.3.23.

Given the above discussion, an empty function is always injective but only surective when the codomain is the emptyset. 

Thus, the empty function is bijective, invertible, when the codomain is the empty set $X=\emptyset$. $\square$