Sunday, March 09, 2008

Representation theorems

In the Dunn book on algebraic logic, there is a chapter on something called representation theorems. This was not something I'd come across before and it was not really explained. The first question is: what is a representation theorem? The answer is that it seems to be a canonical way of mapping the structure in question into a set-theoretic structure which contains operations on the set structure that correspond to the operations on the original structure.

The next question is: why are these interesting? I'm not really sure. The set-theoretic structures have the benefit of being extensional. That could be an epistemological benefit if the original structures aren't obviously extensional. Some of the structures are a little arcane though. For example, the representation of fusion, relevant implication, and the ternary accessibility relation are rather involved. I'm not going to include them; I don't have the reference handy. It isn't simplicity that is the aim of the mapping, per se.

The project of showing that all of math can be done in set theory was something that I thought was more of an early 20th century phenomenon. This seems to be reflected in the things cited. They are all before 1950. Nothing from the set theory is used to reveal anything in the original structures, so it isn't a case of translating from the original language, such as lattice theory, to set theory, finding something neat, then translating the result back into the original language. Some of the representations are technically quite nice but I'm unsure why one would be interested in them in the first place outside of the desire to show that the original structures can be found in the universe of sets.

Generally, Dunn's book is quite good, but it is kind of frustrating that some of the more heavy duty technical parts of the book, such as the representation chapter and subsequent representation theorems, are not motivated. More importantly, the idea and point of a representation theorem are not explained at all. They haven't gotten much clearer as the book goes on. [Edit: The comments clear things up a lot.]

4 comments:

Greg Restall said...

Here's one way to think of the utility of representation theorems: think of an algebra for a modal logic. You've got lots of propositions (or values) in the algebra, which is a boolean algebra with some extra operators for necessity and possibility.

What's a representation for this algebra? It's a concrete algebra in which the propositions (values) are subsets of some underlying carrier set.

What's that? Well, think of the carrier set as a set of worlds, and the proposition as represented by the worlds at which it's true.

A representation theorem is a soundness/completeness theorem connecting the class of algebras in question with some concrete worlds model.

That's why they're philosophically interesting.

Why they're mathematically interesting is similar: concrete set-theoretical structures are often more easily understood or easily classified, when compared to some large abstract class of algebras.

Set theoretic representations provide (or motivate, or give rise to) interpretations, whether we're thinking mathematically or philosophically.

Does that explanation help?

joyrexus said...

Given your interest in Brandom ... recall that he proves a representation theorem about consequence relations, relating them to incompatibility, to help ground his incompatibility semantics. See the handout to Lecture 5 of the Locke Lectures, page 6. A representation theorem for his incompatibility semantics is also discussed at length in his Saying & Doing lectures, Lecture 9.

From p. 1 of Lecture X: "The discussion of this incompatibility semantics is going to be in three phases. The first one we did last time. That’s showing that any consequence relation, whether it’s a material consequence relation or the consequence relation that’s generated by some standard logic (basically any logic except relevance logic), can be codified by an incompatibility semantics. It can be exhibited as an incompatibility entailment as generated by incompatibilities on the sentences the consequence relation is defined on. That was the general representation theorem which involved a soundness result and a completeness result relating the initial consequence relation to the incompatibility entailments."

I find some of his looser formulations quite helpful, e.g.: "Normally, when you’re doing proof theory, you have a consequence relation that’s defined by some axioms and some rules, and then you’ve got a semantic notion of what follows from what, and when you show that if this holds, then this holds we’ve shown that the semantics is sound and if we show that this holds then this holds then it’s complete. And if you show both of these things then you’ve got a general representation theorem relating these two." (Lecture 9, p. 15)

Shawn said...

greg,
Thanks for the comments. Those help a lot. That way of laying things out makes things a bit clearer. The soundness/completeness link was missing for me. I'll have to go back over that chapter with this in mind.

joyrexus,
Thanks for pointing out the Brandom stuff. I hadn't gotten around to looking at it since reading the representation theorem stuff, but it sounds like that is a good idea.

Rick Danko said...

Shawn,

I second greg's comment. A representation theorem can be though of as providing the class of models for a formal theory. The abstract algebra is the theory, and the class of concrete algebra representing the abstract one can be though of as the class of "models". In this sense, proving a representation theorem amounts to providing an interpretation for a theory. A better way to think about this stuff is in terms of category theory, but lets bracket that.

The stone representation theorem says (essentially) that any boolean algebra P can be represented (isomorphically embedded) as a sub-algebra of a powerset algebra over a set X.

What can we take X as?

The set of ultrafilters over P! What are ultrafilters? "Maximally consistent sets of propositions."
What this says then is that a boolean algebra of propositions is isomorphic to the powerset algebra over the ultrafilters of P--"the powerset algebra over the set of worlds".

Tarski, Johnson, and McKinsey extended these results to boolean algebras with n-ary operators. This amounted to proving soundness and completeness for modal logics by treating "worlds" as ultrafilters-"maximally consistent sets of propositions". This is essentially what Kripke did in his 1959, and he was reinventing the wheel to a certain extent.

The stone representation theorem is also important for topological semantics of modal logic, because of Stone duality. Dunn actually talks about this a lot in his book "Algebraic Methods in Philosophical Logic".