text: # properties of injective functions
  
  ###### Theorem 1.
  
  Suppose $A,B,C$ are sets and $f\colon A\to B$, $g\colon B\to C$ are injective functions. Then the composition $g\circ f$ is an injection.
  
  ###### Proof.
  
  Suppose that $(g\circ f)(x)=(g\circ f)(y)$ for some $x,y\in A$. By definition of composition, $g(f(x))=g(f(y))$. Since $g$, is assumed injective, $f(x)=f(y)$. Since $f$ is also assumed injective, $x=y$. Therefore, $(g\circ f)(x)=(g\circ f)(y)$ implies $x=y$, so $g\circ f$ is injective. ∎
  
  ###### Theorem 2.
  
  Suppose $f\colon A\to B$ is an injection, and $C\subseteq A$. Then the restriction $f|_{C}\colon C\to B$ is an injection.
  
  ###### Proof.
  
  Suppose $(f|_{C})(x)=(f|_{C})(y)$ for some $x,y\in C$. By definition of restriction, $f(x)=f(y)$. Since $f$ is assumed injective this, in turn, implies that $x=y$. Thus, $f|_{C}$ is also injective. ∎
  
  ###### Theorem 3.
  
  Suppose $A,B,C$ are sets and that the functions $f\colon A\to B$ and $g\colon B\to C$ are such that $g\circ f$ is injective. Then $f$ is injective.
  
  ###### Proof.
  
  (direct proof) Let $x,y\in A$ be such that $f(x)=f(y)$. Then $g(f(x))=g(f(y))$. But as $g\circ f$ is injective, this implies that $x=y$, hence $f$ is also injective. ∎
  
  ###### Proof.
  
  () Suppose that $f$ were not injective. Then there would exist $x,y\in A$ such that $f(x)=f(y)$ but $x\neq y$. Composing with $g$, we would then have $g(f(x))=g(f(y))$. However, since $g\circ f$ is assumed injective, this would imply that $x=y$, which contradicts a previous statement. Hence $f$ must be injective. ∎
  
  ###### Theorem 4.
  
  Suppose $f\colon A\to B$ is an injection. Then, for all $C\subseteq A$, it is the case that $f^{-1}(f(C))=C$.11In this equation, the symbols “$f$” and “$f^{-1}$” as applied to sets denote the direct image and the inverse image, respectively
  
  ###### Proof.
  
  It follows from the definition of $f^{-1}$ that $C\subseteq f^{-1}(f(C))$, whether or not $f$ happens to be injective. Hence, all that need to be shown is that $f^{-1}(f(C))\subseteq C$. Assume the contrary. Then there would exist $x\in f^{-1}(f(C))$ such that $x\notin C$. By defintion, $x\in f^{-1}(f(C))$ means $f(x)\in f(C)$, so there exists $y\in A$ such that $f(x)=f(y)$. Since $f$ is injective, one would have $x=y$, which is impossible because $y$ is supposed to belong to $C$ but $x$ is not supposed to belong to $C$. ∎
  
  ###### Theorem 5.
  
  Suppose $f\colon A\to B$ is an injection. Then, for all $C,D\subseteq A$, it is the case that $f(C\cap D)=f(C)\cap f(D)$.
  
  ###### Proof.
  
  Whether or not $f$ is injective, one has $f(C\cap D)\subseteq f(C)\cap f(D)$; if $x$ belongs to both $C$ and $D$, then $f(x)$ will clearly belong to both $f(C)$ and $f(D)$. Hence, all that needs to be shown is that $f(C)\cap f(D)\subseteq f(C\cap D)$. Let $x$ be an element of $B$ which belongs to both $f(C)$ and $f(D)$. Then, there exists $y\in C$ such that $f(y)=x$ and $z\in D$ such that $f(z)=x$. Since $f(y)=f(z)$ and $f$ is injective, $y=z$, so $y\in C\cap D$, hence $x\in f(C\cap D)$. ∎
  
  Title properties of injective functions PropertiesOfInjectiveFunctions 2013-03-22 16:40:20 2013-03-22 16:40:20 rspuzio (6075) rspuzio (6075) 22 rspuzio (6075) Theorem msc 03E20 msc 03E99
