Summer Fun

Every year, ANU offers summer scholarships in order to allow undergraduates in Australia or New Zealand to get a taste of research. These scholarships cover transport costs, accomodation and three meals a day at one of the residential colleges as well as spending money. There are also regular social events, both amongst the summer scholars (who come from a wide range of disciplines and locations) and within the particular research schools and departments.

So if you like logic, come on over! There are a number of logic projects available, with more to come. During the summer, there is also the Logic Summer School, as well as a stream of international visitors. I have hacked up a little page with some more info, as well as details of the projects that I am offering.

If this sounds like fun to you, then drop me a note at jonathan(dot)cohen(at)anu(dot)edu(dot)au. Apply the uniform substitution (dot) --> . and (at) --> @ to get my email address. Similarly, if you know anyone who may be interested then go ahead and pass on the details.

Workshops Day 2

It's lunchtime at StreetFest, so I'll take the opportunity to post a bit about what's been going on!

John Baez kicked off the day with a talk on higher dimensional gauge theory. The basic idea here seems to be that you figure out what happens when particles move around on a manifold with odd curvature. The interesting thing is that it is no longer possible to compare, say, two vectors but it is only possible to compare them relative to some path which brings them together. The other cool thing I found out about is something called a "thin homotopy". This is just like Ye Olde Homotopy, except that it sweeps out no area. For instance a homotopy which only does stuff like backtracking along a path is a thin homotopy. Working modulo thin homotopies seems to be the thing to do in this area. Anyway, the slides from the talk are up here.

After that there was a really fun talk by Timothy Porter, who has a wonderful sense of mathematical humour! He was speaking about topological quantum field theories and I managed to follow along a bit and see what manifolds and cobordisms have to do with braided monoidal categories. Neat stuff!

Next up was Andrey Lazarev who spoke about graph cohomology. I don't really understand this stuff so I won't say any more.

In between the talks I had some nice discussions with category theorists about higher dimensional rewriting, noncommutative logic and that sort of jazz. I'll probably hang around at Streetfest for the rest of today and tomorrow - this post will be updated later with the afternoon's talks. Mayhaps someone else will blog details of the philosophy workshop...

Update (26/7): Not many more of the talks were logic related so I decided to stop posting details.

Workshops Day 1

This morning I hung out at StreetFest and learned a bunch of stuff about category theory. First up was Ross Street who spoke about centres in monoidal categories. A monoidal category is essentially a category that carries a "monoid" structure, which may be thought of as a tensor product. An example from logic is the tensor product (conjunction) of linear logic. Or, if you prefer other language, the "fusion" of relevant logic. Or of Lambek Calculus or...

Here's a nice way to think about this. Suppose we only have the tensor-like conjunction. Then, a formula looks something like A ⊗ B ⊗ C. Represent each of A, B and C as a string connected between two bars. So, we have something that looks like:

The centre of this widget is all those formulae A such that A ⊗ X ≡ X ⊗ A for all other X. It turns out that the centre of a moinoidal category is always "braided". That means, if A and B are both in the centre and we go from A ⊗ B to B ⊗ A, then it matters whether we passed A "under" B or A "over" B. This corresponds to the following two situations for our strings:


Remember that the strings are tied at the top and the bottom, so there is no way to pass from one "braiding" to the other (without cutting the strings of course!). Thus, the centre of a monoidal category forms a "braided" monoidal category. These crazy cats crop up all over the place. Quite famously, they are related to topological quantum field theories! The idea is that we imagine some particles (two say. Perhaps named A and B...) floating around in space (on a plane, say). Then, they can pass around each other in all sorts of fanciful ways. If we trace the history of where each particle has been, lo and behold we have a braiding!

