The First Commutative Diagram?

July 8, 2013

Posted by Tom Leinster

$MathML-enabled post (click for more details).$

At lunch today at Category Theory 2013 in Sydney, a bunch of us were talking about the mathematical work of Bertrand Russell, and I remembered this:

It’s from Russell’s 1919 book Introduction to Mathematical Philosophy, and it’s essentially a commutative square in the category of sets and relations, although the notation is very slightly different from how we’d do it now. Click on the image to see the whole page.

I was very surprised to see a commutative diagram from 1919. This was more than twenty years before the birth of category theory. Indeed, I’m not sure that the arrow notation for mappings was commonplace back then. Does anyone know of an earlier example of a commutative diagram in print?

Posted at July 8, 2013 5:38 AM UTC

TrackBack URL for this Entry: https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2631

29 Comments & 0 Trackbacks

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Not an earlier example, but, Mac Lane [Concepts and categories in perspective] did suggest that the arrow notation comes from the 1930s/40s.

Posted by: Zhen Lin on July 8, 2013 11:10 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Great. An excellent reference to bring up at my conference.

Posted by: David Corfield on July 8, 2013 1:47 PM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

N-category cafe and n-forum are not letting me see a list of recent postings ?? but if I click on the name of the rss feed, I do get the latest nd then can scroll down through other recent postings but this is very inefficient

help!!

apologies for posting this here totally out of context but I don’t knwo where else to complain

jim

Posted by: jim_stasheff on July 8, 2013 3:37 PM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Do you mean the n-Cafe main page doesn’t have all the parts it usually does?

If so, that could be a connectivity issue, such that the delivery of the page gets interrupted; and there are at least four plugs that could have a connection problem between you and whatever server Jacques’ is using. There doesn’t seem to be such a trouble at my end, so your difficulty may well disappear.

Posted by: Jesse C. McKeown on July 8, 2013 9:37 PM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Jim, I’ve copied your comment (and Jesse’s reply) over to the TeXnical issues post.

Posted by: Simon Willerton on July 9, 2013 9:25 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

It seems to me that Russell is there just explaining the concept of isomorphism between binary relations. For any $x,y$

$P(x,y) \leftrightarrow Q(S(x),S(y))$

holds. So, he means:

$S: P \to Q$

is an isomorphism. So, category-theoretically, the “objects” would be the binary relations $P$ and $Q$ , and $S$ would be a morphism.

But the objects $x,y,z,w$ at the nodes of Russell’s diagram are relata of $P$ and $Q$ , rather than the relations (i.e., $P,Q$ ) themselves. So, it seems to me that $x,y,z,w$ aren’t objects in the usual category-theoretic sense; and if so, then this doesn’t seem to be a commutative diagram.

On the other hand, the diagramatic arrows between $x$ and $y$ express that the atomic formula $P(x,y)$ holds; and this is more like the structural diagram one gives for a relation. So, I think this is diagram in the model-theoretic sense, not category-theoretic sense.

(Maybe, if we wish to thing of $x,y,z,w$ as “objects”, we can think of the binary relation $P$ as a category: the objects of this category are elements of $Fld(P)$ (the field of $P$ ), and a “morphism” holds between $x,y$ when $P(x,y)$ is true. But then, for what Russell is considering, we have two categories, $P$ and $Q$ , and $S$ is now a functor between categories!)

Russell was one of first to consider classes of isomorphic relations: in PM, he and Whitehead call them “relation-numbers”, because they generalize the Frege-Russell analysis of cardinals as “class-numbers”, i.e., equivalence classes

$[A]_{\sim} = \{B \mid B \sim A\}$

of classes under the relation $\sim$ of bijection.

Jeff

Posted by: Jeffrey Ketland on July 9, 2013 3:47 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Yes, Russell writes the name of a typical element of each set, rather than the name of the set itself. So if $P$ is a relation between $X$ and $Y$ (that is, $P \subseteq X \times Y$ ), then today we’d write $X$ in the top-left corner, whereas Russell wrote a dot at the vertex with an $x$ next to it. That’s why I said that the notaiton was slightly different from what we use today.

I think this is diagram in the model-theoretic sense, not category-theoretic sense.

With minimal notational change, it is a diagram in the category-theoretic sense: it’s a commutative square in the category of sets and relations. The vertical relation $S$ just happens to be a bijective function.

