Wednesday, August 06, 2008

a novel proof of the heine-borel theorem

For a couple of years (off and on) landon and I have been playing with stuff at the intersection of graph theory and the semantic paradoxes (mostly Yablo's omega-Liar). The idea was to find graph theoretical necessary and sufficient conditions for paradoxicality. In graph theoretic terms: Yablo showed that there are acyclic reference graphs that support paradoxes, whereas it was traditionally thought that cyclicality (i.e. self-reference or mediated self-reference) was a necessary condition for a reference graph to support a paradox (what we call a "dangerous" reference graph). Anyway, we have some good results and are getting closer to the answer.

A by-product of all this has been some cool stuff intrinsically interesting to graph theory and other areas of math. One such tangent, with a lot of help from Matt Macauley, turned into a proof of Brouwer's fan theorem (one using Goedel compatness) and then into a proof of the Heine-Borel theorem.  Matt has also tidied it up into a cute prose-style paper, which can be found here.

The work on the paradoxes is scattered throughout various emails but we are hoping to pull it all together soon. Anyway, this is all a distraction from my real back to a priori contingencies, etc.

1 comment:

Anonymous said...

Hi Brian,

For graph theoretic characterisations of the paradoxes, you should check out this paper:

Halbach, Leitgeb, Welch - "Possible worlds semantics for modal notions concieved as predicates", JPL 03

Sounded like it might be relevant.