Maps

Definition

Definition: a relation \(f\) from a set \(A\) to a set \(B\) is called a map or function from \(A\) to \(B\) if for each \(a \in A\) there is one and only one \(b \in B\) with \(afb\).

• To indicate that \(f\) is a map from \(A\) to \(B\) we may write \(f:A \to B\).
• If \(a \in A\) and \(b \in B\) is the unique element with \(afb\) then we may write \(b=f(a)\).
• The set of all maps from \(A\) to \(B\) is denoted by \(B^A\).
• A partial map \(f\) from a \(A\) to \(B\) with the property that for each \(a \in A\) there is at most one \(b \in B\) with \(afb\).

For example, let \(f: \mathbb{R} \to \mathbb{R}\) with \(f(x) = \sqrt{x}\) for all \(x \in \mathbb{R}\) is a partial map, since not all of \(\mathbb{R}\) is mapped.

Proposition: let \(f: A \to B\) and \(g: B \to C\) be maps, then the composition \(g\) after \(f\): \(g \circ f = f;g\) is a map from \(A\) to \(C\).

Proof:

Let \(a \in A\) then \(g(f(a))\) is an element in \(C\) in relation \(f;g\) with \(a\). If \(c \in C\) is an element in \(C\) that is in relation \(f;g\) with \(a\), then there is a \(b \in B\) with \(afb\) and \(bgc\). But then, as \(f\) is a map, \(b=f(a)\) and as \(g\) is a map \(c=g(b)\). Hence \(c=g(b)=g(f(a))\) is the unique element in \(C\) which is in relation \(g \circ f\) with \(a\).

Definition: Let \(f: A \to B\) be a map.

• The set \(A\) is called the domain of \(f\) and the set \(B\) the codomain.
• If \(a \in A\) then the element \(b=f(a)\) is called the image of \(a\) under \(f\).
• The subset of \(B\) consisting of the images of the elements of \(A\) under \(f\) is called the image or range of \(f\) and is denoted by \(\text{Im}(f)\).
• If \(a \in A\) amd \(b=f(a)\) then the element \(a\) is called a pre-image of \(b\). The set of all pre-images of \(b\) is denoted by \(f^{-1}(b)\).

Notice that \(b\) can have more than one pre-image. Indeed if \(f: \mathbb{R} \to \mathbb{R}\) is given by \(f(x) = x^2\) for all \(x \in \mathbb{R}\), then both \(-2\) and \(2\) are pre-images of \(4\).

If \(A'\) is a subset of \(A\) then the image of \(A'\) under \(f\) is the set \(f(A') = \{f(a) \;|\; a \in A'\}\), so \(\text{Im}(f) = f(A)\).

If \(B'\) is a subet of \(B\) then the pre-image of \(B'\), denoted by \(f^{-1}(B')\) is the set of elements \(a\) from \(A\) that are mapped to an element \(b\) of \(B'\).

Theorem: let \(f: A \to B\) be a map.

• If \(A' \subseteq A\), then \(f^{-1}(f(A')) \supseteq A'\).
• If \(B' \subseteq B\), then \(f(f^{-1}(B')) \subseteq B'\).

Proof:

Let \(a' \in A'\), then \(f(a') \in f(A')\) and hence \(a' \in f^{-1}(f(A'))\). Thus \(A' \subseteq f^{-1}(f(A'))\).

