Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

July 8, 2013

The First Commutative Diagram?

Posted by Tom Leinster

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:

Commutative square from Rusell's 1919 book Introduction to Mathematical Philosophy

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:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2631

29 Comments & 0 Trackbacks

Re: The First Commutative Diagram?

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?

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?

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?

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?

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?

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

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

holds. So, he means:

S:PQS: P \to Q

is an isomorphism. So, category-theoretically, the “objects” would be the binary relations PP and QQ, and SS would be a morphism.

But the objects x,y,z,wx,y,z,w at the nodes of Russell’s diagram are relata of PP and QQ, rather than the relations (i.e., P,QP,Q) themselves. So, it seems to me that x,y,z,wx,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 xx and yy express that the atomic formula P(x,y)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,wx,y,z,w as “objects”, we can think of the binary relation PP as a category: the objects of this category are elements of Fld(P)Fld(P) (the field of PP), and a “morphism” holds between x,yx,y when P(x,y)P(x,y) is true. But then, for what Russell is considering, we have two categories, PP and QQ, and SS 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] ={BBA}[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?

Yes, Russell writes the name of a typical element of each set, rather than the name of the set itself. So if PP is a relation between XX and YY (that is, PX×YP \subseteq X \times Y), then today we’d write XX in the top-left corner, whereas Russell wrote a dot at the vertex with an xx 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 SS just happens to be a bijective function.

If you look further down the page, in the paragraph beginning “A relation SS is said to be a ‘correlator’”, I think it’s clear that xx, yy, 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?

Tom,

I think Russell means that

(x,y)P(x,y) \in P

rather than

PX×YP \subseteq X \times Y

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

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

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

S:PQS: P \to Q

is an isomorphism.

Suppose =(A,)\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 LL which has a name for each aAa \in A. E.g., let LL have a constant a̲\underline{a} for each aAa \in A, and let LL have a binary predicate PP standing for the ordering \leq. A literal in LL is any atomic or negated atomic sentence in LL. So, a literal has the form either P(a̲,b̲)P(\underline{a}, \underline{b}) or ¬P(a̲,b̲)\neg P(\underline{a}, \underline{b}). Let Lit(L)Lit(L) be the set of literals in LL. Then the diagram of \mathcal{M} is the set of true literals in LL:

diag():={ϕLit(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?

I think Russell means that

(x,y)P (x,y)\in P

rather than

PX×Y P \subseteq X \times Y

So, x,yx,y are relata of PP, rather than the domain and codomain.

What’s the difference? Had he written anachronistically

X P X S S Y Q Y,\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 PP and QQ in order that SS 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?

David,

What’s the difference?

The point is that

(i) P(x,y)P(x,y)

(ii) Px×yP \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 xx and yy be two terms having the relation PP.

It’s fairly clear from this (and the rest of the chapter) that Russell means (i), not (ii). He does not mean that PP is a relation on x×yx \times y. He means simply that xx bears PP to yy; so x,yx,y are simply things (he calls them “terms”) related by PP, 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 PP and QQ. That is, PP and QQ are isomorphic just if there is a bijection ss from the field of PP to the field of QQ such that, for any x,yx,y,

P(x,y)P(x,y) iff Q(s(x),s(y))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 xx to node yy when P(x,y)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?

I think we all agree that (i) and (ii) mean different things. But until now, no one had been talking about “Px×yP \subseteq x \times y”, as in your (ii); it’s PX×YP \subseteq X \times Y that we’re talking about. (Though as David pointed out, I should have said PX×XP \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?

Tom,

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

P(x,y)P(x,y)

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

Q(z,w)Q(z,w)

Then the vertical lines, for the mapping SS mean:

z=S(x)z = S(x)

w=P(y)w = P(y)

So, the whole diagram means:

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

I.e.,

S:PQS: 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 PP and QQ.

Jeff

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

Re: The First Commutative Diagram?

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

xx is the domain of PP and yy is the codomain of PP”.

Also, everyone agrees that, as you wrote:

the whole diagram means:

   P(x,y)P(x, y) iff Q(S(x),S(y))Q(S(x), S(y)), for arbitrary x,yx, 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?

Tom,

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

In the category of sets and relations, P:XYP : X \to Y is a morphism when PX×YP \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

xPyx \xrightarrow{P} y

would have to mean

P:xyP : 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?

I certainly agree that it’s not natural to interpret Russell as working in RelRel, 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 PP, QQ and SS are all relations, even if PP and QQ are special in that they are relations over a single field, and SS 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:Xx: X, y:Yy: Y, I can’t see a difference between what’s expressed by

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

and

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

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

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

Re: The First Commutative Diagram?

David,

Normally, assuming xXx \in X and yYy \in Y, we’d write:

f:XYf: X \to Y

by:

xy=f(x)x \mapsto y = f(x)

using \mapsto; otherwise, one mixes up the element xXx \in X with the domain XX 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?

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?

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,wx,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?

Evidently PP and QQ relate elements of the same sets, PX×X,QY×Y,SX×YP \subseteq X \times X, Q \subseteq Y \times Y, S \subseteq X \times Y. It sounds as though he’s allowing XX and YY to be different.

SS 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?

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?

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 SS is just a morphism, S:(X,P)(Y,Q)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?

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?

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?

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?

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?

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?

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?

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?

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

Post a New Comment