A function ƒ takes an input
x, and returns an output ƒ(
x). One metaphor describes the function as a "machine" or "
black box" that for each input returns a corresponding output.
The red curve is the graph of a function
f in the
Cartesian plane, consisting of all points with coordinates of the form (
x,
f(
x)). The property of having one output for each input is represented geometrically by the fact that each vertical line (such as the yellow line through the origin) has exactly one crossing point with the curve.
In mathematics, a function[1] is a relation between a set of inputs and a set of potential outputs with the property that each input is related to exactly one output. An example of such a relation is defined by the rule f(x) = x2, which relates an input x to its square, which are both real numbers. The output of the function f corresponding to an input x is denoted by f(x) (read "f of x"). If the input is –3, then the output is 9, and we may write f(–3) = 9.
The input to a function is often called the argument and the output is often called the value. Inputs and outputs need not be numbers – they can be elements of any set, for instance geometric figures. For example, a function could associate a triangle with the number 3, a square with the number 4, and so on.
There are many ways to describe or represent a function. Some functions may be described by a formula or algorithm that tells how to compute the output for a given input. Others are given by a picture, called the graph of the function. In science, many functions are given by a table that gives the outputs for selected inputs. A function can be described through its relationship with other functions, for example as an inverse function or as a solution of a differential equation. In analogy with arithmetic, it is possible to define addition, subtraction, multiplication, and division of functions. Another important operation defined on functions is function composition, where the output from one function becomes the input to another function.
The input and output are often expressed as an ordered pair. In the example above, we have the ordered pair <–3, 9>. This ordered pair can be viewed as the Cartesian coordinates of a point on the graph of the function. But no picture can exactly define every point in an infinite set. In modern mathematics, a function is defined by its set of inputs, called the domain, a set containing the outputs, called its codomain, and the set of all paired input and outputs, called the graph. For example, we could define a function using the rule f(x) = x2 by saying that the domain and codomain are the real numbers, and that the ordered pairs are all pairs of real numbers <x, x2>. 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 and complex analysis.
Functions are "the central objects of investigation" in most fields of modern mathematics. Because functions are so widely used, many traditions have grown up around their use. Informally, functions are often described as machines which take an input and change it into an output. The input is often represented by the letter x or, if the input is a particular time, by the letter t. The output is often represented by the letter y. The function itself is often called f. The notation y = f(x) indicates that a function named f has an input named x and an output named y.
If a function is often used, it may be given a special name as, for example, the signum function of a real number x, defined as follows:
- Failed to parse (Missing texvc executable; please see math/README to configure.): \sgn(x) = \begin{cases} -1 & \text{if } x < 0, \\ 0 & \text{if } x = 0, \\ 1 & \text{if } x > 0. \end{cases}
The set of all permitted inputs to a given function is called the domain of the function. The set of all resulting outputs is called the image or range of the function. The image is often a subset of a set of permissable outputs, called the codomain of the function. Thus, for example, the function f(x) = x2 could take as its domain the set of all real numbers, as its image the set of all non-negative real numbers, and as its codomain the set of all real numbers. In that case, we would describe f as a real-valued function of a real variable. It is not enough to say "f is a function" without specifying the domain and the codomain, unless these are known from the context. A formula such as Failed to parse (Missing texvc executable; please see math/README to configure.): f(x)=\sqrt{x^2-5x+6}
is not a properly defined function on its own; however, it is standard to take the largest possible subset of R as the domain (in this case x ≤ 2 or x ≥ 3) and R as the codomain.
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) = x2 − 1.[4] Furthermore, a function does 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.
Intuitively, a function is a rule that assigns to each element x in a set X a unique element y in a set Y.[5][6] However, it is not quite accurate to speak of a function as being a rule.[7] One difficulty in defining a function in this way is that the terms "rule" and "assign" are not defined earlier, and therefore this definition, although intuitively appealing, is not logically precise;[8] or that defining function as a rule of assignment leads to going in circles.. Nevertheless, this informal definition is used extensively by many authors, especially in textbooks; the crucial point is that the inputs and outputs are paired up "somehow"[10][11].
A function can be described more formally as a collection of pairs of elements with the following property: if (a, b) and (a, c) are both in the collection, then b = c. Thus, the collection does not contain two different pairs with the same first element. If x is in the domain of f, then there must be a unique y, such that (x, y) is an ordered pair in f. This unique y is denoted by f(x).
This diagram represents a function with domain
Failed to parse (Missing texvc executable; please see math/README to configure.): \{ 1, 2, 3 \}
, codomain Failed to parse (Missing texvc executable; please see math/README to configure.): \{ A, B, C, D \}
and set of ordered pairs Failed to parse (Missing texvc executable; please see math/README to configure.): \{ (1,D), (2,C), (3,C) \}
. The image is Failed to parse (Missing texvc executable; please see math/README to configure.): \{C,D\} .
This does not represent a function since 2 is the first element in more than one ordered pair, in particular, (2, B) and (2, C) are both elements of the set of ordered pairs.
Given sets X and Y, a function from X to Y is a set of ordered pairs F of members of these sets such that for every x in X there is a unique y in Y for which the pair (x, y) is in F.[13]An example of a function from the reals to the reals is given by the set of ordered pairs (x, x2), where x is a real number. This squaring function from the reals to the reals is not considered the same as the function from the reals to the non-negative reals as they are two different types of entities.
The above definition of "a function from X to Y" is generally agreed on, 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) = x2 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 one definition a function is an ordered triple of sets, written (X, Y, F), where X is the domain, Y is the codomain, and F is a set of ordered pairs (x, y). In each of the ordered pairs, the first element x is from the domain, the second element y is from the codomain, and a necessary condition is that every element in the domain is the first element in exactly one ordered pair.
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.[15] [16] Concepts like surjective don't apply to such functions, a codomain must be explicitly specified.
Functions are commonly defined as a type of relation. A relation from X to Y is a set of ordered pairs (x, y) with Failed to parse (Missing texvc executable; please see math/README to configure.): x \in X
and Failed to parse (Missing texvc executable; please see math/README to configure.): y \in 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 an ordered pair defines a function as a type of relation.
The notation f: X → Y indicates that f is a function with domain X and codomain Y, and the function f is said to map or associate elements of X to elements of Y. The set of all y is known as the image of the function, and need not be the whole of the codomain. The term range usually refers to the image, but sometimes it refers to the codomain. A specific input in a function is called an argument of the function. For each argument value x, the corresponding unique y in the codomain is called the function value at x, output of ƒ for an argument x, or the image of x under ƒ. The image of x may be written as ƒ(x) or as y.
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 {{{1}}}
If the domain and codomain are both the set of real numbers, as is commonly the case, we say f is a real valued function of a real variable, and the study of such functions is called real variables. If the domain and codomain are both the set of complex numbers, then we say f is a complex valued function of a complex variable. The study of these functions is called complex variables. In most situations, the domain and codomain are understood from context, and only the relationship between the input and output is given, but if Failed to parse (Missing texvc executable; please see math/README to configure.): f(x) = \sqrt{x} , then in real variables the domain is limited to non-negative numbers, while in complex variables the domain is all complex numbers.
The domain X may be void, but if X = ∅ then F = ∅. The codomain Y may be also void, but if Y = ∅ then X = ∅ and F = ∅. Such void functions are not usual, but the theory assures their existence.
Formal description of a function typically involves the function's name, its domain, its codomain, and a rule of correspondence. Thus we frequently see a two-part notation, an example being
- Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{align} f\colon \mathbf{N} &\to \mathbf{R} \\ n &\mapsto \frac{n}{\pi} \end{align}
where the first part is read:
- "ƒ is a function from N to R" (one often writes informally "Let ƒ: X → Y" to mean "Let ƒ be a function from X to Y"), or
- "ƒ is a function on N into R", or
- "ƒ is an R-valued function of an N-valued variable",
and the second part is read:
- Failed to parse (Missing texvc executable; please see math/README to configure.): n \,
maps to Failed to parse (Missing texvc executable; please see math/README to configure.): \frac{n}{\pi}. \,\!
Here the function named "ƒ" has the natural numbers as domain, the real numbers as codomain, and maps n to itself divided by π. Less formally, this long form might be abbreviated
- Failed to parse (Missing texvc executable; please see math/README to configure.): f(n) = \frac{n}{\pi} , \,\!
where f(n) is read as "f as function of n" or "f of n". There is some loss of information: we no longer are explicitly given the domain N and codomain R.
It is common to omit the parentheses around the argument when there is little chance of confusion, thus: sin x; this is known as prefix notation. Writing the function after its argument, as in x ƒ , is known as postfix notation; for example, the factorial function is customarily written n!, even though its generalization, the gamma function, is written Γ(n). Parentheses are still used to resolve ambiguities and denote precedence, though in some formal settings the consistent use of either prefix or postfix notation eliminates the need for any parentheses.
To define a function, sometimes a dot notation is used in order to emphasize the functional nature of an expression without assigning a special symbol to the variable. For instance, Failed to parse (Missing texvc executable; please see math/README to configure.): \scriptstyle a(\cdot)^2
stands for the function Failed to parse (Missing texvc executable; please see math/README to configure.): \textstyle x\mapsto ax^2
, Failed to parse (Missing texvc executable; please see math/README to configure.): \scriptstyle \int_a^{\, \cdot} f(u)du
stands for the integral function Failed to parse (Missing texvc executable; please see math/README to configure.): \scriptstyle x\mapsto \int_a^x f(u)du
, and so on.
Three important kinds of functions are the injections (or one-to-one functions), which have the property that if ƒ(a) = ƒ(b) then a must equal b; the surjections (or onto functions), which have the property that for every y in the codomain there is an x in the domain such that ƒ(x) = y; and the bijections, which are both one-to-one and onto. This nomenclature was introduced by the Bourbaki group.
When the definition of a function by its graph only is used, since the codomain is not defined, the "surjection" must be accompanied with a statement about the set the function maps onto. For example, we might say ƒ maps onto the set of all real numbers.
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: ƒ(x, y) = x·y. This function can be defined formally as having domain Z×Z , the set of all integer pairs; codomain Z; and, for graph, the set of all pairs ((x,y), x·y). Note that 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 ƒ((x,y)). However, it is customary to drop one set of parentheses and consider ƒ(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 Z×N and codomain Z×N. The resultant (quotient, remainder) pair is a single value in the codomain seen as a Cartesian product.
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 CA×B and (CB)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 (ƒ 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 ƒ: Z → Z → Z = x ⟼ y ⟼ x·y.
The familiar binary operations of arithmetic, addition and multiplication, can be viewed as functions from R×R to R. 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 ƒ 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).
File:Function machine5.png
A composite function g(f(x)) can be visualized as the combination of two "machines". The first takes input x and outputs f(x). The second takes f(x) and outputs g(f(x)).
The function composition of two or more functions takes the output of one or more functions as the input of others. The functions ƒ: X → Y and g: Y → Z can be composed by first applying ƒ to an argument x to obtain y = ƒ(x) and then applying g to y to obtain z = g(y). The composite function formed in this way from general ƒ and g may be written
- Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{align} g\circ f\colon X &\to Z \\ x &\mapsto g(f(x)). \end{align}
This notation follows the form such that
- Failed to parse (Missing texvc executable; please see math/README to configure.): (g\circ f)(x) = g(f(x)).\
The function on the right acts first and the function on the left acts second, reversing English reading order. We remember the order by reading the notation as "g of ƒ". The order is important, because rarely do we get the same result both ways. For example, suppose ƒ(x) = x2 and g(x) = x+1. Then g(ƒ(x)) = x2+1, while ƒ(g(x)) = (x+1)2, which is x2+2x+1, a different function.
In a similar way, the function given above by the formula y = 5x−20x3+16x5 can be obtained by composing several functions, namely the addition, negation, and multiplication of real numbers.
An alternative to the colon notation, convenient when functions are being composed, writes the function name above the arrow. For example, if ƒ is followed by g, where g produces the complex number eix, we may write
- Failed to parse (Missing texvc executable; please see math/README to configure.): \mathbf{N} \xrightarrow{f} \mathbf{R} \xrightarrow{g} \mathbf{C} . \,\!
A more elaborate form of this is the commutative diagram.
The unique function over a set X that maps each element to itself is called the identity function for X, and typically denoted by idX. 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 ƒ is any function from X to Y, then
- Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{align} f \circ \mathrm{id}_X &= f , \\ \mathrm{id}_Y \circ f &= f . \end{align}
Informally, a restriction of a function ƒ is the result of trimming its domain.
More precisely, if ƒ is a function from a X to Y, and S is any subset of X, the restriction of ƒ to S is the function ƒ|S from S to Y such that ƒ|S(s) = ƒ(s) for all s in S.
If g is a restriction of ƒ, then it is said that ƒ 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.
If ƒ is a function from X to Y then an inverse function for ƒ, denoted by ƒ−1, is a function in the opposite direction, from Y to X, with the property that a round trip (a composition) returns each element to itself. Not every function has an inverse; those that do are called invertible. The inverse function exists if and only if ƒ is a bijection.
As a simple example, if ƒ converts a temperature in degrees Celsius C to degrees Fahrenheit F, the function converting degrees Fahrenheit to degrees Celsius would be a suitable ƒ−1.
- Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{align} f(C) &= \frac {9}{5} C + 32 \\ f^{-1}(F) &= \frac {5}{9} (F - 32) \end{align}
The notation for composition is similar to multiplication; in fact, sometimes it is denoted using juxtaposition, gƒ, without an intervening circle. With this analogy, identity functions are like the multiplicative identity, 1, and inverse functions are like reciprocals (hence the notation).
For functions that are injections or surjections, generalized inverse functions can be defined, called left and right inverses respectively. Left inverses map to the identity when composed to the left; right inverses when composed to the right.
The concept of the image can be extended from the image of a point to the image of a set. If A is any subset of the domain, then ƒ(A) is the subset of im ƒ consisting of all images of elements of A. We say the ƒ(A) is the image of A under f.
Use of ƒ(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 ƒ[A] for the set { ƒ(x): x ∈ A }.
Notice that the image of ƒ is the image ƒ(X) of its domain, and that the image of ƒ is a subset of its codomain.
The inverse image (or preimage, or more precisely, complete inverse image) of a subset B of the codomain Y under a function ƒ is the subset of the domain X defined by
- Failed to parse (Missing texvc executable; please see math/README to configure.): f^{-1}(B) = \{x \in X : f(x) \in B\}.
So, for example, the preimage of {4, 9} under the squaring function is the set {−3,−2,2,3}.
In general, the preimage of a singleton set (a set with exactly one element) may contain any number of elements. For example, if ƒ(x) = 7, then the preimage of {5} is the empty set but the preimage of {7} is the entire domain. Thus the preimage of an element in the codomain is a subset of the domain. The usual convention about the preimage of an element is that ƒ−1(b) means ƒ−1({b}), i.e
- Failed to parse (Missing texvc executable; please see math/README to configure.): f^{-1}(b) = \{x \in X : f(x) = b\}.
In the same way as for the image, some authors use square brackets to avoid confusion between the inverse image and the inverse function. Thus they would write ƒ−1[B] and ƒ−1[b] for the preimage of a set and a singleton.
The preimage of a singleton set is sometimes called a fiber. The term kernel can refer to a number of related concepts.
A function can be defined by any mathematical condition relating each argument to the corresponding output value. If the domain is finite, a function ƒ may be defined by simply tabulating all the arguments x and their corresponding function values ƒ(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 ƒ(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.
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.
Main article:
Function spaceThe set of all functions from a set X to a set Y is denoted by X → Y, by [X → Y], or by YX. 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 |YX| = |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.
Other examples are the multiplication sign X×Y used for the Cartesian product, where |X×Y| = |X|·|Y|; the factorial sign X!, used for the set of permutations where |X!| = |X|!; and the binomial coefficient sign Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{pmatrix} X\\ n\end{pmatrix} , used for the set of n-element subsets where Failed to parse (Missing texvc executable; please see math/README to configure.): \left| \begin{pmatrix} X \\ n \end{pmatrix} \right| = \begin{pmatrix} |X| \\ n \end{pmatrix}.
If ƒ: X → Y, it may reasonably be concluded that ƒ ∈ [X → Y].
Pointwise operations inherit properties from the corresponding operations on the codomain. For example if ƒ: X → R and g: X → R are functions with a common domain of X and common codomain of a ring R, then the sum function ƒ + g: X → R and the product function ƒ ⋅ g: X → R can be defined as follows:
- Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{align} (f+g)(x) &= f(x)+g(x) , \\ (f\cdot g)(x) &= f(x) \cdot g(x) . \end{align}
There are many other special classes of functions that are important to particular branches of mathematics, or particular applications. Here is a partial list:
- bijection, injection and surjection, or singularly:
- continuous
- differentiable, integrable
- linear, polynomial, rational
- algebraic, transcendental
- trigonometric
- fractal
- odd or even
- convex, monotonic, unimodal
- holomorphic, meromorphic, entire
- vector-valued
- computable
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, and so 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.
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.
The idea of structure-preserving functions, or homomorphisms, led to the abstract notion of morphism, the key concept of category theory. More recently, the concept of functor has been used as an analogue of a function in category theory.[17]
- Historically, some mathematicians can be regarded as having foreseen and come close to a modern formulation of the concept of function. Among them is Oresme (1323–1382) . . . In his theory, some general ideas about independent and dependent variable quantities seem to be present.
[19] Ponte further notes that "The emergence of a notion of function as an individualized mathematical entity can be traced to the beginnings of infinitesimal calculus".
As a mathematical term, "function" was coined by Gottfried Leibniz, in a 1673 letter, to describe a quantity related to a curve, such as a curve's slope at a specific point.[20][21] The functions Leibniz considered are today called differentiable functions. For this type of function, one can talk about limits and derivatives; both are measurements of the output or the change in the output as it depends on the input or the change in the input. Such functions are the basis of calculus.
Johann Bernoulli "by 1718, had come to regard a function as any expression made up of a variable and some constants", and Leonhard Euler during the mid-18th century used the word to describe an expression or formula involving variables and constants e.g., x2+3x+2.
Alexis Claude Clairaut (in approximately 1734) and Euler introduced the familiar notation " f(x) ".
At first, the idea of a function was rather limited. Joseph Fourier, for example, claimed that every function had a Fourier series, something no mathematician would claim today. By broadening the definition of functions, mathematicians were 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 have shown that these functions are, in a precise sense, more common than differentiable functions. Such functions have since been applied to the modeling 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).
Dirichlet and Lobachevsky are traditionally credited with independently giving the modern "formal" definition of a function as a relation in which every first element has a unique second element. Eves asserts that "the student of mathematics usually meets the Dirichlet definition of function in his introductory course in calculus,[24] but Dirichlet's claim to this formalization is disputed by Imre Lakatos:
- There is no such definition in Dirichlet's works at all. But there is ample evidence that he had no idea of this concept. In his [1837], for instance, when he discusses piecewise continuous functions, he says that at points of discontinuity the function has two values: ...[25]
However, Gardiner [26] says "...it seems to me that Lakatos goes too far, for example, when he asserts that 'there is ample evidence that[Dirichlet] had no idea of [the modern function] concept'". Also G. Lejeune Dirichlet's Werke (in German) published by the American Mathematical Society does appear to include a definition along the lines of what is usually ascribed to Dirichlet even though it is concentrated on continuous geometric functions.
Because Dirichlet is credited with being the first to introduce the notion of arbitrary correspondence, his contribution is often recognized by the education community many of whom refer to a variant of the Bourbaki definition of 1939 as the "Dirichlet-Bourbaki" definition.
In the context of "the Differential Calculus" George Boole defined (circa 1849) the notion of a function as follows:
- "That quantity whose variation is uniform . . . is called the independent variable. That quantity whose variation is referred to the variation of the former is said to be a function of it. The Differential calculus enables us in every case to pass from the function to the limit. This it does by a certain Operation. But in the very Idea of an Operation is . . . the idea of an inverse operation. To effect that inverse operation in the present instance is the business of the Int[egral] Calculus."[27]
Logicians of this time were primarily involved with analyzing syllogisms (the 2000 year-old Aristotelian forms and otherwise), or as Augustus De Morgan (1847) stated it: "the examination of that part of reasoning which depends upon the manner in which inferences are formed, and the investigation of general maxims and rules for constructing arguments". At this time the notion of (logical) "function" is not explicit, but at least in the work of De Morgan and George Boole it is implied: we see abstraction of the argument forms, the introduction of variables, the introduction of a symbolic algebra with respect to these variables, and some of the notions of set theory.
De Morgan's 1847 "FORMAL LOGIC OR, The Calculus of Inference, Necessary and Probable" observes that "[a] logical truth depends upon the structure of the statement, and not upon the particular matters spoken of"; he wastes no time (preface page i) abstracting: "In the form of the proposition, the copula is made as abstract as the terms". He immediately (p. 1) casts what he calls "the proposition" (present-day propositional function or relation) into a form such as "X is Y", where the symbols X, "is", and Y represent, respectively, the subject, copula, and predicate. While the word "function" does not appear, the notion of "abstraction" is there, "variables" are there, the notion of inclusion in his symbolism “all of the Δ is in the О” (p. 9) is there, and lastly a new symbolism for logical analysis of the notion of "relation" (he uses the word with respect to this example " X)Y " (p. 75) ) is there:
- " A1 X)Y To take an X it is necessary to take a Y" [or To be an X it is necessary to be a Y]
- " A1 Y)X To take an Y it is sufficient to take a X" [or To be a Y it is sufficient to be an X], etc.
In his 1848 The Nature of Logic Boole asserts that "logic . . . is in a more especial sense the science of reasoning by signs", and he briefly discusses the notions of "belonging to" and "class": "An individual may possess a great variety of attributes and thus belonging to a great variety of different classes" .[29] Like De Morgan he uses the notion of "variable" drawn from analysis; he gives an example of "represent[ing] the class oxen by x and that of horses by y and the conjunction and by the sign + . . . we might represent the aggregate class oxen and horses by x + y".[30]
Eves observes "that logicians have endeavored to push down further the starting level of the definitional development of mathematics and to derive the theory of sets, or classes, from a foundation in the logic of propositions and propositional functions". But by the late 19th century the logicians' research into the foundations of mathematics was undergoing a major split. The direction of the first group, the Logicists, can probably be summed up best by Bertrand Russell 1903 – "to fulfil two objects, first, to show that all mathematics follows from symbolic logic, and secondly to discover, as far as possible, what are the principles of symbolic logic itself."
The second group of logicians, the set-theorists, emerged with Georg Cantor's "set theory" (1870–1890) but were driven forward partly as a result of Russell's discovery of a paradox that could be derived from Frege's conception of "function", but also as a reaction against Russell's proposed solution.[32] Zermelo's set-theoretic response was his 1908 Investigations in the foundations of set theory I – the first axiomatic set theory; here too the notion of "propositional function" plays a role.
[edit] George Boole's The Laws of Thought 1854; John Venn's Symbolic Logic 1881
In his An Investigation into the laws of thought Boole now defined a function in terms of a symbol x as follows:
- "8. Definition. – Any algebraic expression involving symbol x is termed a function of x, and may be represented by the abbreviated form f(x)"
Boole then used algebraic expressions to define both algebraic and logical notions, e.g., 1−x is logical NOT(x), xy is the logical AND(x,y), x + y is the logical OR(x, y), x(x+y) is xx+xy, and "the special law" xx = x2 = x.[34]
In his 1881 Symbolic Logic Venn was using the words "logical function" and the contemporary symbolism ( x = f(y), y = f−1(x), cf page xxi) plus the circle-diagrams historically associated with Venn to describe "class relations",[35] the notions "'quantifying' our predicate", "propositions in respect of their extension", "the relation of inclusion and exclusion of two classes to one another", and "propositional function" (all on p. 10), the bar over a variable to indicate not-x (page 43), etc. Indeed he equated unequivocally the notion of "logical function" with "class" [modern "set"]: "... on the view adopted in this book, f(x) never stands for anything but a logical class. It may be a compound class aggregated of many simple classes; it may be a class indicated by certain inverse logical operations, it may be composed of two groups of classes equal to one another, or what is the same thing, their difference declared equal to zero, that is, a logical equation. But however composed or derived, f(x) with us will never be anything else than a general expression for such logical classes of things as may fairly find a place in ordinary Logic".
[edit] Frege's Begriffsschrift 1879
Gottlob Frege's Begriffsschrift (1879) preceded Giuseppe Peano (1889), but Peano had no knowledge of Frege 1879 until after he had published his 1889.[37] Both writers strongly influenced Russell (1903). Russell in turn influenced much of 20th-century mathematics and logic through his Principia Mathematica (1913) jointly authored with Alfred North Whitehead.
At the outset Frege abandons the traditional "concepts subject and predicate", replacing them with argument and function respectively, which he believes "will stand the test of time. It is easy to see how regarding a content as a function of an argument leads to the formation of concepts. Furthermore, the demonstration of the connection between the meanings of the words if, and, not, or, there is, some, all, and so forth, deserves attention".[38]
Frege begins his discussion of "function" with an example: Begin with the expression[39] "Hydrogen is lighter than carbon dioxide". Now remove the sign for hydrogen (i.e., the word "hydrogen") and replace it with the sign for oxygen (i.e., the word "oxygen"); this makes a second statement. Do this again (using either statement) and substitute the sign for nitrogen (i.e., the word "nitrogen") and note that "This changes the meaning in such a way that "oxygen" or "nitrogen" enters into the relations in which "hydrogen" stood before".[40] There are three statements:
- "Hydrogen is lighter than carbon dioxide."
- "Oxygen is lighter than carbon dioxide."
- "Nitrogen is lighter than carbon dioxide."
Now observe in all three a "stable component, representing the totality of [the] relations";[41] call this the function, i.e.,
- "... is lighter than carbon dioxide", is the function.
Frege calls the argument of the function "[t]he sign [e.g., hydrogen, oxygen, or nitrogen], regarded as replaceable by others that denotes the object standing in these relations".[42] He notes that we could have derived the function as "Hydrogen is lighter than . . .." as well, with an argument position on the right; the exact observation is made by Peano (see more below). Finally, Frege allows for the case of two (or more arguments). For example, remove "carbon dioxide" to yield the invariant part (the function) as:
- "... is lighter than ... "
The one-argument function Frege generalizes into the form Φ(A) where A is the argument and Φ( ) represents the function, whereas the two-argument function he symbolizes as Ψ(A, B) with A and B the arguments and Ψ( , ) the function and cautions that "in general Ψ(A, B) differs from Ψ(B, A)". Using his unique symbolism he translates for the reader the following symbolism:
- "We can read |--- Φ(A) as "A has the property Φ. |--- Ψ(A, B) can be translated by "B stands in the relation Ψ to A" or "B is a result of an application of the procedure Ψ to the object A".[43]
[edit] Peano 1889 The Principles of Arithmetic 1889
Peano defined the notion of "function" in a manner somewhat similar to Frege, but without the precision.[44] First Peano defines the sign "K means class, or aggregate of objects", the objects of which satisfy three simple equality-conditions, a = a, (a = b) = (b = a), IF ((a = b) AND (b = c)) THEN (a = c). He then introduces φ, "a sign or an aggregate of signs such that if x is an object of the class s, the expression φx denotes a new object". Peano adds two conditions on these new objects: First, that the three equality-conditions hold for the objects φx; secondly, that "if x and y are objects of class s and if x = y, we assume it is possible to deduce φx = φy".[47] Given all these conditions are met, φ is a "function presign". Likewise he identifies a "function postsign". For example if φ is the function presign a+, then φx yields a+x, or if φ is the function postsign +a then xφ yields x+a.
[edit] Bertrand Russell's The Principles of Mathematics 1903
While the influence of Cantor and Peano was paramount,[48] in Appendix A "The Logical and Arithmetical Doctrines of Frege" of The Principles of Mathematics, Russell arrives at a discussion of Frege's notion of function, "...a point in which Frege's work is very important, and requires careful examination". In response to his 1902 exchange of letters with Frege about the contradiction he discovered in Frege's Begriffsschrift Russell tacked this section on at the last moment.
For Russell the bedeviling notion is that of "variable": "6. Mathematical propositions are not only characterized by the fact that they assert implications, but also by the fact that they contain variables. The notion of the variable is one of the most difficult with which logic has to deal. For the present, I openly wish to make it plain that there are variables in all mathematical propositions, even where at first sight they might seem to be absent. . . . We shall find always, in all mathematical propositions, that the words any or some occur; and these words are the marks of a variable and a formal implication".
As expressed by Russell "the process of transforming constants in a proposition into variables leads to what is called generalization, and gives us, as it were, the formal essence of a proposition ... So long as any term in our proposition can be turned into a variable, our proposition can be generalized; and so long as this is possible, it is the business of mathematics to do it"; these generalizations Russell named propositional functions". Indeed he cites and quotes from Frege's Begriffsschrift and presents a vivid example from Frege's 1891 Function und Begriff: That "the essence of the arithmetical function 2x3 + x is what is left when the x is taken away, i.e., in the above instance 2( )3 + ( ). The argument x does not belong to the function but the two taken together make the whole". Russell agreed with Frege's notion of "function" in one sense: "He regards functions – and in this I agree with him – as more fundamental than predicates and relations" but Russell rejected Frege's "theory of subject and assertion", in particular "he thinks that, if a term a occurs in a proposition, the proposition can always be analysed into a and an assertion about a".
Russell would carry his ideas forward in his 1908 Mathematical logical as based on the theory of types and into his and Whitehead's 1910–1913 Principia Mathematica. By the time of Principia Mathematica Russell, like Frege, considered the propositional function fundamental: "Propositional functions are the fundamental kind from which the more usual kinds of function, such as “sin ‘’x’’ or log x or "the father of x" are derived. These derivative functions . . . are called “descriptive functions". The functions of propositions . . . are a particular case of propositional functions".[53]
Propositional functions: Because his terminology is different from the contemporary, the reader may be confused by Russell's "propositional function". An example may help. Russell writes a propositional function in its raw form, e.g., as φŷ: "ŷ is hurt". (Observe the circumflex or "hat" over the variable y). For our example, we will assign just 4 values to the variable ŷ: "Bob", "This bird", "Emily the rabbit", and "y". Substitution of one of these values for variable ŷ yields a proposition; this proposition is called a "value" of the propositional function. In our example there are four values of the propositional function, e.g., "Bob is hurt", "This bird is hurt", "Emily the rabbit is hurt" and "y is hurt." A proposition, if it is significant—i.e., if its truth is determinate—has a truth-value of truth or falsity. If a proposition's truth value is "truth" then the variable's value is said to satisfy the propositional function. Finally, per Russell's definition, "a class [set] is all objects satisfying some propositional function" (p. 23). Note the word "all'" – this is how the contemporary notions of "For all ∀" and "there exists at least one instance ∃" enter the treatment (p. 15).
To continue the example: Suppose (from outside the mathematics/logic) one determines that the propositions "Bob is hurt" has a truth value of "falsity", "This bird is hurt" has a truth value of "truth", "Emily the rabbit is hurt" has an indeterminate truth value because "Emily the rabbit" doesn't exist, and "y is hurt" is ambiguous as to its truth value because the argument y itself is ambiguous. While the two propositions "Bob is hurt" and "This bird is hurt" are significant (both have truth values), only the value "This bird" of the variable ŷ satisfies' the propositional function φŷ: "ŷ is hurt". When one goes to form the class α: φŷ: "ŷ is hurt", only "This bird" is included, given the four values "Bob", "This bird", "Emily the rabbit" and "y" for variable ŷ and their respective truth-values: falsity, truth, indeterminate, ambiguous.
Russell defines functions of propositions with arguments, and truth-functions f(p).[54] For example, suppose one were to form the "function of propositions with arguments" p1: "NOT(p) AND q" and assign its variables the values of p: "Bob is hurt" and q: "This bird is hurt". (We are restricted to the logical linkages NOT, AND, OR and IMPLIES, and we can only assign "significant" propositions to the variables p and q). Then the "function of propositions with arguments" is p1: NOT("Bob is hurt") AND "This bird is hurt". To determine the truth value of this "function of propositions with arguments" we submit it to a "truth function", e.g., f(p1): f( NOT("Bob is hurt") AND "This bird is hurt" ), which yields a truth value of "truth".
The notion of a "many-one" functional relation": Russell first discusses the notion of "identity", then defines a descriptive function (pages 30ff) as the unique value ιx that satisfies the (2-variable) propositional function (i.e., "relation") φŷ.
- N.B. The reader should be warned here that the order of the variables are reversed! y is the independent variable and x is the dependent variable, e.g., x = sin(y).[55]
Russell symbolizes the descriptive function as "the object standing in relation to y": R'y =DEF (ιx)(x R y). Russell repeats that "R'y is a function of y, but not a propositional function [sic]; we shall call it a descriptive function. All the ordinary functions of mathematics are of this kind. Thus in our notation "sin y" would be written " sin 'y ", and "sin" would stand for the relation sin 'y has to y".[56]
Hardy 1908, pp. 26–28 defined a function as a relation between two variables x and y such that "to some values of x at any rate correspond values of y." He neither required the function to be defined for all values of x nor to associate each value of x to a single value of y. This broad definition of a function encompasses more relations than are ordinarily considered functions in contemporary mathematics.
David Hilbert set himself the goal of "formalizing" classical mathematics "as a formal axiomatic theory, and this theory shall be proved to be consistent, i.e., free from contradiction" . In Hilbert 1927 The Foundations of Mathematics he frames the notion of function in terms of the existence of an "object":
- 13. A(a) --> A(ε(A)) Here ε(A) stands for an object of which the proposition A(a) certainly holds if it holds of any object at all; let us call ε the logical ε-function".[58] [The arrow indicates “implies”.]
Hilbert then illustrates the three ways how the ε-function is to be used, firstly as the "for all" and "there exists" notions, secondly to represent the "object of which [a proposition] holds", and lastly how to cast it into the choice function.
Recursion theory and computability: But the unexpected outcome of Hilbert's and his student Bernays's effort was failure; see Gödel's incompleteness theorems of 1931. At about the same time, in an effort to solve Hilbert's Entscheidungsproblem, mathematicians set about to define what was meant by an "effectively calculable function" (Alonzo Church 1936), i.e., "effective method" or "algorithm", that is, an explicit, step-by-step procedure that would succeed in computing a function. Various models for algorithms appeared, in rapid succession, including Church's lambda calculus (1936), Stephen Kleene's μ-recursive functions(1936) and Alan Turing's (1936–7) notion of replacing human "computers" with utterly-mechanical "computing machines" (see Turing machines). It was shown that all of these models could compute the same class of computable functions. Church's thesis holds that this class of functions exhausts all the number-theoretic functions that can be calculated by an algorithm. The outcomes of these efforts were vivid demonstrations that, in Turing's words, "there can be no general process for determining whether a given formula U of the functional calculus K [Principia Mathematica] is provable";[59] see more at Independence (mathematical logic) and Computability theory.
Set theory began with the work of the logicians with the notion of "class" (modern "set") for example De Morgan (1847), Jevons (1880), Venn (1881), Frege (1879) and Peano (1889). It was given a push by Georg Cantor's attempt to define the infinite in set-theoretic treatment (1870–1890) and a subsequent discovery of an antinomy (contradiction, paradox) in this treatment (Cantor's paradox), by Russell's discovery (1902) of an antinomy in Frege's 1879 (Russell's paradox), by the discovery of more antinomies in the early 20th century (e.g., the 1897 Burali-Forti paradox and the 1905 Richard paradox), and by resistance to Russell's complex treatment of logic and dislike of his axiom of reducibility[61] (1908, 1910–1913) that he proposed as a means to evade the antinomies.
In 1902 Russell sent a letter to Frege pointing out that Frege's 1879 Begriffsschrift allowed a function to be an argument of itself: "On the other hand, it may also be that the argument is determinate and the function indeterminate . . .."[62] From this unconstrained situation Russell was able to form a paradox:
- "You state ... that a function, too, can act as the indeterminate element. This I formerly believed, but now this view seems doubtful to me because of the following contradiction. Let w be the predicate: to be a predicate that cannot be predicated of itself. Can w be predicated of itself?"[63]
Frege responded promptly that "Your discovery of the contradiction caused me the greatest surprise and, I would almost say, consternation, since it has shaken the basis on which I intended to build arithmetic".[64]
From this point forward development of the foundations of mathematics became an exercise in how to dodge "Russell's paradox", framed as it was in "the bare [set-theoretic] notions of set and element".[65]
The notion of "function" appears as Zermelo's axiom III—the Axiom of Separation (Axiom der Aussonderung). This axiom constrains us to use a propositional function Φ(x) to "separate" a subset MΦ from a previously formed set M:
- "AXIOM III. (Axiom of separation). Whenever the propositional function Φ(x) is definite for all elements of a set M, M possesses a subset MΦ containing as elements precisely those elements x of M for which Φ(x) is true".[66]
As there is no universal set—sets originate by way of Axiom II from elements of (non-set) domain B – "...this disposes of the Russell antinomy so far as we are concerned".[67] But Zermelo's "definite criterion" is imprecise, and is fixed by Weyl, Fraenkel, Skolem, and von Neumann.[68]
In fact Skolem in his 1922 referred to this "definite criterion" or "property" as a "definite proposition":
- "... a finite expression constructed from elementary propositions of the form a ε b or a = b by means of the five operations [logical conjunction, disjunction, negation, universal quantification, and existential quantification].[69]
van Heijenoort summarizes:
- "A property is definite in Skolem's sense if it is expressed . . . by a well-formed formula in the simple predicate calculus of first order in which the sole predicate constants are ε and possibly, =. ... Today an axiomatization of set theory is usually embedded in a logical calculus, and it is Weyl's and Skolem's approach to the formulation of the axiom of separation that is generally adopted.[70]
In this quote the reader may observe a shift in terminology: nowhere is mentioned the notion of "propositional function", but rather one sees the words "formula", "predicate calculus", "predicate", and "logical calculus." This shift in terminology is discussed more in the section that covers "function" in contemporary set theory.
The history of the notion of "ordered pair" is not clear. As noted above, Frege (1879) proposed an intuitive ordering in his definition of a two-argument function Ψ(A, B). Norbert Wiener in his 1914 (see below) observes that his own treatment essentially "revert(s) to Schröder's treatment of a relation as a class of ordered couples".[71] Russell (1903) considered the definition of a relation (such as Ψ(A, B)) as a "class of couples" but rejected it:
- "There is a temptation to regard a relation as definable in extension as a class of couples. This is the formal advantage that it avoids the necessity for the primitive proposition asserting that every couple has a relation holding between no other pairs of terms. But it is necessary to give sense to the couple, to distinguish the referent [domain] from the relatum [converse domain]: thus a couple becomes essentially distinct from a class of two terms, and must itself be introduced as a primitive idea. . . . It seems therefore more correct to take an intensional view of relations, and to identify them rather with class-concepts than with classes."
By 1910–1913 and Principia Mathematica Russell had given up on the requirement for an intensional definition of a relation, stating that "mathematics is always concerned with extensions rather than intensions" and "Relations, like classes, are to be taken in extension".[73] To demonstrate the notion of a relation in extension Russell now embraced the notion of ordered couple: "We may regard a relation ... as a class of couples ... the relation determined by φ(x, y) is the class of couples (x, y) for which φ(x, y) is true". In a footnote he clarified his notion and arrived at this definition:
- "Such a couple has a sense, i.e., the couple (x, y) is different from the couple (y, x) unless x = y. We shall call it a "couple with sense," ... it may also be called an ordered couple.
But he goes on to say that he would not introduce the ordered couples further into his "symbolic treatment"; he proposes his "matrix" and his unpopular axiom of reducibility in their place.
An attempt to solve the problem of the antinomies led Russell to propose his "doctrine of types" in an appendix B of his 1903 The Principles of Mathematics. In a few years he would refine this notion and propose in his 1908 The Theory of Types two axioms of reducibility, the purpose of which were to reduce (single-variable) propositional functions and (dual-variable) relations to a "lower" form (and ultimately into a completely extensional form); he and Alfred North Whitehead would carry this treatment over to Principia Mathematica 1910–1913 with a further refinement called "a matrix".[76] The first axiom is *12.1; the second is *12.11. To quote Wiener the second axiom *12.11 "is involved only in the theory of relations".[77] Both axioms, however, were met with skepticism and resistance; see more at Axiom of reducibility. By 1914 Norbert Wiener, using Whitehead and Russell's symbolism, eliminated axiom *12.11 (the "two-variable" (relational) version of the axiom of reducibility) by expressing a relation as an ordered pair "using the null set. At approximately the same time, Hausdorff (1914, p. 32) gave the definition of the ordered pair (a, b) as { {a,1}, {b, 2} }. A few years later Kuratowski (1921) offered a definition that has been widely used ever since, namely { {a, b}, {a} }".[78] As noted by Suppes (1960) "This definition . . . was historically important in reducing the theory of relations to the theory of sets.[79]
Observe that while Wiener "reduced" the relational *12.11 form of the axiom of reducibility he did not reduce nor otherwise change the propositional-function form *12.1; indeed he declared this "essential to the treatment of identity, descriptions, classes and relations".[80]
Where exactly the general notion of "function" as a many-one correspondence derives from is unclear. Russell in his 1920 Introduction to Mathematical Philosophy states that "It should be observed that all mathematical functions result form one-many [sic – contemporary usage is many-one] relations . . . Functions in this sense are descriptive functions". A reasonable possibility is the Principia Mathematica notion of "descriptive function" – R 'y =DEF (ιx)(x R y): "the singular object that has a relation R to y". Whatever the case, by 1924, Moses Schonfinkel expressed the notion, claiming it to be "well known":
- "As is well known, by function we mean in the simplest case a correspondence between the elements of some domain of quantities, the argument domain, and those of a domain of function values ... such that to each argument value there corresponds at most one function value".[82]
According to Willard Quine, Schönfinkel 1924 "provide[s] for ... the whole sweep of abstract set theory. The crux of the matter is that Schönfinkel lets functions stand as arguments. For Schönfinkel, substantially as for Frege, classes are special sorts of functions. They are propositional functions, functions whose values are truth values. All functions, propositional and otherwise, are for Schönfinkel one-place functions".[83] Remarkably, Schönfinkel reduces all mathematics to an extremely compact functional calculus consisting of only three functions: Constancy, fusion (i.e., composition), and mutual exclusivity. Quine notes that Haskell Curry (1958) carried this work forward "under the head of combinatory logic".[84]
By 1925 Abraham Fraenkel (1922) and Thoralf Skolem (1922) had amended Zermelo's set theory of 1908. But von Neumann was not convinced that this axiomatization could not lead to the antinomies.[85] So he proposed his own theory, his 1925 An axiomatization of set theory[86]. It explicitly contains a "contemporary", set-theoretic version of the notion of "function":
- "[Unlike Zermelo's set theory] [w]e prefer, however, to axiomatize not "set" but "function". The latter notion certainly includes the former. (More precisely, the two notions are completely equivalent, since a function can be regarded as a set of pairs, and a set as a function that can take two values.)".[87]
At the outset he begins with I-objects and II-objects, two objects A and B that are I-objects (first axiom), and two types of "operations" that assume ordering as a structural property[88] obtained of the resulting objects [x, y] and (x, y). The two "domains of objects" are called "arguments" (I-objects) and "functions" (II-objects); where they overlap are the "argument functions" (he calls them I-II objects). He introduces two "universal two-variable operations" – (i) the operation [x, y]: ". . . read 'the value of the function x for the argument y . . . it itself is a type I object", and (ii) the operation (x, y): ". . . (read 'the ordered pair x, y') whose variables x and y must both be arguments and that itself produces an argument (x, y). Its most important property is that x1 = x2 and y1 = y2 follow from (x1 = y2) = (x2 = y2)". To clarify the function pair he notes that "Instead of f(x) we write [f,x] to indicate that f, just like x, is to be regarded as a variable in this procedure". To avoid the "antinomies of naive set theory, in Russell's first of all . . . we must forgo treating certain functions as arguments".[89] He adopts a notion from Zermelo to restrict these "certain functions"[90].
Suppes[91] observes that von Neumann's axiomatization was modified by Bernays "in order to remain nearer to the original Zermelo system . . . He introduced two membership relations: one between sets, and one between sets and classes". Then Gödel [1940][92] further modified the theory: "his primitive notions are those of set, class and membership (although membership alone is sufficient)".[93]. This axiomatization is now known as von Neumann-Bernays-Gödel set theory.
In 1939, Bourbaki, in addition to giving the well-known ordered pair definition of a function as a certain subset of the cartesian product E x F, gave the following:
"Let E and F be two sets, which may or may not be distinct. A relation between a variable element x of E and a variable element y of F is called a functional relation in y if, for all x ∈ E, there exists a unique y ∈ F which is in the given relation with x. "We give the name of function to the operation which in this way associates with every element x ∈ E the element y ∈ F which is in the given relation with x, and the function is said to be determined by the given functional relation. Two equivalent functional relations determine the same function."
Both axiomatic and naive forms of Zermelo's set theory as modified by Fraenkel (1922) and Skolem (1922) define "function" as a relation, define a relation as a set of ordered pairs, and define an ordered pair as a set of two "dissymetric" sets.
While the reader of Suppes (1960) Axiomatic Set Theory or Halmos (1970) Naive Set Theory observes the use of function-symbolism in the axiom of separation, e.g., φ(x) (in Suppes) and S(x) (in Halmos), they will see no mention of "proposition" or even "first order predicate calculus". In their place are "expressions of the object language", "atomic formulae", "primitive formulae", and "atomic sentences".
Kleene (1952) defines the words as follows: "In word languages, a proposition is expressed by a sentence. Then a 'predicate' is expressed by an incomplete sentence or sentence skeleton containing an open place. For example, "___ is a man" expresses a predicate ... The predicate is a propositional function of one variable. Predicates are often called 'properties' ... The predicate calculus will treat of the logic of predicates in this general sense of 'predicate', i.e., as propositional function".
In 1970, Bourbaki, in Chapter II of Elements of mathematics(theory of sets), gave the modern definition of function as a triple f = (F, A, B)[95]
The reason for the disappearance of the words "propositional function" e.g., in Suppes (1960), and Halmos (1970), is explained by Tarski (1946) together with further explanation of the terminology:
- "An expression such as x is an integer, which contains variables and, on replacement of these variables by constants becomes a sentence, is called a SENTENTIAL [i.e., propositional cf his index] FUNCTION. But mathematicians, by the way, are not very fond of this expression, because they use the term "function" with a different meaning. ... sentential functions and sentences composed entirely of mathematical symbols (and not words of everyday languange), such as: x + y = 5 are usually referred to by mathematicians as FORMULAE. In place of "sentential function" we shall sometimes simply say "sentence" – but only in cases where there is no danger of any misunderstanding".
For his part Tarski calls the relational form of function a "FUNCTIONAL RELATION or simply a FUNCTION". After a discussion of this "functional relation" he asserts that:
- "The concept of a function which we are considering now differs essentially from the concepts of a sentential [propositional] and of a designatory function .... Strictly speaking ... [these] do not belong to the domain of logic or mathematics; they denote certain categories of expressions which serve to compose logical and mathematical statements, but they do not denote things treated of in those statements... . The term "function" in its new sense, on the other hand, is an expression of a purely logical character; it designates a certain type of things dealt with in logic and mathematics."
See more about "truth under an interpretation" at Alfred Tarski.
- ^ "The words map or mapping, transformation, correspondence, and operator are among some of the many that are sometimes used as synonyms for function Halmos 1970, p. 30.
- ^ Hartley Rogers, Jr (1987). Theory of Recursive Functions and Effective Computation. MIT. pp. 1–2. ISBN 0-262-68052-1.
- ^ Strang, Gilbert (1991). Calculus (1992 ed.). Wellesley-Cambridge. p. 5. ISBN 0-9614088-2-0. http://books.google.com/books?id=OisInC1zvEMC.
- ^ Binmore, K. G.; Davies, Joan (2001). Calculus. Cambridge University. p. 51. ISBN 0-521-77541-8. http://books.google.com/books?id=sZOTrsHARlEC.
- ^ Suppes 1960, p. 86, "Even today many textbooks of the differential and integral calculus do not give a mathematically satisfactory definition of functions."
- ^ Joshi, K. D. (1983). Introduction to general topology. New Age International. p. 32. ISBN 0-85226-444-5. http://books.google.com/books?id=fvCpXrube5wC.
- ^ George B. Thomas, Jr (1960). Calculus and Analytic Geometry 3rd Edition. Addison-Wesley. pp. 21–22.
- ^ Maxwell Rosenlicht (1968). Introduction to Analysis. Courier Dover Publications. p. 8.
- ^ Hamilton, A. G.. Numbers, sets, and axioms: the apparatus of mathematics. Cambridge University Press. p. 83. ISBN 0-521-24509-5. http://books.google.com/books?id=OXfmTHXvRXMC&pg=PA83&dq=%22function+is+a+relation%22.
- ^ Apostle, Tom (1967). Calculus vol 1. John Wiley. p. 53. ISBN 0-471-00005-1.
- ^ Heins, Maurice. Complex function theory. p. 4. http://books.google.com/books?id=OtyBXTOTwZoC&pg=PA4&dq=%22function+is+a+relation%22.
- ^ John C. Baez; James Dolan (1998). Categorification. arXiv:math/9802029.
- ^ Another short but useful history is found in Eves 1990, pp. 234–235
- ^ Thompson, S.P; Gardner, M; Calculus Made Easy. 1998. Pages 10–11. ISBN 0-312-18548-0.
- ^ Eves dates Leibniz's first use to the year 1694 and also similarly relates the usage to "as a term to denote any quantity connected with a curve, such as the coordinates of a point on the curve, the slope of the curve, and so on" (Eves 1990, p. 234).
- ^ Eves asserts that Dirichlet "arrived at the following formulation: "[The notion of] a variable is a symbol that represents any one of a set of numbers; if two variables x and y are so related that whenever a value is assigned to x there is automatically assigned, by some rule or correspondence, a value to y, then we say y is a (single-valued) function of x. The variable x . . . is called the independent variable and the variable y is called the dependent variable. The permissible values that x may assume constitute the domain of definition of the function, and the values taken on by y constitute the range of values of the function . . . it stresses the basic idea of a relationship between two sets of numbers" Eves 1990, p. 235.
- ^ Lakatos, Imre (1976). Worrall, John; Zahar, Elie. eds. Proofs and Refutations. Cambridge: Cambridge University Press. p. 151. ISBN 0-521-29038-4. http://books.google.com/books?id=1n6SFdXCOBQC. Published postumously.
- ^ Gardiner, A.. Understanding infinity,the mathematics of infinite processes. Courier Dover Publications. p. 275. ISBN 0-486-42538-X. http://books.google.es/books?id=NiDCYJ8vrGQC&pg=PA275&lpg=PA275&dq=dirichlet+lakatos+arbitrary+have+not+checked&source=bl&ots=1Tn6NPwu42&sig=woChOYaXCoomirwrqW1VVWyRxE8&hl=en&sa=X&ei=sTp4T9zyAoHL0QWwsoW4DQ&redir_esc=y.
- ^ Boole circa 1849 Elementary Treatise on Logic not mathematical including philosophy of mathematical reasoning in Grattan-Guinness & Bornet 1997, p. 40
- ^ Boole 1848 in Grattan-Guinness & Bornet 1997, pp. 1, 2
- ^ Boole 1848 in Grattan-Guinness & Bornet 1997, p. 6
- ^ Some of this criticism is intense: see the introduction by Willard Quine preceding Russell 1908a Mathematical logic as based on the theory of types in van Heijenoort 1967, p. 151. See also in von Neumann 1925 the introduction to his Axiomatization of Set Theory in van Heijenoort 1967, p. 395
- ^ cf Boole 1854, pp. 31–34. Boole discusses this "special law" with its two algebraic roots x = 0 or 1, on page 37.
- ^ Although he gives others credit, cf Venn 1881, p. 6
- ^ cf van Heijenoort's introduction to Peano 1889 in van Heijenoort 1967. For most of his logical symbolism and notions of propositions Peano credits "many writers, especially Boole". In footnote 1 he credits Boole 1847, 1848, 1854, Schröder 1877, Peirce 1880, Jevons 1883, MacColl 1877, 1878, 1878a, 1880; cf van Heijenoort 1967, p. 86).
- ^ Frege 1879 in van Heijenoort 1967, p. 7
- ^ Frege's exact words are "expressed in our formula language" and "expression", cf Frege 1879 in van Heijenoort 1967, pp. 21–22.
- ^ This example is from Frege 1879 in van Heijenoort 1967, pp. 21–22
- ^ Frege 1879 in van Heijenoort 1967, pp. 21–22
- ^ Frege cautions that the function will have "argument places" where the argument should be placed as distinct from other places where the same sign might appear. But he does not go deeper into how to signify these positions and Russell 1903 observes this.
- ^ Frege 1879 in van Heijenoort 1967, pp. 21–24
- ^ "...Peano intends to cover much more ground than Frege does in his Begriffsschrift and his subsequent works, but he does not till that ground to any depth comparable to what Frege does in his self-allotted field", van Heijenoort 1967, p. 85
- ^ All symbols used here are from Peano 1889 in van Heijenoort 1967, p. 91).
- ^ "In Mathematics, my chief obligations, as is indeed evident, are to Georg Cantor and Professor Peano. If I had become acquainted sooner with the work of Professor Frege, I should have owed a great deal to him, but as it is I arrived independently at many results which he had already established", Russell 1903, p. viii. He also highlights Boole's 1854 Laws of Thought and Ernst Schröder's three volumes of "non-Peanesque methods" 1890, 1891, and 1895 cf Russell 1903, p. 10
- ^ Russell 1910–1913:15
- ^ Whitehead and Russell 1910–1913:6, 8 respectively
- ^ Something similar appears in Tarski 1946. Tarski refers to a "relational function" as a "ONE-MANY [sic!] or FUNCTIONAL RELATION or simply a FUNCTION". Tarski comments about this reversal of variables on page 99.
- ^ Whitehead and Russell 1910–1913:31. This paper is important enough that van Heijenoort reprinted it as Whitehead & Russell 1910 Incomplete symbols: Descriptions with commentary by W. V. Quine in van Heijenoort 1967, pp. 216–223
- ^ Hilbert in van Heijenoort 1967, p. 466
- ^ Turing 1936–7 in Davis, Martin (1965). The undecidable: basic papers on undecidable propositions, unsolvable problems and computable functions. Courier Dover Publications. p. 145. ISBN 978-0-486-43228-1. http://books.google.com/books?id=qW8x7sQ4JXgC.
- ^ "The nonprimitive and arbitrary character of this axiom drew forth severe criticism, and much of subsequent refinement of the logistic program lies in attempts to devise some method of avoiding the disliked axiom of reducibility" Eves 1990, p. 268.
- ^ Frege 1879 in van Heijenoort 1967, p. 23
- ^ Russell (1902) Letter to Frege in van Heijenoort 1967, p. 124
- ^ Frege (1902) Letter to Russell in van Heijenoort 1967, p. 127
- ^ van Heijenoort's commentary to Russell's Letter to Frege in van Heijenoort 1967, p. 124
- ^ The original uses an Old High German symbol in place of Φ cf Zermelo 1908a in van Heijenoort 1967, p. 202
- ^ Zermelo 1908a in van Heijenoort 1967, p. 203
- ^ cf van Heijenoort's commentary before Zermelo 1908 Investigations in the foundations of set theory I in van Heijenoort 1967, p. 199
- ^ Skolem 1922 in van Heijenoort 1967, pp. 292–293
- ^ van Heijenoort's introduction to Abraham Fraenkel's The notion "definite" and the independence of the axiom of choice in van Heijenoort 1967, p. 285.
- ^ But Wiener offers no date or reference cf Wiener 1914 in van Heijenoort 1967, p. 226
- ^ both quotes from Whitehead & Russell 1913, p. 26
- ^ "*12 The Hierarchy of Types and the axiom of Reducibility". Principia Mathematica. 1913. p. 161. http://books.google.com/books?id=rdMgDpNSdLsC.
- ^ Wiener 1914 in van Heijenoort 1967, p. 224
- ^ commentary by van Heijenoort preceding Wiener 1914 A simplification of the logic of relations in van Heijenoort 1967, p. 224.
- ^ Suppes 1960, p. 32. This same point appears in van Heijenoort's commentary before Wiener (1914) in van Heijenoort 1967, p. 224.
- ^ Wiener 1914 in van Heijeoort 1967, p. 224
- ^ Schönfinkel (1924) On the building blocks of mathematical logic in van Heijenoort 1967, p. 359
- ^ commentary by W. V. Quine preceding Schönfinkel (1924) On the building blocks of mathematical logic in van Heijenoort 1967, p. 356.
- ^ cf Curry and Feys 1958; Quine in van Heijenoort 1967, p. 357.
- ^ von Neumann's critique of the history observes the split between the logicists (e.g., Russell et. al.) and the set-theorists (e.g., Zermelo et. al.) and the formalists (e.g., Hilbert), cf von Neumann 1925 in van Heijenoort 1967, pp. 394–396.
- ^ In addition to the 1925 appearance in van Heijenoort, Suppes 1970:12 cites two more: 1928a and 1929.
- ^ von Neumann 1925 in van Heijenoort 1967, p. 396
- ^ In his 1930-1931 The Philosophy of Mathematics and Hilbert's Proof Theory Bernays asserts (in the context of rebutting Logicism's construction of the numbers from logical axioms) that "the Number concept turns out to be an elementary structural concept". This paper appears on page 243 in Paolo Mancosu 1998 From Brouwer to Hilbert, Oxford University Press, NY, ISBN 0-19-509632-0.
- ^ All quotes from von Neumann 1925 in van Heijenoort 1967, pp. 396–398
- ^ This notion is not easy to summarize; see more at van Heijenoort 1967, p. 397.
- ^ See also van Heijenoort's introduction to von Neumann's paper on pages 393-394.
- ^ cf in particular p. 35 where Gödel declares his primitive notions to be class, set, and "the diadic relation ε between class and class, class and set, set and class, or set and set". Gödel 1940 The consistency of the axiom of choice and of the generalized continuum hypothesis with the axioms of set theory appearing on pages 33ff in Volume II of Kurt Godel Collected Works, Oxford University Press, NY, ISBN 0-19-514721-9 (v.2, pbk).
- ^ All quotes from Suppes 1960, p. 12 footnote. He also references "a paper by R. M. Robinson [1937] [that] provides a simplified system close to von Neumann's original one".
- ^ N.Bourbaki (1970). Elements de Mathematique,Theorie des Ensembles. Diffusion C.C.L.S. p. 13. ISBN [[Special:BookSources/29036840030|29036840030]].
- Bloch, Ethan D. (2011). Proofs and Fundamentals: A First Course in Abstract Mathematics. Springer. ISBN 978-1-4419-7126-5. http://books.google.com/books?id=QJ_537n8zKYC.
- Boole, George (1854). An Investigation into the Laws of Thought on which are founded the Laws of Thought and Probabilities. Walton and Marberly. http://books.google.com/books?id=SWgLVT0otY8C.
- De Morgan, Augustus (1847). Formal Logic, or The Calculus of Inference, Necessary and Probable. Walton and Marberly. http://books.google.com/books?id=HscAAAAAMAAJ.
- Eves, Howard (1990). Foundations and Fundamental Concepts of Mathematics (3rd ed.). Dover. ISBN 0-486-69609-X. http://books.google.com/books?id=-UzKwHWzdesC.
- Grattan-Guinness, Ivor; Bornet, Gérard (1997). George Boole: Selected Manuscripts on Logic and its Philosophy. Springer-Verlag. ISBN 3-7643-5456-9. http://books.google.com/books?id=pzg7UFsIVJIC.
- Halmos, Paul R. (1970). Naive Set Theory. Springer-Verlag. ISBN 0-387-90092-6. http://books.google.com/books?id=x6cZBQ9qtgoC.
- Hardy, Godfrey Harold (1908). A Course of Pure Mathematics. Cambridge University Press (published 1993). ISBN 978-0-521-09227-2. http://books.google.com/books?id=tnrcG2p9rUsC.
- Kleene, Stephen Cole (1952). Introduction to Metamathematics. North-Holland (published 1971). ISBN 978-0-7204-2103-3.
- Ponte, João Pedro (1992). The history of the concept of function and some educational implications. 3. pp. 3–8. http://www.math.tarleton.edu/Faculty/Brawner/550%20MAED/History%20of%20functions.pdf.
- Russell, Bertrand (1903). The Principles of Mathematics: Vol. 1. Cambridge University Press.
- Russell, Bertrand (1920). Introduction to Mathematical Philosophy (2nd ed.). Dover. ISBN 0-486-27724-0.
- Spivak, Michael (2008). Calculus (4th ed.). Publish or Perish. ISBN 978-0-914098-91-1. http://books.google.com/books?id=7JKVu_9InRUC.
- Suppes, Patrick (1960). Axiomatic Set Theory (1972 ed.). Dover. ISBN 0-486-61630-4. http://books.google.com/books?id=sxr4LrgJGeAC. cf. his Chapter 1 Introduction.
- Tarski, Alfred (1946). Introduction to Logic and to the Methodology of Deductive Sciences (1995 ed.). Courier Dover. ISBN 0-486-28462-X. http://books.google.com/books?id=XoWTzdbZgeYC.
- Venn, John (1881). Symbolic Logic. Macmillian. http://books.google.com/books?id=nisCAAAAQAA.
- van Heijenoort, Jean (1967). From Frege to Godel: A Source Book in Mathematical Logic, 1879–1931 (3rd printing 1976 ed.). Harvard University Press. ISBN 0-674-32449-8. http://books.google.com/books?id=v4tBTBlU05sC.
; Frege, Gottlob (1967) [1879]. "Frege (1879) Begriffsschrift, a formula language, modeled upon that of arithmetic, for pure thought". pp. 1–82. With commentary by van Heijenoort. ; Peano, Giuseppe (1967) [1889]. "Peano (1889) The principles of arithmetic, presented by a new method". pp. 83–97. With commentary by van Heijenoort. ; Russell, Bertrand (1967) [1902]. "Russell (1902) Letter to Frege". pp. 124–125. With commentary by van Heijenoort. Wherein Russell announces his discovery of a "paradox" in Frege's work. ; Frege, Gottlob (1967) [1902]. "Frege (1902) Letter to Russell". pp. 126–128. With commentary by van Heijenoort. ; Hilbert, David (1967) [1904]. "Hilbert (1904) On the foundations of logic and arithmetic". pp. 129–138. With commentary by van Heijenoort. ; Richard, Jules (1967) [1905]. "Richard (1905) The principles of mathematics and the problem of sets". pp. 142–144. With commentary by van Heijenoort. The Richard paradox. ; Russell, Bertrand (1967) [1908a]. "Russell (1908a) Mathematical logic as based on the theory of types". pp. 150–182. With commentary by Willard Quine. ; Zermelo, Ernst (1967) [1908]. "Zermelo (1908) A new proof of the possibility of a well-ordering". pp. 183–198. With commentary by van Heijenoort. Wherein Zermelo rails against Poincaré's (and therefore Russell's) notion of impredicative definition. ; Zermelo, Ernst (1967) [1908a]. "Zermelo (1908a) Investigations in the foundations of set theory I". pp. 199–215. With commentary by van Heijenoort. Wherein Zermelo attempts to solve Russell's paradox by structuring his axioms to restrict the universal domain B (from which objects and sets are pulled by definite properties) so that it itself cannot be a set, i.e., his axioms disallow a universal set. ; Whitehead, Alfred North; Russell, Bertrand (1967) [1910]. "Whitehead and Russell (1910) Incomplete symbols: Descriptions". pp. 216–223. With commentary by W. V. Quine. ; Wiener, Norbert (1967) [1914]. "Wiener (1914) A simplification of the logic of relations". pp. 224–227. With commentary by van Heijenoort. ; Skolem, Thoralf (1967) [1922]. "Skolem (1922) Some remarks on axiomatized set theory". pp. 290–301. With commentary by van Heijenoort. Wherein Skolem defines Zermelo's vague "definite property". ; Schönfinkel, Moses (1967) [1924]. "Schönfinkel (1924) On the building blocks of mathematical logic". pp. 355–366. With commentary by Willard Quine. The start of combinatory logic. ; von Neumann, John (1967) [1925]. "von Neumann (1925) An axiomatization of set theory". pp. 393–413. With commentary by van Heijenoort. Wherein von Neumann creates "classes" as distinct from "sets" (the "classes" are Zermelo's "definite properties"), and now there is a universal set, etc. ; Hilbert, David (1967) [1927]. "Hilbert(1927) The foundations of mathematics". pp. 464–479. With commentary by van Heijenoort.
- Whitehead, Alfred North; Russell, Bertrand (1913). Principia Mathematica to *56 (1962 ed.). Cambridge University Press. ISBN 978-0-521-62606-4. http://books.google.com/books?id=rdMgDpNSdLsC.
- Anton, Howard (1980). Calculus with Analytical Geometry. Wiley. ISBN 978-0-471-03248-9.
- Bartle, Robert G. (1976). The Elements of Real Analysis (2nd ed.). Wiley. ISBN 978-0-471-05464-1.
- Dubinsky, Ed; Harel, Guershon (1992). The Concept of Function: Aspects of Epistemology and Pedagogy. Mathematical Association of America. ISBN 0-88385-081-8.
- Frege, Gottlob (1879). Begriffsschrift: eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle.
- Husch, Lawrence S. (2001). Visual Calculus. University of Tennessee. http://archives.math.utk.edu/visual.calculus/. Retrieved 2007-09-27.
- Katz, Robert (1964). Axiomatic Analysis. D. C. Heath and Company. .
- Kleiner, Israel (1989). Evolution of the Function Concept: A Brief Survey. 20. Mathematical Association of America. pp. 282–300. DOI:10.2307/268684 8. JSTOR 2686848. .
- Lützen, Jesper (2003). "Between rigor and applications: Developments in the concept of function in mathematical analysis". In Roy Porter, ed. The Cambridge History of Science: The modern physical and mathematical sciences. Cambridge University Press. ISBN 0521571995. http://books.google.com/books?id=B3WvWhJTTX8C&pg=PA468. An approachable and diverting historical presentation.
- Malik, M. A. (1980). Historical and pedagogical aspects of the definition of function. 11. pp. 489–492. DOI:10.1080/0020739800110404.
- Monna, A. F. (1972). The concept of function in the 19th and 20th centuries, in particular with regard to the discussions between Baire, Borel and Lebesgue. 9. pp. 57–84. DOI:10.1007/BF00348540.
- Reichenbach, Hans (1947) Elements of Symbolic Logic, Dover Publishing Inc., New York NY, ISBN 0-486-24004-5.
- Ruthing, D. (1984). Some definitions of the concept of function from Bernoulli, Joh. to Bourbaki, N.. 6. pp. 72–77.
- Thomas, George B.; Finney, Ross L. (1995). Calculus and Analytic Geometry (9th ed.). Addison-Wesley. ISBN 978-0-201-53174-9.
- Youschkevitch, A. P. (1976). The concept of function up to the middle of the 19th century. 16. pp. 37–85. DOI:10.1007/BF00348305.
|
|
|
|
Overview
|
|
Academic
areas |
|
|
Foundational
concepts |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
