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.

August 22, 2008

Melliès on Functorial Boxes

Posted by David Corfield

John once mentioned the slides of Paul-André Melliès’s talk Functorial boxes in string diagrams. Now you can read a 44 page tutorial on this topic.

I’m a little confused as I noted back then that I saw a resemblance between Peirce’s ‘cuts’ or ‘seps’ for negation and Melliès’s treatment of negation from page 80 of the slides onwards. However, the slides end at p. 78, and there is no mention of negation in the tutorial.

Anyway, in view of the fact that negation may be construed as a monoidal functor, perhaps Peirce had an amazingly astute premonition of things to come.

How interesting! I’ve just seen that Fernando Zalamea (mentioned in this post as a fellow admirer of Lautman) has a paper Towards a Complex Variable Interpretation of Peirce’s Existential Graphs. I’ll just go and read that over a coffee.

Posted at August 22, 2008 2:33 PM UTC

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

11 Comments & 0 Trackbacks

Re: Melliès on Functorial Boxes

I have tried to view more than the first page a few times. It keeps crashing adobe within the browser. It may be this machine. Anyone else have this problem?

Posted by: Scott Carter on August 22, 2008 8:09 PM | Permalink | Reply to this

Re: Melliès on Functorial Boxes

Works fine for me in any of five different ways: Acrobat Reader embedded in a Firefox tab, standalone Acrobat, kpdf, xpdf, and gv.

Posted by: Tom Leinster on August 22, 2008 11:09 PM | Permalink | Reply to this

Re: Melliès on Functorial Boxes

Oh, I was assuming you meant the first pdf link (the slides). But I guess you meant the second (the tutorial). If I just click on the link to the tutorial then Firefox gives me an embedded Acrobat Reader which, like yours, fails to read past the first page. However, if I save the tutorial (by right-clicking on the link) then I can view it fine with any of the four pdf viewers mentioned in my previous comment — including Acrobat. Odd.

Posted by: Tom Leinster on August 23, 2008 2:10 AM | Permalink | Reply to this

Re: Melliès on Functorial Boxes

Tom wrote:

Odd.

This is known problem — especially for large PDF files, I think. It happens, for example, when I use Firefox to access the copy of Derek Wise’s thesis on my website.

Posted by: John Baez on August 23, 2008 9:37 PM | Permalink | Reply to this

Re: Melliès on Functorial Boxes

I am in the process of changing my mind , anyway. It opened fine in Safari, and my window’s machine is ready to be euthenized.

Posted by: Scott Carter on August 24, 2008 6:12 PM | Permalink | Reply to this

Re: Melliès on Functorial Boxes

Also worth reading is Melliès’s Categorical Semantics of Linear Logic. His idea (p. 186) that

logic is polychrome, not monochrome,

has a thoroughly Peircean ring to it. The idea is that

several universes of discourse … generally coexist in logic, and that the purpose of a proof is precisely to intertwine these various universes by applying back and forth modalities … Each universe of discourse implements its own body of internal laws.

Different universes are coloured differently in Melliès’s diagrams. It’s all highly reminiscent of Peirce’s gamma graphs.

On p. 25 of these notes, we read of the tincturing of these graphs that

This was done not only in order to mark different kinds of possibilities, but also to mark different kinds of actualities, different kinds of possibilities consisting of ignorance, of variety, of power and of futurity, and to mark different kinds of intention.

Modalities include: Ordinary actuality, Special actuality, Subjective possibility, Objective possibility, Interrogative mood, Freedom/ability, Metaphysical necessity, Purpose/intention, Imperatives, and The compelled.

But already at the level of negation there’s a difference between Peirce and the monoidal approach. Negation for the latter is a functor from a category to its opposite, where the tensor is ‘and’ in the category and ‘or’ in its opposite. This allows it to be a monoidal functor

not(a or b) = not(a) and not(b).

But when Peirce used a circle or box for negation, the tensor operation inside remained the same, i.e., inside and outside two inscriptions correspond to their conjunction. So it looks like Peirce’s box is rather different.

