7
$\begingroup$

There are a number of famous results to the effect that "countable structures" of a certain type have a universal, "homogeneous" structure of the same type into which they all embed with various nice properties. For example, Urysohn's metric space, Rado's graph and Higman's finitely-presented group all follow this pattern.

Cameron in "The Rado graph and the Urysohn space" notes some relationships between those two objects, while Aksoy, Glassman, Kosheleva and Kreinovich in "From Urysohn's Universal Metric Space To A Universal Space-Time" show that Urysohn's construction can be converted into a version for a suitable definition of "spacetime".

Given the analogies between these constructions, the following questions seem natural:

  • Does a general category-theoretic version exist?

  • Assuming it does, what are the conditions on the "type of structure" giving the category in order for the result to apply?

$\endgroup$
1
  • 2
    $\begingroup$ This may be relevant. $\endgroup$ Commented Aug 9, 2016 at 17:35

1 Answer 1

7
$\begingroup$

The following is essentially a copy-paste from a stackexchange answer I gave here, so I'll make it community wiki.

Trevor Irwin's thesis gives a categorical treatment of Fraïssé limits, a construction which can be used to construct the Rado graph, the Higman group, and the rational Urysohn space. It takes a bit of extra work to get the real Urysohn space from the general theory. This also yields algebraic closures of fields, for instance. In model theory, it gives Hrushovski constructions, and with a slight generalization, also saturated models in model theory. The construction is also similar to Quillen's small object argument, which is not surprising once you see that it's about constructing injective objects.

Let $\mathcal{C}$ be a category and let $\mathcal{F} \subseteq \mathcal{C}$ be a full subcategory. (The following is most interesting when the morphisms of $\mathcal{F}$ are all monos, so $\mathcal{C}$ and $\mathcal{F}$ will often be non-full subcategories of "embeddings" in some category of primary interest.)

  • We say that $X \in \mathcal{C}$ is $\mathcal{F}$-universal if every $F \in \mathcal{F}$ admits a morphism $F \to X$.

  • We say that $X \in \mathcal{C}$ is $\mathcal{F}$-injective if for every $F' \leftarrow F \to X$ with $F,F' \in \mathcal{F}$ there exists $F' \to X$ making a commutative triangle.

  • We say that $X \in \mathcal{C}$ is $\mathcal{F}$-homogeneous if for every $X \leftarrow F \to X$ with $F \in \mathcal{F}$, there is an automorphism $X \cong X$ making a commutative triangle.

Now suppose that

  1. $\mathcal{C}$ has colimits of ($\mathbb{N}$-indexed) chains $C_0 \to C_1\to \dots$ (equivalently, $\mathcal{C}$ has countable filtered colimits).

  2. $\mathcal{F}$ has the property that if $f: F \to \varinjlim C_i$ is a morphism in $\mathcal{C}$ from an object $F \in \mathcal{F}$ to a colimit $\varinjlim C_i$ of a chain $C_0 \to C_1 \to \dots$ in $\mathcal{C}$, then $f$ factors through some $C_i$ (this follows if every $F \in \mathcal{F}$ is finitely presentable in $\mathcal{C}$).

Proposition. If (1) and (2) hold and $X \in \mathcal{C}$ is a colimit of a chain of objects of $\mathcal{F}$, then the following are equivalent and characterize $X$ up to isomorphism:

(i.) $X$ is $\omega\mathcal{F}$-universal and $\mathcal{F}$-homogeneous

(ii.) $X$ is $\mathcal{F}$-universal and $\mathcal{F}$-homogeneous

(iii.) $X$ is $\mathcal{F}$-universal and $\mathcal{F}$-injective.

Here $\omega \mathcal{F}$ denotes the closure of $\mathcal{F}$ under colimits of chains.

(Irwin assumes an additional "monotonicity" condition, but as far as I can see this is not necessary.)

