In mathematics, a function^{[1]} is a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output. An example is the function that relates each real number x to its square x^{2}. The output of a function f corresponding to an input x is denoted by f(x) (read "f of x"). In this example, if the input is −3, then the output is 9, and we may write f(−3) = 9. Likewise, if the input is 3, then the output is also 9, and we may write f(3) = 9. (The same output may be produced by more than one input, but each input gives only one output.) The input variable(s) are sometimes referred to as the argument(s) of the function.
Functions of various kinds are "the central objects of investigation"^{[2]} in most fields of modern mathematics. There are many ways to describe or represent a function. Some functions may be defined by a formula or algorithm that tells how to compute the output for a given input. A picture, with some input, output pairs shown on Cartesian coordinates, is called the graph of the function, and may give an intuitive idea of some of the main features of the function, for example its maximums and minimums. In science, functions are sometimes defined by a table that gives the outputs for selected inputs. In this case, if there is reason to believe the function is smooth, it is sometimes assumed that the values in between the points on the table also exist, but are not known with the accuracy of the measured points. For example, a table might give the temperature at a particular place at specified times, with the assumption that the temperature is a smooth function of time, even though the temperature at times other than those measured is not known. Another form in which functions are given is the implicit function, for example as an inverse to another function or as a solution of a differential equation.
In modern mathematics,^{[3]} a function is defined by its set of inputs, called the domain; a set containing the set of outputs, and possibly additional elements, as members, called its codomain (or target); and the set of all input-output pairs, called its graph. Sometimes the codomain is called the function's "range", but more commonly the word "range" is used to mean, instead, specifically the set of outputs (this is also called the image of the function). For example, we could define a function using the rule f(x) = x^{2} by saying that the domain and codomain are the real numbers, and that the graph consists of all pairs of real numbers (x, x^{2}). The image of this function is the set of non-negative real numbers. Collections of functions with the same domain and the same codomain are called function spaces, the properties of which are studied in such mathematical disciplines as real analysis, complex analysis, and functional analysis.
In analogy with arithmetic, it is possible to define addition, subtraction, multiplication, and division of functions, in those cases where the output is a number. Another important operation defined on functions is function composition, where the output from one function becomes the input to another function.
For an example of a function, let X be the set consisting of four shapes: a red triangle, a yellow rectangle, a green hexagon, and a red square; and let Y be the set consisting of five colors: red, blue, green, pink, and yellow. Linking each shape to its color is a function from X to Y: each shape is linked to a color (i.e., an element in Y), and each shape is "linked", or "mapped", to exactly one color. There is no shape that lacks a color and no shape that has more than one color. This function will be referred to as the "color-of-the-shape function".
The input to a function is called the argument and the output is called the value. The set of all permitted inputs to a given function is called the domain of the function, while the set of permissible outputs is called the codomain. Thus, the domain of the "color-of-the-shape function" is the set of the four shapes, and the codomain consists of the five colors. The concept of a function does not require that every possible output is the value of some argument, e.g. the color blue is not the color of any of the four shapes in X.
A second example of a function is the following: the domain is chosen to be the set of natural numbers (1, 2, 3, 4, ...), and the codomain is the set of integers (..., −3, −2, −1, 0, 1, 2, 3, ...). The function associates to any natural number n the number 4−n. For example, to 1 it associates 3 and to 10 it associates −6.
A third example of a function has the set of polygons as domain and the set of natural numbers as codomain. The function associates a polygon with its number of vertices. For example, a triangle is associated with the number 3, a square with the number 4, and so on.
The term range is sometimes used either for the codomain or for the set of all the actual values a function has.
The concepts of "rules" and "associates", that are used in the above intuitive explanation of functions are not really defined. Therefore this explanation must be completed with a formal definition, which relies on the notion of ordered pair.
A function f from X to Y is set of ordered pairs (x, y) such that x ∈ X and y ∈ Y, which is subject to the following condition: every element of X is the first component of one and only one ordered pair in the set.^{[4]} In other words, for every x in X there is exactly one element y such that the ordered pair (x, y) belongs to the set of pairs defining the function f.
In this definition, X and Y are respectively called the domain and the codomain of the function f. If (x, y) belongs to the set defining f, then y is the value of f for the argument x, or the image of x under f. One says also that y is the value of f for the value x of the variable.
This formal definition is a precise rendition of the idea that to each x is associated an element y of Y, namely the uniquely specified element y with the property just mentioned.
Considering the "color-of-the-shape" function above, the set X is the domain consisting of the four shapes, while Y is the codomain consisting of five colors. The "color-of-the-shape" function described above consists of the set of those ordered pairs, (shape, color) where the color is the actual color of the given shape.
A function f with domain X and codomain Y is commonly denoted
or
The notation
means that (x, y) belongs to the set of pairs defining the function f. When it is needed to refer explicitly to this set of pairs, it is denoted
The symbol used to denote a particular function consists generally of a single letter in italic font, most often the lower-case letters f, g, h. Some widely used functions are represented by a symbol consisting of several letters (generally an abbreviation of their name). In this case, it is set in roman type, such as "sin" for the sine function.
Sometimes the parentheses of the functional notation are omitted if no ambiguity arises, as for instead of
In many cases, a function is defined by a formula that describes how the value of the function is computed from the value of the argument. For example, if a multiplication is defined on a set X, then one may define a square function with domain and codomain X by
or, more commonly,
Similarly, the identity function on a set X is the function
This notation is useful for avoiding naming a function when not necessary, as in the sentence "the square function is the function f defined by f(x) = x^2."
The definition of a function by a formula may use case distinction as for the definition of the absolute value of real numbers:
Normally the definition of a function includes the definition of its domain and its codomain, but it is not always the case. Typically, a function from the reals to the reals does not always refer to a function that has the real numbers a domain. This refers often to a function which has a subset of the reals as domain. In many cases some computation is needed if one want to know the domain exactly (see partial function). For example, if f is a function that has the real numbers as domain and codomain, then is a (possibly partial) function from the reals to the reals whose domain is the set of the reals x such that f(x) ≠ 0. In many cases, this set is difficult to determine exactly, and often, this is not a problem for working with the function.
Finally, dot notation is occasionally used for avoiding naming the variable. For example, may stand for , and may stand for the integral function .
A function can be defined by any mathematical condition relating each argument (input value) to the corresponding output value. If the domain is finite, a function f may be defined by simply tabulating all the arguments x and their corresponding function values f(x). More commonly, a function is defined by a formula, or (more generally) an algorithm — a recipe that tells how to compute the value of f(x) given any x in the domain.
There are many other ways of defining functions. Examples include piecewise definitions, induction or recursion, algebraic or analytic closure, limits, analytic continuation, infinite series, and as solutions to integral and differential equations. The lambda calculus provides a powerful and flexible syntax for defining and combining functions of several variables. In advanced mathematics, some functions exist because of an axiom, such as the Axiom of Choice.
The graph of a function is its set of ordered pairs F. This is an abstraction of the idea of a graph as a picture showing the function plotted on a pair of coordinate axes; for example, (3, 9), the point above 3 on the horizontal axis and to the right of 9 on the vertical axis, lies on the graph of y = x^{2}.
Different formulas or algorithms may describe the same function. For instance f(x) = (x + 1) (x − 1) is exactly the same function as f(x) = x^{2} − 1.^{[5]} Furthermore, a function need not be described by a formula, expression, or algorithm, nor need it deal with numbers at all: the domain and codomain of a function may be arbitrary sets. One example of a function that acts on non-numeric inputs takes English words as inputs and returns the first letter of the input word as output.
As an example, the factorial function is defined on the nonnegative integers and produces a nonnegative integer. It is defined by the following inductive algorithm: 0! is defined to be 1, and n! is defined to be n(n − 1)! for all positive integers n. The factorial function is denoted with the exclamation mark (serving as the symbol of the function) after the variable (postfix notation).
Functions that send integers to integers, or finite strings to finite strings, can sometimes be defined by an algorithm, which gives a precise description of a set of steps for computing the output of the function from its input. Functions definable by an algorithm are called computable functions. For example, the Euclidean algorithm gives a precise process to compute the greatest common divisor of two positive integers. Many of the functions studied in the context of number theory are computable.
Fundamental results of computability theory show that there are functions that can be precisely defined but are not computable. Moreover, in the sense of cardinality, almost all functions from the integers to integers are not computable. The number of computable functions from integers to integers is countable, because the number of possible algorithms is. The number of all functions from integers to integers is higher: the same as the cardinality of the real numbers. Thus most functions from integers to integers are not computable. Specific examples of uncomputable functions are known, including the busy beaver function and functions related to the halting problem and other undecidable problems.
There are a number of general basic properties and notions. In this section, f is a function with domain X and codomain Y.
If A is any subset of the domain X, then f(A) is the subset of the codomain Y consisting of all images of elements of A. We say the f(A) is the image of A under f. The image of f is given by f(X). On the other hand, the inverse image (or preimage, complete inverse image) of a subset B of the codomain Y under a function f is the subset of the domain X defined by
So, for example, the preimage of {4, 9} under the squaring function is the set {−3,−2,2,3}. The term range usually refers to the image,^{[6]} but sometimes it refers to the codomain.
By definition of a function, the image of an element x of the domain is always a single element y of the codomain. However, the preimage of a singleton set (a set with exactly one element) may in general contain any number of elements. For example, if f(x) = 7 (the constant function taking value 7), then the preimage of {5} is the empty set but the preimage of {7} is the entire domain. It is customary to write f^{−1}(b) instead of f^{−1}({b}), i.e.
This set is sometimes called the fiber of b under f. (This notation is the same as that for the inverse function. However, the inverse function of a function is defined if and only if the function is one-to-one and onto. See below of the definition of these terms.)
Use of f(A) to denote the image of a subset A ⊆ X is consistent so long as no subset of the domain is also an element of the domain. In some fields (e.g., in set theory, where ordinals are also sets of ordinals) it is convenient or even necessary to distinguish the two concepts; the customary notation is f[A] for the set { f(x): x ∈ A }. Likewise, some authors use square brackets to avoid confusion between the inverse image and the inverse function. Thus they would write f^{−1}[B] and f^{−1}[b] for the preimage of a set and a singleton.
A function is called injective (or one-to-one; 1-1) if f(a) ≠ f(b) for any two elements a, b, a ≠ b of the domain. It is called surjective (or onto) if the range is identical to the codomain; that is, f(X) = Y. In other words, every element y in the codomain is mapped to by f from some x in the domain. Finally f is called bijective (or the function is a one-to-one correspondence) if it is both injective and surjective. A function that is injective, surjective, or bijective is referred to as an injection, a surjection, or a bijection, respectively. The existence of injections, surjections, or bijections between sets is the key concept defining the relative cardinalities (sizes) of the sets.
"One-to-one" and "onto" are terms that were more common in the older English language literature; "injective", "surjective", and "bijective" were originally coined as French words in the second quarter of the 20th century by the Bourbaki group and imported into English. As a word of caution, "a one-to-one function" is one that is injective, while a "one-to-one correspondence" refers to a bijective function. Also, the statement "f maps A onto B" differs from "f maps A into B" in that the former implies that f is an onto function (i.e., surjective), while the latter makes no assertion about the nature of the mapping. In more complicated statements the one letter difference can easily be missed. Due to the confusing nature of this older terminology, these terms have declined in popularity relative to the Bourbakian terms.
The above "color-of-the-shape" function is not injective, since two distinct shapes (the red triangle and the red rectangle) are assigned the same value. Moreover, it is not surjective, since the image of the function contains only three, but not all five colors in the codomain.
The function composition of two functions takes the output of one function as the input of a second one. More specifically, the composition of f: X → Y with a function g: Y → Z is the function defined by
That is, the value of x is obtained by first applying f to x to obtain y = f(x) and then applying g to y to obtain z = g(y). In the notation , the function on the right, f, acts first and the function on the left, g acts second, reversing English reading order. The notation can be memorized by reading the notation as "g of f" or "g after f".
The composition is only defined when the codomain of f: X → Y is the domain of g: Y → Z. For that reason composition is not commutative, only when both functions are closed on the same domain, i.e. the domain and the codomain are the same , they can be composed in both ways and . But it does not imply that and are the same function.
That is, the order of the composition is important. For example, suppose f(x) = x^{2} and g(x) = x+1. Then g(f(x)) = x^{2}+1, while f(g(x)) = (x+1)^{2}, which is x^{2}+2x+1, a different function.
The unique function over a set X that maps each element to itself is called the identity function for X, and typically denoted by id_{X}. Each set has its own identity function, so the subscript cannot be omitted unless the set can be inferred from context. Under composition, an identity function is "neutral": if f is any function from X to Y, then
Informally, a restriction of a function f is the result of trimming its domain. More precisely, if S is any subset of X, the restriction of f to S is the function f_{S} from S to Y such that f_{S}(s) = f(s) for all s in S. If g is a restriction of f, then it is said that f is an extension of g.
The overriding of f: X → Y by g: W → Y (also called overriding union) is an extension of g denoted as (f ⊕ g): (X ∪ W) → Y. Its graph is the set-theoretical union of the graphs of g and f_{X \ W}. Thus, it relates any element of the domain of g to its image under g, and any other element of the domain of f to its image under f. Overriding is an associative operation; it has the empty function as an identity element. If f_{X ∩ W} and g_{X ∩ W} are pointwise equal (e.g., the domains of f and g are disjoint), then the union of f and g is defined and is equal to their overriding union. This definition agrees with the definition of union for binary relations.
An inverse function for f, denoted by f^{−1}, is a function in the opposite direction, from Y to X, satisfying
That is, the two possible compositions of f and f^{−1} need to be the respective identity maps of X and Y.
As a simple example, if f converts a temperature in degrees Celsius C to degrees Fahrenheit F, the function converting degrees Fahrenheit to degrees Celsius would be a suitable f^{−1}.
Such an inverse function exists if and only if f is bijective. In this case, f is called invertible. The notation (or, in some texts, just ) and f^{−1} are akin to multiplication and reciprocal notation. With this analogy, identity functions are like the multiplicative identity, 1, and inverse functions are like reciprocals (hence the notation).
For any set A, there is exactly one function from the empty set to A, namely the empty function:
The graph of an empty function is a subset of the Cartesian product ∅ × A. Since the product is empty the only such subset is the empty set ∅. The empty subset is a valid graph since for every x in the domain ∅ there is a unique y in the codomain A such that (x, y) ∈ ∅ × A. This statement is an example of a vacuous truth since "there is no x in the domain."
In category theory the existence of an empty function from ∅ to ∅ is required to make the category of sets a category, because in a category each object needs to have an "identity morphism", and only the empty function is the identity on the object ∅. The existence of a unique empty function from ∅ into each set A means that the empty set is an initial object in the category of sets. In terms of cardinal arithmetic, it means that k^{0} = 1 for every cardinal number k—particularly profound when k = 0 to illustrate the strong statement of indices pertaining to 0.
A real-valued function f is one whose codomain is the set of real numbers or a subset thereof. If, in addition, the domain is also a subset of the reals, f is a real valued function of a real variable. The study of such functions is called real analysis.
Real-valued functions enjoy so-called pointwise operations. That is, given two functions
where X is an arbitrary set, their (pointwise) sum f + g and product f ⋅ g are functions with the same domain and codomain. They are defined by the formulas:
In a similar vein, complex analysis studies functions whose domain and codomain are both the set of complex numbers. In most situations, the domain and codomain are understood from context, and only the relationship between the input and output is given, but if , then in real variables the domain is limited to non-negative numbers.
The following table contains a few particularly important types of real-valued functions:
Linear function | Quadratic function |
---|---|
Discontinuous function | Trigonometric functions |
Roughly speaking, a continuous function is one whose graph can be drawn without lifting the pen. | (red), (blue) |
A multivariate function is one which takes several inputs.
There are many other special classes of functions that are important to particular branches of mathematics, or particular applications. Here is a partial list:
The set of all functions from a set X to a set Y is denoted by X → Y, by [X → Y], or by Y^{X}. The latter notation is motivated by the fact that, when X and Y are finite and of size X and Y, then the number of functions X → Y is Y^{X} = Y^{X}. This is an example of the convention from enumerative combinatorics that provides notations for sets based on their cardinalities. If X is infinite and there is more than one element in Y then there are uncountably many functions from X to Y, though only countably many of them can be expressed with a formula or algorithm.
An alternative approach to handling functions with multiple arguments is to transform them into a chain of functions that each takes a single argument. For instance, one can interpret Add(3,5) to mean "first produce a function that adds 3 to its argument, and then apply the 'Add 3' function to 5". This transformation is called currying: Add 3 is curry(Add) applied to 3. There is a bijection between the function spaces C^{A×B} and (C^{B})^{A}.
When working with curried functions it is customary to use prefix notation with function application considered left-associative, since juxtaposition of multiple arguments—as in (f x y)—naturally maps to evaluation of a curried function. Conversely, the → and ⟼ symbols are considered to be right-associative, so that curried functions may be defined by a notation such as f: ℤ → ℤ → ℤ = x ⟼ y ⟼ x·y.
The definitions of function and image in set theory are more general than the ones given above—namely, the definition of function does not mention a domain or a codomain, and the definition of the image F[A] does not require that A be a subset of the domain.^{[7]} Set theory also specializes its function definition to the cases where the domain or both the domain and codomain are specified. This produces the following three definitions.^{[8]}
The first definition allows the use of functions without specifying their domain or codomain. For example, this definition is used to state the replacement axiom of von Neumann–Bernays–Gödel set theory: For all classes F and for all sets X, if F is a function, then F[X] is a set. Since this definition uses set theory's definition of image, X does not have to be a subset or subclass of the domain of F.
The second definition can be used to define a set or class of functions without specifying a codomain. For example, the class of functions on the ordinal α. Also, an infinite sequence can be defined as a function on ω, the set of finite ordinals.
The third definition requires that the function's domain and codomain be specified. For example, the aleph function is a function from the class of ordinals to the class of infinite cardinals. Its function values are denoted by using a subscript: , rather than by using parentheses: . The notation extends the sequence notation into the transfinite.
The above definition of "a function from X to Y" is generally agreed on,^{[citation needed]} however there are two different ways a "function" is normally defined where the domain X and codomain Y are not explicitly or implicitly specified. Usually this is not a problem as the domain and codomain normally will be known. With one definition saying the function defined by f(x) = x^{2} on the reals does not completely specify a function as the codomain is not specified, and in the other it is a valid definition.
In the other definition a function is defined as a set of ordered pairs where each first element only occurs once. The domain is the set of all the first elements of a pair and there is no explicit codomain separate from the image.^{[9]}^{[10]} Concepts like surjective have to be refined for such functions, more specifically by saying that a (given) function is surjective on a (given) set if its image equals that set. For example, we might say a function f is surjective on the set of real numbers.
If a function is defined as a set of ordered pairs with no specific codomain, then f: X → Y indicates that f is a function whose domain is X and whose image is a subset of Y. This is the case in the ISO standard.^{[6]} Y may be referred to as the codomain but then any set including the image of f is a valid codomain of f. This is also referred to by saying that "f maps X into Y"^{[6]} In some usages X and Y may subset the ordered pairs, e.g. the function f on the real numbers such that y=x^{2} when used as in f: [0,4] → [0,4] means the function defined only on the interval [0,2].^{[11]} With the definition of a function as an ordered triple this would always be considered a partial function.
An alternative definition of the composite function g(f(x)) defines it for the set of all x in the domain of f such that f(x) is in the domain of g.^{[12]} Thus the real square root of −x^{2} is a function only defined at 0 where it has the value 0.
Functions are commonly defined as a type of relation. A relation from X to Y is a set of ordered pairs (x, y) with x ∈ X and y ∈ Y. A function from X to Y can be described as a relation from X to Y that is left-total and right-unique. However, when X and Y are not specified there is a disagreement about the definition of a relation that parallels that for functions. Normally a relation is just defined as a set of ordered pairs and a correspondence is defined as a triple (X, Y, F), however the distinction between the two is often blurred or a relation is never referred to without specifying the two sets. The definition of a function as a triple defines a function as a type of correspondence, whereas the definition of a function as a set of ordered pairs defines a function as a type of relation.
Many operations in set theory, such as the power set, have the class of all sets as their domain, and therefore, although they are informally described as functions, they do not fit the set-theoretical definition outlined above, because a class is not necessarily a set. However some definitions of relations and functions define them as classes of pairs rather than sets of pairs and therefore do include the power set as a function.^{[13]}
In some parts of mathematics, including recursion theory and functional analysis, it is convenient to study partial functions in which some values of the domain have no association in the graph; i.e., single-valued relations. For example, the function f such that f(x) = 1/x does not define a value for x = 0, since division by zero is not defined. Hence f is only a partial function from the real line to the real line. The term total function can be used to stress the fact that every element of the domain does appear as the first element of an ordered pair in the graph.
In other parts of mathematics, non-single-valued relations are similarly conflated with functions: these are called multivalued functions, with the corresponding term single-valued function for ordinary functions.
The concept of function can be extended to an object that takes a combination of two (or more) argument values to a single result. This intuitive concept is formalized by a function whose domain is the Cartesian product of two or more sets.
For example, consider the function that associates two integers to their product: f(x, y) = x·y. This function can be defined formally as having domain ℤ×ℤ, the set of all integer pairs; codomain ℤ; and, for graph, the set of all pairs ((x, y), x·y). The first component of any such pair is itself a pair (of integers), while the second component is a single integer.
The function value of the pair (x, y) is f((x, y)). However, it is customary to drop one set of parentheses and consider f(x, y) a function of two variables, x and y. Functions of two variables may be plotted on the three-dimensional Cartesian as ordered triples of the form (x, y, f(x, y)).
The concept can still further be extended by considering a function that also produces output that is expressed as several variables. For example, consider the integer divide function, with domain ℤ×ℕ and codomain ℤ×ℕ. The resultant (quotient, remainder) pair is a single value in the codomain seen as a Cartesian product.
The familiar binary operations of arithmetic, addition and multiplication, can be viewed as functions from ℝ×ℝ to ℝ. This view is generalized in abstract algebra, where n-ary functions are used to model the operations of arbitrary algebraic structures. For example, an abstract group is defined as a set X and a function f from X×X to X that satisfies certain properties.
Traditionally, addition and multiplication are written in the infix notation: x+y and x×y instead of +(x, y) and ×(x, y).
The idea of structure-preserving functions, or homomorphisms, led to the abstract notion of morphism, the key concept of category theory. In fact, functions f: X → Y are the morphisms in the category of sets, including the empty set: if the domain X is the empty set, then the subset of X × Y describing the function is necessarily empty, too. However, this is still a well-defined function. Such a function is called an empty function. In particular, the identity function of the empty set is defined, a requirement for sets to form a category.
The concept of categorification is an attempt to replace set-theoretic notions by category-theoretic ones. In particular, according to this idea, sets are replaced by categories, while functions between sets are replaced by functors.^{[14]}
Wikimedia Commons has media related to Functions. |