Let \(a \in f^{-1}(B')\), then \(f(a) \in B'\). Thus \(f(f^{-1}(B')) \subseteq B'\).

Special maps

Definition: let \(f: A \to B\) be a map.

• \(f\) is called surjective, if for each \(b \in B\) there is at least one \(a \in A\) with \(b = f(a)\). Thus \(\text{Im}(f) = B\).
• \(f\) is called injective if for each \(b \in B\), there is at most one \(a\) with \(f(a) = b\).
• \(f\) is called bijective if it is both surjective and injective. So, if for each \(b \in B\) there is a unique \(a \in A\) with \(f(a) = b\).

For example the map \(\sin: \mathbb{R} \to \mathbb{R}\) is not surjective nor injective. The map \(\sin: [-\frac{\pi}{2},\frac{\pi}{2}] \to \mathbb{R}\) is injective but not surjective and the map \(\sin: \mathbb{R} \to [-1,1]\) is surjective but not injective. To conclude the map \(\sin: [-\frac{\pi}{2},\frac{\pi}{2}] \to [-1,1]\) is a bijective map.

Theorem: let \(A\) be a set of size \(n\) and \(B\) a set of size \(m\). Let \(f: A \to B\) be a map between the sets \(A\) and \(B\).

• If \(n < m\) then \(f\) can not be surjective.
• If \(n > m\) then \(f\) can not be injective.
• If \(n = m\) then \(f\) is injective if and only if it is surjective.

Proof:

Think of pigeonholes. (Not really a proof).

Proposition: let \(f: A \to B\) be a bijection. Then for all \(a \in A\) and \(b \in B\) we have \(f^{-1}(f(a)) = a\) and \(f(f^{-1}(b)) = b\). In particular, \(f^{-1}\) is the inverse of \(f\).

Proof:

Let \(a \in A\). Then \(f^{-1}(f(a)) = a\) by definition of \(f^{-1}\). If \(b \in B\) then by surjectivity of \(f\) there is an \(a \in A\) with \(b = f(a)\). So, by the above \(f(f^{-1}(b)) = f(f^{-1}(f(a))) = f(a) = b\).

Theorem: let \(f: A \to B\) and \(g: B \to C\) be two maps.

1. If \(f\) and \(g\) are surjective then so is \(g \circ f\).
2. If \(f\) and \(g\) are injective then so is \(g \circ f\).
3. If \(f\) and \(g\) are bijective then so is \(g \circ f\).

Proof:

1. Suppose \(f\) and \(g\) are surjective, let \(c \in C\). By surjectivity of \(g\) there is a \(b \in B\) with \(g(b) = c\). Since \(f\) is surjective there is also an \(a \in A\) with \(f(a) = b\). Therefore \(g \circ f(a) = g(f(a)) = g(b) = c\).
2. Suppose \(f\) and \(g\) are injective, let \(a,a' \in A\) with \(g \circ f(a) = g \circ f(a')\). Then \(g(f(a)) = g(f(a'))\) and by injectivity of \(g\) we find \(f(a) = f(a')\). Injectivity of \(f\) implies \(a = a'\).
3. Proofs 1. and 2. imply 3. by definition of bijectivity.

Proposition: if \(f: A \to B\) and \(g: B \to A\) are maps with \(f \circ g = I_B\) and \(g \circ f = I_A\), where \(I_A\) and \(I_B\) denote the identity maps on \(A\) and \(B\), respectively. Then \(f\) and \(g\) are bijections and \(f^{-1} = g\) and \(g^{-1} = f\).

Proof:

Suppose \(f A \to B\) and \(g: B \to A\) are maps with \(f \circ g = I_B\) and \(g \circ f = I_A\). Let \(b \in B\) then \(f(g(b)) = b\), thus \(f\) is surjective. If $a,a' \in A4 with \(f(a) = f(a')\), then $a = g(f(a)) = g(f(a')) = a' and hence \(f\) is injective. Therefore \(f\) is bijective and by symmetry \(g\) is also bijective.

Proposition: suppose \(f: A \to B\) and \(g: B \to C\) are bijective maps. Then the inverse of the map \(g \circ f\) equals \(f^{-1} \circ g^{-1}\).

Proof:

Suppose \(f: A \to B\) and \(g: B \to C\) are bijective maps. Then for all \(a \in A\) we have \((f^{-1} \circ g^{-1}) (g \circ f)(a) = f^{-1}(g^{-1}(g(f(a)))) = f^{-1}(f(a)) = a\).