User:Boute

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 $X$ to $Y$; (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.

The concept of a function or a mapping has been described (Herstein, 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.

This variant is the simplest and also the most widespread throughout the sciences, including (but not limited to) calculus/analysis{{cite book |last1=Apostol |first1=Tom M. |title=Calculus, Volume I |date=1967 |publisher=Wiley |location=New York |edition=Second |isbn=9971-51-396-X}}{{cite book |last1=Bartle |first1=Robert G. |title=The Elements of Real Analysis |date=1964 |publisher=Wiley |location=New York |isbn=}}{{cite book |last1=Bartle |first1=Robert G. |last2=Sherbert |first2=Donald R. |title=Introduction to Real Analysis |date=2011 |publisher=Wiley |location=New York |isbn=9780471433316 |edition=4th}}{{cite book |last1=Carlson |first1=Robert |title=A Concrete Introduction to Real Analysis |date=2006 |publisher=Chapmam & Hall/CRC |location=Boca Raton |isbn=1-58488-654-4}}{{cite book |last1=Flett |first1=Thomas M. |title=Mathematical Analysis |date=1966 |publisher=McGraw-Hill |location=New York}}{{cite book |last1=Kolmogorov |first1=Andrey L. |last2=Fomin |first2=Sergey V. |title=Introductory Real Analysis |date=1975 |publisher=Dover |location=New York |isbn=0-486-61226-0}}{{cite book |last1=Royden |first1=Halsey L. |title=Real Analysis |date=1968 |publisher=Macmillan |location=New York}}{{cite book |last1=Rudin |first1=Walter |title=Principles of Mathematical Analysis |date=1964 |publisher=McGraw-Hill |location=New York |edition=Second}}{{cite book |last1=Thomas |first1=Jeorge B. Jr. |last2=Weir |first2=Maurice W. |last3=Hass |first3=Joel |last4=Giordano |first4=Frank R. |title=Thomas' Calculus |date=2005 |publisher=Pearson/Addison Wesley |location=Boston |edition=Eleventh |isbn=0-321-24335-8}},

set theory{{cite book |last1=Bernays |first1=Paul |title=Axiomatic Set Theory |date=1991 |publisher=Dover Publications Inc. |location=New York |isbn=0-486-66637-9}}{{cite book |last1=Bourbaki |first1=Nicolas |title=Theorie des ensembles |date=1954 |publisher=Hermann & Cie. |location=Paris}}{{cite book |last1=Dasgupta |first1=Abhijit |title=Set Theory |date=2014 |publisher=Birkhauser/Springer |location=New York |isbn=978-1-4614-8853-8}}{{cite book |last1=Halmos |first1=Paul |title=Naive Set Theory |date=1960 |publisher=Van Nostrand Reinhold |location=New York}}{{cite book |last1=Quine |first1=Willard Van Orman |title=Set Theory and its Logic |date=1969 |publisher=Belknap Press/Harvard |location=Cambridge, Mass. |isbn=0674802071}}{{cite book |last1=Suppes |first1=Patrick |title=Axiomatic Set Theory |date=1972 |publisher=Dover Publications Inc. |location=New York |isbn=0-486-61630-4}}{{cite book |last1=Tarski |first1=Alfred |last2=Givant |first2=Steven |title=A Formalization of Set Theory Without Variables |date=1987 |publisher=American Mathematical Society |location=Providence, RI |isbn=0-8218-1041-3}},

logic{{cite book |last1=Mendelson |first1=Elliott |title=Introduction to Mathematical Logic |date=1987 |publisher=Wadsworth & Brooks/Cole |location=Pacific Grove, CA |isbn=0-534-06624-0}}{{cite book |last1=Tarski |first1=Alfred |title=Introduction to Logic |date=1995 |publisher=Dover Publications Inc. |location=New York |isbn=0-486-28462-X}},

algebra{{cite book |last1=Herstein |first1=Israel N. |title=Topics in Algebra |date=1964 |publisher=Xerox College Publishing |location=Lexington, Mass |isbn=0-536-00258-4}},

discrete mathematics{{cite book |last1=Gerstein |first1=Larry J. |title=Introduction to Mathematical Structures and Proofs |date=2012 |publisher=Springer |location=New York |isbn=978-1-4614-4264-6}}{{cite book |last1=Gries |first1=David |last2=Schneider |first2=Fred B. |title=A Logical Approach to Discrete Math |date=2010 |publisher=Springer |location=New York |isbn=1441928359}}{{cite book |last1=Scheinerman |first1=Edward R. |title=Mathematics -- A Discrete Introduction |date=2013 |publisher=Cengage Learning |location=Boston |edition=third |isbn=0-8400-4942-0}},

computer science{{cite book |last1=Meyer |first1=Bertrand |title=Introduction to the Theory of Programming Languages |date=1991 |publisher=Prentice Hall |location=New York |isbn=0-13-498502-8}}{{cite book |last1=Reynolds |first1=John C. |title=Theories of Programming Languages |date=2009 |publisher=Cambridge University Press |location=Cambridge |isbn=978-0-521-10697-9}},

and mathematical physics{{cite book |last1=Szekeres |first1=Peter |title=A Course in Modern Mathematical Physics |date=2004 |publisher=Cambridge University Press |location=Cambridge, UK |isbn=0-521-82960-7}}. Authors and specific page numbers will be mentioned later.

A.1 Basic definition

One of the simplest formulations is provided by Apostol (p.53):

{{quote | "A function $f$ is a set of ordered pairs $(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 or determinate 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 p. 77). Formulations that are equivalent in content and style appear in calculus/analysis (Apostol p. 53, Flett, p. 4), set theory (Bourbaki p. 77, Dasgupta p. 8, Quine p. 21, Suppes p. 57, Tarski & Givant p. 3), logic (Mendelson p. 6, Tarski p. 98), discrete mathematics (Scheinerman p. 73), computer science ((Meyer p. 25, Reynolds p. 452). The wordings differ but all define the same concept, apart from the fact that some authors 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) $G$ is called the domain of $G$ and is written $\backslash mathrm\{dom\}\backslash ,G$ or $\backslash mathcal\{D\}\backslash ,G$. The set of all second members is called the range of $G$ and is written $\backslash mathrm\{ran\}\backslash ,G$ or $\backslash mathcal\{R\}\backslash ,G$. Let $f$ be a function (functional graph). For each $x$ in the domain of $f$ there is exactly one $y$ such that $(x,\; y)\; \backslash in\; f$. Hence $y$ is uniquely determined by $f$ and $x$. It is therefore properly called the value of $f$ at $x$ and can be unambiguously denoted by some suitable combination of $f$ and $x$, the common "default" form being $f\backslash ,x$ or $f(x)$. Other forms may be chosen as convenient by prior agreement, such as $f\_x$ or $x^f$ . A common example of the latter is writing $M^\{\backslash mathsf\; T\}$ for matrix transposition.

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

A.4 Function composition This is the most important operation on functions. For any (plain) functions $f$ and $g$, the composition $g\; \backslash circ\; f$ (also written $f\backslash ,;g$) is also a function, specified as follows: (a) the domain of $g\; \backslash circ\; f$ is the set of all values $x$ in the domain of $f$ such that $f(x)$ is in the domain of $g$ and (b) for any such $x$, the value of $(g\; \backslash circ\; f)(x)$ is given by $(g\; \backslash circ\; f)(x)\; =\; g(f(x))$ or, written with less clutter, $(g\; \backslash circ\; f)\; x\; =\; g(f\backslash ,x)$ (see Apostol p. 140, Flett p. 11, Suppes p. 87, Tarski & Givant p. 3, Mendelson p. 7, Meyer p. 32, Reynolds p. 450,452). Composition has the interesting property that, for all functions $f$, $g$ and $h$, we have $h\; \backslash circ\; (g\; \backslash circ\; f)\; =\; (h\; \backslash circ\; g)\; \backslash circ\; f$. This associativity allows making the parentheses optional and writing, for instance, $h\; \backslash circ\; g\; \backslash circ\; f\; =\; f\backslash ,;g\backslash ,;h$.

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

For instance (Apostol p. 578, Flett p. 5, Dasgupta p. 10, Scheinerman p. 169, Meyer p. 26, Reynolds p. 458):

{{ quote |

A (total) function from $X$ (in)to $Y$ is a function with domain $X$ and range included in $Y$.}}

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

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

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

Consider also

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

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

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

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

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

A.6 A shortcut formulation for a function from $X$ to $Y$ Quite a few authors (Bartle & Sherbert p. 5, Royden p. 8, Halmos p. 30,

Herstein p. 10, Gerstein p. 110, Gries & Schneider p. 280, Szekeres p. 10) do not start from the basic definition given earlier but directly define a function $f$ from $X$ (in)to $Y$ as a subset of $X\; \backslash times\; Y$ such that for every $x$ in $X$ there is exactly one $y$ in $Y$ such that $(x,\; y)\; \backslash in\; f$. Less often, some authors (Bartle p. 13, Gries and Schneider p. 280) use a formulation that amounts to replacing "exactly one" by "at most one", which effectively defines a partial function from $X$ to $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 p. 113).
• Composition $g\; \backslash circ\; f$ is defined for any functions $f$, $g$, although some authors overlook this and define $g\; \backslash circ\; f$ only for $f\; :\; X\; \backslash rightarrow\; Y$ and $g\; :\; Y\; \backslash rightarrow\; Z$, which reduces generality by assuming $\backslash mathrm\{ran\}\backslash ,f\; \backslash subseteq\; \backslash mathrm\{dom\}\backslash ,g$.
• Any function $f$ is a function from its domain to any superset of its range. Hence the versatile specification style illustrated by the examples $\backslash mathsf\{sqra\}$, $\backslash mathsf\{sqrb\}$, $\backslash mathsf\{posrt\}$, $\backslash mathsf\{negrt\}$ remains applicable.
• As before, onto-ness is specified with respect to a set, using "onto" as a preposition (Bartle p. 13, Bartle & Sherbert p.7, Royden p. 8, Halmos p. 31, Herstein p. 12, Gerstein p. 118, Szekeres 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 $f^n$ for $n$-fold function composition and $S^n$ for the $n$-fold Cartesian product, and (ii) defining sequences (in particular pairs) as functions on some subset of the natural numbers. Some definitions (Carlson p. 182, Kolmogorov & Fomin p. 5, Rudin p. 21) avoid this by defining a function $f$ from $X$ to $Y$ less formally as associating "in some manner" a unique value $f(x)$ in $Y$ with every value $x$ in $X$, called the domain of $f$. This can be captured as follows:

{{ quote | 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 (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 $f$ is then the set of all values $f(x)$ for $x$ in the domain of $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 $f$ is then the set of all pairs $(x,\; f\; x)$ for $x$ in the domain of $f$ and is denoted by $\backslash mathcal\; G\backslash ,f$. Evidently $f\; =\; g$ if and only if $\backslash mathcal\; G\backslash ,f\; =\; \backslash mathcal\; G\backslash ,g$. This may be useful in simplifying certain proofs and definitions (e.g., for inverses).

Recall that, for plain functions, the appearance of $Y$ in $f\; :\; X\; \backslash rightarrow\; Y$ specifies that $f(x)\; \backslash in\; Y$, without making $Y$ an attribute of $f$ (in contrast $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 $\backslash mathsf\{sqra\}$, $\backslash mathsf\{sqrb\}$, $\backslash mathsf\{posrt\}$, $\backslash mathsf\{negrt\}$.

Dasgupta (p. 10) points out that making $Y$ an attribute of $f$ in a proper fashion requires explicitly attaching $Y$ to $f$ to form a triplet $\backslash langle\; f,\; X,\; Y\; \backslash rangle$. Mac Lane{{cite book |last1=Mac Lane |first1=Saunders |title=Categories for the Working Mathematician |date=1971 |publisher=Springer |location=New York |isbn=0-387-90036-5}} (p. 27) calls this modification labelling. In general,

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

The set $X$ is called the source of $F$ and $Y$ is called the target of $F$ or the codomain of $F$. The domain and the range of $F$ are those of $f$. Similar formulations, sometimes identifying domain and source, are given by Bourbaki p. 76, Adámek & al.{{cite book |last1=Adámek |first1=Jiří |last2=Herrlich |first2=Horst |last3=Strecker |first3=George E. |title=Abstract and Concrete Categories - The Joy of Cats |date=2004 |publisher=GNU Free Documentation Licence |location=open source}} footnote p. 14, Bird & De Moor{{cite book |last1=Bird |first1=Richard |last2=De Moor |first2=Oege |title=Algebra of Programming |date=1997 |publisher=Prentice Hall/Pearson |location=Harlow |isbn=0-13-507245-X}} p. 26, Pierce{{cite book |last1=Pierce |first1=Benjamin C. |title=Basic Category Theory for Computer Scientists |date=1991 |publisher=The MIT Press |location=Cambridge, Mass. |isbn=0-262-66071-7}} 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 $F\; :=\; \backslash langle\; f,\; X,\; Y\; \backslash rangle$, the following terminology holds: (i) $F$ is partial means that $\backslash mathrm\{dom\}\backslash ,f\; \backslash subseteq\; X$, (ii) $F$ is total means that $\backslash mathrm\{dom\}\backslash ,f\; =\; X$, and (iii) or $F$ is surjective means that $\backslash mathrm\{ran\}\backslash ,f\; =\; Y$.
• Composition $G\; \backslash circ\; F$ is defined only in case $\backslash mathrm\{cod\}\backslash ,F\; =\; \backslash mathrm\{src\}\backslash ,G$. In case $G$ is total this means that $\backslash mathrm\{cod\}\backslash ,F\; =\; \backslash mathrm\{dom\}\backslash ,G$, which is quite restrictive when compared to the plain variant.

{{reflist}}

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