Looking for Compatible Structure
Posted by David Corfield
Here’s a little puzzle for you. Imagine you wanted to set out to find an ordered set with lots of compatible algebraic structure. You’ve just been reading Michiel Hazewinkel’s Niceness Theorems, where he writes
These ruminations started with the observation that it is difficult for, say, an arbitrary algebra to carry additional compatible structure. To do so it must be nice, i.e., as an algebra be regular (not in the technical sense of this word), homogeneous, everywhere the same,… It is for instance very difficult to construct an object that has addition, multiplication and exponentiation, all compatible in the expected ways.
So you have the idea that you’re after a homogeneous order. Where to find one? Well, you’ve also just been reading about the Fraïssé limit construction, and so know that these limits possess homogeneity in spades. So you look up the Fraïssé limit for linear orders, and wait expectantly for opportunities to impose compatible algebraic structure. You won’t be disappointed. Not only does the limit support an addition and a multiplication, it turns out that we can impose an ordered field structure. We have, in fact, arrived at the rationals, the smallest ordered field.
After that success with linear orders, let’s start again with another structure. Let’s try graphs. Certainly we have a nice homogeneous Fraïssé limit, the random or Rado graph, described here. So should we expect to find compatible algebraic structure? If yes, how much? If no, was there something special about the linear order structure relative to the graph structure that allowed for compatible algebraic structure?
Looking about a little, Cayley graphs seem relevant here. If I read slides 8 and 10 of these lectures correctly, then (in many ways) a group structure can be imposed on the vertices of a Rado graph, and generators chosen so that the Rado graph is the corresponding Cayley graph.
Where next? Can the Rado graph support more algebraic structure?
Re: Looking for Compatible Structure
Does anyone think that these Fraisse limits might have some applicability for finite model theory?
I am asking because descriptive complexity theory is a branch of finite model theory. From Wikipedia:
“Descriptive complexity is a branch of finite model theory, a subfield of computational complexity theory and mathematical logic, which seeks to characterize complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and logic allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow “natural” and not tied to the specific abstract machines used to define them.”
Also, David, if you haven’t seen it yet then you might be interested in the 2001 book by Richard T. Cox entitled “Algebra of Probable Inference” which derives probability theory as a unique extension of Boolean algebra. I wonder if this means that probability theory is the only theory of inductive inference that is logically consistent?
(As a final side note, has anyone read the 2008 book by Jean-Pierre Marquis entitled “From a Geometrical Point of View” which views the construction of category theory as an extension of Klein’s Erlangen program in geometry? Thanks.)