Free objects in first order theories

Question

Let $T$ be a first order theory, $M$ its elementary class and consider its forgetfull functor $$M \stackrel{U}{\to} \text{Set}. $$

I would like to characterize those theories such that $U$ has a left adjoint. In fact this can be done.

---

If $M$ is cocomplete then $U$ has a left adjoint iff $T$ is equivalent to a limit theory in $L_{\omega}$.

Proof: This is quite an exercise. I will prove just the necessity. If $F$ exists then $F(\{\cdot\})$ is finitely presentable and also a strong generator of $M$ (here I am using that $U$ always commutes with directed colimits when T is first order), thus $M$ is finitely locally presentable. By the characterization theorem of finitely locally presentable categories, $T$ is equivalent to a limit theory.

---

(Q1): What if $M$ is not cocomplete?

In fact if the adjoint exist, $M$ must be finitely accessible but I do not know any characterization theorem for finitely accessible categories. This is anyway a strong request on the elementary class.

If U has a left adjoint then $M$ is finitely accessible.

Now there are two natural questions.

(Q2): Is the other implication true?

(Q3): What happens if one replaces $M$ with an abstract elementary class?

Answer 1

Here's a second attempt at answering the "homomorphism" version of Q3.

Proposition: Suppose that $U: \mathrm{Hom}(T) \to \mathsf{Set}$ has a left adjoint $F$. Expand $T$ by those definable functions in $T$ which are preserved by all homomorphisms between models of $T$ to obtain a theory $T'$. Let $V(T')$ be the varietal hull of $T$, i.e. it has all the function symbols of $T'$ but not the relation symbols, and is axiomatized by the universally quantified equations that hold in $T'$. Then

1. The reduct of $F$ to just the $T'$-function symbols is the usual free functor $\mathsf{Set} \to \mathrm{Hom}(V(T'))$ (this specifies the interpretation of the $T'$-function symbols in $F(n)$).
2. If $\phi$ is an atomic formula in $T'$, then $\forall \bar x. \phi(\bar x)$ holds if and only if $\phi(\bar e)$ holds in $F(n)$, where $\bar e$ are the generators of $F(n)$ (this specifies the interpretation of the $T'$-relation symbols in $F(n)$).

Conversely, if $V$ is a variety, $T'$ is an expansion of $V$ with the same function symbols, and $T$ is a reduct of $T$ with the same relation symbols and $\mathrm{Hom}(T) = \mathrm{Hom}(T')$, then the free $V$-algebra functor lifts to a left adjoint to $U: \mathrm{Hom}(T') \to \mathsf{Set}$ if and only if the $\mathrm{Lang}(T')$-structure on $F(n)$ defined by (2) models $T'$.

