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.

November 6, 2009

Fraïssé Limits

Posted by David Corfield

The Rado graph, or random graph, seems to be an extraordinary entity. Take countably many nodes, then for each pair of nodes flip a coin and if it shows heads, draw an edge between them. Almost surely you will have generated the Rado graph, RR.

Any finite graph (and indeed any countable graph) is contained in RR, not just in the sense of being embeddedable, but in the sense of being an induced subgraph, that is, it is the full subgraph on a subset of nodes. Along with this universality, RR is also homogenous in the sense that any isomorphism between finite induced subgraphs extends to an automorphism of all of RR.

RR is very robust, you can delete finitely many vertices, add or remove finitely many edges, or interchange edges and non-edges, and you still end up with a graph isomorphic to RR. Furthermore, the odd thing about the construction of this graph is that I didn’t have to tell you the probability pp of the coin showing heads. So long as pp is in (0,1)(0, 1) and the tosses are independent, the Rado graph almost surely emerges.

Not only this, there are many ways to generate it without using random devices. Rado himself took the nodes to be the natural numbers, and an edge between mm and nn whenever either the mmth bit of the binary representation of nn is nonzero, or the nnth bit of the binary representation of mm is nonzero. Yet another method has us take as nodes the prime numbers equal to 1 mod 4. Then we join pp and qq if they are quadratic residues of each other.

I find myself interested in RR because it is an example of a Fraïssé limit. This is nicely explained in Artem Chernikov’s slides – What is…Fraïssé construction? We want a countable category, KK, of finitely generated structures (for a countable signature) whose morphisms are embeddings, which satisfies the three properties:

  • Hereditary: if AA embeds into BB and BB is in KK, then so is AA.
  • Joint embedding property: for any A,BKA, B \in K, there exists a CKC \in K and morphisms ACBA \to C \leftarrow B.
  • Amalgamation property: for arrows f:AB,g:ACf: A \to B, g: A \to C in KK, there exist r:BDr: B \to D and s:CDs: C \to D in KK, such that rf=sgr \circ f = s \circ g.
Then KK is the category of substructures of a countable structure MM which is universal and homogeneous. Examples include the Rado graph as the Fraïssé limit of the category of finite graphs and embeddings, and ,<\langle \mathbb{Q}, \lt \rangle as the Fraïssé limit of the category of finite linearly ordered sets and order preserving injections.

So now some questions: Can this kind of limit be given a natural category theoretic description? Is it related to any of the completions we have listed here? It seems to be a kind of Ind-completion, pretty close to an ideal completion. Can we understand the homogeneity category theoretically?

I should imagine I need to get a look at this thesis – Trevor Irwin, Fraïssé limits and colimits with applications to continua:

The classical Fraïssé construction is a method of taking a direct limit of a family of finite models of a language provided the family fulfills certain amalgamation conditions. The limit is a countable model of the same language which can be characterized by its (injective) homogeneity and universality with respect to the initial family of models. A standard example is the family of finite linear orders for which the Fraïssé limit is the rational numbers with the usual ordering.

We present this classical construction via category theory, and within this context we introduce the dual construction. This respectively constitutes the Fraïssé colimits and limits indicated in the title. We provide several examples.

We then present the projective Fraïssé limit as a special case of the dual construction, and as such it is the categorical dual to the classical (injective) Fraïssé limit. In this dualization we use a notion of model theoretic structure which has a topological ingredient. This results in the countable limit structures being replaced by structures which are zero-dimensional, compact, second countable spaces with the property that the relations are closed and the functions are continuous.

We apply the theory of projective Fraïssé limits to the pseudo-arc by first representing the pseudo-arc as a natural quotient of a projective Fraïssé limit. Using this representation we derive topological properties of the pseudo-arc as consequences of the properties of projective Fraïssé limits. We thereby obtain a new proof of Mioduszewski’s result that the pseudo-arc is surjectively universal among chainable continua, and also a homogeneity theorem for the pseudo-arc which is a strengthening of a result due to Lewis and Smith. We also find a new characterization of the pseudo-arc via the homogeneity property.

