It seems to me that the essential difference between graphs (including hypergraphs) and topological spaces resides in the difference between the covariant and contravariant power set functors. In both cases an object is a family of subsets of a set, with such subsets traditionally called respectively edges and open sets. But whereas a morphism of hypergraphs is a function for which the image of an edge is an edge, a continuous function is one for which the *inverse* image of an open set is open. Is this contrast discussed somewhere? And just how different does this make the resulting two concepts? (Treat the latter as being about *generalized* topological spaces, which drop the requirement that arbitrary unions and finite intersections of open sets be open.) Hypergraphs are a staple of the combinatorial literature, which seems to prefer small edges, doubletons being the motivating case definitive of the so-called simple graphs (of the undirected kind). Edges *coexist* in the sense that the whole hypergraph is viewed as the result of pasting its edges together. In contrast a topological space is perceived as more geometric than combinatorial. And open sets are not so much coexisting constituents of the space as *alternative* ways of "smoothly" partitioning the space into a closed and an open subset. Open sets are typically larger than edges, witness Euclidean space whose nonempty open subsets are all infinite. Whereas the natural view of an edge is an atomic constituent of the whole hypergraph, the natural view of an open set is as a (smoothly bounded) subspace. This passage from conjunctions of edges to disjunctions of open sets would appear to be a natural correlate of the passage from the covariant to the contravariant power set functor. My interest in this distinction stems from Chu's completion of a closed category to a self-dual closed (= *-autonomous) category with a specified dualizer. The morphisms of Chu's completion are defined contravariantly, so that when applied to Set it yields exactly these generalized topological spaces rather than hypergraphs. -- Vaughan Pratt +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
In my previous message tracing the distinction between (hyper)graphs and spaces to the covariant and contravariant power set functors respectively, I asked how different this made graphs and spaces. The two differences I claimed to see were that open sets were larger than edges, and that edges had a conjunctive quality (this edge is present AND that) while open sets were disjunctive (make this cut OR that). Allen Knutson objected to my size argument (that the open subsets of Euclidean space are infinite---indeed they have positive measure) on the ground that closed subsets can be finite. I agree, my size argument is neither complete nor terribly convincing, though I do think there is some correlation between size and the more basic differences. So let me have a shot at answering my question, how do these two functors differentiate graphs from spaces? Both functors take sets to complete atomic Boolean algebras (CABA's) and functions to sup-preserving functions, i.e. morphisms of complete sup-semilattices. The difference lies in their choice of sup-preserving maps. The covariant power set functor chooses the atom-preserving ones, the contravariant one picks the complement-preserving (hence inf-preserving) ones, better known as CABA maps. I claim this makes graphs point-oriented and spaces cut-oriented. Graphs care about how they are held together (by this edge AND that), spaces focus on how they can come apart (in this way OR that). Whereas an edge is a subobject, an open set is a congruence class. Now if we were dealing with say Boolean algebras this distinction would be clear "statically", i.e. without considering morphisms, since no proper subset of a Boolean algebra can be both a subalgebra, which must contain 0 and 1, and a congruence class, which cannot contain both 0 and 1. But for *sets* this distinction is completely invisible statically: every subset can be either a subobject or an equivalence class. Only by watching how a given subset behaves as its parent set "moves" (is acted on by a function) can we tell which it is. Under the action of a function, a subobject behaves like an element: it is neither destroyed nor duplicated, but distinct subobjects may merge into one, and new subobjects can join the existing ones. The behavior of a congruence class under a function is exactly complementary to that of an element: a class can be destroyed or duplicated, but it cannot merge with another class, and no new classes may appear. These features of subobjects and congruence classes constitute the essential differences between the edges of a graph and the open sets of a space respectively. One might also look for differences between graphs and spaces in terms of the localic view of the latter. However locales owe their separate existence to the difference between frame morphisms and CABA maps. This would seem to be a rather more subtle difference than those arising from the differences between the two power set functors, which surely get closer to the heart of the difference between graphs and spaces. Naturally I'd be very interested in pointers to other perspectives on the relationship between graphs and spaces. -- Vaughan Pratt +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
participants (1)
-
Vaughan Pratt