Function (mathematics)
It has been said that functions are "the central objects of investigation" in most fields of mathematics. That is a striking claim for an idea most people first meet as a humble rule that turns one number into another. A function from a set X to a set Y assigns to each element of X exactly one element of Y. The set X carries the name domain. The set Y carries the name codomain. The whole of science, engineering, and nearly every branch of mathematics leans on this single arrangement.
The idea began as something far more physical. A function was the idealization of how one varying quantity depends on another. The position of a planet is a function of time. The position of a car on a road is a function of the time travelled and its average speed. From those concrete pictures grew a concept so general that it can describe almost anything that produces one output for each input.
What follows traces how a planet's position became a set of ordered pairs. It asks why mathematicians stopped trusting the word "assignment". It looks at the moment when a function quietly stops being defined everywhere it seems to be. And it visits the strange territory where a single function insists on having more than one value at once.
Leibniz, Newton and Euler founded calculus on a definition of function that mathematicians used for nearly two centuries. The idea of a function, starting in the 17th century, was fundamental to the new infinitesimal calculus. At that time only real-valued functions of a real variable were considered. Every function was assumed to be smooth. Until the 19th century, the functions in play were differentiable, meaning they carried a high degree of regularity.
The founders' definition could not actually be formalized, because there is no mathematical definition of an "assignment". That gap stayed open until the end of the 19th century, when the first formal definition arrived through set theory. The new definition rested on a quieter idea: a function is simply a relation between elements of the domain and some elements of the codomain.
A binary relation between two sets is a subset of their Cartesian product, the set of all ordered pairs drawn from each. A function becomes a relation satisfying two conditions: every element of the domain appears in some pair, and no element of the domain appears in two different pairs. Phrased without the word relation, a function is an ordered triple of three sets, the domain, the codomain, and the graph.
This set-theoretic move greatly increased the possible applications of the concept. Functions with arbitrary domains and codomains could now be defined. In the second half of the 19th century, the mathematically rigorous definition let functions escape the narrow world of smooth curves. That generality is usually introduced to college students with STEM majors in their second or third year.
A real function is a partial function from the set of real numbers to itself. That phrase "partial" carries weight. A partial function is defined like an ordinary one, but the requirement that every input has an output is dropped. For each input, the value is either in Y or simply undefined. The set of inputs where it is defined is called the domain of definition.
The trouble is that you often cannot see the domain by looking. The determination of the domain may require knowing the zeros of the function. A formula with a division forces you to exclude every value that makes a denominator zero. A square root forces you to keep the argument nonnegative. For a complicated function, finding the domain passes through computing the zeros of auxiliary functions.
This hidden quality can reach extreme heights. The multiplicative inverse of the Riemann zeta function has a domain of definition that is more or less equivalent to one of the major open problems in mathematics. Determining it is tied to the proof or disproof of the Riemann hypothesis.
The difficulty turns absolute in computability theory. A general recursive function is a partial function from the integers to the integers whose values can be computed by an algorithm. Its domain of definition is the set of inputs for which the algorithm does not run forever. A fundamental theorem states that no algorithm can take an arbitrary such function and test whether an input belongs to its domain. That barrier is the Halting problem.
Leonhard Euler first used functional notation in 1734, the familiar style of a name followed by an argument in parentheses. When a symbol runs to several letters with no risk of confusion, the parentheses may vanish. Some functions take a multi-letter symbol set in roman type, like "sin" for sine, in contrast to the italic font used for single-letter names.
Arrow notation takes a different path, defining the rule of a function inline without giving it a name at all. It uses the maps-to arrow, read aloud as "maps to". The notation can fix one argument of a two-variable function to produce a partially applied function, all without inventing a fresh name.
Index notation drops the parentheses entirely, writing a subscript instead. This suits functions whose domain is the natural numbers. Such a function is called a sequence, and its subscripted element is the nth element of the sequence. Subscripts also separate parameters, the variables held fixed during a problem, from the true variables.
Placeholder notation goes further still by emptying the variable of meaning. The symbol stands for nothing; it marks a slot, often an interpunct or a dash, where any value dropped in on the left must appear on the right. Specialized fields add their own marks: linear algebra and functional analysis use a dual pair to show duality, an approach similar to bra-ket notation in quantum mechanics. Logic and computation reach for lambda calculus. Category theory and homological algebra draw commutative diagrams that extend the arrow notation across whole networks of functions.
"Injective", "surjective", and "bijective" were coined as French words in the second quarter of the 20th century by the Bourbaki group, then imported into English. They replaced an older and more confusing vocabulary. "One-to-one" and "onto" filled the earlier English literature, where a single letter could change everything: "maps onto" implies surjective, while "maps into" makes no such claim, and in a long argument that one-letter difference is easily missed.
A function is injective when different inputs always give different outputs, so each codomain element has at most one preimage. An empty function is always injective. If the domain is nonempty, injectivity is exactly the existence of a left inverse, a function that undoes it from the other side.
A function is surjective when its range equals its codomain, so every codomain element is hit by some input. Assuming the axiom of choice, surjectivity is equivalent to having a right inverse. The axiom of choice is needed here precisely because defining that inverse requires picking an element from each nonempty preimage.
A function is bijective when it is both injective and surjective, a one-to-one correspondence. Every bijection admits an inverse function, and this fact, unlike the surjective case, does not require the axiom of choice. Even a function that fails to be bijective can be salvaged by restriction. The cosine function, injective on a suitable interval, yields by restriction the inverse function called arccosine.
The unit circle equation pins down the strangeness at the heart of multi-valued functions. For an input strictly inside the range, it offers two possible values of y, one positive and one negative. At the boundary the two values collapse into a single 0. Outside, there is no value at all. One equation, two implicit functions.
The square root makes the same point with a cleaner picture. For any positive real number there are two choices, the positive root and the negative root. Each is a continuous function, yet their graphs join into a single smooth curve. It is often useful to treat them as one function with two values for positive inputs, one value at 0, and none for negative inputs. Here the positive root feels more natural, but that preference does not survive in general.
Complex functions reveal why the idea matters. Extending a complex function by analytic continuation can fill almost the whole complex plane, yet two different paths can deliver two different answers. Carry the square root of negative one along a path through positive imaginary parts and you reach i; carry it through negative imaginary parts and you reach the other root. One response is a branch cut, a curve along which the function is deliberately discontinuous, giving the principal value. The other response accepts a multi-valued function whose value may jump when you loop around a singularity, a jump named the monodromy.
Some of these creatures resist all simple description. The relation that maps y to a root of a degree-five expression defines the Bring radical, a function that cannot be expressed in terms of the four arithmetic operations and nth roots.
Von Neumann-Bernays-Godel set theory shows how deep the function concept reaches into the bedrock of mathematics. It extends ordinary set theory so that the collection of all sets becomes a class. Its replacement axiom can be stated through functions: if X is a set and F is a function, then the image of X under F is also a set.
The trouble that forces such care appears with the singleton operation. Treating "the set containing s" as a function would give it a domain including all sets, and that collection is not a set. Usual mathematics sidesteps the issue by always fixing a domain, which produces many singleton functions rather than one. Logicians building foundations sometimes need functions whose domain or codomain is left unspecified, and they give precise definitions for these weakly specified objects.
Type theory offers an entirely different starting point. Rather than defining functions out of sets, it takes them as primitive notions. Functions become the inhabitants of function types, constructed using expressions in the lambda calculus.
That same lambda calculus governs how computers compute. In computer programming a function is a subroutine that produces an output for each input. Functional programming builds programs from subroutines that behave like mathematical functions, having no side effects and depending only on their arguments, a property called referential transparency. Haskell encapsulates side effects in the type of a function, while the ML family simply allows them. Three classic models, general recursive functions, lambda calculus, and the Turing machine, all define exactly the same set of computable functions. The Church-Turing thesis claims that every acceptable definition of a computable function lands on that same set.
Common questions
What is a function in mathematics?
A function from a set X to a set Y assigns to each element of X exactly one element of Y. The set X is called the domain and the set Y is called the codomain. Functions are used throughout science, engineering, and most fields of mathematics.
What is the difference between the domain and codomain of a function?
The domain is the set X of inputs to which the function assigns values, while the codomain is the set Y that holds the possible outputs. A function pairs each element of the domain with exactly one element of the codomain.
When was functional notation first used in mathematics?
Leonhard Euler first used functional notation in 1734, writing a function's name followed by its argument in parentheses. Functions are often denoted by a letter such as f, g, or h.
What is a partial function in mathematics?
A partial function from X to Y assigns at most one output to each input, so some inputs may be undefined. It is an ordinary function whose domain is a subset of X, called the domain of definition. When that domain of definition equals X, the partial function is called a total function.
What do injective, surjective, and bijective mean for a function?
A function is injective when different inputs always give different outputs, surjective when every codomain element is the output of some input, and bijective when it is both. A bijective function is a one-to-one correspondence and admits an inverse function. These terms were coined as French words in the second quarter of the 20th century by the Bourbaki group.
How was the modern definition of a function formalized?
The first formal definition of a function appeared at the end of the 19th century, stated in terms of set theory. It defines a function as a binary relation, a subset of the Cartesian product of the domain and codomain, where every domain element appears in exactly one pair. This set-theoretic formalization greatly increased the possible applications of the concept.