Chapter 1 section 2 allufi chapter 0 problems and solutions

2.2: Prove statement (2) in proposition 2.1.

You may assume that given a family of disjoint subset of a set, there is a way to choose one element in each member of the family.

Proposition 2.1)

Assume $A \neq \emptyset$, and let $f : A \rightarrow B$ be a function. Then,
1)f has a right inverse iff it is surjective.

Suppose that f has a right inverse g. We wish to show that f is surjective. Let $b \in B$, consider $f(g(b)) = id_B(b) = b$. Thus, $f( g(b)) = b \implies f$ is surjective.


Conversely, suppose that f is surjective, then we wish to show that f has a right inverse. We shall define $g(b)$ as follows. Consider the set $A_b = \{a \in A : f(a) = b) \}$. Then, this set is non-empty as f is surjective.

Then, select an element $a_{b} \in A_b$. Define $g(b) = a_b$. Similarly, extend this function to the whole domain B, by defining $g(b) = a_b$ constructed in the same way. Then, the constructed function $g : B \rightarrow A$ is a right inverse of $f : A \rightarrow B$ by construction. $\square$

2.3: Prove that the inverse of a bijection is a bijection, and that the composition of two bijection is a bijection.

Suppose that $f : A \rightarrow B$ is a bijection and $f^{-1} : B \rightarrow A$ is the inverse.
Recall $f^{-1} : B \rightarrow A$ is defined as $f^{-1}(b) = a \iff f(a) = b$. Suppose that $c = f^{-1}(b_1) = f^{-1}(b_2)$. This means that $f(c) = b_1$ and $f(c) = b_2$. Since f is a function, this means that $b_1 = b_2$. Therefore $f^{-1}$ is an injection.

Now we wish to show that $f^{-1}$ is a surjection. Let $a \in A$ be arbitrarily element, then consider $f(a) \in B$. Then, $f^{-1}(f(a)) = a \implies f^{-1}$ is surjective. $\square$

Suppose that $f : A \rightarrow B$ and $g: B \rightarrow D$ are two bijective functions.
Consider $h := g \circ f : A \rightarrow D$. Then this is a bijection function since it has two sided inverse $f^{-1} \circ g^{-1} : D \rightarrow A$.  $\square$

2.5: Formulate a notion of epimorphism, in the style of monomorphism seen in 2.6, and prove a result analogous to proposition 2.3, for epimorphisms and surjections.

Formulation: (Here the category we are considering is that of Sets).

A function $f : A \rightarrow B$ is a epimorphisms iff for all sets $Z$ and for all functions such that $\alpha_1,\alpha_2 : B \rightarrow Z$ such that $\alpha_1 \circ f = \alpha \circ f \implies \alpha_1 = \alpha_2$.

Conjecture:
$f : A \rightarrow B$ is a epimorphism $\iff$ f is surjective.

Suppose that $f : A \rightarrow B$ is surjection and suppose Z is a set and $\alpha_1,\alpha_2 : B \rightarrow Z$ such that $\alpha_1 \circ f = \alpha_2 \circ f$. Since f is surjective, so this means that it has a right inverse g $\implies (\alpha_1 \circ f) \circ g = (\alpha_2 \circ f ) \circ g \implies \alpha_1 \circ (f \circ g = id) = \alpha_2 \circ (f \circ g = id) \implies \alpha_1 = \alpha_2$.


Conversely, suppose that $f : A \rightarrow B$ is a epimorphism. Suppose that f isn't surjective. That is there exists $b \in A$ : there exists no $a \in A$ that gets mapped to b. Pick arbitrarily $\alpha_1 : B \rightarrow A$, then construct $\alpha_2 : B \rightarrow A$ to be the same as $\alpha_1$, except at point b, that is $\alpha_1(b) \neq \alpha_2(b)$. Then, $\alpha_1 \circ f = \alpha_2 \circ f$, however $\alpha_1 \neq \alpha_2$. Contradiction. $\square$


2.4: Prove that "isomorphism" is an equivalence relation on any sets.

$A \cong A$ since, id : A \rightarrow A obtained by $id(a) = a$ is trivially a bijection. Thus, the notion of bijection is reflexive.

Suppose that $A \cong B$ and $B \cong C$, then there exists bijections $f : A \rightarrow B$ and $g : B \rightarrow C$. Thus, $g \circ f : A \rightarrow C$ is a bijection from A to C. Thus, $A \cong C$. Thus, the notion of bijection is transitive.


Suppose $A \cong B$, then there exists a bijection $f : A \rightarrow B$. Since, f is a bijection, so it has a unique inverse $f^{-1} : B \rightarrow A$. Moreover, this inverse $f^{-1}$ is a bijection from B to A. Thus $B \cong A$. Therefore, the notion of bijection is symmetric. $\square$

2.6: With the notation as in example 2.4 explain how any function $f : A \rightarrow B$ determines a section of $\pi_A$.

Recall, surjective functions induce right inverses, and we call those right inverses sections.

Recall, Let A and B be sets. Then, there are natural projections $\pi_A$ and $\pi_B$:

\begin{equation*}
\xymatrix{
& A \times B \ar[dl]_{\pi_A} \ar[dr]^{\pi_B} &  \\
A& & B
}
\end{equation*}