As it happens, there are two ways to define a centre in a monoidal category. On the one hand, we can postulate a bunch of commutative diagrams which say that we can shift elements in the centre around however we please. This is called the "lax" centre. The other way is more refined and related to some constructions in algebra (which I have not fully grokked yet!). Essentially, each object, A, in the centre comes equipped with a bunch of "natural transformations", one for each object X in the category, which take A ⊗ X to X ⊗ A. Interestingly enough, these two notions of centre are not always the same (something I hadn't realised before today).

The other highlight of the categorical morning was Robin Cockett, who gave a beautiful talk about turning differential calculus into category theory! That is, we search for categorical analogues of "differentiable" and "smooth" functions. The idea is that we extend lambda calculus with the ability to do differentiation. Except, we do this in a category theoretic setting. This was quite a fun talk with lots of neat diagrams (no one can draw diagrams like a linear logician can!). Rather than waddle may way through discussing this stuff, I'll just point you to the paper (hot off the presses!) wherein all of this is done:

Differential Categories; R Blute, JRB Cockett, RAG Seely

I skipped out on the afternoon's categorical proceedings in order to hop along to the philosophical methodology workshop. Today's events were mainly devised for a group of visiting undergrads and had philosophers explaining their own take on general methodologies for doing philosophy. This was quite a nice insight into the philosophy world for me (since I am, after all, a philosophical neanderthal...). One of my motivations is that I would like to understand how people come up with conjectures and build arguments, so that I cant teach a computer to do the same! I managed to catch two of the talks. First up was Alan Hájek, who spoke about "Philosophical Heuristics". This was quite a neat talk explaining some general procedures for examining philosphical arguments in order to find bogus features. The general techniques are very familiar from maths, though there I think the situation is often a lot clearer since, for instance, definitions are clearly delineated! Quite amusingly, and rather contentiously by Canberra standards, his handout labelled nonclassical logics as weird... After that, Dave Chalmers spoke about "Terminological Disputes" - general ways of deciding whether an argument/disagreement is "terminological". That is, whether there is only a disagreement because the different parties parse a certain term differently.

Tomorrow I will once more hang out at StreetFest for part of the morning and then head over to see what else the philosphers have to say about methodology!

Workshops Galore

The next two weeks are fairly busy this end of the world. Starting tomorrow is the ANU wing of StreetFest, so a bunch of category theorists will descend on Canberra to mark Ross Street's 60th birthday. I'll be going along to a few of the talks (those whose abtracts don't fly too far over my head!). Coinciding with Streetfest, the philosophers are putting on a workshop on philosophical methodology, which I will try to get to (well, at least to a bit of it!). Following hot on the heels of that is an instructional program and workshop on noncommutative geometry and index theory, which I will also be attending. I'll post details of any talks that are directly related to logic.

Blogicians

Both Kenny Easwaran (Antimeta) and Gillian Russell (logicandlanguage.net) were at ANU this week. Gillian was game enough to lead a NotYASS session, despite only arriving in Canberra the same day (if you'll pardon my colloquialism, on ya Gil!). At any rate, here is a pic of the three of us. Unfortunately, we couldn't seem to agree what camera to look at (maybe their pictures fared better)...

What do you mean?

How do I understand what people say? It seems like an impossible thing to do. Every day people utter sentences I have never heard before. And I take it all in and understand them. Bizarre! The most natural explanation of this phenomenon is that I understand what each of the words mean individually and I have some rudimentary understanding of how to put them together to form sentences. But, come now, that can't be all there is to it! Let's see what the linguists have had to say about this.

Compositionality is the principle which states that the meaning of a compound expression is a function of the meaning of its parts and of the syntactic rule by which they are combined. It is this second part which carries most of the import.

Even in purely logical endeavors, the situation is not cut and dry. For instance, in the substitutional interpretation of classical predicate logic, one can derive (∀ x)φ(x) from φ(a), where a is arbitrary. This breaks compositionality. That is, how is one to find the correct interpretation of (∀ x)φ(x) given only one φ(a)? One possibility is to add an infinitary rule, which essentially identifies the universal quantifier with an infinite conjunction. This proposal suggests to me that something like descriptive set theory may be useful, wherein hierarchies of sets correspond to suitable classes of first order sentences.

Not every linguist is too chuffed with compositionality and many counterexamples have been proposed. However, for the most part, these can be dealt with by modifying and/or enriching the syntactic aspect. One of the objections is sentences such as the following:

(1) Joseph said that a child had been born who would become ruler of the world.

Sentence (1) is ambiguous. That is, will the child become ruler of the world in the future of Joseph or in his past? Both are possible. One of the most interesting approaches to dealing with this is similar to how one deals with de dicto/de re ambiguities. That is, one invokes the following:

(*) Different possible interpretations of a sentence correspond to different derivations.

"Derivations" here is taken to mean something along the lines of a derivation in a categorial grammar. Or, say, in parsing. This is quite appealing and is a good motivation for studying isomorphisms of derivations. That is, one would like a natural notion of isomorphism, wherein isomorphic derivations correspond to the same interpretation of a sentence. Is it possible that breaking derivations up into isomorphism classes deals with ambiguity? This does seem like a plausible notion, though one would have to assess the actual notion of isomorphism before being fully convinced.

So, are there sentences which are not compositional? Well, if so, then they would be very odd sentences indeed. That is because every recursively enumerable language can be generated by a compositional grammar. Unfortunately, the way this works is to pick and choose your particular grammar. Not so nice. As a result, one will always eventually run into trouble when using a particular compositional grammar.

So, one possible explanation of how I understand what you say is that I am very good at picking the correct compositional grammar to use in the correct situation. Or, more likely, I have evolved a particular grammar that works quite well in most situations. This is evidenced by the fact that I, like all other children, probably uttered a sentence such as:

(2) I seed two mans

The problem with (2) is, of course, that whatever grammar I was using at the time was a bit too weak and had rules for changing the tense and for pluralising that are not always correct. I'm a bit better at doing these things now...

(The technical parts of this post are mainly based on T.M.V. Janssen's article in The Handbook of Logic and Language)

NICTA L&C

NICTA's Logic and Computation Program has finally decided to admit that I exist. They may, of course, come to rue this decision... And, no, I am not either of the two people in the photo at the top of that page. Heck, I don't even know who they are! Although, that picture isn't on any other group member's biography page. Hmmm....