Discrete Math Problems: VI Injective and Surjective Functions

Injective and Surjective Functions


  1. If \(g\circ f\) is injective, then \(f\) is injective.


    Proof. Assume that \(g\circ f\) is injective. To show that \(f\) is injective, suppose that \(f(x_1)=f(x_2)\) for some \(x_1,x_2 \in X\). Applying \(g\) to both sides gives $g(f(x_1)) = g(f(x_2))$, so \((g\circ f)(x_1) = (g\circ f)(x_2)\). Since \(g\circ f\) is injective, it follows that \(x_1=x_2\). Therefore \(f\) is injective.


  2. 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\).


    Proof. ($\Rightarrow$) First assume that \(f\) is injective and suppose that \(f\circ g=f\circ h\). Let \(w\in W\). Then \((f\circ g)(w)=(f\circ h)(w)\), so \(f(g(w))=f(h(w))\). Since \(f\) is injective, we get \(g(w)=h(w)\). Because this holds for all \(w\in W\), we conclude \(g=h\). ($\Leftarrow$) Conversely, assume that for all functions \(g,h:W\to X\), the condition \(f\circ g=f\circ h\) implies \(g=h\). To show that \(f\) is injective, suppose \(f(a)=f(b)\) for some \(a,b\in X\). Let \(W\) be any singleton set, and choose an element \(x\in W\). Using $W$, we define functions \(g,h:W\to X\) by \(g(x)=a\) and \(h(x)=b\). Then \((f\circ g)(x)=f(a)\) and \((f\circ h)(x)=f(b)\), so \((f\circ g)(x)=(f\circ h)(x)\). By assumption, \(g(x)=h(x)\), which implies \(a=b\). Therefore \(f\) is injective.


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


    Proof. ($\subseteq$) Let \(y \in f(A \cap B)\). Then there exists \(x \in A \cap B\) such that \(f(x)=y\). Since \(x \in A\) and \(x \in B\), it follows that \(y \in f(A)\) and \(y \in f(B)\). Hence \(y \in f(A) \cap f(B)\). ($\supseteq$) Conversely, let \(y \in f(A) \cap f(B)\). Then there exist \(a \in A\) and \(b \in B\) such that \(f(a)=y=f(b)\). Since \(f\) is injective, we conclude \(a=b\). Therefore this common value lies in \(A \cap B\), so \(y \in f(A \cap B)\). Hence \(f(A \cap B)=f(A)\cap f(B)\).


  4. If \(g\circ f\) is surjective, then \(g\) is surjective.


    Proof. Assume that \(g\circ f : X \to Z\) is surjective. To show that \(g : Y \to Z\) is surjective, let \(z \in Z\). Since \(g\circ f\) is surjective, there exists \(x \in X\) such that \((g\circ f)(x)=z\), i.e. \(g(f(x))=z\). Let \(y=f(x)\in Y\). Then \(g(y)=z\). Hence for every \(z \in Z\), there exists \(y \in Y\) such that \(g(y)=z\), so \(g\) is surjective.


  5. 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\).


    Proof. ($\Rightarrow$) First assume that \(f\) is surjective and suppose that \(g\circ f = h\circ f\). Let \(y \in Y\). Since \(f\) is surjective, there exists \(x \in X\) such that \(f(x)=y\). Then $g(y)=g(f(x))=(g\circ f)(x)=(h\circ f)(x)=h(f(x))=h(y)$. Since this holds for all \(y \in Y\), we conclude \(g=h\). ($\Leftarrow$) Conversely, assume that for all functions \(g,h: Y\to Z\), the condition \(g\circ f = h\circ f\) implies \(g=h\). Suppose by contradiction that \(f\) is not surjective, so there exists \(y_0 \in Y\) such that \(y_0 \notin f(X)\). Define functions \(g,h: Y\to Z\) by choosing some \(z_1 \neq z_2\) in \(Z\) and setting


    \[ g(y)=z_1, \quad h(y)= \begin{cases} z_2, & y=y_0 \\ z_1, & y \neq y_0 \end{cases} \]

    Then \(g(y) \neq h(y)\), but for every \(x \in X\), we have \(f(x) \neq y_0\), so \(g(f(x))=h(f(x))=z_1\). Hence \(g\circ f = h\circ f\), contradicting the contrapositive of the assumption. Therefore \(f\) is surjective.


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


    Proof. ($\subseteq$) First, let \(x \in f^{-1}(f(A))\). Then by definition of preimage \(f(x)\in f(A)\), so by definition of image there exists \(a \in A\) such that \(f(x)=f(a)\). Since \(f\) is injective, it follows that \(x=a\). Because \(a \in A\), we conclude \(x \in A\). Thus \(f^{-1}(f(A)) \subseteq A\). ($\supseteq$) Conversely, let \(x \in A\). Then \(f(x)\in f(A)\) by definition of image, so \(x \in f^{-1}(f(A))\) by definition of preimage. Hence \(A \subseteq f^{-1}(f(A))\). Conversely, Therefore $f^{-1}(f(A))=A$.


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


    Proof. ($\subseteq$) Let \(y \in f(f^{-1}(B))\). Then by definition of image there exists \(x \in f^{-1}(B)\) such that \(f(x)=y\). Since \(x \in f^{-1}(B)\), we have \(f(x)\in B\) by definition of preimage, hence \(y \in B\). Therefore \(f(f^{-1}(B)) \subseteq B\). ($\supseteq$) Conversely, let \(y \in B\). Since \(f\) is surjective, there exists \(x \in X\) such that \(f(x)=y\). Because \(y \in B\), this implies \(x \in f^{-1}(B)\) by definition of preimage. Hence \(y=f(x) \in f(f^{-1}(B))\) by definition of image. Therefore \(B \subseteq f(f^{-1}(B))\). Thus $f\bigl(f^{-1}(B)\bigr)=B$.


  8. $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$.


    Proof. $(\Rightarrow)$ Assume that $f$ is injective. For each $y \in f(X)$, there exists a unique $x \in X$ such that $f(x)=y$. Define $g:Y\to X$ by


    \[ g(y)= \begin{cases} x & y=f(x)\text{ for some }x\in X\\ x_0 & y\notin f(X) \end{cases} \]

    Where $x_0\in X$ is fixed. Then for any $x\in X$, we have $f(x)\in f(X)$, so $g(f(x))=x$. Hence $g\circ f=\mathrm{id}_X$, and $g$ is a left inverse of $f$. $(\Leftarrow)$ Conversely, assume that there exists a function $g:Y\to X$ such that $g\circ f=\mathrm{id}_X$. Let $x_1,x_2\in X$ and suppose that $f(x_1)=f(x_2)$. Applying $g$ to both sides gives $g(f(x_1))=g(f(x_2))$. Since $g\circ f=\mathrm{id}_X$, it follows that $x_1=x_2$. Therefore $f$ is injective.


  9. 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$.


    Proof. (\(\Rightarrow\)) Suppose \(f\) is surjective. Then for each \(y \in Y\), there exists \(x \in X\) such that \(f(x)=y\). Define \(g:Y\to X\) by choosing, for each \(y \in Y\), an element \(g(y)\in X\) such that \(f(g(y))=y\). Then for every \(y \in Y\), $(f\circ g)(y)=f(g(y))=y$. Hence \(f\circ g=\mathrm{id}_Y\), so \(g\) is a right inverse of \(f\). (\(\Leftarrow\)) Conversely, suppose there exists \(g:Y\to X\) such that \(f\circ g=\mathrm{id}_Y\). Let \(y \in Y\). Then $y=\mathrm{id}_Y(y)=(f\circ g)(y)=f(g(y))$. Thus \(y\) is in the image of \(f\). Since \(y\) was arbitrary, \(f\) is surjective.


  10. A function \(f:X\to Y\) is bijective if and only if there exists a function \(f^{-1}:Y\to X\) such that $f^{-1}\circ f=\mathrm{id}_X$ and $f\circ f^{-1}=\mathrm{id}_Y$.


    Proof. (\(\Rightarrow\)) Suppose \(f\) is bijective. Since \(f\) is injective, it has a left inverse \(g:Y\to X\) such that $g\circ f=\mathrm{id}_X$. Since \(f\) is surjective, it has a right inverse \(h:Y\to X\) such that $f\circ h=\mathrm{id}_Y$. Then for all \(y \in Y\), $g(y)=g(\mathrm{id}_Y(y))=g(f(h(y)))=(g\circ f)(h(y))=\mathrm{id}_X(h(y))=h(y)$, so \(g=h\). Denote this common function by \(f^{-1}\). Hence $f^{-1}\circ f=\mathrm{id}_X$ and $f\circ f^{-1}=\mathrm{id}_Y$. (\(\Leftarrow\)) Conversely, suppose there exists a function \(f^{-1}:Y\to X\) such that $f^{-1}\circ f=\mathrm{id}_X$ and $f\circ f^{-1}=\mathrm{id}_Y$. If \(f(x_1)=f(x_2)\), then applying \(f^{-1}\) gives $x_1=x_2$, so \(f\) is injective. If \(y \in Y\), then $y=f(f^{-1}(y))$, so \(f\) is surjective. Therefore \(f\) is bijective.


  11. $|A| \leq |B|$ if and only if there exists an injective function \(f:A\to B\).


    Proof. (\(\Rightarrow\)) suppose \(|A|\le |B|\). Then there exists a subset \(C\subseteq B\) such that \(A\) is in bijection with \(C\). That is, there exists a bijection \(g:A\to C\). Define the inclusion map \(i:C\to B\) by \(i(c)=c\). Then \(i\) is injective. Consider the composition $f = i\circ g : A \to B$. Since \(g\) is bijective and \(i\) is injective, their composition \(f\) is injective. Hence there exists an injective function \(f:A\to B\). (\(\Leftarrow\)) Conversely, suppose there exists an injective function \(f:A\to B\). We define the statement \(|A|\le |B|\) to mean that there exists a one-to-one correspondence between \(A\) and a subset of \(B\). Let \(f:A\to B\) be injective and define \(f(A)=\{f(a):a\in A\}\subseteq B\). Then the function $f: A \to f(A)$ is bijective, since it is injective by assumption and surjective by definition of its image. Hence \(A\) is in bijection with a subset of \(B\), so \(|A|\le |B|\).


  12. $|A| \geq |B|$ if and only if there exists a surjective function \(f:A\to B\).


    Proof. (\(\Rightarrow\)) Suppose there exists a surjective function \(f:A\to B\). We show that \(|A|\ge |B|\), meaning there exists an injective function \(g:B\to A\). Since \(f\) is surjective, for each \(b\in B\) choose an element \(g(b)\in A\) such that \(f(g(b))=b\). Then \(g:B\to A\) satisfies \(f\circ g=\mathrm{id}_B\). If \(g(b_1)=g(b_2)\), then applying \(f\) gives $b_1 = f(g(b_1)) = f(g(b_2)) = b_2$, so \(g\) is injective. Hence \(B\) injects into \(A\), so \(|A|\ge |B|\). (\(\Leftarrow\)) Conversely, suppose \(|A|\ge |B|\). Then there exists an injective function \(g:B\to A\). Let \(C=g(B)\subseteq A\). Then \(g:B\to C\) is a bijection, so it has an inverse \(g^{-1}:C\to B\). Define a function \(f:A\to B\) by


    \[ f(a)= \begin{cases} g^{-1}(a) & a\in C\\ b_0 & a\notin C \end{cases} \]

    Where \(b_0\in B\) is fixed. Then for every \(b\in B\), $f(g(b)) = g^{-1}(g(b)) = b$, so \(f\) is surjective. Hence there exists a surjection \(f:A\to B\).


  13. Cantor's Theorem. There is no surjective function \(f:A\to \mathcal{P}(A)\). Equivalently, \(|A| < |\mathcal{P}(A)|\).


    Proof. Suppose, by contradiction, that there exists a surjective function \(f:A\to \mathcal{P}(A)\). We will construct a subset of \(A\) that cannot lie in the image of \(f\). Define \[ S = \{a \in A \mid a \notin f(a)\}. \] Then \(S \subseteq A\), so \(S \in \mathcal{P}(A)\). Since \(f\) is surjective, there exists some \(x \in A\) such that \(f(x)=S\). Now we ask whether \(x \in S\). If \(x \in S\), then by definition of \(S\), we have \(x \notin f(x)\). Since \(f(x)=S\), this implies \(x \notin S\), a contradiction. If \(x \notin S\), then by definition of \(S\), we have \(x \in f(x)\). Since \(f(x)=S\), this implies \(x \in S\), again a contradiction. In both cases we obtain a contradiction, so no such surjective function \(f:A\to \mathcal{P}(A)\) exists. Therefore there is no bijection between \(A\) and \(\mathcal{P}(A)\), and hence \(|A| < |\mathcal{P}(A)|\).