We continue with further applications of these methods to a class of continua known as pseudo-solenoids, and achieve analogous results for the universal pseudo-solenoid.

Available treatments include Wieslaw Kubiś, Fraisse sequences - a category-theoretic approach to universal homogeneous structures:

We present a category-theoretic approach to universal homogeneous objects, with applications in the theory of Banach spaces and in set-theoretic topology,

and Olivia Caramello, Fraïssé’s construction from a topos-theoretic perspective:

We present a topos-theoretic interpretation of (a categorical generalization of) Fraisse’s construction in model theory, with applications to countably categorical theories.

Posted at November 6, 2009 11:47 AM UTC

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

50 Comments & 1 Trackback

Re: Fra´ssÚ Limits

Hi

This seems like a nice construction. You say:

“…the Rado graph almost surely emerges.”

Does this mean “the Rado graph emerges up to graph isomorphism” as suggested in the Wikipedia article, or are you suggesting some probability of occurrence?

Posted by: Alex Hoffnung on November 6, 2009 3:19 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

The phrasing of Peter Cameron in The random graph revisited is

There is a countable graph RR with the property that a random countable graph (edges chosen independently with probability 12\frac{1}{2}) is almost surely isomorphic to RR.

I suppose what’s happening is that there is a probability distribution over the set of all isomorphism classes of graph on countably many nodes, and we’re being told that the measure of all other classes than RR is zero.

Posted by: David Corfield on November 6, 2009 3:29 PM | Permalink | Reply to this

Re: Fra´││Úáęmits

Have a look at chapter 11 of the book Diestel “Graph Theory” and the references cited there (it’s available online, but, sorry, I still have to figure out a few things with this blog framework like creating working links, just google title and author :-).

The probability space is built as a product space of all probablity spaces of edges (indexed by the natural numbers).

Then the event that (g is isomoporph to the Rado graph) has probablity 1.

Posted by: Tim vB on November 6, 2009 5:02 PM | Permalink | Reply to this

Re: Fra´ssÚálimits

Tim: for a simple way to embed live links, choose the text filter “Markdown” from the drop-down menu in the comment form, and write links like this:

