Section 2.2 Maps
Warning 2.2.1.
Many students find this bit of material pretty abstract when they first encounter it. It takes a few tries to get the real feeling that you've “really” understood the definition of maps. My suggestion is to have in your mind as many examples and nonexamples of maps as you can get, and when you hear a statement about maps, try to think about what it says in the examples you have!
The real point of defining things as we have is so we can talk about maps as soon as possible. Maps — 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 T\) thereto.
Definition 2.2.2.
Let \(X\) and \(Y\) be two sets. A map or function \(f\) from \(X\) to \(Y\text{,}\) denoted \(f\colon S\to T\text{,}\) is a subset \(\Gamma(f) \subseteq X \times Y\) such that for every \(x \in X\text{,}\) there exists a unique \(f(x) \in Y\) such that \((x,f(x)) \in \Gamma(f)\text{.}\) The set \(X\) is called the domain or source of \(f\text{,}\) and \(Y\) is the codomain or target of \(f\text{.}\) The subset \(\Gamma(f)\) is called the graph of \(f\text{.}\)
In practice, the way we describe maps is pretty relaxed. We typically identify the source \(X\) and the target \(Y\text{,}\) and then we provide a rule for sending elements of \(X\) to the associated elements of \(Y\text{.}\) The idea is that for every \(x \in X\text{,}\) we have to specify a unique \(f(x) \in Y\) attached to \(x\) in the sense that \((x, f(x)) \in \Gamma(f)\text{.}\)
Example 2.2.3. An example and a nonexample of maps.
We can define a map \(f \colon \NN_0\rightarrow \NN_0\) by the rule \(f(m)=m^2-4\text{.}\) What this means is that the graph of \(f\) is the subset \(\Gamma(f) = \{(m,n) \in \NN_0\times\NN_0 : n = m^2-4\}\text{.}\) Note that for each \(m \in \NN_0\text{,}\) there is a unique element \(n \in \NN_0\) such that \(n=m^2-4\text{.}\)
On the other hand, it is not sensible to define a map \(g \colon \NN_0 \to \NN_0\) by a rule like \(m=g(m)^2-2g(m)+2\text{.}\) This would have graph \(\Gamma(g) = \{(m,n) \in \NN_0\times\NN_0 : m = n^2-2n+2\}\text{,}\) but the trouble here is twofold.
-
First, there are some natural numbers \(m\) such that there is no natural number \(n\) for which \(m = n^2-2n+2\text{.}\) For example, there is no natural number \(n\) such that \(n^2-2n+2=0\text{.}\) (To prove this, let \(n\in \NN_0\text{.}\) Then
\begin{equation*} n^2-2n+2 = n^2 -2n + 1+1 = (n-1)^2 + 1 \geq 1 + 1 = 2\text{,} \end{equation*}since \((n-1)^2\geq 0\text{.}\))
Second, there are natural numbers \(m\) such that there exists more than one natural number \(n\) such that \(m = n^2-2n+2\text{.}\) (Note that \((0,2)\) and \((2,2)\) both lie in \(\Gamma(g)\text{.}\))
Example 2.2.4. A preview of modular arithmetic.
Let \(n\) be a natural number. Recall that \(n = \{0,1,\dots,n-1\}\text{.}\) Then we may define a map \(\mu \colon \NN_0 \to n\) by the rule that for any integer \(m\text{,}\)
In other words, \(\mu(m)\) is the remainder of \(m\) after dividing by \(n\text{.}\) To say it differently, \((m,r)\in \Gamma(\mu)\) if and only if \((\exists d \in \NN_0)(m=nd+r)\text{.}\)
Sometimes, it's handy to use the following notation: we may define a map \(f \colon S \to T\) by the assignment
Example 2.2.5. An example involving the real numbers.
Let \(\RR\) denote the set of real numbers. We may define a map \(e \colon \RR \to \RR\) by the rule
Example 2.2.6. Cases in defining a function.
Let's define a map \(f \colon \NN_0 \to \{\text{red},\text{blue}\}\text{.}\) We can daydream of such a map as painting some natural numbers red and others blue. Defining \(f\) is really the same thing as declaring which natural numbers to paint red, and which to paint blue, in such a way as to ensure that every natural number is painted at least one of these colors, and no natural number is painted both of these colors. Here's a valid way to describe a map \(f\text{:}\)
Here's a definition that does not work:
This doesn't work for two reasons: first, there are natural numbers \(x\) that are neither even nor divisible by \(3\) (like \(5\)); second, there are natural numbers \(x\) that are divisible by both even and divisible by \(3\) (like \(6\)). This rule avoids painting some numbers altogether, and paints other numbers two different colors.
Example 2.2.7. The inclusion map and the identity map.
Let \(T\) be a set, and let \(S \subseteq T\) be a subset. Then there is a map \(i \colon S \to T\) given by the rule \(i(x)=x\text{.}\) This is called the inclusion map. In the particular case in which \(S=T\text{,}\) the map \(i\) is called the identity map \(\mathrm{id} \colon S \to S\text{.}\)
Example 2.2.8. Maps to and from the empty set.
Let \(X\) be any set. Since \(\varnothing \subseteq X\text{,}\) it follows that we alwaays have an inclusion map \(\varnothing \to X\text{.}\) This is in fact the only map \(\varnothing \to X\text{.}\)
On the other hand, let's contemplate the maps \(X \to \varnothing\text{.}\) If \(X=\varnothing\text{,}\) then we have the identity map, but if \(X\neq\varnothing\text{,}\) then there is no map \(X \to \varnothing\text{.}\) After all, if \(X\neq\varnothing\text{,}\) then there is an element \(x \in X\text{.}\) But there's nowhere to send \(x\text{!}\)
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
More formally, the graph \(\Gamma(g\circ f)\) is given by
It is easy enough to see that \(g\circ\mathrm{id}=g\) and \(\mathrm{id}\circ f=f\text{,}\) and moreover composition is associative, so that \((h\circ g)\circ f=h\circ(g\circ f)\text{.}\)