If you look further down the page, in the paragraph beginning “A relation $S$ is said to be a ‘correlator’”, I think it’s clear that $x$ , $y$ , etc. are meant to be arbitrary elements, not specific ones.

What’s the meaning of “diagram” in model theory?

Posted by: Tom Leinster on July 9, 2013 5:02 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Tom,

I think Russell means that

$(x,y) \in P$

rather than

$P \subseteq X \times Y$

So, $x,y$ are relata of $P$ , rather than the domain and codomain. And below, he means that $(z,w) \in Q$ , and and since $z = S(x)$ and $w = S(y)$ , then

$(x,y) \in P \leftrightarrow (S(x),S(y)) \in Q$

and this is understood to hold for all $x,y$ . So,

$S: P \to Q$

is an isomorphism.

Suppose $\mathcal{M} = (A,\leq)$ is, say, a partial order, then the “diagram” of $\mathcal{M}$ , in the sense of model theory, is the set of true atomic sentences and negated atomic sentences (about $\mathcal{M}$ ) in a certain language $L$ which has a name for each $a \in A$ . E.g., let $L$ have a constant $\underline{a}$ for each $a \in A$ , and let $L$ have a binary predicate $P$ standing for the ordering $\leq$ . A literal in $L$ is any atomic or negated atomic sentence in $L$ . So, a literal has the form either $P(\underline{a}, \underline{b})$ or $\neg P(\underline{a}, \underline{b})$ . Let $Lit(L)$ be the set of literals in $L$ . Then the diagram of $\mathcal{M}$ is the set of true literals in $L$ :

$diag(\mathcal{M}) := \{ \phi \in Lit(L) \mid \mathcal{M} \models \phi\}$

Models and diagrams always determine each other, up to isomorphism, and sometimes it’s easier to work with the diagram rather than the model. It’s explained a bit more here:

http://plato.stanford.edu/entries/modeltheory-fo/#Thms

The notion captures the intuitive idea of the “multiplication table” of a relation. I believe the term is due to Abraham Robinson.

Jeff

Posted by: Jeffrey Ketland on July 9, 2013 8:18 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

I think Russell means that

$(x,y)\in P$

rather than

$P \subseteq X \times Y$

So, $x,y$ are relata of $P$ , rather than the domain and codomain.

What’s the difference? Had he written anachronistically

$\array{X & \overset{P}{\to} & X\\ ^S\downarrow && \downarrow^S\\ Y& \underset{Q}{\to} & Y},$

as a commutative diagram in the category of sets and relations, it would have meant the same thing (adding in the condition that ‘domain’ and ‘converse domain’ must be the same for both $P$ and $Q$ in order that $S$ be defined).

Reading what he writes, one could also say, again anachronistically, that he’s working in a category whose objects are sets equipped with a relation, with invertible relation-preserving morphisms.

Posted by: David Corfield on July 9, 2013 9:35 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

David,

What’s the difference?

The point is that

(i) $P(x,y)$

(ii) $P \subseteq x \times y$

do not have the same mathematical meaning. In the text from Ch. VI of Introduction to Mathematical Philosophy that Tom has there, Russell writes:

Let $x$ and $y$ be two terms having the relation $P$ .

It’s fairly clear from this (and the rest of the chapter) that Russell means (i), not (ii). He does not mean that $P$ is a relation on $x \times y$ . He means simply that $x$ bears $P$ to $y$ ; so $x,y$ are simply things (he calls them “terms”) related by $P$ , and not the domain and codomain of a mapping.

The chapter is entitled “Similarity of Relations” and explains the concept of isomorphism between binary relations, as in his $P$ and $Q$ . That is, $P$ and $Q$ are isomorphic just if there is a bijection $s$ from the field of $P$ to the field of $Q$ such that, for any $x,y$ ,

$P(x,y)$ iff $Q(s(x),s(y))$ .

Russell’s “arrow” notation is more like the notation one uses in drawing the “diagram” of a binary relation on the whiteboard (as one usually does for a directed graph, say). An arrow is drawn from node $x$ to node $y$ when $P(x,y)$ holds.

Jeff

Posted by: Jeffrey Ketland on July 9, 2013 11:03 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