[Markdown syntax cheatsheet](http://daringfireball.net/projects/markdown/syntax)

which produces the link Markdown syntax cheatsheet.

Posted by: Peter LeFanu Lumsdaine on November 6, 2009 5:22 PM | Permalink | Reply to this

Re: Fra´┐Żss´┐Ż´┐Żlimits

Thanx, of course I did not find the obvious solution. Doh! But the drop down box does not look like an active GUI element to me, because it is dark grey. That is a classic GUI blooper!
(Attack is the best defense :-)

Hey, I beat John to the answer!

Posted by: Tim vB on November 6, 2009 6:07 PM | Permalink | Reply to this

Re: Fra´││Úáęmits

The phrase “with probability 1” means almost surely, and the Wikipedia said that it is analogous to “almost everywhere” in Measure Theory. I think of it as infinitesimally close to congruence. I read about the concept in regard to the Cantor Dust Set.

Posted by: Stephen Harris on November 6, 2009 10:22 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Yes, that’s what’s going on. Possibly instead of thinking of the probability measure as being on isomorphism classes of graphs, it’s easier to think of the measure as lying on the set {graphs with vertex-set \mathbb{N}}, since then choosing a graph just comes down to choosing which edges are in, so we get a copy of Cantor space 2 2^{\mathbb{N}}, with the obvious “flip an infinite sequence of fair coins” probability measure.

Then the precise statement becomes: the set of graphs on \mathbb{N} isomorphic to RR has measure 1. To show this, use the “extension property” as discussed in the Wikipedia article. It’s easy to see that a random graph has the extension property with probability 1; and any graph with the extension property is isomorphic to RR, again as discussed in the article.

Posted by: Peter LeFanu Lumsdaine on November 6, 2009 5:12 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Alex wrote:

“the Rado graph almost surely emerges.”

Does this mean “the Rado graph emerges up to graph isomorphism” as suggested in the Wikipedia article, or are you suggesting some probability of occurrence?

‘Almost surely’ is how probability theorists say ‘with probability 1’.

But it’s pretty clear that in this case, we only know a graph isomorphic to the Rado graph emerges from this random process.

So, I bet ‘almost surely the Rado graph emerges’ means ‘with probability 1, a graph isomorphic to the Rado graph emerges’.

By the way: just because something happens with probability 1, doesn’t mean it always happens. Flip a fair coin, count the fraction of times it lands heads up, and take a limit as you flip it more and more times. ‘Almost surely’ the fraction converges to 1/21/2. But it’s certainly possible for the coin flips to go like H H H H H H H H H…

Posted by: John Baez on November 6, 2009 5:19 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

By the way: just because something happens with probability 1, doesn’t mean it always happens.

The intuition that an event with probability 0 can be ignored is another of those things that just doesn't generalise from finite to infinite sets.

Posted by: Toby Bartels on November 6, 2009 6:46 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

NB it does generalise to countable sets though! (Since measures are countably additive).

Posted by: Tom E on November 7, 2009 10:25 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

The ratio converges to one, but not the discrepancy value (DV). If you flip a coin 10 times and it comes up 6 heads and 4 tails, then the percentage of difference, is 60% to 40%, or 20%, but the DV is only 6 - 4 = 2.

Now suppose you flipped the coin a million times and the percentage of heads to tails narrowed to 1%. 50.5% of a million Head flips to 49.5% of a million Tail flips, = 1% difference. So the percentage is converging to 50/50 but not the discrepancy value between heads and tails, which would be 10,000. What brings about a true balance between heads and tails in some protracted sequence? It’s when there is no discrepancy at all. Such as 5 heads and 5 tails; or 500,000 heads and 500,000 tails. The discrepancy values are always diverging. No matter if you toss the coin a billion times and the
% ratio of heads to tails has dropped to say .000001, you will see that the discrepancy value always increases. It is never likely that at some huge number of coin tosses that the discrepancy value is going to be exactly 0, so that the % of heads to tails is exactly 0. Because there is no causality involved, and it is just as likely that the discrepancy value (which is actually a technical term) is going to be biased by a chance sequence of more heads to tails and in this given sequence and the % ration of heads to tails can swing back in the other direction.

What is true is that the average of all such sequences, which includes starting off with 6 tails and 4 heads - that all these sequences favoring heads and all the sequences favoring tails, mirror each other, or balance each other, so that the average of heads or tails of all such sequences both converges by % and by discrepancy values. Some people might think that this violates the Central Limit Theorem, but my argument is logical. I discovered it in reading books about chance. I’ve read several books, so I’m not sure of which one (but I’ve read this more than once) maybe it was Jacques Monod’s “Chance and Necessity”.

Posted by: Stephen Harris on November 7, 2009 2:10 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

David wrote:

Can this kind of limit be given a natural category theoretic description?

I think it’s a colimit, since it’s what ordinary people would call a ‘union’. The fun question is whether these conditions:

  • Hereditary: if AA embeds into BB and BB is in KK, then so is AA.
  • Joint embedding property: for any A,BKA, B \in K, there exists a CKC \in K and morphisms ACBA \to C \leftarrow B.
  • Amalgamation property: for arrows f:AB,g:ACf: A \to B, g: A \to C in KK, there exist r:BDr: B \to D and s:CDs: C \to D in KK, such that rf=sgr \circ f = s \circ g.

can be phrased purely category-theoretically, and whether the proof can be made purely category-theoretic.

The three properties above presume that we’re starting with some sort of category and some notion of ‘embedding’ — for example, monomorphism or regular monomorphism.

And I bet they’re starting with a concrete category: a category of structured sets. (Maybe finite sets?) We might need some extra assumptions if we wanted to remove that one.

My only mildly interesting comment is that these 2 properties:

  • Joint embedding property: for any A,BKA, B \in K, there exists a CKC \in K and morphisms ACBA \to C \leftarrow B.
  • Amalgamation property: for arrows f:AB,g:ACf: A \to B, g: A \to C in KK, there exist r:BDr: B \to D and s:CDs: C \to D in KK, such that rf=sgr \circ f = s \circ g.

are called ‘filteredness’ in category theory. The amalgamation property is also closely related to ‘confluence’ in the study of rewrite rules.

Posted by: John Baez on November 6, 2009 5:34 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

And I bet they’re starting with a concrete category: a category of structured sets. (Maybe finite sets?)

This is answered in David's post: KK consists of ‘finitely generated structures (for a countable signature)’, which I take to mean finitely generated objects in some variety of algebras VV (with countable signature). Note that VV is a concrete category in which all monos are regular, so probably this is what is meant by ‘embedding’.

So KK is a countable filtered subcategory of VV that's closed under subobjects.

Posted by: Toby Bartels on November 6, 2009 6:56 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

The signature can also have relation symbols - from the linked definition, it looks like varieties of algebras omit relations, while allowing function symbols. Both the random graph and the rationals as an ordered set are living in purely relational languages.

An embedding preserves cases where the relation holds, but new instances of the relation can appear in the larger structure. Not sure how to phrase any of this categorically.

Posted by: Scott McKuen on November 6, 2009 8:38 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

The signature can also have relation symbols - from the linked definition, it looks like varieties of algebras omit relations, while allowing function symbols. Both the random graph and the rationals as an ordered set are living in purely relational languages.

Good point. That makes it less familiar (at least to me), but it should be amenable.

Posted by: Toby Bartels on November 6, 2009 9:05 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Nobody has mentioned this paper yet and I liked it because it brings together quite a few closely related and a few almost closely related ideas; more graphs than you can shake a stick at. :-)

