I’m in the happy state of just having finished marking exams for this year. There is very little of interest to say about the week that was removed from my life: it would be fun to talk about particularly bizarre mistakes, but I can’t really do that, especially as the results are not yet known (or even fully decided). However, one general theme emerged that made no difference to anybody’s marks. There seems to be a common misconception amongst many Cambridge undergraduates that I’d like to discuss here in the hope that I can clear things up for a few people. (It is an issue that I have discussed already on my web page, but rather than turning that into a blog post I’m starting again.)
The question where the misconception made itself felt was one about functions, injections, surjections, etc. I noticed that a lot of people wrote things like, “If then so is well defined.” Now if you fully understand what a function is, then you will find this quite amusing: if then trivially by the very basic principle that you can substitute something for something else if the two things are equal to each other. (A famous type of counterexample to this from philosophy: two years ago, Michelle Obama was the wife of Barack Obama; Barack Obama is the president of the United States; two years ago, Michelle Obama was not the wife of the president of the United States. Yes yes, there are ways of explaining why this isn’t a real counterexample.)
But it seems only fair, if one is going to laugh at such sentences, to provide examples of functions that are well defined and functions that aren’t, so that the difference can be made clear. But now we have a problem: any putative example of a function that is not well defined is not a function at all. So it begins to seem as though all functions are well defined. But in that case, what are people doing when they check that a function is well defined?
The real question we are asking is this: when we use the words “well defined”, what are we referring to? It can’t be a function, because a function is a function is a function and that’s all there is to it. Is it something like “an attempted definition of a function”? That seems a bit odd: we define things, not definitions. If we wanted to say that a definition really did specify a function, then surely we would just say “This definition is good.” So what kinds of objects are there that are sometimes functions (if they are well defined) and sometimes not functions (if they are not well defined)?
To answer this, let me give a fairly standard example of a definition that feels as though it might define a function but in fact doesn’t. We’ll define a “gunction” as follows: . That is, takes two rationals and creates a new rational by adding the numerators and adding the denominators. For instance, .
Why doesn’t this define a function? Well, , so it ought to be the case that if we replace by in the calculation just made, then we get the same answer. But actually we get , which is not the same as .
But doesn’t this show that what people were writing in their exam scripts is exactly what they should have been writing? I’ve just shown that is not well defined, and did I not do so by finding an example of rational numbers , and such that but ? Well, sort of, but in that case what function am I talking about? What does even mean?
Let’s go back to how the gunction is defined, but with no presuppositions about what a gunction actually is. Suppose that and are rational numbers. Then to calculate we choose integers such that and , and output the answer . As we’ve observed, there are many ways of choosing and many possible distinct fractions that could result. So what we have is not a function but a process that takes an element of and gives us several possible answers.
Thus, a gunction is like a function but it can be multivalued. What is a multivalued function? Well, informally it is “a function that is allowed to take more than one value” such as the gunction defined by . For some examples we could also allow gunctions not to be defined everywhere, as would happen here if we extended the domain of to all of . More formally, a multivalued function from to is a subset of such that for every there is at least one such that . And a more general gunction is just any subset of (otherwise known as a relation).
Let’s stick with the informal definition of a gunction from to as being like a function except that it doesn’t have to take precisely one value for each . The next question that arises is this: why bother with gunctions at all? Why take the risk of a bad definition? Why not just stick to functions so that everything is automatically well defined?
To answer this, let us go back to the rationals and see how we define the sum of two rationals. The most convenient definition is the obvious one: . Let us break that up into a composition of simpler operations. We start with a pair of rational numbers. Next, we choose pairs and of integers such that and . Then we work out the integers and . Finally, we output the answer .
Now the first stage of this process is a very clear example of a multivalued function, since for each pair there are many ways of choosing the pairs and . From then on, however, we are dealing with good old-fashioned functions. So we have just defined a gunction from to by composing a genuinely multivalued function from to with a function from to and then a function from to . (To be slightly more accurate we should say rather than .) The resulting object is a good example of a gunction that happens to be a function, but where that fact, rather than being trivial, is something that needs to be checked.
This example points us to the answer to our earlier questions. It often happens that the most convenient way of defining a function is to define it as a composition , where is a multivalued function and is a function. For to be a function, or, as we usually say, for to be well defined, we need the following to hold: for every and any two possible values of , .
Why does this situation come up so often? Well, often and are not just any old sets but sets of equivalence classes. For example, an element of can be thought of as an equivalence class of pairs , where if and only if . (And this is not just some strange abstract definition: it really is what we are doing when we deal with rationals, except that we happen to write instead of .) If we want to define a function from to , then what do we do?
Let’s suppose that is the set of all equivalence classes of some equivalence relation on a set and that is the set of equivalence classes of an equivalence relation on a set . Then often what we do is this: start with an equivalence class of the relation on ; choose an element of ; apply some function to the element , obtaining an element ; let be the equivalence class of . We then say that .
There is a natural multifunction from to , namely the multifunction that takes the equivalence class to any element of . The procedure we have just defined is the composition of that multifunction with a function from to and the quotient map from to . And what do we need to know about if we want to be a function? We must check that whenever , which is actually not all that different from what the candidates were writing in the exam. However, it is different: the difference between “is equal to” and “is equivalent to” makes the difference between a triviality and something that actually needs to be checked.
Notice that the multifunction from to was in a sense the inverse of the quotient map from to (which equals ). This is another way of thinking about why gunctions/multifunctions arise naturally: they are, so to speak, inverses of functions that don’t have inverses. Or at least, that is a natural way for them to arise.
All this demonstrates that the conventional use of language, with sentences like “We must check that this function is well defined,” is extremely unfortunate: if you have been confused by it, then that is much more the terminology’s fault than it is yours. But it looks as though the terminology is here to stay, so the best advice I can give is that while you write “Let us check that this function is well defined,” you secretly translate it to yourself as “Let us check that this gunction really is a function” or, if that’s a bit too Dr Seuss for your tastes, “Let us check that this multivalued function is in fact a function.” And one last piece of advice, which would have saved a few precious seconds for many candidates on the exam that I’ve just marked: if you’ve just defined a function from to by specifiying unambiguously what it does to each element of , or if you’ve defined it as a composition of two existing functions, then it is automatically well defined and you don’t need to check anything. You don’t even need to say that you don’t need to check anything: it’s just a function and that’s all there is to it. The things that might fail to be well defined are multifunctions.