1.2  Functions

Definition 1.2.1. Let \(X\) and \(Y\) be sets. A rule of assignment \(R\) is a subset of the product \(X\times Y\) such that for all \(x\in X\) and for all \(y_1,y_2\in Y\)

\[(x,y_1)\in R \quad \text{and} \quad (x,y_2)\in R\ \Longrightarrow\ y_1=y_2.\]

The domain of \(R\) is the set

\[\lbrace x : \exists y \in Y\ ((x,y)\in R)\rbrace,\]

and the image of \(R\) is the set

\[\lbrace y : \exists x \in X \ ((x,y)\in R)\rbrace.\]

Definition 1.2.2. A rule of assignment \(R\) whose domain is \(X,\) together with a set \(Y\) that contains the image of \(R\) is called a function from \(X\) to \(Y.\) If \(f\) is a function from \(X\) to \(Y\), we write

\[f\colon X\longrightarrow Y.\]

The set \(X\) is called the domain of \(f\); the image of \(R\) is called the image of \(f\), denoted by \(\operatorname{im}f\); the set \(Y\) is called the codomain of \(f\). If \(x\in X,\) then the unique element of \(Y\) to which \(R\) assigns \(x\) is called the value of \(f\) at \(x\).

Definition 1.2.3. Let \(X\) be a set. The identity function on \(X\) is the function \(\operatorname{id}_X\colon X \to X\) such that \(\operatorname{id}_X(x) =x\) for all \(x\in X\).

Definition 1.2.4. Let \(f\colon X\to Y\) and \(A\subseteq X\) be given. The restriction of \(f\) to \(A\) is the function \(f|_A\colon A\to Y\) whose rule is

\[\lbrace (x,f(x)) : x\in A \rbrace.\]

Definition 1.2.5. Let \(f\colon X\to Y\) and \(g\colon Y\to Z\) be given. The composite of \(f\) and \(g\) is the function \(g \circ f\colon X\to Z\) such that for all \(x\in X\)

\[(g\circ f)(x) = g(f(x)).\]

Definition 1.2.6. A function \(f\colon X\to Y\) is injective or an injection if for all \(x_1,x_2\in X\),

\[f(x_1)=f(x_2)\ \Longrightarrow \ x_1=x_2.\]

A function \(f\colon X\to Y\) is surjective or a surjection if for any \(y\in Y\), there exists \(x\in X\) such that

\[f(x) = y.\]

If a function is both injective and surjective then it 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 injections is injective, and the composite of two surjections is surjective. It follows that the composite of two bijections is bijective.

Definition 1.2.7. Let a function \(f\colon X\to Y\) be bijective. Then the inverse of \(f\) is the function \(f^{-1}\colon Y\to X\) such that \(f^{-1}(y)=x\) where \(f(x)=y.\)

Lemma 1.2.8. Let \(f\colon X\to Y.\) If there are functions \(g\colon Y\to X\) and \(h\colon Y\to X\) such that \(g(f(x))=x\) for all \(x\in X\) and \(f(h(y))=y\) for all \(y\in Y,\) then \(f\) is bijective and \(g=h=f^{-1}.\)

