SANDBOX -- IN PREPARATION -- WILL BE ADDED TO THE MAIN WIKI PAGES WHEN READY

Towards a coherent article about functions (mathematics)

edit

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)

edit

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

edit

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
  is a partial function on    
  is a (total) function on    
statement meaning
  is (in)to    
  is onto    

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

edit

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.

References

edit
  1. ^ a b c d Herstein, Israel N. (1964). Topics in Algebra. Lexington, Mass: Xerox College Publishing. ISBN 0-536-00258-4.
  2. ^ a b c d e f Apostol, Tom M. (1967). Calculus, Volume I (Second ed.). New York: Wiley. ISBN 9971-51-396-X.
  3. ^ a b c Bartle, Robert G. (1964). The Elements of Real Analysis. New York: Wiley.
  4. ^ a b c Bartle, Robert G.; Sherbert, Donald R. (2011). Introduction to Real Analysis (4th ed.). New York: Wiley. ISBN 9780471433316.
  5. ^ a b Carlson, Robert (2006). A Concrete Introduction to Real Analysis. Boca Raton: Chapmam & Hall/CRC. ISBN 1-58488-654-4.
  6. ^ a b c d e f Flett, Thomas M. (1966). Mathematical Analysis. New York: McGraw-Hill.
  7. ^ a b Kolmogorov, Andrey L.; Fomin, Sergey V. (1975). Introductory Real Analysis. New York: Dover. ISBN 0-486-61226-0.
  8. ^ a b c d Royden, Halsey L. (1968). Real Analysis. New York: Macmillan.
  9. ^ a b Rudin, Walter (1964). Principles of Mathematical Analysis (Second ed.). New York: McGraw-Hill.
  10. ^ Thomas, Jeorge B. Jr.; Weir, Maurice W.; Hass, Joel; Giordano, Frank R. (2005). Thomas' Calculus (Eleventh ed.). Boston: Pearson/Addison Wesley. ISBN 0-321-24335-8.
  11. ^ a b Bernays, Paul (1991). Axiomatic Set Theory. New York: Dover Publications Inc. ISBN 0-486-66637-9.
  12. ^ a b c d e Bourbaki, Nicolas (1954). Theorie des ensembles. Paris: Hermann & Cie.
  13. ^ a b c d Dasgupta, Abhijit (2014). Set Theory. New York: Birkhauser/Springer. ISBN 978-1-4614-8853-8.
  14. ^ a b c Halmos, Paul (1960). Naive Set Theory. New York: Van Nostrand Reinhold.
  15. ^ a b c Quine, Willard Van Orman (1969). Set Theory and its Logic. Cambridge, Mass.: Belknap Press/Harvard. ISBN 0674802071.
  16. ^ a b c Suppes, Patrick (1972). Axiomatic Set Theory. New York: Dover Publications Inc. ISBN 0-486-61630-4.
  17. ^ a b c d Tarski, Alfred; Givant, Steven (1987). A Formalization of Set Theory Without Variables. Providence, RI: American Mathematical Society. ISBN 0-8218-1041-3.
  18. ^ a b c Mendelson, Elliott (1987). Introduction to Mathematical Logic. Pacific Grove, CA: Wadsworth & Brooks/Cole. ISBN 0-534-06624-0.
  19. ^ a b Tarski, Alfred (1995). Introduction to Logic. New York: Dover Publications Inc. ISBN 0-486-28462-X.
  20. ^ a b c d Gerstein, Larry J. (2012). Introduction to Mathematical Structures and Proofs. New York: Springer. ISBN 978-1-4614-4264-6.
  21. ^ a b c d Gries, David; Schneider, Fred B. (2010). A Logical Approach to Discrete Math. New York: Springer. ISBN 1441928359.
  22. ^ a b c d e Scheinerman, Edward R. (2013). Mathematics -- A Discrete Introduction (third ed.). Boston: Cengage Learning. ISBN 0-8400-4942-0.
  23. ^ a b c d e f g Meyer, Bertrand (1991). Introduction to the Theory of Programming Languages. New York: Prentice Hall. ISBN 0-13-498502-8.
  24. ^ a b c d e f Reynolds, John C. (2009). Theories of Programming Languages. Cambridge: Cambridge University Press. ISBN 978-0-521-10697-9.
  25. ^ a b c d Szekeres, Peter (2004). A Course in Modern Mathematical Physics. Cambridge, UK: Cambridge University Press. ISBN 0-521-82960-7.
  26. ^ Mac Lane, Saunders (1971). Categories for the Working Mathematician. New York: Springer. ISBN 0-387-90036-5.
  27. ^ Adámek, Jiří; Herrlich, Horst; Strecker, George E. (2004). Abstract and Concrete Categories - The Joy of Cats. open source: GNU Free Documentation Licence.
  28. ^ Bird, Richard; De Moor, Oege (1997). Algebra of Programming. Harlow: Prentice Hall/Pearson. ISBN 0-13-507245-X.
  29. ^ Pierce, Benjamin C. (1991). Basic Category Theory for Computer Scientists. Cambridge, Mass.: The MIT Press. ISBN 0-262-66071-7.

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