I am struggling with this quite simple problem:
Let $A$, $B$ and $C$ be sets ($\neq \emptyset$) and let $f:A \to B$ be a fixed application. Let be $C^A=\{h|h:A \to C \}$ and $C^B=\{g|g:A \to C \}$. Let $\phi: C^B \to C^A$ be the application s.t. $\phi(g)=g \circ f, \forall g\in C^B$.
Prove: if $f$ is surjective then $\phi$ is injective; if $f$ is injective then $\phi$ is surjective.
For the first one I think this solution could be good:
- Let $f$ be surjective then $\exists h:B \to A$ s.t.$f \circ h = \iota_B$.
Let $g_1, g_2 \in C^B$ be s.t $\phi (g_1) = \phi (g_2)$ (that implies $g_1 \circ f = g_2 \circ f$). So: $g_1 =g_1\circ \iota_B=g_1 \circ (f \circ h)= (g_1 \circ f) \circ h =(g_2 \circ f) \circ h = g_2 \circ (f \circ h) = g_2 \circ \iota_B = g_2$
How to prove that if $f$ is injective $\Rightarrow \phi$ is surjective? I thought: if $f$ is injective then $\exists h:B \to A$ s.t. $h \circ f= \iota_A$ and that if $g$ is surjective then $\phi(g) =g \circ f$ is surjective, but how to correlate them?
Best Answer
As you said, if $f$ is injective, then there exists $h : B \to A$ such that $h \circ f = \iota_A$. Given $g \in C^A$, you see that $g \circ h \in C^B$ and $\phi(g \circ h) = g \circ h \circ f = g$.
Added:
Adayah has pointed out that we used $A \ne \emptyset$. But in fact the assumption in the question is $A, B, C \ne \emptyset$.
However, we can do everything under the assumption $C \ne \emptyset$ without any assumption on $A, B$. $A, B \ne \emptyset$ has been treated.
The empty set has the feature that there exists exactly one function $\emptyset \to X$, where $X$ is any set (the "empty" function $\emptyset \to X$), which btw is automatically injective.
The are exactly two cases in which one of $A, B$ is empty:
(1) $A = \emptyset \to B = \emptyset$ which is bijective.
(2) $A = \emptyset \to B \ne \emptyset$ which is injective but not surjective.
Since $C^\emptyset$ has exactly one element and $C^B$ is non-empty, we see that $\phi$ is bijective in case (1) and surjective in case (2).
What if $C = \emptyset$? If $A, B \ne \emptyset$, then $C^A , C^B = \emptyset$ and $\phi$ is a bijection. If $A = B = \emptyset$, then $\phi$ is also a bijection. Only in case $A = \emptyset, B \ne \emptyset$ we see that $\phi$ is not surjective although $f$ is injective.