Fraïssé Limits

November 6, 2009

Posted by David Corfield

$MathML-enabled post (click for more details).$

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, $R$ .

Any finite graph (and indeed any countable graph) is contained in $R$ , not just in the sense of being embeddable, 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, $R$ is also homogenous in the sense that any isomorphism between finite induced subgraphs extends to an automorphism of all of $R$ .

$R$ 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 $R$ . Furthermore, the odd thing about the construction of this graph is that I didn’t have to tell you the probability $p$ of the coin showing heads. So long as $p$ is in $(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 $m$ and $n$ whenever either the $m$ th bit of the binary representation of $n$ is nonzero, or the $n$ th bit of the binary representation of $m$ is nonzero. Yet another method has us take as nodes the prime numbers equal to 1 mod 4. Then we join $p$ and $q$ if they are quadratic residues of each other.

$MathML-enabled post (click for more details).$

I find myself interested in $R$ 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, $K$ , of finitely generated structures (for a countable signature) whose morphisms are embeddings, which satisfies the three properties:

Hereditary: if $A$ embeds into $B$ and $B$ is in $K$ , then so is $A$ .
Joint embedding property: for any $A, B \in K$ , there exists a $C \in K$ and morphisms $A \to C \leftarrow B$ .
Amalgamation property: for arrows $f: A \to B, g: A \to C$ in $K$ , there exist $r: B \to D$ and $s: C \to D$ in $K$ , such that $r \circ f = s \circ g$ .

Then

K

is the category of substructures of a countable structure

M

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 projectiveFraï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: https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2106

51 Comments & 1 Trackback

Re: Fraïssé Limits

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

The phrasing of Peter Cameron in The random graph revisited is

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

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 $R$ is zero.

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

Re: Fraïssé limits

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ïssé limits

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.

Reinhard Diestel, Graph Theory.

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

Re: Fraïssé Limits

$MathML-enabled post (click for more details).$

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^{\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 $R$ 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 $R$ , 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

$MathML-enabled post (click for more details).$

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/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

$MathML-enabled post (click for more details).$

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 $A$ embeds into $B$ and $B$ is in $K$ , then so is $A$ .
Joint embedding property: for any $A, B \in K$ , there exists a $C \in K$ and morphisms $A \to C \leftarrow B$ .
Amalgamation property: for arrows $f: A \to B, g: A \to C$ in $K$ , there exist $r: B \to D$ and $s: C \to D$ in $K$ , such that $r \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, B \in K$ , there exists a $C \in K$ and morphisms $A \to C \leftarrow B$ .
Amalgamation property: for arrows $f: A \to B, g: A \to C$ in $K$ , there exist $r: B \to D$ and $s: C \to D$ in $K$ , such that $r \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

$MathML-enabled post (click for more details).$

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: $K$ consists of ‘finitely generated structures (for a countable signature)’, which I take to mean finitely generated objects in some variety of algebras $V$ (with countable signature). Note that $V$ is a concrete category in which all monos are regular, so probably this is what is meant by ‘embedding’.

So $K$ is a countable filtered subcategory of $V$ 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

$MathML-enabled post (click for more details).$

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

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

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

$MathML-enabled post (click for more details).$

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 $R$ is an $n$ -ary relation, and $h: A \to B$ is an embedding, then

$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

$MathML-enabled post (click for more details).$

Toby wrote:

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

If all monos in $V$ are regular, then $V$ 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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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_n \to S_{n!}$

(see p. 8 of this).

While in $Grp$ , 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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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_N \neq 1_N$ .

There’s sort of implicitly a $\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 $K$ is the class of finitely generated structures that embed into $K$ , 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

$MathML-enabled post (click for more details).$

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 $M$ , the collection of finitely generated substructures of $M$ 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 $M$ .

You have a good point that this implies that any $\Pi_1$ -sentence satisfied by $M$ will be satisfied by all its finitely generated substructures. Thus, in particular, if $M$ is a group then $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)$ 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

$MathML-enabled post (click for more details).$

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_0$ s with amalgamation” and “homogeneous $M$ ” 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

$MathML-enabled post (click for more details).$

While in $Grp$ , regular monomorphisms are inclusions of normal subgroups.

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

$(1 2): S_2 \to S_3$

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

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

Re: Fraïssé Limits

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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 $\Sigma Str \to Set$ that lie over injections in $Set$ . (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 $\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

$MathML-enabled post (click for more details).$

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 $\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

$MathML-enabled post (click for more details).$

A slightly more intrinsic statement is that they are the right class of a factorization system on $\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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

I just came across this old post, and I thought I’d point out that amalgamation + joint embedding is actually a bit weaker than filteredness – to be filtered entails in addition that if there are $f,g: A \overset{\to}{\to} B$ , then there is $h: B \to C$ with $hf = hg$ . This is not going to be the case here because we’re working in a category (the category of L - structures and embeddings) where every morphism is a monomorphism. In the diagram I mentioned, since $h$ would be a monomorphism, we could conclude from $hf = hg$ that $f=g$ and hence that we’re in a preorder, which we’re not.

Amalgamation and joint embedding are, however, among the few nice categorical properties enjoyed by the category Mod(T) of models of a complete first-order theory T (with elementary embeddings as morphisms).

Posted by: Tim Campion on June 15, 2016 9:37 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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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_knots$ , it seems like there should be a way to take “finitely generated structure” to be “link with finitely many components”, and “ $A$ embeds in $B$ ” to be “ $A$ is a sublink of $B$ ” 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, B$ (if we’re thinking of them as embedded in $\mathbb{R}^3$ , then just move $A$ around in its equivalence class if you need to avoid intersecting $B$ );

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

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.

Antonio Montalban, B. Csima, R. Miller, and V. Harizanov, Computability of Fraisse limits.

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

Antonio Montalban and Bakhadyr Khoussainov, A Computable $\aleph_0$-categorical Structure Whose Theory Computes True Arithmetic [randomgraph.pdf].

Now we want to consider random string maps and random string sets. They are just the Fraısse limits of the class of ﬁnite sting maps and of the class of ﬁnite string sets. Recall that a structure is ultra-homogeneous if every two tuples which satisfy the same quantiﬁer 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

The n-Category Café

Skip to the Main Content

November 6, 2009