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$ , isassumed 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$ . Thenthe 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 definitionof 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$ isinjective.

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.

(proof by contradiction)Suppose that $f$ were not injective. Then there would exist $x,y\\in A$ such that $f(x)=f(y)$ but $x\eq y$ . Composing with $g$ , we wouldthen have $g(f(x))=g(f(y))$ . However, since $g\\circ f$ is assumedinjective, this would imply that $x=y$ , which contradicts a previousstatement. 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$ .¹¹In this equation, the symbols “ $f$ ” and“ $f^{-1}$ ” as applied to sets denote the direct image and the inverseimage, 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 thatneed to be shown is that $f^{-1}(f(C))\\subseteq C$ . Assume thecontrary. Then there would exist $x\\in f^{-1}(f(C))$ such that $x\otin 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 clearlybelong to both $f(C)$ and $f(D)$ . Hence, all that needs to be shown isthat $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)$ .∎

单词	PropertiesOfInjectiveFunctions
释义	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$ , isassumed 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$ . Thenthe 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 definitionof 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$ isinjective. 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. (proof by contradiction)Suppose that $f$ were not injective. Then there would exist $x,y\\in A$ such that $f(x)=f(y)$ but $x\eq y$ . Composing with $g$ , we wouldthen have $g(f(x))=g(f(y))$ . However, since $g\\circ f$ is assumedinjective, this would imply that $x=y$ , which contradicts a previousstatement. 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$ .¹¹In this equation, the symbols “ $f$ ” and“ $f^{-1}$ ” as applied to sets denote the direct image and the inverseimage, 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 thatneed to be shown is that $f^{-1}(f(C))\\subseteq C$ . Assume thecontrary. Then there would exist $x\\in f^{-1}(f(C))$ such that $x\otin 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 clearlybelong to both $f(C)$ and $f(D)$ . Hence, all that needs to be shown isthat $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)$ .∎
随便看	ProofOfDeltaSystemLemma proof of delta system lemma proof of De l’Hôpital’s rule ProofOfDesarguesTheorem proof of Desargues’ theorem ProofOfDeterminantLowerBoundOfAStrictDiagonallyDominantMatrix proof of determinant lower bound of a strict diagonally dominant matrix ProofOfDeterminantOfTheVandermondeMatrix proof of determinant of the Vandermonde matrix ProofOfDiamondIsEquivalentToclubsuitAndContinuumHypothesis ProofOfDinisTheorem proof of Dini’s theorem ProofOfDivergenceOfHarmonicSeriesbyGroupingTerms proof of divergence of harmonic series (by grouping terms) ProofOfDivergenceOfHarmonicSeriesbySplittingOddAndEvenTerms proof of divergence of harmonic series (by splitting odd and even terms) ProofOfDivisionAlgorithmForIntegers proof of division algorithm for integers ProofOfDominatedConvergenceTheorem proof of dominated convergence theorem proof of dominated convergence theorem ProofOfDominatedConvergenceTheorem1 ProofOfDoobsInequalities proof of Doob’s inequalities ProofOfDoubleAngleIdentity