Zero-One Laws: I will discuss a geometric Zero-One Law for infinite graphs. The principal examples are Cayley graphs of infinite groups. A a ”geometric” version of Zero-One Law states that for any first-order sentence φ of graph theory either φ or its negation ¬φ holds almost surely on finite subgraphs of a graph X. Reduction to graphs: One can approach an arbitrary algebraic structure X via its Gaifman graph [X] that brings ”geometry” into play.

Coarse First-order Logic: similar to the coarse geometry one can consider a coarse logic. For example the coarse elementary theory of a structure X consists of all sentences that almost surely true in X.

Random substructures: One can define random substructures of X similar to the Erdos’ model. It turns out they are also analogs of the Rado universal graphs. We show that random substructures give models of the coarse first-order theory of X: they are almost surely elementarily equivalent to each other, though not necessarily isomorphic. Random substructures and percolation: There are interesting connections with percolation on graphs.

Labeled Zero-One Law In this case a structure is chosen at random with respect to the uniform distribution on all structures with universe {1,2,…,n}. Compare with the Erdos’ model of a ”random graph” on n vertices.

Unlabeled Zero-One Law In this case one chooses an isomorphism class of structures uniformly at random from the set of isomorphism classes of structures with universe of size n.

Erdos random graphs

A random graph is obtained by starting with a set of n vertices and adding edges between them at random. Most commonly studied is the Erdos-Renyi model, denoted in which every possible edge occurs independently with probability p. If instead we start with an infinite set of vertices, and again let every possible edge occur independently with probability p, then we get an infinite random graph, or Erdos graph.

Rado graphs

