Function (set theory)
From Wikipedia, the free encyclopedia
A function is determined by two collections A and B and an assignment of a unique element of B to each element of A.
We say this at more length, but still informally. Let A and B be two collections. A function f from A to B is determined by a method of associating with each element x of A a uniquely determined element of B, which is denoted by f(x). The set A is called the domain of the function. The set B is called the codomain of the function. The subset of B consisting of the actual values of f is called the range of the function.
The notion of function is usually defined more concretely in terms of set theory. A function from A to B (where A and B are sets) is a kind of binary relation with domain A and codomain B. A binary relation R with domain A and codomain B is a function from A to B if and only if each element x of A is related by R to exactly one element of B.
This is complicated by the fact that there are two separate definitions of binary relation. A binary relation R with domain A and codomain B may be understood to be a set of ordered pairs such that each ordered pair in the set has first component in A and second component in B.
If this definition of relation is used, then a function from A to B is equivalently defined as a set of ordered pairs with the property that the first component of each ordered pair in the set is in A, the second component is in B, and each element of A occurs as the first component of exactly one element of the set.
The difficulty which some have with this definition of binary relation (and the corresponding definition of function) is that one cannot determine the domain or codomain of a relation (or the codomain of a function) from examining the set of ordered pairs. In the case of a function, the domain can be identified as the set of all first components of elements of the function, but the codomain can be taken to be any superset of the set of all second components of elements of the function.
This leads to the alternative definition of a binary relation as an ordered triple (A, B,f) such that f is a set of ordered pairs such that each first component of an element of f belongs to A and each second component belongs to B. Such a triple is then a function from A to B if and only if each element of A occurs exactly once as the first component of an element of f.
Let f be a function from A to B and let x be an element of A. If we use the first definition of function, we define f(x) as the unique element y of B such that the pair (x, y) belongs to f. If we use the second definition, then the function f has the form (A, B,F), and we can define f(x) as the unique element of B such that the pair (x, y) belongs to F.
When working with either definition, we define the graph of f as the set 
. Under the first definition, the graph is the function itself; under the second definition, the graph is the third component of the ordered triple which implements the function.
Once the notation f(x) is defined, the exact way in which the function is defined is usually immaterial, as long as one does not need to identify the codomain of the function.
It is sometimes useful to consider functions which are proper classes. In this case one would need to either use the first definition of function or use a definition of ordered pair which allows one to construct the ordered triple of proper classes needed for the second definition in this case (suitable alternative definitions of ordered pair are described in that article).
Contents |
[edit] Formal notation for functions
If x is a variable understood to belong to A and T is a term (usually containing occurrences of x) whose referent will belong to B if the referent of x belongs to A, then the function which sends each x in A to the corresponding value of the term T can be written 
or (λx.T). Since this notation does not explicitly indicate the codomain (the domain could be fixed in notations 
or 
) it seems more appropriate for use with the first definition of function.
For example, 
would be the function which squares a natural number argument.
These notations are not universally used.
[edit] Special kinds of function
- A function f is an injection from A to B if and only if f(x) = f(y) implies x = y for all x, y in A. An injection is also called a one-to-one function.
- A function f is a surjection from A to B if and only if for every y in B there is an x in A such that y = f(x). A surjection is also called an onto function.
- A function f is a bijection from A to B if and only if it is an injection from A to B and a surjection from A to B.
If the second definition of function is used, we can identify a function as an injection, surjection or bijection without the explicit reference to the intended domain and codomain, because the domain and codomain are components of the function itself. If the first definition is used, injections can be recognized unambiguously, but we cannot tell if a function is a surjection (or bijection) unless the context supplies the intended codomain.
[edit] Operations on functions
The identity function from A to A is defined as the unique function idA from A to A such that idA(x) = x for each x in A.
If f is a bijection from A to B, we define f--1 as the unique function h from B to A satisfying h(f(x)) = x for each element x of A. This function is also called the inverse of the bijection f. Only bijections have inverses.
If f is a function from A to B, and g is a function from B to C, we define the function 
as the unique function h from A to C such that h(x) = g(f(x)) for each x in A. This function is called the composition of g and f. It might seem more natural to denote this by fg (since f is applied first, then g) but the traditional practice of writing the function before its argument causes us to write the terms of the composition in the given order. If f is a function whose domain and codomain are the same, it is common to define fn for each natural number n recursively: f0 is the identity function, and fn + 1 is defined as 
. If f is a bijection as well, then f − n can be defined as (f − 1)n.
If f is a function from X to Y, and A is a subset of X, we define the image of the set A under the function f, or f[A] (sometimes written ambiguously as f(A) and less often as f``A) as 
. (One sometimes calls the value f(x) the image of x under A as well). Further, we define the restriction of f to A, or 
, as the function from A to Y whose graph is the intersection of 
with the graph of f. If B is a subset of Y, we define the preimage of the set B under the function f, or f--1[B] (note that f does not have to be an injection) as 
.
[edit] Function spaces
The notation YX, or more rarely ![[X \rightarrow Y]](../../../math/e/6/4/e64079c9a3e8f83091f8de77b4b4c9ff.png)
, is used for the set of all functions from X to Y. The operation of exponentiation of cardinals is defined in such a way that |Y||X| = |YX|.
[edit] Functions of more than one argument
A rule which takes an element of A and an element of B to an element of C can be construed as taking an element of 
to an element of C: a 'function of two variables' is interpreted as a function with a single argument taken from a Cartesian product. There is an alternative approach: one could instead interpret the function of two variables as sending each element of A to a function from B to C (this is called currying).
In symbols, f(x, y) is usually construed as f((x, y)), so f is understood to belong to 
, but could alternatively be construed as f(x)(y), whence f would be understood to belong to (CA)B.
The formal notation for functions given above can be extended to notations such as 
.
The treatment of functions of more arguments is analogous.
[edit] Connection to other notions of function
The set-theoretic notion of function is an abstraction from the notion of function of one or more real or complex variables found in analysis. The former notion dates from roughly the 17th century of the common era, and the latter from the latter half of the 19th century of the common era. The two notions are now commonly conflated. The treatment of functions in foundations of mathematics is now also strongly influenced by category theory. The function notion is primitive rather than defined in systems of lambda-calculus.
