Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

What is authoritative canonical formal definition of function?

For example,

According to Wolfram MathWorld, $$isafun_1(f)\;\leftrightarrow\; \forall a\in f\;(\exists x\exists y \;\langle x,y\rangle = a) \; \wedge \; \forall x\forall y_1\forall y_2\;((\langle x,y_1\rangle\in f\wedge\langle x,y_2\rangle \in f)\rightarrow y_1=y_2))$$

According to Bourbaki "Elements de Mathematiques, Theorie des Ensembles", $$ isafun_2(f)\;\leftrightarrow\; \exists d\exists g\exists c\;(\langle d,g,c\rangle=f \;\wedge\;isafun_1(g)\;\wedge$$ $$\;\wedge\; \forall x(x \in d\rightarrow \exists y(\langle x,y\rangle \in g)) \;\wedge\; \forall x\forall y(\langle x,y\rangle \in g\rightarrow (x \in d\wedge y\in c))) $$

How to make agree definition of function as triple with extensional equality $$ \forall f\forall g\;[\;(isafun(f)\wedge isafun(g)) \; \rightarrow \; [\;(\forall x(\;f(x)=g(x)\;))\leftrightarrow f=g\;]\;] $$ ?

Why such divergences in definitions exist?

Upd: Two additional questions:

  1. Why function is not a pair in $isafun_2$? First component of triple is perfectly derivable from the second.

  2. What word function exactly means if no underlying theory is specified in context? If I build fully formal knowledge base about mathematics for automated reasoning and want to add notion of contextless function -- how I must describe it?

share|improve this question
1  
I meant "equivalent" in the spirit of category theory. The answer, why there are different definitions, is simple: In analytical number theory for example, nobody cares for a fixed codomain for a function. But in other areas it may matter a lot: algebraic geometry, category theory, mathematical logic. In fact, in some definitions of a category, it is required that $hom(x,y)$ are pairwise disjoint for different $(x,y)$. –  Martin Brandenburg Jul 3 '10 at 8:56
1  
To Martin Brandenburg: Give me a couple of examples, please, when fixed codomain matters a lot and just working with function range is not enough. –  Vag Jul 3 '10 at 9:06
1  
1) Well, extensiona equality has then the form: $f=g$ iff $cod(f)=cod(g), dom(f)=dom(g)$ and $f(x)=g(x)$ for all $x \in dom(f)$. I don't think this causes any problems. 2) Try to define "surjective" with the first definition. –  Martin Brandenburg Jul 3 '10 at 9:16
1  
To Dror Speiser: I've seen numerous sources that define function as in 1st case, not only MathWorld. For instance, us.metamath.org/mpegif/df-fun.html. –  Vag Jul 3 '10 at 12:23
2  
You're right, the definition in mathworld is just not the same as Bourbaki. Maybe you can send an email to update it, so that it would contain a formal paragraph with the second definition you wrote above,. –  Dror Speiser Jul 3 '10 at 13:53

2 Answers 2

up vote 20 down vote accepted

The fact is that different subject areas of mathematics use different definitions for this basic concept. The Bourbaki definition is quite common, particularly in many of the areas well-represented here on MO, but other areas use the ordered-pair definition.

For example, if you open any set-theory text, you will find that a function $f$ is a set of ordered pairs having the functional property that any $x$ is paired with at most one $y$, denoted $f(x)$. This definition, which is completely established and much older than the Bourbaki definition, makes a function a special kind of binary relation, which is any set of ordered pairs. The domain of a function is the set of $x$ for which $f(x)$ exists. The range is the set of all such $f(x)$, and so on. The assertion $f:A\to B$ is a statement about the three objects, $f$, $A$ and $B$, that $f$ is a function with domain $A$ having its range a subset of $B$. In particular, the same function $f$ can have many different codomains.