Posted by: David Corfield on August 26, 2008 12:54 PM | Permalink | Reply to this

Re: Melliès on Functorial Boxes

But when Peirce used a circle or box for negation, the tensor operation inside remained the same, i.e., inside and outside two inscriptions correspond to their conjunction. So it looks like Peirce’s box is rather different.

That’s right: Peirce in effect uses just two primitives (“and” and “not”). The “or” operation is derived.

The specific rules of inference used by Peirce are actually very clever (I particularly have in mind his rule of “iteration”) and have been rediscovered or partly rediscovered over the years (e.g., by Paul Taylor – I’d have to look it up to see what he calls it, but he seems to deem it significant). It is this rule which Gerry and I sought to analyze in our Alpha paper in a linear logic kind of way.

An Alpha graph is a graphical expression which corresponds to a Boolean formula, consisting of (labeled) “spots” and boxes (what Peirce calls “seps”, short for lines of separation) in the plane (called the “sheet of assertion”). A labeled spot can be thought of as a propositional variable. To conjoin two Alpha graphs, just juxtapose them in the plane; to negate an Alpha graph, surround it by a box. The empty sheet of assertion represents the constant “true”.

The three rules of inference (really rule schemes) are

  • “Weakening”: An Alpha graph GG can be weakened by excising any subgraph HH which is surrounded by an even number of boxes, or by adding in as a subgraph any Alpha graph HH so that it is surrounded by an odd number of boxes. The soundness of this rule for propositional logic is by an induction where the base cases are the inferences G=G HG G = G^\prime \wedge H \to G^\prime ¬(G )¬(G H)=G\neg(G^\prime) \to \neg(G^\prime \wedge H) = G
  • One may freely remove or insert a pair of boxes, one enclosing the other, provided there are no spots between them. This just corresponds to the bi-implication G¬¬GG \leftrightarrow \neg \neg G
  • “Iteration”. In this rule, if HH is a subgraph of GG, one can freely insert a second copy of HH inside GG as another subgraph, provided the copy is not placed outside any box containing HH [I hope I’ve remembered this correctly; it’s been a while]. This rule is invertible (“de-iteration”). Again the soundness of these rules is proved by an induction where the base case corresponds to a bi-implication H¬G H¬(HG )H \wedge \neg G^\prime \leftrightarrow H \wedge \neg(H \wedge G^\prime) The forward implication for this case follows by applying the operator HH \wedge - to an instance of weakening. The backward implication uses standard properties of the cartesian product \wedge in conjunction with the fact that there is an arrow H¬(HG )¬G .H \wedge \neg(H \wedge G^\prime) \to \neg G^\prime.

In terms of categorical linear logic, this last arrow corresponds to a strength of the contravariant functor ¬\neg on a *-autonomous category, as I mentioned in comments on Week 268.

So Gerry and I explain the iteration rule as an amalgamation of standard properties of cartesian product together with a fact well-known to categorical logicians: that in the theory of symmetric monoidal closed categories VV, every definable functor VVV \to V (whether covariant or contravariant) carries a canonical strength. The fact that it’s all about strengths makes it a kind of monoidal approach, but I ought to think about this myself a little further in connection with the Week 268 discussion and hopefully tie some of these threads together more tightly.

Posted by: Todd Trimble on August 26, 2008 9:03 PM | Permalink | Reply to this

Re: Melliès on Functorial Boxes

Thanks for the nice summary, Todd! I never really understood what was going on with these alpha graphs until now.

Have you ever thought about comparing Peirce’s alpha graphs with Spencer-Brown’s Laws of Form, and particularly his primary algebra? They’re similar: for example, both count a blank page or ‘void’ as a legitimate expression, both allow you to put a kind of box around something, and both say that two boxes around something is the same as none.

Of course, Spencer-Brown’s discussion is famously gnomic and grandiose, as suited the late 1960s; I hope Peirce’s explanations were clearer. Also, Spencer-Brown claimed he could prove the Four Color Theorem, Fermat’s Last Theorem, Goldbach’s Conjecture, and most recently the Riemann Hypothesis; I imagine Peirce was considerably more level-headed.

