September 2017 - Categories - categories.org.au

Functionally complete/universal basis for graph homomorphisms?
by Mike Stay 02 Oct '17

02 Oct '17

The Sheffer stroke / NAND gate suffices to implement any function from 2^n -> 2. I'm looking for a similar universal basis for graph homomorphisms from Omega^n -> Omega, where Omega is the subgraph classifier with two vertices t, f and five edges in:t->t, out1:t->t, out2:t->f, out3:f->t, out4:f->f. There's obviously a finite set of operations that covers all graph homomorphisms from Omega^n to Omega, because the set of all operations of that form is finite. But how small can that set be? I'd be satisfied with a formula parametric in n, but surprised if it actually depends on n; I'd expect it to be a finite set of binary operations. -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

5 8

Fred
by Ernest G. Manes 28 Sep '17

28 Sep '17

September, 2017. Fred E. J. Linton. For most of the time I knew him, I kept secret what E. and J. stand for, being of the impression that almost nobody knew and it was not my place to tell. I think it is OK to tell you now. Ernest and Julius. Fred spent his whole teaching career at Wesleyan University in Middletown Connecticut. I entered the graduate program there in 1963-64, at the tender age of 20. I do not recall meeting Fred during that first year. In my second year, I developed an interest in categories from my coursework. But Fred wasn't there. He was visiting Mac Lane in Chicago. By the end of the second semester, I knew I wanted to meet him. By good fortune, we both attended the NSF summer program (six weeks long!) in homological algebra at Bowdoin College (principal lecturer Ernst Snapper of Dartmouth). We met right away, and immediately played tennis. I have two memories regarding Fred from this time. (1) Everybody ate lunch and dinner in the dining hall. At one lunch, they served chili. In order to break up the crackers into small pieces, Fred put the packet on the table and applied great force with his elbow. The second time, Alex Rosenberg held his ears. (2) As many of you have noticed, Fred often napped in between talks at a conference. Perhaps you took this as a sign of age. Not so. Fred always did this. At the Bowdoin conference 52 years ago, there was also a music camp with many prominent musicians in residence. Two violinists came over to Fred, asleep on a chair in the lounge, and played Brahm's Lullibye. It didn't wake him up. In Middletown, Fred was very active in folk dancing. His group was very professional and gave quite astounding performances at local venues. This was a major interest in his life. In 1966, we arranged with Wesleyan that I could follow Fred to Zurich in order to attempt to write a thesis. About a week before we were to leave, I asked him about the research focus of the group of category theorists visiting the ETH. He simply replied "triples" with no further explanation. I wondered what on Earth I was getting into. Fred often began a conversation with word play, even if he hadn't seen you for years. His puns drew on English, German, French and Italian. Once when the two of us were trying to negotiate downtown San Juan (at one of Jon Beck's conferences) with neither of us knowing Spanish, he asked for information in Italian; he got strange looks, but it seemed to work. I'm not sure how I settled on "A Triple Miscellany" for a thesis title, but Fred preferred several variants. His favorite was "A Missal tripleary". As recently as a few months ago in Schenectady, Fred chided me for not using ..Missal... Beginning 1969-1970, Fred and I joined a lively group of category theorists for postdocs at Dalhousie University. The one shortcoming for Fred was the lack of a good folk dancing group, so he started one for amateurs. He somehow convinced my wife and I to join. We had fun, but I never learned the Miserlou. Recently I mentioned the names of one or two from that group to Fred. He had kept up with them. I am a graduate of Los Angeles High School and so I grew up steeped in the culture of fixing cars. Fred turned to me for advice on various car problems. One time, his engine just wouldn't start and he asked for help. There was no fuel coming through to the carburetor. Now any California kid knows that either the fuel pump was shot (usually the problem) or the fuel line to the pump was clogged (unlikely). To eliminate the second case, I explained to Fred that if he removed the fuel cap and blew into the tank, I could watch the fuel line (which I had removed from the fuel pump) to see if gasoline was coming out. As it turns out, the fuel line was indeed plugged. As a result the back pressure sprayed gasoline in Fred's eye and he had to visit the emergency room. Fred was a very kind person and often would expend considerable effort to do something good for somebody else. It was his style not to end up in a situation where plans he had promised did not materialize. When he attempted to do things for me, the first I heard about it was when it happened. As an example, I had mentioned to him early on that the Wesleyan stipend might be difficult to live on in Switzerland. He said nothing. After attending the first lecture (very memorable for me --Jon Beck had defined what a triple is), and after the tea and cookies that followed, Fred told me to follow him. We were joined by a gentleman I didn't know. He and Fred spoke in German and it was more complicated than I could follow. Then we proceeded to walk for ten minutes in a basement labyrinth that equaled any in a big city hospital, eventually coming to a very dark alcove with a small "cage". The first gentleman spoke at some length with the gentleman inside the cage; this was in Swiss German which neither Fred nor I could follow. Eventually a piece of paper was produced which I was asked to sign. They then put in my hand the biggest pile of cash I have ever personally held in this life. It was enough for my wife and I to eat on for the balance of the year. (Of course, Beno Eckmann gets credit for that too). My mathematical career was jump-started by the fact that Saunders Mac Lane convened a seminar at Chicago based on my thesis, only four months after it became clear I would finish. I realize now that Fred must have played a substantial role in making this happen. Damn! I miss him. Ernie Manes [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

12 14

distributive squares
by Tom Hirschowitz 27 Sep '17

27 Sep '17

Hi all, My student Clovis Eberhart and I were led to consider certain ‘distributive’ squares of categories and functors, in the sense that doing left then right Kan extension (of presheaves) along one side is isomorphic to doing right then left along the other. Does anyone please know if such squares have been studied somewhere? Best wishes to all, Tom [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

1 0

Re: The use-mention distinction and category theory
by Baruch Garcia 27 Sep '17

27 Sep '17

Thanks, Gershom. While Lawvere correctly points out that some try to misuse Godel's theorem, I disagree with his *philosophical *perspective of the equivalence of Cantor's diagonal argument and Godel's diagonal lemma. The former does not employ the use-mention distinction while the latter does. This is what gives rise to the "paradoxical" nature of Godel's theorem. Please read Quine's "The Ways of Paradox" for more. Regardless, Lawvere's approach to Godel and Tarski provides an important bridge between computer science and category theory. Best, BG On Tue, Sep 26, 2017 at 12:00 PM, Gershom B <gershomb(a)gmail.com> wrote: > I would suggest that one approach to the use-mention distinction is > given in topos theory, or more generally in categorical logic, when we > can talk about the "internal logic" of a category, and discuss objects > of categories from both the internal and external standpoints. > > A common case of this arises in Mike's message when he discusses the > internal hom. Godel, Halting, etc. all can be seen as statements based > on a particular structure surrounding the internal hom as in [1]. > > [1] https://ncatlab.org/nlab/show/Lawvere%27s+fixed+point+theorem > > Cheers, > Gershom > > On Tue, Sep 5, 2017 at 1:36 PM, Mike Stay <metaweta(a)gmail.com> wrote: >> On Sun, Sep 3, 2017 at 1:19 PM, Baruch Garcia <baruchgarcia(a)gmail.com> > wrote: >>> Hello, >>> >>> I was wondering if someone of the categories list could answer this >>> question: >>> >>> In Godel's/Tarski's theorem and the Halting problem, the use-mention >>> distinction (e.g. Boston is populous, but "Boston" is disyllabic) is >>> essential. Is there an analog to the use-mention distinction in > category >>> theory or is the use-mention distinction just its own principle > independent >>> of category theory? >> >> There's something like a distinction between use and mention in a >> symmetric monoidal closed category. Given a morphism f:X -> Y, >> there's the "name" of the function curry(f):I -> X -o Y, where I is >> the monoidal unit and -o is the internal hom. The evaluation morphism >> takes a value g of type X -o Y and a value x of type X and returns >> uncurry(g)(x). >> >> >> -- >> Mike Stay - metaweta(a)gmail.com >> http://www.cs.auckland.ac.nz/~mike >> http://reperiendi.wordpress.com >> [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

1 0

The use-mention distinction and category theory
by Baruch Garcia 27 Sep '17

27 Sep '17

Hello, I was wondering if someone of the categories list could answer this question: In Godel's/Tarski's theorem and the Halting problem, the use-mention distinction (e.g. Boston is populous, but "Boston" is disyllabic) is essential. Is there an analog to the use-mention distinction in category theory or is the use-mention distinction just its own principle independent of category theory? Any suggestion, insight, clarification would be appreciated. Many Thanks! Baruch [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

4 3

Announcement PSSL 102
by Xabier Garcia Martinez 26 Sep '17

26 Sep '17

Dear friends and colleagues, We would like to announce that the 102nd edition of the PSSL (Peripatetic Seminar on Sheaves and Logic) will be held at the University of Santiago de Compostela, Spain, the weekend of 13th - 14th of January 2018. Online registration is already available via the seminar webpage: http://www.usc.es/regaca/pssl102/ We hope to see you soon, Xabier Garcia-Martinez Tim Van der Linden [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

1 0

"Logic for Children" - A workshop (CFP)
by Eduardo Ochs 24 Sep '17

24 Sep '17

Hi list, the following workshop - that will happen in the UniLog 2018, in Vichy, France, in june 16-26 2018 - has some space for categorical and category-related talks... links: http://www.uni-log.org/wk6-logic-for-children.html http://www.uni-log.org/start6.html The deadline for submissions is quite soon, unfortunately - october 5. Here is the description of the workshop, taken from the link above: LOGIC FOR CHILDREN When we explain a theorem to children -- in the strict sense of the term -- we focus on concrete examples, and we avoid generalizations, abstract structures and infinite objects. When we present something to "children", in a wider sense of the term that means "people without mathematical maturity", or even "people without expertise in a certain area", we usually do something similar: we start from a few motivating examples, and then we generalize. One of the aims of this workshop is to discuss techniques for particularization and generalization. Particularization is easy; substituing variables in a general statement is often enough to do the job. Generalization is much harder, and one way to visualize how it works is to regard particularization as a projection: a coil projects a circle-like shadow on the ground, and we can ask for ways to "lift" pieces of that circle to the coil continously. Projections lose dimensions and may collapse things that were originally different; liftings try to reconstruct the missing information in a sensible way. There may be several different liftings for a certain part of the circle, or none. Finding good generalizations is somehow like finding good liftings. The second of our aims is to discuss diagrams. For example, in Category Theory statements, definitions and proofs can be often expressed as diagrams, and if we start with a general diagram and particularize it we get a second diagram with the same shape as the first one, and that second diagram can be used as a version "for children" of the general statement and proof. Diagrams were for a long time considered second-class entities in CT literature ([2] discusses some of the reasons), and were omitted; readers who think very visually would feel that part of the work involved in understanding CT papers and books would be to reconstruct the "missing" diagrams from algebraic statements. Particular cases, even when they were the motivation for the general definition, are also treated as somewhat second-class -- and this inspires a possible meaning for what can call "Category Theory for Children": to start from the diagrams for particular cases, and then "lift" them to the general case. Note that this can be done outside Category Theory too; [1] is a good example. Our third aim is to discuss models. A standard example is that every topological space is a Heyting Algebra, and so a model for Intuitionistic Predicate Logic, and this lets us explain visually some features of IPL. Something similar can be done for some modal and paraconsistent logics; we believe that the figures for that should be considered more important, and be more well-known. References [1]: Jamnik, Mateja: Mathematical Reasoning with Diagrams: From Intuition to Automation. CSLI, 2001. [2]: Krömer, Ralf: Tool and Object: A History and Philosophy of Category Theory. Birkhäuser, 2007. Call for papers Topics of interest to the workshop include, but are not limited to: * Ways to visualize logics or other algebraic structures * (The many roles of) diagrams in Category Theory * Categorical semantics (e.g. topos theory, linear logic, type theory) * Translations between digrammatical languages and formal languages Contributed talks should not exceed a duration of 30 minutes including discussion. To submit a contribution, please send a one-page abstract by October 5, 2017 to: <eduardoochs(a)gmail.com>. Cheers =), Eduardo Ochs http://angg.twu.net/math-b.html http://angg.twu.net/math-b.html#logic-for-children-unilog-2018 [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

1 0

Re: Cartesian morphism ~~> fibration
by David Roberts 21 Sep '17

21 Sep '17

In fact there's a more general construction, recorded in the Stacks Project https://stacks.math.columbia.edu/tag/08NF and in the case that the codomain (only!) is fibred in groupoids it shows that any cartesian functor factors as an equivalence of fibrations followed by a fibration. Regards, David On 21 Sep. 2017 7:17 pm, "Thomas Streicher" < streicher(a)mathematik.tu-darmstadt.de> wrote: >> So I guess this extends your example where the codomain is a discrete >> fibration, merely having to replace the domain by an equivalent category. >> This makes the original cartesian functor a Street fibration, I believe. > > Indeed every functor F between groupoids is a Street fibration and thus > equivalent to a Grothendieck fibration in the sense that there is a > fibarion P and an equivalence E such that F = PE. > > Interesting that this extends to fibered functors! > > Thomas > [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

1 0

Re: Cartesian morphism ~~> fibration
by Thomas Streicher 21 Sep '17

21 Sep '17

> So I guess this extends your example where the codomain is a discrete > fibration, merely having to replace the domain by an equivalent category. > This makes the original cartesian functor a Street fibration, I believe. Indeed every functor F between groupoids is a Street fibration and thus equivalent to a Grothendieck fibration in the sense that there is a fibarion P and an equivalence E such that F = PE. Interesting that this extends to fibered functors! Thomas [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

1 0

Re: Cartesian morphism ~~> fibration
by David Roberts 21 Sep '17

21 Sep '17

Dear Thomas, Thanks for that example (and to someone else who, off-line, gave me the example where B is trivial). Here's the version for categories fibred in groupoids https://stacks.math.columbia.edu/tag/06N7 So I guess this extends your example where the codomain is a discrete fibration, merely having to replace the domain by an equivalent category. This makes the original cartesian functor a Street fibration, I believe. This is all in the context of stacks, and in particular algebraic or other presentable sacks, which is what I'm looking at, though in greater generality than the Stacks Project. David On 21 Sep. 2017 3:19 am, "Thomas Streicher" < streicher(a)mathematik.tu-darmstadt.de> wrote: >> I'm trying to find a reference for the following result, if indeed it is >> true. > > I think the claim is wrong in general. Let P : X->B be a fibration of > categories with a terminal object, i.e. P has a right adjoint right > inverse One. Then One : Id_B -> P is a cartesian functor though > itself not a fibration in general (e.g. B = 1 and X the ordinal 2 then > One picks 1 from 2 which has empty fibre over 0). > > However, if P is a fibration and Q is a discrete fibration and F is a > functor with QF = P then F is a fibration iff F is a cartesian functor > from P to Q. > > Thomas > [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

1 0