Skip to main content

Section 5.5 Maps

The real point of defining things as we have is so we can talk about maps as soon as possible. Maps — {\addfontfeature{LetterSpace=5.0}\textsmallcaps{aka}} set maps, mappings, functions — are an important notion in set theory. The idea is that a map \(f\colon S \to T\) is a way of taking each element \(s\in S\) and associating one and only one element \(f(s)\in Y\) thereto. Importantly, though, a map \(f\colon S \to T\) “knows” its source \(S\text{,}\) its target \(T\text{,}\) and the method of associating elements of \(T\) with elements of \(S\text{.}\) Thus a map \(f\colon S \to T\) is defined as an ordered triple \(\angs{S,T,\Gamma(f)}\) in which \(\Gamma(f) \subseteq S \times T\) is a subset with the property that for every element \(s \in S\text{,}\) there is a unique

element \(f(x)\in Y\) such that \(\angs{x,f(x)}\in\Gamma(f)\text{.}\)

In practice, the way we describe maps is pretty relaxed. We typically identify the source \(S\) and the target \(T\text{,}\) and then we provide a rule for “sending” elements of \(S\) to the associated elements of \(T\text{.}\) The idea is that for every \(s \in S\text{,}\) we have to specify a unique \(f(s) \in T\) “attached” to \(s\) in the sense that \(\angs{s, f(s)} \in \Gamma(f)\text{.}\)

Sometimes, it's handy to use the following notation: we may define a map \(f \colon S \to T\) by the assignment

\begin{equation*} s \mapsto \text{ [some formula involving \(s\)] }\text{.} \end{equation*}

For instance, we can specify a map \(f\colon \omega \to \{0,1\}\) by saying that \(f(0)=0\) and for any successor \(n+1\text{,}\) we let \(f(n+1)\) be the unique element of \(\{0,1\}\) such that \(f(n+1)\neq f(n)\text{.}\) Since we can check that \(f(n+1)\) is indeed unique with this property, we are assured that \(f\) really is a map.

Suppose \(S\subseteq X\text{.}\) There is a map \(i\colon S \to X\) such that \(i(s)=s\text{,}\) called the inclusion map. When \(S=X\text{,}\) this is called the identity map \(\id\text{.}\)

If we specify two sets \(S\) and \(T\text{,}\) then we can write \(\Map(S, T) \subseteq \PP(S \times T)\) consisting of those subsets \(\Gamma \subseteq S \times T\) such that \(\angs{S, T, \Gamma}\) is a map. We can write this as:

\begin{equation*} \Map(S, T) \coloneq \{ \Gamma \subseteq \PP(S \times T) : (\forall s \in S)(\exists ! t \in T)(\angs{s,t} \in \Gamma) \}\text{.} \end{equation*}

this is our set of maps from \(S\) to \(T\text{.}\)

\​begin{exr} Suppose \(X\) a set (possibly empty). The set \(\Map(\varnothing,X)\) always consists of exactly one element: the inclusion map \(\varnothing \to X\text{.}\) The point here is that \(\varnothing \times X = \varnothing\text{,}\) so \(\PP(\varnothing \times X) = \{\varnothing\}\text{.}\) The unique subset \(\varnothing \subseteq \varnothing\) is a map \(\varnothing \to X\text{:}\) indeed, the condition is:

\begin{equation*} (\forall s \in \varnothing)(\exists ! t \in X)(\angs{s,t} \in \varnothing)\text{,} \end{equation*}

which is always true. The set \(\Map(X,\varnothing)\) is often, but not always, empty. Once again, we are looking at the unique subset \(\varnothing \subseteq X \times \varnothing = \varnothing\text{,}\) and the condition is:

\begin{equation*} (\forall s \in X)(\exists t \in \varnothing)(\angs{s,t} \in \varnothing)\text{,} \end{equation*}

which is true if \(X = \varnothing\text{;}\) otherwise it is false. \end{exr}

Maps can be composed. If \(f\colon S \to T\) is a map, and \(g\colon T \to U\) is another, then you can “do \(f\) first, and then do \(g\)”. That is, one can form a new map \(g\circ f\colon S \to U\) such that for any \(s\in S\text{,}\) one has

\begin{equation*} (g\circ f)(s)\coloneq g(f(s))\text{.} \end{equation*}

More formally, \(f\) and \(g\) are triples \(\angs{S,T,\Gamma(f)}\) and \(\angs{T,U,\Gamma(g)}\) (respectively), and \(g\circ f\) is the triple \(\angs{S,U,\Gamma(g\circ f)}\text{,}\) where

\begin{equation*} \Gamma(g\circ f)\coloneq\{(s,u)\in S\times U : (\exists t\in T)((s,t)\in\Gamma(f)\wedge(t,u)\in\Gamma(g))\}\text{.} \end{equation*}

It is easy enough to see that \(g\circ\id=g\) and \(\id\circ f=f\text{,}\) and moreover composition is associative, so that \((h\circ g)\circ f=h\circ(g\circ f)\text{.}\)