Tag Archives: identity

abstractmath.org, category theory, exposition, math, proof, understanding math

A new kind of introduction to category theory

Leave a comment

About this article

  • This post is an alpha version of the first part of the intended article.
  • People who are beginners in learning abstract math concepts have many misunderstandings about the definitions and early theorems of category theory.
  • This article introduces a few basic concepts of category theory. It goes into detail in Purple Prose about the misunderstandings that can arise with each of the concepts. The article is not at all a complete introduction to categories.
  • My blog post Introducing abstract topics describes some of the strategies needed in teaching a new abstract math concept.
  • This article also introduces a few examples of categories that are primarily chosen to cause the reader to come up against some of those misunderstandings. The first example is completely abstract.
  • Math students usually see categories after considerable exposure to abstract math, but students in computing science and other fields may see it without having much background in abstraction. I hope teachers in such courses will include explanations of the sort of misunderstandings mentioned in this article.
  • Like all posts in Gyre&Gimble and all posts in abstractmath.org, this article is licensed under a Creative Commons Attribution-ShareAlike 2.5 License. If you are teaching a class involving category theory, feel free to hand it out, and to modify it (in which case you should include a link to this post).
  • You could also use the article as a source of remarks you make in the class about the topics.

About categories

To be written.

Definition of category

A category is a type of Mathematical structure consisting of two types of data, whose relationships are entirely determined by some axioms. After the definition is complete, I will introduce several categories with a detailed discussion of each one, explaining how they fit the definition of category.

Axiom 1: Data

  1. A category consists of two types of data: objects and arrows.
  2. No object can be an arrow and no arrow can be an object.

Notes for Axiom 1

  • An object of a category can be any kind of mathematical object. It does not have to be a set and it does not have to have elements.
  • Arrows of a category are also called morphisms. You may be familiar with “homomorphisms”, “homeomorphisms” or “isomorphisms”, all of which are functions. This does not mean that a “morphism” in an arbitrary category is a function.

Axiom 2: Domain and codomain

  1. Each arrow has a domain and a codomain, each of which is an object of the category.
  2. The domain and the codomain of an arrow may or may not be the same object.
  3. Each arrow has only one domain and only one codomain.

Notes for Axiom 2

  • If $f$ is an arrow with domain $A$ and codomain $B$, that fact is typically shown either by the notation “$f:A\to B$” or by a diagram like this:

  • The notation “$f:A\to B$” is like that used for functions. This notation may be used in any category, but it does not imply that $f$ is a function or that $A$ and $B$ have elements.
  • For such an arrow, the notation “$\text{dom}(f)$” refers to $A$ and “$\text{cod}(f)$” refers to $B$.
  • For a given category $\mathsf{C}$, the collection of all the arrows with domain $A$ and codomain $B$ may be denoted by
    • “$\text{Hom}(A,B)$” or
    • “$\text{Hom}_\mathsf{C}(A,B)$” or
    • “$\mathsf{C}(A,B)$”.
  • Some newer books and articles in category theory use the name source for domain and target for codomain. This usage has the advantage that a newcomer to category theory will be less likely to think of an arrow as a function.

Axiom 3: Composition

  1. If $f$ and $g$ are arrows in a category for which $\text{cod}(f)=\text{dom}(g)$, as in this diagram:

    then there is a unique arrow with domain $A$ and codomain $C$ called the composite of $f$ and $g$.

Notes for Axiom 3

    diagra

  • An important metaphor for composition is: Every path of length 2 has exactly one composite.
  • The unique arrow required by Axiom 3 may be denoted by “$g\circ f$” or “$gf$”. “$g\circ f$” is more explicit, but “$gf$” is much more commonly used by category theorists.
  • Many constructions in categories may be shown by diagrams, like the one used just above.
  • The diagram

    is said to commute if $h=g\circ f$. The idea is that going along $f$ and then $g$ is the same as going along $h$.

  • It is customary in some texts in category theory to indicate that a diagram commutes by putting a gyre in the middle:
  • The concept of category is an abstraction of the idea of function, and the composition of arrows is an abstraction of the composition of functions. It uses the same notation, “$g\circ f$”. If $f$ and $g$ are set functions, then for an element $x$ in the domain of $f$, \[(g\circ f)(x)=g(f(x))\]
  • But in arbitrary category, it may make no sense to evaluate an arrow $f$ at some element $x$; indeed, the domain of $f$ may not have elements at all, and then the statement “$(g\circ f)(x)=g(f(x))$” is meaningless.