Another useful variation of the function concept is the concept of a partial function, common in many parts of logic, particularly set theory and computability theory. A partial function on $A$ is simply a function whose domain is included in $A$. In this case, we write $f:A\to B$, but with with three dots (my MO tex ability can't seem to do it), to mean that $f$ is a function with $dom(f)\subset A$ and $ran(f)\subset B$. This notion is particularly usefful in computability theory, where one has functions that might not produce an output on all input. But it also arises in set theory, where one often build partial orders consisting of small partial functions from one set to another. The union of a chain of such functions is a function again. It would be silly to insist in the Bourbaki style that there are really invisible functors running through this construction adjusting the domains and co-domains.

One could object that the set-theorists could use the Bourbaki definition, if only they prepared better: in any context where many functions are treated, they should simply delimit an upper bound for the co-domains under consideration and use that co-domain for all the functions. But this proposal bumps into set-theoretic issues. For example, if I consider the class of all functions from an ordinal to the ordinals, then the only common co-domain is the class of all ordinals. But as this is a proper class, it isn't available if I want to consider only set functions. So there are good set-theoretic reasons not to use the Bourbaki definition.

There are numerous other basic concepts that are given different precise meanings in different subjects of mathematics. For example, the concept of tree. In graph theory, it is a graph with no loops, whereas in set theory, it is a kind of partial order. In finite combinatorics, it might be a finitte partial order having no diamonds, but in the infinitary theory, one often means a partial order such that the predecessors of every node are well-ordered (making the levels of the tree form a well-ordered hierarchy). The graph-theoretic definition does not allow for the cases of Souslin trees and Kurepa trees, which are central in the other theory.

There are surely numerous other examples where terminology differs.

share|improve this answer
9  
The term "function" is not meaningless, but the precise definition has to be established by context. The same is true for many other words: "ring" (does it have a unity?), "poset" (weak, strong, or the same as a preorder?), "graph" (is it a simple graph?), etc. We lie to students by telling them that each term in mathematics has an authoritative definition, which doesn't stand up to close scrutiny. But it has an inner truth: the precise definition of "graph" may change, but it's not going to change into the definition of a ring. –  Carl Mummert Jul 3 '10 at 13:24
2  
Vag, there are of course degrees of precision in mathematics, each serving a different kind of purpose. At the bottom underlying level, there is the hyper-precise accounts arising in the various formal systems, which would be more precise even than the definitions you and I mentioned, but few would argue that we should all operate only in that formal language just because we believe that it is possible in principle to do so. –  Joel David Hamkins Jul 3 '10 at 14:41
3  
Vag, you are asking how we manage to teach the concept of function... just go into any class where it is taught, and you'll see that these problems you seem to be talking about simply do not exist. –  Mariano Suárez-Alvarez Jul 3 '10 at 15:02
1  
In programming I've found that giving absolutely precise meaning for ANY terms is very rewarding. For instance, more rigour means more human activities to automatize or made computer assisted. And while studying mathematics I've found that almost every time I formalize some important notion I discover various mistakes, misunderstandings, nontotalities, discrepancies, etc. Human intuition is good at abstracting and searching similarities but bad at case analysis. –  Vag Jul 6 '10 at 22:06
3  
But the function concept has been made absolutely precise. In fact, it has been made fully precise twice, in two different ways. Each group prefers to use their own precise definition, for sound reasons, and I don't see how it would help anyone for you to give a third, incompatible definition, that was different than either of these. Rather than giving a "contextless" definition, you would instead merely be providing a third, unneeded, context. –  Joel David Hamkins Jul 16 '10 at 20:00

When we use the Bourbaki definition of function as a triple $(domain, codomain, graph)$, then two functions are usually defined to be equal iff their domains and graphs are equal. So equal functions can have different codomains. The problem is that the same sign "=" is used both for the the equality of functions and the "universal" equality (In ZFC, for example, the "universal" equality is defined for all sets). That is, the sign "=" is overloaded. Normally, from the context one can determine what is the intended meaning.

But there is a more serious trouble (as Vag pointed out early) with the Bourbaki definition, when a function is an element of a set. So it seems that the definition of function as a set of ordered pairs having the functional property is more preferable.

share|improve this answer
    
Let me devise some theory with contradiction in it. You'll come and see and state: "there is contradiction in it!". I'll reply: "No. This is misunderstanding on your side, because there is hidden patch that must be implicitly applied mentally while reading my theory, this patch removes contradiction completely." –  Vag Jul 5 '10 at 19:55
1  
OK, I agree with your previous comment which you deleted. Then you asked about the case when a function is an element of a set. Indeed, in this case there is a serious trouble with the Bourbaki definition. So now in my work I decided not to use the Bourbaki definition. –  Victor Makarov Jul 6 '10 at 12:32
1  
Could you explain the serious trouble you mention? Why can't we have Bourbaki triples being elements of a set? This seems to happen quite often. –  Joel David Hamkins Jul 6 '10 at 17:08
6  
That sounds like a problem with calling that relation equality, rather than a problem with the Bourbaki definition of function itself. Of course, it isn't really equality, but just an equivalence relation, whose equivalence classes are canonically indexed by the ordered-pair definition of function. But we have no reason to expect equality of sets to respect that relation. –  Joel David Hamkins Jul 6 '10 at 23:18
5  
Moschovakis uses the set-theoretic definition of function---the set of ordered pairs definition---not the Bourbaki definition. And for that definition, this notion of equivalence is equality. –  Joel David Hamkins Jul 8 '10 at 20:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.