Tran Chieu Minh recently asked on Math Overflow why the definition of a function is asymmetric: it treats the domain and the codomain differently. In other words, why privilege functions over relations? (Edit: Tran has since deleted the question.)
I think this is an interesting question, but I don’t think it’s appropriate for Math Overflow, so I’m redirecting discussion of it here. My own answer is below.
First, I think it’s important to recognize that thinking of mathematics in terms of sets and functions is a specific historical choice that mathematicians have made. Mathematics wasn’t always done this way, and it won’t always be done this way. For example, consider Terence Tao’s recent blog post where he replaces sets and functions with oracles and algorithms. There’s no reason to expect that more radical shifts in perspective aren’t possible, although admittedly when you’ve been trained to think in terms of sets and functions it’s a hard habit to break.
With that caveat in mind, here’s one idea I learned about from a discussion on the n-category cafe. The definition of a function has its roots in the arrow of time and in determinism. If you believe in determinism, you believe that the future state of the universe is a function of its current state: in other words, that to every current state there is associated a particular choice of future state, say one second in the future. Determinism and the arrow of time privilege the past over the future because a given past always leads to a given future, but the same future may be the result of multiple pasts: that’s why the codomain and domain of a function are treated asymmetrically. Indeed, think about the naive definition of a function: it’s a rule or process for starting with one thing and getting another. These processes are supposed to be deterministic and run in some amount of time: you start with an input and at some future time you obtain an output.
What else can we say? Well, a fundamental reason to study functions on a set 
I think there is a second question in the subtext of this question, though:
Why are functions such a successful framework for organizing mathematics?
In other words, why are functions so powerful that it isn’t necessary to step up to relations, for example? (Relations can, of course, themselves be described using functions.) I think one answer here is Yoneda’s lemma, which implies that any locally small category can be “represented” as a certain category of sets and functions between those sets. (It implies, for example, that the category of sets and relations can be represented in this way!) There is probably a deeper reason, although I can’t think of anything intelligent to say about it at the moment.
Annoying Precision 
I was thinking about this, and I’m going to admit, I kindof like terming things in terms of relations better.
(sorry if this was repeated above. I haven’t learned category theory yet…)
We define a relation
to be a subset of ordered pairs 
.
to just be all the ordered pairs reversed.
is injective if each element of 
has at most one arrow pointing into it.
is surjective if each element of 
has at least one arrow pointing into it.
is injective’ (that’s an injective with a prime) if 
is injective, and surjective’ if 
is surjective.
We define
We say a relation
We say a relation
We say a relation
Then a function is just a relation that is injective’ and surjective’, while a bijection is a relation that is all four: injective’, surjective’, injective and surjective.
I mean, I’m a big fan of relations too. There are lots of “functions” people work with (the complex logarithm, for example) that are much better thought of as relations (that is, as partial multivalued functions). But the point of my post is that there are very natural reasons to think of functions first, and in any case by the Yoneda lemma we can more or less restrict ourselves to thinking in terms of functions. (A relation between two sets is just a function from one power set to the other satisfying certain properties.)
I didn’t put it in my mind in a precise way, so is just as a random taught, but maybe is possible to answer to the question with an argument with this structure inside: We use function,so we use asimmetry because we have an asymmetric knowledge of the objects. We have some really easy objects to start with, and we want pushing them in, or receiving data into them(e.g:the asymmetry of our knowledge can be represented in both orientation of the arrow) understand more hidden objects. So function are something as an expansion process, corresponding to our cognitive process of knowledge. So the asymmetry is in our mind. I make this try having in mind, example such that Cayley theorem(transformation group as known object, abstract group hidden), the basic of differential geometry of curve and surface(R^n with his differential structure and surfaces as hidden), measure theory(R as known object, the measure space as hidden),basic field theory(Q,Zp as known object, and the concept of charateristic as hidden)…and maybe many other deeper example then this just very basics(but i don’t have deep knowledge of math so maybe if this is a good way to think about the question some other can do it)
That’s it exactly. Abstract nonsense indeed! Thank you.
On rereading what I’m wondering has anyone constructed a ‘binary operation’ where we can combine the two elements in more than two ways such that the third way is as important as the other two.
I’m not sure if this is exactly what you’re looking for, but these kinds of things are studied in higher category theory. In a
-category, there is both vertical composition and horizontal composition of 
-morphisms. More generally in an 
-category I think there are 
different kinds of composition for 
-morphisms.
I have been thinking of another object that has for good historical and mathematical reasons — binary relations. We have pre- and post-“multiplication”. All binary relation we can think of — by definition — have this construction. As I’m writing on a phone I won’t detail some obvious examples. Can anyone think of a category where there is a “third” or more way. Of course I can’t think if a natural example but has anyone constructed an abstract example where we could post- or pre-multiply or multiply “from above” etc. — or is this covered by multiplying by an inverse for example. It may well be a crazy thought but something I was thinking about that was prompted by this post.
Can you elaborate on this statement please? “… because a function
is just a special type of function 
.”
2^B is the set of subsets of B. Given a function f : B to X, taking the preimage of any element of X gives a subset of B, and this defines a function from X to 2^B.
There is a way to remove the asymmetry of functional relations: the difunctional relations or better difunctional
correspondances. They constitute a category whose objects are the pairs sets + equivalence the arrows satifying compatibility with respective equivalences on the source and target.
Cf the “résumé” of my talk in the SIC (Séminaire itinérant de Catégories)
I scanned through the comments and it seems no one as yet has written on what I’m going to say next. So here goes.
In mathematics, when you have a function
, often the domain X has geometric/analytic/topological properties while the target Y has algebraic properties.
Eg, often the elements of X are points. And we take limits of points in X. And we use the algebraic properties of Y, eg Y is the reals, to add and multiply functions.
Even if we have functors like a sheaf
, one sees that we take limits in the domain category Top(X) to get stalks and use pushouts or whatever limits via the “algebraic properties” of the target category Set.
For a perspective on relations of finite arity, see Relation Theory at PlanetMath.
Triadic relations are especially important in mathematics, and also in C.S. Peirce’s theory of sign relations, which provides a general framework for studying all forms of communication, inquiry, logic, and thought.
Two points determine a line.
What’s it gotta do wit time?
(Before I invite more flames let me clarify: studying permutation groups has certainly been useful over the past 150 years or so, and studying groups as permutation groups has as well. But I think studying a group G by considering it as a permutation group acting on itself by left multiplication is not particularly fruitful. Usually permutations are useful when you have a faithful permutation representation of degree much smaller than the order of the group. Also, when people talk about infinite groups acting on other mathematical objects, like, say, topological spaces, I think the permutation viewpoint is essentially moot.)
I was about to cite Cayley’s theorem as an equally useless theorem!
Cayley’s theorem has mostly psychological value, at least to me: it is a reassurance that the abstract and concrete definitions of a group are equivalent, just as embedding theorems for manifolds are a reassurance that the abstract and concrete definitions of a manifold are equivalent.
According to Wikipedia, the Whitney trick in the embedding theorem has uses in the proof of the h-cobordism theorem.
I didn’t quite mean to say that embedding theorems only have psychological value; perhaps a better analogue in the other direction would be about groups which have nice faithful representations. Representations, like embeddings, can potentially be much more useful than abstract descriptions.
I agree! It’s just that Cayley’s theorem seems to me to exemplify the notion of a useless theorem.
The strong Cayley theorem, on the other hand, can actually be quite useful in ruling out groups of certain orders from being simple. If you’re into that sort of thing.
I would say that Cayley’s theorem is mostly only of psychological value. I know one counter-example though: one of the nicer ways to prove the Sylow theorems is to show that, if they are true for a group G, then they are true for all subgroups of G, then check them by hand for S_n.
@fpqc: my point (and Kucera’s theorem) was not about local smallness/largeness. (When it comes to category theory, I rarely care about set-theoretic issues like largeness/smallness, and am happy to take the naive viewpoint.)
Let me be more specific. A concrete category is a category C that has a faithful functor to Set (the category of sets and set mappings). We often think of concrete categories as “categories of sets with extra structure.”
However, the category of topological spaces with morphisms=homotopy classes of continuous maps is not a concrete category. It is, however, a quotient of the concrete category of topological spaces/continuous maps, in a natural sense.
Kucera’s theorem says that these are the only two possibilities: every category is a quotient of a concrete one.
As far as I can tell, Kucera’s theorem is still a meaningful statement, in all three points of view (the naive one, your view that “there’s no such thing as largeness”, or the other view I’ve seen, which discusses issues of largeness/smallness at great length).
It may be a meaningful statement, but it’s not a useful statement. Concrete categories are totally useless unless you know which concrete category you’re working with (Say the category of groups or something).
I suppose that’s true. On the other hand, it does answer a question that burns in every undergrad’s mind when they first read about categories. “Are the objects of the category (always) sets?” Kucera says that they can be.
(Anyways, Kucera’s theorem was mostly a side remark to my point #1. In fact, your comments are an analogue of my point #1, albeit in a slightly different setting: just because every category is a quotient of a concrete one does not make concrete categories a good basis for working categorically. This is also analogous to: just because, by Cayley’s theorem, every group is a permutation group, does not necessarily make permutations a good basis for doing group theory.)
Dear Qiaochu,
Either you’re goofing around on IRC or somebody is impersonating you:
Joins: t0rajir0u ( ~qchu@host-137-205-30-192.res.warwick.ac.uk ) joined #math-ag ( 16 Users )
Quits: t0rajir0u ( ~qchu@host-137-205-30-192.res.warwick.ac.uk ) quit IRC [ Client Quit ]
Joins: fppf ( ~rollo.rei@host-137-205-30-192.res.warwick.ac.uk ) joined #math-ag ( 15 Users )
I only suspect that it is not you because why would you be in Warwick, but similarly, why would said person join then quit and change his name?
Best,
fpqc
Thanks for bringing this to my attention. That is indeed not me. Has the user done anything else with my name?
Nope, he only used your name for about a minute then quit and switched it. I was wondering if it was you, but I guess not! Meanwhile, #math-ag on irc.efnet.net is an IRC channel for “Graduate level math with an algebraic flavour”. Feel free to stop by!
Mathematics has always been about distilling complex sets of data into something simpler. For example, people thousands of years ago worked out procedures to compute areas of land so they could trade without being ripped off. They could have worked with a relation representing two regions that have the same area. But that’s a complex thing. It’s much simpler if we can reduce the description of a plot of land to a single real number and compare those. So naturally we are led to the idea of a procedure that takes a description as input and returns a single number. It seems to me that this is where functions come from and that it has little to do with anything temporal.
1) @Qiaochu: Just because every locally small category can be “represented” as a certain category of sets and functions between those sets, does not mean that sets and functions are necessarily a Good or The Best framework for doing mathematics. By the way, you might be interested in Kucera’s result that *every* category is a quotient of a concrete one (i.e. category of sets and functions) [Ludek Kucera, Every category is a factorization of a concrete one, Journal of Pure and Applied Algebra, Volume 1, Issue 4, December 1971, Pages 373-376.].
By way of analogy: Turing machines are computationally universal, but that doesn’t necessarily make them a Good programming language.
2) I do agree with Tran’s comments (and Thurston’s, I guess), that the concept of function has some good correlation with our intuition about time and processes in the physical world, and hence they have significant value in that sense.
3) @Tran: I think functions come up so much in algebra because algebra is about ways of combining things (elements, subsets, etc.), and you often want that way to be *deterministic*. Hence the idea of functions, which are inherently deterministic.
4) There are several notable examples in mathematics where relations come up in fundamental ways. Two examples: 1) cobordism in topology and 2) bisimilarity in automata theory/process algebra.
1) I don’t think I ever made such a claim, and I said as much at the beginning of the post. The only claim is that there are both psychological and (possibly) abstract reasons why functions are “good enough.”
4) Certainly many examples of important relations exist. Again, I think Tran’s question was more about the relative prominence of functions.
1.) There’s no such thing as a large category. Sets and functions are good enough to build category theory (Specifically ZFC+Universes) with relative largeness/smallness. Concrete categories are useless/pointless.
So I dispute that your point #1 has any meaning at all. =)
(This was a reply to Josh, not Qiaochu).
Some revisit: Yesterday, I read the article “On Proof and Progress in Mathematics” by William Thurston, and notice this passage which might be of interest,
We have a facility for thinking about processes or sequences of actions that can often be used to good effect in mathematical reasoning. One way to think of a function is as an action, a process, that takes the domain to the range. This is particularly valuable when composing functions. Another use of this facility is in remembering proofs:
people often remember a proof as a process consisting of several steps. In topology, the notion of a homotopy is most often thought of as a process taking time. Mathematically, time is no different from one more spatial dimension, but since humans interact with it in a quite different way, it is psychologically very different.
Here is some synthesis to what written above by Qiaochu and this. I am actually not adding anything new, just some reordering.
Based on the article above we have a heuristic definition of a function: A function (in a classical sense) is what obtained from a process by forgetting what happens outside the domain and codomain.
This definition can be back up by seeing how the notion of function came about. The current concept of function is actually the abstraction of a property of the concept of the function in the old days. During the time of Euler or so, whenever people think of function, they think of something like x^2 or sinx. The property we pick out is of course that each element in the domain correspond to exactly one element in the codomain. This property correspond to out view as function as something obtained from a process.
Seeing a function as something obtained from a process, we can see how the deterministic view point come in: As a process is something happening in time, the deterministic idea come in, and therefore necessarily there is some asymmetric property between the domain and codomain as elaborated by Qiaochu above. This asymmetry is inherited by the notion of function.
Suppose the above is reasonable, we ask the further question why function is so pervasive in mathematics.
The social part of this question can be seen through the above passage by Thurston:
* There is possibly some psychological factor that we tend to think in term of function.
The platonic part is not entirely clear. I have some partial answer for this.
The concept of function arises naturally in analysis. The strong ties between analysis and physics might explains why the nature of the question in analysis is so closed to a processes happening in time.
A side remark: This possibly also gives us an answer why there is also asymmetry in the notion of continuous function. The origin of continuous function is the heuristic that if we have a natural process a small change in the input will result in a small change in the out put.
I am still very confused by the fact that function is still appear everywhere in algebra. I other words, why should the idea of determinism appear in algebra. Perhaps your second idea come in but I am not totally convinced.
Just because something has evolved historically does not mean it is “optimal”. I think it also might have to do with a finitary number of answers to a particular input being easier to deal with. If, say, inverse trig operations somehow had more primary importance, the function would have been much less emphasized.
These days, I’d say the function isn’t as important, except in education ease-of-use is still an issue.
But inverse trig functions are functions – as long as you redefine their codomain properly. What I assume Tran was asking about is not why we teach students about functions in school, but why the basic objects of modern mathematics are defined in terms of sets and functions – e.g. a group is a set equipped with a function from pairs of elements to elements satisfying certain properties… certainly this is not the only way to define a group.
Just to be totally concrete with my example, sometimes you don’t want it as a function. In the SSA case of Law of Sines you can have two possible answers (which shows up as actual issue sometimes, like in astronomy). So if somehow this situation happened with other operations a great deal, some structure other than functions might have become the standard.
I may be wrong but it seems to me that the carefully treatment of the theory of functions in text books, let’s say 40 to 80 year old, is now harder to find.
The fact that the domain is treated differently from the codomain isn’t it also due to the more difficult task to invert a function? If you have a derivative function it is harder to find (or even impossible) the anti-derivative (integral). And Implicite functions are sometimes difficult to be expressed in a closed form.
In general the closed form of sequences defined as recursive relations is also difficult to find.
It has just come to my mind that in the case of sequences it is more natural to think of the domain as the naturals than otherwise.
Thanks for the answer. This is precisely the thing I was looking for.
No problem. I’ve edited the first part of the answer a little; there was something important I forgot to say about the “deterministic” view of functions between two sets.
Hello, Qiaochu, thanks again for posting the question here.