Thursday, 1 April 2010

Graphs and Topoi


In this paper we survey the fundamental constructions of a presheaf topos in the case
of the elementary topos of graphs. We prove that the transition graphs of nondeterministic
automata (a.k.a. labelled transition systems) are the separated presheaves for the double
negation topology, and obtain as an application that their category is a quasitopos.
Keywords: topos theory, graph theory, automata theory, transition systems

1 Introduction
Sheaf topoi are usually associated to continuous mathematics, such as differential or algebraic
geometry. Nonetheless, several (pre)sheaf topoi with simple (even finite!) base categories describe
fundamental mathematical objects such as trees and graphs. It has been suggested by
Lawvere [5] that these simple topoi have a rich combinatorial structure. Nonetheless, very few
results are known about them, and their internal workings seem to be mostly unexplored.


No comments: