SANDBOX -- IN PREPARATION -- WILL BE ADDED TO THE MAIN WIKI PAGES WHEN READY
Towards a coherent article about functions (mathematics)
Rationale The following outline is a suggestion for prospective editors. For various reasons (stability of edits and links to related articles) I prefer not doing any editing myself, but present these notes as a resource for others. The basic rationale is that the article should center on helping the readers rather than on the personal preferences of the writers/editors. Therefore I will not start with my own preferred definition but with a reader-oriented one with the following characteristics: (a) utmost simplicity; (b) enhancing clarity by adhering to the principle of separation of concerns, in this case separating the concept of function pure and simple from characterizing a function as being from to
; (c) the most general one in view of its algebraic properties, especially around composition; (d) prevalent in basic university/college textbooks in mathematics; (e) a convenient logical basis for explaining/understanding/comparing other variants. It is fortunate that all these properties happen to coincide. Also fortunate is that in the current literature there are essentially only two variants, simply distinguished by whether or not the notion of a codomain plays any role, so covering both remains very manageable. Also clarifying for the readers are brief justifications of the design decisions behind the definitions, without turning the article into a fully-fledged tutorial that is too long for Wikipedia. In view of the many misconceptions observed in the printed literature and on the web (including Wikipedia), a substantial package of references is indispensable. The text follows next.
Outline for the article (text starts here)
The concept of a function or a mapping has been described (Herstein[1], page 9) as "probably the single most important and universal notion that runs through all of mathematics". Evidently this also pertains to all other branches of science (physics, engineering etc.) where mathematics is used.
In present-day mathematics, there are essentially two major variants of the function concept, and in a balanced account both must be addressed. For this purpose, we designate them as (A) the plain variant and (B) the labeled variant, which has a codomain. The subject matter also requires ample references, also because different formulations often define the same variant, thereby clarifying each other. About a dozen paragraph suffice for giving the reader a structured guide through the rather varied literature.
A. Functions: the plain variant
This variant is the simplest and also the most widespread throughout the sciences, including (but not limited to) calculus/analysis[2][3][4][5][6][7][8][9][10],set theory[11][12][13][14][15][16][17],logic[18][19],algebra[1],discrete mathematics[20][21][22],computer science[23][24],and mathematical physics[25]. Authors and specific page numbers will be mentioned later.
A.1 Basic definition One of the simplest formulations is provided by Apostol[2] (p.53):
"A function
is a set of ordered pairs
no two of which have the same first member."
In general, a collection of ordered pairs is called a graph or a relation and is called functional[12][23] or determinate[21] if no two pairs have the same first member (or component). Thus the preceding definition can be rephrased by saying that a function is a functional graph ((Bourbaki[12] p. 77). Formulations that are equivalent in content and style appear in calculus/analysis (Apostol[2] p. 53, Flett[6], p. 4), set theory (Bourbaki[12] p. 77, Dasgupta[13] p. 8, Quine[15] p. 21, Suppes[16] p. 57, Tarski & Givant[17] p. 3), logic (Mendelson[18] p. 6, Tarski[19] p. 98), discrete mathematics (Scheinerman[22] p. 73), computer science ((Meyer[23] p. 25, Reynolds[24] p. 452). The wordings differ but all define the same concept, apart from the fact that some authors[11][15][17] apply them to classes instead of mere sets.
A.2 Conventions The set of all first members of the ordered pairs in a graph (or relation) is called the domain of
and is written
or
. The set of all second members is called the range of
and is written
or
. Let
be a function (functional graph). For each
in the domain of
there is exactly one
such that
. Hence
is uniquely determined by
and
. It is therefore properly called the value of
at
and can be unambiguously denoted by some suitable combination of
and
, the common "default" form being
or
. Other forms may be chosen as convenient by prior agreement, such as
or
. A common example of the latter is writing
for matrix transposition.
A.3 The function equality theorem (Apostol[2] p. 54) Functions and
are equal (
) if and only if (a)
and
have the same domain and (b)
for every
in this domain. This theorem follows directly from set equality and holds for all formulations (preceding and following) of the definition of plain functions. It implies that a (plain) function
is fully specified by its domain and the value
for each
in that domain. An illustration follows next.
A.4 Function composition This is the most important operation on functions. For any (plain) functions and
, the composition
(also written
) is also a function, specified as follows: (a) the domain of
is the set of all values
in the domain of
such that
is in the domain of
and (b) for any such
, the value of
is given by
or, written with less clutter,
(see Apostol[2] p. 140, Flett[6] p. 11, Suppes[16] p. 87, Tarski & Givant[17] p. 3, Mendelson[18] p. 7, Meyer[23] p. 32, Reynolds[24] p. 450,452). Composition has the interesting property that, for all functions
,
and
, we have
. This associativity allows making the parentheses optional and writing, for instance,
.
A.5 Conveying domain and range information The literature presents numerous conventions for relating the domain and/or range of a (plain) function to sets
and
. A helpful preamble is the following legend.
statement | meaning |
---|---|
statement | meaning |
---|---|
For instance (Apostol[2] p. 578, Flett[6] p. 5, Dasgupta [13] p. 10, Scheinerman[22] p. 169, Meyer[23] p. 26, Reynolds[24] p. 458):
A (total) function from
(in)to
is a function with domain
and range included in
.
Flett[6] (p. 5) warns that such phrases only conveys information about the domain and the range but does not define a new kind of function. A function from to
is commonly introduced by writing
, where
can be interpreted as the set of all (total) functions from
(in)to
(Meyer[23] p. 26, Reynolds[24] p. 458), in other contexts also written
. As a logical consequence,
stipulates that (a) the domain of
is
and (b) the values
are in
and can be further specified, for instance, by a formula. This style is very convenient, as illustrated by the following function specifications
with
and
with
.
By definition, both specify the same function ( ) which is onto
but not onto
.Consider also
with
and
with
.
Here and
are respectively the positive and negative square root function. Both are functions from
to
but
is onto
whereas
is onto
.
Similarly, a partial function from to
is a function with domain included in
and range included in
. For instance, in calculus/analysis most functions are defined on some subset (interval, region, ...) of
,
,
,
and so on hence are partial on these sets. For the set of partial functions from
(in)to
one finds various notations, such as
(Meyer[23] p. 26) and
(Reynolds[24] p. 458).
As a very interesting illustration, the reader can verify that, given and
, the composition
is a partial function from
to
and that
is a total function from
to
iff
, which trivially holds in case
.
Important remark: as in natural language, onto is used as a preposition, mentioning explicitly (Flett[6] p. 5, Scheinerman[22] p. 172; more references follow in the next paragraph). A function that is onto
is sometimes called surjective on
or a surjection on
. Scheinerman[22] (p, 172) designates omitting
as "mathspeak", but it is not harmless and may cause misunderstandings.
A.6 A shortcut formulation for a function from to
Quite a few authors (Bartle & Sherbert[4] p. 5, Royden[8] p. 8, Halmos[14] p. 30,Herstein[1] p. 10, Gerstein[20] p. 110, [25] Gries & Schneider[21] p. 280, Szekeres[25] p. 10) do not start from the basic definition given earlier but directly define a function
from
(in)to
as a subset of
such that for every
in
there is exactly one
in
such that
. Less often, some authors (Bartle[3] p. 13, Gries and Schneider[21] p. 280) use a formulation that amounts to replacing "exactly one" by "at most one", which effectively defines a partial function from
to
.
Important remark: appearances notwithstanding, this shortcut formulation logically defines exactly the same kind of function as the basic definition with exactly the same properties and conventions. In particular:,
- The function equality theorem holds as stated (only mentioned explicitly by Gerstein[20] p. 113).
- Composition
is defined for any functions
,
, although some authors overlook this and define
only for
and
, which reduces generality by assuming
.
- Any function
is a function from its domain to any superset of its range. Hence the versatile specification style illustrated by the examples
,
,
,
remains applicable.
- As before, onto-ness is specified with respect to a set, using "onto" as a preposition (Bartle[3] p. 13, Bartle & Sherbert[4] p.7, Royden[8] p. 8, Halmos[14] p. 31, Herstein[1] p. 12, Gerstein[20] p. 118, Szekeres[25] p. 11).
A.7 Separating the plain function concept from its graph Whereas defining a function as a graph is very precise and rigorous, it creates some ambiguities for certain common conventions. Just two examples: (i) writing for
-fold function composition and
for the
-fold Cartesian product, and (ii) defining sequences (in particular pairs) as functions on some subset of the natural numbers. Some definitions (Carlson[5] p. 182, Kolmogorov & Fomin[7] p. 5, Rudin[9] p. 21) avoid this by defining a function
from
to
less formally as associating "in some manner" a unique value
in
with every value
in
, called the domain of
. This can be captured as follows:
A (plain) function is an entity that is fully specified by a domain, which is a collection (set or a class) of values, and by a unique value assigned to each element in this domain.
As noted by Royden[8] (footnote p. 8) this formulation can be made precise by taking the statement of the function equality theorem (A.3) as an axiom. The range of is then the set of all values
for
in the domain of
.All earlier auxiliary formulations carry through literally as stated, namely, fully general composition (A.4) and conveying domain/range information (A5). The graph of
is then the set of all pairs
for
in the domain of
and is denoted by
. Evidently
if and only if
. This may be useful in simplifying certain proofs and definitions (e.g., for inverses).
B. Functions: the labeled variant and the notion of codomain
Recall that, for plain functions, the appearance of in
specifies that
, without making
an attribute of
(in contrast
, which is specified to be the domain). How to exploit this flexibility in function specifications was demonstrated by the examples for illustrated by the examples
,
,
,
.
Dasgupta[13] (p. 10) points out that making an attribute of
in a proper fashion requires explicitly attaching
to
to form a triplet
. Mac Lane[26] (p. 27) calls this modification labelling. In general,
A (labeled) function is a triplet
where
is a (plain) partial function from
to
.
The set is called the source of
and
is called the target of
or the codomain of
. The domain and the range of
are those of
. Similar formulations, sometimes identifying domain and source, are given by Bourbaki[12] p. 76, Adámek & al.[27] footnote p. 14, Bird & De Moor[28] p. 26, Pierce[29] p. 2. Some of the major differences with the plain varianr are:
- Equality of labeled functions requires equality for source, domain, codomain and images.
- For a labeled function
, the following terminology holds: (i)
is partial means that
, (ii)
is total means that
, and (iii) or
is surjective means that
.
- Composition
is defined only in case
. In case
is total this means that
, which is quite restrictive when compared to the plain variant.