13
$\begingroup$

All structures are countable with countable signature.

Given a structure $\mathcal{A}$, the age of $\mathcal{A}$, $Age(\mathcal{A})$, is the set of structures isomorphic to finitely-generated substructures of $\mathcal{A}$ (see http://en.wikipedia.org/wiki/Age_(model_theory)). (This isn't really a set, but we can restrict attention to those structures contained in $H_{\omega_{17}}$, say.) $Age(\mathcal{A})$ automatically satisfies the Joint Embedding and Hereditariness properties, but may lack the Amalgamation property: an example of this is the undirected graph $\mathcal{G}$ with integers as vertices, and an edge between ever pair $(z, z+1)$.

Given a collection $\mathbb{K}$ of finite structures closed under isomorphism with the Joint Embedding, Hereditariness, and Amalgamation properties, we can form the Fraïssé limit of $\mathbb{K}$, the unique homogeneous structure $F(\mathbb{K})$ with $Age(F(\mathbb{K}))=\mathbb{K}$. Specifically, let $\mathbb{P}(\mathbb{K})=\mathbb{P}$ be the poset whose elements are finite sequences $\emptyset\prec \mathcal{A}_0\prec . . . \prec\mathcal{A}_n$ of structures in $\mathbb{K}$, ordered by reverse extension; then forcing with $\mathbb{P}$ produces the Fraïssé limit. Formally, there is a countable collection $\mathcal{D}$ of dense sets in $\mathbb{P}$ such that the direct limit of the terms of any $\mathcal{D}$-generic filter through $\mathbb{P}$ is isomorphic to the Fraïssé limit.

Now if $\mathbb{K}$ lacks the Amalgamation property, there will be no homogeneous structure with age $\mathbb{K}$. The poset $\mathbb{P}(\mathbb{K})$, however, still makes sense, and we can consider the collection $Fil(\mathbb{K})$ of all structures formed by (taking direct limits of terms of) maximal filters through $\mathbb{P}(\mathbb{K})$.

Moreover, we can compare structures in $Fil(\mathbb{K})$ in terms of relative genericity. For $D\subseteq \mathbb{P}(\mathbb{K})$ dense, let $\mathcal{O}_D$ be the set of structures which can be built by filters hitting $D$. These sets $\mathcal{O}_D$ then generate a topology $\tau_\mathbb{K}$ on $Fil(\mathbb{K})$. This space is terrible, but seems reasonably natural if what we're interested in is how generic elements of $Fil(\mathbb{K})$ are.

As it turns out, elements of $Fil(\mathbb{K})$ can be extremely generic, even though the Fraïssé limit as such may not exist. Specifically, let $Gen(\mathbb{K})$ be the class of isomorphism classes of structures $\mathcal{A}$ such that in every open $\mathcal{O}_D$ there is a copy $\mathcal{B}\cong\mathcal{A}$. Then, for example, consider the graph $\mathcal{G}$ from the first paragraph and let $\mathbb{K}=Age(\mathcal{G})$. $Fil(\mathbb{K})$ is precisely the class of acyclic infinite graphs in which each vertex has degree at most 2. However, the graph $\mathcal{G}$ is special among these graphs, since there is a countable collection $\mathcal{D}$ of dense subsets of $\mathbb{P}(\mathbb{K})$ such that any $\mathcal{D}$-generic filter corresponds to $\mathcal{G}$. This means $Gen(\mathbb{K})=\{\mathcal{G}\}$, and so in some sense $\mathcal{G}$ is the closest thing to a Fraisse limit of $Age(\mathcal{G})$ as we might reasonably expect to exist.

In general, if $Gen(Age(\mathcal{A}))$ has precisely one element, denote that element by $G(\mathcal{A})$, and call it the generalized Fraïssé limit of $Age(\mathbb{A})$.


My questions are as follows. First, the obvious:

What are some sources for learning about this construction? In particular, what's it actually called?

Second,

When is $Gen(Age(\mathcal{A}))$ nonempty? When does it have exactly one element?

Finally, the fact that $G(\mathcal{G})=\mathcal{G}$ motivates me to ask:

Suppose $Gen(Age(\mathcal{A}))$ has exactly one element. What can we say about $G(\mathcal{A})$ in relation to $\mathcal{A}$? For example, what structures $\mathcal{A}$ do we have $G(\mathcal{A})=\mathcal{A}$?

A couple quick observations: any homogeneous structure $\mathcal{A}$ will certainly have $G(\mathcal{A})=\mathcal{A}$. On the other hand, consider the graph $\mathcal{G}_\omega$ consisting of the disjoint union of infinitely many copies of $\mathcal{G}$; then $G(\mathcal{G}_\omega)=\{\mathcal{G}\}$, so not every structure has this property even if it has singleton $Gen$. Finally, note that we will always have $G(G(\mathcal{A}))=G(\mathcal{A})$ if $G(\mathcal{A})$ exists.

$\endgroup$
  • $\begingroup$ You first lost me at "ordered by reverse extension", and then completely at the word forcing. But just to state the obvious: Except for your starting with a single structure rather than an incomplete theory, some aspects sound a lot like a model companion. $\endgroup$ – user12283 Oct 18 '15 at 16:11
7
$\begingroup$

This question has been around for a long time, and the OP himself has known the answer for almost as long! But just in the interest of putting some references out there, I'll give an answer:

Let $\mathbb{K}$ be a class of finite structures. Then $Gen(\mathbb{K})$ contains a unique isomorphism class $M_{\mathbb{K}}$ (often called the generic limit of $\mathbb{K}$) if and only if $\mathbb{K}$ is countable up to isomorphism, has the JEP, and has the weak amalgamation property:

(WAP) For any $A\in \mathbb{K}$, there exists $B\in \mathbb{K}$ and an embedding $f\colon A\to B$ such that for all $C_1,C_2\in \mathbb{K}$ and embeddings $g_1\colon B\to C_1$ and $g_2\colon B\to C_2$, there exists $D\in \mathbb{K}$ and embeddings $h_1\colon C_1\to D$ and $h_2\colon C_2\to D$ such that $h_1\circ g_1\circ f = h_2\circ g_2\circ f$: $\require{AMScd}$ \begin{CD} A @>f>> B\\ @VfVV @VVg_1V\\ B @. C_1\\ @Vg_2VV @Vh_1VV\\ C_2 @>h_2>> D \end{CD} Note that we don't require $h_1\circ g_1 = h_2\circ g_2$, so the images of $B$ in $D$ under $h_1\circ g_1$ and $h_2\circ g_2$ may be different.

The usual amalgamation property (AP) has the same statement, but with $B = A$ and $f = \text{id}_A$.

References: The equivalence between WAP and the existence of a generic limit was identified by Ivanov in his paper Generic expansions of $\omega$-categorical structures and semantics of generalized quantifiers and independently by Kechris and Rosendal in their paper Turbulence, amalgamation and generic automorphisms of homogeneous structures. A clear presentation (in the wider context of finitely generated structures) can be found in the recent paper Games on finitely generated structures by Krawczyk and Kubiś. I also gave an exposition (in the wider context of classes of finite structures with specified "strong embeddings" between them) in my PhD thesis (Section 4.2).

So that answers the first and second questions. For the third question, a structure $M$ is the generic limit of its age if and only if it satisfies weak homogeneity: For any substructure $A\leq M$, there is an embedding $f\colon A\to B$ (with $B\in Age(M)$) such that for any embedding $g\colon B\to C$ (with $C\in Age(M)$), $C$ embeds in $M$ over $A$, i.e. there is an embedding $h\colon C\to M$ such that $h\circ g\circ f$ is the inclusion of $A$ into $M$.

The condition of weak homogeneity is implicitly there in Ivanov's original paper (since it's what powers the back-and-forth argument establishing uniqueness of the generic limit), but he doesn't give it a name. Again, my thesis is a reference for this equivalence.

$\endgroup$
  • $\begingroup$ Holy crud, I completely forgot about this question - thanks for putting it to rest! (And I think it's worth pointing out that the only reason I knew all this was because you explained it to me!) $\endgroup$ – Noah Schweber Jan 27 '17 at 22:37
3
$\begingroup$

Kubis wrote a lot on this subject.

This.

This.

I also have a small contribution on this subject.

There is also an even more abstract point of view, started by Rosicky in '80.

The general motto is that the amalgamation property has a key role in the construction of the Fraissé limit, any weakening of it corresponds to a weakening of the universal property limit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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