Proof. (i.) -> (ii.) is trivial. (ii.) -> (iii.) requires just a moment's thought. (iii.) -> (ii.) uses a back-and-forth argument, inductively building up both directions of an isomorphism, working up the chain defining $X$. (iii.) -> [the first clause of (i.)] is easy. The fact that (iii.) characterizes $X$ up to isomorphism uses another back-and-forth argument.

Let's call an $X$ satisfying the equivalent condtions of the proposition $\mathcal{F}$-saturated. We can get existence of such an $X$ with some mild additional conditions on $\mathcal{F}$:

  1. $\mathcal{F}$ has the joint embedding property: any pair of objects $F_1, F_2 \in \mathcal{F}$, admit a cocone, i.e. there is a diagram $F_1 \to F_3 \leftarrow F_2$ in $\mathcal{F}$.

  2. $\mathcal{F}$ has the amalgamation property: any span $F_1 \leftarrow F_0 \to F_2$ in $\mathcal{F}$ admits a cocone, i.e. it can be completed to a commutative square like

$\require{AMScd} \begin{CD} F_0 @>>> F_1\\ @VVV @VVV \\ F_2 @>>> F_3 \end{CD} $

Theorem. If (1,2,3,4) hold and $\mathcal{F}$ is essentially countable then there exists an $\mathcal{F}$-saturated object $X \in \mathcal{C}$ which is a colimit of a chain of objects of $\mathcal{F}$. Conversely, if there exists an $X \in \mathcal{C}$ which is $\mathcal{F}$-injective and $\mathcal{F}$-universal, and which is a colimit of a chain of objects of $\mathcal{C}$ and (2) holds, then (3,4) hold.

Proof. We construct a chain $X_0 \to X_1 \to \dots$ whose colimit is will be $X$. The idea is to solve the lifting problems of $\mathcal{F}$-universality and $\mathcal{F}$-injectivity by using (3) and (4) to extend the chain with solutions to these lifting problems. Then since any lifting problem must factor through a finite stage of the chain, it can be solved at a finite stage and thus be solved in the colimit. Some care must be taken in doing this, see Irwin's thesis or another reference on the Fraïssé construction. The "conversely" statement takes just a moment's reflection.

When we take $\mathcal{C}$ to be the category of graphs and embeddings and $\mathcal{F}$ to be the subcategory of finite graphs, we construct the Rado graph this way, and similarly other Fraïssé limits. When we take $\mathcal{C}$ to be the category of rational metric spaces and isometric embeddings and $\mathcal{F}$ to be the subcategory of finite metric spaces, we construct the rational Urysohn space this way. When we take $\mathcal{C}$ to be groups and injective homomorphisms and $\mathcal{F}$ to be the finitely presented groups, we get the Higman group, and so forth.

Everything generalizes easily to cardinalities $\kappa$ larger than countable -- in (1) $\mathcal{C}$ will have to be closed under colimits of chains of length $\leq \kappa$, while in (2), $\mathcal{F}$ will have to have this property with respect to chains of length $\kappa$ and moreover be closed under colimits of chains of length less than $\kappa$. (3) and (4) require no modification. In the existence theorem we require that $\mathcal{F}$ have size essentially $\leq \kappa$. By taking $\mathcal{C}$ to be the category of models of a first-order theory and $\mathcal{F}$ to be the models of size $< \kappa$, we recover the construction of saturated models in the usual sense in model theory, with the usual set-theoretical provisos.

$\endgroup$
2
  • $\begingroup$ A very belated thankyou for this answer, which I've only just read through properly and is about as comprehensive as I could have wished for! I came back to this question after trying to familiarize myself with the notion of saturated model, and it's reassuring to hear that they can be treated in essentially the same way. $\endgroup$ Commented Nov 7, 2016 at 9:01
  • $\begingroup$ A very belated response: glad to help! $\endgroup$ Commented Dec 5, 2016 at 1:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .