User:Boute

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 ${\displaystyle f}$ is a set of ordered pairs ${\displaystyle (x,y)}$ 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) ${\displaystyle G}$ is called the domain of ${\displaystyle G}$ and is written ${\displaystyle \mathrm {dom} \,G}$ or ${\displaystyle {\mathcal {D}}\,G}$. The set of all second members is called the range of ${\displaystyle G}$ and is written ${\displaystyle \mathrm {ran} \,G}$ or ${\displaystyle {\mathcal {R}}\,G}$. Let ${\displaystyle f}$ be a function (functional graph). For each ${\displaystyle x}$ in the domain of ${\displaystyle f}$ there is exactly one ${\displaystyle y}$ such that ${\displaystyle (x,y)\in f}$. Hence ${\displaystyle y}$ is uniquely determined by ${\displaystyle f}$ and ${\displaystyle x}$. It is therefore properly called the value of ${\displaystyle f}$ at ${\displaystyle x}$ and can be unambiguously denoted by some suitable combination of ${\displaystyle f}$ and ${\displaystyle x}$, the common "default" form being ${\displaystyle f\,x}$ or ${\displaystyle f(x)}$. Other forms may be chosen as convenient by prior agreement, such as ${\displaystyle f_{x}}$ or ${\displaystyle x^{f}}$ . A common example of the latter is writing ${\displaystyle M^{\mathsf {T}}}$ for matrix transposition.

A.3 The function equality theorem (Apostol^[2] p. 54) Functions ${\displaystyle f}$ and ${\displaystyle g}$ are equal (${\displaystyle f=g}$) if and only if (a) ${\displaystyle f}$ and ${\displaystyle g}$ have the same domain and (b) ${\displaystyle f(x)=g(x)}$ for every ${\displaystyle x}$ 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 ${\displaystyle f}$ is fully specified by its domain and the value ${\displaystyle f(x)}$ for each ${\displaystyle x}$ in that domain. An illustration follows next.