explanation: The document is a collection of theorems and proofs related to the properties of injective functions. It does not contain any explicit questions or question-and-answer pairs.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # properties of injective functions
  
  ###### Theorem 1.
  
  Suppose $A,B,C$ are sets and $f\colon A\to B$, $g\colon B\to C$ are injective functions. Then the composition $g\circ f$ is an injection.
  
  ###### Proof.
  
  Suppose that $(g\circ f)(x)=(g\circ f)(y)$ for some $x,y\in A$. By definition of composition, $g(f(x))=g(f(y))$. Since $g$, is assumed injective, $f(x)=f(y)$. Since $f$ is also assumed injective, $x=y$. Therefore, $(g\circ f)(x)=(g\circ f)(y)$ implies $x=y$, so $g\circ f$ is injective. ∎
  
  ###### Theorem 2.
  
  Suppose $f\colon A\to B$ is an injection, and $C\subseteq A$. Then the restriction $f|_{C}\colon C\to B$ is an injection.
  
  ###### Proof.
  
  Suppose $(f|_{C})(x)=(f|_{C})(y)$ for some $x,y\in C$. By definition of restriction, $f(x)=f(y)$. Since $f$ is assumed injective this, in turn, implies that $x=y$. Thus, $f|_{C}$ is also injective. ∎
  
  ###### Theorem 3.
  
  Suppose $A,B,C$ are sets and that the functions $f\colon A\to B$ and $g\colon B\to C$ are such that $g\circ f$ is injective. Then $f$ is injective.
  
  ###### Proof.
  
  (direct proof) Let $x,y\in A$ be such that $f(x)=f(y)$. Then $g(f(x))=g(f(y))$. But as $g\circ f$ is injective, this implies that $x=y$, hence $f$ is also injective. ∎
  
  ###### Proof.
  
  () Suppose that $f$ were not injective. Then there would exist $x,y\in A$ such that $f(x)=f(y)$ but $x\neq y$. Composing with $g$, we would then have $g(f(x))=g(f(y))$. However, since $g\circ f$ is assumed injective, this would imply that $x=y$, which contradicts a previous statement. Hence $f$ must be injective. ∎
  
  ###### Theorem 4.
  
  Suppose $f\colon A\to B$ is an injection. Then, for all $C\subseteq A$, it is the case that $f^{-1}(f(C))=C$.11In this equation, the symbols “$f$” and “$f^{-1}$” as applied to sets denote the direct image and the inverse image, respectively
  
  ###### Proof.
  
  It follows from the definition of $f^{-1}$ that $C\subseteq f^{-1}(f(C))$, whether or not $f$ happens to be injective. Hence, all that need to be shown is that $f^{-1}(f(C))\subseteq C$. Assume the contrary. Then there would exist $x\in f^{-1}(f(C))$ such that $x\notin C$. By defintion, $x\in f^{-1}(f(C))$ means $f(x)\in f(C)$, so there exists $y\in A$ such that $f(x)=f(y)$. Since $f$ is injective, one would have $x=y$, which is impossible because $y$ is supposed to belong to $C$ but $x$ is not supposed to belong to $C$. ∎
  
  ###### Theorem 5.
  
  Suppose $f\colon A\to B$ is an injection. Then, for all $C,D\subseteq A$, it is the case that $f(C\cap D)=f(C)\cap f(D)$.
  
  ###### Proof.
  
  Whether or not $f$ is injective, one has $f(C\cap D)\subseteq f(C)\cap f(D)$; if $x$ belongs to both $C$ and $D$, then $f(x)$ will clearly belong to both $f(C)$ and $f(D)$. Hence, all that needs to be shown is that $f(C)\cap f(D)\subseteq f(C\cap D)$. Let $x$ be an element of $B$ which belongs to both $f(C)$ and $f(D)$. Then, there exists $y\in C$ such that $f(y)=x$ and $z\in D$ such that $f(z)=x$. Since $f(y)=f(z)$ and $f$ is injective, $y=z$, so $y\in C\cap D$, hence $x\in f(C\cap D)$. ∎
  
  Title properties of injective functions PropertiesOfInjectiveFunctions 2013-03-22 16:40:20 2013-03-22 16:40:20 rspuzio (6075) rspuzio (6075) 22 rspuzio (6075) Theorem msc 03E20 msc 03E99
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document is a collection of theorems and proofs related to the properties of injective functions. It does not contain any explicit questions or question-and-answer pairs.
  
  Label: no-question