The Rado graph is the countable graph R such that for any finite graph Y and any vertex v of Y , any embedding of Y − v as an induced subgraph of R can be extended to an embedding of Y into R.

A Rado graph is unique (up to isomorphism). A Rado graph contains all finite and countably infinite graphs as induced subgraphs.

Posted by: Stephen Harris on November 7, 2009 2:46 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Y.Glebski et al, R. Fagin Zero-One Law .

Don't forget http:// for external links! This one should be

Y.Glebski et al, R. Fagin Zero-One Law .

Posted by: Toby Bartels on November 7, 2009 3:16 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Sorry, I’ve had a string of bad luck with cut and paste lately, but I shall return home.

Posted by: Stephen Harris on November 7, 2009 7:44 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Scott wrote

An embedding preserves cases where the relation holds, but new instances of the relation can appear in the larger structure. Not sure how to phrase any of this categorically.

I’m getting confused about embeddings. According to Wikipedia and other sources, the model theoretic notion requires that relations be such that, if RR is an nn-ary relation, and h:ABh: A \to B is an embedding, then

AR(a 1,...,a n)iffBR(h(a 1),...,h(a n)). A \models R(a_1, ..., a_n) iff B \models R(h(a_1),..., h(a_n)).

So in the case of graphs embeddings are just the inclusions of induced subgraphs? I needn’t have made that distinction in the first sentence of the second paragraph of my post?

Posted by: David Corfield on November 7, 2009 10:15 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Given that the construction for graphs being discussed is about graphs that don’t contain loops, I guess that the embeddings had better be as stated or else the category wouldn’t satisfy the amalgamation property.

Were the two mappings of the graph of two unconnected nodes to the complete graph on two nodes to count as embeddings, an amalgamation of them would need a loop.

Posted by: David Corfield on November 7, 2009 12:08 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

No, you are exactly right - this is a mistake on my part. Embeddings do not allow the image to have new instances of the relations. I was thinking of the weaker notion of homomorphism.

Posted by: Scott McKuen on November 7, 2009 9:45 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Toby wrote:

This is answered in David’s post: KK consists of ‘finitely generated structures (for a countable signature)’, which I take to mean finitely generated objects in some variety of algebras VV (with countable signature). Note that VV is a concrete category in which all monos are regular, so probably this is what is meant by ‘embedding’.

If all monos in VV are regular, then VV is balanced (all epic monos are isomorphisms). But the category of commutative monoids is not balanced.

Posted by: Todd Trimble on January 2, 2010 6:16 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

John wrote

these 2 properties…are called ‘filteredness’ in category theory

(I can’t believe you’re still linking to Wikipedia and not nLab, so I changed the link in the quote.)

Yes, that’s why I was gesturing towards Awodey’s ideal completion under filtered colimits of monomorphisms.

So is there any difference between filtered colimits in the category of graphs with embeddings as morphisms, and filtered colimits of monomorphisms in the category of graphs with all graph morphisms?

Posted by: David Corfield on November 6, 2009 8:33 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

David wrote:

So is there any difference between filtered colimits in the category of graphs with embeddings as morphisms, and filtered colimits of monomorphisms in the category of graphs with all graph morphisms?

It sounds like you’re using a concept of ‘embedding’ which is stronger than ‘monomorphism’? The map from the discrete graph on 2 vertices to the complete graph on 2 vertices is a monomorphism in the category of graphs that you’re using, right? But it’s not an embedding?

Posted by: John Baez on November 8, 2009 12:41 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

It sounds like you’re using a concept of ‘embedding’ which is stronger than ‘monomorphism’? The map from the discrete graph on 2 vertices to the complete graph on 2 vertices is a monomorphism in the category of graphs that you’re using, right? But it’s not an embedding?

Right, that's been established in other comments here.

I think that an embedding here is a regular monomorphism (in the category of simple graphs).

Posted by: Toby Bartels on November 8, 2009 3:19 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Yes, we were looking at the right kind of monomorphism up here.

