Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

January 8, 2010

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?

Posted at January 8, 2010 11:04 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2150

2 Comments & 0 Trackbacks

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.)

Posted by: Charlie Stromeyer on January 9, 2010 2:32 PM | Permalink | Reply to this

Re: Looking for Compatible Structure

the 2001 book by Richard T. Cox entitled “Algebra of Probable Inference”

This is a very nice little book, although I don't think that a mathematician (or philosopher) will feel bound by its arguments. Although last published in 2001, it goes back (at least) to 1961.

Posted by: Toby Bartels on January 9, 2010 9:14 PM | Permalink | Reply to this

Post a New Comment