Function (mathematics)

The terms function, mapping, map, transformation and operator are usually used synonymously.

Table of contents

1 Intuitive introduction 2 History 3 Formal definition 4 Domains, codomains, and ranges 5 Injective, surjective and bijective functions 6 Images and preimages 7 Graph of a function 8 Examples of functions 9 n-ary function: function of several variables 10 Composing functions 10.1 Inverse function 10.2 Restrictions and extensions 11 Pointwise operations 12 Computable and non-computable functions 13 Functions from the categorical viewpoint 14 References 15 External links

Intuitive introduction

Intuitively, a function is a "rule" that assigns a unique output to each given input. Here are some examples of functions:

• Each person has a favorite colour (red, orange, yellow, green, cyan, blue, indigo, or violet). The colour is a function of the person. For example, John has favorite colour red, while Kim has favorite colour violet. Here, the input is the person, and the output is one of the 8 colours.
• Some children are selling lemonade in the summer. The number of lemonades they sell is a function of the temperature outside. For example, if it is 85 degrees outside, they sell 10 lemonades, but if it is 95 degrees outside, they sell 25 lemonades. Here, the input is the temperature, and the output is the number of lemonades they sell.
• A stone is dropped from different stories of a tall building. The time it takes the stone to reach the ground is a function of the storey. For example, the stone takes 2 seconds to fall from the second storey, but only 4 seconds to fall from the 10th storey. Here, the input is the storey, and the output is the number of seconds.

A very common type of function occurs when the argument and the function value are both numbers, the functional relationship is expressed by a formula, and the value of the function is obtained by direct substitution of the argument into the formula. Consider for example

A straightforward generalization is to allow functions depending on several arguments. For instance,

In the sciences, we often encounter functions that are not given by (known) formulas. Consider for instance the temperature distribution on earth over time: this is a function which takes location and time as arguments and gives as output the temperature at that location at that time.

We have seen that the intuitive notion of function is not limited to computations using single numbers and not even limited to computations; the mathematical notion of function is still more general and is not limited to situations involving numbers. Rather, a function links a "domain" (set of inputs) to a "codomain" (set of possible outputs) in such a way that every element of the domain is associated to precisely one element of the codomain. Functions are abstractly defined as certain relations, as will be seen below. Because of this generality, the function concept is fundamental to virtually every branch of mathematics.

History

As a mathematical term, "function" was coined by Leibniz in 1694, to describe a quantity related to a curve, such as a curve's slope or a specific point of a curve. The functions Leibniz considered are today called differentiable functions, and they are the type of function most frequently encountered by nonmathematicians. For this type of function, one can talk about limitss and derivatives; both are measurements of the change of output values associated to a change of input values, and these measurements are the basis of calculus.

The word function was later used by Euler during the mid-18th century to describe an expression or formula involving various argumentss, e.g. f(x) = sin(x) + x³.

During the 19th century, mathematicians started to formalize all the different branches of mathematics. Weierstrass advocated building calculus on arithmetic rather than on geometry, which favoured Euler's definition over Leibniz's (see arithmetization of analysis).

By broadening the definition of functions, mathematicians were then able to study "strange" mathematical objects such as continuous functions that are nowhere differentiable. These functions were first thought to be only theoretical curiosities, and they were collectively called "monsters" as late as the turn of the 20th century. However, powerful techniques from functional analysis has shown that these functions are actually more common than differentiable functions. Such functions have since been applied to the modelling of physical phenomena such as Brownian motion.

