Discrete Mathematics: Injective and Surjective Functions

Injective and Surjective Functions

Prove each of the following statements.

1. \(|X|\le |Y|\) if and only if there exists an injective function $f:X\to Y$. Hint: Proceed by contradiction, and apply the Pigeonhole Principle.





2. If \(g\circ f: X \to Z\) is injective, then \(f: X \to Y\) is injective. Hint: Prove the contrapositive.





3. A function \(f:X\to Y\) is injective if and only if, for any functions \(g,h:W\to X\), if \(f\circ g=f\circ h\), then \(g=h\). Hint: Prove the contrapositive. Define trivial functions \(g,h:W\to X\) such that \(f\) must be injective.





4. If \(f:X\to Y\) is injective and \(A,B \subseteq X\), then
   
   \[ f(A \cap B)=f(A)\cap f(B) \]





5. If \(f:X\to Y\) is injective and \(A \subseteq X\), then
   
   \[ f^{-1}(f(A))=A \]





6. \(f:X\to Y\) is injective if and only if \(f\) has a left inverse \(g:Y\to X\) such that
   
   \[ g\circ f=\mathrm{id}_X \]
   where \(\mathrm{id}_X(x)=x\) for all \(x\in X\). Hint: Define \(g:Y\to X\) using \(f(X)\).





7. \(|X|\ge |Y|\) if and only if there exists a surjective function $f:X\to Y$. Hint: Proceed by contradiction, and apply the Pigeonhole Principle.





8. If \(g\circ f: X \to Z\) is surjective, then \(g: Y \to Z\) is surjective. Hint: Prove the contrapositive.





9. A function \(f:X\to Y\) is surjective if and only if for all functions \(g,h:Y\to Z\), if $g\circ f=h\circ f$ then $g=h$. Hint: Proceed by contradiction using the contrapositive. Assume that \(f\) is not surjective and define two trivial functions \(g,h:Y\to Z\) where \(g\neq h\) and \(g\circ f=h\circ f\).





10. If \(f:X\to Y\) is surjective and \(B\subseteq Y\), then
    
    \[ f\bigl(f^{-1}(B)\bigr)=B \]





11. A function \(f:X\to Y\) is surjective if and only if \(f\) has a right inverse \(g:Y\to X\) such that
    
    \[ f\circ g=\mathrm{id}_Y \]
    where \(\mathrm{id}_Y(y)=y\) for all \(y\in Y\). Hint: Define \(g:Y\to X\) using \(f^{-1}(Y)\), and use the Axiom of Choice.