Function

The word "function" refers to basic concepts in several disciplines:

   * In sociology, social functions are the basis of functionalism.
   * In computer science, a function is a subprogram or subroutine. See also
     functional programming.
   * This page focuses on mathematical functions (see below).

Introduction

The concept of function is a generalization of the common notion of a
"mathematical formula". Functions describe special mathematical
relationships between two objects, x and y=f(x). The object x is called the
argument of the function f, and y is said to "depend functionally" on x.

Intuitively, a function is a way to assign to each value of the argument x a
unique value of the function f(x). This could be specified by a formula, a
relationship, and/or a rule. This concept is deterministic, always producing
the same result from the same input (the generalization to random values is
called a stochastic process). A function may be thought of as a "machine" or
"black box" converting valid input into a unique output.

The most familiar kind of function is that where the argument and the
function's value are both numbers, and the functional relationship is
expressed by a formula, and the value of the function is obtained from the
arguments by direct substitution. Consider for example

     f(x) = x2

which assigns to any number x its square.

A straightforward generalization is to allow functions depending not on a
single number, but on several. For instance,

     g(x,y) = xy

which takes two numbers x and y and assigns to them their product, xy.

According to how a function is specified, it is said to be an explicit
function (as above) or an implicit function, as in

     xf(x) = 1

which implicitly specifies the function

     f(x) = 1 / x

See also How to specify a function.

We have seen that the intuitive notion of function is not limited to
computations using single numbers, but the mathematical notion of function
is not limited to computations, or even to situations involving numbers at
all. Because of this generality, functions appear in a wide variety of
mathematical contexts, and several mathematical fields are based on the
study of functions.

It should be noted that the words "function", "mapping", "map" and
"transformation" are usually used synonymously. Furthermore, functions may
occasionally referred to as well-defined function or total function (See the
section "Formal Definition" below).

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 said curve. Functions related to curves are nowaday called
differentiable functions and are still the most frequently type of functions
encounted by non-mathematicians. For such kind of functions, one can talk
about limits and derivatives; both are measurements of the change of output
values associated to a change of input values, and they are the basics of
calculus.

The word function was later used by Euler during the mid-18th Century to
describe an expression involving various arguments; ie: y = F(x). By
broadening the definition of functions, mathematicians were then able to
study "strange" mathematical objects such as functions which are nowhere
differentiable. Those functions, first thought as purely imaginary and
called collectively "monsters" as late as the turn of the 20th century, were
later found to be important in the modelling of physical phenomena such as
Brownian motion.

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). Towards the end of the
century, mathematicians started trying to formalize all of mathematics using
set theory and they sought definitions of every mathematical object as a
set. It was Dirichlet that gave the modern "formal" definition of function.

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

Formal Definition

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

  1. f is functional: if x f y (x is f-related to y) and x f z, then y = z.
     i.e., for each input value, there should only be one possible output
     value.
  2. f is total: for all x in X, there exists a y in Y such that x f y. i.e.
     for each input value, the formula should produce at least one output
     value within Y.

For each input value x in the domain, the corresponding unique output value
y in the codomain is denoted by f(x).

