Category Archives: category theory

Definition of function

Note: This is a revision of the article on specification and definition of functions from abstractmath.org. Many of the links in this article take you to other articles in abstractmath.org.

A function is a mathematical object.

To deal with functions as a math object, 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$.
  • (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 value of $f$ at $a$ is most cohttp://www.abstractmath.org/MM/MMonly written $f(a)$, but see Functions: Notation and Terminology.
  • To evaluate $f$ at $a$ means to determine $f(a)$. The two examples of functions below show that different functions may have different strategies for evaluating them.
  • In the expression “$f(a)$”, $a$ is called the input or (old-fashioned) argument of $f$.
  • “FP” means functional property.
  • “VIC” means “value in codomain”.

Examples

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

A finite function

Let $F$ be the function defined on the set $\left\{\text{a},\text{b},\text{c},\text{d}\right\}$ as follows: \[F(\text{a})=\text{a},\,\,\,F(\text{b})=\text{c},\,\,\,F(\text{c})=\text{c},\,\,\,F(\text{d})=\text{b}\]In this definition, $\text{a},\text{b},\text{c},\text{d}$ are letters of the alphabet, not variables. 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\{\text{a},\,\text{b},\,\text{c},\,\text{d} \right\}$”. The phrase “is defined on”
    means that the domain is that set. That is standard terminology.
  • The value of $F$ at each element of the domain is given explicitly. The value at
    $\text{b}$, for example, is $\text{c}$, because the definition says that $F(\text{b}) = \text{c}$. No other reason needs to be given. Mathematical definitions can be arbitrary.
  • The codomain of $F$ is not specified, but must include the set $\{\text{a},\text{b},\text{c}\}$. 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).
  • The diagram below shows how $F$ obeys the rule that the value of an element $x$ in the domain is completely determined by $x$ and $F$.
  • If two arrows had started from the same element of the domain, then $F$ would not be a function. (It would be a multivalued function).
  • If there were an element of the domain that no arrow started from, it $F$ would not be a function. (It would be a partial function.)
  • In this example, to evaluate $F$ at $b$ (to determine the value of $F$ at $b$) means to look at the definition of $F$, which says among other things that the value is $c$ (or alternatively, look at the diagram above and see what letter the arrow starting at $b$ points to). In this case, “evaluation” does not imply calculating a formula.

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 obtained by calculating \[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 of $G$ does not specify the codomain, either. However, the codomain must include all real numbers greater than or equal to $4$. (Why?)
  • So if an author wrote, “Let $H(x)=\frac{1}{x}$”, the domain would be the set of all real numbers except $0$. But a careful author would write, “Let $H(x)=\frac{1}{x}$ ($x\neq0$).”

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.

History

The discussion below 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.

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.

In particular, this definition, along with the use of set theory, enabled abstract math (ahem) to become a cohttp://www.abstractmath.org/MM/MMon tool for understanding math and proving theorems. It is conceivable that some readers may wish it hadn’t. Well, tough.

The modern definition of function given here (which builds on the ordered pairs with functional property definition) came into use beginning in the 1950’s. The modern definition 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 definition, 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 (which is just what requirement FP says in the specification). 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.

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.



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$ \text{dom} fis 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:\text{dom}f\to\text{cod} f$.

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.
  • This makes the graph, which should be a concept derived from the concept of function, appear to be a necessary part of the function.
  • That suggests incorrectly that the graph is more of a primary intuition that other intuitions such as function as map, function as transformer, and other points of view discussed in the article Images and meta­phors for functions.
  • The concept of graph of a function is indeed an important intuition, and is discussed with examples in the articles Graphs of continuous functions and Graphs of finite functions.
  • Nevertheless, the fact that the concept of graph appears in the definition of function does not make it the most important intuition.

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 the codomain $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

  • A function $f$ is a set of ordered pairs with the functional property.
  • If $f$ is a function according to this definition, the domain of $f$ is the set of first coordinates of all the pairs in $f$.
  • If $x\in \text{dom} f$, then we define the value of $f$ at $x$, denoted by $f(x)$, to be the second coordinate of the only ordered pair in $f$ whose first coordinate is $x$.

Remarks

  • This definition is still widely used in mathematical writing.
  • Many authors do not tell you which definition they are using.
  • For many purposes (including freshman calculus for the most part) it does not matter which definition is used.
  • In some branches of math, the modern definition adds great clarity to many complicated situations; using the older definition can even make it difficult to describe some important constructions. There is more about this in New Approaches below.

Possible confusion

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

  • For example, since the identity function ${{\operatorname{id}}_{A}}:A\to A$ and the inclusion function ${{i}_{A,\,B}}:A\to B$ have the same graph, users of the older definition are required in theory to say they are the same function.
  • Also it requires you to say that the graph of a function is the same thing as the function.
  • In my observation, this does not make a problem in practice, unless there is a very picky person in the room.
  • It also appears to me that the modern definition is (quite rightly) winning and the original abstract definition is disappearing.

Multivalued function

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 cohttp://www.abstractmath.org/MM/MMon 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$, so that $\frac{x^3}{3}$, $\frac{x^3}{3}+42$, $\frac{x^3}{3}-1$ and $\frac{x^3}{3}+2\pi$ are among the infinitely many antiderivatives 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.”)

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 every mathe­ma­tician with a Ph. D. knew that complex functions were multi­valued.

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.

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 hot dog is not a dog, either. I once had a Russian teacher who was Polish and a German teacher who was Hungarian. So what? See the Hand­book (click on
radial category).

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. But arrows in a category do not have to be functions; in that way category theory is an abstraction of functions.

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.

References

  • Functions in Wikipedia. This is an extensive and mostly well-done description of the use of functions in mathematics.

Creative Commons License

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

Send to Kindle

A slow introduction to category theory

Category theory turns math inside-out. Definitions depend on nothing inside, but on everything outside. — John Cook

About this post

This is a draft of the first part of an article on category theory that will be posted on abstractmath.org. It replaces an earlier version that was posted in June, 2016.

During the last year or so, I have been monitoring the category theory questions on Math Stack Exchange. Some of the queries are clearly from people who do not have enough of a mathematical background to understand basic abstract reasoning, for example the importance of definitions and the difficulties described in the abmath artice on Dysfunctional attitudes and behaviors. Category theory has become important in several fields outside mathematics, for example computer science and database theory.

This article is intended to get people started in category theory by giving a very detailed definition of “category” and some examples described in detail with an emphasis on how the example fits the definition of category. That’s all the present version does, but I intend to add some examples of constructions and properties such as the dual category, product, and other concepts that some of the inquirers on Math Stack Exchange had great difficulty with.

There is no way in which this article is a proper introduction to category theory. It is intended only to give beginners some help over the initial steps of understanding the subject, particularly the aspects of understanding that cause many hopeful math majors to fall off the Abstraction Cliff.

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 introduce several example categories with a detailed discussion of each one, explaining how they fit the definition of category.


Axiom 1: Data

A category consists of two types of data: objects and arrows.

Notes for Axiom 1

  • You will see in the section on Examples of categories that every definition of a category $\mathsf{C}$ starts by specifying what the objects of $\mathsf{C}$ are and what the arrows of $\mathsf{C}$ are. That is what Axiom I requires.
  • 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

Each arrow of a category has a domain and a codomain, each of which is an object of the category.

Notes for Axiom 2

  • The domain and the codomain of an arrow may or may not be the same object.
  • Each arrow has only one domain and only one codomain.
  • 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:
  • Warning: 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 an arrow $f:A\to B$, 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

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

  • 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$.

  • It is useful to think of $f$ followed by $g$ as a path in the diagram. Then a metaphor for composition is: Every path of length 2 has exactly one composite.
  • It is customary in some texts in category theory to indicate that a diagram commutes by putting a gyre in the middle:
  • Note that the composite of the path that I described as “$f$ followed by $g$” is written as “$g\circ f$” or “$gf$”, which seems backward. Nevertheless, the most common notation in category theory for the composite of “$f$ followed by $g$” is $gf$. Some authors in computer science write “$f;g$” for “$gf$” to get around this problem.
  • 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

Note: WordpPress does not recognize the html command

    . Axiom 1 should be 4a, Axiom 2 4b Axiom 3 4c and Axiom 4 4d.

  1. For each object $A$ of a category, there is an arrow denoted by $\mathsf{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\]
  • There may be many arrows with domain and codomain both equal to $A$ (for example in the category $\mathsf{Set}$), but only one of them is $\textsf{id}_A$. It can be proved that $\textsf{id}_A$ is the unique arrow satisfying both (c) and (d) of the axiom.

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 $D$ 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 algebraic notation 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 these examples, I 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 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. (Some of 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: Data

  • 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.
  • Our other definitions of categories involve math objects you actually know something about.

Axiom 2: Domain and Codomain

  • 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: Composition

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: Identity arrows

Axiom 5: Associativity

  • 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: IntegerDiv

  • This example uses familiar mathematical objects — positive integers.
  • The arrows are not functions that can be applied to elements, since integers do not have elements.

Axiom 1: Data

  • The objects of IntegerDiv are all the positive integers.
  • Suppose $m$ and $n$ are positive integers:
  • If $m$ divides $n$, there is exactly one arrow from $m$ to $n$. I will call this arrow $\textsf{mdn}$. (This is my notation. There is no standard notation for this category.) For example there is one arrow from $2$ to $6$, denoted by $\textsf{2d6}$.
  • If $m$ does not divide $n$, there is no arrow from $m$ to $n$.

Axiom 2: Domain and codomain

The arrow denoted by $\textsf{mdn}$ has domain $m$ and codomain $n$.

Example

Example

Example

which may also be shown as

Axiom 3: Composition

The composite of

must be $\textsf{rdt}$, since that is the only arrow with domain $r$ and codomain $t$.

This fact can also be written this way: \[\mathsf{sdt}\circ\textsf{rds}=\textsf{rdt}\]

Axiom 4: Identity arrows

The composites

and

must commute since the arrows shown are the only possible arrows with the domains and codomains shown. In other words, $\textsf{id}_\textsf{r}=\textsf{rdr}$ and $\textsf{id}_\textsf{s}=\textsf{sds}$.

Axiom 5: Associativity

In the diagram below,

there is only one arrow from one integer to another, so $\textsf{k}$ must be both \[\textsf{tdu}\circ(\textsf{sdt}\circ\textsf{rds})\] and \[(\textsf{tdu}\circ\textsf{sdt})\circ\textsf{rds}\] as required.

Example 3: The category of Sets

In this section, I define the category $\mathsf{Set}$ (that is standard terminology in category theory.) This example will be very different from $\mathsf{MyFin}$, because it involves known mathematical objects — sets and functions.

Axiom 1: Data

  • Every set is an object of $\mathsf{Set}$ and nothing else is.
  • Every function between sets is an arrow of $\mathsf{Set}$ and nothing else is an arrow of $\mathsf{Set}$.

Axiom 2: Domain and codomain

For a given function $f$, $\text{dom}(f)$ is the domain of the function $f$ in the usual sense, and $\text{cod}(f)$ is the codomain of $f$ in the usual sense. (See Functions: specification and definition for more about domain and codomain.)

Examples

  • Let $f:\mathbb{R}\to\mathbb{R}$ be the function defined by $f(x):=x^2$. Then the arrow $f$ in $\mathsf{Set}$ satisfies $\text{dom}(f)= \mathbb{R}$ and also $\text{cod}(f)=\mathbb{R}$.
  • Let $j:\{1,2,3\}\to\{1,2,3,4\}$ be defined by $j(1):=1$, $j(2):=4$ and $j(3):=3$. Then $\text{dom}(j)=\{1,2,3\}$ and $\text{cod}(j)=\{1,2,3,4\}$.

Axiom 3: Composition

The composite of $f:A\to B$ and $g:B\to C$ is the function $g\circ f:A\to C$ defined by \[\text{(DC)}\,\,\,\,\,\,\,\,\,\,(g\circ f)(a):=g(f(a))\]

Note

Many other categories have a similar definition of composition, including categories whose objects are math structures with underlying sets and whose arrows are structure-preserving functions between the underlying sets. But be warned: There are many useful categories whose arrows do not evaluate at an element of an object because the objects don’t have elements. In that case, (DC) is meaningless. This is true of $\mathsf{MyFin}$ and $\mathsf{IntegerDiv}$.

Axiom 4: Identity arrows

For a set $A$, the identity arrow $\textsf{id}_A:A\to A$ is, as you might expect, the identity function defined by $\textsf{id}_A(a)=a$ for every $a\in A$. We must prove that these diagrams commute:

The calculations below show that they commute. They use the definition of composite given by (DC).

  • For any $b\in B$, \[(\textsf{id}_A\circ f)(b)=\textsf{id}_A(f(b))=f(b)\]
  • For any $a\in A$, \[(g\circ \textsf{id}_A)(a)=g(\textsf{id}_A(a))=g(a)\]

Note: In $\mathsf{Set}$, there are generally many arrows from a particular set $S$ to itself (for example there are $4$ from $\{1,2\}$ to itself), but only one is the identity arrow.

Axiom 5: Associativity

Composition of arrows in $\mathsf{Set}$ is associative because function composition is associative. Suppose we have functions as in this diagram:

We must show that the two triangles containing $k$ in this diagram commute:

In algebraic notation, this requires showing that for every element $a\in A$,\[(h\circ(g\circ f))(a))=((h\circ g)\circ f)(a)\]

The calculation below does that. It makes repeated use of Definition (DC) of composition. For any $a\in A$,\[\begin{equation}
\begin{split}
\big(h\circ (g\circ f)\big)(a)
& = h\big((g\circ f)(a)\big) \\
& = h\big(g(f(a))\big) \\
& = (h\circ g)(f(a)) \\
& = \big((h\circ g)\circ f\big)(a)
\end{split}
\end{equation}\]

Example 4: The category of Monoids


  • This definition makes repeated use of the fact that a homomorphism of monoids is a set function. Specifically, if $(S,\Delta)$ and $(T,\nabla)$ are monoids with identities $e_S$ and $e_{T}$, a homomorphism $h:S\to T$ must be a set function that satisfies the following two axioms: \[\text{(ME)}\,\,\,\,\,\,\,\,h(e_S)=e_T\] and for all elements $s, s’$ of $S$, \[\text{(MM)}\,\,\,\,\,\,\,\,h(s\Delta s’)=h(s)\nabla h(s’)\]
  • The category of monoids may be denoted by $\mathsf{Mon}$.

Axiom 1: Data

  • Every monoid is an object of the category of monoids, and nothing else is.
  • If $f$ is a homomorphism of monoids, then $f$ is an arrow of the category of monoids, and nothing else is.

Axiom 2: Domain and codomain

If $(S,\Delta)$ and $(T,\nabla)$ are monoids and $f:(S,\Delta)\to(T,\nabla)$ is a homomorphism of monoids, then the domain of $f$ is $(S,\Delta)$ and the codomain of $f$ is $(T,\nabla)$.

Notes

  • Since $f$ takes elements of the set $S$ to elements of the set $T$, it is also an arrow in the category $\mathsf{Set}$. In general, very few functions from $S$ to $T$ will be monoid homomorphisms from $(S,\Delta)$ to $(T,\nabla)$.
  • Many authors do not distinguish between $f$ regarded as an arrow of $\mathsf{Mon}$ and $f$ regarded as an arrow of $\mathsf{Set}$. Others may write $U(f)$ for the arrow in $\mathsf{Set}$. “$U$” stands for “underlying functor“, also called “forgetful functor”.

Axiom 3: Composition

The composite of

is the composite $g\circ f$ as set functions:

It is necessary to check that $g\circ f$ is a monoid homomorphism. The following calculation shows that it preserves the monoid operation; it makes repeated use of equations (DC) and (MM).

The calculation: For elements $r$ and $r’$ of $R$,\[\begin{align*}
(g\circ f)(r\,{\scriptstyle \square}\, r’)
&=g\left(f(r\, {\scriptstyle \square}\, r’)\right)\,\,\,\,\,\text{(DC)}\\ &=g\left(f(r) {\scriptstyle\, \Delta}\, f(r’)\right)\,\,\,\,\,\text{(MM)}\\
&=g(f(r)){\scriptstyle \,\nabla}\, g(f(r’))\,\,\,\,\text{(MM)}\\
&=(g\circ f)(r){\scriptstyle \,\nabla}\,(g\circ f)(r’)\,\,\,\,\,\text{(DC)}
\end{align*}\]

The fact that $g\circ f$ preserves the identity of the monoid is shown in the next section.

Axiom 4: Identity arrows

For a monoid $(S,\Delta)$, the identity function $\text{id}_S:S\to S$ preserves the monoid operation $\Delta$, because $\text{id}_S(s\Delta s’)=s\Delta s’$ by definition of the identity function, and that is $\text{id}_S(s)\Delta \text{id}_S(s’)$ for the same reason.

The required diagrams below must commute because the set functions commute and, by Axiom 3, the set composition of a monoid homomorphism is a monoid homomorphism.

We also need to show that $g\circ f$ as in

preserves identities. This calculation proves that it does; it uses (DC) and (ME)

\[\begin{align*}
(g\circ f)(\text{id}_R)
&=g(f((\text{id}_R))\\
&=g(\text{id}_S)\\
&=\text{id}_T
\end{align*}\]

Axiom 5: Associativity

The diagram

in the category $\mathsf{Set}$ commutes, so the diagram

must also commute.

References

All these references are available on line.

  Creative Commons License        

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

Send to Kindle

Very early difficulties II

Very early difficulties II

This is the second part of a series of posts about certain difficulties math students have in the very early stages of studying abstract math. The first post, Very early difficulties in studying abstract math, gives some background to the subject and discusses one particular difficulty: Some students do not know that it is worthwhile to try starting a proof by rewriting what is to be proved using the definitions of the terms involved.

Math StackExchange

The website Math StackExchange is open to any questions about math, even very easy ones. It is in contrast with Math OverFlow, which is aimed at professional mathematicians asking questions in their own field.

Math SE contains many examples of the early difficulties discussed in this series of posts, and I recommend to math ed people (not just RUME people, since some abstract math occurs in advanced high school courses) that they might consider reading through questions on Math SE for examples of misunderstanding students have.

There are two caveats:

  • Most questions on Math SE are at a high enough level that they don’t really concern these early difficulties.
  • Many of the questions are so confused that it is hard to pinpoint what is causing the difficulty that the questioner has.

Connotations of English words

The terms(s) defined in a definition are often given ordinary English words as names, and the beginner automatically associates the connotations of the meaning of the English word with the objects defined in the definition.

Infinite cardinals

If $A$ if a finite set, the cardinality of $A$ is simply a natural number (including $0$). If $A$ is a proper subset of another set $B$, then the cardinality of $A$ is strictly less than the cardinality of $B$.

In the nineteenth century, mathematicians extended the definition of cardinality for infinite sets, and for the most part cardinality has the same behavior as for finite sets. For example, the cardinal numbers are well-ordered. However, for infinite sets it is possible for a set and a proper subset of the set to have the same cardinality. For example, the cardinality of the set of natural numbers is the same as the cardinality of the set of rational numbers. This phenomenon causes major cognitive dissonance.

Question 1331680 on Math Stack Exchange shows an example of this confusion. I have also discussed the problem with cardinality in the abstractmath.org section Cardinality.

Morphism in category theory

The concept of category is defined by saying there is a bunch of objects called objects (sorry bout that) and a bunch of objects called morphisms, subject to certain axioms. One requirement is that there are functions from morphisms to objects choosing a “domain” and a “codomain” of each morphism. This is spelled out in Category Theory in Wikibooks, and in any other book on category theory.

The concepts of morphism, domain and codomain in a category are therefore defined by abstract definitions, which means that any property of morphisms and their domains and codomains that is true in every category must follow from the axioms. However, the word “morphism” and the talk about domains and codomains naturally suggests to many students that a morphism must be a function, so they immediately and incorrectly expect to evaluate it at an element of its domain, or to treat it as a function in other ways.

Example

If $\mathcal{C}$ is a category, its opposite category $\mathcal{C}^{op}$ is defined this way:

  • The objects of $\mathcal{C}^{op}$ are the objects of $\mathcal{C}$.
  • A morphism $f:X\to Y$ of $\mathcal{C}^{op}$ is a morphism from $Y$ to $X$ of $\mathcal{C}$ (swap the domain and codomain).

In Question 980933 on Math SE, the questioner is saying (among other things) that in $\text{Set}^{op}$, this would imply that there has to be a morphism from a nonempty set to the empty set. This of course is true, but the questioner is worried that you can’t have a function from a nonempty set to the empty set. That is also true, but what it implies is that in $\text{Set}^{op}$, the morphism from $\{1,2,3\}$ to the empty set is not a function from $\{1,2,3\}$ to the empty set. The morphism exists, but it is not a function. This does not any any sense make the definition of $\text{Set}^{op}$ incorrect.

Student confusion like this tends to make the teacher want to have a one foot by six foot billboard in his classroom saying

A MORPHISM DOESN’T HAVE TO BE A FUNCTION!

However, even that statement causes confusion. The questioner who asked Question 1594658 essentially responded to the statement in purple prose above by assuming a morphism that is “not a function” must have two distinct values at some input!

That questioner is still allowing the connotations of the word “morphism” to lead them to assume something that the definition of category does not give: that the morphism can evaluate elements of the domain to give elements of the codomain.

So we need a more elaborate poster in the classroom:

The definition of “category” makes no requirement
that an object has elements
or that morphisms evaluate elements.

As was remarked long long ago, category theory is pointless.

English words implementing logic

There are lots of questions about logic that show that students really do not think that the definition of some particular logical construction can possibly be correct. That is why in the abstractmath.org chapter on definitions I inserted this purple prose:

A definition is a totalitarian dictator.

It is often the case that you can explain why the definition is worded the way it is, and of course when you can you should. But it is also true that the student has to grovel and obey the definition no matter how weird they think it is.

Formula and term

In logic you learn that a formula is a statement with variables in it, for example “$\exists x((x+5)^3\gt2)$”. The expression “$(x+5)^3$” is not a formula because it is not a statement; it is a “term”. But in English, $H_2O$ is a formula, the formula for water. As a result, some students have a remarkably difficult time understanding the difference between “term” and “formula”. I think that is because those students don’t really believe that the definition must be taken seriously.

Exclusive or

Question 804250 in MathSE says:

“Consider $P$ and $Q$. Let $P+Q$ denote exclusive or. Then if $P$ and $Q$ are both true or are both false then $P+Q$ is false. If one of them is true and one of them is false then $P+Q$ is true. By exclusive or I mean $P$ or $Q$ but not both. I have been trying to figure out why the truth table is the way it is. For example if $P$ is true and $Q$ is true then no matter what would it be true?”

I believe that the questioner is really confused by the plus sign: $P+Q$ ought to be true if $P$ and $Q$ are both true because that’s what the plus sign ought to mean.

Yes, I know this is about a symbol instead of an English word, but I think the difficulty has the same dynamics as the English-word examples I have given.

If I have understood this difficulty correctly, it is similar to the students who want to know why $1$ is not a prime number. In that case, there is a good explanation.

Only if

The phrase “only if” simply does not mean the same thing in math as it does in English. In Question 17562 in MathSE, a reader asks the question, why does “$P$ only if $Q$” mean the same as “if $P$ then $Q$” instead of “if $Q$ then $P$”?

Many answerers wasted a lot of time trying to convince us that “$P$ only if $Q$” mean the same as “if $P$ then $Q$” in ordinary English, when in fact it does not. That’s because in English, clauses involving “if” usually connote causation, which does not happen in math English.

Consider these two pairs of examples.

  1. “I take my umbrella only if it is raining.”
  2. “If I take my umbrella, then it is raining.”
  3. “I flip that switch only if a light comes on.”
  4. “If I flip that switch, a light comes on.”

The average non-mathematical English speaker will easily believe that (1) and (4) are true, but will balk and (2) and (3). To me, (3) means that the light coming on makes me flip the switch. (2) is more problematical, but it does (to me) have a feeling of causation going the wrong way. It is this difference that causes students to balk at the equivalence in math of “$P$ only if $Q$” and “If $P$, then $Q$”. In math, there is no such thing as causation, and the truth tables for implication force us to live with the fact that these two sentences mean the same thing.

Henning Makholm’ answer to Question 17562 begins this way: “I don’t think there’s really anything to understand here. One simply has to learn as a fact that in mathematics jargon the words ‘only if’ invariably encode that particular meaning. It is not really forced by the everyday meanings of ‘only’ and’ if’ in isolation; it’s just how it is.” That is the best way to answer the question. (Other answerers besides Makholm said something similar.)

I have also discussed this difficulty (and other difficulties with logic) in the abmath section on “only if“.

References

Creative Commons License

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

Send to Kindle

My early life as a mathematician

My early life as a mathematician.

Revised 22 January 2016.

In 1965, I received my Ph.D. at Duke University based on a dissertation about polynomials over finite fields. My advisor was Leonard Carlitz.

In Carlitz’s algebra course, the textbook was Van der Waerden’s Algebra. It is way too old-fashioned to be used nowadays, but it did indeed present post-Noether type abstract algebra. Carlitz also had me read large chunks of Martin Weber’s Lehrbuch der Algebra, written in German in 1895 (so totally not post-Noether) and published using Fraktur. A few years ago one of my sons asked me to retype the words to some of the songs written in Fraktur in a German-American shape note book in Roman type (but still in German), which I did. This was for German teachers in the Concordia Language Villages to use with their students. I sometimes wonder if I am the last person on earth able to read Fraktur fluently.

I learned mathematical logic from Joe Shoenfield from his dittoed notes that later became an excellent textbook. I rediscovered Craig’s Trick while working on problem he gave. That considerably strengthened my sense of self-worth.

I accepted a job at Western Reserve University, now Case Western Reserve University, where I stayed until I retired in 1999. In the few years after 1965, I wrote several papers about finite fields. They are all summarized in the book Finite Fields, by Rudolf Lidl and Harald Niederreiter.

I was almost immediately attracted to category theory and to computing science, both of which Carlitz hated. I did not let that stop me. (Now is the time to say, Follow The Beat of your Own Drum or some such cliché.)

Early on, Paul Dedecker was at CWRU briefly, and from him I learned about sheaves, cribles and the like. This inspired me to take part in an algebraic geometry summer school at Bowdoin College, where I learned from lectures by David Mumford and by reading his Red Book when it was still red.

Because one of the papers in finite fields showed that certain types of permutation polynomials formed wreath products of groups, I also pursued group theory, in particular by taking part in the finite group theory summer school at Bowdoin in 1970.

During that time I pored over Beck’s thesis on cohomology, which with the group theory I had learned resulted in my paper Automorphisms of group extensions. That paper has the most citations of all my research papers.

In the early days, I had several graduate students. All of them worked in group theory. One of them, Shair Ahmad, went on to produce several Ph.D. students, all in differential equations and dynamical systems.

One thing I can brag about is that I never ever told him I hated differential equations or dynamical systems. In fact, I didn’t hate either one. There were people in the department in both fields and they made me jealous the way they could model real life phenomena with those tools. One relevant point about that is that I was a liberal arts math major from Oberlin before going to Duke and had had very few courses in any kind of science. This made me very different from most people in the department, who has B.S. undergrad degrees.

In those days, John Isbell and Peter Hilton were in the math department at CWRU for awhile, which boosted my knowledge and interest in category theory. Hilton arranged for me to spend a year at the E.T.H. in Zürich, where I met Michael Barr. I eventually wrote two books on category theory with him. But that is getting away from Early Days, so I will stop here.

Creative Commons License

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

Send to Kindle

Functions: Metaphors, Images and Representations

Please read this post at abstractmath.org. I originally posted the document here but some of the diagrams would not render, and I haven’t been able to figure out why. Sorry for having to redirect.

Send to Kindle

Proofs using diagrams

Introduction

This post gives a proof of an easy theorem in category theory using the graph-based logic approach of Graph based logic and sketches, (GBLS) by Atish Bagchi and me.

Formal logic is typically defined in terms of formulas and terms, defined recursively as strings of characters, together with rules of inference. GBLS proposes a new approach to logic where diagrams are used instead of strings of characters. The exposition here spells out the proof in more detail than GBLS does and uses various experimental ways of drawing diagrams using Mathematica.

To follow this proof, you need to be familiar with basic category theory. Most special definitions that are needed are defined in this post where they are first used. Section 1 of GBLS also gives the definitions you need with more context.

The theorem

The Theorem to be proved (it is Theorem 8.3.1 of GBLS) says that, in any category, if the triangles in the diagram below commute, then the outside square commutes. This is easy using the associative law: If $xf=h$ and $kx=g$, then $kh=k(xf)=(kx)f=gf$.

Subject Diagram

So what?

This theorem is not interesting. The point of this post is to present a new approach to proving such theorems, using diagrams instead of strings. The reason that exhibiting the dig
rammatic proof is interesting is that many different kinds of categories have a FL cattheory, including these:

Essentially algebraic string-based logic is described in detail in Partial Horn logic and cartesian categories, by E. Palmgren and Steven Vickers.

Commercial

My concept of form in A generalization of the concept of sketch generalizes sketches to all the categories that can be defined as models of FL cattheories. So the method of proof using diagrams can be applied to theorems about the objects defined by forms.

Concepts needed for the graph-based proof

To prove the theorem, I will make use of $\mathbf{ThCat}$, the FL cattheory for categories.

  • An FL category is a category with all finite limits.
  • GLBS uses the word cattheory for what Category theory for computing science and Toposes, triples and theories call the theory of a sketch.
  • In many books and articles, and in nLab, a “sketch” is what we call the cattheory (or the theory) of a sketch. For us, the sketch is a generating collection of objects, arrows, diagrams, cones and cocones for the cattheory. The category of models of the sketch and the cattheory are equivalent.
  • $\mathbf{ThCat}$ is a category with finite limits freely generated by certain designated objects, arrows, commutative diagrams and limit cones, listed below.
  • A model of $\mathbf{ThCat}$ in $\mathbf{Set}$ (the category of sets, whichever one you like) is an FL functor $\mathfrak{C}:\mathbf{ThCat}\to\mathbf{Set}.$
  • Such a model $\mathfrak{C}$ is a small category, and every small category is such a model. If this statement worries you, read Section 3.4 of GBLS.
  • Natural transformations between models are FL-preserving functors that preserve the structure on the nose.
  • The category of models of $\mathbf{ThCat}$ in $\mathbf{Set}$ is equivalent to the category of small categories and morphisms, which, unlike the category of models, includes functors that don’t preserve things on the nose.
  • $\mathbf{ThCat}$ is an example of the theory of an FL sketch. Chapter 4 of GBLS describes this idea in detail. The theory has the same models as the sketch.
  • The sketch generating $\mathbf{ThCat}$ is defined in detail in section 7.2 of GBLS.

Some objects and arrows of $\mathbf{ThCat}$

I will make use of the following objects and arrows that occur in $\mathbf{ThCat}.$ A formal thing is a construction in $\mathbf{ThCat}$ that becomes an actual thing in a model. So for example a model $\mathfrak{C}$ of $\mathbf{ThCat}$ in $\mathbf{Set}$ is an actual (small) category, and $\mathfrak{C}(\mathsf{ar_2})$ is the set of all composable pairs of arrows in the category $\mathfrak{C}$.

  • $\mathsf{ob}$, the formal set of objects.
  • $\mathsf{ar}$, the formal set of arrows.
  • $\mathsf{ar}_2$, the formal set of composable pairs of arrows.
  • $\mathsf{ar}_3$, the formal set of composable triples of arrows.
  • $\mathsf{unit} : \mathsf{ob}\to \mathsf{ar}$ that formally picks out the identity arrow of an object.
  • $\mathsf{dom},\mathsf{cod} : \mathsf{ar}\to \mathsf{ob}$ that formally pick out the domain and codomain of an arrow.
  • $\mathsf{comp} : \mathsf{ar}_2\to \mathsf{ar}$ that picks out the composite of a composable pair.
  • $\mathsf{lfac}, \mathsf{rfac} :\mathsf{ar}_2\to \mathsf{ar}$ that pick out the left and right factors in a composable pair.
  • $\mathsf{lfac}, \mathsf{mfac},\mathsf{rfac} :\mathsf{ar}_3 \to\mathsf{ar}$ that pick out the left, middle and right factors in a composable triple of arrows.
  • $\mathsf{lass}, \mathsf{rass} : \mathsf{ar}_3 \to \mathsf{ar}_2$: $\mathsf{lass}$ formally takes $\langle{h,g,f}\rangle$ to $\langle{hg,f}\rangle$ and $\mathsf{rass}$ takes it to $\langle{h,gf}\rangle$.

$\mathsf{ob}$, $\mathsf{ar}$, $\mathsf{unit}$, $\mathsf{dom}$, $\mathsf{cod}$ and $\mathsf{comp}$ are given primitives and the others are defined as limits of finite diagrams composed of those objects. This is spelled out in Chapter 7.2 of GBLS. The definition of $\mathbf{ThCat}$ also requires certain diagrams to be commutative. They are all provided in GBLS; the one enforcing associativity is shown later in this post.

Color coding

I will use color coding to separate syntax from semantics.

  • Syntax consists of constructions in $\mathbf{ThCat}.$ The description will always be a commutative diagram in black, with annotations as explained later.
  • The limit of the description will be an object in $\mathbf{ThCat}$ (the form) whose value in a model $\mathfrak{C}$ will be shown in green, because being an element of the value of a model makes it semantics.
  • When a limit cone is defined, the projections (which are arrows in $\mathbf{ThCat}$) will be shown in blue.

Descriptions

In graph-based logic, a type of construction that can be made in a category has a description, which (in the case of our Theorem) is a finite diagram in $\mathbf{ThCat}$. The value of the limit of the description in a model $\mathfrak{C}$ is the set of all instances of that type of construction in $\mathfrak{C}$.

The Subject Diagram

  • This diagram is the subject matter of the Theorem. It is not assumed to be commutative.
  • As in most diagrams in category theory texts, the labels in this diagram are variables, so the diagram is implicitly universally quantified. The Subject Diagram is a generic diagram of its shape.
  • “Any diagram of its shape” includes diagrams in which some of the nodes may represent the same object. An extreme example is the graph in which every node is an object $\mathsf{E}$ and every arrow is its identity arrow. The diagram below is nevertheless an example of the Subject Diagram:
  • Shapes of diagrams are defined properly in Section 2.3 of
    GBLS and in Section 4.1 of Category Theory for Computing Science.

The description of the Subject Diagram

Diagram SDD below shows the Subject Diagram as the limit of its description. The description is the black diagram.


Diagram SDD

Definition of $\mathsf{ar}_2$

The object $\mathsf{ar}_2$ of composable pairs of arrows is defined as a pullback:

In the usual categorical notation this would be shown as

This makes use of the fact that the unnamed blue arrow is induced by the other two projection arrows. In the rest of the post, projection arrows that are induced are normally omitted.

An enrichment of the description

Because $\mathsf{ar}_2$ is defined as a pullback, we can enrich the description of Diagram SDD by adjoining two pullbacks as shown below. This is Diagram 8.10 in GBLS. The enriched diagram has the same limit as the description of Diagram SDD.

Enriched Diagram SDD

Note that the projections from the limit to the two occurrences of $\mathsf{ar}_2$ induce all the other projections. This follows by diagram chasing; remember that the description must be a commutative diagram.

Make the triangles commute

To make the triangles commute, we add two comp arrows to the enriched diagram as shown below. These two arrows are not induced by the description; they are therefore additions to the description — they describe a more restrictive (green) diagram with commutative triangles and so are shown in black.

Diagram TC: The triangles commute

The left comp makes $xf=h$ and the right comp makes $kx=g$.

The outside square commutes

Now we enrich Diagram TC with four objects, <comp,id>, <id,comp> and three comp arrows as shown in bolder black. These objects and arrows already exist in $\mathbf{ThCat}$ and therefore do not change the limit, which must be the same as the limit of Diagram TC.

The outside square commutes

The diagram in bold black is exactly the commutative diagram that requires associativity for these particular objects and arrows, which immediately implies that $gf=kh$, as the Theorem requires.

By the definitions of $\mathsf{ar_2}$ and $\mathsf{ar_3}$, the part of the description in bold black induces the rest of the diagram. Omitting the rest of the diagram would make $\mathsf{ar_2}$ and $\mathsf{ar_3}$ modules in the sense of GBLS, Chapter 7.4. Modules would be vital to deal with proofs more complicated than the one given here.

References

Creative Commons License

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

Send to Kindle

Grothendieck

In 1965, I received my Ph.D. with a dissertation about polynomials over finite fields. I accepted a job at Western Reserve U., now Case W.R.U. There I immediately began trying to learn category theory, which I thought was the best math thing since sliced bread. (My thesis adviser hated category theory. He also hated computer science, which also fascinated me.)

I was really lucky, for during the next few years John Isbell, Peter Hilton and Paul Dedecker came to stay for a few years, allowing me to pick up a decent understanding of categories. Dedecker only stayed one year, but from him I learned about sheaves, cribles and the like, which inspired me to spend a summer at Bowdoin College learning about algebraic geometry from David Mumford and his Red Book.

It was only gradually that I learned that many of the most interesting ideas came from Alexandre Grothendieck. His ideas are now everywhere in math and we should all be grateful for his life and work.  I wish he had continued working.  He could have done wonders for computing science.

 

Send to Kindle

Sets

I have been working my way through abstractmath.org, revising the articles and turning them into pure HTML so they will be easier to update. In some cases I am making substantial revisions. In particular, many of the articles need a more modern point of view.

 

The math community’s understanding of sets and structures has changed because of category theory and will change
because of homotopy type theory.

 

This post considers some issues and possibilities concerning the chapter on sets.

The references listed at the end of the article include several about homotopy type theory. They provide different viewpoints and require different levels of sophistication.

A specification of the concept of set

The abmath article Specification of sets specifies what a set is in this way:

A set is a single math object distinct from but completely determined by what its elements are.

I have used this specification for sets since the eighties, first in my Discrete Math lecture notes and then in abstractmath.org. It has proved useful because it is quite simple and the statement implies lots of immediate consequences. Each of the first four consequences in this list below exposes a confusion that some students have.

Consequences of the specification

  1. A set is a math object. It has the same status as the number “$143$” and the sine function and the real line: they are all objects of math. A set is not merely a typographically convenient way to define a certain collection of things.
  2. A set is a single object. Many beginners seem to have in their head that the set $\{3,4\}$ is two things.
  3. A set is distinct from its elements. The set $\{3,4\}$ is not $3$, it is not $4$, it is not a number at all.
  4. The spec implies that $\{3,4\}$ is the same set as $\{4,3\}$. Some students think they understand this but some of their mistakes show that they don’t really understand it.
  5. On the other hand, $\{3,5\}$ is a different set from $\{3,4\}$. I haven’t noticed this bothering students but it bothers me. See the discussion on ursets below.

Those consequences make the spec a useful teaching tool. But if a beginning abstract math student gets very far in their studies, some complications come up.

Defining “set”

In the late nineteenth century, math people started formally defining particular math structures such as groups and various
kinds of spaces. This was normally done by starting with a set and adding structure.

You may think that “starting with a set and adding structure” brushes a lot of complications under the rug. Well, don’t look under the rug, at least not right now.

The way they thought about sets was a informal version of what is now called naive set theory. In particular, they freely defined particular sets using what is essentially setbuilder notation, producing sets in a way which (I claim) satisfies my specification.

Bertrand Russell wakes everyone up

Then along came Russell’s paradox. In the context of this discussion, the paradox implied that the spec for sets is not a definition.The spec provides a set of necessary conditions for being a set. But it is not sufficient. You can say “Let $S$ be the set of all sets that…[satisfy some condition]” until you are blue in the face, but there are conditions (including the empty condition) that don’t define a set.

The Zermelo-Fraenkel axioms

The Zermelo-Fraenkel axioms were designed to provide a definition that didn’t create contradictions. The axioms accomplish this by creating a sort of hierarchy that requires that each set must be defined in terms of sets defined previously. They provide a good way (but not the only one) of providing a way of legitimizing our use of sets in math.

Observe that the “set of all sets” is certainly not “defined” in terms of previously defined sets!

Sets as a foundation

During those days there was a movement to provide a solid foundation for mathematics. After Zermelo-Fraenkel came along, the progress of thinking seemed to be:

  1. Sets are in trouble.
  2. Zermelo-Fraenkel solves our set difficulties.
  3. So let’s require that every math object be a set.

That list is oversimplified. In particular, the development of predicate logic was essential to this approach, but I can’t write about everything at once.

This leads to monsters such as the notorious definition of ordered pair:

The ordered pair $(a,b)$ is the set $\{a,\{b\}\}$.

This leads to the ludicrous statement that $a$ is an element of $(a,b)$ but that $b$ is not.

By saying every math object may be modeled as a set with structure, ZF set theory becomes a model of all of math. This approach gives a useful proof that all of math is as consistent as ZF set theory is.

But many mathematicians jumped to the conclusion that every math object must be a set with structure. This approach does not match the way mathematicians think about math objects. In particular, it makes computerized proof assistance hard to use because you have to translate your thinking into sets and first order logic.

Sets by category theory

“A mathematical object is determined by the role it plays in a category.” — A. Grothendieck

In category theory, you define math structures in terms of how they relate to other math structures. This shifts the emphasis from

What is it?

to

What are its properties?

For example, an ordered pair is a mathematical object $p$ determined by these properties:

  • It determines mathematical objects $p_1$ and $p_2$.
  • $p$ is completely determined by what $p_1$ is and what $p_2$ is.
  • If $p$ and $q$ are ordered pairs and $p_1=q_1$ and $p_2=q_2$ then $p=q$.

Categorical definition of set

“Categorical” here means “as understood in category theory”. It unfortunately has a very different meaning in model theory (set of axioms with only one model up to isomorphism) and in general usage, as in “My answer is categorically NO” said by someone who is red in the face. The word “categorial” has an entirely different meaning in linguistics. *Sigh*.

William Lawvere has produced an axiomatization of the category of sets.
The most accessible introduction to it that I know of is the article Rethinking set theory, by Tom Leinster. This axiomatization defines sets by their relationship with each other and other math objects in much the same way as the categorical definition of (for example) groups gives a definition of groups that works in any category.

“Set” means two different things

The word set as used informally has two different meanings.

  • According to my specification of sets, $\{3,4\}$ is a set and so is $\{3,5\}$.
  • $\{3,4\}$ and $\{3,5\}$ are not the same set because they don’t have the same elements.
  • But in the category of sets, any two $2$-element sets are isomorphic. (So are any two seven element sets.)
  • From a categorical point of view, two isomorphic objects in a category can be be thought of as the same object, with a caveat that you have better make it clear which isomorphism you are thinking of.

One of the great improvements in mathematics that homotopy type theory supplies is a systematic way of keeping track of the isomorphisms, the isomorphisms between the isomorphisms, and so on ad infinitum (literally). But note: I am just beginning to understand htt, so regard this remark as something to be suspicious of.

  • But $\{3,4\}$ and $\{3,5\}$ may not be thought of as the same object according to the spec I gave, because they don’t have the same elements.
  • This means that the traditional idea of set is not the same as the strict categorical idea of set.

I suggest that we keep the word “set” for the traditional concept and call the strict categorical concept an urset.

A traditional set is a structure on an urset

The traditional set $\{3,5\}$ consists of the unique two-element urset coindexed on the integers.

A (ur)set $S$ coindexed by a math structure $A$ is a monic map from $S$ to the underlying set of $A$. In this example, the map has codomain the integers and takes one element of the two-element urset to $3$ and the other to $5$.

Note added 2014-10-05 in response to Toby Bartels’ comment: I am inclined to use the names “abstract set” for “urset” and “concrete set” for coindexed sets when I revise the articles on sets. But most of the time we can get away with just “set”.

There is clearly no isomorphism of coindexed sets from $\{3,4\}$ to $\{3,5\}$, so those two traditional sets are not equal in the category of coindexed sets.

I made up the phrase “coindexed set” to use in this sense, since it is a kind of opposite of indexed set. If terminology for this already exists, lemme know. Linguists will tell you they use the word “coindexed” in a different sense.

Elements

The concept of “element” in categorical thinking is very different from the traditional idea, where an element of a set can be any mathematical object. In categorical thinking, an element of an object $A$ of a category $\mathbf{C}$ is an arrow $1\to A$ where $1$ is the terminal object. Thus $4$ as an integer is the arrow $1\to \mathbb{Z}$ whose unique value is the number $4$.

An object is an element of only one set

In the usage of category theory, the arrow $1\to\mathbb{R}$ whose value is the real number $4$ is a different math object from the arrow $1\to\mathbb{Z}$ whose value is the integer $4$.

A category theorist will probably agree that we can identify the integer $4$ with the real number $4$ via the well known canonical embedding of the ring of integers into the field of real numbers. But in categorical thinking you have to keep all such embeddings in mind; you don’t say the integer $4$ is the same thing as the real number $4$. (Most computer languages keep them distinct, too.)

This difference is actually not hard to get used to and is in fact an improvement over traditional set theory. When you do category theory you use lots of commutative diagrams. The embeddings show up as monic arrows and are essential in keeping the different objects ($\mathbb{Z}$ and $\mathbb{R}$ in the example) separate.

The paper Relating first-order set theory and elementary toposes, by Awodey, Butz, Simpson and Streicher, introduces a concept of “structural system of inclusions” that appears to me to restore the idea of object being an element of more than one set for many purposes.

Homotopy type theory allows an object to have only one type, with much the same effect as in the categorical approach.

Variable elements

The arrow $1\to \mathbb{Z}$ that picks out the integer $4$ is a constant function. It is useful to think of any arrow $A\to B$ of any category as a variable element (or generalized element) of the object $B$. For example, the function $f:\mathbb{R}\to \mathbb{R}$ defined by $f(x)=x^2$ allows you to
think of $x^2$ as a variable number with real parameter. This is another way of thinking about the “$y$” in the equation $y=x^2$, which is commonly called a dependent variable.

One way to think about $y$ is that some statements about it are true, some are false, and many statements are neither true nor false.

  • $y\geq 0$ is true.
  • $y\lt0$ is false.
  • $y\leq1$ is neither true nor false.

This way of thinking about variable objects clears up a lot of confusion about variables and deserves to be more widely used in teaching.

The book Category theory for computing science provides some examples of the use of variable elements as a way of thinking about categorical ideas.

References

Creative Commons License< ![endif]>

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

Send to Kindle

The only axiom of algebra

This is one of a series of posts I am writing to help me develop my thoughts about how particular topics in my book Abstracting Algebra (“AbAl“) should be organized. This post concerns the relation between substitution and evaluation that essentially constitutes the definition of algebra. The Mathematica code for the diagrams is in Subs Eval.nb.

Substitution and evaluation

This post depends heavily on your understanding of the ideas in the post Presenting binary operations as trees.

Notation for evaluation

I have been denoting evaluation of an expression represented as a tree like this:



In standard algebra notation this would be written:\[(6-4)-1=2-1=1\]

Comments

This treatment of evaluation is intended to give you an intuition about evaluation that is divorced from the usual one-dimensional (well, nearly) notation of standard algebra. So it is sloppy. It omits fine points that will have to be included in AbAl.

  • The evaluation goes from bottom up until it reaches a single value.
  • If you reach an expression with an empty box, evaluation stops. Thus $(6-3)-a$ evaluates only to $3-a$.
  • $(6-a)-1$ doesn’t evaluate further at all, although you can use properties peculiar to “minus” to change it to $5-a$.
  • I used the boxed “1” to show that the value is represented as a trivial tree, not a number. That’s so it can be substituted into another tree.

Notation for substitution

I will use a configuration like this

to indicate the data needed to substitute the lower tree into the upper one at the variable (blank box). The result of the substitution is the tree

In standard algebra one would say, “Substitute $3\times 4$ for $a$ in the expression $a+5$.” Note that in doing this you have to name the variable.

Example

“If you substitute $12$ for $a$ in $a+5$ you get $12+5$”:

results in

Example

“If you substitute $3\times 4$ for $a$ in $a+b$ you get $3\times4+b$”:

results in

Comments

Like evaluation, this treatment of substitution omits details that will have to be included in AbAl.

  • You can also substitute on the right side.
  • Substitution in standard algebraic notation often requires sudden syntactic changes because the standard notation is essentially two-dimensional. Example: “If you substitute $3+ 4$ for $a$ in $a\times b$ you get $(3+4)\times b$”.
  • The allowed renaming of free variables except when there is a clash causes students much trouble. This has to be illustrated and contrasted with the “binop is tree” treatment which is context-free. Example: The variable $b$ in the expression $(3\times 4)+b$ by itself could be changed to $a$ or $c$, but in the sentence “If you substitute $3+ 4$ for $a$ in $a\times b$ you get $(3+4)\times b$”, the $b$ is bound. It is going to be difficult to decide how much of this needs explaining.

The axiom

The Axiom for Algebra says that the operations of substitution and evaluation commute: if you apply them in either order, you get the same resulting tree. That says that for the current example, this diagram commutes:

The Only Axiom for Algebra

In standard algebra notation, this becomes:

  • Substitute, then evaluate: If $a=3\times 4$, then $a+5=3\times 4+5=12+5$.
  • Evaluate, then substitute: If $a=3\times 4$, then $a=12$, so $a+5=12+5$.

Well, how underwhelming. In ordinary algebra notation my so-called Only Axiom amounts to a mere rewording. But that’s the point:

The Only Axiom of Algebra is what makes algebraic manipulation work.

Miscellaneous comments

  • In functional notation, the Only Axiom says precisely that $\text{eval}∘\text{subst}=\text{subst}∘(\text{eval},\text{id})$.
  • The Only Axiom has a symmetric form: $\text{eval}∘\text{subst}=\text{subst}∘(\text{id},\text{eval})$ for the right branch.
  • You may expostulate: “What about associativity and commutativity. They are axioms of algebra.” But they are axioms of particular parts of algebra. That’s why I include examples using operations such as subtraction. The Only Axiom is the (ahem) only one that applies to all algebraic expressions.
  • You may further expostulate: Using monads requires the unitary or oneidentity axiom. Here that means that a binary operation $\Delta$ can be applied to one element $a$, and the result is $a$. My post Monads for high school III. shows how it is used for associative operations. The unitary axiom is necessary for representing arbitrary binary operations as a monad, which is a useful way to give a theoretical treatment of algebra. I don’t know if anyone has investigated monads-without-the-unitary-axiom. It sounds icky.
  • The Only Axiom applies to things such as single valued functions, which are unary operations, and ternary and higher operations. They also apply to algebraic expressions involving many different operations of different arities. In that sense, my presentation of the Only Axiom only gives a special case.
  • In the case of unary operations, evaluation is what we usually call evaluation. If you think about sets the way I do (as a special kind of category), evaluation is the same as composition. See “Rethinking Set Theory”, by Tom Leinster, American Mathematical Monthly, May, 2014.
  • Calculus functions such as sine and the exponential are unary operations. But not all of calculus is algebra, because substitution in the differential and integral operators is context-sensitive.

References

Preceding posts in this series

Remarks concerning these posts
  • Each of the posts in this series discusses how I will present a small part of AbAl.
  • The wording of some parts of the posts may look like a first draft, and such wording may indeed appear in the text.
  • In many places I will talk about how I should present the topic, since I am not certain about it.

Other references

Creative Commons License

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


Send to Kindle