Even if the monomorphisms used for graphs are regular, it seems that they’re not for groups. The universal Hall group is the inductive limit of embeddings

S nS n! S_n \to S_{n!}

(see p. 8 of this).

While in GrpGrp, regular monomorphisms are inclusions of normal subgroups.

Posted by: David Corfield on November 8, 2009 5:27 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Hang on a sec—are we talking about structures for a language, or about models for a theory? The category of groups is the latter but not the former, and I think that the regular monics in the corresponding category of structures (“pointed magmas”, say) really are just the substructure inclusions (= embeddings).

Posted by: Mike Shulman on November 9, 2009 5:21 PM | Permalink | PGP Sig | Reply to this

Re: Fra´ssÚ Limits

Under the desired idea of embedding, pointed magmas won’t have the JEP - let magma M be a group, and magma N have 1 N*1 N1 N1_N * 1_N \neq 1_N.

There’s sort of implicitly a 1\forall_1-theory hanging around because the HP and JEP conditions by themselves are enough to ensure that your collection of structures (up to isomorphism) is already the “age” of some countable structure. Whatever universal sentences that structure satisfies (if any) will have to hold in the whole class.

Stephen Harris mentioned this implicitly in the computability abstract below, but the age of a structure KK is the class of finitely generated structures that embed into KK, but only considering structures up to isomorphism.

Posted by: Scott McKuen on November 10, 2009 2:39 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Under the desired idea of embedding, pointed magmas won’t have the JEP

But the question isn’t about whether the collection of all structures has the JEP. The point is that given any MM, the collection of finitely generated substructures of MM has the JEP (and the other properties), and that conversely any collection of fg structures that does satisfy these properties all embed in some canonical MM.

You have a good point that this implies that any Π 1\Pi_1-sentence satisfied by MM will be satisfied by all its finitely generated substructures. Thus, in particular, if MM is a group then C 0(M)C_0(M) (defined in pointed magmas) will consist entirely of monoids. If we add another unary operation to our magmas that becomes the inverse operation in our groups, then C 0(M)C_0(M) in “involutory pointed magmas” will consist entirely of groups.

Posted by: Mike Shulman on November 10, 2009 3:27 AM | Permalink | PGP Sig | Reply to this

Re: Fra´ssÚ Limits

Oh, so what’s happening in the case of the groups? How should we describe Hall’s universal group?

Posted by: David Corfield on November 9, 2009 5:59 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Oh, so what’s happening in the case of the groups? How should we describe Hall’s universal group?

I don’t know; I don’t know anything about this stuff! I just noticed that your description of the general Fraisse construction was only about structures.

In the case of groups, the answer might just be that groups are closed under subobjects and filtered colimits in pointed magmas, so the equivalence between “C 0C_0s with amalgamation” and “homogeneous MM” in pointed magmas restricts to an equivalence in groups. If that’s so, then possibly something similar is also true for some more general class of finitary theories.

Posted by: Mike Shulman on November 9, 2009 6:27 PM | Permalink | PGP Sig | Reply to this

Re: Fra´ssÚ Limits

While in GrpGrp, regular monomorphisms are inclusions of normal subgroups.

I had thought so too, but it’s come to my attention recently that all monomorphisms in GrpGrp are regular (this is actually mentioned in the nLab article). For example, the inclusion

(12):S 2S 3(1 2): S_2 \to S_3

is the equalizer of the identity map and conjugation by the element (12)(1 2).

Posted by: Todd Trimblre on January 2, 2010 6:07 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Huh. Now why did we all think otherwise?

Posted by: Mike Shulman on January 3, 2010 3:27 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Todd wrote in part:

it’s come to my attention recently that all monomorphisms in Grp are regular (this is actually mentioned in the nLab article).

Mike replied:

Huh. Now why did we all think otherwise?

