6
$\begingroup$

I came across some slides talking about the Hrushovski construction. One of the examples was the construction of a "universal tree".

I was curious because the collection of finite trees does not satisfy amalgamation (under substructure). I looked on the internet and on arXiv, but unsuccessfully.

My question: How is a universal tree defined? Can you provide any reference?

$\endgroup$
7
  • 6
    $\begingroup$ That's not much to go on. Maybe you could at least link to the slides you were reading? $\endgroup$
    – Tim Campion
    Jul 26, 2016 at 2:12
  • $\begingroup$ The slides were not of real help. The universal tree was more like a footnote there. $\endgroup$ Jul 26, 2016 at 23:50
  • 3
    $\begingroup$ That's okay. They would still help provide some context. $\endgroup$
    – Tim Campion
    Jul 26, 2016 at 23:58
  • 5
    $\begingroup$ Yggdrasil, in the Norse mythology, is an example of a universal tree. :-) $\endgroup$
    – Asaf Karagila
    Jul 27, 2016 at 4:36
  • $\begingroup$ In metric geometry there is an object called $\mathbb{R}$-tree which is probably related: en.m.wikipedia.org/wiki/Real_tree $\endgroup$
    – Uri Bader
    Jul 27, 2016 at 7:35

1 Answer 1

8
$\begingroup$

Let me preface this by saying that I don't actually know anything about Hrushovski constructions except that they are Fraïssé-like. I don't know what "universal tree" refers to in the slides you've read, but I can say what it means to me.

The Fraïssé limit takes in a class of finite structures $\mathcal{F}$ satisfying amalgamation and joint embedding, and it returns a structure $\mathbb{F}$. If $\mathcal{F}$ was also closed under substrucures, then the class of finite substructures of $\mathbb{F}$ (the age of $\mathbb{F}$) coincides with $\mathcal{F}$. But even if $\mathcal{F}$ is not closed under substructures, it's still the case that $\mathbb{F}$ is universal and homogeneous with respect to $\mathcal{F}$, and moreover $\mathbb{F}$ is the union of an $\omega$-indexed chain of embeddings of structures from $\mathcal{F}$ (and $\mathbb{F}$ is also universal with respect to structures that are unions of $\omega$-indexed chains of embeddings of structures from $\mathcal{F}$). Moreover, these properties still characterize $\mathbb{F}$ up to isomorphism. So it makes sense to talk about the Fraïssé limit of a class of structures even without closure under substructures.

If you take $\mathcal{F}$ to be finite trees, then since trees are closed under unions of chains, the Fraïssé limit $\mathbb{F}$ is still a (countable) tree, and it is universal and homogeneous with respect to finite trees (and universal with respect to countable trees). In this sense it deserves to be called the "universal tree".

I've discussed a categorical perspective on Fraïssé limits here, in case you're interested. I suspect that Hrushovski constructions fit into the same categorical framework. Incidentally, so does the construction of saturated models.

EDIT I should be specific about the category of trees I'm considering. I consider a tree to be a connected graph with no cycles, and morphisms to be graph embeddings. These structures are closed under unions of chains, and have amalgamation and joint embedding. So the Fraïssé limit of trees in this sense is again a tree in this sense. This object probably deserves the name "universal tree". The rooted version also works, if morphisms are required to preserve roots. So do rooted and unrooted versions of forests.

If instead we take trees to be connected posets with well-ordered initial segments, and morphisms to be order-preserving maps, then we have a lot more morphisms, and as Eric Wofsey shows in the stackexchange question that Ioannis Souldatos links to below, we no longer have amalgamation. However, if we additionally require our morphisms to preserve the minimal element of each poset, then for we get a category which is only a little more complicated than the rooted version of the category in the previous paragraph - basically, we now have "refinement" maps, which allow us to split an edge into two edges. This category has amalgamation and joint embedding, but is not closed under directed unions. So the Fraïssé limit exists as a poset, but it is no longer a tree in this sense. This is related to the fact that well-ordering is not a first-order concept.

$\endgroup$
8
  • 2
    $\begingroup$ Yes, no doubt this is what is meant by "universal tree". But of course there are many possible tree languages, and which one you choose (or, alternatively, what class of embeddings you consider) will change what universal homogeneous tree you get. $\endgroup$ Jul 27, 2016 at 17:54
  • $\begingroup$ Interesting. I was definitely vague about this point. Are there interesting examples other than taking an embedding to be an induced subgraph (where the tree is considered as a graph)? I suppose there are other points of variation, too -- depending on whether your trees are binary, rooted, etc. $\endgroup$
    – Tim Campion
    Jul 27, 2016 at 18:02
  • $\begingroup$ Sometimes we take planar trees... Sometimes set-theorists use the word "tree" to mean a partial order with well-ordered downwards ideals; finite examples should be in bijection with finite rooted trees, but "subtrees" may skip some vertices $\endgroup$ Jul 27, 2016 at 18:20
  • $\begingroup$ @TimCampion: The difference between Hrushovski and Fraisse constructions lies on the morphisms used. In Fraisse, we use the substructure relation. In Hrushovski we can use other morphisms, usually called "strong substructure". Your answer outlines how the process works in general. This part is fine. The problem is that trees do not satisfy amalgamation under the substructure relation (See an older question of mine: math.stackexchange.com/q/1810644/142433) So the question is: Under what morphisms do finite trees satisfy amalgamation and joint embedding? This part was not clear to me. $\endgroup$ Jul 27, 2016 at 22:20
  • $\begingroup$ Ah, thanks! What you call a "tree" in the other question I suppose is the set-theorist definition that Jesse McKeown referred to. I would call it a "directed forest", probably, because it is not required to be connected. But I think the main thing driving the failure of amalgamation is the directedness. I believe that undirected trees or forests satisfy amalgamation under embedding. If you want a notion of directedness, you could use rooted trees / rooted forests, which I believe also satisfy amalgamation under embedding. $\endgroup$
    – Tim Campion
    Jul 28, 2016 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.