Thos are defined by $$\pi_A((a,b) := a$$
$$\pi_B((a,b)) := b$$

Both maps are clearly surjective. Given any function $f : A \rightarrow B$ construct a section $g : A \rightarrow A \times B$ of $\pi_A$ as follows, $a \mapsto (a,f(a))$. This is a section since $(\pi_A \circ g)(a) = a \  \forall \ a \in A$. Thus any function $f : A \rightarrow B$, determines a section of $\pi_A$. $\square$

2.7: Let $f : A \rightarrow B$. Prove that the graph $\Gamma_f$ of f is isomorphic to A.

Recall, $$\Gamma_f := \{(a,b) \ : \ b = f(a)\}.$$

Consider $\theta : A \rightarrow \Gamma_f$ given by $a \mapsto (a,f(a))$, then it is obvious that this gives an isomorphism.

Let $m = (c,f(c)) \in \gamma_f$, then $\theta(c) = m$. Therefore, $\theta$ is surjective.

Suppose that $$(a_1,f(a_1)) = (a_2,f(a_2)) \implies a_1 = a_2 \ and \ f(a_1) = f(a_2).$$

Thus, $\theta$ is injective as $a_1 = a_2$. $\square$

More questions and solutions to come for this section.

2.8: Describe as explicitly as you can all terms in the canonical decomposition of the function $\mathbb{R} \rightarrow \mathbb{C}$ defined by $r \mapsto e^{2 \pi r}$.

Recall given any $f : A \rightarrow B$ we have the following decomposition
$$A \twoheadrightarrow A/\sim~ \rightarrow im(f) \hookrightarrow B$$

Here the map $A/\sim~ \rightarrow im(f)$ is a isomorphism.  Recall $a_1 \sim a_2 \iff f(a_1) = f(a_2)$.
Therefore given $\psi : \mathbb{R} \rightarrow \mathbb{C}$ given by $r \mapsto e^{2\pi r}$. We have $r_1 \sim r_2 \iff e^{2\pi r_1} = e^{2\pi r_2} \iff r_2 = r_1 + 2\pi  k$ for some $k \in \mathbb{Z}$.

Therefore $A/~ \cong S^{1}$ that is $A/~$ is a circle. This exercise matches exercise 1.6.


2.9: Show that if $A^{\prime} \cong A^{\prime \prime}$ and $B^{\prime} \cong B^{\prime \prime}$, and further $A^{\prime} \cap B^{\prime} = \emptyset$ and $A^{\prime \prime} \cap B^{\prime \prime} = \emptyset$, then $A^{\prime} \cup B^{\prime} \cong A^{\prime \prime} \cup B^{\prime \prime}$. Conclude that the operation $A \coprod B$ is well defined up-to-isomorphism.

Since $A^{\prime} \cong A^{\prime \prime} \implies$ there exists a bijection $f : A^{\prime} \rightarrow A^{\prime \prime}$. Similiarly since $B^{\prime} \cong B^{\prime \prime} \implies$ there exists a bijection $g : B^{\prime} \rightarrow B^{\prime \prime}$. Construct $\phi : A^{\prime} \cup B^{\prime} \rightarrow A^{\prime \prime} \cup B^{\prime \prime}$ as follows:

$c \mapsto f(c) \ if \ c \in A^{\prime}$ and $c \mapsto g(c)\ if\ c \in B^{\prime}$. Since $A^{\prime} \cap B^{\prime} = \emptyset$, so c can't be simulatenously in both $A^{\prime}$ and $B^{\prime}$, so $\phi$ is well defined. We have to prove it is a bijection.

Suppose $\phi(c_1) = \phi(c_2)$, then either $c \in A^{\prime}$ or $c \in B^{\prime}$. As $\phi$ is well defined we have $f(c_1) = f(c_2)$ or $g(c_1) = g(c_2)$ then from the fact that f and g are bijection then we have $c_1 = c_2$. 

Suppose that $d \in A^{\prime \prime} \cup B^{\prime \prime}$ then $d \in A^{\prime \prime}$ or $d \in B^{\prime \prime}$, but it can't be in both. Suppose $d \in A^{\prime \prime}$, since f is bijection it has unique inverse $f^{-1}$. Consider the element $f^{-1}(d) \in A^{\prime}$, then $\phi(f^{-1}(d)) = f(f^{-1}(d)) = d \implies f$ is surjective. $\square$

2.10: Show that if A and B are finite sets, then $|B^{A}| = |B|^{|A|}$

Suppose $f : A \rightarrow B$. For each $a \in A$ there are $|B|$ choices to assign the value of the function at that point. Then there is total of $|B|^|A|$ choices for assigning specific functions from A to B. $\square$

2.11: In view of exercise 2.10, it isn't unreasonable to use $2^{A}$ to denote the set of functions from arbitrarily set A to a set with 2 elements say $\{0,1\}$. Prove that there is a bijection between $2^{A}$ and the power set of A.

Consider the map $\psi : P(A) \rightarrow 2^{A}$ defined by $B \mapsto I_B : A \rightarrow \{0,1\}$, where $I_B$ is defined as follows $I_B(a) = 1$ if $a \in B$ and $I_B(a) = 0$ if $a \notin B$.  Claim the map $\psi$ above is a bijection.

Suppose $f \in 2^{A}$. Then construct $B \in P(A)$ as follows:

$x \in B \iff f(x) = 1$. Then, $\psi(B) = f$. It is clear that $\psi$ is injective. $\square$