Probably because the nLab article said the wrong thing too, until Reid Barton fixed it last week.

Posted by: Toby Bartels on January 4, 2010 5:43 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Now why did we all think otherwise?

Probably because the nLab article said the wrong thing too, until Reid Barton fixed it last week.

I’m be more inclined to say that the nLab article said the wrong thing because we all thought the wrong thing. Otherwise one of us would have fixed it.

Posted by: Mike Shulman on January 4, 2010 4:28 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

So it sounds like one question is whether we can characterize this sort of “embedding” categorically. I think one way to say it would be that they are the cartesian morphisms for the underlying-set functor ΣStrSet\Sigma Str \to Set that lie over injections in SetSet. (Of course, unless the signature Σ\Sigma is purely relational, this functor is not a fibration, but it may still have individual cartesian morphisms.)

A slightly more intrinsic statement is that they are the right class of a factorization system on ΣStr\Sigma Str whose left class is the maps that are surjections on underlying sets. So one abstract situation in which to work would be a category equipped with a factorization system. Can we impose axioms on such a factorization system that allow the proof to go through in such generality?

Posted by: Mike Shulman on November 9, 2009 5:49 AM | Permalink | PGP Sig | Reply to this

Re: Fra´ssÚ Limits

Could it be that embeddings are not very natural category theoretically and that this is in an indication of a tension between category theory and model theory?

Posted by: David Corfield on November 9, 2009 3:46 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

It sounds like you are suggesting finding diagram conditions that mimic “relation” and “function” and then using the functorial nature of the factorization to preserve those diagrams across the morphism intended to be an embedding?

Posted by: Scott McKuen on November 9, 2009 5:14 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

It sounds like you are suggesting finding diagram conditions that mimic “relation” and “function” and then using the functorial nature of the factorization to preserve those diagrams across the morphism intended to be an embedding?

No, that doesn’t sound at all like what I was thinking of. (-: I was asking whether we can abstract out the essential properties of this factorization system, so that an analogous theorem could be proven in any category (not just ΣStr\Sigma Str) equipped with a factorization system satisfying suitable axioms. There shouldn’t be any need to make the objects of that category “look like” structures.

Posted by: Mike Shulman on November 9, 2009 5:36 PM | Permalink | PGP Sig | Reply to this

Re: Fra´ssÚ Limits

A slightly more intrinsic statement is that they are the right class of a factorization system on ΣStr\Sigma Str whose left class is the maps that are surjections on underlying sets.

Any hope that these surjections can be identified perfectly intrinsically as the regular epimorphisms? These match the surjections in very many cases, including all algebraic (but not topological) concrete categories.

Posted by: Toby Bartels on November 9, 2009 7:46 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Any hope that these surjections can be identified perfectly intrinsically as the regular epimorphisms? These match the surjections in very many cases, including all algebraic (but not topological) concrete categories.

I’m pretty sure the regular epimorphisms of graphs are going to be those that are surjective on edges as well as on vertices. These graphs are much more “topological” than “algebraic”.

Posted by: Mike Shulman on November 9, 2009 8:51 PM | Permalink | PGP Sig | Reply to this

Re: Fra´ssÚ Limits

I’m pretty sure the regular epimorphisms of graphs are going to be those that are surjective on edges as well as on vertices.

But isn't that we want here? Or no, we want embeddings to be locally surjective on edges, but not surjections.

Posted by: Toby Bartels on November 9, 2009 9:51 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

I am reminded of a talk by Steve Donkin on the character table of a group. I don’t recall the details. This group was constructed using symmetric groups and a limit. However it was then shown to be far more robust and to have other properties. This makes me think this is the group version of the hoped-for general construction.

Posted by: Bruce Westbury on November 7, 2009 9:21 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

Perhaps you mean Hall’s universal locally finite group. It is simple, every finite group admits a monomorphism to it, and any two isomorphic finite subgroups are conjugate. That’s a Fraïssé amalgamation or limit for the category of finitely generated groups.

Posted by: David Corfield on November 7, 2009 10:03 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

David wrote:

The Rado graph, or random graph, seems to be an extraordinary entity.

This is true in a sense — but also a bit funny, since there’s a sense in which the Rado graph is the most ordinary countable graph. Make any big random mess of a countable graph — don’t do anything special — and you’ll almost surely get the Rado graph. So, it’s extraordinary only in its ordinariness. This accounts for its robustness.

Posted by: John Baez on November 8, 2009 12:37 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

This is really loose and ad hoc, but is there a Fraïssé limit for knots and links? For a well-chosen logical language L knotsL_knots, it seems like there should be a way to take “finitely generated structure” to be “link with finitely many components”, and “AA embeds in BB” to be “AA is a sublink of BB” In that case, the HP, AP, and JEP should all hold:

HP) we’ve defined “substructure” to mean sublink, so this is trivial;

