13
$\begingroup$

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?

$\endgroup$
13
  • 1
    $\begingroup$ 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)$. $\endgroup$ Jul 3, 2010 at 8:56
  • 1
    $\begingroup$ 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. $\endgroup$
    – Vag
    Jul 3, 2010 at 9:06
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 3, 2010 at 9:16
  • 2
    $\begingroup$ 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,. $\endgroup$ Jul 3, 2010 at 13:53
  • 2
    $\begingroup$ It seems to me that the words in Wolfram Mathworld (apparently unchanged after a decade) do not define ‘function’ at all but ‘function from $A$ to $B$’. That they later call $B$ ‘the’ codomain of $f$ lends support to this. Similarly, if somebody said ‘A subset of $A$ is a set $S$ such that every $a \in S$ belongs to $A$’, you would not think that they meant that ‘subset’ means the same as ‘set’. The superset $A$ is also part of the concept. $\endgroup$ Dec 11, 2020 at 6:47

2 Answers 2

31
$\begingroup$

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.

$\endgroup$
19
  • 12
    $\begingroup$ 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. $\endgroup$ Jul 3, 2010 at 13:24
  • 3
    $\begingroup$ 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. $\endgroup$ Jul 3, 2010 at 14:41
  • 6
    $\begingroup$ 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. $\endgroup$ Jul 3, 2010 at 15:02
  • 4
    $\begingroup$ Many words lack meaning out of context, while becoming precise in a context. Why should you expect that there is a meaning for this word outside of any context? Our various mathematical contexts are set up specifically to give words precise meanings, and there seems to be little reason why these contexts must agree. In the case of function, I took as my answer task to explain that indeed there is a difference in meaning for different subject areas. But we can all translate easily from one context to the other, and any amibguity is therefore quickly resolved. Is there any issue left? $\endgroup$ Jul 6, 2010 at 16:54
  • 5
    $\begingroup$ 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. $\endgroup$ Jul 16, 2010 at 20:00
4
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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." $\endgroup$
    – Vag
    Jul 5, 2010 at 19:55
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 6, 2010 at 12:32
  • 4
    $\begingroup$ 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. $\endgroup$ Jul 6, 2010 at 17:08
  • 14
    $\begingroup$ 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. $\endgroup$ Jul 6, 2010 at 23:18
  • 9
    $\begingroup$ 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. $\endgroup$ Jul 8, 2010 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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