But still, the similarity of these systems is interesting.

Now I see that the Wikipedia article I cited actually mentions Peirce. It’s a strange article: it seems to do a decent and fairly erudite job of talking about whether Spencer–Brown’s Laws of Form were just Boolean logic in disguise. But it runs off the rails a bit when it claims:

The primary arithmetic is analogous to the following formal languages from mathematics and computer science:

  • A Dyck language of order 1 with a null alphabet;
  • The simplest context-free language in the Chomsky hierarchy;
  • A rewrite system that is strongly normalizing and confluent.

It’d be better to say the primary arithmetic is an example of a rewrite system that’s strongly normalizing and confluent.

Hmm. Another Wikipedia article explicitly claims that Spencer-Browns primary algebra is isomorphic to Peirce’s ‘entitative graphs’ (= alpha graphs).

Posted by: John Baez on August 27, 2008 6:18 AM | Permalink | Reply to this

Re: Melliès on Functorial Boxes

Yeah, just as Peirce’s system of Alpha graphs on nn labeled spots can be reckoned as the free Boolean algebra on nn elements, Spencer-Brown’s primary algebra corresponds the “spotless” case where n=0n = 0, thus giving the free Boolean algebra on 0 elements, which is the Boolean algebra 2.

The first time I saw Spencer-Brown’s little book was as an undergraduate, and I had no idea what to make of it. I found the mystical prose hard to follow but curious and fascinating, though, as if I were at a wild party talking to someone under the influence of LSD, but then after a while pretty tiresome and no longer enjoyable, for exactly the same reason.

It’s been so long that I’ve looked at it that I can’t swear that he doesn’t extend the system so as to rediscover Alpha. And I guess you know that Louis Kauffman speaks enthusiastically about ‘the calculus of indications’ in his On Knots, and seems to have some creative readings of the ‘knottiness’ of certain infinite graphs. So my interest is still piqued after all, and maybe I’ll go back one day and take another look.

Posted by: Todd Trimble on August 27, 2008 7:02 AM | Permalink | Reply to this

Spencer-Brown’s Laws of Form; … on Functorial Boxes

I think that Louis Kauffman is right to enthuse over Spencer-Brown’s Laws of Form:

* 1969. London: Allen and Unwin, hardcover.
* 1972. Crown Publishers, hardcover: ISBN 0-517-52776-6
* 1973. Bantam Books, paperback. ISBN 0-553-07782-1
* 1979. E.P. Dutton, paperback. ISBN 0-525-47544-3
* 1994. Portland OR: Cognizer Company, paperback. ISBN 0-9639899-0-1

See discussion examples, citations, hotlinks, and the connection to Groupoids, at:

Laws of Form
From Wikipedia, the free encyclopedia

I don’t dispute the Trippy association (hey, first published in 1969, right?) but I have done some research on Imaginary Logic triggered by that strange subtle little book.

Anyone else here have strong feelings about this?

Posted by: Jonathan Vos Post on August 27, 2008 11:08 PM | Permalink | Reply to this

Re: Melliès on Functorial Boxes

Todd wrote:

It’s been so long that I’ve looked at it that I can’t swear that he doesn’t extend the system so as to rediscover Alpha.

According to Wikipedia, Spencer–Brown first introduces something called the primary arithmetic, which corresponds to the free Boolean algebra on no elements, namely 2. But then he introduces the primary algebra, which introduces variables. This could be isomorphic to Peirce’s Alpha calculus.

So my interest is still piqued after all, and maybe I’ll go back one day and take another look.

The Wikipedia article might be quicker to read, though it’s a bit bizarre in its own way. It’s not very scholarly, but a full-blown scholarly investigation of Spencer–Brown’s ideas seems like overkill to me.

Posted by: John Baez on August 28, 2008 3:00 AM | Permalink | Reply to this

Post a New Comment