Consider the following three examples:

 [NotMap1.png]This is not a "well-defined" function; because, the element 3, in X, is associated with two elements b and c in Y
              (Condition 1 is violated). This is a multivalued function.

 [NotMap2.png]This is not a "well-defined" function; because, the element 1, in XÊ, is associated with nothing (Condition 2 is
              violated). This is a partial function.
              This is a function, called a discrete function (or rarely piecewise function); of which the range is {a,c,d}. It can
              be stated explicitly as
 [Mathmap.png]
                   [f(x)=\left\{\begin{matrix} a, & \mbox{if }x=1 \\ d, & \mbox{if }x=2 \\ c, & \mbox{if }x=3. \end{matrix}\right.]

Occasionally, all three relations above are called functions. In this case,
the function satisfies Conditions (1) and (2) is said to be a "well-defined
function" or "total function". In this encyclopedia, the terms "well-defined
function", "total function" and "function" are synonymous.

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 wrongly called the range because of a failure to distinguish
between possible and actual values.

In computer science, specifying the datatypes of the arguments and return
values sets 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.

Graph of a functions

The graph of a function f is the collection of all points(x, f(x)), for all
x in set X. In the example of the discrete function, the graph of f is
{(1,a),(2,d),(3,c)}. 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.

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.

Images and preimages

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

The image (or direct image) of A⊂X under f is the subset of Y defined by

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


Notice that the range of f is the image f(X) of its domain. In our example
of discrete function, the image of {2,3} under f is f({2,3})={c,d} and the
range of f is {a,c,d}.

The preimage of y∈Y is the set f−1(y)={x∈X : f(x)=y}. If the
set is a singleton {x}, then we simply say that x=f−1(y) is the
preimage of y.

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

     fÊ−1(B)Ê:= {x in XÊ: f(x)∈B}.

In our example of discrete function, the preimage of {a,b} is
fÊ−1({a,b})={1}.

Note that with this definiton, fÊ-1 becomes a function whose domain is the
set of all subsets of Y (also known as the power set of Y) and whose
codomain is the power set of X.

Some consequences that follow immediately from these definitions are:

   * f(A1Ê∪ÊA2)Ê= f(A1)Ê∪Êf(A2).
   * f(A1Ê∩ÊA2)Ê⊆ f(A1)Ê∩Êf(A2).
   * fÊ−1(B1Ê∪ÊB2)Ê= fÊ−1(B1)Ê∪ÊfÊ−1(B2).
   * fÊ−1(B1Ê∩ÊB2)Ê= fÊ−1(B1)Ê∩ÊfÊ−1(B2).
   * f(fÊ−1(B))Ê⊆ÊB.
   * fÊ−1(f(A))Ê⊇ÊA.

The results relating images and preimages to the algebra of intersection and
union work for any number of sets, not just for 2.

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) if and only if x = y. Our example is an injective function.
   * 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" in some sense.

Examples of functions

(More can be found at List of functions.)

   * The relation wght between persons in the United States and their
     weights.
   * The relation between nations and their capitals.
   * The relation sqr between natural numbers n and their squares n2.
   * The relation nlog 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 and is
     therefore only a partial function.
   * The relation dist between points in the plane R2 and their distances
     from the origin (0,0).
   * The relation grav between a point in the punctured plane R2Ê\ {(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).

Most commonly used types of mathematical functions involving addition,
division, exponents, logarithms, multiplication, polynomials, radicals,
rationals, subtraction, and trigonometric expressions. They are sometimes
collectively referred as Elementary functions -- but the meaning of this
term varies among different branches of mathematics. Example of
non-elementary functions are Bessel functions and gamma functions.

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.

If [Y\sub 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\circ f^n=f^n\circ f=f^{n+1}] for
natural n follow immediately. On their heels comes the idea of functional
root; given f and n, find a g such that gn=f. (Feynman illustrated practical
use of functional roots in one of his anecdotal books.  Tasked with
building an analogue arctan computer and finding its parts overstressed, he
instead designed a machine for a functional root  of arctan and
chained enough copies to make the arctan machine.)

Inverse function

If a function f:X→Y is bijective then preimages of any element y in the
codomain Y is a singleton. A function taking y∈Y to its preimage
f−1(y) is a well-defined function called the inverse of f and is
denoted by f−1.

An example of an inverse function, for f(x) = x2, is f(x)−1 =
√x. Likewise, the inverse of 2x is x/2. The inverse function is the
function that "undoes" its original.

Pointwise operations

If f:ÊXÊ→ÊR and g:ÊXÊ→ÊR are functions with common domain X and
codomain is a ring R, then one can define the sum function fÊ+Êg: XÊ→ÊR
and the product function fÊ×Êg: XÊ→ÊR as follows:

     (fÊ+Êg)(x)Ê:= f(x)Ê+Êg(x);
     (fÊ×Êg)(x)Ê:= f(x)Ê×Êg(x);

for all x in X.

This turns the set of all such functions into a ring. The binary operations
in that ring have as domain ordered pairs of functions, and as codomain
functions. This is an example of climbing up in abstraction, to functions of
more complex types.

By taking some other algebraic structure A in the place of R, we can turn
the set of all functions from X to A into an algebraic structure of the same
type in an analogous way.

Enumeration

The number of computable functions (aka calculable functions) from integers
to integers is countable and its size is the transfinite number aleph-null,
which is written [\aleph_0]. The number of all functions from integers to
integers is higher: the same as the cardinality of the real numbers. This
counting argument shows that there are functions from integers to integers
that are not computable. For examples of noncomputable functions, see the
articles on the halting problem and Rice's theorem.