Definition 1.2.1. Let \(A\) and \(B\) be sets. A rule of assignment \(R\) is a subset of the product \(A\times B\) such that
\[\forall x\in A\ \forall y_1,y_2\in B\ (((x,y_1)\in R \land (x,y_2)\in R) \Rightarrow y_1=y_2).\]The domain of \(R\) is the set \(\lbrace x : \exists y \in B\ ((x,y)\in R)\rbrace,\) and the image of \(R\) is the set \(\lbrace y : \exists x \in A \ ((x,y)\in R)\rbrace.\)
Definition 1.2.2. A rule of assignment \(R\) whose domain is \(A,\) together with a set \(B\) that contains the image of \(R\) is a function from \(A\) to \(B.\) When we denote the function as \(f,\) we write
\[f: A\longrightarrow B,\]The domain \(A\) of \(R\) is the domain of \(f,\) and the image of \(R\) is the image of \(f;\) the set \(B\) is the codomain of \(f.\) If \(a\in A,\) the value of \(f\) at \(a\) is the unique element of \(B\) to which \(R\) assigns \(a.\)
Definition 1.2.3. Let \(f:A\to B\) and \(A_0\subseteq A\) be given. The restriction of \(f\) to \(A_0\) is the function with codomain \(B\) whose rule is \(\lbrace (x,f(x)) : x\in A_0 \rbrace.\) It is denoted by \(f|_{A_0}.\)
Definition 1.2.4. Let \(f:A\to B\) and \(g:B\to C\) be given. The composite of \(f\) and \(g\) is the function \(g \circ f : A\to C\) such that \((g\circ f)(x) = g(f(x)).\)
Definition 1.2.5. A function \(f:A\to B\) is injective if
\[\forall x_1,x_2\in A\ (f(x_1)=f(x_2) \Rightarrow x_1=x_2),\]and surjective if
\[\forall y\in B\, \exists x\in A\ (y=f(x)).\]If \(f\) is both injective and surjective then \(f\) is said to be bijective.
Injectivity of \(f\) only depends on the rule of \(f,\) while surjectivity depends on both the rule of \(f\) and the codomain of \(f,\) The composite of two injective functions is injective, and the composite of two surjective functions is surjective. It follows that the composite of two bijective functions is bijective.
Definition 1.2.6. Let a function \(f:A\to B\) be bijective. Then the inverse of \(f\) is the function \(f^{-1}:B\to A\) such that \(f^{-1}(y)=x\) where \(f(x)=y.\)
Lemma 1.2.7. Let \(f:A\to B.\) If there are functions \(g:B\to A\) and \(h:B\to A\) such that \(g(f(x))=x\) for all \(x\in A\) and \(f(h(y))=y\) for all \(y\in B,\) then \(f\) is bijective and \(g=h=f^{-1}.\)
Proof. Let \(a,a'\in A.\) We have \((f(a),a)\in g\) and \((f(a'),a')\in g.\) Thus, if \(f(a)=f(a')\) then \(a=a',\) by Definition 1.2.1. Therefore \(f\) is injective. Let \(b\in B.\) We have \((h(b),b)\in f.\) Thus there exists \(a\in A\) such that \((a,b)\in f.\) Therefore \(f\) is surjective. Since \(f\) is both injective and surjective, \(f\) is bijective.
Let \(b\in B.\) Then there exists \(a\) such that \(f(a)=b.\) Since \(g(b)=g(f(a))=a,\) \(g\) is the inverse of \(f.\) Since \(f(a)=b\) and \(f(h(b))=b,\) by the definition of injectivity, \(a=h(b).\) Thus \(h\) is also the inverse of \(f.\) \(\square\)
Definition 1.2.8. Let \(f:A\to B\) and \(A_0\subseteq A.\) The image of \(A_0\) under \(f\) is the set \(f[A_0]\) defined by
\[f[A_0]=\lbrace y \in B : \exists x\in A_0 \ (y=f(x)) \rbrace.\]If \(B_0\subseteq B,\) the preimage of \(B_0\) under \(f\) is the set \(f^{-1}[B_0]\) defined by
\[f^{-1}[B_0] = \lbrace x \in A : f(x)\in B_0 \rbrace .\]We can also define set-level operations of the image operation and the preimage operation from the above.
Theorem 1.2.9. Let \(f:A\to B\) and let \(A_i\subseteq A\) for \(i=0\) and \(i=1.\) The image operation \(f\) preserves only the inclusion and union operation. That is, the followings hold.
- \(A_0\subseteq A_1 \Rightarrow f[A_0]\subseteq f[A_1].\)
- \(f[A_0\cup A_1]=f[A_0]\cup f[A_1].\)
- \(f[A_0\cap A_1] \subseteq f[A_0]\cap f[A_1],\) the equality holds if \(f\) is injective.
- \(f[A_0] - f[A_1]\subseteq f[A_0-A_1],\) the equality holds if \(f\) is injective.
Proof.
(1) If \(b\in f[A_0],\) there exists \(a\in A_0\) such that \(f(a)=b.\) Since \(A_0\subseteq A_1,\) it follows that \(a\in A_1.\) Thus \(b=f(a)\in f[A_1].\) Therefore \(f[A_0]\subseteq f[A_1].\)
(2) Suppose that \(b\in f[A_0\cup A_1].\) Then there exists \(a\in A_0\cup A_1\) such that \(f(a)=b.\) Without loss of generality, let \(a\in A_0.\) It follows that \(b=f(a)\in f[A_0],\) so that \(b\in f[A_0]\cup f[A_1].\) Thus \(f[A_0\cup A_1]\subseteq f[A_0]\cup f[A_1].\)
Conversely, we suppose that \(b\in f[A_0]\cup f[A_1].\) Without loss of generality, let \(b\in f[A_0].\) Then there exists \(a\in A_0\) such that \(f(a)=b.\) Since \(a\in A_0\cup A_1,\) it follows that \(b=f(a)\in A_0\cup A_1.\) Thus \(f[A_0]\cup f[A_1]\subseteq f[A_0\cup A_1].\) Consequently, \(f[A_0\cup A_1]=f[A_0]\cup f[A_1].\)
(3) Suppose that \(b\in f[A_0\cap A_1].\) Then there exists \(a\in A_0\cap A_1\) such that \(f(a)=b.\) Since \(a\in A_0\) and \(a\in A_1,\) it follows that \(f(a)\in f[A_0]\) and \(f(a)\in F[A_1].\) Thus \(b=f(a)\in f[A_0]\cap f[A_1],\) and, consequently, \(f[A_0\cap A_1] \subseteq f[A_0]\cap f[A_1].\)
We now suppose that \(f\) is injective. If \(b\in f[A_0]\cap f[A_1],\) then there exists exactly one \(a\in A\) such that \(f(a)=b.\) Since \(a\in A_0\) and \(a\in A_1,\) it follows that \(a\in A_0\cap A_1.\) Therefore \(f(a)\in f[A_0\cap A_1],\) and, thus, \(f[A_0]\cap f[A_1]\subseteq f[A_0\cap A_1].\) Given that \(f[A_0\cap A_1] \subseteq f[A_0]\cap f[A_1],\) we finally have \(f[A_0\cap A_1] = f[A_0]\cap f[A_1].\)
(4) Suppose that \(b\in f[A_0] - f[A_1].\) Then \(b\in f[A_0]\) and \(b\notin f[A_1].\) It follows that there exists \(a\in A_0\) such that \(f(a)=b,\) and \(a\notin A_1.\) Thus \(a\in A_0-A_1.\) Therefore \(b=f(a)\in f[A_0-A_1],\) and, consequently, \(f[A_0] - f[A_1]\subseteq f[A_0-A_1].\)
We now suppose that \(f\) is injective and \(b\in f[A_0-A_1].\) Then there exists exactly one \(a\in A\) such that \(f(a)=b.\) That is, \(a\in A_0-A_1.\) It follows that \(a\in A_0\) and \(a\notin A_1.\) Thus \(b\in f[A_0]\) and \(b\notin f[A_1].\) Therefore \(b\in f[A_0] - f[A_1],\) and, thus, \(f[A_0-A_1]\subseteq f[A_0] - f[A_1].\) Given that \(f[A_0] - f[A_1]\subseteq f[A_0-A_1],\) we finally have \(f[A_0] - f[A_1]=f[A_0 - A_1].\)\(\square\)
Theorem 1.2.10. Let \(f:A\to B\) and let \(B_i\subseteq B\) for \(i=0\) and \(i=1.\) The preimage operation \(f^{-1}\) preserves the operations of union, intersection, and difference. It also preserves the inclusion. That is, the followings hold.
- \(B_0\subseteq B_1 \Rightarrow f^{-1}[B_0]\subseteq f^{-1}[B_1].\)
- \(f^{-1}[B_0\cup B_1]=f^{-1}[B_0]\cup f^{-1}[B_1].\)
- \(f^{-1}[B_0\cap B_1] = f^{-1}[B_0]\cap f^{-1}[B_1].\)
- \(f^{-1}[B_0] - f[B_1] = f^{-1}[B_0-B_1].\)
Proof. It is not quite different from in proving Theorem 1.2.9 to prove this.
Theorem 1.2.10. Let \(f:A\to B, A_0\subseteq A,\) and \(B_0\subseteq B.\) Then
\[A_0\subseteq f^{-1}[f[A_0]]\quad \text{and} \quad f[f^{-1}[B_0]]\subseteq B_0.\]The first inclusion is an equality if \(f\) is injective, and the second is an equality if \(f\) is surjective.
Proof. If \(a\in A_0\) then \(f(a)\in f[A_0].\) Thus all the elements of \(A\) whose image under \(f\) is the same as \(f(a)\) are elements of \(f^{-1}[f[A_0]],\) by Definition 1.2.8. Thus \(a\in f^{-1}[f[A_0]].\) Consequently,
We now suppose that \(f\) is injective. If \(a\in f^{-1}[f[A_0]]\) then \(f(a)\in f[A_0].\) That is, there exists \(a'\in A_0\) such that \(f(a')\in A_0\) such that \(f(a')=f(a).\) Since \(f\) is injective, \(a'=a,\) thus \(a\in A_0.\) Therefore, \(f^{-1}[f[A_0]] \subseteq A_0.\) Given \((\ast),\) it follows that \(f^{-1}[f[A_0]] = A_0.\)
If \(b\in f[f^{-1}[B_0]]\) then there exists \(a\in f^{-1}[B_0]\) such that \(f(a)=b.\) Thus \(f(a)\in B_0.\) Since \(f(a)=b,b\in B_0.\) Consequently,
We now suppose that \(f\) is surjective. Thus there exists \(a\in A\) such that \(f(a)=b\) if \(b\in B_0.\) By Definition 1.2.8, \(a\in f^{-1}[B_0],\) thus \(f(a)\in f[f^{-1}[B_0]].\) Therefore \(B_0 \subseteq f[f^{-1}[B_0]].\) Given \((\ast \ast ),\) it follows that \(f[f^{-1}[B_0]]= B_0.\) \(\square\)
References
- Munkres, J. R. (2000). Topology (2nd ed.). Pearson.