32
$\begingroup$

Despite my username, my background is mostly in functional analysis where (at least to my understanding), a function $f$ is considered as a mathematical object in its own right distinctly different from the values it takes under point evaluation (i.e. $f(x)$). Another way of stating this is that the possible values of a function under evaluation are properties of the function, when considered as its own mathematical object.

However, I am reading a book about the foundations of mathematics by Kunen and he refers to a function as being identified with its graph (i.e. a set of ordered pairs) in axiomatic set theory. I was under the impression that this definition of a function as a set of ordered pairs was an oversimplification that teachers used in high school that one grew out of past calculus.

So anyways, what is the most fundamental definition of a function? Obviously we all (students of mathematics) know what a function is intuitively but formally, I have a hard time swallowing the idea that a function is the same thing as its graph. I realize that the whole point of axiomatic set theory is to make it possible to denominate every mathematical object in terms of sets but I find this definition to be particularly disappointing. I suspect that this is one of those things that just depends on what area one chooses to work in but I'd love to see what thoughts some of the more experienced mathematicians on here can offer.

$\endgroup$
16
  • 13
    $\begingroup$ You can put down all sorts of formalisms, none of which seem to be satisfactory in all contexts. $\endgroup$
    – Ian
    Commented Dec 11, 2016 at 22:06
  • 6
    $\begingroup$ The possessive its does not have an apostrophe. Sort of backwards of usage for people. It's means it is, one of those contractions. $\endgroup$
    – Will Jagy
    Commented Dec 11, 2016 at 22:07
  • 31
    $\begingroup$ I don't quite see what's so disappointing about the graph definition. $\endgroup$
    – user159517
    Commented Dec 11, 2016 at 22:08
  • 17
    $\begingroup$ Even if you want to believe that a function something other than its graph, you should at least agree that a function is determined by its collection of ordered pairs $\endgroup$ Commented Dec 11, 2016 at 22:13
  • 13
    $\begingroup$ I think the only "disappointment" in areas like functional analysis is that you can't recover the intended codomain of a function from its graph. Under the usual topology on $\Bbb{R}$, $x \mapsto \sqrt{x}$ is open when viewed as a member of $\Bbb{R} \to \Bbb{R_{\ge0}}$ but not when viewed as a member of $\Bbb{R} \to \Bbb{R}$. $\endgroup$
    – Rob Arthan
    Commented Dec 11, 2016 at 22:41

7 Answers 7

46
$\begingroup$

There are two common "general" definitions for functions in modern mathematics:

  1. A function is a set (or class) of ordered pairs with a particular property: if $(x,y)$ and $(x,z)$ both belong to the function, then $y=z$.

  2. A function is an ordered triplet, $(A,B,f)$ with $f$ being a set of ordered pairs as the previous definition goes, with domain $A$ and range a subset of $B$.

(There can be other definitions, depending on the context.)

These definitions are not "an oversimplification that teachers used in high school", and certainly not something to "grow out of" past calculus. In fact, in most high schools, a student is likely to believe that a function is always given by some sort of formula, whereas in both of these abstract definitions no formula is needed, and in many cases, one cannot even assume there is a formula in the meta-language which defines the graph of the function.

There is no reason to be disappointed by this formalization any more than there is to be disappointed by the implementation of "integer" as a number in a finite range (such as $-2^{31}$ to $2^{31}-1$) when it comes to programming in C. Functions, as well as integers in C, are useful to us and their formalization works out just fine; and whenever we reach some limitations of these formalizations we can bypass them (with class functions in set theory, and with bignum libraries in C, often limited mostly by available memory).

There are two good reasons not to think of functions in terms of "properties":

  1. When formalizing mathematics, one can show that in general one should not expect every mathematical object to have "expressible properties". Namely, given the real numbers, and any "naively reasonable naming mechanism" there will be real numbers which cannot be named. So if we cannot expect every real number to have a discerning property, why should we expect more complicated objects to have them?

  2. The point of set theory as a foundational theory is to implement mathematics at a semantic level. Namely, interpret objects as sets. Having a very simple definition for a set (in a technical sense of "very simple") is a good thing, and it allows the foundations to carry all sort of theorems. For example, when talking about sufficiently simple statements about the natural numbers, one can omit the axiom of choice from the assumptions.

    One of the reasons this can be done is that our interpretation of "function" is sufficiently simple that we can be certain it does not change between our original universe, and an inner universe where the axiom of choice holds. That way we can ensure that if the statement was true in the inner universe, it will remain true in our universe as well. Of course, one could perhaps formalize similar theorems for however you wish to encode functions into sets, but the more complicated the coding mechanism becomes, the more fragile our theorems become, and it gets harder to prove them.

    So simplicity has its benefits when it comes to actually proving things from a foundational point of view.