Comments

Post a Comment

Popular posts from this blog

Linear Algebra: I Scalars and Vectors

Scalars and Vectors A scalar is defined as a real number $c \in \mathbb{R}$ with 1 dimensional length $|c|$ and either positive or negative direction on the number line. A vector , denoted $\vec{v}$, is an ordered collection of scalars with dimension $n \geq 1$: Written as a column vector $$\vec{v} =\begin{bmatrix} v_1 \\ \vdots \\ v_n \end{bmatrix}\in \mathbb{R}^n $$ Written as row vector $$\vec{v}^\top =\begin{bmatrix} v_1 & \ldots & v_n \end{bmatrix}\in \mathbb{R}^n$$ Where $\top$ is the transpose operator that exchanges column vectors with row vectors. Note $(\vec{v}^\top)^\top = \vec{v}$. Also, scalars defined as real numbers always equal their own transpose $c^\top = c$. With magnitude $$\|\vec{v}\| = \|\vec{v}^\top\|=\sqrt{v_1^2+\ldots+v_n^2} \geq 0$$ And direction (with the exception of $\vec{0}$ where $\|\vec{0}\|=0$ and $\vec{0}$ has no direction). Row vectors can be treated as transposes of column vectors,...
Read more

Linear Algebra: XI Eigenvalues and Eigenvectors

