On “well-defined” functions

As a TA for CS251 I frequently see people verify that a function is well-defined when there is no need to. And just as often I see the opposite. So let’s set the record straight here: what exactly is a function, and when do we need to check whether something is genuinely a function?

Given two sets $X$ and $Y$, a function if $f \colon X \to Y$ is just a subset of the Cartesian product $X \times Y$ such that for each $x \in X$, there is exactly one $y \in Y$ such that $(x, y) \in f$.

As you expect, we write $f(x)$ to denote said unique $y$.

So what happens when we attempt to define a function? Essentially, we are associating each $x \in X$ with some subset of elements in $Y$. For example, in the function $f : \mathbb N \to \mathbb N$ where $f(x) = 2x$, we are associating $x$ with $\{2x\}$. For example, we just associate $1$ with $2$, $2$ with $4$, and so on.

When we attempt to define a function $f$, we would like to have $f$ associate each $x$ with exactly one value in $y$.

Most of the time we write a function as $f(x) = \dots$ and in this case there are no problems. If it is some formula of $x$, this is always fine. Perhaps it is a piecewise formula, where you first have to check whether $x$ is even or odd. No matter. This will always be fine.

Now let me give you a very quick bad definition of a function. Suppose that we are attempting to map the positive rationals to positive integers. Suppose you say, “we associate the rational $p / q$ (where $p$, $q$ are integers) with the integer $p + q$.” News flash: we associate $2 / 3$ with $2 + 3 = 5$ and $4 / 6$ with $4 + 6 = 10$. Since $2 / 3 = 4 / 6$, we have associated multiple elements with the same rational.

Now what is the actual issue? When we define a function, we are associating a representation of an element in $X$ with some value in $Y$. What we are really doing when we say “for all $x \in X$, $f(x) = 2x$” is that we are representing each element of $X$ as $x$. The “for all $x$” quantifier guarantees that each element in $X$ is accessed exactly once with the representation $x$, and then we associate each $x$ with $2x$.

But when we look at $f(p/q) = p + q$, what we are doing is associating a value to every fractional representation of a number. And we have already seen that a rational number has many fractional representations, such as $2 /3 = 4 / 6$. Of course, the way we fix this is stipulate “for all relatively prime $p, q$, we have $f(p/q) = p + q$”. Now this genuinely is a function, because we have ensured that we are only associating values to one representation of each rational number.

If we are earnestly trying to define a function $f$, we are not going to associate a representation of an element with more than one value. Because if we do, the subset of $X \times Y$ we are describing automatically is not a function anymore.

Now, we do not need ascribe every representation of an element in $X$ with a value in $Y$. Ideally, we would like to ascribe exactly one representation of an element with a value, which is why there is no need to check that functions of the form “for all $x \in X$, $f(x) = \dots$” are well-defined. There is nothing to check! It is obviously a function.

But what of functions where you genuinely have no choice but to associate a value to multiple representations of an element? In this case, I personally say we check for representation invariance of the function, or that such a function is representation invariant.

As an example, take modular arithmetic. We would like to be able to define $13 + 10$ modulo $12$ the same way that $1 + 10$ is defined modulo $12$, and it turns out that $13 + 10 \equiv 1 + 10$ modulo $12$. Likewise, $13 \cdot 10 \equiv 1 \cdot 10$ modulo $12$. So it is okay to ascribe a value to multiple representations when defining multiplication, because they are all consistent.

In general, what we need to check here is representation invariance. In other words, if $a \equiv b$ and $c \equiv d$, we need to make sure that $a c \equiv b d$. (All these equivalences are modulo $n$.) And it is easy to check that this is indeed true, so multiplication can be properly defined in modular arithmetic.

To summarize,

• a function is a subset of $X \times Y$,
• we associate values in $Y$ to representations of values in $X$ when we attempt to define a function,
• ideally for each element in $X$, we only ascribe values to one representation of the element,
• but sometimes we genuinely need to ascribe a value to multiple representations of the element, in which case we must check that the ascribed value is the same across all representations we access.

And the last bullet point is the only time you need to check that a function is “well-defined”.