Axiom 4: Identity arrows

  1. For each object $A$ of a category, there is a unique arrow denoted by $\textsf{id}_A$.
  2. $\textsf{dom}(\textsf{id}_A)=A$ and $\textsf{cod}(\textsf{id}_A)=A$.
  3. For any object $B$ and any arrow $f:B\to A$, the diagram

    commutes.

  4. For any object $C$ and any arrow $g:A\to C$, the diagram

    commutes.

Notes for Axiom 4

  • The fact stated in Axiom 4(b) could be shown diagrammatically either as

    or as

  • Facts (c) and (d) can be written in algebraic notation: For any arrow $f$ going to $A$,\[\textsf{id}_A\circ f=f\]and for any arrow $g$ coming from $A$,\[g\circ \textsf{id}_A=g\]

Axiom 5: Associativity

  1. If $f$, $g$ and $h$ are arrows in a category for which $\text{cod}(f)=\text{dom}(g)$ and $\text{cod}(g)=\text{dom}(h)$, as in this diagram:

    then there is a unique arrow $k$ with domain $A$ and codomain $C$ called the composite of $f$, $g$ and $h$.

  2. In the diagram below, the two triangles containing $k$ must both commute.

Notes for Axiom 5

  • Axiom 5b requires that \[h\circ(g\circ f)=(h\circ g)\circ f\](which both equal $k$), which is the usual formula for associativity.
  • Note that the top two triangles commute by Axiom 3.
  • The associativity axiom means that we can get rid of parentheses and write \[k=h\circ f\circ g\]just as we do for addition and multiplication of numbers.
  • In my opinion the notation using categorical diagrams communicates information much more clearly than algebraic notation does. In particular, you don’t have to remember the domains and codomains of the functions — they appear in the picture. I admit that diagrams take up much more space, but now that we read math stuff on a computer screen instead of on paper, space is free.

Examples of categories

For the first three examples, I will give a detailed explanation about how they fit the definition of category.

Example 1: MyFin

This first example is a small, finite category which I have named $\mathsf{MyFin}$ (my very own finite category). It is not at all an important category, but it has advantages as a first example.

  • It’s small enough that you can see all the objects and arrows on the screen at once, but big enough not to be trivial.
  • The objects and arrows have no properties other than being objects and arrows. (The other examples involve familiar math objects.)
  • So in order to check that $\mathsf{MyFin}$ really obeys the axioms for a category, you can use only the skeletal information given here. As a result, you must really understand the axioms!

A correct proof will be based on axioms and theorems. The proof can be suggested by your intuitions, but intuitions are not enough. When working with $\mathsf{MyFin}$ you won’t have any intuitions!

A diagram for $\mathsf{MyFin}$

This diagram gives a partial description of $\mathsf{MyFin}$.

Now let’s see how to make the diagram above into a category.

Axiom 1

  • The objects of $\mathsf{MyFin}$ are $A$, $B$, $C$ and $D$.
  • The arrows are $f$, $g$, $h$, $j$, $k$, $r$, $s$, $u$, $v$, $w$ and $x$.
  • You can regard the letters just listed as names of the objects and arrows. The point is that at this stage all you know about the objects and arrows are their names.
  • If you prefer, you can think of the arrows as the actual arrows shown in the $\mathsf{MyFin}$ diagram.
  • Our definition of $\mathsf{MyFin}$ is an abstract definition. You may have seen multiplication tables of groups given in terms of undefined letters. (If you haven’t, don’t worry.) Those are also abstract definitions.
  • Most of our other definitions of categories involve math objects you actually know something about. They are like the definition of division, for example, where the math objects are integers.

Axiom 2

  • The domains and codomains of the arrows are shown by the diagram above.
  • For example, $\text{dom}(r)=A$ and $\text{cod}(r)=C$, and $\text{dom}(v)=\text{cod}(v)=B$.