$\endgroup$
17
  • 2
    $\begingroup$ C has unsigned long long standardized since 1999. $\endgroup$ Commented Dec 11, 2016 at 22:43
  • 3
    $\begingroup$ C's $\mathtt{int}$ types have also supported negative values since the C language was first implemented in the 1970s. What the heck has C got to do with this? $\endgroup$
    – Rob Arthan
    Commented Dec 11, 2016 at 22:47
  • 3
    $\begingroup$ @Daniel: Yes, I'm aware of the existence of long integers. But I hope that it's sufficiently clear that the point I'm trying to make does not depend on a fixed integer type interpretation of C99 or whatever similar programming language. $\endgroup$
    – Asaf Karagila
    Commented Dec 11, 2016 at 22:49
  • 3
    $\begingroup$ @Rob: If it bothers you that much, feel free to edit unsigned into my answer. $\endgroup$
    – Asaf Karagila
    Commented Dec 11, 2016 at 22:50
  • 2
    $\begingroup$ @Asaf: a C implementation with 33 bit integers could comply with the C standard, but while you were writing your comment, I was busy changing $32$ to $31$. $\ddot{\smile}$. $\endgroup$
    – Rob Arthan
    Commented Dec 11, 2016 at 23:02
11
$\begingroup$

How you view a function depends on what you want to do with that function. If set theory is your foundation then functions are modeled as being pairs of elements between the elements of the domain and that elements image in the codomian.

However in type theories a function is treated as a fundamental thing that can't be simplified. We simply describe how functions map between types via lambda calculus.

In category theory the fact that function map elements becomes of less importance as a functions behaviour as it is composed with other functions becomes more important.

$\endgroup$
10
$\begingroup$

In general, mathematicians aren't so interested in what things are, more in what things do. A function is a thing that you can apply to objects to obtain other objects. It doesn't really matter if you define a function as a graph, as a triplet (domain, codomain, graph), a first-class object, or something else entirely - it still represents the same abstract concept. (Assuming the definition supports this concept, of course).

Once you establish the basic properties of functions, you can pretty much forget the definition. Just like I know that 4+5=9 without caring if I defined natural numbers as sets of all smaller natural numbers, or something else.

Personally I find the definition as a graph more elegant than the triplet definition. Specifying the domain is unnecessary since it is uniquely obtainable from the graph. Specifying the codomain does add some information, but this extra information is often irrelevant. Not to mention that triplets are by themselves messy to define.

Even with the graph definition, the function is still "a mathematical object in its own right". The collection of all values it gives to all inputs is an abstraction that transcends any single value it takes.

$\endgroup$
5
  • 1
    $\begingroup$ I agree with almost everything, but saying that specifying codomain is useless is the same as saying discriminating between surjection and non-surjection is useless. It most certainly is not. $\endgroup$
    – Ennar
    Commented Dec 12, 2016 at 21:04
  • 3
    $\begingroup$ @Ennar: You can specify the intended codomain separately when it's important. For a function $f$ defined as a graph, it's meaningless to say "$f$ is surjective", but you can definitely say "$f$ is onto $B$" or "$f$ is a bijection from $A$ to $B$". $\endgroup$ Commented Dec 12, 2016 at 21:25
  • $\begingroup$ Yes you can and in almost all cases should. There is big difference between $x\mapsto x^2:\Bbb R_+\to \Bbb R$ and $x\mapsto x^2:\Bbb R_+\to \Bbb R_+$. Saying codomain brings useless information is plainly wrong. There are many cases in practice when you simply don't know how to calculate range of a function directly and use abstract machinery to find it (what is the range of $x\mapsto x^3$ with domain $\Bbb R$?). $\endgroup$
    – Ennar
    Commented Dec 12, 2016 at 21:48
  • $\begingroup$ And since OP comes from functional analysis, let us just contemplate on the difference between codomain being Banach space or not. $\endgroup$
    – Ennar
    Commented Dec 12, 2016 at 21:57
  • $\begingroup$ @Ennar: I've edited the answer slightly to account for the possibility that the codomain could be useful. $\endgroup$ Commented Dec 13, 2016 at 9:53
