Functions on General Sets

definitions
discrete-math
set-theory
functions

The set-theoretic definition of a function — not “a rule” or “a formula”, but a particular kind of subset of a Cartesian product. See sets-and-set-notation for the Cartesian products this is built on.

The definition

A function \(f : X \to Y\) is a subset \(f \subseteq X \times Y\) such that for each \(x \in X\), there is a unique \(y \in Y\) such that \((x,y) \in f\).

The function is the set of pairs. There is no separate “rule” object — the familiar notations are all names for the same set:

\[y = 2x + 1 \qquad\text{or}\qquad f(x) = 2x + 1 \qquad\text{or}\qquad f = \{(x,y) \in \mathbb{R} \times \mathbb{R} : y = 2x+1\}\]

and the bridge between the two styles is

\[f(x) = y \quad\Longleftrightarrow\quad (x,y) \in f\]

Defining a function this way costs a little intuition and buys a great deal of precision: the definition applies to any sets at all, not just sets of numbers, and questions like “are these two functions equal?” become ordinary questions about set equality.

Three conditions hidden in one sentence

Unpacking “for each \(x \in X\) there is a unique \(y \in Y\) with \((x,y) \in f\)” gives three separate things to check:

  1. Every \(x \in X\) is used — no element of the domain is left without a value. (“for each \(x \in X\)”)
  2. Every value lands in \(Y\) — no pair points somewhere outside the codomain.
  3. Each \(x\) has only one value — no \(x\) appears as the first coordinate of two different pairs. (“unique”)

Checking a candidate means checking all three, and a candidate can fail each one separately.

Figure 1: The uniqueness condition, seen graphically. A subset of the plane is a function of x exactly when every vertical line meets it at most once: the middle curve fails because one input is paired with two outputs, while the right-hand curve passes despite repeating output values, which the definition never forbids. The red vertical line in the middle and right-hand panels is the test.

The asymmetry in that picture is the whole definition: repeated \(y\)-values are fine, repeated \(x\)-values are not. The right-hand curve takes the same value three times over and is still a function.

Worked: which of these is a function?

Let \(X = \{1,2,3\}\) and \(Y = \{1,2,3,4\}\). Which one of the following is a function from \(X\) to \(Y\)?

Candidate Why
(a) \(\{(1,2), (1,3), (2,4)\}\) ✗ \(f(1) = 2\) and \(f(1) = 3\) — the value at \(1\) is not unique. (Also \(3\) is unused.)
(b) \(\{(1,2), (2,3), (3,2), (4,1)\}\) ✗ \(4 \notin X\) — a pair whose first coordinate is outside the domain
(c) \(\{(1,2), (2,3), (3,5)\}\) ✗ \(5 \notin Y\) — a value outside the codomain
(d) \(\{(1,2), (2,1), (3,1)\}\) ✓ all first coordinates in \(X\), all second in \(Y\), each of \(1,2,3\) used exactly once

Each wrong answer breaks a different one of the three conditions, which is what makes this a good question: the three failures are not variations on one mistake.

For (d): \(f(1) = 2\), \(f(2) = 1\), \(f(3) = 1\). Note \(f(2) = f(3)\) — two inputs sharing a value is not a problem, for exactly the reason the picture above shows.

Codomain and range

The two are constantly confused, and the difference is one word:

For a function \(f : X \to Y\), the co-domain is \(Y\), and the range is \(f(X) = \{f(x) : x \in X\}\), which is a subset of \(Y\).

Is Determined by
Co-domain \(Y\) — where values are allowed to land the declaration \(f : X \to Y\)
Range \(f(X)\) — where values actually land the pairs in \(f\)

So the codomain is a choice you make when you write down the function, and the range is a fact you compute. Always \(f(X) \subseteq Y\), and the containment is often proper.

For the function (d) above, \(f = \{(1,2),(2,1),(3,1)\}\):

\[\text{co-domain} = Y = \{1,2,3,4\} \qquad\qquad \text{range} = f(X) = \{1,2\} \subseteq Y\]

\(3\) and \(4\) are in the codomain and not in the range — they are permitted values that this particular function never takes.

Image and preimage

The two definitions generalise “range” to any subset, in each of the two directions:

If \(f : X \to Y\) is any function and \(A\) is any subset of \(X\), then the image of \(A\) is \[f(A) = \{f(x) : x \in A\}\]

If \(f : X \to Y\) is any function and \(B\) is any subset of \(Y\), then the inverse image or preimage of \(B\) is \[f^{-1}(B) = \{x \in X : f(x) \in B\}\]

Both take a set and return a set — \(A \subseteq X\) gives \(f(A) \subseteq Y\), and \(B \subseteq Y\) gives \(f^{-1}(B) \subseteq X\). The range is then just the image of the whole domain, \(f(X)\).

The notation \(f^{-1}\) here does not mean an inverse function. \(f^{-1}(B)\) is defined for any function, invertible or not — the emphasis on any in both definitions is the point. It is a set-to-set operation that always exists; an inverse function is a different thing that usually does not.

Figure 2: Image and preimage of the same function, read in opposite directions. Following the lines forward from a subset of X collects a subset of Y; following them backwards from a subset of Y collects every x that lands in it — which can be several elements, or none at all. In each panel the domain is on the left and the co-domain on the right, each line runs from an element of X to its value in Y, and the subset under discussion is outlined in colour with its expression in the same colour.

Worked

Let \(X = \{1,2,3\}\), \(Y = \{1,2,3,4\}\) and \(f = \{(1,2), (2,1), (3,1)\}\), the function from the question above. So \(f(1) = 2\), \(f(2) = 1\), \(f(3) = 1\).

Asked for Working Answer
(a) image of \(\{1\}\) \(f(1) = 2\) \(f(\{1\}) = \{2\}\)
(b) image of \(\{2,3\}\) \(f(2) = 1\), \(f(3) = 1\) \(f(\{2,3\}) = \{1\}\)
(c) inverse image of \(\{2\}\) which \(x\) have \(f(x) = 2\)? only \(x=1\) \(f^{-1}(\{2\}) = \{1\}\)
(d) preimage of \(\{1\}\) which \(x\) have \(f(x) = 1\)? \(x = 2\) and \(x = 3\) \(f^{-1}(\{1\}) = \{2,3\}\)
(e) preimage of \(\{3,4\}\) no \(x\) maps to \(3\) or \(4\) \(f^{-1}(\{3,4\}) = \emptyset\)

Three things this table is designed to show — they are the three panels of Figure 2:

  • (b): an image can be smaller than the set you started with. \(\{2,3\}\) has two elements, \(f(\{2,3\})\) has one, because \(f\) sends both to the same place.
  • (d): a preimage can be larger than the set you started with. One element of \(Y\) pulls back to two of \(X\).
  • (e): a preimage can be empty. \(\{3,4\}\) lies outside the range entirely. Note this is a perfectly good answer, not a failure — \(\emptyset\) is a subset of \(X\) like any other, and it is the reason \(f^{-1}\) needs no invertibility to be defined.

Always write the answers as sets: \(f^{-1}(\{2\}) = \{1\}\), not \(= 1\). The operation returns a subset, and dropping the braces is the standard slip.

See also