JEP) just take the union of the two links A,BA, B (if we’re thinking of them as embedded in 3\mathbb{R}^3, then just move AA around in its equivalence class if you need to avoid intersecting BB);

AP) this basically is the same as JEP except you also need your particular embedding of BB to be deformed so it’s AA-substructure matches the AA-substructure of CC;

Its not clear to me exactly what the right function and relation symbols would be to make this work. Perhaps you’d want to have something like the category of tangles as the term algebra for your language, but without explicit constants for the cup, cap and crossings.

Posted by: Scott McKuen on November 8, 2009 1:28 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

The only trouble I could imagine is wildness, but maybe that’s not a problem.

There are certainly Fraïssé-like things happening in spatial situations. There’s a universal Urysohn metric space, although this requires a certain completion process:

But the difference between classical model theory and our case consist in the following: after construction of the inductive limit we must make the completion of the space, I do not see how to axiomatize this construction for uncountable case.

Hmm, I don’t suppose this has something to do with the kind of duality which sees the inductive limit that is an initial algebra be completed to the projective limit which is a terminal coalgebra (e.g., binary rationals complete to reals).

There is work done on projective Fraïssé limits with a bearing on continua.

Posted by: David Corfield on November 9, 2009 3:00 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

I was looking to better understand Turing degrees, when I happened across “Embeddings into the Turing degrees” and noticed a couple of papers on Fraisse limits which have a heavy emphasis on computability.

Abstract. Fraısse studied countable structures S through analysis of the age of S, i.e., the set of all finitely generated substructures of S. We investigate the effectiveness of his analysis, considering effectively presented lists of finitely generated structures and asking when such a list is the age of a computable structure. We focus particularly on the Fraısse limit.

Now we want to consider random string maps and random string sets. They are just the Fraısse limits of the class of finite sting maps and of the class of finite string sets. Recall that a structure is ultra-homogeneous if every two tuples which satisfy the same quantifier free types are automorphic.

Posted by: Stephen Harris on November 9, 2009 7:06 AM | Permalink | Reply to this

Re: Fra´ssÚ Limits

A philosopher, Justin Bledin, uses the Fra´ssÚ Limit construction of the rationals in his paper Model Theoretic Explanations in the Theory of Dense Linear Orderings.

Posted by: David Corfield on November 25, 2009 12:42 PM | Permalink | Reply to this

Re: Fra´ssÚ Limits

From the 20 page preview available of Irwin’s thesis, I see he uses the term feltered subcategory to describe a full subcategory satisfying the joint embedding property and amalgamation property. It doesn’t seem as though the term has caught on, however. Perhaps making the thesis freely available would help.

Posted by: David Corfield on November 26, 2009 10:19 AM | Permalink | Reply to this
Read the post Looking for Compatible Structure
Weblog: The n-Category Café
Excerpt: Can Fraisse limits support algebraic structure?
Tracked: January 8, 2010 11:53 AM

Post a New Comment