A.4 Function composition This is the most important operation on functions. For any (plain) functions ${\displaystyle f}$ and ${\displaystyle g}$, the composition ${\displaystyle g\circ f}$ (also written ${\displaystyle f\,;g}$) is also a function, specified as follows: (a) the domain of ${\displaystyle g\circ f}$ is the set of all values ${\displaystyle x}$ in the domain of ${\displaystyle f}$ such that ${\displaystyle f(x)}$ is in the domain of ${\displaystyle g}$ and (b) for any such ${\displaystyle x}$, the value of ${\displaystyle (g\circ f)(x)}$ is given by ${\displaystyle (g\circ f)(x)=g(f(x))}$ or, written with less clutter, ${\displaystyle (g\circ f)x=g(f\,x)}$ (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 ${\displaystyle f}$, ${\displaystyle g}$ and ${\displaystyle h}$, we have ${\displaystyle h\circ (g\circ f)=(h\circ g)\circ f}$. This associativity allows making the parentheses optional and writing, for instance, ${\displaystyle h\circ g\circ f=f\,;g\,;h}$.

A.5 Conveying domain and range information The literature presents numerous conventions for relating the domain and/or range of a (plain) function ${\displaystyle f}$ to sets ${\displaystyle X}$ and ${\displaystyle Y}$. A helpful preamble is the following legend.

More information , is a partial function on ...

statement	meaning
${\displaystyle f}$ is a partial function on ${\displaystyle X}$	${\displaystyle \mathrm {dom} \,f\subseteq X}$
${\displaystyle f}$ is a (total) function on ${\displaystyle X}$	${\displaystyle \mathrm {dom} \,f=X}$

Close

More information , is (in)to ...

statement	meaning
${\displaystyle f}$ is (in)to ${\displaystyle Y}$	${\displaystyle \mathrm {ran} \,f\subseteq Y}$
${\displaystyle f}$ is onto ${\displaystyle Y}$	${\displaystyle \mathrm {ran} \,f=Y}$

Close

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 ${\displaystyle X}$ (in)to ${\displaystyle Y}$ is a function with domain ${\displaystyle X}$ and range included in ${\displaystyle Y}$.

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 ${\displaystyle X}$ to ${\displaystyle Y}$ is commonly introduced by writing ${\displaystyle f:X\rightarrow Y}$, where ${\displaystyle X\rightarrow Y}$ can be interpreted as the set of all (total) functions from ${\displaystyle X}$ (in)to ${\displaystyle Y}$ (Meyer^[23] p. 26, Reynolds^[24] p. 458), in other contexts also written ${\displaystyle Y^{X}}$. As a logical consequence, ${\displaystyle f:X\rightarrow Y}$ stipulates that (a) the domain of ${\displaystyle f}$ is ${\displaystyle X}$ and (b) the values ${\displaystyle f(x)}$ are in ${\displaystyle Y}$ and can be further specified, for instance, by a formula. This style is very convenient, as illustrated by the following function specifications

${\displaystyle {\mathsf {sqra}}:\mathbb {R} \rightarrow \mathbb {R} }$ with ${\displaystyle {\mathsf {sqra}}\,x=x^{2}}$ and ${\displaystyle {\mathsf {sqrb}}:\mathbb {R} \rightarrow \mathbb {R} _{\geq 0}}$ with ${\displaystyle {\mathsf {sqrb}}\,x=x^{2}}$.

By definition, both specify the same function (${\displaystyle {\mathsf {sqra}}={\mathsf {sqrb}}}$) which is onto ${\displaystyle \mathbb {R} _{\geq 0}}$ but not onto ${\displaystyle \mathbb {R} }$. Consider also

${\displaystyle {\mathsf {posrt}}:\mathbb {R} _{\geq 0}\rightarrow \mathbb {R} _{\geq 0}}$ with ${\displaystyle ({\mathsf {posrt}}\,x)^{2}=x}$ and ${\displaystyle {\mathsf {negrt}}:\mathbb {R} _{\geq 0}\rightarrow \mathbb {R} _{\leq 0}}$ with ${\displaystyle ({\mathsf {negrt}}\,x)^{2}=x}$.

Here ${\displaystyle {\mathsf {posrt}}}$ and ${\displaystyle {\mathsf {negrt}}}$ are respectively the positive and negative square root function. Both are functions from ${\displaystyle \mathbb {R} _{\geq 0}}$ to ${\displaystyle \mathbb {R} }$ but ${\displaystyle {\mathsf {posrt}}}$ is onto ${\displaystyle \mathbb {R} _{\geq 0}}$ whereas ${\displaystyle {\mathsf {negrt}}}$ is onto ${\displaystyle \mathbb {R} _{\leq 0}}$.

Similarly, a partial function from ${\displaystyle X}$ to ${\displaystyle Y}$ is a function with domain included in ${\displaystyle X}$ and range included in ${\displaystyle Y}$. For instance, in calculus/analysis most functions are defined on some subset (interval, region, ...) of ${\displaystyle \mathbb {R} }$, ${\displaystyle \mathbb {R} ^{n}}$, ${\displaystyle \mathbb {C} }$, ${\displaystyle \mathbb {C} ^{n}}$ and so on hence are partial on these sets. For the set of partial functions from ${\displaystyle X}$ (in)to ${\displaystyle Y}$ one finds various notations, such as ${\displaystyle X\not \rightarrow Y}$ (Meyer^[23] p. 26) and ${\displaystyle X\;{\stackrel {\longrightarrow }{\scriptscriptstyle \mathrm {PFUN} }}\;Y}$ (Reynolds^[24] p. 458).

As a very interesting illustration, the reader can verify that, given ${\displaystyle f:X\rightarrow Y}$ and ${\displaystyle g:U\rightarrow V}$, the composition ${\displaystyle g\circ f}$ is a partial function from ${\displaystyle X}$ to ${\displaystyle V}$ and that ${\displaystyle g\circ f}$ is a total function from ${\displaystyle X}$ to ${\displaystyle V}$ iff ${\displaystyle \mathrm {ran} \,f\subseteq \mathrm {dom} \,g}$, which trivially holds in case ${\displaystyle Y=U}$.

Important remark: as in natural language, onto is used as a preposition, mentioning ${\displaystyle Y}$ explicitly (Flett^[6] p. 5, Scheinerman^[22] p. 172; more references follow in the next paragraph). A function that is onto ${\displaystyle Y}$ is sometimes called surjective on ${\displaystyle Y}$ or a surjection on ${\displaystyle Y}$. Scheinerman^[22] (p, 172) designates omitting ${\displaystyle Y}$ as "mathspeak", but it is not harmless and may cause misunderstandings.

A.6 A shortcut formulation for a function from ${\displaystyle X}$ to ${\displaystyle Y}$ 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 ${\displaystyle f}$ from ${\displaystyle X}$ (in)to ${\displaystyle Y}$ as a subset of ${\displaystyle X\times Y}$ such that for every ${\displaystyle x}$ in ${\displaystyle X}$ there is exactly one ${\displaystyle y}$ in ${\displaystyle Y}$ such that ${\displaystyle (x,y)\in f}$. 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 ${\displaystyle X}$ to ${\displaystyle Y}$.

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 ${\displaystyle g\circ f}$ is defined for any functions ${\displaystyle f}$, ${\displaystyle g}$, although some authors overlook this and define ${\displaystyle g\circ f}$ only for ${\displaystyle f:X\rightarrow Y}$ and ${\displaystyle g:Y\rightarrow Z}$, which reduces generality by assuming ${\displaystyle \mathrm {ran} \,f\subseteq \mathrm {dom} \,g}$.
• Any function ${\displaystyle f}$ is a function from its domain to any superset of its range. Hence the versatile specification style illustrated by the examples ${\displaystyle {\mathsf {sqra}}}$, ${\displaystyle {\mathsf {sqrb}}}$, ${\displaystyle {\mathsf {posrt}}}$, ${\displaystyle {\mathsf {negrt}}}$ 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 ${\displaystyle f^{n}}$ for ${\displaystyle n}$-fold function composition and ${\displaystyle S^{n}}$ for the ${\displaystyle n}$-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 ${\displaystyle f}$ from ${\displaystyle X}$ to ${\displaystyle Y}$ less formally as associating "in some manner" a unique value ${\displaystyle f(x)}$ in ${\displaystyle Y}$ with every value ${\displaystyle x}$ in ${\displaystyle X}$, called the domain of ${\displaystyle f}$. 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 ${\displaystyle f}$ is then the set of all values ${\displaystyle f(x)}$ for ${\displaystyle x}$ in the domain of ${\displaystyle f}$. All earlier auxiliary formulations carry through literally as stated, namely, fully general composition (A.4) and conveying domain/range information (A5). The graph of ${\displaystyle f}$ is then the set of all pairs ${\displaystyle (x,fx)}$ for ${\displaystyle x}$ in the domain of ${\displaystyle f}$ and is denoted by ${\displaystyle {\mathcal {G}}\,f}$. Evidently ${\displaystyle f=g}$ if and only if ${\displaystyle {\mathcal {G}}\,f={\mathcal {G}}\,g}$. 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 ${\displaystyle Y}$ in ${\displaystyle f:X\rightarrow Y}$ specifies that ${\displaystyle f(x)\in Y}$, without making ${\displaystyle Y}$ an attribute of ${\displaystyle f}$ (in contrast ${\displaystyle X}$, 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 ${\displaystyle {\mathsf {sqra}}}$, ${\displaystyle {\mathsf {sqrb}}}$, ${\displaystyle {\mathsf {posrt}}}$, ${\displaystyle {\mathsf {negrt}}}$.

Dasgupta^[13] (p. 10) points out that making ${\displaystyle Y}$ an attribute of ${\displaystyle f}$ in a proper fashion requires explicitly attaching ${\displaystyle Y}$ to ${\displaystyle f}$ to form a triplet ${\displaystyle \langle f,X,Y\rangle }$. Mac Lane^[26] (p. 27) calls this modification labelling. In general,

A (labeled) function is a triplet ${\displaystyle F:=\langle f,X,Y\rangle }$ where ${\displaystyle f}$ is a (plain) partial function from ${\displaystyle X}$ to ${\displaystyle Y}$.

The set ${\displaystyle X}$ is called the source of ${\displaystyle F}$ and ${\displaystyle Y}$ is called the target of ${\displaystyle F}$ or the codomain of ${\displaystyle F}$. The domain and the range of ${\displaystyle F}$ are those of ${\displaystyle f}$. 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 ${\displaystyle F:=\langle f,X,Y\rangle }$, the following terminology holds: (i) ${\displaystyle F}$ is partial means that ${\displaystyle \mathrm {dom} \,f\subseteq X}$, (ii) ${\displaystyle F}$ is total means that ${\displaystyle \mathrm {dom} \,f=X}$, and (iii) or ${\displaystyle F}$ is surjective means that ${\displaystyle \mathrm {ran} \,f=Y}$.
• Composition ${\displaystyle G\circ F}$ is defined only in case ${\displaystyle \mathrm {cod} \,F=\mathrm {src} \,G}$. In case ${\displaystyle G}$ is total this means that ${\displaystyle \mathrm {cod} \,F=\mathrm {dom} \,G}$, which is quite restrictive when compared to the plain variant.

References

Last updated: Boute (talk) 13:11, 15 February 2022 (UTC)