Proof: Let us prove the first part. For $\bar a \in M \in \mathrm{Hom}(T)$, let $\langle \bar a \rangle: F(n) \to M$ denote the unique homomorphism such that $ \langle \bar a \rangle(\bar e) = \bar a$. For $t \in F(n)$, let $[t]_M (\bar a) = \langle \bar a \rangle(t)$. Let $\mathbf{R}(\bar x, \bar{\mathbf{y}}) = \wedge\wedge_i R_i(\bar x,\bar{\mathbf{y}})$ be the infinite conjunction of all positive quantifier-free formulas $R_i(\bar x, \bar{\mathbf{y}})$ such that $F(n) \models R_i(\bar e,\bar{\mathbf{t}})$, where $\bar{\mathbf{t}}$ is a fixed enumeration of the elements of $F(n)$. The uniqueness of the homomorphism $\langle \bar a \rangle$ for each $\bar a$ tells us that $T \vdash \forall \bar x,\bar{\mathbf{y}},\bar{\mathbf{y}}'. \mathbf{R}(\bar x,\bar{\mathbf{y}}) \wedge \mathbf{R}(\bar x, \bar{\mathbf{y}}') \to \wedge \wedge_i \mathbf{y}_i = \mathbf{y}'_i$. For any $t \in F(n)$, it follows by compactness that we have $T \vdash \forall \bar x, \bar y, \bar y'. R_t(\bar x,y,\bar y) \wedge R_t(\bar x,y',\bar y) \to y = y'$ for some (positive, quantifier-free) $R_t(\bar x, y, \bar y)$, and that in fact $\exists \bar y. R_t(\bar x, y,\bar y)$ is a definition of $y=[t](\bar x)$ valid in all models of $T$. So there is a function symbol $f(\bar x)$ in $T'$ such that $f(\bar a) = [t](\bar a)$ for all $\bar a$ and in particular, $f(\bar e) = [t](\bar e) = t$.

This tells us that every $t \in F(n)$ is representable as $t = f(\bar e)$ for some function $f(\bar x)$ in $T'$. Now if $f(\bar e) = g(\bar e)$ holds for two functions $f(\bar x)$ and $g(\bar x)$ in $T'$, then for any $\bar a \in M^n$ we have $f(\bar a) = f(\langle \bar a \rangle(\bar e)) = \langle \bar a \rangle(f(\bar e)) = \langle \bar a \rangle (g(\bar e)) = g(\langle \bar a \rangle(\bar e)) = g(\bar a)$, so the universal equation $\forall \bar x . f(\bar x) = g(\bar x)$ holds in $V(T')$. Conversely, of course, if $\forall \bar x. f(\bar x) = g(\bar x)$ holds, then in particular $f(\bar e) = g(\bar e)$ holds. This proves (1). Then (2) follows by similar reasoning.

(As a side note, given that $F$ exists, the functions of $T'$ are precisely those definable in $T$ by formulas of the form $f(\bar x) = y \leftrightarrow \exists \bar y . R(\bar x, y, \bar y)$ with $R$ a positive quantifier-free formula; we have shown one direction, while the other holds for any theory $T$.)

The converse is clear.

Answer 2

Let me explain why the question, raised in the comments, of what the morphisms of $M$ are, sheds a lot of light on this question. If $T$ is a first-order theory I will use $\mathrm{Mod}(T)$ to denote its category of models with elementary embeddings as morphisms, and $\mathrm{Hom}(T)$ to denote its category of models with homomorphisms as morphisms.

Observation: Let $M$ be a category and $U: M \to \mathsf{Set}$ a functor, and suppose that $U$ factors through the non-full subcategory $\mathsf{Set}_\mathrm{inj}$ of sets and injective maps. Suppose also that $U$ has a left adjoint. Then:

• $U$ must actually factor through the subcategory $\{\emptyset,1\}$.
• If moreover $U$ is faithful, then $M$ is a poset.

A proof will be given at the end. In particular, the hypotheses of both bullet points are satisfied in the following cases:

1. $M= \mathrm{Mod}(T)$ and $U$ the usual forgetful functor.

2. $M$ is $\mathsf{Set}_\mathrm{inj}$.

3. $(M,U)$ is any AEC, as in (Q3).

This leads to the following conclusions:

• By (1) if in Q1 we take $M$ to mean $\mathrm{Mod}(T)$, then the answer is "$F$ exists only in degenerate cases".

• By (2), the answer to Q2 is: "No".

• By (3), the answer to Q3 is: "If $(M,U)$ is an AEC, then $F$ exists only in degenerate cases."

Let us also observe that

1. For any first-order theory $T$, there is a first-order theory $T'$ (the Morleyization of $T$) such that $\mathrm{Hom}(T') = \mathrm{Mod}(T)$, with the same forgetful functor to $\mathsf{Set}$.

2. $\mathrm{Hom}(T)$ need not be accessible. For example, let $T$ be the theory $\exists x \exists y x \neq y$. Then $M$ is the category $\mathsf{Set}_{\geq 2}$ of sets of cardinality at least 2, which doesn't even have split idempotents.

3. If $T$ is a complete theory with infinite models, then $\mathrm{Mod}(T)$ is never finitely accessible.

Now, if $M$ means $\mathrm{Hom}(T)$, we can conclude that

• On account of (1) the answer to Q1 is "There are lots cases where $F$ does not exist".
• On account of (2) and OP's observation that if $F$ exists then $M$ is finitely accessible, the answer to Q1 is "There is at least one case, and likely lots of cases, where $F$ does not exist".
• (1),and (3), together again with OP's observation about finite accessibility, give yet another way to see the answer to Q1 is "there are lots of cases for which $F$ does not exist.

But Q1 is pretty vague. It's possible that what the OP really means is "Even if it's rare for $F$ to exist, can we identify any conditions more general than cocompleteness under which $F$ exists?". In that case, the answer seems to be: "In light of the above observations, and especially (2), probably one can say no more about this question for $M = \mathrm{Hom}(T)$ than one can say about the case where $M$ is an arbitrary concrete category (which is to say, not much)".

---

Proof of Observation:

In $\mathsf{Set}$, every morphism except for the morphisms $\emptyset \to S$ where $S \neq \emptyset$ factors as a split mono followed by a split epi. But in $M$, every split mono and every split epi is an isomorphism. So the restriction $F|_{\mathsf{Set}_{\neq \emptyset}}: \mathsf{Set}_{\neq \emptyset} \to M$ of $F$ to the category of nonempty sets factors through the localization of $\mathsf{Set}_{\neq \emptyset}$ at all morphisms, which is the terminal category.

Now the coproduct $2 = 1 \amalg 1$ is preserved by $F$. The two coproduct injections $1^\to_\to 2$ are exchanged by an automorphism of 2 which is sent to the identity by $F$, so the two coproduct injections are the same map $F(1) \to F(2)$. This implies that for any object $X \in M$, there is at most one map $F(1) \to X$. But by adjointness, maps $F(1) \to X$ correspond to elements of $X$. So every object of $M$ has at most one element.

Moreover, $F(\emptyset)$ must be an initial object. This, along with the universal property of $F(1)$, implies the first bullet point. If $U$ is faithful, this means that $M$ must be a poset, with $F(\emptyset)$ a bottom element $\bot$. By its universal property, $F(1) = \min(U^{-1}(1))$. Moreover no element of $U^{-1}(1)$ is below an element of $U^{-1}(0)$. Conversely, any poset and functor $U$ meeting this description have a left adjoint $F$ meeting this description.