Eigenvalues and Eigenvectors Let \( A \) be an \( n \) by \( n \) square matrix, defining a linear transformation \( T: \mathbb{R}^n \to \mathbb{R}^n \). A non-zero vector \( \vec{v} \) is called an eigenvector of matrix \( A \) / a linear transformation \( T \) if: $$ T(\vec{v}) = A\vec{v} = \lambda \vec{v} $$ for some scalar $\lambda$, called its eigenvalue , which can be either real or complex even if $A$ has all real values. A matrix \( A \) does not change its eigenvectors' directions since each \( A\vec{v} \) is a scalar multiple of \( \vec{v} \). An eigenvalue tells you the change in magnitude since \( \| \lambda \vec{v} \| = |\lambda| \|\vec{v}\| \), and its sign tells you its orientation. A square matrix $A$ has a zero eigenvalue if and only if $\mathrm{Null}(A)$ is non-trivial. If $\vec{v}$ is an eigenvector of $A$ with eigenvalue $\lambda$, then $c \vec{v}$ ($c \neq 0$) is also an eigenvector of $A$ with eigenvalue $\lambda$. The eig...
Read more

Linear Algebra: VIII The Fundamental Theorem of Linear Algebra

The Fundamental Theorem of Linear Algebra Consider a linear transformation $T: \mathbb{R}^n \rightarrow \mathbb{R}^m$ defined by $T(\vec{x}) = A\vec{x}$ where $A$ is an $m$ by $n$ matrix. The row echelon form and reduced row echelon form of a matrix described below are products of $m$ by $m$ elementary matrices (row operations) times $A$ / compositions of linear transformations described by these elementary matrices with $T$. Row Echelon Form (REF) An $m$ by $n$ matrix $A$ is in row echelon form , denoted $\text{REF}(A)$, if: Each row has a non-zero leading entry called its pivot . The next pivot is to the right of the previous pivot above it. Every entry below each pivot is zero. All zero rows are at the bottom. Leading variables of $A$ correspond to pivot columns in $\mathrm{REF}(A)$, and the corresponding columns of $A$ form a linearly independent set. Free variables of $A$ correspond to columns without a pivot in $\mathrm{REF}(A)...
Read more