I think we all agree that (i) and (ii) mean different things. But until now, no one had been talking about “ $P \subseteq x \times y$ ”, as in your (ii); it’s $P \subseteq X \times Y$ that we’re talking about. (Though as David pointed out, I should have said $P \subseteq X \times X$ .) Was it a typo?

Posted by: Tom Leinster on July 10, 2013 12:16 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Tom,

Right, so probably best to forget the upper-case $X,Y$ and focus on the node labels used by Russell ( $x,y,z,w$ ) in the diagram. The upper arrowed line in Russell’s diagram means:

$P(x,y)$

So, this represents the atomic claim that $x$ bears the relation $P$ to $y$ . Equivalently, $(x,y) \in P$ . So, I’m pretty sure it doesn’t have the category-theoretic meaning that $P$ is a morphism from $x$ to $y$ . It doesn’t mean “ $x$ is the domain of $P$ and $y$ is the codomain of $P$ ”. The lower arrowed line means:

$Q(z,w)$

Then the vertical lines, for the mapping $S$ mean:

$z = S(x)$

$w = P(y)$

So, the whole diagram means:

$P(x,y)$ iff $Q(S(x),S(y))$ , for arbitrary $x,y$

I.e.,

$S: P \to Q$ is an isomorphism

So, this is how Russell explains “The Similarity of Relations”, i.e., as we’d now say, isomorphisms between binary relations $P$ and $Q$ .

Jeff

Posted by: Jeffrey Ketland on July 10, 2013 3:36 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Again, I think we’re talking at cross purposes. No one is claiming that the horizontal arrow means

“ $x$ is the domain of $P$ and $y$ is the codomain of $P$ ”.

Also, everyone agrees that, as you wrote:

the whole diagram means:

$P(x, y)$ iff $Q(S(x), S(y))$ , for arbitrary $x, y$

— this is not in dispute.

We don’t seem to be getting anywhere. Maybe it’s differing cultural backgrounds to blame.

Posted by: Tom Leinster on July 11, 2013 4:37 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Tom,

I think we’re getting somewhere! I see how this is getting confusing: partly because we jumped from lower-case $x$ to upper case $X$ , and then got both $x$ and $X$ in play.

In the category of sets and relations, $P : X \to Y$ is a morphism when $P \subseteq X \times Y$ . So, when you said this was a commutative diagram in the category of sets and relations, the upper arrowed line in Russell’s diagram

$x \xrightarrow{P} y$

would have to mean

$P : x \to y$ .

Is that right?

Jeff

Posted by: Jeffrey Ketland on July 12, 2013 1:48 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

I certainly agree that it’s not natural to interpret Russell as working in $Rel$ , since the restrictions then seem rather arbitrary as to which kinds of morphisms make up the commutative square. As you say, in the discussion he’s just dealing with isomorphic structures, i.e., isomorphic graphs.

On the other hand, there does seem to be some understanding on his part that $P$ , $Q$ and $S$ are all relations, even if $P$ and $Q$ are special in that they are relations over a single field, and $S$ is a bijection between fields.

In a possible world, he would have realised that, since they are arrows of the same kind, he had devised a commutative diagram. Then he would have thought more generally about composition of general binary relations as composition of arrows, and from there he would have generalised to invent category theory :)

As for notation, say we work with sets and functions, for generic $x: X$ , $y: Y$ , I can’t see a difference between what’s expressed by

$x \overset{f}{\to} y$

and

$X \overset{f}{\to} Y.$

Both seems to me to be declaring in the type theoretic fashion that if $x : X$ , then $f(x): Y$ , the former having introduced a term $y : Y$ and declared $y = f(x):Y$ .

Posted by: David Corfield on July 9, 2013 12:09 PM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

David,

Normally, assuming $x \in X$ and $y \in Y$ , we’d write:

$f: X \to Y$

by:

$x \mapsto y = f(x)$

using $\mapsto$ ; otherwise, one mixes up the element $x \in X$ with the domain $X$ itself.

Russell composes relations; but might Russell in any case have gone in that “algebraic” direction? I don’t think Russell would have approached things in the algebraic way characteristic of category theory, because for him, relations were crucial, while functions were simply relations satisfying a uniqueness clause.

Still, Russell’s co-author A.N. Whitehead wrote the 1898 monograph Universal Algebra, and that surely played some role in the development of algebra up to Eilenberg and MacLane. It’s online here

http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.chmm/1263316509