8
$\begingroup$

First off, let me preface my answer by noting that the question of what something "really is" is a red herring, or even actively harmful — in the end, what matters is that we have one or more ways of encoding a notion in mathematical terms, and can express what one can do with the notion in said terms.


Historically, the notion of relation has had priority. For example, when you had a point restricted to moving about on the standard parabola, one spoke in terms like "$x$ and $y$ are two variables related by the equation $y = x^2$", not "there is a function $f$ so that $(x, f(x))$ lies on the parabola for all $x$".

Similarly, logic has historically been about propositions and predicates — properties that objects might have, and relations between objects — and one expresses the general idea of function as being a special kind of relation.

Even if one has a notion of function symbols for constructing terms, such as elementary arithmetic operations $+,-,\times,\div$, that's not sufficient for the general notion of function. For example, one might want to define the real square root function, and an essential part of this is to use the relation "$y \times y = x \text{ and } y \geq 0$".

Now, logic and set theory are heavily intertwined, to the point where one might even say that set theory is the same thing as higher order logic. Sets mimic logical predicates, with the assertion "$x \in P$" corresponding to the assertion "$x$ has property $P$". All of the set operations reflect various aspects of logic; e.g. the intersection of sets $X \cap Y$ corresponds to the conjunction of predicates $X \wedge Y$, the existence of product sets $X \times Y$ corresponds to the fact we can simultaneously talk about $x \in X$ and $y \in Y$, and so forth.

So once we've established a function from $X$ to $Y$ can be expressed as a predicate on $X \times Y$, we immediately equate the notion with that of a subset of $X \times Y$. That subset is precisely the graph of the function.


That said, there are alternate but more or less equivalent ways to develop things. In addition to predicate logic, we have things simply typed lambda calculus or dependent type theory. In addition to Zermelo set theory, we have things like ETCS (the "elementary theory of the category of sets").

$\endgroup$
8
$\begingroup$

Fix two sets $X,Y$. A relation $R$ from $X$ to $Y$ is merely a subset of the cartesian product $X\times Y$. We say $x$ is related to $y$ if $(x,y)\in R$. A relation is thus a choice of pairs $(x,y)$. A function from $X$ to $Y$ is a relation $f$ from $X$ to $Y$ such that,

for each $x\in X$, there is exactly one $y\in Y$ such that $(x,y)\in f$, which we usually denote $f(x)$.

Then $f = \{ (x,f(x)) : x\in X\}$ may be the graph you were thinking about. As noted in the comments, the function $f$ is not only the data of the graph, but also of the source $X$ and target $Y$, whence the complete notation reads $f:X\longrightarrow Y$ for "$f$ is a function from $X$ to $Y$."

$\endgroup$
4
  • 1
    $\begingroup$ More exactly, a relation is the triplet made up of $X$, $Y$ and a subset $R$ of $X\times Y$. $\endgroup$
    – Bernard
    Commented Dec 11, 2016 at 22:16
  • 1
    $\begingroup$ @Bernard, you are correct, but from categorical point of view, one often defines morphisms as members of hom-set $\operatorname{Hom}(X,Y)$ for each pair of objects in a category, rather than globally. $\endgroup$
    – Ennar
    Commented Dec 11, 2016 at 22:25
  • $\begingroup$ Seems like this is relevant to this answer: math.stackexchange.com/questions/442522/… $\endgroup$
    – Squirtle
    Commented Dec 13, 2016 at 18:52
  • $\begingroup$ Why is the set of ordered pairs that belong to a function called a graph? The word graph can easily mislead one into thinking about a geometric cartesian 2-d plot of the ordered pairs. But this is wrong, since one has to pick a coordinate system to graph this way; e.g. a rectangular coordinate graph or a polar graph, etc. Formally a function is just a subset of the Cartesian product of the domain and codomain with some additional properties like well defined-edness. You don't have to graph these ordered pairs. You can just list the ordered pairs in a set e.g. $\{ (0,0), (1,1) (2,2) \}$. $\endgroup$
    – john
    Commented Feb 16 at 21:03
6
$\begingroup$

You might be interested in categorical perspective: we have notion of objects and notion of morphisms between pairs of objects. Thus, from categorical point of view, there is a category $\bf{Set}$ whose object are sets and morphisms between two sets are functions. In this perspective, we don't actually care how functions are implemented, but how they behave. In functional analysis one could for example study category of Banach spaces and bounded linear maps, or some other category of topological vector spaces.

