Mappings as Generalized Functions

A mapping is a function without the numbers. The definition you learnt in 13.1 was phrased in terms of real numbers because that is the setting of high-school algebra. The same definition works just as well for arrows between any two sets, people to phone numbers, countries to capitals, vectors to vectors. The word "mapping" is the term mathematicians use when they want to emphasise that the inputs and outputs need not be numbers.

Definition

A mapping (or map) $f: A \to B$ is a rule that assigns to each element of $A$ exactly one element of $B$. The set $A$ is the domain, the set $B$ is the codomain. If $f(a) = b$ we say $b$ is the image of $a$ and $a$ is a preimage of $b$.

Two things are worth noticing immediately: (i) every element of $A$ gets exactly one image, the function rule from 13.1 still applies; (ii) an element of $B$ can have any number of preimages, including zero. Think of it as arrows leaving $A$: each element of $A$ has one arrow leaving it, but a target in $B$ may receive several arrows or none at all.

Image of a subset

For a subset $S \subseteq A$, the image of $S$ under $f$ is

$f(S) = \{f(a) : a \in S\} \subseteq B.$

The image of $f$ (with no qualifier) is $f(A)$, the set of elements in $B$ that actually get hit by something. The image is always a subset of the codomain; equality means the mapping is surjective, a concept you will meet in the next section.

Three small examples

• Squaring on the integers. Let $A = \mathbb{Z}$, $B = \mathbb{Z}$, $f(n) = n^2$. The image is the set of non-negative perfect squares $\{0, 1, 4, 9, 16, \ldots\}$. The preimage of $4$ is $\{-2, 2\}$, two arrows arrive at $4$. The preimage of $3$ is empty.
• Mod 3 on a finite set. Let $A = \{0, 1, 2, 3, 4, 5\}$, $B = \{0, 1, 2\}$, $f(n) = n \bmod 3$. The image is all of $B$, and each element of $B$ has exactly two preimages.
• Person to country. Let $A$ be all people, $B$ be all countries, $f$ assign each person their country of birth. The image is the set of countries with at least one citizen alive; preimages have wildly different sizes (China has billions, Vatican City has very few).

• Databases: A foreign key from one table to another is a mapping: each row in "Orders" maps to a row in "Customers" via the customer ID; the preimage of one customer is the set of all orders by that customer.
• Programming: A HashMap<K, V> IS a mapping from keys to values; the image of the map is exactly the set of currently-stored values.
• Cryptography: An encryption function maps plaintext to ciphertext; for decryption to work, the map must be a bijection (every ciphertext has exactly one preimage).

(Click any element on the left oval (the domain X), then click an element on the right oval (the codomain Y) to attach an arrow. The widget reports whether the current diagram is a valid function, that is, whether every element of X has exactly one arrow out. Try the "Partial" preset to see what a non-mapping looks like.)

What is NOT a mapping

Two failure modes a mapping must avoid:

• Some input has no image. Defining "the assignment $1 \mapsto a, 2 \mapsto b$" on $A = \{1, 2, 3\}$ is not a mapping, the element $3$ has no arrow leaving it.
• Some input has two images. Defining "$1 \mapsto a$ and $1 \mapsto b$ where $a \neq b$" is not a mapping, the rule is ambiguous for input $1$.

Try it

• Let $A = \{1, 2, 3, 4\}$ and $f(x) = x^2 \bmod 5$. List the image and find the preimage of each element of $B = \{0, 1, 2, 3, 4\}$.
• Construct a mapping $f: \{a, b, c\} \to \{x, y\}$ whose image equals the codomain. How many such mappings are there?
• For $f: \{1, 2, 3, 4, 5\} \to \mathbb{Z}$, $f(n) = 2n - 1$, compute $f(\{2, 4\})$ and $f(\{1, 3, 5\})$.

A trap to watch for

It is tempting to say "$f$ is not a function because nothing in $A$ maps to $b \in B$." That is not a problem. The mapping rule only demands that each element of the domain has an image; it places no constraints on the codomain. If no element of $A$ maps to $b$, then $b$ simply has an empty preimage, the mapping is still a perfectly good mapping, just not surjective. The "every element has exactly one image" rule applies to the domain, not the codomain.

What you now know

You can recognise a rule as a mapping (or reject it because some input is unspecified or ambiguous), compute the image of an element or subset, find the preimage of an element, and distinguish image from codomain. The next section formalises the toolbox, composition, identity, inverse, and introduces the three properties (injective, surjective, bijective) that the rest of mathematics relies on.

Quick check

Mark section complete →

References

• Lang, S. (1971). Basic Mathematics. Springer. Chapter 14 §1, mappings as the abstract generalisation of functions.
• Halmos, P. (1974). Naive Set Theory. Springer. Section 8: functions and mappings between sets, image, preimage.
• Rudin, W. (1976). Principles of Mathematical Analysis, 3rd ed. McGraw-Hill. Chapter 2: mappings, images, and inverse images at the level used in analysis.