Proof. Let \(x,x'\in X.\) If \(f(x)=f(x'),\) then \(x=g(f(x))=g(f(x'))=x'.\) Therefore \(f\) is injective. For every \(y\in Y,\) we have \(f(h(y))=y,\) so \(f\) is surjective. Hence \(f\) is bijective. Now let \(y\in Y.\) Since \(f\) is surjective, there exists \(x\in X\) such that \(f(x)=y.\) Then \(g(y)=g(f(x))=x.\) Also, \(f(h(y))=y=f(x),\) so injectivity gives \(h(y)=x.\) Thus \(g(y)=h(y)=f^{-1}(y)\) for every \(y\in Y,\) and therefore \(g=h=f^{-1}.\) \(\square\)

Definition 1.2.9. Let \(f\colon X\to Y\) and \(A\subseteq X.\) The image of \(A\) under \(f\) is the set

\[f(A)=\lbrace y \in Y : \exists x\in A \ (y=f(x)) \rbrace.\]

If \(C\subseteq Y,\) the preimage of \(C\) under \(f\) is the set

\[f^{-1}(C) = \lbrace x \in X : f(x)\in C \rbrace .\]

We now describe how images and preimages interact with set operations.

Theorem 1.2.10. Let \(f\colon X\to Y,\) and let \(A,B\subseteq X.\) Then the following statements hold:

  1. If \(A\subseteq B,\) then \(f(A)\subseteq f(B).\)
  2. \(f(A\cup B)=f(A)\cup f(B).\)
  3. The inclusion \(f(A\cap B)\subseteq f(A)\cap f(B)\) holds; the equality holds if \(f\) is injective.
  4. The inclusion \(f(A)\setminus f(B)\subseteq f(A\setminus B)\) holds; the equality holds if \(f\) is injective.

Proof. (1) Suppose that \(y\in f(A).\) Then \(y=f(x)\) for some \(x\in A.\) Since \(A\subseteq B,\) we have \(x\in B,\) and hence \(y\in f(B).\) (2) Suppose that \(y\in f(A\cup B).\) Then \(y=f(x)\) for some \(x\in A\cup B.\) Thus \(x\in A\) or \(x\in B,\) so \(y\in f(A)\cup f(B).\) Conversely, if \(y\in f(A)\cup f(B),\) then \(y=f(x)\) for some \(x\in A\) or some \(x\in B.\) Hence \(x\in A\cup B,\) and therefore \(y\in f(A\cup B).\) (3) If \(y\in f(A\cap B),\) then \(y=f(x)\) for some \(x\in A\cap B.\) Thus \(y\in f(A)\) and \(y\in f(B),\) which proves that \(f(A\cap B)\subseteq f(A)\cap f(B).\) Now suppose that \(f\) is injective and \(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, \(a=b,\) so \(a\in A\cap B.\) Hence \(y\in f(A\cap B).\) (4) Suppose that \(y\in f(A)\setminus f(B).\) Then \(y=f(x)\) for some \(x\in A.\) If \(x\in B,\) then \(y\in f(B),\) a contradiction. Therefore \(x\in A\setminus B,\) and hence \(y\in f(A\setminus B).\) Now suppose that \(f\) is injective and \(y\in f(A\setminus B).\) Then \(y=f(x)\) for some \(x\in A\setminus B,\) so \(y\in f(A).\) If \(y\in f(B),\) then \(y=f(x')\) for some \(x'\in B.\) Injectivity gives \(x=x',\) contradicting \(x\notin B.\) Thus \(y\notin f(B),\) and therefore \(y\in f(A)\setminus f(B).\)\(\square\)

Theorem 1.2.11. Let \(f\colon X\to Y,\) and let \(C,D\subseteq Y.\) Then the following statements hold:

  1. If \(C\subseteq D,\) then \(f^{-1}(C)\subseteq f^{-1}(D).\)
  2. \(f^{-1}(C\cup D)=f^{-1}(C)\cup f^{-1}(D).\)
  3. \(f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D).\)
  4. \(f^{-1}(C\setminus D)=f^{-1}(C)\setminus f^{-1}(D).\)

Proof. Statement (1) follows immediately from the definition of preimage. For each \(x\in X,\)

\[\begin{align} x\in f^{-1}(C\cup D) &\Longleftrightarrow f(x)\in C\cup D \Longleftrightarrow x\in f^{-1}(C)\cup f^{-1}(D),\\ x\in f^{-1}(C\cap D) &\Longleftrightarrow f(x)\in C\cap D \Longleftrightarrow x\in f^{-1}(C)\cap f^{-1}(D),\\ x\in f^{-1}(C\setminus D) &\Longleftrightarrow f(x)\in C\setminus D \Longleftrightarrow x\in f^{-1}(C)\setminus f^{-1}(D). \end{align}\]

Thus (2), (3), and (4) follow by extensionality.\(\square\)

Theorem 1.2.12. Let \(f\colon X\to Y,\) let \(A\subseteq X,\) and let \(C\subseteq Y.\) Then

\[A\subseteq f^{-1}(f(A))\quad \text{and} \quad f(f^{-1}(C))\subseteq C.\]

The first inclusion is an equality if \(f\) is injective, and the second is an equality if \(f\) is surjective.

Proof. If \(x\in A,\) then \(f(x)\in f(A),\) and hence \(x\in f^{-1}(f(A)).\) Therefore \(A\subseteq f^{-1}(f(A)).\) Now suppose that \(f\) is injective and \(x\in f^{-1}(f(A)).\) Then \(f(x)\in f(A),\) so there exists \(a\in A\) such that \(f(a)=f(x).\) Injectivity gives \(a=x,\) and therefore \(x\in A.\) Thus \(f^{-1}(f(A))\subseteq A,\) proving that \(f^{-1}(f(A))=A.\) If \(y\in f(f^{-1}(C)),\) then \(y=f(x)\) for some \(x\in f^{-1}(C).\) Hence \(f(x)\in C,\) so \(y\in C.\) Therefore \(f(f^{-1}(C))\subseteq C.\) Finally, suppose that \(f\) is surjective and \(y\in C.\) Then \(y=f(x)\) for some \(x\in X.\) Since \(f(x)\in C,\) we have \(x\in f^{-1}(C),\) and hence \(y\in f(f^{-1}(C)).\) Thus \(C\subseteq f(f^{-1}(C)),\) proving that \(f(f^{-1}(C))=C.\) \(\square\)