William Lawvere found axioms known as ETCS that categorically encode notion of sets (note that this does not give ZFC, there is no replacement in ETCS). Now, this hasn't really caught on in mainstream mathematics (as far as I know) and I doubt it has uses in functional analysis.

The point I want to make is that any kind of (foundational) theory gives implementation of notions one wants to work with. There are many possibilities and what you choose depends on what you want to do with it. Many mathematicians won't care how basic notions such as functions are implemented, as long as they can use their familiar properties. Since we are talking about functions, let's take a step back and ask ourselves what ordered pair is in the first place. Wiki article lists three possible ways. Personally, I don't care whether $(a,b) = \{\{a\},\{a,b\}\}$ or $(a,b) = \{\{\{a\},\emptyset\},\{\{b\}\}\}$ as long as I know $(a,b) =(a',b')$ iff $a=a'$ and $b=b'$. The same goes for functions, all I care is that for $f,g\colon X\to Y$, $f=g$ iff $f(x) = g(x),\forall x\in X$ (note how this is very nicely encoded by "graph definition" of a function).

$\endgroup$
2
  • $\begingroup$ Good answer. Note it is possible to reject functional extensionality where $f = g$ if $f(x) = g(x) \forall x \in X$, if you view a function as a procedure and not just as a black-box assignment of outputs to inputs -- this isn't the standard understanding of a function in mainstream math, but it's done in constructive settings. I think the most fundamental thing everyone could agree on is that a function can be applied to an element of its domain to produce an element of its codomain. $\endgroup$ Commented Dec 13, 2016 at 10:00
  • 1
    $\begingroup$ @6005, thank you. I'm not really familiar with constructive settings, but I do agree it is fundamental that we apply functions on domain to produce something in codomain. $\endgroup$
    – Ennar
    Commented Dec 13, 2016 at 14:56
1
$\begingroup$

One approach to answering "what is" a function is to ask: how could we tell if two functions are different? This is closely tied to a famous phrase "no entity without identity" from Quine in the philosophy of mathematics.

The motivation of this approach is that, if there is some kind of information that we use to tell two functions apart, then that information must be an intrinsic part of the notion of "function". On the other hand, if there is information that we do not use to distinguish functions, then that information is not an intrinsic part.

For most modern mathematics, function identity is treated extensionally: two functions are the same if they have the same domain and have the same value at each point of the domain. In some contexts, functions also have a specified codomain, and to be equal two functions must also have the same codomain.

So, looking at that criterion for identity of functions, the key information is the graph of the function, the domain of the function if it is not clear from the graph, and the codomain of the function if we wish to specify that. No other information is needed to tell whether two functions are the same, and so based on the approach I am describing no other information is intrinsic to the notion of "function".

Of course, this leads exactly to the definitions of a function that are mentioned in the answer by Asaf Karagila. The point of this post is to point out a well motivated way at arriving at those definitions.

There is one other thing that I want to mention in this post, which is that the notion of function identity is sometimes different, in areas such as some parts of constructive mathematics and lambda calculus. In most mathematics, the expressions $y = 2(x+1)$ and $y = 2x+2$ are viewed as defining the same function from $\mathbb{N}$ to $\mathbb{N}$. This means that the defining formula (when there is one) is not usually considered part of the notion of "function". In other areas, function equality is treated "intensionally" rather than extensionally, and so those formulas are viewed as defining different intensional functions, because in these areas the formula for a function is viewed as an intrinsic part of the function.

$\endgroup$
3
  • $\begingroup$ Carl Mummert: Have you considered, and/or would you consider running in the 2018 moderator election? A number of us find you an ideal candidate, but the presumption is that you may not be interested. I thought I'd "flat out" ask you, yourself. $\endgroup$
    – amWhy
    Commented Aug 3, 2018 at 15:13
  • $\begingroup$ @amWhy: Thank you for the vote of confidence - it’s really appreciated. I am afraid I am already overcommitted this year, and the time and patience needed for moderating are not something that can be done in a hurry. Some of my obligations may go away after this year, and I may be able to think again about moderating then. $\endgroup$ Commented Aug 4, 2018 at 19:07
  • $\begingroup$ Thanks for commenting. I'll check in with you early next election!! $\endgroup$
    – amWhy
    Commented Aug 4, 2018 at 19:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .