Forcing an ultrahomogeneous structure in a non-relational language

Question

The "longer" Hodges has the following exercise (8.2.10):

Let $L$ be a finite relational signature and $K$ a non-empty class of $L$-structures which has HP, JEP and AP. Let $T$ be the theory of structures whose age is $\subseteq K$. Show that the Fraisse limit of $K$ is an enforceable model of $T$.

The emphasis is mine. If I were to believe the Gricean maxims, I would assume that this is not generally true of a functional language $L$. In fact, I can kind of see that how adding relations in other stages of the construction messes up what you do with partial isomorphisms.

Is there an illuminating example of such a theory $T$ in a functional language where the Fraisse limit is not enforceable?

Addendum: The construction here is analogous to the proof of the omitting types theorem or any other Henkin-type constructions. We expand $L$ with countably many constants to obtain $L^+$. We construct an $\omega$-chain $(T_i)$ of finite sets of literals in $L^+$ that are consistent with $T$ by stages. A player $E$ is assigned an infinite-coinfinite subset $X_E$ of $\omega$ and is responsible for saying what $T_i$ is for $i \in X_E$. Finally, we build the so-called canonical model $A$ of $T^+ := \bigcup_i T_i$ from the terms made up of the constants occurring in $T$ and taking the quotient by the relations following from $T + T^+$.

A property $P$ of the structure $A$ being built by forcing is enforceable if the player responsible for that property has a winning strategy (where a win for her is to have $A$ satisfy $P$); a structure $M$ is enforceable if the property of being isomorphic to $M$ is enforceable.

Answer 1

I think this comes down to how we treat ages and Fraisse limits in functional languages.

The direct analogue of ages in the functional case is to talk about finitely generated structures. However, this winds up clashing horribly with enforceability, which is instead about finitely approximated structures. For example, take $K$ to be the class of all finitely generated abelian goups. Then we can appropriately form the (analogue of the) Fraisse limit of $K$, and unless I'm missing something it's just $(\bigoplus_\mathbb{N}\mathbb{Q})\oplus (\bigoplus_\mathbb{N}\mathbb{Q}/\mathbb{Z})$ - certainly it has many elements of infinite order. But in the corresponding game, player $2$ can enforce that every element has finite order (and, again unless I'm missing something, $\bigoplus_\mathbb{N}\mathbb{Q}/\mathbb{Z}$ is enforceable).

For relational structures, though, there's no difference between "finitely generated" and "finite" so this issue doesn't arise.

Answer 2

Just to add to Noah's answer: In Fraïssé theory settings, it's common to assume we're working in a finite relational language. But usually what's actually important is the following (more technical) consequence: For every $n$, there are only finitely many isomorphism types of $n$-generated structures in $K$. Let's call this condition $(\star)$.

Here an $n$-generated structure is a structure $A$ and an $n$-tuple $\overline{a}$ such that $A = \langle\overline{a}\rangle$, and an isomorphism of $n$-generated structures $(A,\overline{a})\cong (B,\overline{b})$ is an isomorphism $\sigma\colon A\to B$ such that $\sigma(\overline{a}) = \overline{b}$.

If $T$ is the theory of structures with age contained in $K$, then an isomorphism class of $n$-generated structures in $K$ is essentially the same as a complete quantifier-free type in $n$ free variables consistent with $T$. So $(\star)$ is equivalent to for every $n$, there are only finitely many complete quantifier-free $n$-types consistent with $T$.

This condition is exactly what's needed to prove that the theory of the Fraïssé limit of $K$ is $\aleph_0$-categorical and has quantifier elimination, and I believe it's also sufficient to prove that the Fraïssé limit is enforceable in Hodges's sense. I think Hodges is just trying to keep things simple by saying "finite relational", which is a non-technical condition that everyone understands.

Note that in a relational language, every $n$-generated structure has size at most $n$, so $(\star)$ just asserts that there are only finitely many structures of each size in $K$ up to isomorphism. This is trivial if the language is finite, but may fail in an infinite language.

As soon as we add function symbols, $(\star)$ has more teeth. It implies that for all $n$, there is a finite upper bound $N$ on the size of $n$-generated structures: otherwise, there infinitely many terms $(t_i)_{i\in \omega}$ such that the formulas $t(x_1,\dots,x_n) = x_{n+1}$ are pairwise non-equivalent modulo $T$, and hence there are infinitely many quantifier-free $(n+1)$-types consistent with $T$. In particular, $(\star)$ implies every finitely generated structure in $K$ is finite - as Noah pointed out, this is not the case in the class of abelian groups!

If the language is finite, $(\star)$ is equivalent to the above condition: for all $n$, there is a finite upper bound $N$ on the size of $n$-generated structures.

Here are some examples:

• Consider the (infinite, relational) language with one $n$-ary relation $R_n$ for each $n$. The class of all finite structures in this language does not satisfy $(\star)$, since there are $2^{\aleph_0}$ $1$-generated structures: for each $n$, we can choose independently whether $R_n(a,a,\dots,a)$ holds.

• Now let $K$ be a class of finite structures in the language above such that if $R_n(a_1,\dots,a_n)$ holds, then $a_i\neq a_j$ for all $1\leq i < j \leq n$ (e.g. the class such that each $R_n$ is a hypergraph relation). Then $K$ satisfies $(\star)$, since only the relations $R_1,\dots,R_n$ can be nontrivial on an $n$-generated structure.

• The class of finite Boolean algebras satisfies $(\star)$, since the language is finite, and an $n$-generated Boolean algebra has size at most $2^{2^n}$.

• The class of finite fields of charcteristic $p$ does not satisfy $(\star)$: every finite field has cyclic multiplicative group, so every finite field of characterstic $p$ can be $1$-generated.