Quite a bit of lasting notation ( $\forall, \exists, \in$ ) was introduced by Peano. But I don’t know of the history of the arrow notation; my guess would be to look at Noether, van der Waerden and Birkhoff.

Jeff

Posted by: Jeffrey Ketland on July 9, 2013 1:18 PM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

I don’t think Russell would have approached things in the algebraic way characteristic of category theory, because for him, relations were crucial, while functions were simply relations satisfying a uniqueness clause.

This makes it sound as if you’re saying that morphisms in a category have to be functions of some kind. You’re not, are you? If Russell’s square is to be interpreted as living in some category, it would probably be the category whose objects are sets and whose morphisms are relations.

Posted by: Tom Leinster on July 11, 2013 4:39 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Tom,

Agreed - yes, the morphisms can be anything, so long as they have a source, a target and compose in the right way. I just think Russell himself is not likely to have conceived of things in this (Hilbertian) way though. I think Russell’s diagram is more like the directed graph of a binary relation, or like a Hasse diagram for a partial order, etc., than a commutative diagram. So, I don’t think the nodes $x,y,z,w$ label sets. For Russell’s purposes, they could label towns or stars …

Russell did advocate a form of structuralism though (probably influenced by Dedekind) and this is linked through a convoluted history to some of the recent discussions of “structure identity”.

Jeff

Posted by: Jeffrey Ketland on July 12, 2013 3:06 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Evidently $P$ and $Q$ relate elements of the same sets, $P \subseteq X \times X, Q \subseteq Y \times Y, S \subseteq X \times Y$ . It sounds as though he’s allowing $X$ and $Y$ to be different.

$S$ has an intertwiner-ish, 2-morphism feel, no?

Posted by: David Corfield on July 9, 2013 6:35 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Oops, yes, you’re right. Doesn’t make a difference to the historical interpretation, though.

Posted by: Tom Leinster on July 9, 2013 7:12 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

As above, it can be recast as a commutative diagram in the category of sets and relations, although then perhaps one might wonder why he chose to have the vertical morphisms to be the same.

Reading the text, as I said, it seems he’s chosen the category whose objects are sets equipped with a relation and invertible relation-preserving morphisms. Then $S$ is just a morphism, $S: (X, P) \to (Y, Q)$ .

Posted by: David Corfield on July 9, 2013 9:42 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

I think what Russell is doing is what we now call a diagram chase.

Posted by: Jesse C. McKeown on July 10, 2013 1:20 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Interestingly, at the end of the seventh paragraph of Russell’s essay What I Believe he states that “everything interesting is a matter of organization, not primal substance.” Sounds like something straight out of MacLane’s Form and Function.

Posted by: John Meuser on August 5, 2013 1:58 AM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Saunders would prefer Mac Lane

Posted by: jim_stasheff on August 6, 2013 1:18 PM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

That may be, and apparently the “Mac Lane” (with the spacing) joke never got old for Saunders. But if memory serves, it eventually grew too old for at least one of his daughters, who reverted back to the old space-free spelling.

Posted by: Todd Trimble on August 6, 2013 5:28 PM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Never heard the joke. Can guess: first name Mac, family name Lane?

Posted by: jim_stasheff on August 7, 2013 1:22 PM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

The “joke” Mac Lane didn’t get tired of was that his wife had problems typing his name without a space. Maybe he just wanted “space” to be part of his name. He was hyper-proud of his Scottish descent and I think I recall that his family had already changed the spelling of the name to make it more Scottish (in the US, the mixed Scots-Irish would spell the name with a “Mc”)

Posted by: RodMcGuire on August 7, 2013 3:41 PM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

Life is never that simple! The Wikipedia article on the Gaelic naming system states ‘Note that Scottish Gaelic does not put a space between the Mac and the second element, whereas in Irish, there is a space.’

Posted by: Tim Porter on August 7, 2013 8:35 PM | Permalink | Reply to this

Re: The First Commutative Diagram?

$MathML-enabled post (click for more details).$

There seem to be various stories about how the space got in there. Wikipedia reports a story about his first wife Dorothy having trouble typing the name, but another I’d heard is slightly more humorous and involved the vagaries of printers. I don’t recall if he and I ever discussed this.

Posted by: Todd Trimble on August 10, 2013 12:14 AM | Permalink | Reply to this

The n-Category Café

Skip to the Main Content

July 8, 2013