Towards the end of the 19th century, mathematicians started trying to formalize all of mathematics using set theory, and they sought to define every mathematical object as a set. It was Dirichlet that gave the modern "formal" definition of function (see #Formal Definition below).

In Dirichlet's definition, a function is a special case of a relation. In most cases of practical interest, however, the differences between the modern definition and Euler's definition are negligible.

Formal definition

Formally, a function f from a set X of input values to a set Y of possible output values (written as f : X → Y) is a relation between X and Y which satisfies:

1. f is total: for all x in X, there exists a y in Y such that x f y (x is f-related to y), i.e. for each input value, there is at least one output value in Y.
2. f is many-to-one: if x f y and x f z, then y = z. i.e., many input values can be related to one output value, but one input value cannot be related to many output values.

A more concise expression of the above definition is the following: a function from X to Y is a subset f of the cartesian product X × Y, such that for each x in X, there is a unique y in Y such that the ordered pair (x, y) is in f.

The set of all functions f : X → Y is denoted by Y^X. Note that |Y^X| = |Y|^|X| (refer to Cardinal numbers).

A relation between X and Y that satisfies condition (1) is a multivalued function. Every function is a multivalued function, but not every multivalued function is a function. A relation between X and Y that satisfies condition (2) is a partial function. Every function is a partial function, but not every partial function is a function. In this encyclopedia, the term "function" will mean a relation satisfying both conditions (1) and (2), unless otherwise stated.

Consider the following three examples:

	This relation is total but not many-to-one; the element 3 in X is related to two elements b and c in Y. Therefore, this is a multivalued function, but not a function.
	This relation is many-to-one but not total; the element 1 in X is not related to any element of Y. Therefore, this is a partial function, but not a function.
	This relation is both total and many-to-one, and so it is a function from X to Y. The function can be given explicitly as f = {(1, a), (2, d), (3, c)} or as

Domains, codomains, and ranges

X, the set of input values, is called the domain of f, and Y, the set of possible output values, is called the codomain. The range of f is the set of all actual outputs {f(x) : x in the domain}. Beware that sometimes the codomain is incorrectly called the range because of a failure to distinguish between possible and actual values. An endofunction is a function whose domain and range are identical.

In computer science, the datatypes of the arguments and return values specify the domain and codomain (respectively) of a subprogram. So the domain and codomain are constraints imposed initially on a function; on the other hand the range has to do with how things turn out in practice.

Injective, surjective and bijective functions

Several types of functions are very useful, deserve special names:

• Injective (one-to-one) functions send different arguments to different values; in other words, if x and y are members of the domain of f, then f(x) = f(y) only if x = y.
• Surjective (onto) functions have their range equal to their codomain; in other words, if y is any member of the codomain of f, then there exists at least one x such that f(x) = y.
• Bijective functions are both injective and surjective; they are often used to show that the sets X and Y are the "same size" in some sense.

The image of an element x∈X under f is the output f(x).

The image of a subset A⊂X under f is the subset of Y defined by

f(A) := {f(x) : x in A}.

Note that with this definiton, the direct image f becomes a function whose domain is the set of all subsets of X (also known as the power set of X) and whose codomain is the power set of Y. Note that the same notation is used for the original function f and its direct image. This is a common convention; the intended usage must be inferred by context.

The preimage (or inverse image) of a set B ⊂ Y under f is the subset of X defined by

f ⁻¹(B) := {x in X : f(x)∈B}.

Note that with this definiton, f ⁻¹ becomes a function whose domain is the power set of Y and whose codomain is the power set of X'.

Some consequences that follow immediately from these definitions are:

• f(A₁ ∪ A₂) = f(A₁) ∪ f(A₂).
• f(A₁ ∩ A₂) ⊆ f(A₁) ∩ f(A₂).
• f ⁻¹(B₁ ∪ B₂) = f ⁻¹(B₁) ∪ f ⁻¹(B₂).
• f ⁻¹(B₁ ∩ B₂) = f ⁻¹(B₁) ∩ f ⁻¹(B₂).
• f(f ⁻¹(B)) ⊆ B.
• f ⁻¹(f(A)) ⊇ A.

Graph of a function

The graph of a function f is the set of all ordered pairs(x, f(x)), for all x in the domain X. There are theorems formulated or proved most easily in terms of the graph, such as the closed graph theorem.

If X and Y are real lines, then this definition coincides with the familiar sense of graph. Below is the graph of a cubic function:

This function is surjective but not injective.

Note that since a relation on the two sets X and Y is usually formalized as a subset of X×Y, the formal definition of function actually identifies the function f with its graph.

Examples of functions

(More can be found at List of functions.)

• The relation wght between persons in the United States and their weights at a particular time.
• The relation between nations and their capitals, if we exclude those nations that maintain multiple capitals [1].
• The relation sqr between natural numbers n and their squares n².
• The relation ln between positive real numbers x and their natural logarithms ln(x). Note that the relation between real numbers and their natural logarithms is not a function because not every real number has a natural logarithm; that is, this relation is not total.
• The relation dist between points in the plane R² and their distances from the origin (0,0).
• The relation grav between a point in the punctured plane R² \\ {(0,0)} and the vector describing the gravitational force that a certain mass at that point would experience from a certain other mass at the origin (0,0).

n-ary function: function of several variables

Functions in applications are often functions of several variables: the values they take depend on a number of different factors. From a mathematical point of view all the variables must be made explicit in order to have a functional relationship - no 'hidden' factors are allowed. Then again, from the mathematical point of view, there is no qualitative difference between functions of one and of several variables. A function of three real variables is just a function that applies to triples of real numbers. The following paragraph says this in more formal language.

If the domain of a function is a subset of the Cartesian product of n sets then the function is called an n-ary function. For example, the relation dist has the domain R × R and is therefore a binary function. In that case dist((x,y)) is simply written as dist(x,y).

Another name applied to some types of functions of several variables is operation. In abstract algebra, operators such as "*" are defined as binary functions; when we write a formula such as x*y in this context, we are implicitly invoking the function *(x,y), but writing it in a convenient infix notation.

An important theoretical paradigm, functional programming, takes the function concept as central. In that setting, the handling of functions of several variables becomes an operational matter, for which the lambda calculus provides the basic syntax. The composition of functions (see under composing functions immediately below) becomes a question of explicit forms of substitution, as used in the substitution rule of calculus. In particular, a formalism called currying can be used to reduce n-ary functions to functions of a single variable.

Composing functions

The functions f: X → Y and g: Y → Z can be composed by first applying f to an argument x and then applying g to the result. Thus one obtains a function g o f: X → Z defined by (g o f)(x) := g(f(x)) for all x in X. As an example, suppose that an airplane's height at time t is given by the function h(t) and that the oxygen concentration at height x is given by the function c(x). Then (c o h)(t) describes the oxygen concentration around the plane at time t.

In the mid-20th century, some mathematicians decided that writing "gof" to mean "first apply f, then apply g" was too confusing and decided to change notations. They wrote "xf" for "f(x)" and "xfg" for "g(f(x))". However, this movement never caught on, and nowadays this notation is found only in old books.

The functions g and f are commutative if g o f=f o g. If Y⊂X then f may compose with itself; this is sometimes denoted f ². (Do not confuse it with the notation commonly seen in trigonometry.) The functional powers f of ⁿ = f ⁿ o f = f ⁿ⁺¹ for natural n follow immediately. This is a generalized version of the common f^-1 for an inverse function. On their heels comes the idea of functional root; given f and n, find a g such that gⁿ=f. (Richard Feynman illustrated practical use of functional roots in one of his anecdotal books. <which?> Tasked with building an analogue arctan computer and finding its parts overstressed, he instead designed a machine for a functional root <fifth?> of arctan and chained enough copies to make the arctan machine.)

Inverse function