Axiom 3

Showing the $\mathsf{MyFin}$ diagram does not completely define $\mathsf{MyFin}$. We must say what the composites of all the paths of length 2 are.

  • In fact, most of them are forced, but two of them are not.
  • We must have $g\circ f=r$ because $r$ is the only arrow possible for the composite, and Axiom 3 requires that every path of length 2 must have a composite.
  • For the same reason, $h\circ g=s$.
  • All the paths involving $u$, $v$, $w$ and $x$ are forced:

  • (p1) $u\circ u=u$, $v\circ v=v$, $w\circ w=w$ and $x\circ x=x$.
  • (p2) $f\circ u=f$, $r\circ u=r$, $j\circ u=j$ and $k\circ u=k$. You can see that, for example, $f\circ u=f$ by opening up the loop on $f$ like this:

    There is only one arrow going from $A$ to $B$, namely$f$, so $f$ has to be the composite $f\circ u$.

  • (p3) $v\circ f=f$, $g\circ v=g$ and $s\circ v=s$.
  • (p4) $w\circ g=g$, $w\circ r=r$ and $h\circ w=h$.
  • (p5) $x\circ h=h$, $x\circ s=s$, $x\circ j=j$ and $x\circ k=k$.

  • For $s\circ f$ and $h\circ r$, we have to choose between $j$ and $k$ as composites. Since $s\circ f=(h\circ g)\circ f$ and $h\circ r=h\circ (g\circ f)$, Axiom 3 requires that we must chose one of $j$ and $k$ to be both composites.

    Definition: $s\circ f=h\circ r=j$.

    If we had defined $s\circ f=h\circ r=k$ we would have a different category, although one that is “isomorphic” to $\mathsf{MyFin}$ (you have to define “isomorphic” or look it up.)

    • Axiom 4

    • It is clear from the $\mathsf{MyFin}$ diagram that for each object there is just one arrow that has that object both as domain and as codomain, as required by Axiom 4a.
    • The requirements in Axiom 4b and 4c are satisfied by statements (p1) through (p5).

    Axiom 5

    • Since we have already required both $(h\circ g)\circ f$ and $h\circ(g\circ f)$ to be $k$, composition is associative.

    Example 2: Set

    To be written.

    This will be a very different example, because it involves known mathematical objects — sets and functions. But there are still issues, for example the fact that the inclusion of $\{1,2\}$ into $\{1,2,3\}$ and the identity map on $\{1,2\}$ are two different arows in the category of sets.

    Example 3: IntegerDiv

    To be written.

    The objects are all the positive integers and there is an arrow from $m$ to $n$ if and only if $m$ divides $n$. So this example involves familiar objects and predicates, but the arrows are nevertheless not functions that take elements to elements. Integers don’t have elements. I would expect to show how the GCD of two integers is a limit.

    References

      Creative Commons License

    This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.

    Send to Kindle
    abstracting algebra, category theory, exposition, language of math, math, understanding math

    Presenting binary operations

    Leave a comment

    This is the first of a set of notes I am writing to help me develop my thoughts about how particular topics in my book Abstracting algebra should be organized. This article describes my plan for the book in some detail. The present post has some thoughts about presenting binary operations.

    Before binary operations are introduced

    Traditionally, an abstract algebra book assumes that the student is familiar with high school algebra and will then proceed with an observation that such operations as $+$ and $\times$ can be thought of as functions of two variables that take a number to another number. So the first abstract idea is typically the concept of binary operation, although in another post I will consider whether that really should be the first abstract concept.

    The Abstracting Algebra book will have a chapter that presents concrete examples of algebraic operations and expressions on numbers as in elementary school and as in high school algebra. This section of the post outlines what should be presented there. Each subsection needs to be expanded with lots of examples.

    In elementary school

    In elementary school you see expressions such as

    • $3+4$
    • $3\times 4$
    • $3-4$

    The student invariably thinks of these expressions as commands to calculate the value given by the expression.

    They will also see expressions such as
    \[\begin{equation}
    \begin{array}[b]{r}
    23\\
    355\\
    + 96\\
    \hline
    \end{array}
    \end{equation}\]
    which they will take as a command to calculate the sum of the whole list:
    \[\begin{equation}
    \begin{array}[b]{r}
    23\\
    355\\
    + 96\\
    \hline
    474
    \end{array}
    \end{equation}\]

    That uses the fact that addition is associative, and the format suggests using the standard school algorithm for adding up lists. You don’t usually see the same format with more than two numbers for multiplication, even though it is associative as well. In some elementary schools in recent years students are learning other ways of doing arithmetic and in particular are encouraged to figure out short cuts for problems that allow them. But the context is always “do it”, not “this represents a number”.

    Algebra

    In algebra you start using letters for numbers. In algebra, “$a\times b$” and “$a+b$” are expressions in the symbolic language of math, which means they are like noun phrases in English such as “My friend” and “The car I bought last week and immediately totaled” in that both are used semantically as names of objects. English and the symbolic language are both languages, but the symbolic language is not a natural language, nor is it a formal language.

    Example

    In beginning algebra, we say “$3+5=8$”, which is a (true) statement.

    Basic facts about this equation:

    The expressions “$3+5$” and “$8$”

    • are not the same expression
    • but in the standard semantics of algebra they have the same meaning
    • and therefore the equation communicates information that neither “$3+5$” nor “$8$” communicate.

    Another example is “$3+5=6+2$”.

    Facts like this example need to be communicated explicitly before binary operations are introduced formally. The students in a college abstract algebra class probably know the meaning of an equation operationally (subconsciously) but they have never seen it made explicit. See Algebra is a difficult foreign language.

    Note

    The equation “$3+5=6+2$” is an expression just as much as “$3+5$” and “$6+2$” are. It denotes an object of type “equation”, which is a mathematical object in the same way as numbers are. Most mathematicians do not talk this way, but they should.

    Binary operations

    Early examples

    Consciousness-expanding examples should appear early and often after binary operations are introduced.

    Common operations

    • The GCD is a binary operation on the natural numbers. This disturbs some students because it is not written in infix form. It is associative. The GCD can be defined conceptually, but for computation purposes needs (Euclid’s) algorithm. This gives you an early example of conceptual definitions and algorithms.
    • The maximum function is another example of this sort. This is a good place to point out that a binary operation with the “same” definition cen be defined on different sets. The max function on the natural numbers does not have quite the same conceptual definition as the max on the integers.

    Extensional definitions

    In order to emphasize the arbitrariness of definitions, some random operations on a small finite sets should be given by a multiplication table, on sets of numbers and sets represented by letters of the alphabet. This will elicit the common reaction, “What operation is it?” Hidden behind this question is the fact that you are giving an extensional definition instead of a formula — an algorithm or a combination of familiar operations.

    Properties

    The associative and commutative properties should be introduced early just for consciousness-raising. Subtraction is not associative or commutative. Rock paper scissors is commutative but not associative. Groups of symmetries are associative but not commutative.

    Binary operation as function

    The first definition of binary operation should be as a function. For example, “$+$” is a function that takes pairs of numbers to numbers. In other words, $+:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ is a function.

    We then abstract from that example and others like it from specific operations to arbitrary functions $\Delta:S\times S\to S$ for arbitrary sets $S$.

    This is abstraction twice.

    • First we replace the example operations by an arbitrary operation. such as multiplication, subtraction, GCD and MAX on $\mathbb{Z}$, or something complicated such as \[(x,y)\mapsto 3(xy-1)^2(x^2+xy^3)^3\].
    • Then we replace sets of numbers by arbitrary sets. An example would be the random multiplication on the set $\{1,2,5\}$ given by the table
      \[
      \begin{array}{c|ccc}
      \Delta& 1&2&5\\
      \hline
      1&2&2&1\\
      2&5&2&1\\
      5&2&1&5
      \end{array}
      \]
      This defines a function $\Delta:\{1,2,5\}\times\{1,2,5\}\to\{1,2,5\}$ for which for example $\Delta(2,1)=5$, or $2\Delta 1=5$. This example uses numbers as elements of the set and is good for eliciting the “What operation is it?” question.
    • I will use examples where the elements are letters of the alphabet, as well. That sort of example makes the students think the letters are variables they can substitute for, another confusion to be banished by the wise professor who know the right thing to say to make it clear. (Don’t ask me; I taught algebra for 35 years and I still don’t know the right thing to say.)

    It is important to define prefix notation and infix notation right away and to use both of them in examples.

    Other representations of binary operations.

    The main way of representing binary operations in Abstracting Algebra will be as trees, which I will cover in later posts. Those posts will be much more interesting than this one.

    Binary operations in high school and college algebra

    • Some binops are represented in infix notation: “$a+b$”, “$a-b$”, and “$a\times b$”.
    • “$a\times b$” is usually written “$ab$” for letters and with the “$\times$” symbol for numbers.
    • Some binops have idiosyncratic representation: “$a^b$”, “${a}\choose{b}$”.
    • A lot of binops such as GCD and MAX are given as functions of two variables (prefix notation) and their status as binary operations usually goes unmentioned. (That is not necessarily wrong.)
    • The symbol “$(a,b)$” is used to denote the GCD (a binop) and is also used to denote a point in the plane or an open interval, both of which are not strictly binops. They are binary operations in a multisorted algebra (a concept I expect to introduce later in the book.)
    • Some apparent binops are in infix notation but have flaws: In “$a/b$”, the second entry can’t be $0$, and the expression when $a$ and $b$ are integers is often treated as having good forms ($3/4$) and bad forms ($6/8$).

    Trees

    The chaotic nature of algebraic notation I just described is a stumbling block, but not the primary reason high school algebra is a stumbling block for many students. The big reason it is hard is that the notation requires students to create and hold complicated abstract structures in their head.

    Example

    This example is a teaser for future posts on using trees to represent binary operations. The tree below shows much more of the structure of a calculation of the area of a rectangle surmounted by a semicircle than the expression

    \[A=wh+\frac{1}{2}\left(\pi(\frac{1}{2}w)^2\right)\]
    does.

    The tree explicitly embodies the thought process that leads to the formula:

    • You need to add the area of the rectangle and the area of the semicircle.
    • The area of the rectangle is width times height.
    • The area of the semicircle is $\frac{1}{2}(\pi r^2)$.
    • In this case, $r=\frac{1}{2}w$.

    Any mathematician will extract the same abstract structure from the formula\[A=wh+\frac{1}{2}\left(\pi(\frac{1}{2}w)^2\right)\] This is difficult for students beginning algebra.

    References

    Creative Commons License

    This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.


    Send to Kindle
    abstractmath.org, exposition, language of math, math, representations, understanding math

    The definition of “function”

    1 Comment

     

    This is the new version of the abstractmath article on the definition of function. I had to adapt the formatting and some of it looks weird, but legible. It is prettier on abstractmath.org.

    I expect to announce new revisions of other abmath articles on this blog, with links, but not to publish them here. This article brings out a new point of view about defining functions that I wanted to call attention to, so I am publishing it here, as well.

     

    FUNCTIONS: SPECIFICATION AND DEFINITION

    It is essential that you understand many of the images, metaphors and terminology that mathe­maticians use when they think and talk about functions. For many purposes, the precise mathematical definition of "function" does not play much of a role when you are trying to understand particular kinds of functions. But there is one point of view about functions that has resulted in fundamental progress in math:

     

     

    A function is a mathematical object.

    To deal with functions in that way you need a precise definition of "function". That is what this article gives you.

    • The article starts by giving a specification of "function".
    • After that, we get into the technicalities of the definitions of the general concept of function.
    • Things get complicated because there are several inequivalent definitions of "function" in common use.

    Specification of "function"

    A function $f$ is a mathematical object which determines and is completely determined by the following data:

    (DOM) $f$ has a domain, which is a set. The domain may be denoted by $\text{dom} f$.

    (COD) $f$ has a codomain, which is also a set and may be denoted by $\text{cod} f$.

    (VAL) For each element $a$ of the domain of $f$, $f$ has a value at $a$, denoted by $f(a)$.

    (FP) The value of $f$ at $a$ is completely determined by $a$ and $f$.

    (VIC) The value of $f$ at $a$ must be an element of the codomain of $f$.

    • The operation of finding $f(a)$ given $f$ and $a$ is called evaluation.
    • "FP" means functional property.
    • "VIC" means "value in codomain".

    Examples

    The examples of functions chapter contains many examples. The two I give here provide immediate examples.

    A finite function

    Let $F$ be the function defined on the set $\left\{1,\,2,3,6 \right\}$ as follows: $F(1)=3,\,\,\,F(2)=3,\,\,\,F(3)=2,\,\,\,F(6)=1$. This is the function called "Finite'' in the chapter on examples of functions.

    • The definition of $F$ says "$F$ is defined on the set $\left\{1,\,2,\,3,\,6 \right\}$". That phrase means that the domain is that set.
    • The value of $F$ at each element of the domain is given explicitly. The value at 3, for example, is 2, because the definition says that $F(2) = 3$. No other reason needs to be given. Mathematical definitions can be arbitrary.
    • The codomain of $F$ is not specified, but must include the set $\{1,2,3\}$. The codomain of a function is often not specified when it is not important — which is most of the time in freshman calculus (for example).

    A real-valued function

    Let $G$ be the real-valued function defined by the formula $G(x)={{x}^{2}}+2x+5$.

    • The definition of $G$ gives the value at each element of the domain by a formula. The value at $3$, for example, is $G(3)=3^2+2\cdot3+5=20$.
    • The definition of $G$ does not specify the domain. The convention in the case of functions defined on the real numbers by a formula is to take the domain to be all real numbers at which the formula is defined. In this case, that is every real number, so the domain is $\mathbb{R}$.
    • The definition does not specify the codomain, either. However, must include all real numbers greater than or equal to 4. (Why?)

    What the specification means

    • The specification guarantees that a function satisfies all five of the properties listed.
    • The specification does not define a mathematical structure in the way mathematical structures have been defined in the past: In particular, it does not require a function to be one or more sets with structure.
    • Even so, it is useful to have the specification, because:

       

       

      Many mathematical definitions
      introduce extraneous technical elements
      which clutter up your thinking
      about the object they define.

       

       

      I will say more about this when I give the various definitions that are in use.

    History

    Until late in the nineteenth century, functions were usually thought of as defined by formulas (including infinite series). Problems arose in the theory of harmonic analysis which made mathematicians require a more general notion of function. They came up with the concept of function as a set of ordered pairs with the functional property (discussed below), and that understanding revolutionized our understanding of math.

    This discussion is an over­simpli­fication of the history of mathe­matics, which many people have written thick books about. A book relevant to these ideas is Plato's Ghost, by Jeremy Gray.

    In particular, this definition, along with the use of set theory, enabled abstract math (ahem) to become a common tool for understanding math and proving theorems. It is conceivable that some of you may wish it hadn't. Well, tough.

    The more modern definition of function given here (which builds on the older definition) came into use beginning in the 1950's. The strict version became necessary in algebraic topology and is widely used in many fields today.

    The concept of function as a formula never disappeared entirely, but was studied mostly by logicians who generalized it to the study of function-as-algorithm. Of course, the study of algorithms is one of the central topics of modern computing science, so the notion of function-as-formula (updated to function-as-algorithm) has achieved a new importance in recent years.

    To state both the old abstract definition and the modern one, we need a preliminary idea.

    The functional property

    A set $P$ of ordered pairs has the functional property if two pairs in $P$ with the same first coordinate have to have the same second coordinate (which means they are the same pair). In other words, if $(x,a)$ and $(x,b)$ are both in $P$, then $a=b$.

    How to think about the functional property

    The point of the functional property is that for any pair in the set of ordered pairs, the first coordinate determines what the second one is. That's why you can write "$G(x)$'' for any $x $ in the domain of $G$ and not be ambiguous.

    Examples

    • The set $\{(1,2), (2,4), (3,2), (5,8)\}$ has the functional property, since no two different pairs have the same first coordinate. Note that there are two different pairs with the same second coordinate. This is irrelevant to the functional property.
    • The set $\{(1,2), (2,4), (3,2), (2,8)\}$ does not have the functional property. There are two different pairs with first coordinate 2.
    • The empty set $\emptyset$ has the function property vacuously.

    Graph of a function.

    Example: graph of a function defined by a formula

    In calculus books, a picture like this one (of part of $y=x^2+2x+5$) is called a graph. Here I use the word "graph" to denote the set of ordered pairs \[\left\{ (x,{{x}^{2}}+2x+5)\,\mathsf{|}\,x\in \mathbb{R } \right\}\] which is a mathematical object rather than some ink on a page or pixels on a screen.

    The graph of any function studied in beginning calculus has the functional property. For example, the set of ordered pairs above has the functional property because if $x$ is any real number, the formula ${{x}^{2}}+2x+5$ defines a specific real number.

    • if $x = 0$, then ${{x}^{2}}+2x+5=5$, so the pair $(0, 5)$ is an element of the graph of $G$. Each time you plug in $0$ in the formula you get 5.
    • if $x = 1$, then ${{x}^{2}}+2x+5=8$.
    • if $x = -2$, then ${{x}^{2}}+2x+5=5$.

    You can measure where the point $\{-2,5\}$ is on the (picture of) the graph and see that it is on the blue curve as it should be. No other pair whose first coordinate is $-2$ is in the graph of $G$, only $(-2, 5)$. That is because when you plug $-2$ into the formula ${{x}^{2}}+2x+5$, you get $5$ and nothing else. Of course, $(0, 5)$ is in the graph, but that does not contradict the functional property. $(0, 5)$ and $(-2, 5)$ have the same second coordinate, but that is OK.

    Modern mathematical definition of function

    A function $f$ is a mathematical structure consisting of the following objects:

    • A set called the domain of $f$, denoted by $\text{dom} f$.
    • A set called the codomain of $f$, denoted by $\text{cod} f$.
    • A set of ordered pairs called the graph of $ f$, with the following properties:
    • $\text{dom} f$ is the set of all first coordinates of pairs in the graph of $f$.
    • Every second coordinate of a pair in the graph of $f$ is in $\text{cod} f$ (but $\text{cod} f$ may contain other elements).
    • The graph of $f$ has the functional property.

    Using arrow notation, this implies that $f:A\to B$.

    Remark

    The main difference between the specification of function given previously and this definition is that the definition replaces the statement "$f$ has a value at $a$" by introducing a set of ordered pairs (the graph) with the functional property.

    • This set of ordered pairs is extra structure introduced by the definition mainly in order to make the definition a classical sets-with-structure, which makes the graph, which should be a concept derived from the concept of function, into an apparently necessary part of the function.
    • That suggests incorrectly that the graph is more of a primary intuition that other intuitions such as function as relocator, function as transformer, and other points of view discussed in the article Intuitions and metaphors for functions.

    Examples

    • Let $F$ have graph $\{(1,2), (2,4), (3,2), (5,8)\}$ and define $A = \{1, 2, 3, 5\}$ and $B = \{2, 4, 8\}$. Then $F:A\to B$ is a function. In speaking, we would usually say, "$F$ is a function from $A$ to $B$."
    • Let $G$ have graph $\{(1,2), (2,4), (3,2), (5,8)\}$ (same as above), and define $A = \{1, 2, 3, 5\}$ and $C = \{2, 4, 8, 9, 11, \pi, 3/2\}$. Then $G:A\to C$ is a (admittedly ridiculous) function. Note that all the second coordinates of the graph are in $C$, along with a bunch of miscellaneous suspicious characters that are not second coordinates of pairs in the graph.
    • Let $H$ have graph $\{(1,2), (2,4), (3,2), (5,8)\}$. Then $H:A\to \mathbb{R}$ is a function, since $2$, $4$ and $8$ are all real numbers.
    • Let $D = \{1, 2, 5\}$ and $E = \{1, 2, 3, 4, 5\}$. Then there is no function $D\to A$ and no function $E\to A$ with graph $\{(1,2), (2,4), (3,2), (5,8)\}$. Neither $D$ nor $E$ has exactly the same elements as the first coordinates of the graph.

    Identity and inclusion

    Suppose we have two sets  A and  B with $A\subseteq B$.

    • The identity function on A is the function ${{\operatorname{id}}_{A}}:A\to A$ defined by ${{\operatorname{id}}_{A}}(x)=x$ for all $x\in A$. (Many authors call it ${{1}_{A}}$).
    • When $A\subseteq B$, the inclusion function from $A$ to $B$ is the function $i:A\to B$ defined by $i(x)=x$ for all $x\in A$. Note that there is a different function for each pair of sets $A$ and $B$ for which $A\subseteq B$. Some authors call it ${{i}_{A,\,B}}$ or $\text{in}{{\text{c}}_{A,\,B}}$.

    The identity function and an inclusion function for the same set $A$ have exactly the same graph, namely $\left\{ (a,a)|a\in A \right\}$. More about this below.

    Other definitions of function

    Original abstract definition of function

    Definition

    Remarks

    Possible confusion

    Some confusion can result because of the presence of these two different definitions.

    Multivalued function

    Some older mathematical papers in com­plex func­tion theory do not tell you that their functions are multi­valued. There was a time when com­plex func­tion theory was such a Big Deal in research mathe­matics that the phrase "func­tion theory" meant complex func­tion theory and all the cogno­scenti knew that their functions were multi­valued.

    The phrase multivalued function refers to an object that is like a function $f:S\to T$ except that for $s\in S$, $f(s)$ may denote more than one value.

    Examples

    • Multivalued functions arose in considering complex functions. In common practice, the symbol $\sqrt{4}$ denoted $2$, although $-2$ is also a square root of $4$. But in complex function theory, the square root function takes on both the values $2$ and $-2$. This is discussed in detail in Wikipedia.
    • The antiderivative is an example of a multivalued operator. For any constant $C$, $\frac{x^3}{3}+C$ is an antiderivative of $x^2$.

    A multivalued function $f:S\to T$ can be modeled as a function with domain $S$ and codomain the set of all subsets of $T$. The two meanings are equivalent in a strong sense (naturally equivalent}). Even so, it seems to me that they represent two differ­ent ways of thinking about multivalued functions. ("The value may be any of these things…" as opposed to "The value is this whole set of things.")

    The phrases "multivalued function" and "partial function" upset some picky types who say things like, "But a multi­valued func­tion is not a func­tion!". A step­mother is not a mother, either. See the Hand­book article on radial category.

    Partial function

    A partial function $f:S\to T$ is just like a function except that its input may be defined on only a subset of $S$. For example, the function $f(x)=\frac{1}{x}$ is a partial function from the real numbers to the real numbers.

    This models the behavior of computer programs (algorithms): if you consider a program with one input and one output as a function, it may not be defined on some inputs because for them it runs forever (or gives an error message).

    In some texts in computing science and mathematical logic, a function is by convention a partial function, and this fact may not be mentioned explicitly, especially in research papers.

    New approaches to functions

    All the definitions of function given here produce mathematical structures, using the traditional way to define mathematical objects in terms of sets. Such definitions have disadvantages.

    Mathematicians have many ways to think about functions. That a function is a set of ordered pairs with a certain property (functional) and possibly some ancillary ideas (domain, codomain, and others) is not the way we usually think about them$\ldots$Except when we need to reduce the thing we are studying to its absolutely most abstract form to make sure our proofs are correct. That most abstract form is what I have called the rigorous view or the dry bones and it is when that reasoning is needed that the sets-with-structure approach has succeeded.

    Our practice of abstraction has led us to new approaches to talking about functions. The most important one currently is category theory. Roughly, a category is a bunch of objects together with some arrows going between them that can be composed head to tail. Functions between sets are examples of this: the sets are the objects and the functions the arrows.

    This abstracts the idea of function in a way that brings out common ideas in various branches of math. Research papers in many branches of mathematics now routinely use the language of category theory. Categories now appear in some undergraduate math courses, meaning that Someone needs to write a chapter on category theory for abstractmath.org.

    Besides category theory, computing scientists have come up with other abstract ways of dealing with functions, for example type theory. It has not come as far along as category theory, but has shown recent signs of major progress.

    Both category theory and type theory define math objects in terms of their effect on and relationship with other math objects. This makes it possible to do abstract math entirely without using sets-with-structure as a means of defining concepts.

     

    Send to Kindle