Introduction
The compactness theorem is one of the cornerstones of model theory. Together with Łoś’ theorem, it provides a powerful bridge between local and global properties, showing that structures satisfying arbitrarily large finite fragments of a theory can be assembled into genuine models. These ideas are behind some of the most important techniques in the subject, ranging from the model-theoretic method of diagrams and amalgamation to the construction of nonstandard models of analysis.
The first-named and second-named authors acknowledge with gratitude the support of the Marie Skłodowska-Curie postdoctoral fellowship 101130801 and the EPSRC postdoctoral fellowship EP/X027139/1, respectively.
From a categorical perspective, compactness is closely related to the existence and well-behaviour of ultraproducts. In the ordinary setting, Łos’ theorem identifies the interpretation of a first-order formula φ \varphi φ in an ultraproduct of structures A = ∏ i ∈ I A i / U A = \prod_{i\in I} A_i/\mathcal{U} A = ∏ i ∈ I A i / U with the ultraproduct of their interpretations:
φ ( A ) ≅ ∏ i ∈ I φ ( A i ) / U . \varphi(A) \cong\prod_{i\in I} \varphi(A_i)/\mathcal{U}. φ ( A ) ≅ i ∈ I ∏ φ ( A i ) / U .
The compactness theorem then follows by a standard ultraproduct construction.
The interaction between logic and category theory has proved remarkably fruitful, leading to deep connections with accessible categories [31 , 4 ] , ultracategories [30 , 28 ] , Grothendieck toposes [26 , 29 ] , the development of hyperdoctrines [25 , 24 ] , the theory of deductive systems [23 ] , and type theory [39 ] . Recently, enriched versions of regular and positive logic (also known as coherent logic) have been developed in a series of papers by Rosický and the second-named author [37 , 35 , 36 ] . These frameworks extend familiar fragments of first-order logic from sets to structures internal to a symmetric monoidal closed category V \mathcal{V} V , equipped with a suitable factorisation system ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) , which encodes how subobjects and existential quantifiers are interpreted. They recover classical regular and positive logic when V = S e t \mathcal{V} = \mathbf{Set} V = Set , while also including examples arising from algebra [33 ] , order theory [8 , 1 ] , functional analysis [13 ] , and theoretical computer science [32 ] . Despite the development of the syntax and semantics of enriched logic, a general compactness theorem has so far been missing.
Main results. The main goal of the present paper is to provide a compactness theorem for enriched logic. More precisely, we establish enriched versions of Łos’ theorem, which we will refer to as Łos-style theorems from now on, and compactness for both regular and positive logic. Our approach follows the classical strategy, but substantial new difficulties arise.
In the enriched setting, ultraproducts must be constructed at the level of the base of enrichment, and the interpretation of formulas involves the chosen factorisation system, rather than subobjects alone. As a consequence, the validity of the compactness theorem depends on categorical properties of the base of enrichment and chosen factorisation system that are automatic in S e t \mathbf{Set} Set , but that are an additional and genuine requirement in a general enriched framework.
To isolate the needed assumptions, we introduce the notion of reduced product stable enrichment bases (Theorems 3.3 and 4.1). This guarantees that reduced products interact suitably with finite limits, powers, and the chosen factorisation system. To cover the case of positive logic an additional condition is required, namely what we call the ultraproduct covering property (Theorem 4.2). This property controls the interaction between ultraproducts and finite coproducts and turns out to be satisfied in a large number of natural examples.
Under these hypotheses we prove Łos-style theorems for enriched logic. The first theorem states that the interpretation of regular formulas commutes with reduced products, and that the interpretation of positive formulas commutes with ultraproducts. The second theorem gives the familiar consequence: if a sequent holds on a large subset of the factors, then it holds in the corresponding reduced product (Theorem 4.6 establishes a converse under additional assumptions).
Theorem 1.1 (Łos-style theorem 1). Assume that V \mathcal{V} V is reduced product stable. Let L \mathbb{L} L be a language on V \mathcal{V} V and let φ \varphi φ be an L \mathbb{L} L -formula. Let A : = ∏ i ∈ I A i / F A := \prod_{i\in I} A_i/\mathcal{F} A := ∏ i ∈ I A i / F be a reduced product of L \mathbb{L} L -structures. Then
φ ( A ) ≅ ∏ i ∈ I φ ( A i ) / F \varphi(A) \cong\prod_{i\in I} \varphi(A_i)/\mathcal{F} φ ( A ) ≅ i ∈ I ∏ φ ( A i ) / F provided that:
(i) φ \varphi φ is regular, or;
(ii) φ \varphi φ is positive, F \mathcal{F} F is an ultrafilter, and V \mathcal{V} V has the ultraproduct covering property.
Theorem 1.2 (Łos-style theorem 2). Assume that V \mathcal{V} V is reduced product stable. Let L \mathbb{L} L be a language on V \mathcal{V} V and let σ \sigma σ be a sequent of L \mathbb{L} L -formulas. Let A : = ∏ i ∈ I A i / F A := \prod_{i\in I} A_i/\mathcal{F} A := ∏ i ∈ I A i / F be a reduced product of L \mathbb{L} L -structures. Then
{ i ∈ I ∣ A i ⊨ σ } ∈ F implies A ⊨ σ , \{i \in I \mid A_i \models\sigma\} \in\mathcal{F}\quad\text{implies}\quad A \models\sigma, { i ∈ I ∣ A i ⊨ σ } ∈ F implies A ⊨ σ , provided that:
(i) σ \sigma σ is a sequent of regular formulas, or;
(ii) σ \sigma σ is a sequent of positive formulas, F \mathcal{F} F is an ultrafilter, and V \mathcal{V} V has the ultraproduct covering property.
Another key feature of this paper is the treatment of formulas with parameters, which are extremely important in applications of the compactness theorem. In contrast with the classical setting, parameters cannot in general be represented by constant symbols, unless the base of enrichment is semicartesian (i.e., the monoidal unit is terminal, see Theorem 5.3 and § 6.1 ). This forces a separate treatment of parameters (see Theorem 5.1), so that our results are applicable beyond the semicartesian case. We extend our second Łoś-style theorem so that it can handle parameters (see Theorem 5.7 ). Using this we then prove the compactness theorem for enriched regular and positive logic, allowing parameters.
Theorem 1.3 (Compactness). Assume that V \mathcal{V} V is reduced product stable. Let L \mathbb{L} L be a language on V \mathcal{V} V , let T \mathbb{T} T be a theory, and let Σ \Sigma Σ be a set of sequents with parameters in P \mathcal{P} P . Assume also that the monoidal unit I I I is finitely presentable or that all sequents in Σ \Sigma Σ are of the form ⊤ ⊢ ψ ( p 1 , … , p n ) \top\vdash\psi(p_1,\ldots,p_n) ⊤ ⊢ ψ ( p 1 , … , p n ) . If every finite subset of T ∪ Σ \mathbb{T} \cup\Sigma T ∪ Σ has a model then T ∪ Σ \mathbb{T} \cup\Sigma T ∪ Σ has a model, provided that:
(i) every sequent in T ∪ Σ \mathbb{T} \cup\Sigma T ∪ Σ is a sequent of regular formulas (possibly with parameters), or;
(ii) every sequent in T ∪ Σ \mathbb{T} \cup\Sigma T ∪ Σ is a sequent of positive formulas (possibly with parameters) and V \mathcal{V} V has the ultraproduct covering property.
As an application, we develop an enriched version of the model-theoretic method of diagrams. Given an enriched structure A A A , we show that homomorphisms with domain A A A correspond precisely to models of the set Diag ( A ) \operatorname{Diag}(A) Diag ( A ) of all (regular) atomic formulas with parameters from A A A that are true in A A A (this is called the diagram of A A A , see Theorem 6.3).
Theorem 1.4 (Enriched model-theoretic method of diagrams). Assume that V 0 \mathcal{V}_0 V 0 is locally finitely presentable with its finitely presentable objects closed under the monoidal product and that ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is proper. Let L \mathbb{L} L be a language on V \mathcal{V} V and let A A A be an L \mathbb{L} L -structure. Then the functor
A / Str ( L ) 0 ⟶ Mod ( Diag ( A ) ) , A/\operatorname{Str}(\mathbb{L})_0 \longrightarrow\operatorname{Mod}(\operatorname{Diag}(A)), A / Str ( L ) 0 ⟶ Mod ( Diag ( A )) , h : A → B ⟼ ( B , ( h ∘ a ) p a ∈ P ( A ) ) , h\colon A \to B \longmapsto(B,(h \circ a)_{p_a \in\mathcal{P}(A)}), h : A → B ⟼ ( B , ( h ∘ a ) p a ∈ P ( A ) ) , which is the identity on arrows, is an isomorphism of categories.
We use this machinery to derive amalgamation properties, which ultimately result in the power of the central model-theoretic notion of a type as a set of formulas. As a corollary we show how spans of structures, or even models of a fixed theory, can be amalgamated (Theorem 7.7) if one of the arrows is an immersion (i.e., reflects truth of formulas).
Theorem 1.5. Assume that V \mathcal{V} V is reduced product stable, that V 0 \mathcal{V}_0 V 0 is locally finitely presentable, that ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is proper, and that I I I is E \mathcal{E} E -projective.
Let A A A be an L \mathbb{L} L -structure and B B B be a model of some L \mathbb{L} L -theory T \mathbb{T} T , and let A ← a X → b B A \xleftarrow{a} X \xrightarrow{b} B A a X b B be a span of arrows in V \mathcal{V} V . Suppose that tp p p ( a ; A ) ⊆ tp p p ( b ; B ) \operatorname{tp}_{\mathrm{pp}}(a;A) \subseteq\operatorname{tp}_{\mathrm{pp}}(b;B) tp pp ( a ; A ) ⊆ tp pp ( b ; B ) . Then there is a model C C C of T \mathbb{T} T together with homomorphisms f : A → C f\colon A \to C f : A → C and g : B → C g\colon B \to C g : B → C such that f ∘ a = g ∘ b f \circ a = g \circ b f ∘ a = g ∘ b , provided that:
(i) T \mathbb{T} T is regular, or;
(ii) T \mathbb{T} T is positive and V \mathcal{V} V has the ultraproduct covering property.
The assumptions required for our main results are shown to hold in a broad range of examples. Besides recovering the classical case over S e t \mathbf{Set} Set , our framework applies to many presheaf top-oses, categories of monoid acts, the category of abelian groups and related additive categories, categories of (small) enriched categories, and the categories of posets and pseudometric spaces. We also exhibit examples where some of the assumptions fail (sometimes we still have enough for our results concerning regular logic, see § 9.3 ), showing that the additional categorical conditions introduced in the paper are genuinely necessary.
Overview. The paper is organised as follows. In § 2 we recall the required background on factorisation systems and enriched logic. We then start by defining ultraproducts and reduced products for enriched structures in § 3 . Section 4 establishes enriched Łoś-style theorems. In § 5 we introduce parameters and prove the compactness theorem. § 6 and § 7 develop the enriched model-theoretic method of diagrams and its applications to amalgamation. The standalone § 8 studies the ultraproduct covering property and provides general criteria ensuring it holds. Finally, § 9 collects a range of examples and counterexamples illustrating the scope of our theory.
Preliminaries
Factorisation systems
Factorisation systems. We will assume the reader to be familiar with the notion of an (orthogonal) factorisation system, introduced in [11 ] . Given a category C \mathcal{C} C this consists of a pair ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) formed by classes of arrows in C \mathcal{C} C satisfying the properties of [11 Definition 2.2] . In this section we recall some basic properties of this theory.
Definition 2.1. A factorisation system ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) on a category C \mathcal{C} C is called proper if E \mathcal{E} E and M \mathcal{M} M are contained in the classes of epimorphisms and monomorphisms, respectively.
Since our enrichment base will be complete and cocomplete, the following fact (and its dual) give equivalent characterisations of M \mathcal{M} M being contained in the monomorphisms (and dually, E \mathcal{E} E being contained in the epimorphisms).
Fact 2.2 ([11 Proposition 2.1.4] ). The following are equivalent for a factorisation system ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) in a category with finite coproducts:
every arrow in M \mathcal{M} M is a monomorphism;
E \mathcal{E} E contains the strong epimorphisms;
E \mathcal{E} E contains the split epimorphism;
E \mathcal{E} E contains the regular epimorphisms;
the left cancellation property in E \mathcal{E} E holds: f g ∈ E fg \in\mathcal{E} f g ∈ E implies f ∈ E f \in\mathcal{E} f ∈ E .
Definition 2.3. Let ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) be a factorisation system on a cocomplete category C \mathcal{C} C . A set of objects X \mathcal{X} X in C \mathcal{C} C is called an E \mathcal{E} E -generator if for any object A A A in C \mathcal{C} C the arrow
∐ f : X → A , X ∈ X X ⟶ A \coprod_{f:X\to A,\ X\in\mathcal{X}} X \longrightarrow A f : X → A , X ∈ X ∐ X ⟶ A is in E \mathcal{E} E .
The notions that are usually referred to as generator and strong generator (recalled below) arise in this way and are used quite often in category theory.
We will freely use the following equivalent characterisation of E \mathcal{E} E -generators.
Proposition 2.5. Let ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) be a factorisation system on a cocomplete category C \mathcal{C} C with M \mathcal{M} M contained in the monomorphisms. A set of objects X \mathcal{X} X in C \mathcal{C} C is an E \mathcal{E} E -generator if and only if for any A ∈ C A\in\mathcal{C} A ∈ C there is a family { X i } i ∈ I \{X_i\}_{i\in I} { X i } i ∈ I of objects in X \mathcal{X} X and an arrow ∐ i ∈ I X i → A \coprod_{i\in I}X_i\to A ∐ i ∈ I X i → A in E \mathcal{E} E .
Proof. The left to right direction is trivial. The other direction follows from the canonical factorisation
∐ i ∈ I X i ⟶ ∐ f : X → A , X ∈ X X ⟶ A \coprod_{i\in I}X_i \longrightarrow\coprod_{f:X\to A,\ X\in\mathcal{X}}X \longrightarrow A i ∈ I ∐ X i ⟶ f : X → A , X ∈ X ∐ X ⟶ A
of the arrow ∐ i ∈ I X i → A \coprod_{i\in I}X_i\to A ∐ i ∈ I X i → A in E \mathcal{E} E , and the fact that E \mathcal{E} E has the left cancellation property by Theorem 2.2. □
Lemma 2.7. Let ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) be a factorisation system on a cocomplete category C \mathcal{C} C with M \mathcal{M} M contained in the monomorphisms. Assume also that C \mathcal{C} C has an E \mathcal{E} E -generator X \mathcal{X} X . Suppose that f : A → B f:A\to B f : A → B is an arrow such that any g : X → B g:X\to B g : X → B , with X ∈ X X\in\mathcal{X} X ∈ X , factors through f f f . Then f ∈ E f\in\mathcal{E} f ∈ E .
Proof. Since X \mathcal{X} X is an E \mathcal{E} E -generator we have an arrow ∑ j ∈ J g j : ∑ j ∈ J X j → B \sum_{j\in J}g_j:\sum_{j\in J}X_j\to B ∑ j ∈ J g j : ∑ j ∈ J X j → B , with X j ∈ X X_j\in\mathcal{X} X j ∈ X , which lies in E \mathcal{E} E . By assumption each g j g_j g j factors through f f f inducing an arrow g ~ j : X j → A \widetilde{g}_j:X_j\to A g j : X j → A . It follows that the triangle
∑ j ∈ J X j → ∑ j ∈ J g ~ j A ∑ j ∈ J g j ↓ ↓ f B = B \begin{CD}
\sum_{j\in J}X_j @>{\sum_{j\in J}\widetilde{g}_j}>> A\\
@V{\sum_{j\in J}g_j}VV @VV{f}V\\
B @= B
\end{CD} j ∈ J ∑ X j ∑ j ∈ J g j ↓ ⏐ B ∑ j ∈ J g j A ↓ ⏐ f B commutes. Since M \mathcal{M} M is contained in the monomorphisms, the left cancellation property holds, so that f ∈ E f\in\mathcal{E} f ∈ E .
Enriched logic
We assume the reader to be familiar with the basics of enriched category theory. For a reference on this topic, see [17 ] .
We work in the setting developed in [37 , 35 , 36 ] ; and therefore we fix a symmetric monoidal closed complete and cocomplete category V = ( V 0 , ⊗ , I ) \mathcal{V}=(\mathcal{V}_0,\otimes,I) V = ( V 0 , ⊗ , I ) endowed with a factorisation system ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) , which is:
enriched [27 ] : M \mathcal{M} M is closed in V 2 \mathcal{V}^{2} V 2 under powers (or equivalently, E \mathcal{E} E is closed under tensors);
such that every arrow in M \mathcal{M} M is a monomorphism.
Later on we shall assume additional hypotheses on V \mathcal{V} V and ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) , depending on the results that we need to prove; in particular, V 0 \mathcal{V}_0 V 0 will often be assumed to be locally finitely presentable and ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) to be proper.
We denote by V f p \mathcal{V}_{\mathrm{fp}} V fp the full subcategory spanned by the finitely presentable objects of V 0 \mathcal{V}_0 V 0 . When V \mathcal{V} V is locally finitely presentable as a closed category, meaning that V f p \mathcal{V}_{\mathrm{fp}} V fp contains the unit and is closed under the monoidal product, there is a well-behaved theory of locally finitely presentable V \mathcal{V} V -categories (see [18 ] ), and V f p \mathcal{V}_{\mathrm{fp}} V fp coincides with the full subcategory of the enriched finitely presentable objects of V \mathcal{V} V . However, we will not consider enriched presentability in this paper.
Unlike the references we follow, that allow infinitary logic, in this paper we will treat only the finitary case, so that whenever we talk about languages, formulas, and theories, we actually mean finitary languages, finitary formulas, and finitary theories. Let us begin by recalling the notions of a language L \mathbb{L} L , L \mathbb{L} L -structures, and terms in L \mathbb{L} L .
Definition 2.8 ([35 Definition 3.3] ). A (single-sorted) language L \mathbb{L} L (over V \mathcal{V} V ) is the data of:
a set of function symbols f : ( X , Y ) f:(X,Y) f : ( X , Y ) with arities X , Y ∈ V f p X,Y\in\mathcal{V}_{\mathrm{fp}} X , Y ∈ V fp ;
a set of relation symbols R : X R:X R : X , with arity an object X ∈ V f p X\in\mathcal{V}_{\mathrm{fp}} X ∈ V fp .
Definition 2.9 ([35 Definition 3.4] ). Given a language L \mathbb{L} L , an L \mathbb{L} L -structure is the data of an object A ∈ V A\in\mathcal{V} A ∈ V with:
an arrow f A : A X → A Y f_A:A^X\to A^Y f A : A X → A Y in V \mathcal{V} V for every function symbol f : ( X , Y ) f:(X,Y) f : ( X , Y ) in L \mathbb{L} L ;
an M \mathcal{M} M -subobject r A : R A → A X r_A:R_A\to A^X r A : R A → A X for every relation symbol R : X R:X R : X in L \mathbb{L} L .
Definition 2.10 ([37 Definition 4.1] ). Let L \mathbb{L} L be a language. The class of L \mathbb{L} L -terms is defined recursively as follows:
every arrow f : Y → X f:Y\to X f : Y → X of V f p \mathcal{V}_{\mathrm{fp}} V fp is an ( X , Y ) (X,Y) ( X , Y ) -ary term;
every function symbol f : ( X , Y ) f:(X,Y) f : ( X , Y ) of L \mathbb{L} L is an ( X , Y ) (X,Y) ( X , Y ) -ary term;
if t t t is a ( X , Y ) (X,Y) ( X , Y ) -ary term and Z Z Z is in V f p \mathcal{V}_{\mathrm{fp}} V fp , then t Z t^Z t Z is a ( Z ⊗ X , Z ⊗ Y ) (Z\otimes X,Z\otimes Y) ( Z ⊗ X , Z ⊗ Y ) -ary term;
given ( t 1 , … , t n ) (t_1,\ldots,t_n) ( t 1 , … , t n ) , where each t j t_j t j is an ( X j , Y j ) (X_j,Y_j) ( X j , Y j ) -ary term, and an ( ∑ j = 1 n Y j , W ) (\sum_{j=1}^{n}Y_j,W) ( ∑ j = 1 n Y j , W ) -ary term s s s ; then s ( t 1 , … , t n ) s(t_1,\ldots,t_n) s ( t 1 , … , t n ) is a ( ∑ j = 1 n X j , W ) (\sum_{j=1}^{n}X_j,W) ( ∑ j = 1 n X j , W ) -ary term.
Interpretation of terms in an L \mathbb{L} L -structure is defined recursively as one would expect; see [37 Definition 4.1] for details. Next we recall how the class of positive L \mathbb{L} L -formulas is defined.
Definition 2.11 ([36 Definition 3.4] ). Given a language L \mathbb{L} L , the atomic formulas of L \mathbb{L} L are defined as follows:
(1) for any ( X , Y ) (X,Y) ( X , Y ) -ary terms s , t s,t s , t ,
s ( x ) = t ( x ) s(x)=t(x) s ( x ) = t ( x )
is an X X X -ary atomic formula;
(2) for any X X X -ary relation R R R , any Y ∈ V f p Y \in\mathcal{V}_{\mathrm{fp}} Y ∈ V fp , and any ( Z , X ⊗ Y ) (Z,X\otimes Y) ( Z , X ⊗ Y ) -ary term t t t ,
R Y ( t ( z ) ) R^{Y}(t(z)) R Y ( t ( z ))
is a Z Z Z -ary atomic formula;
(3) truth : for any arity X ∈ V f p X \in\mathcal{V}_{\mathrm{fp}} X ∈ V fp we have the X X X -ary atomic formula ⊤ \top ⊤ ;
(4) false : for any arity X ∈ V f p X \in\mathcal{V}_{\mathrm{fp}} X ∈ V fp we have the X X X -ary atomic formula ⊥ \bot ⊥ .
Positive formulas are built recursively from atomic formulas by taking:
(5) conjunctions : if φ 1 \varphi_1 φ 1 and φ 2 \varphi_2 φ 2 are X X X -ary formulas then
φ 1 ∧ φ 2 \varphi_1 \wedge\varphi_2 φ 1 ∧ φ 2
is an X X X -ary formula;
(6) existential quantification : if ψ ( x , y ) \psi(x,y) ψ ( x , y ) is an ( X + Y ) (X+Y) ( X + Y ) -ary formula then
∃ y ψ ( x , y ) \exists y\psi(x,y) ∃ y ψ ( x , y )
is an X X X -ary formula;
(7) disjunctions : if φ 1 \varphi_1 φ 1 and φ 2 \varphi_2 φ 2 are X X X -ary formulas then
φ 1 ∨ φ 2 \varphi_1 \vee\varphi_2 φ 1 ∨ φ 2
is an X X X -ary formula.
The class of regular formulas is defined by only allowing rules (1)-(3), (5), and (6).
Enriched logic has only been developed for positive logic. Interpreting full first-order logic in a category requires substantially more structure, even for intuitionistic semantics. Should an enriched version of full first-order logic be developed in the future then it is likely the techniques in this paper would extend to such a logic. For now, we stick with enriched positive logic.
Definition 2.12 ([36 Definition 3.5] ). For any L-structure A A A and any positive X X X -ary formula φ ( x ) \varphi(x) φ ( x ) we define recursively its interpretation in A A A as an M \mathcal{M} M -subobject φ ( A ) → A X \varphi(A) \rightarrow A^X φ ( A ) → A X .
(1) If φ ( x ) ≡ ( s ( x ) = t ( x ) ) \varphi(x) \equiv(s(x)=t(x)) φ ( x ) ≡ ( s ( x ) = t ( x )) then the interpretation φ ( A ) → A X \varphi(A) \rightarrow A^X φ ( A ) → A X is the ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) -factorisation of the equaliser of s A s_A s A and t A t_A t A :
A s , t → E φ ( A ) eq ( s A , t A ) ↓ ↓ M A X \begin{CD}
A_{s,t} @>{\mathcal{E}}>> \varphi(A) \\
@V{\operatorname{eq}(s_A,t_A)}VV @VV{\mathcal{M}}V \\
@. A^X
\end{CD} A s , t eq ( s A , t A ) ↓ ⏐ E φ ( A ) ↓ ⏐ M A X (2) If φ ( z ) ≡ R Y ( t ( z ) ) \varphi(z) \equiv R^Y(t(z)) φ ( z ) ≡ R Y ( t ( z )) then the interpretation φ ( A ) → A Z \varphi(A) \rightarrow A^Z φ ( A ) → A Z is the pullback
φ ( A ) → A Z ↓ ↓ t A R A Y → r A Y A X ⊗ Y \begin{CD}
\varphi(A) @>>> A^Z \\
@VVV @VV{t_A}V \\
R_A^Y @>{r_A^Y}>> A^{X\otimes Y}
\end{CD} φ ( A ) ↓ ⏐ R A Y r A Y A Z ↓ ⏐ t A A X ⊗ Y (3) If φ ( x ) ≡ ⊤ \varphi(x) \equiv\top φ ( x ) ≡ ⊤ then ⊤ ( A ) : = A X → A X \top(A):=A^X \rightarrow A^X ⊤ ( A ) := A X → A X is the identity.
(4) If φ ( x ) ≡ ⊥ \varphi(x) \equiv\bot φ ( x ) ≡ ⊥ then ⊥ ( A ) → A X \bot(A) \rightarrow A^X ⊥ ( A ) → A X is the ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) -factorisation
0 → E ⊥ ( A ) ↓ M A X \begin{CD}
0 @>{\mathcal{E}}>> \bot(A) \\
@. @VV{\mathcal{M}}V \\
@. A^X
\end{CD} 0 E ⊥ ( A ) ↓ ⏐ M A X (5) If φ ( x ) ≡ φ 1 ( x ) ∧ φ 2 ( x ) \varphi(x) \equiv\varphi_1(x) \wedge\varphi_2(x) φ ( x ) ≡ φ 1 ( x ) ∧ φ 2 ( x ) then φ ( A ) → A X \varphi(A) \rightarrow A^X φ ( A ) → A X is the pullback
φ ( A ) → φ 1 ( A ) ↓ ↓ φ 2 ( A ) → A X \begin{CD}
\varphi(A) @>>> \varphi_1(A) \\
@VVV @VVV \\
\varphi_2(A) @>>> A^X
\end{CD} φ ( A ) ↓ ⏐ φ 2 ( A ) φ 1 ( A ) ↓ ⏐ A X
(6) If φ ( x ) ≡ ∃ y ψ ( x , y ) \varphi(x) \equiv\exists y\psi(x,y) φ ( x ) ≡ ∃ y ψ ( x , y ) then φ ( A ) → A X \varphi(A) \rightarrow A^{X} φ ( A ) → A X is the ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) -factorisation
ψ ( A ) → ε φ ( A ) → M A X ↓ A X + Y → π X A X \begin{CD}
\psi(A) @>{\varepsilon}>> \varphi(A) @>{\mathcal{M}}>> A^{X}\\
@VVV @. @.\\
A^{X+Y} @>{\pi_{X}}>> A^{X}
\end{CD} ψ ( A ) ↓ ⏐ A X + Y ε π X φ ( A ) A X M A X
(7) if φ ( x ) ≡ φ 1 ( x ) ∨ φ 2 ( x ) \varphi(x) \equiv\varphi_{1}(x) \lor\varphi_{2}(x) φ ( x ) ≡ φ 1 ( x ) ∨ φ 2 ( x ) then φ ( A ) → A X \varphi(A) \rightarrow A^{X} φ ( A ) → A X is the ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) -factorisation
φ 1 ( A ) + φ 2 ( A ) → ε φ ( A ) → M A X \begin{CD}
\varphi_{1}(A)+\varphi_{2}(A) @>{\varepsilon}>> \varphi(A) @>{\mathcal{M}}>> A^{X}
\end{CD} φ 1 ( A ) + φ 2 ( A ) ε φ ( A ) M A X
Note that, if M \mathcal{M} M contains the class of the regular monomorphisms (equivalently: ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is proper) then the interpretation of s ( x ) = t ( x ) s(x)=t(x) s ( x ) = t ( x ) in A A A coincides with the equaliser of s A s_{A} s A and t A t_{A} t A . Similarly, if every arrow out of the initial object is in M \mathcal{M} M , then the interpretation of ⊥ \bot ⊥ is the initial object (this is always the case in our examples).
We can talk about satisfaction of formulas and sequents of such.
Definition 2.13. Given X X X -ary formulas φ \varphi φ and ψ \psi ψ , we say that an L \mathcal{L} L -structure A A A satisfies the sequent φ ( x ) ⊢ ψ ( x ) \varphi(x)\vdash\psi(x) φ ( x ) ⊢ ψ ( x ) , and write
A ⊨ ( φ ⊢ ψ ) , A \models(\varphi\vdash\psi), A ⊨ ( φ ⊢ ψ ) ,
if φ ( A ) ≤ ψ ( A ) \varphi(A)\leq\psi(A) φ ( A ) ≤ ψ ( A ) as M \mathcal{M} M -subobjects of A X A^{X} A X .
When in a sequent φ ( x ) ⊢ ψ ( x ) \varphi(x)\vdash\psi(x) φ ( x ) ⊢ ψ ( x ) as above we have φ ≡ ⊤ \varphi\equiv\top φ ≡ ⊤ we simply write A ⊨ ψ A\models\psi A ⊨ ψ , instead of A ⊨ ( ⊤ ⊢ ψ ) A\models(\top\vdash\psi) A ⊨ ( ⊤ ⊢ ψ ) , and this happens if and only if ψ ( A ) ≅ A X \psi(A)\cong A^{X} ψ ( A ) ≅ A X .
Definition 2.14 ([35 Definition 3.4] ). A homomorphism of L \mathcal{L} L -structures h : A → B h:A\to B h : A → B is determined by an arrow h : A → B h:A\to B h : A → B in V \mathcal{V} V making the left square below commute
A X → h X B X f A ↓ ↓ f B A Y → h Y B Y R A → h R R B r A ↓ ↓ r B A X → h X B X \begin{CD}
A^{X} @>{h^{X}}>> B^{X}\\
@V{f_{A}}VV @VV{f_{B}}V\\
A^{Y} @>{h^{Y}}>> B^{Y}
\end{CD}
\qquad
\begin{CD}
R_{A} @>{h_{R}}>> R_{B}\\
@V{r_{A}}VV @VV{r_{B}}V\\
A^{X} @>{h^{X}}>> B^{X}
\end{CD} A X f A ↓ ⏐ A Y h X h Y B X ↓ ⏐ f B B Y R A r A ↓ ⏐ A X h R h X R B ↓ ⏐ r B B X
for any f : ( X , Y ) f:(X,Y) f : ( X , Y ) in L \mathcal{L} L , and such that there exist a (necessarily unique) arrow h R : R A → R B h_{R}:R_{A}\to R_{B} h R : R A → R B completing the commutative diagram above on the right for any relation symbol R : X R:X R : X in L \mathcal{L} L .
The V \mathcal{V} V -category Str ( L ) \operatorname{Str}(\mathcal{L}) Str ( L ) of L \mathcal{L} L -structures is defined in [35 Definition 3.8] and its underlying category Str ( L ) 0 \operatorname{Str}(\mathcal{L})_{0} Str ( L ) 0 has L \mathcal{L} L -structures as objects and homomorphisms of such as arrows.
As shown in [36 Proposition 4.1] , every positive formula φ \varphi φ induces a functor
φ ( − ) : Str ( L ) 0 → V 0 \varphi(-):\operatorname{Str}(\mathcal{L})_{0}\to\mathcal{V}_{0} φ ( − ) : Str ( L ) 0 → V 0
assigning to each A ∈ Str ( L ) 0 A\in\operatorname{Str}(\mathcal{L})_{0} A ∈ Str ( L ) 0 the object φ ( A ) \varphi(A) φ ( A ) and to each homomorphism of structures h : A → B h:A\to B h : A → B the (necessarily unique) arrow φ ( h ) \varphi(h) φ ( h ) making the square below commute
φ ( A ) → φ ( h ) φ ( B ) ↓ ↓ A X → h X B X \begin{CD}
\varphi(A) @>{\varphi(h)}>> \varphi(B)\\
@VVV @VVV\\
A^{X} @>{h^{X}}>> B^{X}
\end{CD} φ ( A ) ↓ ⏐ A X φ ( h ) h X φ ( B ) ↓ ⏐ B X
Definition 2.15 ([36 Definition 3.12] ). Given a set T \mathrm{T} T of sequents of formulas, we denote by Mod ( T ) \operatorname{Mod}(\mathrm{T}) Mod ( T ) the full subcategory of Str ( L ) \operatorname{Str}(\mathcal{L}) Str ( L ) spanned by those L \mathcal{L} L -structures that satisfy the sequents in T \mathrm{T} T . We shall call such T \mathrm{T} T an L \mathcal{L} L -theory and an element M ∈ Mod ( T ) M\in\operatorname{Mod}(\mathrm{T}) M ∈ Mod ( T ) a model of T \mathrm{T} T .
We also have a notion of pointwise satisfaction that will turn out to be useful later.
Definition 2.16. Let A A A be an L \mathcal{L} L -structure, φ \varphi φ be an X X X -ary formula, and a : Y → A X a:Y\to A^{X} a : Y → A X be an arrow in V \mathcal{V} V . We write
A ⊨ φ ( a ) A\models\varphi(a) A ⊨ φ ( a )
to mean that a a a factors through the inclusion φ ( A ) → A X \varphi(A)\rightarrow A^{X} φ ( A ) → A X .
Given a sequent σ ≡ ( φ ⊢ ψ ) \sigma\equiv(\varphi\vdash\psi) σ ≡ ( φ ⊢ ψ ) and a : Y → A X a: Y \to A^{X} a : Y → A X , we write
A ⊨ σ ( a ) A \models\sigma(a) A ⊨ σ ( a )
if A ⊨ φ ( a ) A \models\varphi(a) A ⊨ φ ( a ) implies A ⊨ ψ ( a ) A \models\psi(a) A ⊨ ψ ( a ) .
In [36 ] the pointwise satisfaction above was considered only for the case Y = I Y=I Y = I .
Definition 2.17. Let X \mathcal{X} X be a set of objects of V \mathcal{V} V . Given an L \mathcal{L} L -structure A A A and a sequent σ \sigma σ , we say that A A A X \mathcal{X} X -satisfies σ \sigma σ if A ⊨ σ ( a ) A \models\sigma(a) A ⊨ σ ( a ) for all arrows a : Y → A X a: Y \to A^{X} a : Y → A X in V \mathcal{V} V with domain in X \mathcal{X} X .
Proposition 2.18. Let X \mathcal{X} X be an E \mathcal{E} E -generator of V 0 \mathcal{V}_{0} V 0 , A A A be an L \mathcal{L} L -structure, and σ \sigma σ a sequent. Then A ⊨ σ A \models\sigma A ⊨ σ if and only if A A A X \mathcal{X} X -satisfies σ \sigma σ .
As will be evident from the proof, for the left to right direction we get in fact that A A A then Ob ( V ) \operatorname{Ob}(\mathcal{V}) Ob ( V ) -satisfies σ \sigma σ . So the assumption about X \mathcal{X} X being an E \mathcal{E} E -generator is only used in the other direction.
Proof. Let φ \varphi φ and ψ \psi ψ be X \mathcal{X} X -ary formulas such that σ ≡ ( φ ⊢ ψ ) \sigma\equiv(\varphi\vdash\psi) σ ≡ ( φ ⊢ ψ ) . If A ⊨ σ A \models\sigma A ⊨ σ then any arrow Y → A X Y \to A^{X} Y → A X that factors through φ ( A ) \varphi(A) φ ( A ) also factors through ψ ( A ) \psi(A) ψ ( A ) , as witnessed by composing the factorisation with the arrow φ ( A ) → ψ ( A ) \varphi(A) \to\psi(A) φ ( A ) → ψ ( A ) that witnesses A ⊨ σ A \models\sigma A ⊨ σ .
For the other direction we have by assumption that for any a : Y → φ ( A ) a: Y \to\varphi(A) a : Y → φ ( A ) , with Y ∈ X Y \in\mathcal{X} Y ∈ X , there is f a : Y → ψ ( A ) f_a: Y \to\psi(A) f a : Y → ψ ( A ) such that composing with the arrows φ ( A ) → A X \varphi(A) \rightarrow A^{X} φ ( A ) → A X and ψ ( A ) → A X \psi(A) \rightarrow A^{X} ψ ( A ) → A X yields a commutative square. Taking the coproduct we thus have a commutative square given by the solid arrows in the diagram below.
∐ a : Y → ψ ( A ) , Y ∈ X f a ⟶ ψ ( A ) ⟶ A X ∐ a : Y → φ ( A ) , Y ∈ X Y ⟶ φ ( A ) ⟶ A X \begin{aligned}
\coprod_{a:Y\to\psi(A),\,Y\in\mathcal{X}} f_a &\longrightarrow\psi(A) \longrightarrow A^{X}\\
\coprod_{a:Y\to\varphi(A),\,Y\in\mathcal{X}} Y &\longrightarrow\varphi(A) \longrightarrow A^{X}
\end{aligned} a : Y → ψ ( A ) , Y ∈ X ∐ f a a : Y → φ ( A ) , Y ∈ X ∐ Y ⟶ ψ ( A ) ⟶ A X ⟶ φ ( A ) ⟶ A X
As X \mathcal{X} X is an X \mathcal{X} X -generator, the bottom left arrow is in E \mathcal{E} E . So we get the dashed diagonal filler arrow, making the entire diagram commute. The triangle on the right then witnesses that A ⊨ σ A \models\sigma A ⊨ σ , as required. □ \square □
The following shows how existential quantification behaves with respect to pointwise satisfaction.
Proposition 2.19. Let φ ( x ) \varphi(x) φ ( x ) be an X \mathcal{X} X -ary formula of the form ∃ y ψ ( x , y ) \exists y\psi(x,y) ∃ y ψ ( x , y ) , where ψ ( x , y ) \psi(x,y) ψ ( x , y ) is ( X + Y ) (\mathcal{X}+\mathcal{Y}) ( X + Y ) -ary. Let also A A A be an L \mathcal{L} L -structure and let a : Z → A X a: Z \to A^{X} a : Z → A X be an arrow in V \mathcal{V} V . If there is an arrow b : Z → A Y b: Z \to A^{Y} b : Z → A Y such that A ⊨ ψ ( ( a , b ) ) A \models\psi((a,b)) A ⊨ ψ (( a , b )) , where ( a , b ) : Z → A X × A Y ≅ A X + Y (a,b): Z \to A^{X} \times A^{Y} \cong A^{X+Y} ( a , b ) : Z → A X × A Y ≅ A X + Y is the induced arrow, then A ⊨ φ ( a ) A \models\varphi(a) A ⊨ φ ( a ) .
The converse holds if Z Z Z is E \mathcal{E} E -projective.
Proof. If A ⊨ ψ ( ( a , b ) ) A \models\psi((a,b)) A ⊨ ψ (( a , b )) then the dashed arrow in the diagram below exists, making everything commute.
Z ⇢ ψ ( A ) ⟶ φ ( A ) ↘ ( a , b ) ↓ ↓ A X + Y → π X A X \begin{aligned}
Z &\dashrightarrow\psi(A) \longrightarrow\varphi(A)\\
&\searrow^{(a,b)} \quad\downarrow\qquad\downarrow\\
&\qquad A^{X+Y} \xrightarrow{\pi_X} A^{X}
\end{aligned} Z ⇢ ψ ( A ) ⟶ φ ( A ) ↘ ( a , b ) ↓ ↓ A X + Y π X A X
We thus see that a = π X ( a , b ) a=\pi_X(a,b) a = π X ( a , b ) factors through φ ( A ) \varphi(A) φ ( A ) , and so A ⊨ φ ( a ) A \models\varphi(a) A ⊨ φ ( a ) .
For the converse, suppose that Z Z Z is E \mathcal{E} E -projective and that A ⊨ φ ( a ) A \models\varphi(a) A ⊨ φ ( a ) . Then the dashed arrow in the diagram below exists, such that its composition with φ ( A ) → A X \varphi(A) \rightarrow A^{X} φ ( A ) → A X is a a a .
Z ⇢ ψ A ⟶ φ A ↓ ↓ A X + Y → π X A X \begin{aligned}
Z &\dashrightarrow\psi^{A} \longrightarrow\varphi^{A}\\
&\qquad\downarrow\qquad\downarrow\\
&A^{X+Y} \xrightarrow{\pi_X} A^{X}
\end{aligned} Z ⇢ ψ A ⟶ φ A ↓ ↓ A X + Y π X A X
Since Z Z Z is E \mathcal{E} E -projective we then find the dotted arrow, making the top triangle commute. The composition Z → ψ ( A ) → A X + Y → A Y Z \to\psi(A) \to A^{X+Y} \to A^{Y} Z → ψ ( A ) → A X + Y → A Y is then the desired b b b such that A ⊨ ψ ( ( a , b ) ) A \models\psi((a,b)) A ⊨ ψ (( a , b )) . □ \square □
We conclude this section with a brief comment on substitution in the enriched framework.
Remark 2.20. If φ ( x ) \varphi(x) φ ( x ) is an X X X -ary formula and t t t is a ( W , X ) (W,X) ( W , X ) -ary term, then we can recursively define the W W W -ary substitution formula φ ( t ( w ) ) \varphi(t(w)) φ ( t ( w )) as follows.
If φ ( x ) ≡ ( s 1 ( x ) = s 2 ( x ) ) \varphi(x) \equiv(s_1(x)=s_2(x)) φ ( x ) ≡ ( s 1 ( x ) = s 2 ( x )) then φ ( t ( w ) ) : = ( s 1 ( t ) ( w ) = s 2 ( t ) ( w ) ) \varphi(t(w)) := (s_1(t)(w)=s_2(t)(w)) φ ( t ( w )) := ( s 1 ( t ) ( w ) = s 2 ( t ) ( w )) .
If φ ( x ) ≡ R Y ( s ( x ) ) \varphi(x) \equiv R^Y(s(x)) φ ( x ) ≡ R Y ( s ( x )) then φ ( t ( w ) ) : = R Y ( s ( t ) ( w ) ) \varphi(t(w)) := R^Y(s(t)(w)) φ ( t ( w )) := R Y ( s ( t ) ( w )) .
If φ ( x ) ≡ ⊤ \varphi(x) \equiv\top φ ( x ) ≡ ⊤ then φ ( t ( w ) ) : = ⊤ \varphi(t(w)) := \top φ ( t ( w )) := ⊤ .
If φ ( x ) ≡ ⊥ \varphi(x) \equiv\bot φ ( x ) ≡ ⊥ then φ ( t ( w ) ) : = ⊥ \varphi(t(w)) := \bot φ ( t ( w )) := ⊥ .
If φ ( x ) ≡ φ 1 ( x ) ∧ φ 2 ( x ) \varphi(x) \equiv\varphi_1(x) \land\varphi_2(x) φ ( x ) ≡ φ 1 ( x ) ∧ φ 2 ( x ) then φ ( t ( w ) ) : = φ 1 ( t ( w ) ) ∧ φ 2 ( t ( w ) ) \varphi(t(w)) := \varphi_1(t(w)) \land\varphi_2(t(w)) φ ( t ( w )) := φ 1 ( t ( w )) ∧ φ 2 ( t ( w )) .
If φ ( x ) ≡ ∃ y ψ ( x , y ) \varphi(x) \equiv\exists y\psi(x,y) φ ( x ) ≡ ∃ y ψ ( x , y ) then φ ( t ( w ) ) : = ∃ y ψ ( t ( w ) , y ) \varphi(t(w)) := \exists y\psi(t(w),y) φ ( t ( w )) := ∃ y ψ ( t ( w ) , y ) .
If φ ( x ) ≡ φ 1 ( x ) ∨ φ 2 ( x ) \varphi(x) \equiv\varphi_1(x) \lor\varphi_2(x) φ ( x ) ≡ φ 1 ( x ) ∨ φ 2 ( x ) then φ ( t ( w ) ) : = φ 1 ( t ( w ) ) ∨ φ 2 ( t ( w ) ) \varphi(t(w)) := \varphi_1(t(w)) \lor\varphi_2(t(w)) φ ( t ( w )) := φ 1 ( t ( w )) ∨ φ 2 ( t ( w )) .
Given an A A A , φ \varphi φ , and t t t as above, it is straightforward to see that φ ( t ( A ) ) \varphi(t(A)) φ ( t ( A )) is given by the pullback below
φ ( t ( A ) ) → A W ↓ ↓ t A φ ( A ) → A X \begin{CD}
\varphi(t(A)) @>>> A^W \\
@VVV @VV{t_A}V \\
\varphi(A) @>>> A^X
\end{CD} φ ( t ( A )) ↓ ⏐ φ ( A ) A W ↓ ⏐ t A A X
provided that one of the following holds:
φ \varphi φ is a conjunction of atomic formulas (including ⊥ \bot ⊥ ) and E \mathcal{E} E is contained in the class of epimorphisms or is pullback stable;
φ \varphi φ is regular and E \mathcal{E} E is pullback stable;
φ \varphi φ is positive, E \mathcal{E} E is pullback stable, and V 0 \mathcal{V}_0 V 0 is finitary extensive.
In this context, given any a : Y → A W a:Y \to A^W a : Y → A W , it follows that that A ⊨ φ ( t ( a ) ) A \models\varphi(t(a)) A ⊨ φ ( t ( a )) if and only if A ⊨ φ ( t A ∘ a ) A \models\varphi(t_A \circ a) A ⊨ φ ( t A ∘ a ) .
Reduced products and ultraproducts
To even state a Łos-style theorem, we need to make sense of ultraproducts of structures in the enriched sense. More generally, we will define reduced products of such structures, which are defined with respect to a filter rather than an ultrafilter and interact well with the regular fragment of logic.
Definition 3.1. Let I \mathcal{I} I be a set. A filter on I \mathcal{I} I is a nonempty family F ⊆ P ( I ) \mathcal{F} \subseteq\mathcal{P}(\mathcal{I}) F ⊆ P ( I ) of subsets of I \mathcal{I} I such that:
∅ ∉ F \varnothing\notin\mathcal{F} ∅ ∈ / F ,
if J ∈ F J \in\mathcal{F} J ∈ F and J ⊆ J ′ J \subseteq J' J ⊆ J ′ then J ′ ∈ F J' \in\mathcal{F} J ′ ∈ F ,
if J , J ′ ∈ F J,J' \in\mathcal{F} J , J ′ ∈ F then J ∩ J ′ ∈ F J \cap J' \in\mathcal{F} J ∩ J ′ ∈ F .
We call a filter U \mathcal{U} U on I \mathcal{I} I an ultrafilter on I \mathcal{I} I if furthermore for all J ⊆ I J \subseteq\mathcal{I} J ⊆ I either J ∈ U J \in\mathcal{U} J ∈ U or I ∖ J ∈ U \mathcal{I} \setminus J \in\mathcal{U} I ∖ J ∈ U .
Ultrafilters can equivalently be characterised as maximal filters. That is, those filters U \mathcal{U} U such that if F ⊇ U \mathcal{F} \supseteq\mathcal{U} F ⊇ U is a filter then F = U \mathcal{F}=\mathcal{U} F = U .
Definition 3.2. Let C \mathcal{C} C be a complete and cocomplete category and let { A i } i ∈ I \{A_i\}_{i\in\mathcal{I}} { A i } i ∈ I be a family of objects in C \mathcal{C} C . For any filter F \mathcal{F} F on I \mathcal{I} I we define the reduced product to be the following directed colimit:
∏ i ∈ I A i / F : = colim J ∈ F ∏ i ∈ J A i \prod_{i\in\mathcal{I}} A_i/\mathcal{F} := \mathop{\operatorname{colim}}_{J\in\mathcal{F}} \prod_{i\in J} A_i i ∈ I ∏ A i / F := colim J ∈ F i ∈ J ∏ A i
where F \mathcal{F} F is ordered reversely by inclusion. The arrows in the diagram are the obvious projections ∏ i ∈ J A i → ∏ i ∈ J ′ A i \prod_{i\in J} A_i \to\prod_{i\in J'} A_i ∏ i ∈ J A i → ∏ i ∈ J ′ A i for J ⊇ J ′ J \supseteq J' J ⊇ J ′ .
If F \mathcal{F} F is an ultrafilter then we call ∏ i ∈ I A i / F \prod_{i\in\mathcal{I}} A_i/\mathcal{F} ∏ i ∈ I A i / F the ultraproduct instead.
Since Str ( L ) 0 \operatorname{Str}(\mathcal{L})_0 Str ( L ) 0 is complete and cocomplete, we can always form reduced products of L \mathcal{L} L -structures. However, to obtain a nice explicit description we will need our base of enrichment V \mathcal{V} V to satisfy a few properties.
Definition 3.3. Our fixed base of enrichment V \mathcal{V} V with factorisation system ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is called reduced product ready if the following hold.
Finite limits commute in V \mathcal{V} V with directed colimits.
(2) Finite powers commute in V \mathcal{V} V with directed colimits.
(3) The class M \mathcal{M} M is closed in V 2 \mathcal{V}^{2} V 2 under directed colimits.
The following equivalent condition is sometimes easier to check than Theorem 3.3(2).
Fact 3.4 ([18 (5.2)] ). If V 0 \mathcal{V}_0 V 0 is locally finitely presentable then finite powers commute in V 0 \mathcal{V}_0 V 0 with directed colimits if and only if the finitely presentable objects in V 0 \mathcal{V}_0 V 0 are closed under the monoidal product.
If V \mathcal{V} V is reduced product ready then the reduced product of arrows in M \mathcal{M} M is again in M \mathcal{M} M . More precisely, given a family { f i : A i → B i } i ∈ I \{f_i:A_i\to B_i\}_{i\in I} { f i : A i → B i } i ∈ I of arrows in M \mathcal{M} M and a filter F \mathcal{F} F on I I I , the induced arrow
∏ i ∈ I f i / F : ∏ i ∈ I A i / F ⟶ ∏ i ∈ I B i / F \prod_{i\in I}f_i/\mathcal{F}:\prod_{i\in I}A_i/\mathcal{F}\longrightarrow\prod_{i\in I}B_i/\mathcal{F} i ∈ I ∏ f i / F : i ∈ I ∏ A i / F ⟶ i ∈ I ∏ B i / F
is again in M \mathcal{M} M . This follows because such a reduced product is a directed colimit of products, and M \mathcal{M} M is closed under limits (being the right part of a factorisation system) and under directed colimits (by assumption, Theorem 3.3(3)). Similarly, we have for any finitely presentable X X X that
( ∏ i ∈ I A i / F ) X ≅ ∏ i ∈ I A i X / F , \left(\prod_{i\in I}A_i/\mathcal{F}\right)^X\cong\prod_{i\in I}A_i^X/\mathcal{F}, ( i ∈ I ∏ A i / F ) X ≅ i ∈ I ∏ A i X / F ,
because powers always commute with limits and finite powers commute with directed colimits (by assumption, Theorem 3.3(2)). Finally, finite limits commute with reduced products in a similar manner. We will often use these facts implicitly from now on.
Definition 3.5. Assume that V \mathcal{V} V is reduced product ready. Let L \mathbb{L} L be a language on V \mathcal{V} V , let { A i } i ∈ I \{A_i\}_{i\in I} { A i } i ∈ I be a family of L \mathbb{L} L -structures, and let F \mathcal{F} F be a filter on I I I . We define the reduced product
A : = ∏ i ∈ I A i / F A:=\prod_{i\in I}A_i/\mathcal{F} A := i ∈ I ∏ A i / F to be the following L \mathbb{L} L -structure. Its underlying object is ∏ i ∈ I A i / F \prod_{i\in I}A_i/\mathcal{F} ∏ i ∈ I A i / F , as in Theorem 3.2. For each ( X , Y ) (X,Y) ( X , Y ) -ary function symbol f f f in L \mathbb{L} L we let its interpretation f A : A X → A Y f_A:A^X\to A^Y f A : A X → A Y be the composition
A X ≅ ∏ i ∈ I A i X / F → ∏ i ∈ I f A i / F ∏ i ∈ I A i Y / F ≅ A Y . A^X\cong\prod_{i\in I}A_i^X/\mathcal{F}\xrightarrow{\prod_{i\in I}f_{A_i}/\mathcal{F}}\prod_{i\in I}A_i^Y/\mathcal{F}\cong A^Y. A X ≅ i ∈ I ∏ A i X / F ∏ i ∈ I f A i / F i ∈ I ∏ A i Y / F ≅ A Y . For each X X X -ary relation symbol R R R in L \mathbb{L} L we let its interpretation R A R_A R A be the M \mathcal{M} M -subobject represented by
∏ i ∈ I R A i / F ⟶ ∏ i ∈ I A i X / F ≅ A X , \prod_{i\in I}R_{A_i}/\mathcal{F}\longrightarrow\prod_{i\in I}A_i^X/\mathcal{F}\cong A^X, i ∈ I ∏ R A i / F ⟶ i ∈ I ∏ A i X / F ≅ A X , which formally is the reduced product of representatives of the family of M \mathcal{M} M -subobjects { R A i } i ∈ I \{R_{A_i}\}_{i\in I} { R A i } i ∈ I .
Proposition 3.6 (interpretations commute with reduced products). Assume that V \mathcal{V} V is reduced product ready. Let L \mathbb{L} L be a language and let A : = ∏ i ∈ I A i / F A:=\prod_{i\in I}A_i/\mathcal{F} A := ∏ i ∈ I A i / F be a reduced product of L \mathbb{L} L -structures. Then:
(i) for any ( X , Y ) (X,Y) ( X , Y ) -ary term t t t in L \mathbb{L} L its interpretation t A t_A t A is given by the composition
A X ≅ ∏ i ∈ I A i X / F → ∏ i ∈ I t A i / F ∏ i ∈ I A i Y / F ≅ A Y , A^X\cong\prod_{i\in I}A_i^X/\mathcal{F}\xrightarrow{\prod_{i\in I}t_{A_i}/\mathcal{F}}\prod_{i\in I}A_i^Y/\mathcal{F}\cong A^Y, A X ≅ i ∈ I ∏ A i X / F ∏ i ∈ I t A i / F i ∈ I ∏ A i Y / F ≅ A Y , (ii) for any X X X -ary relation symbol R R R and any ( Z , X ⊗ Y ) (Z,X\otimes Y) ( Z , X ⊗ Y ) -ary term t t t in L \mathbb{L} L the interpretation of R Y ( t ) R^Y(t) R Y ( t ) in A A A is given by the composition
∏ i ∈ I R Y ( t ( A i ) ) / F ⟶ ∏ i ∈ I A i Z / F ≅ A Z . \prod_{i\in I}R^Y(t(A_i))/\mathcal{F}\longrightarrow\prod_{i\in I}A_i^Z/\mathcal{F}\cong A^Z. i ∈ I ∏ R Y ( t ( A i )) / F ⟶ i ∈ I ∏ A i Z / F ≅ A Z .
Proof. Item (i) is proved by induction on the complexity of the term t t t . The case where t t t is an arrow f : Y → X f:Y\to X f : Y → X in V f p \mathcal{V}_{\mathrm{fp}} V fp follows because finite powers commute with reduced products and ( − ) f : ( − ) X → ( − ) Y (-)^f:(-)^X\to(-)^Y ( − ) f : ( − ) X → ( − ) Y is a natural transformation. The case where t t t is a function symbol of arity ( X , Y ) (X,Y) ( X , Y ) in L \mathbb{L} L follows by definition of the L \mathbb{L} L -structure A A A . For the case where t t t is of the form s Z s^{Z} s Z we compose isomorphisms as below.
A X ⊗ Z → s A Z A Y ⊗ Z ≅ ↓ ↓ ≅ ( A X ) Z → ( s A ) Z ( A Y ) Z ≅ ↓ ↓ ≅ ( ∏ i ∈ I A i X / F ) Z ⟶ ( ∏ i ∈ I s A i / F ) Z ⟶ ( ∏ i ∈ I A i Y / F ) Z ≅ ↓ ↓ ≅ ∏ i ∈ I ( A i X ) Z / F ⟶ ∏ i ∈ I ( s A i ) Z / F ⟶ ∏ i ∈ I ( A i Y ) Z / F ≅ ↓ ↓ ≅ ∏ i ∈ I A i X ⊗ Z / F → s A i Z ∏ i ∈ I A i Y ⊗ Z / F \begin{aligned}
A^{X\otimes Z} &\xrightarrow{\ s^{Z}_{A}\ } A^{Y\otimes Z}\\
\cong\ \downarrow&& \downarrow\ \cong\\
(A^{X})^{Z} &\xrightarrow{\ (s_{A})^{Z}\ } (A^{Y})^{Z}\\
\cong\ \downarrow&& \downarrow\ \cong\\
\left(\prod_{i\in I} A_{i}^{X}/\mathcal{F}\right)^{Z} &\longrightarrow\left(\prod_{i\in I} sA_{i}/\mathcal{F}\right)^{Z} \longrightarrow\left(\prod_{i\in I} A_{i}^{Y}/\mathcal{F}\right)^{Z}\\
\cong\ \downarrow&& \downarrow\ \cong\\
\prod_{i\in I}(A_{i}^{X})^{Z}/\mathcal{F} &\longrightarrow\prod_{i\in I}(sA_{i})^{Z}/\mathcal{F} \longrightarrow\prod_{i\in I}(A_{i}^{Y})^{Z}/\mathcal{F}\\
\cong\ \downarrow&& \downarrow\ \cong\\
\prod_{i\in I}A_{i}^{X\otimes Z}/\mathcal{F} &\xrightarrow{\ s^{Z}_{A_{i}}\ } \prod_{i\in I}A_{i}^{Y\otimes Z}/\mathcal{F}
\end{aligned} A X ⊗ Z ≅ ↓ ( A X ) Z ≅ ↓ ( i ∈ I ∏ A i X / F ) Z ≅ ↓ i ∈ I ∏ ( A i X ) Z / F ≅ ↓ i ∈ I ∏ A i X ⊗ Z / F s A Z A Y ⊗ Z ( s A ) Z ( A Y ) Z ⟶ ( i ∈ I ∏ s A i / F ) Z ⟶ ( i ∈ I ∏ A i Y / F ) Z ⟶ i ∈ I ∏ ( s A i ) Z / F ⟶ i ∈ I ∏ ( A i Y ) Z / F s A i Z i ∈ I ∏ A i Y ⊗ Z / F ↓ ≅ ↓ ≅ ↓ ≅ ↓ ≅
definition of s A Z s^{Z}_{A} s A Z
induction hypothesis
finite powers commute with directed colimits
definition of s A i Z s^{Z}_{A_{i}} s A i Z
The outer rectangle is now the required isomorphism, where the vertical isomorphisms compose to the canonical isomorphism by commutativity of the square
A X ⊗ Z → ≅ ( A X ) Z ≅ ↑ ↑ ≅ ∏ i ∈ I A i X ⊗ Z / F → ≅ ∏ i ∈ I ( A i X ) Z / F \begin{aligned}
A^{X\otimes Z} &\xrightarrow{\ \cong\ } (A^{X})^{Z}\\
\cong\ \uparrow&& \uparrow\ \cong\\
\prod_{i\in I}A_{i}^{X\otimes Z}/\mathcal{F} &\xrightarrow{\ \cong\ } \prod_{i\in I}(A_{i}^{X})^{Z}/\mathcal{F}
\end{aligned} A X ⊗ Z ≅ ↑ i ∈ I ∏ A i X ⊗ Z / F ≅ ( A X ) Z ≅ i ∈ I ∏ ( A i X ) Z / F ↑ ≅
which in turn follows from naturality of the isomorphism ( − ) X ⊗ Z ≅ ( ( − ) X ) Z (-)^{X\otimes Z}\cong((-)^{X})^{Z} ( − ) X ⊗ Z ≅ (( − ) X ) Z (and similar for Y Y Y ).
Finally, we consider the case where t t t is a composition of terms. More precisely, there is a finite family of terms { s j : ( X j , Y j ) } j ∈ J \{s_{j}:(X_{j},Y_{j})\}_{j\in J} { s j : ( X j , Y j ) } j ∈ J and a ( ∑ j ∈ J Y j , Z ) (\sum_{j\in J}Y_{j},Z) ( ∑ j ∈ J Y j , Z ) -ary term r r r such that t t t is r ( ( s j ) j ∈ J ) r((s_{j})_{j\in J}) r (( s j ) j ∈ J ) . We again construct a commutative diagram such that the outer rectangle is the required isomorphism. To save some space, we simplify notation by setting X : = ∑ j ∈ J X j X:=\sum_{j\in J}X_{j} X := ∑ j ∈ J X j and Y : = ∑ j ∈ J Y j Y:=\sum_{j\in J}Y_{j} Y := ∑ j ∈ J Y j .
A X → r ( ( s j ) j ∈ J ) A A Z ≅ ↓ ∥ ∏ j ∈ J A X j → ( s j , A ) j ∈ J ∏ j ∈ J A Y j → ≅ A Y → r A A Z ≅ ↓ ≅ ↓ ≅ ↓ ∥ ∏ j ∈ J ( ∏ i ∈ I A i X j / F ) → ( ∏ i ∈ I s j , A i / F ) j ∈ J ∏ j ∈ J ( ∏ i ∈ I A i Y j / F ) ∏ i ∈ I A i Y / F → ∏ i ∈ I r A i / F ∏ i ∈ I A i Z / F ≅ ↓ ≅ ↓ ∥ ∥ ∏ i ∈ I ( ∏ j ∈ J A i X j ) / F ⟶ ∏ i ∈ I ( ∏ j ∈ J A i Y j ) / F → ≅ ∏ i ∈ I A i Y / F → ∏ i ∈ I r A i / F ∏ i ∈ I A i Z / F ≅ ↓ ∥ ∥ ∏ i ∈ I A i X / F → ∏ i ∈ I r ( ( s j ) j ∈ J ) A i / F ∏ i ∈ I A i Z / F \begin{aligned}
A^{X} &\xrightarrow{\ r((s_{j})_{j\in J})_{A}\ } A^{Z}\\
\cong\ \downarrow&& \Vert\\
\prod_{j\in J}A^{X_{j}} &\xrightarrow{\ (s_{j,A})_{j\in J}\ } \prod_{j\in J}A^{Y_{j}}\xrightarrow{\ \cong\ }A^{Y}\xrightarrow{\ r_{A}\ }A^{Z}\\
\cong\ \downarrow&& \cong\ \downarrow\quad\cong\ \downarrow\quad\Vert\\
\prod_{j\in J}\left(\prod_{i\in I}A_{i}^{X_{j}}/\mathcal{F}\right) &\xrightarrow{\ (\prod_{i\in I}s_{j,A_{i}}/\mathcal{F})_{j\in J}\ } \prod_{j\in J}\left(\prod_{i\in I}A_{i}^{Y_{j}}/\mathcal{F}\right) &\prod_{i\in I}A_{i}^{Y}/\mathcal{F}\xrightarrow{\ \prod_{i\in I}r_{A_{i}}/\mathcal{F}\ }\prod_{i\in I}A_{i}^{Z}/\mathcal{F}\\
\cong\ \downarrow&& \cong\ \downarrow\quad\Vert\quad\Vert\\
\prod_{i\in I}\left(\prod_{j\in J}A_{i}^{X_{j}}\right)/\mathcal{F} &\longrightarrow\prod_{i\in I}\left(\prod_{j\in J}A_{i}^{Y_{j}}\right)/\mathcal{F}\xrightarrow{\ \cong\ }\prod_{i\in I}A_{i}^{Y}/\mathcal{F}\xrightarrow{\ \prod_{i\in I}r_{A_{i}}/\mathcal{F}\ }\prod_{i\in I}A_{i}^{Z}/\mathcal{F}\\
\cong\ \downarrow&& \Vert\quad\Vert\\
\prod_{i\in I}A_{i}^{X}/\mathcal{F} &\xrightarrow{\ \prod_{i\in I}r((s_{j})_{j\in J})_{A_{i}}/\mathcal{F}\ } \prod_{i\in I}A_{i}^{Z}/\mathcal{F}
\end{aligned} A X ≅ ↓ j ∈ J ∏ A X j ≅ ↓ j ∈ J ∏ ( i ∈ I ∏ A i X j / F ) ≅ ↓ i ∈ I ∏ j ∈ J ∏ A i X j / F ≅ ↓ i ∈ I ∏ A i X / F r (( s j ) j ∈ J ) A A Z ( s j , A ) j ∈ J j ∈ J ∏ A Y j ≅ A Y r A A Z ( ∏ i ∈ I s j , A i / F ) j ∈ J j ∈ J ∏ ( i ∈ I ∏ A i Y j / F ) ⟶ i ∈ I ∏ j ∈ J ∏ A i Y j / F ≅ i ∈ I ∏ A i Y / F ∏ i ∈ I r A i / F i ∈ I ∏ A i Z / F ∏ i ∈ I r (( s j ) j ∈ J ) A i / F i ∈ I ∏ A i Z / F ∥ ≅ ↓ ≅ ↓ ∥ i ∈ I ∏ A i Y / F ∏ i ∈ I r A i / F i ∈ I ∏ A i Z / F ≅ ↓ ∥ ∥ ∥ ∥
definition of r ( ( s j ) j ∈ J ) A r((s_{j})_{j\in J})_{A} r (( s j ) j ∈ J ) A
induction hypothesis
induction hypothesis
finite limits commute with reduced products
definition of ∏ i ∈ I r ( ( s j ) j ∈ J ) A i / F \prod_{i\in I}r((s_{j})_{j\in J})_{A_{i}}/\mathcal{F} ∏ i ∈ I r (( s j ) j ∈ J ) A i / F
The commutativity of the unlabelled rectangle in the middle column follows by writing out the definitions of the isomorphisms involved.
For item (ii) we consider the commutative cube below.
∏ i ∈ I R Y ( t ( A i ) ) / F → ∏ i ∈ I A i Z / F ↑ ↑ R Y ( t ( A ) ) → A Z ↓ ↓ ∏ i ∈ I ( R A i ) Y / F → ∏ i ∈ I A i X ⊗ Y ↑ ↑ ( R A ) Y → A X ⊗ Y \begin{CD}
\prod_{i\in I} R^{Y}(t(A_i))/\mathcal{F} @>>> \prod_{i\in I} A_i^{Z}/\mathcal{F}\\
@AAA @AAA\\
R^{Y}(t(A)) @>>> A^{Z}\\
@VVV @VVV\\
\prod_{i\in I}(R_{A_i})^{Y}/\mathcal{F} @>>> \prod_{i\in I} A_i^{X\otimes Y}\\
@AAA @AAA\\
(R_A)^{Y} @>>> A^{X\otimes Y}
\end{CD} i ∈ I ∏ R Y ( t ( A i )) / F ⏐ ↑ R Y ( t ( A )) ↓ ⏐ i ∈ I ∏ ( R A i ) Y / F ⏐ ↑ ( R A ) Y i ∈ I ∏ A i Z / F ⏐ ↑ A Z ↓ ⏐ i ∈ I ∏ A i X ⊗ Y ⏐ ↑ A X ⊗ Y
The bottom left arrow is an isomorphism by definition of A A A as an L \mathbb{L} L -structure and the fact that Y Y Y is finitely presentable, making the bottom face commute. The right face commutes by item (i). The front face is a pullback by definition, and the back face is also a pullback since finite limits commute with reduced products. We thus find the dashed isomorphism, as required.
Łos-style theorems
In this section we prove Łos-style theorems for two fragments of enriched logic: one for enriched regular logic and reduced products, and one for enriched positive logic and ultraproducts. To make sense of the reduced products (and ultraproducts), our base of enrichment needs to be at least reduced product ready. However, we need a little more.
Definition 4.1. Our fixed base of enrichment V \mathcal{V} V with factorisation system ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is called reduced product stable if it is reduced product ready and the class E \mathcal{E} E is closed in V 2 \mathcal{V}^{2} V 2 under small products.
Definition 4.2. A complete and cocomplete category C \mathcal{C} C with factorisation system ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is said to have the ultraproduct covering property if for any set I I I , any ultrafilter U \mathcal{U} U on I I I , and families ( A i ) i ∈ I (A_i)_{i\in I} ( A i ) i ∈ I and ( B i ) i ∈ I (B_i)_{i\in I} ( B i ) i ∈ I of objects in V \mathcal{V} V the comparison arrows
0 ⟶ ∏ i ∈ I 0 / U and ∏ i ∈ I A i / U + ∏ i ∈ I B i / U ⟶ ∏ i ∈ I ( A i + B i ) / U 0 \longrightarrow\prod_{i\in I} 0/\mathcal{U}
\qquad\text{and}\qquad
\prod_{i\in I} A_i/\mathcal{U}+\prod_{i\in I} B_i/\mathcal{U}\longrightarrow\prod_{i\in I}(A_i+B_i)/\mathcal{U} 0 ⟶ i ∈ I ∏ 0/ U and i ∈ I ∏ A i / U + i ∈ I ∏ B i / U ⟶ i ∈ I ∏ ( A i + B i ) / U are in E \mathcal{E} E .
In Section 9 we will see many examples of enrichment bases that are reduced product stable and satisfy the ultraproduct covering property, but we also give an example of an enrichment base that is reduced product stable but fails the ultraproduct covering property (Theorem 9.9).
The reason for requiring U \mathcal{U} U in the above definition to be an ultrafilter is that this property fails for general filters, see the example below. Furthermore, in Section 8 we give natural assumptions that imply the ultraproduct covering property, and it is evident from the proofs there how U \mathcal{U} U being an ultrafilter is used.
Example 4.3. Let V = S e t \mathcal{V}=\mathrm{Set} V = Set with the usual factorisation system. Let A i = B i = 1 A_i=B_i=1 A i = B i = 1 for all i ∈ ω i\in\omega i ∈ ω and let F \mathcal{F} F be the filter of cofinite subsets of ω \omega ω . Then ∏ i ∈ ω A i / F = ∏ i ∈ ω B i / F = 1 \prod_{i\in\omega}A_i/\mathcal{F}=\prod_{i\in\omega}B_i/\mathcal{F}=1 ∏ i ∈ ω A i / F = ∏ i ∈ ω B i / F = 1 . The elements of ∏ i ∈ ω ( A i + B i ) / F \prod_{i\in\omega}(A_i+B_i)/\mathcal{F} ∏ i ∈ ω ( A i + B i ) / F are represented by ω \omega ω -long strings of 1s and 0s, i.e., elements of 2 ω 2^\omega 2 ω . Two such strings ( x i ) i ∈ ω (x_i)_{i\in\omega} ( x i ) i ∈ ω and ( y i ) i ∈ ω (y_i)_{i\in\omega} ( y i ) i ∈ ω represent the same element if and only if they agree on cofinitely many positions. So ∏ i ∈ ω ( A i + B i ) / F \prod_{i\in\omega}(A_i+B_i)/\mathcal{F} ∏ i ∈ ω ( A i + B i ) / F has cardinality continuum, and can never admit a surjection from ∏ i ∈ ω A i / F + ∏ i ∈ ω B i / F = 2 \prod_{i\in\omega}A_i/\mathcal{F}+\prod_{i\in\omega}B_i/\mathcal{F}=2 ∏ i ∈ ω A i / F + ∏ i ∈ ω B i / F = 2 .
Remark 4.4. Since the initial object is stable under colimits and so are the arrows in E \mathcal{E} E , the arrow 0 ⟶ ∏ i ∈ I 0 / U 0\longrightarrow\prod_{i\in I}0/\mathcal{U} 0 ⟶ ∏ i ∈ I 0/ U lies in E \mathcal{E} E whenever the arrow 0 ⟶ ∏ i ∈ J 0 0\longrightarrow\prod_{i\in J}0 0 ⟶ ∏ i ∈ J 0 lies in E \mathcal{E} E for any nonempty set J J J . Note that this arrow is always a split monomorphism (since we can postcompose it with any product projection to obtain the identity on 0 0 0 ); thus, if it is in E \mathcal{E} E and every arrow of E \mathcal{E} E is an epimorphism, then it is automatically an isomorphism.
It follows that the first condition of the ultraproduct covering property holds whenever the initial object is stable under small products. This is the case for instance when 0 0 0 is actually a zero object (that is, coincides with the terminal object) or when it is strictly initial (that is, every arrow into 0 0 0 is an isomorphism).
Theorem 1.1 (Łos-style theorem 1), repeated. Assume that V \mathcal{V} V is reduced product stable. Let L L L be a language on V \mathcal{V} V and let φ \varphi φ be an L L L -formula. Let A : = ∏ i ∈ I A i / F A := \prod_{i\in I} A_i/F A := ∏ i ∈ I A i / F be a reduced product of L L L -structures. Then
φ ( A ) ≅ ∏ i ∈ I φ ( A i ) / F \varphi(A) \cong\prod_{i\in I}\varphi(A_i)/F φ ( A ) ≅ i ∈ I ∏ φ ( A i ) / F provided that:
(i) φ \varphi φ is regular, or;
(ii) φ \varphi φ is positive, F F F is an ultrafilter, and V \mathcal{V} V has the ultraproduct covering property.
Proof. For a finitely presentable X X X in V \mathcal{V} V , write
ρ X : A X → ≅ ∏ i ∈ I A i X / F \rho^X:A^X \xrightarrow{\cong} \prod_{i\in I}A_i^X/F ρ X : A X ≅ i ∈ I ∏ A i X / F
for the canonical isomorphism. We will construct an isomorphism ρ φ \rho^\varphi ρ φ , by induction on the complexity of φ \varphi φ , such that the square below commutes.
φ ( A ) → A X ρ φ ↓ ↓ ρ X ∏ i ∈ I φ ( A i ) / F → ∏ i ∈ I A i X / F \begin{CD}
\varphi(A) @>>> A^X \\
@V{\rho^\varphi}VV @VV{\rho^X}V \\
\prod_{i\in I}\varphi(A_i)/F @>>> \prod_{i\in I}A_i^X/F
\end{CD} φ ( A ) ρ φ ↓ ⏐ i ∈ I ∏ φ ( A i ) / F A X ↓ ⏐ ρ X i ∈ I ∏ A i X / F
Part of the base case, namely when φ ≡ R Y ( t ) \varphi\equiv R^Y(t) φ ≡ R Y ( t ) for an X X X -ary relation symbol R R R and ( Z , X ⊗ Y ) (Z,X\otimes Y) ( Z , X ⊗ Y ) -ary term t t t , is already given by Theorem 3.6(ii).
Then there are ⊤ \top ⊤ and ⊥ \bot ⊥ . The former is trivial, and the latter we will treat later in the proof, as it is only relevant for (ii).
The final part of the base case is when φ ≡ ( s = t ) \varphi\equiv(s=t) φ ≡ ( s = t ) for some ( X , Y ) (X,Y) ( X , Y ) -ary terms s s s and t t t . Then, for any i ∈ I i\in I i ∈ I , the interpretation φ ( A i ) \varphi(A_i) φ ( A i ) is defined as the ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) -factorisation
A i s , t ⟶ φ ( A i ) ⟶ A i X , A_i^{s,t} \longrightarrow\varphi(A_i) \longrightarrow A_i^X, A i s , t ⟶ φ ( A i ) ⟶ A i X ,
where A i s , t A_i^{s,t} A i s , t is the equaliser of ( s A i , t A i ) (s_{A_i},t_{A_i}) ( s A i , t A i ) . By Theorem 3.6(i) we have that s A ≅ ∏ i ∈ I s A i / F s_A\cong\prod_{i\in I}s_{A_i}/F s A ≅ ∏ i ∈ I s A i / F and t A ≅ ∏ i ∈ I t A i / F t_A\cong\prod_{i\in I}t_{A_i}/F t A ≅ ∏ i ∈ I t A i / F . So, since ∏ i ∈ I A i s , t / F \prod_{i\in I}A_i^{s,t}/F ∏ i ∈ I A i s , t / F is the equaliser of ∏ i ∈ I s A i / F \prod_{i\in I}s_{A_i}/F ∏ i ∈ I s A i / F and ∏ i ∈ I t A i / F \prod_{i\in I}t_{A_i}/F ∏ i ∈ I t A i / F (as finite limits commute with reduced products), we find an isomorphism ρ s , t : A s , t → ∏ i ∈ I A i s , t / F \rho^{s,t}:A^{s,t}\to\prod_{i\in I}A_i^{s,t}/F ρ s , t : A s , t → ∏ i ∈ I A i s , t / F . Taking the reduced product of the ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) -factorisations componentwise we thus obtain the solid part of the following diagram
A s , t → q φ ( A ) → m A X ρ s , t ↓ ≅ ρ φ ↓ ρ X ↓ ≅ ∏ i ∈ I A i s , t / F → q ‾ ∏ i ∈ I φ ( A i ) / F → m ‾ ∏ i ∈ I A i X / F \begin{CD}
A^{s,t} @>{q}>> \varphi(A) @>{m}>> A^X \\
@V{\rho^{s,t}}V{\cong}V @V{\rho^\varphi}VV @V{\rho^X}V{\cong}V \\
\prod_{i\in I}A_i^{s,t}/F @>{\overline q}>> \prod_{i\in I}\varphi(A_i)/F @>{\overline m}>> \prod_{i\in I}A_i^X/F
\end{CD} A s , t ρ s , t ↓ ⏐ ≅ i ∈ I ∏ A i s , t / F q q φ ( A ) ρ φ ↓ ⏐ i ∈ I ∏ φ ( A i ) / F m m A X ρ X ↓ ⏐ ≅ i ∈ I ∏ A i X / F
Since M \mathcal{M} M is closed under reduced products the arrow m ‾ \overline m m is still in M \mathcal{M} M . By orthogonality of the factorisation system, there exists a unique ρ φ \rho^\varphi ρ φ as above making the squares commute. Since V \mathcal{V} V is reduced product stable, the reduced product of arrows in E \mathcal{E} E is again in E \mathcal{E} E , because E \mathcal{E} E is closed under colimits (being the left part of a factorisation system) and small products (by assumption). So q ‾ \overline q q is in E \mathcal{E} E , and ρ φ \rho^\varphi ρ φ is an isomorphism by the uniqueness (up to isomorphism) of the ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) -factorisations.
For the case where φ ≡ φ 1 ∧ φ 2 \varphi\equiv\varphi_1\wedge\varphi_2 φ ≡ φ 1 ∧ φ 2 we consider the following commutative cube.
φ ( A ) → ρ φ 2 ∏ i ∈ I φ 2 ( A i ) / F ↓ ↓ φ 2 ( A ) → ∏ i ∈ I A i X / F ↑ ↑ φ 1 ( A ) → A X \begin{CD}
\varphi(A) @>{\rho^{\varphi_2}}>> \prod_{i\in I}\varphi_2(A_i)/F \\
@VVV @VVV \\
\varphi_2(A) @>>> \prod_{i\in I}A_i^X/F \\
@AAA @AAA \\
\varphi_1(A) @>>> A^X
\end{CD} φ ( A ) ↓ ⏐ φ 2 ( A ) ⏐ ↑ φ 1 ( A ) ρ φ 2 i ∈ I ∏ φ 2 ( A i ) / F ↓ ⏐ i ∈ I ∏ A i X / F ⏐ ↑ A X
The existence of ρ φ 1 \rho^{\varphi^1} ρ φ 1 and ρ φ 2 \rho^{\varphi^2} ρ φ 2 , as well as the commutativity of the bottom and right faces, follows from the induction hypothesis. The front face is a pullback by definition. The back face is, again by definition, a reduced product of pullbacks. So since finite limits commute with reduced products, the back face is a pullback and we find the required isomorphism ρ φ \rho^\varphi ρ φ .
The final case that needs to be checked for item (i) is where φ ≡ ∃ y ψ ( x , y ) \varphi\equiv\exists y\psi(x,y) φ ≡ ∃ y ψ ( x , y ) . We consider the diagram below whose horizontal arrows are induced by those defining φ ( A i ) \varphi(A_i) φ ( A i ) and φ ( A ) \varphi(A) φ ( A ) as ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) -factorisations.
ψ ( A ) ⟶ φ ( A ) ⟶ A X ↓ ρ ψ ≅ ↓ ρ φ ↓ ρ X ≅ ∏ i ∈ I ψ ( A i ) / F → r ∏ i ∈ I φ ( A i ) / F → n ∏ i ∈ I A i X / F \begin{array}{ccccc}
\psi(A) & \longrightarrow& \varphi(A) & \longrightarrow& A^X \\
\downarrow{\scriptstyle\rho^\psi}_{\cong} & & \downarrow{\scriptstyle\rho^\varphi} & & \downarrow{\scriptstyle\rho^X}_{\cong} \\
\prod_{i\in I}\psi(A_i)/\mathcal{F} & \xrightarrow{r} & \prod_{i\in I}\varphi(A_i)/\mathcal{F} & \xrightarrow{n} & \prod_{i\in I}A_i^X/\mathcal{F}
\end{array} ψ ( A ) ↓ ρ ψ ≅ ∏ i ∈ I ψ ( A i ) / F ⟶ r φ ( A ) ↓ ρ φ ∏ i ∈ I φ ( A i ) / F ⟶ n A X ↓ ρ X ≅ ∏ i ∈ I A i X / F
Since n ∈ M n \in\mathcal{M} n ∈ M , by orthogonality, there is an arrow ρ φ \rho^\varphi ρ φ as above. As before, we also have r ∈ E r \in\mathcal{E} r ∈ E , and so ρ φ \rho^\varphi ρ φ is an isomorphism (see the case where φ ≡ ( s = t ) \varphi\equiv(s=t) φ ≡ ( s = t ) ).
Finally, with the additional hypotheses of (ii), we are left with two more cases, namely where φ ≡ ⊥ \varphi\equiv\bot φ ≡ ⊥ and φ ≡ φ 1 ∨ φ 2 \varphi\equiv\varphi_1 \lor\varphi_2 φ ≡ φ 1 ∨ φ 2 .
When φ ≡ ⊥ \varphi\equiv\bot φ ≡ ⊥ , of arity X X X , we have again an induced diagram as follows.
0 ⟶ ⊥ ( A ) ⟶ A X ↓ ↓ ρ ⊥ ↓ ρ X ≅ ∏ i ∈ I 0 / F → r ∏ i ∈ I ⊥ ( A i ) / F → n ∏ i ∈ I A i X / F \begin{array}{ccccc}
0 & \longrightarrow& \bot(A) & \longrightarrow& A^X \\
\downarrow& & \downarrow{\scriptstyle\rho^\bot} & & \downarrow{\scriptstyle\rho^X}_{\cong} \\
\prod_{i\in I}0/\mathcal{F} & \xrightarrow{r} & \prod_{i\in I}\bot(A_i)/\mathcal{F} & \xrightarrow{n} & \prod_{i\in I}A_i^X/\mathcal{F}
\end{array} 0 ↓ ∏ i ∈ I 0/ F ⟶ r ⊥ ( A ) ↓ ρ ⊥ ∏ i ∈ I ⊥ ( A i ) / F ⟶ n A X ↓ ρ X ≅ ∏ i ∈ I A i X / F
Again, r r r is in E \mathcal{E} E and n n n in M \mathcal{M} M . By the ultraproduct covering property the left vertical arrow is also in E \mathcal{E} E , so ρ ⊥ \rho^\bot ρ ⊥ must be an isomorphism.
To conclude consider the case where φ ≡ φ 1 ∨ φ 2 \varphi\equiv\varphi_1 \lor\varphi_2 φ ≡ φ 1 ∨ φ 2 ; we have an induced diagram
φ 1 ( A ) + φ 2 ( A ) ⟶ φ ( A ) ⟶ A X ↓ ρ φ 1 + ρ φ 2 ↓ ρ φ ↓ ρ X ≅ ∏ i ∈ I φ 1 ( A i ) / F + ∏ i ∈ I φ 2 ( A i ) / F → c ∏ i ∈ I ( φ 1 ( A i ) + φ 2 ( A i ) ) / F → r ∏ i ∈ I φ ( A i ) / F → n ∏ i ∈ I A i X / F \begin{array}{ccccc}
\varphi_1(A)+\varphi_2(A) & \longrightarrow& \varphi(A) & \longrightarrow& A^X \\
\downarrow{\scriptstyle\rho^{\varphi_1}+\rho^{\varphi_2}} & & \downarrow{\scriptstyle\rho^\varphi} & & \downarrow{\scriptstyle\rho^X}_{\cong} \\
\prod_{i\in I}\varphi_1(A_i)/\mathcal{F}+\prod_{i\in I}\varphi_2(A_i)/\mathcal{F} & \xrightarrow{c} & \prod_{i\in I}(\varphi_1(A_i)+\varphi_2(A_i))/\mathcal{F} & \xrightarrow{r} & \prod_{i\in I}\varphi(A_i)/\mathcal{F} \xrightarrow{n} \prod_{i\in I}A_i^X/\mathcal{F}
\end{array} φ 1 ( A ) + φ 2 ( A ) ↓ ρ φ 1 + ρ φ 2 ∏ i ∈ I φ 1 ( A i ) / F + ∏ i ∈ I φ 2 ( A i ) / F ⟶ c φ ( A ) ↓ ρ φ ∏ i ∈ I ( φ 1 ( A i ) + φ 2 ( A i )) / F ⟶ r A X ↓ ρ X ≅ ∏ i ∈ I φ ( A i ) / F n ∏ i ∈ I A i X / F
where ρ φ 1 + ρ φ 2 \rho^{\varphi_1}+\rho^{\varphi_2} ρ φ 1 + ρ φ 2 is invertible by inductive hypothesis, c c c is the unique comparison arrow, and ρ φ \rho^\varphi ρ φ is again induced by orthogonality. As before, we have that r ∈ E r \in\mathcal{E} r ∈ E . By the ultraproduct covering property we also have c ∈ E c \in\mathcal{E} c ∈ E . So ρ φ \rho^\varphi ρ φ is an isomorphism by uniqueness of ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) -factorisations. □ \square □
Lemma 4.5. Let { A i } i ∈ I \{A_i\}_{i\in I} { A i } i ∈ I and { B i } i ∈ I \{B_i\}_{i\in I} { B i } i ∈ I be two families of objects in a complete and cocomplete category C \mathcal{C} C , indexed by the same set I I I and let F \mathcal{F} F be a filter on I I I . Suppose that for some J ∈ F J \in\mathcal{F} J ∈ F there is a family of arrows { f i : A i → B i } i ∈ J \{f_i:A_i\to B_i\}_{i\in J} { f i : A i → B i } i ∈ J . Then there is a unique induced arrow f : ∏ i ∈ I A i / F → ∏ i ∈ I B i / F f:\prod_{i\in I}A_i/\mathcal{F}\to\prod_{i\in I}B_i/\mathcal{F} f : ∏ i ∈ I A i / F → ∏ i ∈ I B i / F such that the diagram below commutes
∏ i ∈ J A i → ∏ i ∈ J f i ∏ i ∈ J B i ↓ ↓ ∏ i ∈ I A i / F → f ∏ i ∈ I B i / F \begin{array}{ccccc}
\prod_{i\in J}A_i & \xrightarrow{\prod_{i\in J}f_i} & \prod_{i\in J}B_i \\
\downarrow& & \downarrow\\
\prod_{i\in I}A_i/\mathcal{F} & \xrightarrow{f} & \prod_{i\in I}B_i/\mathcal{F}
\end{array} ∏ i ∈ J A i ↓ ∏ i ∈ I A i / F ∏ i ∈ J f i f ∏ i ∈ J B i ↓ ∏ i ∈ I B i / F
where the vertical arrows are the coprojections.
Proof. The compositions
( ∏ i ∈ J ′ A i → ∏ i ∈ J ′ f i ∏ i ∈ J ′ B i ⟶ ∏ i ∈ I B i / F ) J ′ ∈ F , J ′ ⊆ J (1) \left(\prod_{i\in J'} A_i \xrightarrow{\prod_{i\in J'} f_i} \prod_{i\in J'} B_i \longrightarrow\prod_{i\in I} B_i/\mathcal{F}\right)_{J'\in\mathcal{F},\,J'\subseteq J} \tag*{(1)} ( i ∈ J ′ ∏ A i ∏ i ∈ J ′ f i i ∈ J ′ ∏ B i ⟶ i ∈ I ∏ B i / F ) J ′ ∈ F , J ′ ⊆ J (1)
form a cocone for the diagram of ∏ i ∈ I A i / F \prod_{i\in I} A_i/F ∏ i ∈ I A i / F restricted to those J ′ ∈ F J' \in\mathcal{F} J ′ ∈ F with J ′ ⊆ J J' \subseteq J J ′ ⊆ J . This restriction is cofinal in the original diagram of ∏ i ∈ I A i / F \prod_{i\in I} A_i/F ∏ i ∈ I A i / F and thus induces a unique arrow ∏ i ∈ I A i / F → ∏ i ∈ I B i / F \prod_{i\in I} A_i/F \to\prod_{i\in I} B_i/F ∏ i ∈ I A i / F → ∏ i ∈ I B i / F , which is our required f f f .
Theorem 1.2 (Łos-style theorem 2), repeated. Assume that V \mathcal{V} V is reduced product stable. Let L \mathbb{L} L be a language on V \mathcal{V} V and let σ \sigma σ be a sequent of L \mathbb{L} L -formulas. Let A : = ∏ i ∈ I A i / F A := \prod_{i\in I} A_i/F A := ∏ i ∈ I A i / F be a reduced product of L \mathbb{L} L -structures. Then
{ i ∈ I ∣ A i ⊨ σ } ∈ F implies A ⊨ σ , \{i\in I \mid A_i \models\sigma\}\in F \quad\text{implies} \quad A \models\sigma, { i ∈ I ∣ A i ⊨ σ } ∈ F implies A ⊨ σ , provided that:
(i) σ \sigma σ is a sequent of regular formulas, or;
(ii) σ \sigma σ is a sequent of positive formulas, F F F is an ultrafilter, and V \mathcal{V} V has the ultraproduct covering property.
Proof. Let φ \varphi φ and ψ \psi ψ be the X X X -ary formulas such that σ \sigma σ is the sequent φ ⊢ ψ \varphi\vdash\psi φ ⊢ ψ . Write J : = { i ∈ I ∣ A i ⊨ σ } J := \{i\in I \mid A_i \models\sigma\} J := { i ∈ I ∣ A i ⊨ σ } and assume J ∈ F J\in F J ∈ F . For any i ∈ J i\in J i ∈ J there is an arrow f i : φ ( A i ) → ψ ( A i ) f_i\colon\varphi(A_i)\to\psi(A_i) f i : φ ( A i ) → ψ ( A i ) making the diagram below commute.
φ ( A i ) → f i ψ ( A i ) ↓ ↓ A i X = A i X \begin{CD}
\varphi(A_i) @>{f_i}>> \psi(A_i)\\
@VVV @VVV\\
A_i^X @= A_i^X
\end{CD} φ ( A i ) ↓ ⏐ A i X f i ψ ( A i ) ↓ ⏐ A i X
By Theorem 4.5 we thus find the arrow f f f in the diagram below, making the square on the left commute.
∏ i ∈ I φ ( A i ) / F → ≅ φ ( A ) → ∏ i ∈ I A i / F → ≅ A X ↑ ↑ ↑ ∏ i ∈ J φ ( A i ) → f ∏ i ∈ J A i X ↓ ∏ i ∈ J f i ↓ ∏ i ∈ J ψ ( A i ) → ∏ i ∈ I ψ ( A i ) / F → ≅ ψ ( A ) \begin{CD}
\prod_{i\in I}\varphi(A_i)/F @>{\cong}>> \varphi(A) @>>> \prod_{i\in I}A_i/F @>{\cong}>> A^X\\
@AAA @. @AAA @AAA\\
\prod_{i\in J}\varphi(A_i) @>{f}>> \prod_{i\in J}A_i^X\\
@VV{\prod_{i\in J}f_i}V @VVV\\
\prod_{i\in J}\psi(A_i) @>>> \prod_{i\in I}\psi(A_i)/F @>{\cong}>> \psi(A)
\end{CD} i ∈ I ∏ φ ( A i ) / F ⏐ ↑ i ∈ J ∏ φ ( A i ) ↓ ⏐ ∏ i ∈ J f i i ∈ J ∏ ψ ( A i ) ≅ f φ ( A ) i ∈ J ∏ A i X ↓ ⏐ i ∈ I ∏ ψ ( A i ) / F ≅ i ∈ I ∏ A i / F ⏐ ↑ ψ ( A ) ≅ A X ⏐ ↑
Furthermore, the triangle involving f f f commutes by the unicity part of Theorem 4.5. The isomorphisms in that same triangle follow from Theorem 1.1, which concludes our proof. □ \square □
For a converse we use pointwise satisfaction of formulas.
Theorem 4.6 (Łos-style theorem 2, with converse). Assume that V \mathcal{V} V is reduced product stable and suppose that there exists a finitely presentable E \mathcal{E} E -generator Y Y Y of V 0 \mathcal{V}_0 V 0 . Let L \mathbb{L} L be a language on V \mathcal{V} V and let σ \sigma σ be a sequent of L \mathbb{L} L -formulas. Let A : = ∏ i ∈ I A i / F A := \prod_{i\in I} A_i/F A := ∏ i ∈ I A i / F be a reduced product of L \mathbb{L} L -structures. Then
{ i ∈ I ∣ A i ⊨ σ } ∈ F if and only if A ⊨ σ , \{i\in I \mid A_i \models\sigma\}\in F \quad\text{if and only if} \quad A \models\sigma, { i ∈ I ∣ A i ⊨ σ } ∈ F if and only if A ⊨ σ , provided that:
(i) σ ≡ ( φ ⊢ ψ ) \sigma\equiv(\varphi\vdash\psi) σ ≡ ( φ ⊢ ψ ) is a sequent of X X X -ary regular formulas and there is an arrow a : Y → A X a\colon Y\to A^X a : Y → A X such that A ⊨ φ ( a ) A \models\varphi(a) A ⊨ φ ( a ) , or;
(ii) σ \sigma σ is a sequent of regular formulas and F F F is an ultrafilter, or;
(iii) σ \sigma σ is a sequent of positive formulas, F F F is an ultrafilter, and V \mathcal{V} V has the ultraproduct covering property.
Proof. The left to right direction is Theorem 1.2, we prove the converse. We start by defining
J : = { i ∈ I ∣ A i ⊭ σ } . J := \{i\in I \mid A_i \not\models\sigma\}. J := { i ∈ I ∣ A i ⊨ σ } .
For every i ∈ J i\in J i ∈ J there is b i : Y → A i X b_i\colon Y\to A_i^X b i : Y → A i X such that A i ⊭ σ ( b i ) A_i\not\models\sigma(b_i) A i ⊨ σ ( b i ) , by Theorem 2.18. We first prove (i). By assumption, there is an arrow a : Y → A X a\colon Y\to A^X a : Y → A X such that A ⊨ φ ( a ) A\models\varphi(a) A ⊨ φ ( a ) . By Theorem 1.1(i) this arrow factors as
Y ⟶ ∏ i ∈ I φ ( A i ) / F ≅ φ ( A ) ⟶ A X . Y \longrightarrow\prod_{i\in I}\varphi(A_i)/F \cong\varphi(A) \longrightarrow A^X. Y ⟶ i ∈ I ∏ φ ( A i ) / F ≅ φ ( A ) ⟶ A X .
Since Y Y Y is finitely presentable, the first factor of the above arrow factors as
Y → a ′ ∏ i ∈ J ′ φ ( A i ) ⟶ ∏ i ∈ I φ ( A i ) / F , Y \xrightarrow{a'} \prod_{i\in J'}\varphi(A_i) \longrightarrow\prod_{i\in I}\varphi(A_i)/\mathcal{F}, Y a ′ i ∈ J ′ ∏ φ ( A i ) ⟶ i ∈ I ∏ φ ( A i ) / F ,
for some J ′ ∈ F J' \in\mathcal{F} J ′ ∈ F . For i ∈ J ∪ J ′ i \in J \cup J' i ∈ J ∪ J ′ we define an arrow c i : Y → A i X c_i:Y \to A_i^X c i : Y → A i X as follows: if i ∈ J i \in J i ∈ J then c i : = b i c_i:=b_i c i := b i , otherwise, if i ∈ J ′ ∖ J i \in J'\setminus J i ∈ J ′ ∖ J , then c i c_i c i is the composite
Y \xrightarrow{a'} \prod_{i\in J'}\varphi(A_i) \longrightarrow\varphi(A_i) \lhook\joinrel\longrightarrow A_i^X.
For each i ∈ J ∪ J ′ i \in J \cup J' i ∈ J ∪ J ′ we have A i ⊨ φ ( c i ) A_i \models\varphi(c_i) A i ⊨ φ ( c i ) . Indeed, for i ∈ J ′ ∖ J i \in J'\setminus J i ∈ J ′ ∖ J this is by construction and for i ∈ J i \in J i ∈ J we have A i ⊭ σ ( c i ) A_i \not\models\sigma(c_i) A i ⊨ σ ( c i ) , so we must have A i ⊨ φ ( c i ) A_i \models\varphi(c_i) A i ⊨ φ ( c i ) and A i ⊭ ψ ( c i ) A_i \not\models\psi(c_i) A i ⊨ ψ ( c i ) . Write c : Y → A X c:Y \to A^X c : Y → A X for the composite
Y → ( c i ) i ∈ J ∪ J ′ ∏ i ∈ J ∪ J ′ A i X ⟶ ∏ i ∈ I A i X / F ≅ A X . Y \xrightarrow{(c_i)_{i\in J\cup J'}} \prod_{i\in J\cup J'} A_i^X \longrightarrow\prod_{i\in I} A_i^X/\mathcal{F} \cong A^X. Y ( c i ) i ∈ J ∪ J ′ i ∈ J ∪ J ′ ∏ A i X ⟶ i ∈ I ∏ A i X / F ≅ A X .
Then by construction (and implicitly using Theorem 1.1(i) again) we have A ⊨ φ ( c ) A \models\varphi(c) A ⊨ φ ( c ) . So since A ⊨ σ A \models\sigma A ⊨ σ , we must also have A ⊨ ψ ( c ) A \models\psi(c) A ⊨ ψ ( c ) . So, like before, c c c factors as
Y ⟶ ∏ i ∈ J ∗ ψ ( A i ) ⟶ ∏ i ∈ J ∗ A i X ⟶ ∏ i ∈ I A i X / F ≅ A X , Y \longrightarrow\prod_{i\in J^*}\psi(A_i) \longrightarrow\prod_{i\in J^*} A_i^X \longrightarrow\prod_{i\in I} A_i^X/\mathcal{F} \cong A^X, Y ⟶ i ∈ J ∗ ∏ ψ ( A i ) ⟶ i ∈ J ∗ ∏ A i X ⟶ i ∈ I ∏ A i X / F ≅ A X ,
for some J ∗ ∈ F J^* \in\mathcal{F} J ∗ ∈ F . We may as well assume J ∗ ⊆ J ∪ J ′ J^* \subseteq J \cup J' J ∗ ⊆ J ∪ J ′ . In fact, this factorisation is essentially unique, and so we may assume that the factor Y → ∏ i ∈ J ∗ ψ ( A i ) → ∏ i ∈ J ∗ A i X Y \to\prod_{i\in J^*}\psi(A_i) \to\prod_{i\in J^*} A_i^X Y → ∏ i ∈ J ∗ ψ ( A i ) → ∏ i ∈ J ∗ A i X is given by ( c i ) i ∈ J ∗ (c_i)_{i\in J^*} ( c i ) i ∈ J ∗ . So for all i ∈ J ∗ i \in J^* i ∈ J ∗ we have A i ⊨ ψ ( c i ) A_i \models\psi(c_i) A i ⊨ ψ ( c i ) , which means that J ∗ ∩ J = ∅ J^* \cap J = \varnothing J ∗ ∩ J = ∅ . In other words, J ∗ ⊆ I ∖ J J^* \subseteq I \setminus J J ∗ ⊆ I ∖ J , and hence { i ∈ I ∣ A i ⊨ σ } = I ∖ J ∈ F \{i \in I \mid A_i \models\sigma\}=I\setminus J\in\mathcal{F} { i ∈ I ∣ A i ⊨ σ } = I ∖ J ∈ F , as required.
We now prove (ii) by considering two cases. Either there is an arrow a : Y → A X a:Y \to A^X a : Y → A X as in (i), and then we are done by (i), or there is no such arrow. In that second case we cannot have J ∈ F J\in\mathcal{F} J ∈ F , as A i ⊨ φ ( b i ) A_i \models\varphi(b_i) A i ⊨ φ ( b i ) for every i ∈ J i \in J i ∈ J and so we would have an arrow
b : Y → ( b i ) i ∈ J ∏ i ∈ J A i X ⟶ ∏ i ∈ I A i X / F ≅ A X , b:Y \xrightarrow{(b_i)_{i\in J}} \prod_{i\in J} A_i^X \longrightarrow\prod_{i\in I} A_i^X/\mathcal{F} \cong A^X, b : Y ( b i ) i ∈ J i ∈ J ∏ A i X ⟶ i ∈ I ∏ A i X / F ≅ A X ,
such that A ⊨ φ ( b ) A \models\varphi(b) A ⊨ φ ( b ) . So since F \mathcal{F} F is an ultrafilter, we have { i ∈ I ∣ A i ⊨ σ } = I ∖ J ∈ F \{i \in I \mid A_i \models\sigma\}=I\setminus J\in\mathcal{F} { i ∈ I ∣ A i ⊨ σ } = I ∖ J ∈ F , as required. Finally, the proof of (iii) is the same, except any uses of Theorem 1.1(i) are replaced by Theorem 1.1(ii).
Example 4.7. The assumption about the existence of an arrow Y → A X Y \to A^X Y → A X in Theorem 4.6(i) is necessary. Without it, the statement is false, already in the case V = S e t \mathcal{V}=\mathbf{Set} V = Set . In that case, Y = 1 Y=1 Y = 1 is our finitely presentable generator. Consider a language L \mathcal{L} L with one unary relation symbol P P P . We let I = ω I=\omega I = ω and define A i : = { 0 , 1 } A_i:=\{0,1\} A i := { 0 , 1 } with A i ⊨ ¬ P ( 0 ) ∧ P ( 1 ) A_i\models\neg P(0)\land P(1) A i ⊨ ¬ P ( 0 ) ∧ P ( 1 ) if i i i is even and A i : = { 0 } A_i:=\{0\} A i := { 0 } with A i ⊨ ¬ P ( 0 ) A_i\models\neg P(0) A i ⊨ ¬ P ( 0 ) if i i i is odd. Let F \mathcal{F} F be the filter on I I I of cofinite sets. Then A ⊨ P ( x ) ⊢ ⊥ A\models P(x)\vdash\bot A ⊨ P ( x ) ⊢ ⊥ , because every cofinite set contains at least one odd number. At the same time { i ∈ I ∣ A i ⊨ P ( x ) ⊢ ⊥ } \{i\in I\mid A_i\models P(x)\vdash\bot\} { i ∈ I ∣ A i ⊨ P ( x ) ⊢ ⊥ } is the set of odd numbers, which is not an element of F \mathcal{F} F because any cofinite set will contain at least one even number.
Compactness and formulas with parameters
We would be ready to prove the compactness theorem now, but one of the main strengths of the compactness theorem is to apply it to what model theorists refer to as “parameters”. Their function is to describe part of a structure that we wish to construct and show that finite fragments of it can be constructed, so that the compactness theorem then implies that our desired structure exists. In the case V = S e t \mathcal{V}=\mathbf{Set} V = Set this is done using constant symbols: we introduce constant symbols for the elements we wish to exist in the structure and we use logical formulas to describe how we want these elements to be related to one another. For example, this happens in the model-theoretic method of diagrams (see Theorem 6.1). However, for a general base of enrichment V \mathcal{V} V we cannot just work with constant symbols. For example, in the case V = A b \mathcal{V}=\mathbf{Ab} V = Ab a constant symbol — i.e., a ( 0 , X ) (0,X) ( 0 , X ) -ary function symbol — can only be interpreted in one way in any given structure A A A , namely as the unique arrow 0 = 1 = A 0 → A X 0=1=A^0\to A^X 0 = 1 = A 0 → A X . We thus introduce parameters as a separate mechanism.
Definition 5.1. A parameter is a symbol p : X p:X p : X , where X X X is an object of V \mathcal{V} V , called the domain of p p p .
Given a set P \mathcal{P} P of parameters and an object A A A of V \mathcal{V} V , an interpretation of P \mathcal{P} P in A A A is a tuple ( p A ) p ∈ P (p^{A})_{p\in\mathcal{P}} ( p A ) p ∈ P , where for each p : X p:X p : X in P \mathcal{P} P
is an arrow in V \mathcal{V} V .
A morphism of P \mathcal{P} P -interpretations h : A → B h:A\to B h : A → B is an arrow in V \mathcal{V} V making the triangle
X ↙ p B ↘ p A B ⟵ h A \begin{array}{ccccc}
& & X & & \\
& \swarrow^{p^{B}} & & \searrow^{p^{A}} & \\
B & \underset{h}{\longleftarrow} & & & A
\end{array} B ↙ p B h ⟵ X ↘ p A A commute for all p : X p:X p : X in P \mathcal{P} P .
The main point about parameters is to use them in L \mathbb{L} L -structures and L \mathbb{L} L -formulas.
Definition 5.2. Let L \mathbb{L} L be a language on V \mathcal{V} V and let P \mathcal{P} P be a set of parameters. An ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structure ( A , ( p A ) p ∈ P ) (A,(p^{A})_{p\in\mathcal{P}}) ( A , ( p A ) p ∈ P ) is an L \mathbb{L} L -structure A A A together with an interpretation ( p A ) p ∈ P (p^{A})_{p\in\mathcal{P}} ( p A ) p ∈ P of P \mathcal{P} P in A A A . A morphism of ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structures is an arrow in V \mathcal{V} V that is both a homomorphism of L \mathbb{L} L -structures and a morphism of P \mathcal{P} P -interpretations. We write Str ( L , P ) \operatorname{Str}(\mathbb{L},\mathcal{P}) Str ( L , P ) for the (ordinary) category of ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structures.
Sometimes we may drop the tuple of parameters from the notation and just say talk about the ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structure A A A .
As discussed before, parameters are a separate mechanism from the enriched syntax. The example below shows the necessity for this separation. The situation is different when V \mathcal{V} V is semicartesian (i.e., the monoidal unit I I I is the terminal object), in which case we can capture parameters using constant symbols, like in the V = S e t \mathcal{V}=\mathbf{Set} V = Set case. This is made precise in § 6.1 .
Example 5.3. In general Str ( L , P ) \operatorname{Str}(\mathbb{L},\mathcal{P}) Str ( L , P ) is not the underlying category of some V \mathcal{V} V -category. Indeed, if V = A b \mathcal{V}=\mathbf{Ab} V = Ab , L = ∅ \mathbb{L}=\varnothing L = ∅ , and P = { p : Z } \mathcal{P}=\{p:\mathbb{Z}\} P = { p : Z } , then Str ( L , P ) = A b ∗ \operatorname{Str}(\mathbb{L},\mathcal{P})=\mathbf{Ab}_{*} Str ( L , P ) = Ab ∗ coincides with the category of pointed abelian groups (that is, abelian groups with a specified element) which is not A b \mathbf{Ab} Ab -enriched (since, for example, certain homsets are empty).
We now introduce the notion of parametrised formulas and sequents, and the validity of such formulas and sequents in structures.
Definition 5.4. An L \mathbb{L} L -formula with parameters in P \mathcal{P} P is a tuple ( φ , p 1 , … , p n ) (\varphi,p_{1},\ldots,p_{n}) ( φ , p 1 , … , p n ) , which we will denote by φ ( p 1 , … , p n ) \varphi(p_{1},\ldots,p_{n}) φ ( p 1 , … , p n ) , where φ \varphi φ is an ( X 1 + … + X n ) (X_{1}+\ldots+X_{n}) ( X 1 + … + X n ) -ary L \mathbb{L} L -formula and p 1 : X 1 , … , p n : X n p_{1}:X_{1},\ldots,p_{n}:X_{n} p 1 : X 1 , … , p n : X n are parameters in P \mathcal{P} P .
Given an ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structure ( A , ( p A ) p ∈ P ) (A,(p^{A})_{p\in\mathcal{P}}) ( A , ( p A ) p ∈ P ) and φ ( p 1 , … , p n ) \varphi(p_{1},\ldots,p_{n}) φ ( p 1 , … , p n ) as above, there is an arrow p : = ( p 1 A + … + p n A ) t : I → A X 1 + … + X n p:=(p_{1}^{A}+\ldots+p_{n}^{A})^{t}:I\to A^{X_{1}+\ldots+X_{n}} p := ( p 1 A + … + p n A ) t : I → A X 1 + … + X n induced by the transpose of the coproduct of the interpretations of the parameters. We say that ( p 1 , … , p n ) (p_{1},\ldots,p_{n}) ( p 1 , … , p n ) realises φ \varphi φ in A A A or that A A A satisfies φ ( p 1 , … , p n ) \varphi(p_{1},\ldots,p_{n}) φ ( p 1 , … , p n ) , and write
A ⊨ φ ( p 1 , … , p n ) , A\models\varphi(p_{1},\ldots,p_{n}), A ⊨ φ ( p 1 , … , p n ) , if A ⊨ φ ( p ) A\models\varphi(p) A ⊨ φ ( p ) as an L \mathbb{L} L -structure, in the sense of Theorem 2.16.
Definition 5.5. An L \mathbb{L} L -sequent with parameters in P \mathcal{P} P is a tuple ( σ , p 1 , … , p n ) (\sigma,p_{1},\ldots,p_{n}) ( σ , p 1 , … , p n ) , denoted by σ ( p 1 , … , p n ) \sigma(p_{1},\ldots,p_{n}) σ ( p 1 , … , p n ) , where σ \sigma σ is an ( X 1 + … + X n ) (X_{1}+\ldots+X_{n}) ( X 1 + … + X n ) -ary sequent φ ⊢ ψ \varphi\vdash\psi φ ⊢ ψ , and p 1 : X 1 , … , p n : X n p_{1}:X_{1},\ldots,p_{n}:X_{n} p 1 : X 1 , … , p n : X n are parameters in P \mathcal{P} P . We may also write φ ( p 1 , … , p n ) ⊢ ψ ( p 1 , … , p n ) \varphi(p_{1},\ldots,p_{n})\vdash\psi(p_{1},\ldots,p_{n}) φ ( p 1 , … , p n ) ⊢ ψ ( p 1 , … , p n ) for such a parametrised sequent.
Given an ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structure ( A , ( p A ) p ∈ P ) (A,(p^{A})_{p\in\mathcal{P}}) ( A , ( p A ) p ∈ P ) and σ ( p 1 , … , p n ) \sigma(p_{1},\ldots,p_{n}) σ ( p 1 , … , p n ) as above, we say that A A A satisfies σ ( p 1 , … , p n ) \sigma(p_{1},\ldots,p_{n}) σ ( p 1 , … , p n ) and write
A ⊨ σ ( p 1 , … , p n ) , A\models\sigma(p_{1},\ldots,p_{n}), A ⊨ σ ( p 1 , … , p n ) , if A ⊨ φ ( p 1 , … , p n ) A\models\varphi(p_{1},\ldots,p_{n}) A ⊨ φ ( p 1 , … , p n ) implies A ⊨ ψ ( p 1 , … , p n ) A\models\psi(p_{1},\ldots,p_{n}) A ⊨ ψ ( p 1 , … , p n ) .
Given a set Σ \Sigma Σ of L \mathbb{L} L -sequents with in P \mathcal{P} P , we denote by Mod ( Σ ) \operatorname{Mod}(\Sigma) Mod ( Σ ) the full subcategory of Str ( L , P ) \operatorname{Str}(\mathbb{L},\mathcal{P}) Str ( L , P ) spanned by those ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structures that satisfy every sequent in Σ \Sigma Σ . An object of Mod ( Σ ) \operatorname{Mod}(\Sigma) Mod ( Σ ) is called a model of Σ \Sigma Σ .
:::`
As usual, we will view a formula φ ( p 1 , … , p n ) \varphi(p_1,\ldots,p_n) φ ( p 1 , … , p n ) with parameters as a sequent ⊤ ⊢ φ ( p 1 , … , p n ) \top\vdash\varphi(p_1,\ldots,p_n) ⊤ ⊢ φ ( p 1 , … , p n ) , so that it makes sense to speak of a model of a set of formulas with parameters.
We note that the domains of parameters in a sequent (or formula) with parameters are finitely presentable, because they match the arity of the sequent, which is formulated in finitary logic.
We are now ready for our final ingredient in proving a compactness theorem for parametrised sequents: a parametrised version of our Los-style theorem, which in turn requires reduced products of ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structures.
Definition 5.6. Assume that V \mathcal{V} V is reduced product ready. Let L \mathbb{L} L be a language on V \mathcal{V} V and let P \mathcal{P} P be a set of parameters. Given a family { A i } i ∈ I \{A_i\}_{i\in I} { A i } i ∈ I of ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structures and a filter F \mathcal{F} F on I I I we define the reduced product A : = ∏ i ∈ I A i / F A := \prod_{i\in I} A_i/\mathcal{F} A := ∏ i ∈ I A i / F to be the following ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structure. The underlying L \mathbb{L} L -structure is just the reduced product of L \mathbb{L} L -structures. For p : X p\colon X p : X in P \mathcal{P} P we define its interpretation p A : X → A p^A\colon X \to A p A : X → A to be the composition
X → ( p A i ) i ∈ I ∏ i ∈ I A i → ∏ i ∈ I A i / F , X \xrightarrow{(p^{A_i})_{i\in I}} \prod_{i\in I} A_i \to\prod_{i\in I} A_i/\mathcal{F}, X ( p A i ) i ∈ I i ∈ I ∏ A i → i ∈ I ∏ A i / F , where the second arrow is the coprojection.
Theorem 5.7 (Los-style theorem, with parameters). Assume that V \mathcal{V} V is reduced product stable. Let L \mathbb{L} L be a language on V \mathcal{V} V and let σ ( p 1 , … , p n ) \sigma(p_1,\ldots,p_n) σ ( p 1 , … , p n ) be a sequent of L \mathbb{L} L -formulas with parameters in P \mathcal{P} P . Assume also that the monoidal unit I I I is finitely presentable or that σ \sigma σ is of the form ⊤ ⊢ ψ ( p 1 , … , p n ) \top\vdash\psi(p_1,\ldots,p_n) ⊤ ⊢ ψ ( p 1 , … , p n ) . Let A : = ∏ i ∈ I A i / F A := \prod_{i\in I} A_i/\mathcal{F} A := ∏ i ∈ I A i / F be a reduced product of ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structures. Then
{ i ∈ I ∣ A i ⊨ σ ( p 1 , … , p n ) } ∈ F implies A ⊨ σ ( p 1 , … , p n ) , \{i\in I \mid A_i \models\sigma(p_1,\ldots,p_n)\}\in\mathcal{F}\quad\text{implies}\quad A\models\sigma(p_1,\ldots,p_n), { i ∈ I ∣ A i ⊨ σ ( p 1 , … , p n )} ∈ F implies A ⊨ σ ( p 1 , … , p n ) , provided that:
σ \sigma σ is a sequent of regular formulas, or;
σ \sigma σ is a sequent of positive formulas, F \mathcal{F} F is an ultrafilter, and V \mathcal{V} V has the ultraproduct covering property.
Proof. Let φ \varphi φ and ψ \psi ψ be ( X 1 + ⋯ + X n ) (X_1+\cdots+X_n) ( X 1 + ⋯ + X n ) -ary formulas such that σ \sigma σ is the sequent φ ⊢ ψ \varphi\vdash\psi φ ⊢ ψ , and suppose that A ⊨ φ ( p 1 , … , p n ) A \models\varphi(p_1,\ldots,p_n) A ⊨ φ ( p 1 , … , p n ) . Write p : = ( p 1 A + ⋯ + p n A ) t : I → A X 1 + ⋯ + X n p := (p_1^{A}+\cdots+p_n^{A})t\colon I\to A^{X_1+\cdots+X_n} p := ( p 1 A + ⋯ + p n A ) t : I → A X 1 + ⋯ + X n for the arrow induced by the transpose of the coproduct of the interpretations of the parameters. So p p p factors through φ ( A ) ≅ ∏ i ∈ I φ ( A i ) / F \varphi(A)\cong\prod_{i\in I}\varphi(A_i)/\mathcal{F} φ ( A ) ≅ ∏ i ∈ I φ ( A i ) / F , where the isomorphism follows from Theorem 1.1. We claim that p p p factors as
I → ∏ i ∈ J φ ( A i ) → ∏ i ∈ J A i X 1 + ⋯ + X n → ∏ i ∈ I A i X 1 + ⋯ + X n / F ≅ A X 1 + ⋯ + X n , I\to\prod_{i\in J}\varphi(A_i)\to\prod_{i\in J}A_i^{X_1+\cdots+X_n}\to\prod_{i\in I}A_i^{X_1+\cdots+X_n}/\mathcal{F}\cong A^{X_1+\cdots+X_n}, I → i ∈ J ∏ φ ( A i ) → i ∈ J ∏ A i X 1 + ⋯ + X n → i ∈ I ∏ A i X 1 + ⋯ + X n / F ≅ A X 1 + ⋯ + X n ,
for some J ∈ F J\in\mathcal{F} J ∈ F , such that the first two arrows compose to ( ( p 1 A i + ⋯ + p n A i ) t ) i ∈ J : I → ∏ i ∈ J A i X 1 + ⋯ + X n ((p_1^{A_i}+\cdots+p_n^{A_i})t)_{i\in J}\colon I\to\prod_{i\in J}A_i^{X_1+\cdots+X_n} (( p 1 A i + ⋯ + p n A i ) t ) i ∈ J : I → ∏ i ∈ J A i X 1 + ⋯ + X n . If φ ≡ ⊤ \varphi\equiv\top φ ≡ ⊤ then we can take J = I J=I J = I . If φ \varphi φ is not ⊤ \top ⊤ then we assumed that I I I is finitely presentable, so we find J ∈ F J\in\mathcal{F} J ∈ F such that p p p factors through ∏ i ∈ J φ ( A i ) \prod_{i\in J}\varphi(A_i) ∏ i ∈ J φ ( A i ) . The condition on the composition of the first two arrows then follows (after possibly replacing J J J with a smaller set in F \mathcal{F} F ) from essential uniqueness of the factorisation of p p p through the diagram of ∏ i ∈ I A i X 1 + ⋯ + X n / F \prod_{i\in I}A_i^{X_1+\cdots+X_n}/\mathcal{F} ∏ i ∈ I A i X 1 + ⋯ + X n / F .
Define
J ′ : = J ∩ { i ∈ I ∣ A i ⊨ σ ( p 1 , … , p n ) } , J' := J\cap\{i\in I\mid A_i\models\sigma(p_1,\ldots,p_n)\}, J ′ := J ∩ { i ∈ I ∣ A i ⊨ σ ( p 1 , … , p n )} ,
so J ′ ∈ F J'\in\mathcal{F} J ′ ∈ F . Then for all i ∈ J ′ i\in J' i ∈ J ′ we have that A i ⊨ ψ ( p 1 , … , p n ) A_i\models\psi(p_1,\ldots,p_n) A i ⊨ ψ ( p 1 , … , p n ) . So ( p 1 A i + ⋯ + p n A i ) t : I → A i X 1 + ⋯ + X n (p_1^{A_i}+\cdots+p_n^{A_i})t\colon I\to A_i^{X_1+\cdots+X_n} ( p 1 A i + ⋯ + p n A i ) t : I → A i X 1 + ⋯ + X n factors through ψ ( A i ) \psi(A_i) ψ ( A i ) . We thus find the dashed arrow in the diagram below, making the entire diagram commute (where the isomorphisms at the top come from Theorem 1.1).
I ⟶ ψ ( A ) ⟶ A X 1 + ⋯ + X n I ↘ ↗ ∏ i ∈ J ′ ψ ( A i ) ⟶ ∏ i ∈ J ′ A i X 1 + ⋯ + X n I ↑ ↑ ∏ i ∈ I ψ ( A i ) / F ⟶ ∏ i ∈ I A i X 1 + ⋯ + X n / F \begin{aligned}
&I \longrightarrow\psi(A) \longrightarrow A^{X_1+\cdots+X_n}\\
&\phantom{I}\searrow\qquad\qquad\qquad\qquad\nearrow\\
&\prod_{i\in J'}\psi(A_i) \longrightarrow\prod_{i\in J'}A_i^{X_1+\cdots+X_n}\\
&\phantom{I}\uparrow\qquad\qquad\qquad\qquad\uparrow\\
&\prod_{i\in I}\psi(A_i)/\mathcal{F} \longrightarrow\prod_{i\in I}A_i^{X_1+\cdots+X_n}/\mathcal{F}
\end{aligned} I ⟶ ψ ( A ) ⟶ A X 1 + ⋯ + X n I ↘ ↗ i ∈ J ′ ∏ ψ ( A i ) ⟶ i ∈ J ′ ∏ A i X 1 + ⋯ + X n I ↑ ↑ i ∈ I ∏ ψ ( A i ) / F ⟶ i ∈ I ∏ A i X 1 + ⋯ + X n / F
So p p p factors through ψ ( A ) \psi(A) ψ ( A ) and hence A ⊨ ψ ( p 1 , … , p n ) A \models\psi(p_1,\ldots,p_n) A ⊨ ψ ( p 1 , … , p n ) , as required.
Theorem 1.3 (Compactness), repeated. Assume that V \mathcal{V} V is reduced product stable. Let L \mathcal{L} L be a language on V \mathcal{V} V , let T \mathbb{T} T be a theory, and let Σ \Sigma Σ be a set of sequents with parameters in P \mathcal{P} P . Assume also that the monoidal unit I I I is finitely presentable or that all sequents in Σ \Sigma Σ are of the form ⊤ ⊢ ψ ( p 1 , … , p n ) \top\vdash\psi(p_1,\ldots,p_n) ⊤ ⊢ ψ ( p 1 , … , p n ) .
If every finite subset of T ∪ Σ \mathbb{T}\cup\Sigma T ∪ Σ has a model then T ∪ Σ \mathbb{T}\cup\Sigma T ∪ Σ has a model, provided that:
every sequent in T ∪ Σ \mathbb{T}\cup\Sigma T ∪ Σ is a sequent of regular formulas (possibly with parameters), or;
every sequent in T ∪ Σ \mathbb{T}\cup\Sigma T ∪ Σ is a sequent of positive formulas (possibly with parameters) and V \mathcal{V} V has the ultraproduct covering property.
Proof. Recall that [ T ∪ Σ ] < ω [\mathbb{T}\cup\Sigma]^{<\omega} [ T ∪ Σ ] < ω denotes the set of finite subsets of T ∪ Σ \mathbb{T}\cup\Sigma T ∪ Σ . For each S ∈ [ T ∪ Σ ] < ω S\in[\mathbb{T}\cup\Sigma]^{<\omega} S ∈ [ T ∪ Σ ] < ω we fix a model A S A_S A S of S S S , which exists by assumption. For a sequent (possibly with parameters) σ ∈ T ∪ Σ \sigma\in\mathbb{T}\cup\Sigma σ ∈ T ∪ Σ we write
[ σ ] : = { S ∈ [ T ∪ Σ ] < ω ∣ σ ∈ S } . [\sigma]:=\{S\in[\mathbb{T}\cup\Sigma]^{<\omega}\mid\sigma\in S\}. [ σ ] := { S ∈ [ T ∪ Σ ] < ω ∣ σ ∈ S } .
For any σ 1 , σ 2 ∈ T ∪ Σ \sigma_1,\sigma_2\in\mathbb{T}\cup\Sigma σ 1 , σ 2 ∈ T ∪ Σ we have { σ 1 , σ 2 } ∈ [ σ 1 ] ∩ [ σ 2 ] \{\sigma_1,\sigma_2\}\in[\sigma_1]\cap[\sigma_2] { σ 1 , σ 2 } ∈ [ σ 1 ] ∩ [ σ 2 ] , so the family of sets { [ σ ] } σ ∈ T ∪ Σ \{[\sigma]\}_{\sigma\in\mathbb{T}\cup\Sigma} {[ σ ] } σ ∈ T ∪ Σ can be extended to an ultrafilter U \mathcal{U} U on [ T ∪ Σ ] < ω [\mathbb{T}\cup\Sigma]^{<\omega} [ T ∪ Σ ] < ω . We claim that the ultraproduct of ( L , P ) (\mathcal{L},\mathcal{P}) ( L , P ) -structures
A : = ∏ S ∈ [ T ∪ Σ ] < ω A S / U A:=\prod_{S\in[\mathbb{T}\cup\Sigma]^{<\omega}} A_S/\mathcal{U} A := S ∈ [ T ∪ Σ ] < ω ∏ A S / U
is the required model of T ∪ Σ \mathbb{T}\cup\Sigma T ∪ Σ .
To verify this, we let σ ∈ T ∪ Σ \sigma\in\mathbb{T}\cup\Sigma σ ∈ T ∪ Σ be a sequent (possibly with parameters). By construction A S ⊨ σ A_S\models\sigma A S ⊨ σ for each S ∈ [ σ ] S\in[\sigma] S ∈ [ σ ] , so [ σ ] ⊆ { S ∈ [ T ∪ Σ ] < ω ∣ A S ⊨ σ } [\sigma]\subseteq\{S\in[\mathbb{T}\cup\Sigma]^{<\omega}\mid A_S\models\sigma\} [ σ ] ⊆ { S ∈ [ T ∪ Σ ] < ω ∣ A S ⊨ σ } . Again, by construction [ σ ] ∈ U [\sigma]\in\mathcal{U} [ σ ] ∈ U , so { S ∈ [ T ∪ Σ ] < ω ∣ A S ⊨ σ } ∈ U \{S\in[\mathbb{T}\cup\Sigma]^{<\omega}\mid A_S\models\sigma\}\in\mathcal{U} { S ∈ [ T ∪ Σ ] < ω ∣ A S ⊨ σ } ∈ U . We thus conclude by Theorem 1.2 (or Theorem 5.7 if σ \sigma σ is a sequent with parameters) that A ⊨ σ A\models\sigma A ⊨ σ , as required.
Model-theoretic method of diagrams
The model-theoretic method of diagrams is a technique for axiomatising homomorphisms A → B A\to B A → B , for a fixed L \mathcal{L} L -structure A A A . Combined with the compactness theorem, this is a powerful and extremely important model-theoretic tool. It allows us to amalgamate models (Theorem 7.7), and is the cornerstone of the correspondence between (syntactic) types and automorphism orbits of the monster model, see also Theorem 7.4.
We begin by recalling the traditional method of diagrams, and point out why this fails generally in categories other than Set. This provides us with intuition for the rest of this section.
Remark 6.1 (Traditional model-theoretic method of diagrams). Fix some traditional (i.e., V = Set \mathcal{V}=\operatorname{Set} V = Set ) language L \mathcal{L} L and an L \mathcal{L} L -structure A A A . We extend L \mathcal{L} L to a new language L ( A ) \mathcal{L}(A) L ( A ) by adding a new constant symbol c a c_a c a for each a ∈ A a\in A a ∈ A . The diagram of A A A is the following set of L ( A ) \mathcal{L}(A) L ( A ) -sentences:
Diag ( A ) : = { φ ( c a 1 , … , c a n ) ∣ φ ( x 1 , … , x n ) is an atomic L -formula and A ⊨ φ ( a 1 , … , a n ) } . \operatorname{Diag}(A):=\{\varphi(c_{a_1},\ldots,c_{a_n})\mid\varphi(x_1,\ldots,x_n)\text{ is an atomic }\mathcal{L}\text{-formula and }A\models\varphi(a_1,\ldots,a_n)\}. Diag ( A ) := { φ ( c a 1 , … , c a n ) ∣ φ ( x 1 , … , x n ) is an atomic L -formula and A ⊨ φ ( a 1 , … , a n )} .
Given any L \mathbb{L} L -homomorphism h : A → B h:A\to B h : A → B , we can view B B B naturally as an L ( A ) \mathbb{L}(A) L ( A ) -structure by interpreting c a c_a c a as h ( a ) h(a) h ( a ) , for all a ∈ A a\in A a ∈ A , and we will have B ⊨ Diag ( A ) B\models\operatorname{Diag}(A) B ⊨ Diag ( A ) . Conversely, given a model B B B of Diag ( A ) \operatorname{Diag}(A) Diag ( A ) , we can define a function h : A → B h:A\to B h : A → B by setting h ( a ) = ( c a ) B h(a)=(c_a)^B h ( a ) = ( c a ) B , and this will be an L \mathbb{L} L -homomorphism. There is thus a correspondence between L \mathbb{L} L -homomorphisms with domain A A A and models of Diag ( A ) \operatorname{Diag}(A) Diag ( A ) .
In Theorem 6.1 we made essential use of the fact that we can construct a function A → B A\to B A → B on an element-by-element basis. This can be done because any object in S e t \mathsf{Set} Set is a coproduct of the terminal object 1 1 1 . This is no longer true in an arbitrary base of enrichment V \mathcal{V} V . However, if V 0 \mathcal{V}_0 V 0 is locally finitely presentable then any object is still a colimit of finitely presentable objects. We can, and will, thus replace the use of constant symbols by parameters, as introduced in § 5 .
We start by breaking up an arbitrary parameter into its finite parts, similar to how traditionally an infinite tuple of variables or constant symbols breaks up into finite subtuples (and ultimately into singletons).
Definition 6.2. Let A A A be any object in V \mathcal{V} V . We define a set of parameters as follows
P ( A ) : = { p a : X ∣ a : X → A is an arrow in V and X is finitely presentable } . \mathcal{P}(A):=\{p_a:X\mid a:X\to A\text{ is an arrow in }\mathcal{V}\text{ and }X\text{ is finitely presentable}\}. P ( A ) := { p a : X ∣ a : X → A is an arrow in V and X is finitely presentable } .
We only use P ( A ) \mathcal{P}(A) P ( A ) in contexts where V 0 \mathcal{V}_0 V 0 is locally presentable, so it is indeed (essentially) a set.
Definition 6.3. Let L \mathbb{L} L be a language on V \mathcal{V} V and let A A A be an L \mathbb{L} L -structure. We naturally interpret P ( A ) \mathcal{P}(A) P ( A ) in A A A by defining ( p a ) A : = a (p_a)^A:=a ( p a ) A := a . We then define the diagram of A A A to be the following set of formulas with parameters in P ( A ) \mathcal{P}(A) P ( A ) :
Diag ( A ) : = { φ ( p 1 , … , p n ) ∣ p 1 : X 1 , … , p n : X n are in P ( A ) , φ is ( X 1 + ⋯ + X n ) -ary regular atomic, and A ⊨ φ ( p 1 , … , p n ) } . \begin{aligned}
\operatorname{Diag}(A):=\{&\varphi(p_1,\ldots,p_n)\mid p_1:X_1,\ldots,p_n:X_n\text{ are in }\mathcal{P}(A),\\
&\varphi\text{ is }(X_1+\cdots+X_n)\text{-ary regular atomic, and}\\
&A\models\varphi(p_1,\ldots,p_n)\}.
\end{aligned} Diag ( A ) := { φ ( p 1 , … , p n ) ∣ p 1 : X 1 , … , p n : X n are in P ( A ) , φ is ( X 1 + ⋯ + X n ) -ary regular atomic, and A ⊨ φ ( p 1 , … , p n )} .
By definition A A A is a model of Diag ( A ) \operatorname{Diag}(A) Diag ( A ) .
We only allow regular atomic formulas in Diag ( A ) \operatorname{Diag}(A) Diag ( A ) (i.e., we exclude ⊥ \bot ⊥ ) for two reasons. Firstly, this is enough, as we will see. Secondly, we can then apply the compactness theorem to Diag ( A ) \operatorname{Diag}(A) Diag ( A ) even in settings where we do not have the ultraproduct covering property (cf. § 7 and § 9.3 ). This may seem unnecessary, because one would expect that ⊥ \bot ⊥ is never satisfied, but this can happen. For example, if V = A b \mathcal{V}=\mathsf{Ab} V = Ab , L = ∅ \mathbb{L}=\varnothing L = ∅ , and A = Z A=\mathbb{Z} A = Z , then A ⊨ ⊥ ( 0 ) A\models\bot(0) A ⊨ ⊥ ( 0 ) , where 0 0 0 is the zero map.
Notation 6.4. Let s : ( X , Z ) s:(X,Z) s : ( X , Z ) and t : ( Y , Z ) t:(Y,Z) t : ( Y , Z ) be L \mathbb{L} L -terms. We recall from [35 Notation 4.7] that s ( x ) = t ( y ) s(x)=t(y) s ( x ) = t ( y ) is an abbreviation for the ( X + Y ) (X+Y) ( X + Y ) -ary atomic formula defined by
s ( i X ( x , y ) ) = t ( i Y ( x , y ) ) , s(i_X(x,y))=t(i_Y(x,y)), s ( i X ( x , y )) = t ( i Y ( x , y )) , where i X i_X i X and i Y i_Y i Y are the inclusions of X X X and Y Y Y into X + Y X+Y X + Y , respectively. We extend this notation to equations with parameters. That is, given parameters p : X p:X p : X and q : Y q:Y q : Y , we write s ( p ) = t ( q ) s(p)=t(q) s ( p ) = t ( q ) for the parametrised formula ( s ( x ) = t ( y ) , p , q ) (s(x)=t(y),p,q) ( s ( x ) = t ( y ) , p , q ) .
Proposition 6.5. Let L \mathbb{L} L be a language on V \mathcal{V} V , let P = { p : X , q : Y } \mathcal{P}=\{p:X,q:Y\} P = { p : X , q : Y } be a set of parameters, and let ( A , p A , q A ) (A,p^A,q^A) ( A , p A , q A ) be an ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structure. For any L \mathbb{L} L -terms s : ( X , Z ) s:(X,Z) s : ( X , Z ) and t : ( Y , Z ) t:(Y,Z) t : ( Y , Z ) we have that A ⊨ s ( p ) = t ( q ) A\models s(p)=t(q) A ⊨ s ( p ) = t ( q ) if the square below commutes.
I → ( p A ) t A X ( q A ) t ↓ ↓ s A A Y → t A A Z \begin{CD}
I @>{(p^A)t}>> A^X\\
@V{(q^A)t}VV @VV{s_A}V\\
A^Y @>{t_A}>> A^Z
\end{CD} I ( q A ) t ↓ ⏐ A Y ( p A ) t t A A X ↓ ⏐ s A A Z
The converse holds if ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is proper.
Proof. The interpretation of the term i X i_X i X in A A A is the projection A i X : A X + Y → A X A^{i_X}:A^{X+Y}\to A^X A i X : A X + Y → A X , and similar for i Y i_Y i Y and A i Y A^{i_Y} A i Y . So the interpretation of the formula s ( x ) = t ( y ) s(x)=t(y) s ( x ) = t ( y ) in A A A is the ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) -factorisation of the equaliser E E E of s A A i X s_AA^{i_X} s A A i X and t A A i Y t_AA^{i_Y} t A A i Y , as pictured in the diagram below.
E → e ( s ( x ) = t ( y ) ) ( A ) → m A X + Y ⇉ s A A i X t A A i Y A Z E\xrightarrow{e}(s(x)=t(y))(A)\xrightarrow{m}A^{X+Y}\underset{t_AA^{i_Y}}{\overset{s_AA^{i_X}}{\rightrightarrows}}A^Z E e ( s ( x ) = t ( y )) ( A ) m A X + Y t A A i Y ⇉ s A A i X A Z
Write r : = ( p A + q A ) t : I → A X + Y r := (p^{A} + q^{A})^{t} : I \to A^{X+Y} r := ( p A + q A ) t : I → A X + Y . If the square in the statement commutes then s A A i X r = t A A i Y r s_{A}A^{i_{X}}r = t_{A}A^{i_{Y}}r s A A i X r = t A A i Y r . So there is an induced arrow I → E I \to E I → E , which shows that r r r factors through ( s ( x ) = t ( y ) ) ( A ) (s(x) = t(y))(A) ( s ( x ) = t ( y )) ( A ) . That is, A ⊨ s ( p ) = t ( q ) A \models s(p) = t(q) A ⊨ s ( p ) = t ( q ) , as required.
For the converse we assume that ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is proper. So E \mathcal{E} E is contained in the epimorphisms, hence M \mathcal{M} M contains all regular monomorphisms by Theorem 2.2. Then e e e is an isomorphism and ( s ( x ) = t ( y ) ) ( A ) (s(x) = t(y))(A) ( s ( x ) = t ( y )) ( A ) is already the equaliser. If A ⊨ s ( p ) = t ( q ) A \models s(p) = t(q) A ⊨ s ( p ) = t ( q ) then r r r factors through ( s ( x ) = t ( y ) ) ( A ) (s(x) = t(y))(A) ( s ( x ) = t ( y )) ( A ) , say, as m f mf m f for some f : I → ( s ( x ) = t ( y ) ) ( A ) f : I \to(s(x) = t(y))(A) f : I → ( s ( x ) = t ( y )) ( A ) . We compute
s A ( p A ) t = s A A i X r = s A A i X m f = t A A i Y m f = t A A i Y r = t A ( q A ) t , s_{A}(p^{A})^{t} = s_{A}A^{i_{X}}r = s_{A}A^{i_{X}}mf = t_{A}A^{i_{Y}}mf = t_{A}A^{i_{Y}}r = t_{A}(q^{A})^{t}, s A ( p A ) t = s A A i X r = s A A i X m f = t A A i Y m f = t A A i Y r = t A ( q A ) t ,
as required.
Corollary 6.6. Let L \mathbb{L} L be a language on V \mathcal{V} V , let P = { p : X , q : Y } \mathcal{P} = \{p : X, q : Y\} P = { p : X , q : Y } be a set of parameters, and let ( A , p A , q A ) (A,p^{A},q^{A}) ( A , p A , q A ) be an ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structure. For any arrow s : Y → X s : Y \to X s : Y → X in V \mathcal{V} V we have that A ⊨ s ( p ) = q A \models s(p) = q A ⊨ s ( p ) = q if p A ∘ s = q A p^{A} \circ s = q^{A} p A ∘ s = q A .
The converse holds if ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is proper.
Proof. By definition, s s s is an ( X , Y ) (X,Y) ( X , Y ) -ary term. So we apply Theorem 6.5 with t = id Y t = \operatorname{id}_{Y} t = id Y . Commutativity of the square in Theorem 6.5 then becomes ( q A ) t = s A ∘ ( p A ) t (q^{A})^{t} = s_{A} \circ(p^{A})^{t} ( q A ) t = s A ∘ ( p A ) t . In this case, s A = A s : A X → A Y s_{A} = A^{s} : A^{X} \to A^{Y} s A = A s : A X → A Y , and so the transpose of s A ∘ ( p A ) t s_{A} \circ(p^{A})^{t} s A ∘ ( p A ) t is p A ∘ s p^{A} \circ s p A ∘ s . So, by taking transposes, commutativity of the square is equivalent to p A ∘ s = q A p^{A} \circ s = q^{A} p A ∘ s = q A .
We now establish the correspondence between homomorphisms of L \mathbb{L} L -structures with domain A A A and models of Diag ( A ) \operatorname{Diag}(A) Diag ( A ) , which we will phrase in terms of an isomorphism of categories.
Lemma 6.7. Let L \mathbb{L} L be a language on V \mathcal{V} V and let A A A be an L \mathbb{L} L -structure. There is a faithful functor
A / Str ( L ) 0 ⟶ Mod ( Diag ( A ) ) , A/\operatorname{Str}(\mathbb{L})_{0} \longrightarrow\operatorname{Mod}(\operatorname{Diag}(A)), A / Str ( L ) 0 ⟶ Mod ( Diag ( A )) , h : A → B ⟼ ( B , ( h ∘ a ) a ∈ P ( A ) ) , h : A \to B \longmapsto(B,(h \circ a)_{a \in\mathcal{P}(A)}), h : A → B ⟼ ( B , ( h ∘ a ) a ∈ P ( A ) ) , which is the identity on arrows. Furthermore, if V f p \mathcal{V}_{\mathrm{fp}} V fp is a generator of V 0 \mathcal{V}_{0} V 0 then this functor is also full and injective on objects.
Proof. Let h : A → B h : A \to B h : A → B be an object in A / Str ( L ) 0 A/\operatorname{Str}(\mathbb{L})_{0} A / Str ( L ) 0 . First we show that ( B , ( h ∘ a ) a ∈ P ( A ) ) (B,(h \circ a)_{a \in\mathcal{P}(A)}) ( B , ( h ∘ a ) a ∈ P ( A ) ) is a model of Diag ( A ) \operatorname{Diag}(A) Diag ( A ) . Let φ ( p a 1 , … , p a n ) ∈ Diag ( A ) \varphi(p_{a_{1}},\ldots,p_{a_{n}}) \in\operatorname{Diag}(A) φ ( p a 1 , … , p a n ) ∈ Diag ( A ) . Then the fact that A ⊨ φ ( p a 1 , … , p a n ) A \models\varphi(p_{a_{1}},\ldots,p_{a_{n}}) A ⊨ φ ( p a 1 , … , p a n ) means that the dashed arrow below exists.
I → ( a 1 + ⋯ + a n ) t A X 1 + ⋯ + X n ↓ h X 1 + ⋯ + X n φ ( A ) → φ ( h ) φ ( B ) \begin{CD}
I @>{(a_{1}+\cdots+a_{n})^{t}}>> A^{X_{1}+\cdots+X_{n}} \\
@. @VV{h^{X_{1}+\cdots+X_{n}}}V \\
\varphi(A) @>{\varphi(h)}>> \varphi(B)
\end{CD} I φ ( A ) ( a 1 + ⋯ + a n ) t φ ( h ) A X 1 + ⋯ + X n ↓ ⏐ h X 1 + ⋯ + X n φ ( B )
Since h X ( a 1 + ⋯ + a n ) t = ( h ∘ ( a 1 + ⋯ + a n ) ) t h^{X}(a_{1}+\cdots+a_{n})^{t} = (h \circ(a_{1}+\cdots+a_{n}))^{t} h X ( a 1 + ⋯ + a n ) t = ( h ∘ ( a 1 + ⋯ + a n ) ) t , and this factors through φ ( B ) \varphi(B) φ ( B ) , it follows that also B ⊨ φ ( p a 1 , … , p a n ) B \models\varphi(p_{a_{1}},\ldots,p_{a_{n}}) B ⊨ φ ( p a 1 , … , p a n ) .
Let now h : A → B h : A \to B h : A → B and h ′ : A → B ′ h' : A \to B' h ′ : A → B ′ be objects in A / Str ( L ) 0 A/\operatorname{Str}(\mathbb{L})_{0} A / Str ( L ) 0 , and let g : B → B ′ g : B \to B' g : B → B ′ be an arrow in A / Str ( L ) 0 A/\operatorname{Str}(\mathbb{L})_{0} A / Str ( L ) 0 . That is, g ∘ h = h ′ g \circ h = h' g ∘ h = h ′ . Then g g g is by definition already an arrow in Str ( L ) 0 \operatorname{Str}(\mathbb{L})_{0} Str ( L ) 0 , that is, it an L \mathbb{L} L -homomorphism. Furthermore, for any p a ∈ P ( A ) p_{a} \in\mathcal{P}(A) p a ∈ P ( A ) we have
g ∘ ( h ∘ a ) = h ′ ∘ a , g \circ(h \circ a) = h' \circ a, g ∘ ( h ∘ a ) = h ′ ∘ a ,
so g g g is a morphism of ( L , P ( A ) ) (\mathbb{L},\mathcal{P}(A)) ( L , P ( A )) -structures. We conclude that the functor is indeed well-defined, and since it is the identity on arrows, it is faithful.
Assume now that V f p \mathcal{V}_{\mathrm{fp}} V fp is a generator of V 0 \mathcal{V}_{0} V 0 . We first show that the functor is full. Let h h h and h ′ h' h ′ be as above, and let g : ( B , ( h ∘ a ) a ∈ P ( A ) ) → ( B ′ , ( h ′ ∘ a ) a ∈ P ( A ) ) g : (B,(h \circ a)_{a \in\mathcal{P}(A)}) \to(B',(h' \circ a)_{a \in\mathcal{P}(A)}) g : ( B , ( h ∘ a ) a ∈ P ( A ) ) → ( B ′ , ( h ′ ∘ a ) a ∈ P ( A ) ) be any arrow in Mod ( Diag ( A ) ) \operatorname{Mod}(\operatorname{Diag}(A)) Mod ( Diag ( A )) . Then g g g is a morphism of ( L , P ( A ) ) (\mathbb{L},\mathcal{P}(A)) ( L , P ( A )) -structures. So for any a : X → A a : X \to A a : X → A in V \mathcal{V} V with X X X in V f p \mathcal{V}_{\mathrm{fp}} V fp we have
g ∘ h ∘ a = h ′ ∘ a . g \circ h \circ a = h' \circ a. g ∘ h ∘ a = h ′ ∘ a .
Using that V f p \mathcal{V}_{\mathrm{fp}} V fp is a generator, it follows that g ∘ h = h ′ g \circ h = h' g ∘ h = h ′ . As g g g is in particular an L \mathbb{L} L -homomorphism, we conclude that it is an arrow h → h ′ h \to h' h → h ′ in A / Str ( L ) 0 A/\operatorname{Str}(\mathbb{L})_{0} A / Str ( L ) 0 . Finally we show that the functor is injective on objects. Once again, we let h h h and h ′ h' h ′ be as above, and now we assume that ( B , ( h ∘ a ) p a ∈ P ( A ) ) = ( B ′ , ( h ′ ∘ a ) p a ∈ P ( A ) ) (B,(h\circ a)_{p_a\in\mathcal{P}(A)})=(B',(h'\circ a)_{p_a\in\mathcal{P}(A)}) ( B , ( h ∘ a ) p a ∈ P ( A ) ) = ( B ′ , ( h ′ ∘ a ) p a ∈ P ( A ) ) . Then B = B ′ B=B' B = B ′ as L \mathcal{L} L -structures and h ∘ a = h ′ ∘ a h\circ a=h'\circ a h ∘ a = h ′ ∘ a for any a : X → A a:X\to A a : X → A in V \mathcal{V} V with X X X in V f p \mathcal{V}_{\mathrm{fp}} V fp . Since V f p \mathcal{V}_{\mathrm{fp}} V fp is a generator of V 0 \mathcal{V}_0 V 0 , it follows that h = h ′ h=h' h = h ′ .
Theorem 1.4 (Enriched model-theoretic method of diagrams), repeated. Assume that V 0 \mathcal{V}_0 V 0 is locally finitely presentable with its finitely presentable objects closed under the monoidal product and that ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is proper. Let L \mathcal{L} L be a language on V \mathcal{V} V and let A A A be an L \mathcal{L} L -structure. Then the functor
A / Str ( L ) 0 ⟶ Mod ( Diag ( A ) ) , A/\operatorname{Str}(\mathcal{L})_0 \longrightarrow\operatorname{Mod}(\operatorname{Diag}(A)), A / Str ( L ) 0 ⟶ Mod ( Diag ( A )) , h : A ⟶ B ⟼ ( B , ( h ∘ a ) p a ∈ P ( A ) ) , h:A\longrightarrow B \longmapsto(B,(h\circ a)_{p_a\in\mathcal{P}(A)}), h : A ⟶ B ⟼ ( B , ( h ∘ a ) p a ∈ P ( A ) ) , which is the identity on arrows, is an isomorphism of categories.
By Theorem 3.4 the above theorem applies in particular to those V \mathcal{V} V that are reduced product ready and where V 0 \mathcal{V}_0 V 0 is locally finitely presentable (and ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is proper).
Proof. In a locally finitely presentable category V 0 \mathcal{V}_0 V 0 , the finitely presentable objects V f p \mathcal{V}_{\mathrm{fp}} V fp always form a generator. So by Theorem 6.7 it only remains to show that the functor is surjective on objects, which amounts to constructing its inverse. Let ( B , ( p a B ) p a ∈ P ( A ) ) (B,(p_a^B)_{p_a\in\mathcal{P}(A)}) ( B , ( p a B ) p a ∈ P ( A ) ) be any model of Diag ( A ) \operatorname{Diag}(A) Diag ( A ) . We first construct an L \mathcal{L} L -homomorphism h : A → B h:A\to B h : A → B . Since V 0 \mathcal{V}_0 V 0 is locally finitely presentable we can write
A ≅ colim ( V f p / A → π V 0 ) A\cong\operatorname{colim}(\mathcal{V}_{\mathrm{fp}}/A\xrightarrow{\pi}\mathcal{V}_0) A ≅ colim ( V fp / A π V 0 )
taken along the canonical diagram on the slice V f p / A \mathcal{V}_{\mathrm{fp}}/A V fp / A . Now, for any t : Y → X t:Y\to X t : Y → X in V f p \mathcal{V}_{\mathrm{fp}} V fp we have by Theorem 6.6 that
A ⊨ t ( p a ) = p a ∘ t . A\models t(p_a)=p_a\circ t. A ⊨ t ( p a ) = p a ∘ t .
Since ( B , ( p a B ) p a ∈ P ( A ) ) (B,(p_a^B)_{p_a\in\mathcal{P}(A)}) ( B , ( p a B ) p a ∈ P ( A ) ) is a model of Diag ( A ) \operatorname{Diag}(A) Diag ( A ) , we also know that B ⊨ t ( p a ) = p a ∘ t B\models t(p_a)=p_a\circ t B ⊨ t ( p a ) = p a ∘ t , which by Theorem 6.6 again means exactly that the triangle
X → t Y p a ∘ t B ↓ ↓ p a B B = B \begin{CD}
X @>{t}>> Y \\
@V{p_{a\circ t}^{B}}VV @VV{p_a^{B}}V \\
B @= B
\end{CD} X p a ∘ t B ↓ ⏐ B t Y ↓ ⏐ p a B B
commutes. In other words, the family ( p a B ) a ∈ V f p / A (p_a^B)_{a\in\mathcal{V}_{\mathrm{fp}}/A} ( p a B ) a ∈ V fp / A defines a cocone over the diagram π : V f p / A → V 0 \pi:\mathcal{V}_{\mathrm{fp}}/A\to\mathcal{V}_0 π : V fp / A → V 0 . Thus there exists a unique arrow h : A → B h:A\to B h : A → B in V \mathcal{V} V such that h ∘ a = p a B h\circ a=p_a^B h ∘ a = p a B for all a ∈ V f p / A a\in\mathcal{V}_{\mathrm{fp}}/A a ∈ V fp / A . We are left to show that h h h preserves the interpretation of function and relation symbols. It then follows immediately that the functor sends h h h to ( B , ( p a B ) p a ∈ P ( A ) ) (B,(p_a^B)_{p_a\in\mathcal{P}(A)}) ( B , ( p a B ) p a ∈ P ( A ) ) .
Before proceeding, we fix some notation. Let b : Z → A X b:Z\to A^X b : Z → A X be any arrow in V \mathcal{V} V with X X X and Z Z Z finitely presentable. Then the transpose b t : X ⊗ Z → A b^t:X\otimes Z\to A b t : X ⊗ Z → A has finitely presentable domain, and so there is a parameter p b t : X ⊗ Z p_{b^t}:X\otimes Z p b t : X ⊗ Z in P ( A ) \mathcal{P}(A) P ( A ) . The equality h ∘ b t = p b t B h\circ b^t=p_{b^t}^B h ∘ b t = p b t B then translates to commutativity of the triangle below
Z → b A X q b ↓ ↓ h X B X = B X \begin{CD}
Z @>{b}>> A^X \\
@V{q_b}VV @VV{h^X}V \\
B^X @= B^X
\end{CD} Z q b ↓ ⏐ B X b A X ↓ ⏐ h X B X
where we define q b : = ( p b t B ) t q_b:=(p_{b^t}^B)^t q b := ( p b t B ) t .
Let now f : ( X , Y ) f:(X,Y) f : ( X , Y ) be an arbitrary function symbol in L \mathcal{L} L and let b : Z → A X b:Z\to A^X b : Z → A X be any arrow in V \mathcal{V} V with Z Z Z finitely presentable. Consider the diagram below, where we wish to prove that the central square commutes.
→ a b b ↓ h X ↑ → h X f A ↓ f B ↓ → h Y \begin{CD}
& Z @>{a_b}>> B^X \\
@V{b}VV @A{h^X}AA \\
A^X @>{h^X}>> B^X \\
@V{f_A}VV @V{f_B}VV \\
A^Y @>{h^Y}>> B^Y
\end{CD} a b h X h Y b ↓ ⏐ f A ↓ ⏐ h X ⏐ ↑ f B ↓ ⏐
The triangles with vertex Z Z Z and bases h X h^X h X and h Y h^Y h Y commute by the arguments above. The triangle with base f A f_A f A commutes by definition and so by Theorem 6.5:
A ⊨ f Z ( p b t ) = p ( f A ∘ b ) t . A \models f^Z(p_b^t)=p_{(f_A\circ b)^t}. A ⊨ f Z ( p b t ) = p ( f A ∘ b ) t .
It follows that B B B satisfies the same formula with parameters, which means that the triangle with base f B f_B f B also commutes (Theorem 6.5). In conclusion, the equality
f B ∘ h X ∘ b = h Y ∘ f A ∘ b f_B\circ h^X\circ b=h^Y\circ f_A\circ b f B ∘ h X ∘ b = h Y ∘ f A ∘ b
holds. Since this is the case for any arrow b b b with domain in the generator V f p \mathcal{V}_{\mathrm{fp}} V fp , we obtain that h h h preserves the interpretation of f f f .
Finally, let R : X R:X R : X be an arbitrary relation symbol in L \mathbb{L} L , and let r A : R A ↣ A X r_A:R_A\rightarrowtail A^X r A : R A ↣ A X and r B : R B ↣ B X r_B:R_B\rightarrowtail B^X r B : R B ↣ B X be its interpretations in A A A and B B B , respectively. Let { b j : Z j → R A } j ∈ J \{b_j:Z_j\to R_A\}_{j\in J} { b j : Z j → R A } j ∈ J be the set of all arrows in V \mathcal{V} V with codomain R A R_A R A and finitely presentable domain. For each j ∈ J j\in J j ∈ J we write a j : = r A b j : Z j → A X a_j:=r_A b_j:Z_j\to A^X a j := r A b j : Z j → A X with transpose a j t : X ⊗ Z j → A a_j^t:X\otimes Z_j\to A a j t : X ⊗ Z j → A . Then by definition A ⊨ R Z j ( p a j t ) A\models R^{Z_j}(p_{a_j}^t) A ⊨ R Z j ( p a j t ) ; thus also B ⊨ R Z j ( p a j t ) B\models R^{Z_j}(p_{a_j}^t) B ⊨ R Z j ( p a j t ) , meaning that ( p a j t ) t = h X ∘ a j (p_{a_j}^t)^t=h^X\circ a_j ( p a j t ) t = h X ∘ a j factors as r B ∘ c j r_B\circ c_j r B ∘ c j for some c j : Z j → R B c_j:Z_j\to R_B c j : Z j → R B . We thus obtain the solid part of the commutative diagram below.
∐ j ∈ J Z j → c : = ∑ j ∈ J c j R B b : = ∑ j ∈ J b j ↓ ↓ r B R A → r A A X → h X B X \begin{CD}
\coprod_{j\in J}Z_j @>{c:=\sum_{j\in J}c_j}>> R_B \\
@V{b:=\sum_{j\in J}b_j}VV @VV{r_B}V \\
R_A @>{r_A}>> A^X @>{h^X}>> B^X
\end{CD} j ∈ J ∐ Z j b := ∑ j ∈ J b j ↓ ⏐ R A c := ∑ j ∈ J c j r A R B ↓ ⏐ r B A X h X B X
The arrow b b b is then in E \mathcal{E} E because V f p \mathcal{V}_{\mathrm{fp}} V fp is an E \mathcal{E} E -generator by Theorem 2.6. By definition r B r_B r B is in M \mathcal{M} M , so by orthogonality the dashed arrow R A → R B R_A\to R_B R A → R B exists, making everything commute. It follows that h h h preserves the interpretation of R R R and is an L \mathbb{L} L -homomorphism, as required.
If we take L \mathbb{L} L to be the empty language then a model of Diag ( A ) \operatorname{Diag}(A) Diag ( A ) is essentially just a cocone for the canonical diagram of A A A . The model-theoretic method of diagrams then just says that, in a locally finitely presentable category V 0 \mathcal{V}_0 V 0 , arrows h : A → B h:A\to B h : A → B correspond to cocones for the canonical diagram of A A A . Although this is nothing new, it is useful that this can be expressed syntactically, so we introduce some notation and terminology for it.
Definition 6.8. The bare diagram BareDiag ( A ) \operatorname{BareDiag}(A) BareDiag ( A ) of an object A A A is Diag ( A ) \operatorname{Diag}(A) Diag ( A ) , where A A A is considered as a structure in the empty language.
Corollary 6.9. For any object A A A of V \mathcal{V} V there is a faithful functor
A / V 0 ⟶ Mod ( BareDiag ( A ) ) , \mathcal{A}/\mathcal{V}_0 \longrightarrow\operatorname{Mod}(\operatorname{BareDiag}(A)), A / V 0 ⟶ Mod ( BareDiag ( A )) , h : A → B ⟼ ( B , ( h ∘ a ) p a ∈ P ( A ) ) , h:A\to B \longmapsto(B,(h\circ a)_{p_a\in P(A)}), h : A → B ⟼ ( B , ( h ∘ a ) p a ∈ P ( A ) ) , which is the identity on arrows.
Furthermore, if V 0 \mathcal{V}_0 V 0 is locally finitely presentable and ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is proper then this functor is an isomorphism of categories.
Note that the above does not require closure of V f p \mathcal{V}_{\mathrm{fp}} V fp under the monoidal product, because that was only used in Theorem 1.4 to prove that h h h is an L \mathbb{L} L -homomorphism.
The semicartesian case
In this section we focus on the case where V \mathcal{V} V is semicartesian; that is, when the unit I I I is the terminal object of V \mathcal{V} V . This is necessary to obtain an extension of Theorem 1.4 where the isomorphism is actually an enriched isomorphism. We further assume that the unit is finitely presentable so that it can be used as an arity of our logic.
The reason why the unit needs to be the terminal object is twofold. On one hand, it allows us to see parameters as function symbols (with input arity 0) of an enriched language, so that structures naturally assemble into a V \mathcal{V} V -category. On the other hand, enriched slice categories are better behaved in the semicartesian case, as the underlying category of an enriched slice is the ordinary slice on the underlying category.
Let us focus first on parameters and interpretations. In this case, to specify a parameter p : X p\colon X p : X is the same as specifying a function symbol c p : ( 0 , X ) c_p\colon(0,X) c p : ( 0 , X ) , that is, a constant symbol. Indeed, the interpretation of such a function symbol in a structure A A A is given by an arrow
( c p ) A : 1 ≅ A 0 ⟶ A X (c_p)_A\colon1 \cong A^0 \longrightarrow A^X ( c p ) A : 1 ≅ A 0 ⟶ A X
which, by monoidal closedness, corresponds to an arrow p A : X ≅ 1 ⊗ X ⟶ A p^A\colon X \cong1\otimes X \longrightarrow A p A : X ≅ 1 ⊗ X ⟶ A in V \mathcal{V} V .
Definition 6.10. Given a set P \mathcal{P} P of parameters (with finitely presentable domains) and a language L \mathbb{L} L , we form a new language L P \mathbb{L}_{\mathcal{P}} L P by extending L \mathbb{L} L with a new constant symbol c p : ( 0 , X ) c_p\colon(0,X) c p : ( 0 , X ) for each p ∈ P p\in\mathcal{P} p ∈ P .
The correspondence between the interpretations of a parameter p p p and a constant c p c_p c p tells us how to view an ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structure as an L P \mathbb{L}_{\mathcal{P}} L P -structure, and vice versa. In particular, it follows that Str ( L , P ) \operatorname{Str}(\mathbb{L},\mathcal{P}) Str ( L , P ) and Str ( L P ) 0 \operatorname{Str}(\mathbb{L}_{\mathcal{P}})_0 Str ( L P ) 0 are isomorphic.
A parametrised formula φ ( p 1 , … , p n ) \varphi(p_1,\ldots,p_n) φ ( p 1 , … , p n ) corresponds to the L P \mathbb{L}_{\mathcal{P}} L P -formula φ ( c p 1 , … , c p n ) \varphi(c_{p_1},\ldots,c_{p_n}) φ ( c p 1 , … , c p n ) . Indeed, the function symbols c p 1 : ( 0 , X 1 ) , … , c p n : ( 0 , X n ) c_{p_1}\colon(0,X_1),\ldots,c_{p_n}\colon(0,X_n) c p 1 : ( 0 , X 1 ) , … , c p n : ( 0 , X n ) induce a ( 0 , X 1 + … + X n ) (0,X_1+\ldots+X_n) ( 0 , X 1 + … + X n ) -ary term ( c p 1 , … , c p n ) (c_{p_1},\ldots,c_{p_n}) ( c p 1 , … , c p n ) , since the n n n -fold sum of 0 is still 0. Then this term can be substituted for the free variables in φ \varphi φ as in Theorem 2.20. The semantics for these two formulas agree, as is made precise below.
Proposition 6.11. Let A A A be an ( L , P ) (\mathbb{L},\mathcal{P}) ( L , P ) -structure, simultaneously viewed as an L P \mathbb{L}_{\mathcal{P}} L P -structure. Then
A ⊨ φ ( p 1 , … , p n ) ⟺ A ⊨ φ ( c p 1 , … , c p n ) , A \models\varphi(p_1,\ldots,p_n) \quad\Longleftrightarrow\quad A \models\varphi(c_{p_1},\ldots,c_{p_n}), A ⊨ φ ( p 1 , … , p n ) ⟺ A ⊨ φ ( c p 1 , … , c p n ) ,
provided that we satisfy the necessary assumptions for φ \varphi φ from Theorem 2.20.
Since the diagram of a structure only contains atomic formulas, the necessary (for us) assumptions from Theorem 2.20 are satisfied by assuming that ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is proper, which we need anyway.
Proof. Consider the pullback below given by Theorem 2.20.
φ ( c p 1 , … , c p n ) ( A ) → m A 0 ≅ 1 ↓ ↓ ( c p 1 , … , c p n ) A = ( p 1 A + … + p n A ) t φ ( A ) → A X 1 + … + X n \begin{CD}
\varphi(c_{p_1},\ldots,c_{p_n})(A) @>m>> A^0 \cong1 \\
@VVV @VV(c_{p_1},\ldots,c_{p_n})_A=(p^A_1+\ldots+p^A_n)^t V \\
\varphi(A) @>>> A^{X_1+\ldots+X_n}
\end{CD} φ ( c p 1 , … , c p n ) ( A ) ↓ ⏐ φ ( A ) m A 0 ≅ 1 ↓ ⏐ ( c p 1 , … , c p n ) A = ( p 1 A + … + p n A ) t A X 1 + … + X n
Then A ⊨ φ ( p 1 , … , p n ) A\models\varphi(p_1,\ldots,p_n) A ⊨ φ ( p 1 , … , p n ) if and only if the arrow ( p 1 A + … + p n A ) t (p^A_1+\ldots+p^A_n)^t ( p 1 A + … + p n A ) t factors through the inclusion of φ ( A ) \varphi(A) φ ( A ) , if and only if there exists r : 1 → φ ( c p 1 , … , c p n ) ( A ) r\colon1\to\varphi(c_{p_1},\ldots,c_{p_n})(A) r : 1 → φ ( c p 1 , … , c p n ) ( A ) such that m r = 1 mr=1 m r = 1 , if and only if m m m is an isomorphism (since it is both in M \mathcal{M} M and a split epimorphism), if and only if A ⊨ φ ( c p 1 , … , c p n ) A\models\varphi(c_{p_1},\ldots,c_{p_n}) A ⊨ φ ( c p 1 , … , c p n ) . □
It follows that we can view Mod ( Diag ( A ) ) \operatorname{Mod}(\operatorname{Diag}(A)) Mod ( Diag ( A )) as a V \mathcal{V} V -category of models of an L P ( A ) \mathbb{L}_{\mathcal{P}(A)} L P ( A ) -theory, for which we introduce some notation.
Definition 6.12. Let A A A be an L \mathbb{L} L -structure. We write L ( A ) \mathbb{L}(A) L ( A ) for the language that we called L P ( A ) \mathbb{L}_{\mathcal{P}(A)} L P ( A ) above. Through the translation discussed above, we view Diag ( A ) \operatorname{Diag}(A) Diag ( A ) as an L ( A ) \mathbb{L}(A) L ( A ) -theory.
As mentioned in the introduction to this section, slice categories also make sense in the enriched sense. Indeed A / Str ( L ) A/\operatorname{Str}(\mathbb{L}) A / Str ( L ) can be viewed as a comma object in the 2-category V \mathcal{V} V -CAT (which is complete). Explicitly, the objects of A / Str ( L ) A/\operatorname{Str}(\mathbb{L}) A / Str ( L ) are arrows h : A → B h\colon A\to B h : A → B in Str ( L ) \operatorname{Str}(\mathbb{L}) Str ( L ) , as in the ordinary case, and the hom-objects are defined by the pullback below in V \mathcal{V} V .
A / Str ( L ) ( h , h ′ ) → Str ( L ) ( B , B ′ ) ↓ ↓ − ∘ h 1 → h ′ Str ( L ) ( A , B ′ ) \begin{CD}
A/\operatorname{Str}(\mathcal L)(h,h') @>>> \operatorname{Str}(\mathcal L)(B,B') \\
@VVV @VV{-\circ h}V \\
1 @>{h'}>> \operatorname{Str}(\mathcal L)(A,B')
\end{CD} A / Str ( L ) ( h , h ′ ) ↓ ⏐ 1 h ′ Str ( L ) ( B , B ′ ) ↓ ⏐ −∘ h Str ( L ) ( A , B ′ )
Since the same pullback in Set applied to Str ( L ) 0 \operatorname{Str}(\mathcal L)_0 Str ( L ) 0 defines the homsets of A / Str ( L ) 0 A/\operatorname{Str}(\mathcal L)_0 A / Str ( L ) 0 , it follows immediately that ( A / Str ( L ) ) 0 ≅ A / Str ( L ) 0 (A/\operatorname{Str}(\mathcal L))_0 \cong A/\operatorname{Str}(\mathcal L)_0 ( A / Str ( L ) ) 0 ≅ A / Str ( L ) 0 .
Remark 6.13. Note that the construction above still makes sense when V \mathcal V V is not semicartesian, one just has to replace 1 1 1 with I I I in the pullback above. However, in this case it is not true any more that ( A / Str ( L ) ) 0 (A/\operatorname{Str}(\mathcal L))_0 ( A / Str ( L ) ) 0 is isomorphic to A / Str ( L ) 0 A/\operatorname{Str}(\mathcal L)_0 A / Str ( L ) 0 , since the left vertical above now carries non-trivial information.
Since comma objects are examples of flexible 2 2 2 -limits and Str ( L ) \operatorname{Str}(\mathcal L) Str ( L ) is locally presentable (as a V \mathcal V V -category), by [22 Corollary 5.8] also A / Str ( L ) A/\operatorname{Str}(\mathcal L) A / Str ( L ) is locally presentable and the forgetful V \mathcal V V -functor U : A / Str ( L ) → Str ( L ) U:A/\operatorname{Str}(\mathcal L)\to\operatorname{Str}(\mathcal L) U : A / Str ( L ) → Str ( L ) is continuous and directed-colimit preserving. If V \mathcal V V is locally finitely presentable as a closed category, then Str ( L ) \operatorname{Str}(\mathcal L) Str ( L ) and A / Str ( L ) A/\operatorname{Str}(\mathcal L) A / Str ( L ) are actually locally finitely presentable.
We are now ready to prove that in this case the ordinary functor from Theorem 6.7 extends to one of V \mathcal V V -categories. Recall that a V \mathcal V V -functor is called faithful if the action on hom-objects is a monomorphism in V \mathcal V V .
Lemma 6.14. Assume that V \mathcal V V is semicartesian, the monoidal unit is finitely presentable, and ( E , M ) (\mathcal E,\mathcal M) ( E , M ) is proper. The functor from Theorem 6.7 extends uniquely to a V \mathcal V V -functor
A / Str ( L ) ⟶ Mod ( Diag ( A ) ) , A/\operatorname{Str}(\mathcal L)\longrightarrow\operatorname{Mod}(\operatorname{Diag}(A)), A / Str ( L ) ⟶ Mod ( Diag ( A )) , h : A ⟶ B ⟼ ( B , ( h ∘ a ) p a ∈ P ( A ) ) , h:A\longrightarrow B\longmapsto\left(B,(h\circ a)_{p_a\in P(A)}\right), h : A ⟶ B ⟼ ( B , ( h ∘ a ) p a ∈ P ( A ) ) , which is faithful and preserves powers. Moreover, if V f p \mathcal V_{\mathrm{fp}} V fp is a generator of V 0 \mathcal V_0 V 0 this is also injective on objects and fully faithful as a V \mathcal V V -functor.
Proof. To begin with, notice that Mod ( Diag ( A ) ) \operatorname{Mod}(\operatorname{Diag}(A)) Mod ( Diag ( A )) is closed in Str ( L ( A ) ) \operatorname{Str}(\mathcal L(A)) Str ( L ( A )) under powers (since ( E , M ) (\mathcal E,\mathcal M) ( E , M ) is proper the validity of regular atomic formulas is stable under powers), and the forgetful V \mathcal V V -functor Str ( L ( A ) ) → Str ( L ) \operatorname{Str}(\mathcal L(A))\to\operatorname{Str}(\mathcal L) Str ( L ( A )) → Str ( L ) preserves powers since they are computed as in V \mathcal V V in both V \mathcal V V -categories (see [35 Theorem 3.9] ).
Consider now the ordinary functor
F ~ : A / Str ( L ) 0 ⟶ Mod ( Diag ( A ) ) 0 \widetilde F:A/\operatorname{Str}(\mathcal L)_0\longrightarrow\operatorname{Mod}(\operatorname{Diag}(A))_0 F : A / Str ( L ) 0 ⟶ Mod ( Diag ( A ) ) 0
defined by Theorem 6.7 . By definition of F ~ \widetilde F F and since powers in both V \mathcal V V -categories are constructed as in Str ( L ) \operatorname{Str}(\mathcal L) Str ( L ) it follows that F ~ \widetilde F F preserves the action of taking powers ; meaning that
F ~ ( h X ) ≅ F ~ ( h ) X \widetilde F(h^X)\cong\widetilde F(h)^X F ( h X ) ≅ F ( h ) X
naturally in h ∈ A / Str ( L ) 0 h\in A/\operatorname{Str}(\mathcal L)_0 h ∈ A / Str ( L ) 0 and X ∈ V X\in\mathcal V X ∈ V (we cannot ask that F ~ \widetilde F F actually preserves powers, as it is not a V \mathcal V V -functor).
By the dual of results in the Appendix of [14 ] (see also [20 9.2] ), it follows that F ~ = F 0 \widetilde F=F_0 F = F 0 for a unique power-preserving V \mathcal V V -functor F : A / Str ( L ) → Mod ( Diag ( A ) ) F:A/\operatorname{Str}(\mathcal L)\to\operatorname{Mod}(\operatorname{Diag}(A)) F : A / Str ( L ) → Mod ( Diag ( A )) . The idea behind this argument is that, since F ~ \widetilde F F preserves the action of taking powers, then the composite
V 0 ( X , A / Str ( L ) ( h , k ) ) ≅ A / Str ( L ) 0 ( h , k X ) → F ~ h , k X Mod ( Diag ( A ) ) 0 ( F ~ ( h ) , F ~ ( k X ) ) \mathcal V_0(X,A/\operatorname{Str}(\mathcal L)(h,k))\cong A/\operatorname{Str}(\mathcal L)_0(h,k^X)\xrightarrow{\widetilde F_{h,k^X}}\operatorname{Mod}(\operatorname{Diag}(A))_0(\widetilde F(h),\widetilde F(k^X)) V 0 ( X , A / Str ( L ) ( h , k )) ≅ A / Str ( L ) 0 ( h , k X ) F h , k X Mod ( Diag ( A ) ) 0 ( F ( h ) , F ( k X ))
≅ Mod ( Diag ( A ) ) 0 ( F ~ ( h ) , F ~ ( k ) X ) ≅ V 0 ( X , Mod ( Diag ( A ) ) ( F ~ ( h ) , F ~ ( k ) ) ) \cong\operatorname{Mod}(\operatorname{Diag}(A))_0(\widetilde F(h),\widetilde F(k)^X)\cong\mathcal V_0(X,\operatorname{Mod}(\operatorname{Diag}(A))(\widetilde F(h),\widetilde F(k))) ≅ Mod ( Diag ( A ) ) 0 ( F ( h ) , F ( k ) X ) ≅ V 0 ( X , Mod ( Diag ( A )) ( F ( h ) , F ( k )))
defines a natural transformation V 0 ( − , A / Str ( L ) ( h , k ) ) ⇒ V 0 ( − , Mod ( Diag ( A ) ) ( F ~ ( h ) , F ~ ( k ) ) ) \mathcal V_0(-,A/\operatorname{Str}(\mathcal L)(h,k))\Rightarrow\mathcal V_0(-,\operatorname{Mod}(\operatorname{Diag}(A))(\widetilde F(h),\widetilde F(k))) V 0 ( − , A / Str ( L ) ( h , k )) ⇒ V 0 ( − , Mod ( Diag ( A )) ( F ( h ) , F ( k ))) , which, by the Yoneda embedding, is induced by a unique morphism
F h , k : A / Str ( L ) ( h , k ) ⟶ Mod ( Diag ( A ) ) 0 ( F ~ ( h ) , F ~ ( k ) ) F_{h,k}:A/\operatorname{Str}(\mathcal L)(h,k)\longrightarrow\operatorname{Mod}(\operatorname{Diag}(A))_0(\widetilde F(h),\widetilde F(k)) F h , k : A / Str ( L ) ( h , k ) ⟶ Mod ( Diag ( A ) ) 0 ( F ( h ) , F ( k ))
which defines the action of F F F on the hom-objects.
By Theorem 6.7 , F 0 F_0 F 0 is faithful; we will use the fact F F F preserves powers to infer that F F F is then faithful as a V \mathcal{V} V -functor. Indeed, given any two objects h , k ∈ A / Str ( L ) h,k \in A/\operatorname{Str}(\mathbb{L}) h , k ∈ A / Str ( L ) the action on hom-objects F h , k F_{h,k} F h , k is a monomorphism if and only if V 0 ( X , F h , k ) \mathcal{V}_0(X,F_{h,k}) V 0 ( X , F h , k ) is injective for all objects X X X in V \mathcal{V} V . Since F F F preserves powers by X X X it follows that
V 0 ( X , F h , k ) ≅ ( F 0 ) h , k X \mathcal{V}_0(X,F_{h,k}) \cong(F_0)_{h,k}X V 0 ( X , F h , k ) ≅ ( F 0 ) h , k X
as objects of Set 2 \operatorname{Set}^2 Set 2 . As F 0 F_0 F 0 is faithful we have that ( F 0 ) h , k X (F_0)_{h,k}X ( F 0 ) h , k X is a monomorphism and hence F h , k F_{h,k} F h , k is a monomorphism too.
Assume now that V f p \mathcal{V}_{\mathrm{fp}} V fp is a generator of V \mathcal{V} V , then by Theorem 6.7 the functor F 0 F_0 F 0 is fully faithful and injective on objects. Thus, arguing as above, V 0 ( X , F h , k ) \mathcal{V}_0(X,F_{h,k}) V 0 ( X , F h , k ) is bijective for any X ∈ V X \in\mathcal{V} X ∈ V and any h , k h,k h , k in the slice. It follows that F h , k F_{h,k} F h , k is an isomorphism in V \mathcal{V} V and hence F F F is fully faithful as a V \mathcal{V} V -functor.
Theorem 6.15 (Enriched model-theoretic method of diagrams, semicartesian case). *Assume that V \mathcal{V} V is semicartesian with V 0 \mathcal{V}_0 V 0 locally finitely presentable as a closed category, and that ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is proper. Let L \mathbb{L} L be a language on V \mathcal{V} V and let A A A be an L \mathbb{L} L -structure. Then the V \mathcal{V} V -functor
A / Str ( L ) ⟶ Mod ( Diag ( A ) ) , A/\operatorname{Str}(\mathbb{L}) \longrightarrow\operatorname{Mod}(\operatorname{Diag}(A)), A / Str ( L ) ⟶ Mod ( Diag ( A )) , h : A ⟶ B ⟼ ( B , ( h ∘ a ) p a ∈ P ( A ) ) , h\colon A \longrightarrow B \longmapsto(B,(h\circ a)_{p_a\in P(A)}), h : A ⟶ B ⟼ ( B , ( h ∘ a ) p a ∈ P ( A ) ) , from Theorem 6.14 is an isomorphism of V \mathcal{V} V -categories.
Proof. By Theorem 6.14 the functor is injective on objects and fully faithful. Moreover, by Theorem 1.4 it is actually bijective on objects (since its underlying functor is); thus it is an isomorphism of V \mathcal{V} V -categories.
Amalgamation
The main application of the model-theoretic method of diagrams is to amalgamate structures (see Theorem 7.7). The base of amalgamation does not even need to be a structure itself (see Theorem 1.5). The latter is what ultimately results in the power of the central model-theoretic notion of types (see Theorem 7.4).
Definition 7.1. An L \mathbb{L} L -formula φ \varphi φ is called positive primitive , or a pp-formula , if it is of the form
φ ( x ) ≡ ∃ y ψ ( x , y ) \varphi(x) \equiv\exists y\psi(x,y) φ ( x ) ≡ ∃ y ψ ( x , y )
where ψ \psi ψ is a conjunction of regular atomic formulas.
Definition 7.2. Let A A A be an L \mathbb{L} L -structure and let a : X → A a\colon X \to A a : X → A be any arrow in V \mathcal{V} V . We naturally view A A A as an ( L , P ( X ) ) (\mathbb{L},P(X)) ( L , P ( X )) -structure as follows. By definition, a parameter p x : X ′ ∈ P ( X ) p_x\colon X' \in P(X) p x : X ′ ∈ P ( X ) corresponds to an arrow x : X ′ → X x\colon X' \to X x : X ′ → X , and we set p x A : = a ∘ x p_x^A := a\circ x p x A := a ∘ x . We define the positive primitive type of a a a in A A A , or pp-type of a a a in A A A , to be the following set of formulas with parameters
tp p p ( a ; A ) : = { φ ( p 1 , … , p n ) ∣ p 1 : X 1 , … , p n : X n are in P ( X ) , \operatorname{tp}_{\mathrm{pp}}(a;A):=\{\varphi(p_1,\ldots,p_n)\mid p_1\colon X_1,\ldots,p_n\colon X_n\text{ are in }P(X), tp pp ( a ; A ) := { φ ( p 1 , … , p n ) ∣ p 1 : X 1 , … , p n : X n are in P ( X ) ,
φ is an ( X 1 + … + X n ) -ary pp-formula, and \varphi\text{ is an }(X_1+\ldots+X_n)\text{-ary pp-formula, and} φ is an ( X 1 + … + X n ) -ary pp-formula, and
A ⊨ φ ( p 1 , … , p n ) } . A\models\varphi(p_1,\ldots,p_n)\}. A ⊨ φ ( p 1 , … , p n )} .
Remark 7.3. The definitions of pp-type and diagram (Theorem 6.3) look somewhat similar. There are two key differences. Firstly, the parameters in a type come from P ( X ) P(X) P ( X ) for any object X X X in V \mathcal{V} V , so X X X does not have to be (the underlying object of) an L \mathbb{L} L -structure. Secondly, the diagram only contains atomic formulas with parameters. For an arbitrary L \mathbb{L} L -structure A A A we thus have that
Diag ( A ) ⊆ tp p p ( id A ; A ) , \operatorname{Diag}(A)\subseteq\operatorname{tp}_{\mathrm{pp}}(\operatorname{id}_A;A), Diag ( A ) ⊆ tp pp ( id A ; A ) ,
and in fact Diag ( A ) \operatorname{Diag}(A) Diag ( A ) consists of precisely the atomic formulas in tp p p ( id A ; A ) \operatorname{tp}_{\mathrm{pp}}(\operatorname{id}_A;A) tp pp ( id A ; A ) .
In combination with the compactness theorem, types are very powerful. The key property is that they allow us to amalgamate structures, even if the ‘base’ of the amalgamation is not necessarily a structure itself.
Theorem 1.5, repeated. Assume that V \mathcal{V} V is reduced product stable, that V 0 \mathcal{V}_0 V 0 is locally finitely presentable, that ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is proper, and that I I I is E \mathcal{E} E -projective.
Let A A A be an L \mathbb{L} L -structure and B B B be a model of some L \mathbb{L} L -theory T \mathbb{T} T , and let A ← a X → b B A \xleftarrow{a} X \xrightarrow{b} B A a X b B be a span of arrows in V \mathcal{V} V . Suppose that tpp P ( a ; A ) ⊆ tpp P ( b ; B ) \operatorname{tpp}_{\mathbb{P}}(a; A) \subseteq\operatorname{tpp}_{\mathbb{P}}(b; B) tpp P ( a ; A ) ⊆ tpp P ( b ; B ) . Then there is a model C C C of T \mathbb{T} T together with homomorphisms f : A → C f \colon A \to C f : A → C and g : B → C g \colon B \to C g : B → C such that f ∘ a = g ∘ b f \circ a = g \circ b f ∘ a = g ∘ b , provided that:
(i) T \mathbb{T} T is regular, or;
(ii) T \mathbb{T} T is positive and V \mathcal{V} V has the ultraproduct covering property.
Proof. Consider the set of parameters P : = P ( A ) ∪ P ( B ) ∪ P ( X ) \mathcal{P} := \mathcal{P}(A) \cup\mathcal{P}(B) \cup\mathcal{P}(X) P := P ( A ) ∪ P ( B ) ∪ P ( X ) , together with the following set of parametrised formulas
Γ : = Diag ( A ) ∪ Diag ( B ) ∪ BareDiag ( X ) ∪ Σ a ∪ Σ b . \Gamma:= \operatorname{Diag}(A) \cup\operatorname{Diag}(B) \cup\operatorname{BareDiag}(X) \cup\Sigma_a \cup\Sigma_b. Γ := Diag ( A ) ∪ Diag ( B ) ∪ BareDiag ( X ) ∪ Σ a ∪ Σ b .
Here Σ a : = { p a ∘ x = p x ∣ p x ∈ P ( X ) } \Sigma_a := \{p_a \circ x = p_x \mid p_x \in\mathcal{P}(X)\} Σ a := { p a ∘ x = p x ∣ p x ∈ P ( X )} , which is a set of formulas with parameters in P ( A ) ∪ P ( X ) \mathcal{P}(A) \cup\mathcal{P}(X) P ( A ) ∪ P ( X ) , and Σ b \Sigma_b Σ b is defined similarly.
We claim that T ∪ Γ \mathbb{T} \cup\Gamma T ∪ Γ has a model. By compactness (Theorem 1.3 ) it is enough to show that every finite subset of T ∪ Γ \mathbb{T} \cup\Gamma T ∪ Γ has a model. We prove this by showing that for any finite Δ 0 ⊆ Diag ( A ) \Delta_0 \subseteq\operatorname{Diag}(A) Δ 0 ⊆ Diag ( A ) and Σ 0 ⊆ Σ a \Sigma_0 \subseteq\Sigma_a Σ 0 ⊆ Σ a the set of parametrised formulas
Γ 0 : = Δ 0 ∪ Diag ( B ) ∪ BareDiag ( X ) ∪ Σ 0 ∪ Σ b \Gamma_0 := \Delta_0 \cup\operatorname{Diag}(B) \cup\operatorname{BareDiag}(X) \cup\Sigma_0 \cup\Sigma_b Γ 0 := Δ 0 ∪ Diag ( B ) ∪ BareDiag ( X ) ∪ Σ 0 ∪ Σ b
has a model that is also a model of T \mathbb{T} T .
Let p x 1 : X 1 , … , p x n : X n p_{x_1}\colon X_1,\ldots,p_{x_n}\colon X_n p x 1 : X 1 , … , p x n : X n and p a 1 : Y 1 , … , p a k : Y k p_{a_1}\colon Y_1,\ldots,p_{a_k}\colon Y_k p a 1 : Y 1 , … , p a k : Y k be the parameters from P ( X ) \mathcal{P}(X) P ( X ) and P ( A ) \mathcal{P}(A) P ( A ) , respectively, that appear in Σ 0 \Sigma_0 Σ 0 and Δ 0 \Delta_0 Δ 0 , without duplicates. Let ψ ( x ˉ , y ˉ ) \psi(\bar{x},\bar{y}) ψ ( x ˉ , y ˉ ) be the conjunction of all the underlying L \mathbb{L} L -formulas in Δ 0 \Delta_0 Δ 0 and Σ 0 \Sigma_0 Σ 0 , with x ˉ = ( x 1 , … , x n ) \bar{x}=(x_1,\ldots,x_n) x ˉ = ( x 1 , … , x n ) and y ˉ = ( y 1 , … , y k ) \bar{y}=(y_1,\ldots,y_k) y ˉ = ( y 1 , … , y k ) . Here, if a certain formula involves only a subset of ( X 1 , … , X n , Y 1 , … , Y k ) (X_1,\ldots,X_n,Y_1,\ldots,Y_k) ( X 1 , … , X n , Y 1 , … , Y k ) , we act by substitution along the term induced by the coproduct inclusion of the given arities, this does not change the meaning of satisfaction by Theorem 2.20. So ψ ( x ˉ , y ˉ ) \psi(\bar{x},\bar{y}) ψ ( x ˉ , y ˉ ) is ( X 1 + … + X n + Y 1 + … + Y k ) (X_1+\ldots+X_n+Y_1+\ldots+Y_k) ( X 1 + … + X n + Y 1 + … + Y k ) -ary and is a conjunction of regular atomic formulas. We let φ ( x ˉ ) \varphi(\bar{x}) φ ( x ˉ ) be the pp-formula ∃ y ˉ ψ ( x ˉ , y ˉ ) \exists\bar{y}\,\psi(\bar{x},\bar{y}) ∃ y ˉ ψ ( x ˉ , y ˉ ) .
Naturally viewing A A A as an ( L , P ( A ) ∪ P ( X ) ) (\mathbb{L},\mathcal{P}(A)\cup\mathcal{P}(X)) ( L , P ( A ) ∪ P ( X )) -structure, we have A ⊨ ψ ( p ˉ x ˉ , p ˉ a ˉ ) A \models\psi(\bar{p}_{\bar{x}},\bar{p}_{\bar{a}}) A ⊨ ψ ( p ˉ x ˉ , p ˉ a ˉ ) , where p ˉ x ˉ = ( p x 1 , … , p x n ) \bar{p}_{\bar{x}}=(p_{x_1},\ldots,p_{x_n}) p ˉ x ˉ = ( p x 1 , … , p x n ) and p ˉ a ˉ = ( p a 1 , … , p a k ) \bar{p}_{\bar{a}}=(p_{a_1},\ldots,p_{a_k}) p ˉ a ˉ = ( p a 1 , … , p a k ) . By Theorem 2.19 we thus have A ⊨ φ ( p ˉ x ˉ ) A \models\varphi(\bar{p}_{\bar{x}}) A ⊨ φ ( p ˉ x ˉ ) . So φ ( p ˉ x ˉ ) ∈ tpp P ( a ; A ) ⊆ tpp P ( b ; B ) \varphi(\bar{p}_{\bar{x}}) \in\operatorname{tpp}_{\mathbb{P}}(a; A) \subseteq\operatorname{tpp}_{\mathbb{P}}(b; B) φ ( p ˉ x ˉ ) ∈ tpp P ( a ; A ) ⊆ tpp P ( b ; B ) , and hence B ⊨ φ ( p ˉ x ˉ ) B \models\varphi(\bar{p}_{\bar{x}}) B ⊨ φ ( p ˉ x ˉ ) . By Theorem 2.19 again we thus find a ′ : I → B Y 1 + … + Y k a' \colon I \to B^{Y_1+\ldots+Y_k} a ′ : I → B Y 1 + … + Y k such that
B ⊨ ψ ( ( ( p x 1 B + … + p x n B ) t , a ′ ) ) . B \models\psi\left(\left(\left(p_{x_1}^{B}+\ldots+p_{x_n}^{B}\right)^{t},a'\right)\right). B ⊨ ψ ( ( ( p x 1 B + … + p x n B ) t , a ′ ) ) .
We will now interpret p a 1 , … , p a k p_{a_1},\ldots,p_{a_k} p a 1 , … , p a k in B B B . For each 1 ≤ i ≤ k 1 \leq i \leq k 1 ≤ i ≤ k we let p a i B p_{a_i}^{B} p a i B be the transpose of the i i i th component of a ′ a' a ′ . That is, the transpose of the composite
I → a ′ B Y 1 + … + Y k ≅ B Y 1 × … × B Y k → π i B Y i , I \xrightarrow{a'} B^{Y_1+\ldots+Y_k} \cong B^{Y_1}\times\ldots\times B^{Y_k} \xrightarrow{\pi_i} B^{Y_i}, I a ′ B Y 1 + … + Y k ≅ B Y 1 × … × B Y k π i B Y i ,
where π i \pi_i π i is the i i i th projection. By construction we thus have B ⊨ ψ ( p ˉ x ˉ , p ˉ a ˉ ) B \models\psi(\bar{p}_{\bar{x}},\bar{p}_{\bar{a}}) B ⊨ ψ ( p ˉ x ˉ , p ˉ a ˉ ) , making B B B into a model of T ∪ Γ 0 \mathbb{T} \cup\Gamma_0 T ∪ Γ 0 , proving the claim.
There is thus a model C C C of T ∪ Γ \mathbb{T} \cup\Gamma T ∪ Γ . Since C C C is a model of Diag ( A ) \operatorname{Diag}(A) Diag ( A ) and Diag ( B ) \operatorname{Diag}(B) Diag ( B ) , there are L \mathbb{L} L -homomorphisms f : A → C f \colon A \to C f : A → C and g : B → C g \colon B \to C g : B → C by the enriched model-theoretic method of diagrams (Theorem 1.4). There is also an arrow h : X → C h \colon X \to C h : X → C in V \mathcal{V} V by Theorem 6.9, because C C C is a model of BareDiag ( X ) \operatorname{BareDiag}(X) BareDiag ( X ) . By that same result, h h h is the unique arrow such that p x C = h ∘ x p_x^C=h\circ x p x C = h ∘ x for all p x ∈ P ( X ) p_x\in\mathcal{P}(X) p x ∈ P ( X ) .
We also have
p x C = p a ∘ x C = f ∘ a ∘ x , p_x^C=p_{a\circ x}^C=f\circ a\circ x, p x C = p a ∘ x C = f ∘ a ∘ x ,
for all p x ∈ P ( X ) p_x\in\mathcal{P}(X) p x ∈ P ( X ) , where the first equality follows because C C C is a model of Σ a \Sigma_a Σ a and the second equality follows because f f f is such that p a ′ C = f ∘ a ′ p_{a'}^C=f\circ a' p a ′ C = f ∘ a ′ for all p a ′ ∈ P ( A ) p_{a'}\in\mathcal{P}(A) p a ′ ∈ P ( A ) . By uniqueness of h h h we thus conclude that h = f ∘ a h=f\circ a h = f ∘ a . Analogously, we have h = g ∘ b h=g\circ b h = g ∘ b , and so f ∘ a = g ∘ b f\circ a=g\circ b f ∘ a = g ∘ b . □ \square □
Remark 7.4. Typically, model theorists like to work in a monster model M \mathfrak{M} M , a very big and very homogeneous model in which every (small) model embeds. Amalgamation of small models then translates to an automorphism of the monster model, making it so that two tuples a a a and b b b in M \mathfrak{M} M (in our setting: arrows a , b : X → M a,b\colon X\to\mathfrak{M} a , b : X → M ) are in the same automorphism orbit (in our settings: satisfy f ∘ a = b f\circ a=b f ∘ a = b for some automorphism f f f of M \mathfrak{M} M ) if and only if they satisfy the same formulas (in our setting: tpp P ( a ; M ) = tpp P ( b ; M ) \operatorname{tpp}_{\mathbb{P}}(a;\mathfrak{M})=\operatorname{tpp}_{\mathbb{P}}(b;\mathfrak{M}) tpp P ( a ; M ) = tpp P ( b ; M ) ). The construction of such a monster model is standard, once an amalgamation property like Theorem 1.5 has been established. However, doing so is beyond the scope of this paper, so we leave it for future work.
The following notion was considered in [35 Section 6] , under the name of elementary morphism , where a connection was established with an enriched notion of pure morphisms in Str ( L ) \operatorname{Str}(\mathbb{L}) Str ( L ) .
Definition 7.5. A homomorphism h : A → B h:A\to B h : A → B of L \mathbb{L} L -structures is called an L \mathbb{L} L -immersion if for every pp-formula φ ( x ) \varphi(x) φ ( x ) the induced square
φ ( A ) → φ ( h ) φ ( B ) ↓ ↓ A X → h X B X \begin{CD}
\varphi(A) @>{\varphi(h)}>> \varphi(B) \\
@VVV @VVV \\
A^{X} @>{h^{X}}>> B^{X}
\end{CD} φ ( A ) ↓ ⏐ A X φ ( h ) h X φ ( B ) ↓ ⏐ B X is a pullback.
Proposition 7.6. Let h : A → B h:A\to B h : A → B be an L \mathbb{L} L -homomorphism. Then for every a : Y → A X a:Y\to A^{X} a : Y → A X and any X X X -ary pp-formula φ ( x ) \varphi(x) φ ( x ) we have that
A ⊨ φ ( a ) ⟹ B ⊨ φ ( h X ∘ a ) . A\models\varphi(a)\quad\Longrightarrow\quad B\models\varphi(h^{X}\circ a). A ⊨ φ ( a ) ⟹ B ⊨ φ ( h X ∘ a ) . If h h h is an L \mathbb{L} L -immersion then we have for all such a a a and φ \varphi φ that
A ⊨ φ ( a ) ⟺ B ⊨ φ ( h X ∘ a ) . A\models\varphi(a)\quad\Longleftrightarrow\quad B\models\varphi(h^{X}\circ a). A ⊨ φ ( a ) ⟺ B ⊨ φ ( h X ∘ a ) . Proof. Consider the diagram below
Y → c φ ( A ) → φ ( h ) φ ( B ) a ↓ ↓ ↓ A X → h X B X \begin{CD}
Y @>{c}>> \varphi(A) @>{\varphi(h)}>> \varphi(B) \\
@V{a}VV @VVV @VVV \\
A^{X} @>{h^{X}}>> B^{X}
\end{CD} Y a ↓ ⏐ A X c h X φ ( A ) ↓ ⏐ B X φ ( h ) φ ( B ) ↓ ⏐ If A ⊨ φ ( a ) A\models\varphi(a) A ⊨ φ ( a ) then by definition the arrow c c c exists, making the left triangle commute. So h X ∘ a h^{X}\circ a h X ∘ a factors through φ ( B ) \varphi(B) φ ( B ) via φ ( h ) ∘ c \varphi(h)\circ c φ ( h ) ∘ c , and hence B ⊨ φ ( h X ∘ a ) B\models\varphi(h^{X}\circ a) B ⊨ φ ( h X ∘ a ) .
If h h h is an L \mathbb{L} L -immersion and B ⊨ φ ( h X ∘ a ) B\models\varphi(h^{X}\circ a) B ⊨ φ ( h X ∘ a ) then by definition the arrow b b b in the above diagram exists, making the outer square commute. Since the smaller square is a pullback square, we thus find the arrow c c c making everything commute. So a a a factors through φ ( A ) \varphi(A) φ ( A ) via c c c , and we conclude that A ⊨ φ ( a ) A\models\varphi(a) A ⊨ φ ( a ) .
Corollary 7.7. Assume that V \mathcal{V} V is reduced product stable, that V 0 \mathcal{V}_{0} V 0 is locally finitely presentable, that ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is proper, and that I I I is E \mathcal{E} E -projective.
Let B ← f A → g C B\xleftarrow{f}A\xrightarrow{g}C B f A g C be a span of L \mathbb{L} L -structures, where f f f is an immersion, g g g is a homomorphism, and C C C is a model of some L \mathbb{L} L -theory T T T . Then there exists a cospan B → f ′ D ← g ′ C B\xrightarrow{f'}D\xleftarrow{g'}C B f ′ D g ′ C of homomorphisms, such that the arising square commutes (i.e., f ′ ∘ f = g ′ ∘ g f'\circ f=g'\circ g f ′ ∘ f = g ′ ∘ g ) and D D D is a model of T T T , provided that:
T T T is regular, or;
T T T is positive and V \mathcal{V} V has the ultraproduct covering property.
Proof. We claim that tpp p p ( f ; B ) ⊆ tpp p p ( g ; C ) \operatorname{tpp}_{\mathrm{pp}}(f;B)\subseteq\operatorname{tpp}_{\mathrm{pp}}(g;C) tpp pp ( f ; B ) ⊆ tpp pp ( g ; C ) , and so the result follows from Theorem 1.5. Let φ ( p a 1 , … , p a n ) ∈ tpp p p ( f ; B ) \varphi(p_{a_{1}},\ldots,p_{a_{n}})\in\operatorname{tpp}_{\mathrm{pp}}(f;B) φ ( p a 1 , … , p a n ) ∈ tpp pp ( f ; B ) be a formula with parameters p a 1 : X 1 , … , p a n : X n p_{a_{1}}:X_{1},\ldots,p_{a_{n}}:X_{n} p a 1 : X 1 , … , p a n : X n in P ( A ) \mathcal{P}(A) P ( A ) . Writing out definitions, this means that
B ⊨ φ ( f X 1 + ⋯ + X n ∘ ( a 1 + ⋯ + a n ) t ) . B\models\varphi\left(f^{X_{1}+\cdots+X_{n}}\circ(a_{1}+\cdots+a_{n})^{t}\right). B ⊨ φ ( f X 1 + ⋯ + X n ∘ ( a 1 + ⋯ + a n ) t ) . So by Theorem 7.6 we have
A ⊨ φ ( ( a 1 + ⋯ + a n ) t ) . A\models\varphi\left((a_{1}+\cdots+a_{n})^{t}\right). A ⊨ φ ( ( a 1 + ⋯ + a n ) t ) . Again, by Theorem 7.6 we have
C ⊨ φ ( g X 1 + ⋯ + X n ∘ ( a 1 + ⋯ + a n ) t ) . C\models\varphi\left(g^{X_{1}+\cdots+X_{n}}\circ(a_{1}+\cdots+a_{n})^{t}\right). C ⊨ φ ( g X 1 + ⋯ + X n ∘ ( a 1 + ⋯ + a n ) t ) . The latter is precisely saying that φ ( p a 1 , … , p a n ) ∈ tpp p p ( g ; C ) \varphi(p_{a_{1}},\ldots,p_{a_{n}})\in\operatorname{tpp}_{\mathrm{pp}}(g;C) φ ( p a 1 , … , p a n ) ∈ tpp pp ( g ; C ) , as required.
The ultraproduct covering property
In this section we give sufficient conditions that imply the ultraproduct covering property (Theorem 4.2). Note that the contents of this section are about ordinary category theory, no enrichment is considered here.
Definition 8.1. An object X X X in a category C \mathcal{C} C is called finitely connected if C ( X , − ) \mathcal{C}(X,-) C ( X , − ) preserves finite coproducts.
Theorem 8.2. Suppose that a category C \mathcal{C} C has a strong generator X \mathcal{X} X formed by finitely presentable finitely connected objects. Then the arrows appearing in Theorem 4.2 are isomorphisms. It follows that C \mathcal{C} C satisfies the ultraproduct covering property for any choice of factorisation system.
Proof. Consider X \mathcal{X} X as a full subcategory of C \mathcal{C} C ; then the restricted Yoneda embedding
J : C ⟶ [ X o p , S e t ] J:\mathcal{C}\longrightarrow[\mathcal{X}^{\mathrm{op}},\mathbf{Set}] J : C ⟶ [ X op , Set ]
preserves all limits as well as directed colimits and finite coproducts (since C ( X , − ) \mathcal{C}(X,-) C ( X , − ) does so for each X ∈ X X\in\mathcal{X} X ∈ X ) and is conservative (since X \mathcal{X} X is a strong generator). It follows that J J J carries the comparison arrows in Theorem 4.2 to the corresponding ones in [ X o p , S e t ] [\mathcal{X}^{\mathrm{op}},\mathbf{Set}] [ X op , Set ] , which we know to be isomorphisms because they are so in S e t \mathbf{Set} Set and limits and colimits are computed pointwise in [ X o p , S e t ] [\mathcal{X}^{\mathrm{op}},\mathbf{Set}] [ X op , Set ] . The result follows by conservativity of J J J . □
It is enough for X \mathcal{X} X to only be an E \mathcal{E} E -generator.
Theorem 8.3. Let C \mathcal{C} C be a category with a factorisation system ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) . Suppose that C \mathcal{C} C has an E \mathcal{E} E -generator X \mathcal{X} X that consists of finitely connected finitely presentable objects. Then C \mathcal{C} C satisfies the ultraproduct covering property.
Proof. Let us first consider the condition on the initial object. Since every object X ∈ X X\in\mathcal{X} X ∈ X is finitely connected, there is no arrow X → 0 X\to0 X → 0 . It follows by Theorem 2.7 that the unique arrow
0 ⟶ ∏ j ∈ J 0 , 0\longrightarrow\prod_{j\in J}0, 0 ⟶ j ∈ J ∏ 0 ,
for any nonempty set J J J , lies in E \mathcal{E} E . Thus so does
0 ⟶ ∏ j ∈ J 0 / U , 0\longrightarrow\prod_{j\in J}0/\mathcal{U}, 0 ⟶ j ∈ J ∏ 0/ U ,
for any ultrafilter U \mathcal{U} U on J J J , by Theorem 4.4.
Let { A i } i ∈ I \{A_i\}_{i\in I} { A i } i ∈ I and { B i } i ∈ I \{B_i\}_{i\in I} { B i } i ∈ I be familes of objects, U \mathcal{U} U an ultrafilter on I I I , and f : X → ∏ i ∈ I ( A i + B i ) / U f:X\to\prod_{i\in I}(A_i+B_i)/\mathcal{U} f : X → ∏ i ∈ I ( A i + B i ) / U any arrow with X ∈ X X\in\mathcal{X} X ∈ X . By Theorem 2.7 it is enough to show that f f f factors through the comparison arrow
∏ i ∈ I A i / U + ∏ i ∈ I B i / U ⟶ ∏ i ∈ I ( A i + B i ) / U . \prod_{i\in I}A_i/\mathcal{U}+\prod_{i\in I}B_i/\mathcal{U}\longrightarrow\prod_{i\in I}(A_i+B_i)/\mathcal{U}. i ∈ I ∏ A i / U + i ∈ I ∏ B i / U ⟶ i ∈ I ∏ ( A i + B i ) / U .
As X X X is finitely presentable, f f f factors as
X → f ′ ∏ i ∈ J ( A i + B i ) ⟶ ∏ i ∈ I ( A i + B i ) / U , X\xrightarrow{f'}\prod_{i\in J}(A_i+B_i)\longrightarrow\prod_{i\in I}(A_i+B_i)/\mathcal{U}, X f ′ i ∈ J ∏ ( A i + B i ) ⟶ i ∈ I ∏ ( A i + B i ) / U ,
for some J ∈ U J\in\mathcal{U} J ∈ U . For i ∈ J i\in J i ∈ J , write f i ′ : X → A i + B i f'_i:X\to A_i+B_i f i ′ : X → A i + B i for the composition of f ′ f' f ′ with the i i i th projection. Since X X X is finitely connected, f i ′ f'_i f i ′ factors as
X → g i C i ⟶ A i + B i , X\xrightarrow{g_i}C_i\longrightarrow A_i+B_i, X g i C i ⟶ A i + B i ,
where C i C_i C i is either A i A_i A i or B i B_i B i . Define
J A : = { i ∈ J ∣ C i = A i } , J B : = { i ∈ J ∣ C i = B i } . J_A:=\{i\in J\mid C_i=A_i\},\qquad J_B:=\{i\in J\mid C_i=B_i\}. J A := { i ∈ J ∣ C i = A i } , J B := { i ∈ J ∣ C i = B i } .
Then either J A ∈ U J_A\in\mathcal{U} J A ∈ U or J B ∈ U J_B\in\mathcal{U} J B ∈ U , because U \mathcal{U} U is an ultrafilter. Without loss of generality, assume J A ∈ U J_A\in\mathcal{U} J A ∈ U . Then we find the following commutative diagram
X → ( g i ) i ∈ J A ∏ i ∈ J A A i → ∏ i ∈ J A A i + ∏ i ∈ J A B i → ∏ i ∈ I A i / U + ∏ i ∈ I B i / U ( f i ′ ) i ∈ J A ↓ ↓ ↓ ∏ i ∈ J A A i + B i → ∏ i ∈ I ( A i + B i ) / U \begin{CD}
X @>{(g_i)_{i\in J_A}}>> \prod_{i\in J_A} A_i @>>> \prod_{i\in J_A} A_i+\prod_{i\in J_A} B_i @>>> \prod_{i\in I} A_i/\mathcal{U}+\prod_{i\in I} B_i/\mathcal{U}\\
@V{(f'_i)_{i\in J_A}}VV @. @VVV @VVV\\
\prod_{i\in J_A} A_i+B_i @>>> \prod_{i\in I}(A_i+B_i)/\mathcal{U}
\end{CD} X ( f i ′ ) i ∈ J A ↓ ⏐ i ∈ J A ∏ A i + B i ( g i ) i ∈ J A i ∈ J A ∏ A i i ∈ I ∏ ( A i + B i ) / U i ∈ J A ∏ A i + i ∈ J A ∏ B i ↓ ⏐ i ∈ I ∏ A i / U + i ∈ I ∏ B i / U ↓ ⏐
The composition of the bottom arrows is f f f , so the composition of the top arrows gives the required factorisation. □
The conditions in Theorems 8.2 and 8.3 are sufficient, but not necessary. For example, in § 9.5 we will see that A b \mathbf{Ab} Ab satisfies the ultraproduct covering property (the comparison arrow is an isomorphism). However, there are no finitely connected objects in A b \mathbf{Ab} Ab . Indeed, initial objects are never finitely connected and for any non-trivial group G G G the diagonal Δ : G → G × G ≅ G + G \Delta:G\to G\times G\cong G+G Δ : G → G × G ≅ G + G does not factor through either summand.
Applications and examples
Rather than having some running examples that we slowly build up throughout the paper, we present them here all at once, so that everything can be found in one place. We first give an overview of the various assumptions on V \mathcal{V} V and ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) that are used throughout the paper.
The most basic assumptions are being reduced product ready (Theorem 3.3) and reduced product stable (Theorem 4.1), which are needed for all our main results.
All our main results have statements for regular logic and positive logic. The latter needs V \mathcal{V} V to have the ultraproduct covering property (Theorem 4.2).
The assumption that V 0 \mathcal{V}_0 V 0 has a finitely presentable E \mathcal{E} E -generator is needed for a converse to version 2 of our Los-style theorem (Theorem 4.6).
To deal with sequents with parameters, both in our Los-style theorem (Theorem 5.7) and the enriched compactness theorem (Theorem 1.3), we need that the monoidal unit I I I is finitely presentable . Without that assumption, these theorems still work for formulas with parameters (i.e., sequents of the form ⊤ ⊢ φ ( p 1 , … , p n ) \top\vdash\varphi(p_1,\ldots,p_n) ⊤ ⊢ φ ( p 1 , … , p n ) ).
For the enriched model-theoretic method of diagrams (Theorem 1.4) and for the amalgamation results in Section 7, we need that V 0 \mathcal{V}_0 V 0 is locally finitely presentable , ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is proper , and I I I is E \mathcal{E} E -projective . That last assumption is not needed in the model-theoretic method of diagrams, but it does need the finitely presentable objects to be closed under the monoidal product, something which is already included the other assumptions for the amalgamation results.
If V \mathcal{V} V is semicartesian and the monoidal unit finitely presentable then the enriched model-theoretic method of diagrams, which is formulated as an isomorphism of ordinary categories, upgrades to an isomorphism of enriched categories (Theorem 6.15).
If the base is locally finitely presentable as a closed category, which is often the case, then many of the assumptions are automatic. In terms of the above list, the second and third bullet points become automatic, and the first one is partially satisfied.
Proposition 9.1. If V \mathcal{V} V is locally finitely presentable as a closed category then the first two properties of being reduced product ready (Theorem 3.3, (1) and (2)) hold. Furthermore, if the right class M \mathcal{M} M of the factorisation system ( E , M ) (\mathcal{E},\mathcal{M}) ( E , M ) is the class of monomorphisms or the class of regular monomorphisms then V \mathcal{V} V is reduced product ready.
Proof. In any locally finitely presentable category, finite limits commute with directed colimits [4 Proposition 1.59] , and Theorem 3.3(2) holds by Theorem 3.4. If M \mathcal{M} M is the class of (regular) monomorphisms then its members can be expressed as finite limits, and so Theorem 3.3(3) holds. □
The category of sets
By taking V = S e t \mathcal{V}=\mathbf{Set} V = Set with its cartesian closed structure and the usual (epi, mono) factorisation system, we recover ordinary (unenriched) logic. Of course, this satisfies all the assumptions that we have considered in this paper for our enrichment base. The results in this paper then recover the classical results.
Presheaf topoi
We describe a class of presheaf topoi that can be used as bases of enrichment, so that all our theorems apply.
Theorem 9.2. Let C \mathcal{C} C be a small category such that one of the following holds:
C \mathcal{C} C has binary products,
each connected component of C \mathcal{C} C is equivalent to a finite category.
Then the presheaf topos [ C o p , S e t ] [\mathcal{C}^{\mathrm{op}},\mathbf{Set}] [ C op , Set ] with the cartesian closed structure and the ( E , M ) : = ( e p i , m o n o ) (\mathcal{E},\mathcal{M}) := (\mathrm{epi},\mathrm{mono}) ( E , M ) := ( epi , mono ) factorisation system has the following properties:
(1) it is locally finitely presentable,
(2) it is reduced product stable,
(3) it satisfies the ultraproduct covering property.
Proof. Presheaf categories are locally finitely presentable [4 Example 1.12] : the representable presheaves form a strong generator of finitely presentable objects.
For (2) we note that any topos automatically satisfies (1) and (3) of Theorem 3.3. So to conclude that [ C o p , S e t ] [\mathcal{C}^{\mathrm{op}},\mathbf{Set}] [ C op , Set ] is reduced product ready it is enough to show that finitely presentable objects are closed under binary products, by Theorem 3.4. This follows by Theorems 9.5 and 9.6 for our respective cases.
Epimorphisms in presheaf categories are precisely those morphisms that are pointwise surjective. Since products are computed pointwise, we conclude that epimorphisms are closed under products, so [ C o p , S e t ] [\mathcal{C}^{\mathrm{op}},\mathbf{Set}] [ C op , Set ] is reduced product stable.
Property (3), the ultraproduct covering property, holds because it does so in S e t \mathbf{Set} Set and limits and colimits in [ C o p , S e t ] [\mathcal{C}^{\mathrm{op}},\mathbf{Set}] [ C op , Set ] are computed pointwise.
Corollary 9.3. Let C \mathcal{C} C be a small category such that one of the following holds:
Then the presheaf topos [ C o p , S e t ] [\mathcal{C}^{\mathrm{op}},\mathbf{Set}] [ C op , Set ] with the cartesian closed structure and the ( E , M ) : = ( epi , mono ) (\mathcal{E},\mathcal{M}) := (\operatorname{epi},\operatorname{mono}) ( E , M ) := ( epi , mono ) factorisation system, in addition to satisfying the properties listed in Theorem 9.2 , is locally finitely presentable as a closed category and the terminal object (and hence, the monoidal unit) is projective.
Proof. Both properties follow from the terminal object being representable.
The only place in the above proof where the assumptions in the bullet points are used is to show that finitely presentable objects are closed under binary products. We first give an example of how this can fail in general presheaf categories.
Example 9.4. Consider the category S e t N \mathbf{Set}^{\mathbb{N}} Set N of sets with an endomorphism. So this is a presheaf category, where N \mathbb{N} N is viewed as a monoid (i.e., a one-object category) under addition. There is one representable presheaf, which is simply N \mathbb{N} N where the endomorphism takes n n n to n + 1 n+1 n + 1 . Representable presheaves are finitely presentable, but the product N × N \mathbb{N} \times\mathbb{N} N × N is not finitely presentable. Indeed, the endomorphism on the product sends ( n , k ) (n,k) ( n , k ) to ( n + 1 , k + 1 ) (n+1,k+1) ( n + 1 , k + 1 ) . So, for i < ω i < \omega i < ω , we can define
X i : = { ( n , k ) ∈ N × N ∣ ∣ n − k ∣ ≤ i } X_i:=\{(n,k) \in\mathbb{N}\times\mathbb{N}\mid|n-k|\leq i\} X i := {( n , k ) ∈ N × N ∣ ∣ n − k ∣ ≤ i } and we view X i X_i X i as a subpresheaf of N × N \mathbb{N}\times\mathbb{N} N × N . With the inclusions X i ⊆ X j X_i\subseteq X_j X i ⊆ X j for i ≤ j i\leq j i ≤ j we can write N × N \mathbb{N}\times\mathbb{N} N × N as the directed colimit N × N = colim i < ω X i \mathbb{N}\times\mathbb{N}=\operatorname{colim}_{i<\omega}X_i N × N = colim i < ω X i . The identity on N × N \mathbb{N}\times\mathbb{N} N × N does not factor through this diagram, so N × N \mathbb{N}\times\mathbb{N} N × N is not finitely presentable.
We are grateful to Adámek and Sousa for helpful discussions that improved the proofs of the following two lemmas. The (partial) converse of the first is due to them, using similar techniques as in their recent work [7 ] , and we thank them for allowing us to include it.
Lemma 9.5. If each connected component of C \mathcal{C} C is equivalent to a finite category then the finitely presentable objects in [ C o p , S e t ] [\mathcal{C}^{\mathrm{op}},\mathbf{Set}] [ C op , Set ] are closed under binary products. If C \mathcal{C} C is a groupoid the converse is true.
Proof. Without loss of generality we can assume that each connected component of C \mathcal{C} C is a finite category. Let F F F be a presheaf on C \mathcal{C} C . If F ( C ) F(C) F ( C ) is empty (resp. finite) for all C C C in some connected component of C \mathcal{C} C then we will say that F F F is empty (resp. finite) on that connected component. It is then straightforward to check that F F F is finitely presentable if and only if F F F is empty on all but finitely many connected components, and whenever F F F is nonempty on a connected component then it is finite on that component. This property is clearly closed under binary products.
For the converse assume that C \mathcal{C} C is a groupoid; the goal translates into proving that every object of C \mathcal{C} C has finite automorphism group. We prove the contrapositive, so let C ∈ C C\in\mathcal{C} C ∈ C have infinite automorphism group G G G . We will only consider presheaves where all components are empty, except for the one at C C C , so that we can identify such presheaves with right G G G -sets. We view G G G as a presheaf, namely the presheaf represented by C C C , which is thus finitely presentable. We claim that G × G G\times G G × G is not finitely presentable. For an arbitrary X ⊆ G X\subseteq G X ⊆ G we define the presheaf A X : = { ( x , y ) ∈ G × G ∣ x y − 1 ∈ X } A_X:=\{(x,y)\in G\times G\mid xy^{-1}\in X\} A X := {( x , y ) ∈ G × G ∣ x y − 1 ∈ X } . Then G × G = colim X ⊆ f i n G A X G\times G=\operatorname{colim}_{X\subseteq_{\mathrm{fin}}G}A_X G × G = colim X ⊆ fin G A X , but id G × G \operatorname{id}_{G\times G} id G × G does not factor through this diagram, proving our claim.
Lemma 9.6. Let C \mathcal{C} C be a small category with binary products. Then the finitely presentable objects in [ C o p , S e t ] [\mathcal{C}^{\mathrm{op}},\mathbf{Set}] [ C op , Set ] are closed under binary products.
Proof. The finitely presentable presheaves are precisely the finite colimits of representable presheaves by [17 Theorem 5.37 and Proposition 5.41] . Colimits in S e t \mathbf{Set} Set distribute over binary products [6 Example 3.20] . Since limits and colimits of presheaves are computed pointwise, the same is true in [ C o p , S e t ] [\mathcal{C}^{\mathrm{op}},\mathbf{Set}] [ C op , Set ] . So a binary product of finitely presentable objects is a finite colimit of binary products of representables. We conclude because the representables are closed under binary products, by assumption and the fact that the Yoneda embedding preserves limits.
Topos of sheaves on Boolean algebras
Here we will consider toposes of sheaves on (countable) Boolean algebras, which turn out to be examples that satisfy all our assumptions, except for the ultraproduct covering property (see Theorem 9.9). We thank Kanalas for helpful discussions related to the material in this section, and in particular Theorem 9.9 is based on an idea of his (taking place in Sh ( R ) \operatorname{Sh}(\mathbb{R}) Sh ( R ) instead [16 ] ).
Theorem 9.7. Let Sh ( B , J c o h ) \operatorname{Sh}(B,J_{\mathrm{coh}}) Sh ( B , J coh ) be the topos of sheaves on a countable Boolean algebra B B B with respect to the coherent topology, equipped with the cartesian closed structure and the usual (epi, mono) factorisation system. Then:
it is locally finitely presentable as a closed category,
it is reduced product stable,
the terminal object (and hence, the monoidal unit) is projective.
Proof. Item (1) follows from Theorem 9.8, since Sh ( B , J c o h ) \operatorname{Sh}(B,J_{\mathrm{coh}}) Sh ( B , J coh ) is a coherent topos. We can equivalently view Sh ( B , J c o h ) \operatorname{Sh}(B,J_{\mathrm{coh}}) Sh ( B , J coh ) as the topos of sheaves on the Stone space of B B B . So it is a localic topos, and following [15 Example D4.5.2(d)] , supports split in Sh ( B , J c o h ) \operatorname{Sh}(B,J_{\mathrm{coh}}) Sh ( B , J coh ) , which means that every subterminal object is projective. So we have (3).
Finally, we prove (2). By Theorem 9.1 it remains to show that epimorphisms are closed under products. So let { f i : A i → B i } i ∈ I \{f_i:A_i\to B_i\}_{i\in I} { f i : A i → B i } i ∈ I be a family of epimorphisms. As Sh ( B , J c o h ) \operatorname{Sh}(B,J_{\mathrm{coh}}) Sh ( B , J coh ) is localic, the subterminal objects form a generator [15 Theorem C1.4.7] . By Theorem 2.7 it is thus enough to show that for any subterminal T T T , any arrow g : T → ∏ i ∈ I B i g:T\to\prod_{i\in I}B_i g : T → ∏ i ∈ I B i factors through ∏ i ∈ I f i \prod_{i\in I}f_i ∏ i ∈ I f i . This quickly follows, because for each i ∈ I i\in I i ∈ I , projectivity of T T T (see before) yields a factorisation π i g = f i h i \pi_i g=f_i h_i π i g = f i h i , for some h i : T → A i h_i:T\to A_i h i : T → A i , where π i : ∏ i ∈ I B i → B i \pi_i:\prod_{i\in I}B_i\to B_i π i : ∏ i ∈ I B i → B i is the i i i th projection. So ( h i ) i ∈ I : T → ∏ i ∈ I A i (h_i)_{i\in I}:T\to\prod_{i\in I}A_i ( h i ) i ∈ I : T → ∏ i ∈ I A i is the required factor.
Table 9.8.
Proposition 9.8. Any coherent topos is locally finitely presentable as a closed category with respect to the cartesian closed structure.
Proof. Any coherent topos can be presented as Sh ( C , J ) \operatorname{Sh}(C,J) Sh ( C , J ) , where C C C is a finitely complete category and J J J is generated by finite covering familes [15 Theorem D3.3.1] . Following [15 Remark D3.3.12] , such a topos is locally finitely presentable. We will redo part of that argument to prove our stronger claim.
Write ι : Sh ( C , J ) → [ C o p , Set ] \iota:\operatorname{Sh}(C,J)\to[C^{\mathrm{op}},\operatorname{Set}] ι : Sh ( C , J ) → [ C op , Set ] for the inclusion functor, and a : [ C o p , Set ] → Sh ( C , J ) a:[C^{\mathrm{op}},\operatorname{Set}]\to\operatorname{Sh}(C,J) a : [ C op , Set ] → Sh ( C , J ) for the sheafification functor. As mentioned in [15 Remark D3.3.12] , it is straightforward to check that ι \iota ι preserves directed colimits. It follows that if F F F is finitely presentable in [ C o p , Set ] [C^{\mathrm{op}},\operatorname{Set}] [ C op , Set ] then a ( F ) a(F) a ( F ) is finitely presentable in Sh ( C , J ) \operatorname{Sh}(C,J) Sh ( C , J ) . Indeed, for a directed diagram ( G i ) i ∈ I (G_i)_{i\in I} ( G i ) i ∈ I in Sh ( C , J ) \operatorname{Sh}(C,J) Sh ( C , J ) :
Hom ( a ( F ) , c o l i m i ∈ I G i ) ≅ Hom ( F , ι ( c o l i m i ∈ I G i ) ) \operatorname{Hom}(a(F),\mathop{\mathrm{colim}}_{i\in I}G_i)\cong\operatorname{Hom}(F,\iota(\mathop{\mathrm{colim}}_{i\in I}G_i)) Hom ( a ( F ) , colim i ∈ I G i ) ≅ Hom ( F , ι ( colim i ∈ I G i ))
≅ Hom ( F , c o l i m i ∈ I ι ( G i ) ) \cong\operatorname{Hom}(F,\mathop{\mathrm{colim}}_{i\in I}\iota(G_i)) ≅ Hom ( F , colim i ∈ I ι ( G i ))
≅ c o l i m i ∈ I Hom ( F , ι ( G i ) ) \cong\mathop{\mathrm{colim}}_{i\in I}\operatorname{Hom}(F,\iota(G_i)) ≅ colim i ∈ I Hom ( F , ι ( G i ))
≅ c o l i m i ∈ I Hom ( a ( F ) , G i ) , \cong\mathop{\mathrm{colim}}_{i\in I}\operatorname{Hom}(a(F),G_i), ≅ colim i ∈ I Hom ( a ( F ) , G i ) ,
as required.
Since C C C has a terminal object, the terminal object in [ C o p , Set ] [C^{\mathrm{op}},\operatorname{Set}] [ C op , Set ] is representable and is thus finitely presentable. It follows that the terminal object in Sh ( C , J ) \operatorname{Sh}(C,J) Sh ( C , J ) is finitely presentable.
Now let F F F and G G G be finitely presentable objects in Sh ( C , J ) \operatorname{Sh}(C,J) Sh ( C , J ) . It remains to show that F × G F\times G F × G is finitely presentable. Since [ C o p , Set ] [C^{\mathrm{op}},\operatorname{Set}] [ C op , Set ] is locally finitely presentable, there is a directed diagram ( A i ) i ∈ I (A_i)_{i\in I} ( A i ) i ∈ I of finitely presentable objects in [ C o p , Set ] [C^{\mathrm{op}},\operatorname{Set}] [ C op , Set ] such that ι ( F ) = c o l i m i ∈ I A i \iota(F)=\mathop{\mathrm{colim}}_{i\in I}A_i ι ( F ) = colim i ∈ I A i . Hence
F ≅ a ι ( F ) = a ( c o l i m i ∈ I A i ) ≅ c o l i m i ∈ I a ( A i ) . F\cong a\iota(F)=a(\mathop{\mathrm{colim}}_{i\in I}A_i)\cong\mathop{\mathrm{colim}}_{i\in I}a(A_i). F ≅ a ι ( F ) = a ( colim i ∈ I A i ) ≅ colim i ∈ I a ( A i ) .
Since F F F is finitely presentable, the identity must factor through this diagram, and so F F F is a retract of a ( A ) a(A) a ( A ) for some A A A that is finitely presentable in [ C o p , Set ] [C^{\mathrm{op}},\operatorname{Set}] [ C op , Set ] . Similarly, G G G is a retract of a ( B ) a(B) a ( B ) for some B B B that is finitely presentable in [ C o p , Set ] [C^{\mathrm{op}},\operatorname{Set}] [ C op , Set ] . So F × G F\times G F × G is a retract of a ( A ) × a ( B ) ≅ a ( A × B ) a(A)\times a(B)\cong a(A\times B) a ( A ) × a ( B ) ≅ a ( A × B ) . We thus have that F × G F\times G F × G is a retract of a finitely presentable object, because A × B A\times B A × B is finitely presentable by Theorem 9.6, and so F × G F\times G F × G is finitely presentable.
We finish this section with an example of a topos as in Theorem 9.7 that fails the ultraproduct covering property.
Example 9.9. Recall that the Cantor space 2 ω 2^{\omega} 2 ω it the space with a clopen basis given by
U ( η ) = { σ ∈ 2 ω ∣ η ⊆ σ } , U(\eta)=\{\sigma\in2^{\omega}\mid\eta\subseteq\sigma\}, U ( η ) = { σ ∈ 2 ω ∣ η ⊆ σ } , where η ∈ 2 < ω \eta\in2^{<\omega} η ∈ 2 < ω ranges over the finite sequences. We also recall that it is the Stone space of the countable atomless Boolean algebra. So Theorem 9.7 applies to Sh ( 2 ω ) \operatorname{Sh}(2^{\omega}) Sh ( 2 ω ) . We show that the ultraproduct covering property fails for Sh ( 2 ω ) \operatorname{Sh}(2^{\omega}) Sh ( 2 ω ) .
Write ζ \zeta ζ and ζ n \zeta_n ζ n for the constant 0 0 0 sequences of length ω \omega ω and n n n respectively. For each n < ω n<\omega n < ω , let A n A_n A n and B n B_n B n be the subterminals corresponding to the opens U n : = U ( ζ n ) U_n:=U(\zeta_n) U n := U ( ζ n ) and V : = 2 ω ∖ { ζ } V:=2^{\omega}\setminus\{\zeta\} V := 2 ω ∖ { ζ } , respectively. Let U \mathcal{U} U be a non-principal ultrafilter on ω \omega ω . We will show that the arrow
∏ n < ω A n / U + ∏ n < ω B n / U ⟶ ∏ n < ω ( A n + B n ) / U \prod_{n<\omega} A_n/\mathcal{U}+\prod_{n<\omega} B_n/\mathcal{U}\longrightarrow\prod_{n<\omega}(A_n+B_n)/\mathcal{U} n < ω ∏ A n / U + n < ω ∏ B n / U ⟶ n < ω ∏ ( A n + B n ) / U is not an epimorphism by showing that it is not surjective on the stalk at ζ \zeta ζ . Firstly, we argue that ∏ n < ω A n / U = 0 \prod_{n<\omega}A_n/\mathcal{U}=0 ∏ n < ω A n / U = 0 by showing that ∏ n ∈ J A n = 0 \prod_{n\in J}A_n=0 ∏ n ∈ J A n = 0 for all J ∈ U J\in\mathcal{U} J ∈ U . Indeed, for any J ∈ U J\in\mathcal{U} J ∈ U and any nonempty open W ⊆ 2 ω W\subseteq2^{\omega} W ⊆ 2 ω , there is n ∈ J n\in J n ∈ J such that W ⊈ U n W\nsubseteq U_n W ⊈ U n , because J J J is infinite. Thus A n ( W ) = ∅ A_n(W)=\varnothing A n ( W ) = ∅ and the claim follows.
Since B n ( W ) = ∅ B_n(W)=\varnothing B n ( W ) = ∅ for each neighbourhood W W W of ζ \zeta ζ , we have ( ∏ n ∈ J B n ) ζ = ∅ (\prod_{n\in J}B_n)_{\zeta}=\varnothing ( ∏ n ∈ J B n ) ζ = ∅ . Stalks commute with colimits, so the stalk of ∏ n < ω A n / U + ∏ n < ω B n = ∏ n < ω B n / U \prod_{n<\omega}A_n/\mathcal{U}+\prod_{n<\omega}B_n=\prod_{n<\omega}B_n/\mathcal{U} ∏ n < ω A n / U + ∏ n < ω B n = ∏ n < ω B n / U at ζ \zeta ζ is empty. To conclude we show that the stalk of ∏ n < ω A n + B n / U \prod_{n<\omega}A_n+B_n/\mathcal{U} ∏ n < ω A n + B n / U at ζ \zeta ζ is nonempty, for which it is enough to show that ( A n + B n ) ( 2 ω ) (A_n+B_n)(2^{\omega}) ( A n + B n ) ( 2 ω ) is nonempty for every n < ω n<\omega n < ω . Viewing A n + B n A_n+B_n A n + B n as the étalé space p : U n + V → 2 ω p:U_n+V\to2^{\omega} p : U n + V → 2 ω , this amounts to producing a section s : 2 ω → U n + V s:2^{\omega}\to U_n+V s : 2 ω → U n + V . We have 2 ω = U n + ( 2 ω ∖ U n ) 2^{\omega}=U_n+(2^{\omega}\setminus U_n) 2 ω = U n + ( 2 ω ∖ U n ) , because U n U_n U n is clopen. As 2 ω ∖ U n ⊆ V 2^{\omega}\setminus U_n\subseteq V 2 ω ∖ U n ⊆ V we can let s s s be the induced map 2 ω = U n + ( 2 ω ∖ U n ) → U n + V 2^{\omega}=U_n+(2^{\omega}\setminus U_n)\to U_n+V 2 ω = U n + ( 2 ω ∖ U n ) → U n + V .
In fact, a Łoś-style theorem for positive logic is not possible in Sh ( 2 ω ) \operatorname{Sh}(2^{\omega}) Sh ( 2 ω ) . Consider a language L L L with two propositional symbols P P P and Q Q Q . For each n < ω n<\omega n < ω we let M n M_n M n be the model that interprets P P P and Q Q Q as A n A_n A n and B n B_n B n respectively, and we let M : = ∏ n < ω M n / U M:=\prod_{n<\omega}M_n/\mathcal{U} M := ∏ n < ω M n / U . Consider the formula φ ≡ P ∨ Q \varphi\equiv P\vee Q φ ≡ P ∨ Q . Then φ ( M n ) = 1 \varphi(M_n)=1 φ ( M n ) = 1 for all n < ω n<\omega n < ω , while φ ( M ) \varphi(M) φ ( M ) is the subterminal corresponding to V V V .
The category of monoid acts
The main motivation for this section is that we would like apply our work to the category Set N \operatorname{Set}^{\mathbb{N}} Set N of sets with an endomorphism, to capture the model theory of difference algebra (see also [40 ] ). However, as we have seen in Theorem 9.4, the cartesian closed structure on this category does not work well for us. We swap our topos-theoretic perspective for a more algebraic one, and work in the generality where N \mathbb{N} N is replaced by any commutative monoid.
Definition 9.10. Let S S S be a monoid. An S S S -act is a set X X X with a left S S S -action. We will write the action of s ∈ S s\in S s ∈ S on x ∈ X x\in X x ∈ X as s ⋅ x s\cdot x s ⋅ x . We write S S S -Act for the category of S S S -acts, where morphisms are functions that commute with the S S S -actions.
Of course, S S S -Act is the same as the presheaf category [ S , Set ] [S,\operatorname{Set}] [ S , Set ] , with S S S viewed as a one-object category. However, as discussed before, we will take a more algebraic perspective and the intended monoidal structure will be different from the cartesian closed structure we put on toposes (see Sections 9.2 and 9.3). We thus use different notation to emphasise the different perspective.
Definition 9.11. Let S S S be a commutative monoid. We define a tensor operation ⊗ \otimes ⊗ on S S S -acts as follows. Let A A A and B B B be S S S -acts. Define a binary relation ∼ \sim ∼ on A × B A\times B A × B by
( s ⋅ a , b ) ∼ ( a , s ⋅ b ) , (s\cdot a,b)\sim(a,s\cdot b), ( s ⋅ a , b ) ∼ ( a , s ⋅ b ) , and let ≈ \approx ≈ be the equivalence relation generated by ∼ \sim ∼ . We define the tensor of A A A and B B B to be the quotient
A ⊗ B : = ( A × B ) / ≈ , A\otimes B:=(A\times B)/\approx, A ⊗ B := ( A × B ) / ≈ , and we write a ⊗ b a\otimes b a ⊗ b for the equivalence class of ( a , b ) (a,b) ( a , b ) . The S S S -action on A ⊗ B A\otimes B A ⊗ B is given by s ⋅ ( a ⊗ b ) : = s ⋅ a ⊗ b = a ⊗ s ⋅ b s\cdot(a\otimes b):=s\cdot a\otimes b=a\otimes s\cdot b s ⋅ ( a ⊗ b ) := s ⋅ a ⊗ b = a ⊗ s ⋅ b .
This assignment is bifunctorial: for f : A → A ′ f:A\to A' f : A → A ′ and g : B → B ′ g:B\to B' g : B → B ′ we have a morphism
f ⊗ g : A ⊗ B → A ′ ⊗ B ′ , f\otimes g:A\otimes B\to A'\otimes B', f ⊗ g : A ⊗ B → A ′ ⊗ B ′ , a ⊗ b ↦ f ( a ) ⊗ g ( b ) . a\otimes b\mapsto f(a)\otimes g(b). a ⊗ b ↦ f ( a ) ⊗ g ( b ) .
The commutativity of S S S is needed so that A A A can also be viewed as a right S S S -act, and so the tensor actually makes sense.
Definition 9.12. Let S S S be a monoid. We define a functor [ − , − ] : S - A c t o p × S - A c t → S - A c t [-,-]\colon S\text{-}\mathbf{Act}^{\mathrm{op}} \times S\text{-}\mathbf{Act} \to S\text{-}\mathbf{Act} [ − , − ] : S - Act op × S - Act → S - Act as follows. For S S S -acts A A A and B B B we set
[ A , B ] = S - A c t ( A , B ) , [A,B] = S\text{-}\mathbf{Act}(A,B), [ A , B ] = S - Act ( A , B ) , and the S S S -action is pointwise. That is, for f : A → B f\colon A \to B f : A → B we let ( s ⋅ f ) : A → B (s \cdot f)\colon A \to B ( s ⋅ f ) : A → B be given by ( s ⋅ f ) ( a ) = s ⋅ f ( a ) (s \cdot f)(a) = s \cdot f(a) ( s ⋅ f ) ( a ) = s ⋅ f ( a ) . The functor’s action on morphisms is given by precomposition and postcomposition, respectively.
Proposition 9.13. Let S S S be a commutative monoid. The tuple ( S - A c t , ⊗ , S , [ − , − ] ) (S\text{-}\mathbf{Act}, \otimes, S, [-,-]) ( S - Act , ⊗ , S , [ − , − ]) , is a symmetric monoidal closed category. Here S S S acts on itself in the obvious way.
Proof. This is a straightforward, but lengthy, verification. It also follows from more general results, as the construction here is a specific instance of Day convolution [10 ] , for which the above conclusion is known. Alternatively, S S S -Act can be seen as the Eilenberg-Moore category of algebras for a commutative monad, so by [38 Corollary 2.5.7] the tuple in the statement is indeed symmetric monoidal closed.
Theorem 9.14. Let S S S be a commutative monoid. Then ( S - A c t , ⊗ , S , [ − , − ] ) (S\text{-}\mathbf{Act}, \otimes, S, [-,-]) ( S - Act , ⊗ , S , [ − , − ]) with the usual ( E , M ) : = ( epi , mono ) (\mathcal{E},\mathcal{M}) := (\textit{epi}, \textit{mono}) ( E , M ) := ( epi , mono ) factorisation system has the following properties:
(1) it is locally finitely presentable as a closed category,
(2) it is reduced product stable,
(3) it satisfies the ultraproduct covering property,
(4) the monoidal unit is projective.
Proof. The proof is mostly the same as Theorem 9.2, because S S S -Act is a presheaf category. We note the differences, which come from the different monoidal structure.
The monoidal unit is a representable presheaf (in fact, the only representable presheaf) and is thus finitely presentable and projective.
We are left to verify that finite powers commute with directed colimits, which was the point of this different monoidal structure. So let A A A be finitely presentable and let ( C i ) i ∈ I (C_i)_{i \in I} ( C i ) i ∈ I be a directed system. Then indeed we have
[ A , c o l i m i ∈ I C i ] ≅ c o l i m i ∈ I [ A , C i ] , [A,\mathop{\mathrm{colim}}_{i \in I} C_i] \cong\mathop{\mathrm{colim}}_{i \in I}[A,C_i], [ A , colim i ∈ I C i ] ≅ colim i ∈ I [ A , C i ] ,
as sets by definition of finite presentability, and it quickly follows that this is an isomorphism of S S S -acts.
The category of abelian groups and other CMon-categories
For this section we let V \mathcal{V} V be a symmetric monoidal closed category that is locally finitely presentable as a closed category and naturally enriched over C M o n \mathbf{CMon} CMon , the category of commutative monoids. The final requirement is equivalent to asking that V \mathcal{V} V has finite direct sums (that is, finite coproducts coincide with finite products). The prototypical example is A b \mathbf{Ab} Ab , the category of abelian groups, but we shall see other examples later.
On such a V \mathcal{V} V we can always choose the (strong epi, mono) factorisation system, which we now fix. As usual, since V \mathcal{V} V is locally finitely presentable as a closed category, it is reduced product ready (see Theorem 9.1). Moreover, since finite coproducts are absolute, they commute with (all limits and in particular) products, so that:
0 ≅ ∏ i ∈ J 0 and ∏ i ∈ J A i + ∏ i ∈ J B i ≅ ∏ i ∈ J ( A i + B i ) 0 \cong\prod_{i \in J} 0
\qquad\text{and}\qquad
\prod_{i \in J} A_i + \prod_{i \in J} B_i \cong\prod_{i \in J}(A_i + B_i) 0 ≅ i ∈ J ∏ 0 and i ∈ J ∏ A i + i ∈ J ∏ B i ≅ i ∈ J ∏ ( A i + B i )
for any set J J J and J J J -indexed families of objects. Now, given any ultrafilter U \mathcal{U} U on a set I I I , using the canonical isomorphism above and the fact that finite coproducts commute with directed colimits, it follows that
0 ≅ ∏ i ∈ I 0 / U and ∏ i ∈ I A i / U + ∏ i ∈ I B i / U ≅ ∏ i ∈ I ( A i + B i ) / U , 0 \cong\prod_{i \in I} 0/\mathcal{U}
\qquad\text{and}\qquad
\prod_{i \in I} A_i/\mathcal{U} + \prod_{i \in I} B_i/\mathcal{U} \cong\prod_{i \in I}(A_i + B_i)/\mathcal{U}, 0 ≅ i ∈ I ∏ 0/ U and i ∈ I ∏ A i / U + i ∈ I ∏ B i / U ≅ i ∈ I ∏ ( A i + B i ) / U ,
showing that V \mathcal{V} V satisfies the ultraproduct covering property.
It remains to give conditions on V \mathcal{V} V implying stability of strong epimorphisms under products; this would give that V \mathcal{V} V is also reduced product stable. This is certainly the case when V \mathcal{V} V is infinitary regular , as this readily implies that strong epimorphisms and regular epimorphisms coincide and are stable under products.
Recall from [4 Section 3.B] that V \mathcal{V} V is called a finitary quasivariety if it has a strong (and hence regular) generator made of finitely presentable and projective objects (that is, objects X X X for which V 0 ( X , − ) \mathcal{V}_0(X,-) V 0 ( X , − ) preserves directed colimits and regular epimorphisms). It is well known that finitary quasivarieties are locally finitely presentable and infinitary regular (see again [4 Section 3.B] or [20 Section 4] ).
In [20 Definition 4.11] a symmetric monoidal closed V \mathcal{V} V is called a symmetric monoidal finitary quasivariety if it is a finitary quasivariety, the monoidal unit I I I is finitely presentable, and the finitely presentable projective objects are closed under the monoidal product (note that I I I is not required to be projective).
Theorem 9.15. Let V \mathcal{V} V be a symmetric monoidal finitary quasivariety which is also CMon -enriched. Then V \mathcal{V} V , equipped with the (regular epi, mono) factorisation system, has the following properties:
it is locally finitely presentable as a closed category,
it is reduced product stable,
it satisfies the ultraproduct covering property.
Proof. Note that V \mathcal{V} V is locally finitely presentable as a closed category by [20 Remark 4.13] ; then everything follows by the arguments above. □ \square □
It follows that all the CMon -enriched examples of [20 ] , as well as all the examples of [21 Section 4.2] , fit this framework. Here we mention a few, where the monoidal structure is assumed to be the standard one:
the category CMon of commutative monoids;
the category Ab of abelian groups;
the category A b t f \mathbf{Ab}_{\mathrm{tf}} Ab tf of torsion free abelian groups;
for a commutative ring R R R , the categories R R R -Mod of R R R -modules, G G G -GR(Mod) of G G G -graded R R R -modules over an abelian group G G G , and DG (R R R -Mod ) of differentially graded R R R -modules;
more generally, for V \mathcal{V} V as in [21 Section 4.2] and any small compact closed V \mathcal{V} V -category C \mathcal{C} C , the category [ C , V ] 0 [\mathcal{C},\mathcal{V}]_0 [ C , V ] 0 of V \mathcal{V} V -functors and V \mathcal{V} V -natural transformations between them (with Day’s convolution).
In the examples above, the unit I I I is regular projective in all cases but that of differentially graded modules and possibly (5).
The category of small V \mathcal{V} V -categories
Let V \mathcal{V} V be a symmetric monoidal closed category, then so is the category V \mathcal{V} V -Cat of small V \mathcal{V} V -categories and V \mathcal{V} V -functors [17 Section 1.4] . The monoidal unit I I I is given by the V \mathcal{V} V -category with one single object ⋆ \star ⋆ and hom-object I ( ⋆ , ⋆ ) = I I(\star,\star)=I I ( ⋆ , ⋆ ) = I . The tensor product A ⊗ B \mathcal{A}\otimes\mathcal{B} A ⊗ B of two V \mathcal{V} V -categories has Ob ( A ) × Ob ( B ) \operatorname{Ob}(\mathcal{A})\times\operatorname{Ob}(\mathcal{B}) Ob ( A ) × Ob ( B ) as set of objects, and
A ⊗ B ( ( A , B ) , ( A ′ , B ′ ) ) : = A ( A , A ′ ) ⊗ B ( B , B ′ ) \mathcal{A}\otimes\mathcal{B}((A,B),(A',B')):=\mathcal{A}(A,A')\otimes\mathcal{B}(B,B') A ⊗ B (( A , B ) , ( A ′ , B ′ )) := A ( A , A ′ ) ⊗ B ( B , B ′ )
as hom-objects (see [17 ] for details).
If we assume moreover that V \mathcal{V} V is locally finitely presentable as a closed category, then so is the category V \mathcal{V} V -Cat by [19 Proposition 4.8] .
Regarding factorisation systems, we have a few choices:
(i) (surjective on objects, injective on objects and fully faithful);
(ii) (strong epi, mono);
(iii) (epi, strong mono).
In (i) and (ii) M \mathcal{M} M is closed under directed colimits, so that V \mathcal{V} V -Cat is reduced product ready (Theorem 9.1). The class E \mathcal{E} E is closed under products in (i), so for this choice V \mathcal{V} V -Cat is reduced product stable; moreover the unit is E \mathcal{E} E -projective.
Remark 9.16. Note that there is also the factorisation system (bijective on objects, fully faithful), but since fully faithful morphisms are not necessarily monomorphic, this is not of interest for us.
We now focus on the ultraproduct covering property. The initial object in V \mathcal{V} V -Cat is the V \mathcal{V} V -category with no objects. As such it forms a strictly initial object; hence the first part of the ultraproduct covering property holds by Theorem 4.4.
Next, recall that given V \mathcal{V} V -categories A , B \mathcal{A},\mathcal{B} A , B , their coproduct A + B \mathcal{A}+\mathcal{B} A + B in V \mathcal{V} V -Cat has the disjoint union of the objects of A \mathcal{A} A and of B \mathcal{B} B as set of objects and
( A + B ) ( X , Y ) = { A ( X , Y ) if X , Y ∈ A , B ( X , Y ) if X , Y ∈ B , 0 otherwise. (\mathcal{A}+\mathcal{B})(X,Y)=
\begin{cases}
\mathcal{A}(X,Y) & \text{if } X,Y\in\mathcal{A},\\
\mathcal{B}(X,Y) & \text{if } X,Y\in\mathcal{B},\\
0 & \text{otherwise.}
\end{cases} ( A + B ) ( X , Y ) = ⎩ ⎨ ⎧ A ( X , Y ) B ( X , Y ) 0 if X , Y ∈ A , if X , Y ∈ B , otherwise.
We also fix the following notation for an object G ∈ V G\in\mathcal{V} G ∈ V : the V \mathcal{V} V -category 2 G 2_G 2 G has two objects x , y x,y x , y and only non-trivial hom 2 G ( x , y ) : = G 2_G(x,y):=G 2 G ( x , y ) := G .
Proposition 9.17. Assume that in V \mathcal{V} V the initial object 0 0 0 is subterminal; that is, for any object X X X there is at most one arrow X → 0 X\to0 X → 0 . For any ultrafilter U \mathcal{U} U on a set I I I , and families ( A i ) i ∈ I (\mathcal{A}_i)_{i\in I} ( A i ) i ∈ I and ( B i ) i ∈ I (\mathcal{B}_i)_{i\in I} ( B i ) i ∈ I of V \mathcal{V} V -categories the comparison V \mathcal{V} V -functor
ρ : ∏ i ∈ I A i / U + ∏ i ∈ I B i / U ⟶ ∏ i ∈ I ( A i + B i ) / U \rho:\prod_{i\in I}\mathcal{A}_i/\mathcal{U}+\prod_{i\in I}\mathcal{B}_i/\mathcal{U}\longrightarrow\prod_{i\in I}(\mathcal{A}_i+\mathcal{B}_i)/\mathcal{U} ρ : i ∈ I ∏ A i / U + i ∈ I ∏ B i / U ⟶ i ∈ I ∏ ( A i + B i ) / U is bijective on objects and a strong epimorphism. In particular ρ \rho ρ lies in E \mathcal{E} E for any of the factorisation systems mentioned above and thus V \mathcal{V} V -Cat satisfies the ultraproduct covering property.
Proof. We have already observed that V \mathcal{V} V -Cat has a strict initial objects, so to show the ultraproduct covering property it is really enough to prove the conditions about ρ \rho ρ . Fix a strong generator G G G of V \mathcal{V} V made of finitely presentable objects; by [19 Proposition 4.7] the family { 2 G } G ∈ G \{2_G\}_{G\in\mathcal{G}} { 2 G } G ∈ G is a strong generator for V \mathcal{V} V -Cat made of finitely presentable V \mathcal{V} V -categories. To prove that ρ \rho ρ is a strong epimorphism we apply Theorem 2.7.
Fix then G ∈ G G\in\mathcal{G} G ∈ G and a V \mathcal{V} V -functor F : 2 G → ∏ i ∈ I ( A i + B i ) / U F:2_G\to\prod_{i\in I}(\mathcal{A}_i+\mathcal{B}_i)/\mathcal{U} F : 2 G → ∏ i ∈ I ( A i + B i ) / U . By finite presentability there exists J ∈ U J\in\mathcal{U} J ∈ U such that F F F factors as F J : 2 G → ∏ j ∈ J ( A j + B j ) F_J:2_G\to\prod_{j\in J}(\mathcal{A}_j+\mathcal{B}_j) F J : 2 G → ∏ j ∈ J ( A j + B j ) , which is then determined by a family of V \mathcal{V} V -functors
F j : 2 G → A j + B j F_j:2_G\to\mathcal{A}_j+\mathcal{B}_j F j : 2 G → A j + B j
for j ∈ J j\in J j ∈ J . By definition of 2 G 2_G 2 G each F j F_j F j is determined by the choice of two objects X j , Y j X_j,Y_j X j , Y j in A j + B j \mathcal{A}_j+\mathcal{B}_j A j + B j and an arrow
f j : G → ( A j + B j ) ( X j , Y j ) f_j:G\to(\mathcal{A}_j+\mathcal{B}_j)(X_j,Y_j) f j : G → ( A j + B j ) ( X j , Y j )
in V \mathcal{V} V . We can write J J J as the (disjoint) union of the following sets:
J 1 : = { j ∈ J ∣ X j , Y j ∈ A j } J_1:=\{j\in J\mid X_j,Y_j\in\mathcal{A}_j\} J 1 := { j ∈ J ∣ X j , Y j ∈ A j } ;
J 2 : = { j ∈ J ∣ X j , Y j ∈ B j } J_2:=\{j\in J\mid X_j,Y_j\in\mathcal{B}_j\} J 2 := { j ∈ J ∣ X j , Y j ∈ B j } ;
J 3 : = { j ∈ J ∣ X j ∈ A j , Y j ∈ B j } J_3:=\{j\in J\mid X_j\in\mathcal{A}_j,\ Y_j\in\mathcal{B}_j\} J 3 := { j ∈ J ∣ X j ∈ A j , Y j ∈ B j } ;
J 4 : = { j ∈ J ∣ X j ∈ B j , Y j ∈ A j } J_4:=\{j\in J\mid X_j\in\mathcal{B}_j,\ Y_j\in\mathcal{A}_j\} J 4 := { j ∈ J ∣ X j ∈ B j , Y j ∈ A j } .
By the ultrafilter properties exactly one of these lies in U \mathcal{U} U . We treat only the cases were J 1 J_1 J 1 or J 3 J_3 J 3 are in U \mathcal{U} U since the other two are symmetric. Suppose that J 1 ∈ U J_1\in\mathcal{U} J 1 ∈ U , then we can define a V \mathcal{V} V -functor
F ~ : 2 G → F J 1 ∏ j ∈ J 1 A j → a J 1 ∏ i ∈ I A i / U → ι 1 ∏ i ∈ I A i / U + ∏ i ∈ I B i / U \widetilde{F}:2_G\xrightarrow{F_{J_1}}\prod_{j\in J_1}\mathcal{A}_j\xrightarrow{a_{J_1}}\prod_{i\in I}\mathcal{A}_i/\mathcal{U}\xrightarrow{\iota_1}\prod_{i\in I}\mathcal{A}_i/\mathcal{U}+\prod_{i\in I}\mathcal{B}_i/\mathcal{U} F : 2 G F J 1 j ∈ J 1 ∏ A j a J 1 i ∈ I ∏ A i / U ι 1 i ∈ I ∏ A i / U + i ∈ I ∏ B i / U
where a J 1 a_{J_1} a J 1 is the coprojection and ι 1 \iota_1 ι 1 is the first coproduct inclusion, while F J 1 F_{J_1} F J 1 sends x x x to ( X j ) j ∈ J 1 (X_j)_{j\in J_1} ( X j ) j ∈ J 1 , y y y to ( Y j ) j ∈ J 1 (Y_j)_{j\in J_1} ( Y j ) j ∈ J 1 , and with action on the homs
( f j ) j ∈ J 1 : G → ( ∏ j ∈ J 1 A j ) ( ( X j ) j ∈ J 1 , ( Y j ) j ∈ J 1 ) . (f_j)_{j\in J_1}:G\to\left(\prod_{j\in J_1}\mathcal{A}_j\right)((X_j)_{j\in J_1},(Y_j)_{j\in J_1}). ( f j ) j ∈ J 1 : G → j ∈ J 1 ∏ A j (( X j ) j ∈ J 1 , ( Y j ) j ∈ J 1 ) .
One can easily conclude that ρ ∘ F ~ = F \rho\circ\widetilde{F}=F ρ ∘ F = F . Suppose now that J 3 ∈ U J_3\in\mathcal{U} J 3 ∈ U , then we can define a V \mathcal{V} V -functor
F ~ : 2 G → F J 3 ∏ j ∈ J 3 A j + ∏ j ∈ J 3 B j → a J 3 + b J 3 ∏ i ∈ I A i / U + ∏ i ∈ I B i / U \widetilde{F}:2_G\xrightarrow{F_{J_3}}\prod_{j\in J_3}\mathcal{A}_j+\prod_{j\in J_3}\mathcal{B}_j\xrightarrow{a_{J_3}+b_{J_3}}\prod_{i\in I}\mathcal{A}_i/\mathcal{U}+\prod_{i\in I}\mathcal{B}_i/\mathcal{U} F : 2 G F J 3 j ∈ J 3 ∏ A j + j ∈ J 3 ∏ B j a J 3 + b J 3 i ∈ I ∏ A i / U + i ∈ I ∏ B i / U
where a J 3 a_{J_3} a J 3 and b J 3 b_{J_3} b J 3 are the coprojections, while F J 3 F_{J_3} F J 3 sends x x x to ( X j ) j ∈ J 3 ∈ ∏ j ∈ J 3 A j (X_j)_{j\in J_3}\in\prod_{j\in J_3}\mathcal{A}_j ( X j ) j ∈ J 3 ∈ ∏ j ∈ J 3 A j , y y y to ( Y j ) j ∈ J 3 ∈ ∏ j ∈ J 3 B j (Y_j)_{j\in J_3}\in\prod_{j\in J_3}\mathcal{B}_j ( Y j ) j ∈ J 3 ∈ ∏ j ∈ J 3 B j , and with action on the homs
G → f 0 = ( ∏ j ∈ J 3 A j + ∏ j ∈ J 3 B j ) ( ( X j ) j ∈ J 3 , ( Y j ) j ∈ J 3 ) , G\xrightarrow{f}0=\left(\prod_{j\in J_3}\mathcal{A}_j+\prod_{j\in J_3}\mathcal{B}_j\right)((X_j)_{j\in J_3},(Y_j)_{j\in J_3}), G f 0 = j ∈ J 3 ∏ A j + j ∈ J 3 ∏ B j (( X j ) j ∈ J 3 , ( Y j ) j ∈ J 3 ) ,
@page 36/40 starts_mid=0 ends_mid=1 where f f f is the unique arrow G → 0 G \to0 G → 0 . This arrow exists, as witnessed by f j f_j f j for any j ∈ J 3 j \in J_3 j ∈ J 3 and is unique by the assumption on 0 0 0 . It is easy to see that ρ ∘ F ~ = F \rho\circ\widetilde{F} = F ρ ∘ F = F .
To show that ρ \rho ρ is bijective on objects it is enough to observe that Ob : V -Cat → Set \operatorname{Ob}\colon\mathcal{V}\text{-Cat} \to\operatorname{Set} Ob : V -Cat → Set is continuous and cocontinuous (see for instance [19 Section 5] ) and that ρ \rho ρ is a bijection when taking ultraproducts of sets. □ \square □
Remark 9.18. If in V \mathcal{V} V every arrow out of the initial object is a monomorphism, then one can show that ρ \rho ρ is moreover faithful (the hom components are monomorphisms) and hence an isomorphism of V \mathcal{V} V -categories (being both a monomorphism and a strong epimorphism).
If V \mathcal{V} V has a strict initial object this follows from Theorem 8.2 since one can easily check that the family { 2 G } G ∈ G \{2_G\}_{G \in\mathcal{G}} { 2 G } G ∈ G considered in the proof is a strong generator of finitely presentable and connected objects. However, this does not cover for instance the case of V = Ab \mathcal{V} = \operatorname{Ab} V = Ab .
Summarising we obtain the following.
Theorem 9.19. Let V \mathcal{V} V be locally finitely presentable as a closed category and such that the initial object is subterminal. Then V -Cat \mathcal{V}\text{-Cat} V -Cat , equipped with one of the factorisation systems (i)–(iii) has the following properties:
(1) it is locally finitely presentable as a closed category,
(2) it is reduced product ready,
(3) it satisfies the ultraproduct covering property.
If the given factorisation system is (i), then V -Cat \mathcal{V}\text{-Cat} V -Cat is also reduced product stable and the unit is E \mathcal{E} E -projective.
Example 9.20. Examples of bases of enrichment that can be obtained via this procedure include:
the category Set \operatorname{Set} Set , by taking V = 1 \mathcal{V} = 1 V = 1 the singleton category;
the category Prd \operatorname{Prd} Prd of preorders, by enriching over V = { 0 , 1 } \mathcal{V} = \{0,1\} V = { 0 , 1 } with truncated addition as monoidal structure;
the category Ab -Cat \operatorname{Ab}\text{-Cat} Ab -Cat of small preadditive categories;
the category Cat \operatorname{Cat} Cat of small categories, by enriching over Set \operatorname{Set} Set ;
the category n -Cat n\text{-Cat} n -Cat of small n n n -categories, by enriching on ( n − 1 ) -Cat (n-1)\text{-Cat} ( n − 1 ) -Cat (this is obtained recursively starting from the previous point).
Example 9.21. In the context of 2-categories, the paper [12 ] introduces the fragment isoregular logic of enriched regular logic over V = Cat \mathcal{V} = \operatorname{Cat} V = Cat with the (strong epi, mono) factorisation system. Its aim is to define a logical framework to present categories with structures defined by universal properties.
If we extend isoregular logic by allowing finite disjunctions, Theorem 9.19 tells us that the ultraproduct covering property holds. Moreover, since isoregular logic is defined to involve only those strong epimorphisms in Cat \operatorname{Cat} Cat which are surjective equivalences , and these are stable under products, it is easy to see that all the results that involve reduced product stability also apply to this context.
The category of posets
Let us fix as base of enrichment the cartesian closed category Pos \operatorname{Pos} Pos of partially ordered sets. This is well known to be locally finitely presentable as a closed category, so that conditions (1) and (2) of Theorem 3.3 are automatically satisfied (see Theorem 9.1).
We have two choices of meaningful factorisation systems on Pos \operatorname{Pos} Pos .
The (surjective, embedding) factorisation system, which coincides with the (epi, strong mono) one. Here, a surjection is simply an order preserving map that is surjective as a function, and an embedding is injective morphism of posets that reflects the order relation.
The (strong epi, mono) factorisation system. See [37 Examples A.2(2)] for an explicit description and the fact that strong epimorphisms coincide with regular epimorphisms and are stable under products.
In both cases the class M \mathcal{M} M is closed under directed colimits and E \mathcal{E} E is closed under products, making V \mathcal{V} V reduced product stable. The unit 1 1 1 is E \mathcal{E} E -projective in both cases. Moreover, the poset
2 : = { < } \mathbb{2} := \{\,{<}\,\} 2 := { < }
is a finitely presentable and connected object and forms a strong generator of Pos; thus the ultraproduct covering property holds for both factorisation systems by Theorem 8.2 .
We have thus proved the following.
Theorem 9.22. The cartesian closed category Pos of posets equipped with either the (surjective, embedding) or the (strong epi, mono) factorisation system, has the following properties:
(1) it is locally finitely presentable as a closed category,
(2) it is reduced product stable,
(3) it satisfies the ultraproduct covering property;
(4) the unit is E \mathcal{E} E -projective.
The category of pseudometric spaces
Also of interest in theoretical computer science, especially in quantitative reasoning, is enrichment over the category Met of (generalised) metric spaces and contractions. As we show in the next section, this is not suitable for us since directed colimits do not commute with finite limits (making Met not reduced product ready). This problem vanishes if we replace metric spaces with pseudometric spaces.
Definition 9.23. A (generalised) pseudometric space is the data of a set X X X together with a distance d : X × X → [ 0 , ∞ ] d: X \times X \to[0,\infty] d : X × X → [ 0 , ∞ ] which is symmetric, satisfies the triangular inequality, and such that d ( x , x ) = 0 d(x,x)=0 d ( x , x ) = 0 for any x ∈ X x \in X x ∈ X . We denote by PMet the category of pseudometric spaces and contractions.
We do not require that if d ( x , y ) = 0 d(x,y)=0 d ( x , y ) = 0 then x = y x=y x = y ; that would make a pseudometric space into a metric space.
The category PMet is locally ℵ 1 \aleph_1 ℵ 1 -presentable and the forgetful functor PMet → \to → Set is both continuous and cocontinuous [5 Example 2.3(4)] . The same proof as that appearing in [2 Example 2.2(5)] shows that the finitely presentable pseudometric spaces are exactly the finite discrete spaces (that is, those finite spaces for which d ( x , y ) = ∞ d(x,y)=\infty d ( x , y ) = ∞ whenever x ≠ y x \ne y x = y ); these are exactly the finite coproducts of the terminal object. (Note that since finite discrete spaces are not a strong generator, this implies that PMet is not locally finitely presentable.)
The monoidal closed structure which is usually considered on Met (see e.g., [5 Remark 2.2] ) extends with no changes to PMet. The monoidal unit is given by the terminal object 1, and for any X , Y ∈ P M e t X,Y \in\mathrm{PMet} X , Y ∈ PMet we define X ⊗ Y : = ( X × Y , d X ⊗ Y ) X \otimes Y := (X \times Y,d_{X\otimes Y}) X ⊗ Y := ( X × Y , d X ⊗ Y ) where
d X ⊗ Y ( ( x , y ) , ( x ′ , y ′ ) ) = d X ( x , x ′ ) + d Y ( y , y ′ ) . d_{X\otimes Y}((x,y),(x',y'))=d_X(x,x')+d_Y(y,y'). d X ⊗ Y (( x , y ) , ( x ′ , y ′ )) = d X ( x , x ′ ) + d Y ( y , y ′ ) .
The internal hom is defined by [ X , Y ] : = ( P M e t ( X , Y ) , d [ X , Y ] ) [X,Y] := (\mathrm{PMet}(X,Y),d_{[X,Y]}) [ X , Y ] := ( PMet ( X , Y ) , d [ X , Y ] ) where
d [ X , Y ] ( f , g ) = sup x ∈ X d Y ( f ( x ) , g ( x ) ) . d_{[X,Y]}(f,g)=\sup_{x\in X}d_Y(f(x),g(x)). d [ X , Y ] ( f , g ) = x ∈ X sup d Y ( f ( x ) , g ( x )) .
Directed colimits commute with finite limits in PMet. The case of products is treated in [2 Lemma 3.7] (there the distance takes value in [ 0 , 1 ] [0,1] [ 0 , 1 ] , but the proof does not change). Commutation with equalisers follows easily from the fact that these are computed in PMet as in Set via isometric subspaces, and isometries are stable under directed colimits. As for finite powers, since the finitely presentable objects are finite discrete spaces, powers by them are just finite products (of the same object multiple times) and as such commute with directed colimits.
Like in Met, we have two factorisation systems of interest:
In both cases the class E \mathcal{E} E is closed under products and M \mathcal{M} M under directed colimits. Moreover the monoidal unit 1 is an E \mathcal{E} E -generator with respect to both factorisation systems, and E \mathcal{E} E -projective with respect to the first. It follows by Theorem 8.3 that PMet satisfies the ultraproduct covering property.
Summarising, even though PMet is not locally finitely presentable, we have shown the following.
Theorem 9.24. The symmetric monoidal closed category PMet equipped with either the (surjective, isometry) or the (dense, closed isometry) factorisation system, has the following properties:
(1) it is reduced product stable,
(2) it satisfies the ultraproduct covering property,
(3) the monoidal unit is finitely presentable and finitely presentable objects are closed under the monoidal product,
(4) the monoidal unit is E \mathcal{E} E -projective with respect to the first factorisation system.
Non-examples and counterexamples
Enrichment over the cartesian closed category ω \omega ω -CPO, of ω \omega ω -complete partial orders, is of interest in theoretical computer science and its logic has been studied for instance in [3 ] . However, finitary enriched logic does not seem to behave nicely in this context. Indeed, ω \omega ω -CPO is known not to be locally finitely presentable and, in addition, finite limits do not commute with directed colimits as shown in the example below. Thus it is not even reduced product ready.
Example 9.25. Consider the ω \omega ω -complete poset ω + 1 = { 0 < 1 < ⋯ < ω } \omega+1=\{0<1<\cdots<\omega\} ω + 1 = { 0 < 1 < ⋯ < ω } , and for any natural n > 0 n>0 n > 0 the object P n = { 0 < 1 < ⋯ < n < ∞ } P_n=\{0<1<\cdots<n<\infty\} P n = { 0 < 1 < ⋯ < n < ∞ } . These, ordered by inclusion, form a directed family whose colimit is ω + 2 = { 0 < 1 < ⋯ < ω < ∞ } \omega+2=\{0<1<\cdots<\omega<\infty\} ω + 2 = { 0 < 1 < ⋯ < ω < ∞ } .
Consider, for n > 0 n>0 n > 0 , the ω \omega ω -complete poset Q n Q_n Q n obtained by adding to ω + 1 \omega+1 ω + 1 an element n ‾ \overline{n} n such that n < n ‾ < ω n<\overline{n}<\omega n < n < ω , but n ‾ \overline{n} n is not comparable with any other n < k < ω n<k<\omega n < k < ω . These form a directed family where Q n → Q n + 1 Q_n\to Q_{n+1} Q n → Q n + 1 fixes ω + 1 \omega+1 ω + 1 and sends n ‾ \overline{n} n to n + 1 n+1 n + 1 . The colimit of this in ω \omega ω -CPO is still ω + 1 \omega+1 ω + 1 (since, in such a colimit n ‾ ∼ n + 1 \overline{n}\sim n+1 n ∼ n + 1 and ω = sup n n ≤ sup n n ‾ ≤ ω \omega=\sup_n n\leq\sup_n\overline{n}\leq\omega ω = sup n n ≤ sup n n ≤ ω , so also n ‾ ∼ ω \overline{n}\sim\omega n ∼ ω ).
Now, for any n n n let f n , g n : P n → Q n f_n,g_n:P_n\to Q_n f n , g n : P n → Q n be defined by f n ( k ) = g n ( k ) = k f_n(k)=g_n(k)=k f n ( k ) = g n ( k ) = k for any k ≤ n k\leq n k ≤ n , f n ( ∞ ) = ω f_n(\infty)=\omega f n ( ∞ ) = ω , and g n ( ∞ ) = n ‾ g_n(\infty)=\overline{n} g n ( ∞ ) = n . It is easy to see that f n f_n f n and g n g_n g n are natural with respect to the directed diagrams.
When taking the directed colimit, the maps f ∞ f_\infty f ∞ and g ∞ g_\infty g ∞ coincide both with the map ω + 2 → ω + 1 \omega+2\to\omega+1 ω + 2 → ω + 1 which is the identity on the natural numbers and sends ω \omega ω and ∞ \infty ∞ to ω \omega ω . Thus the equaliser of the directed colimit trivialises, returning ω + 2 \omega+2 ω + 2 .
Given n ∈ N n\in\mathbb{N} n ∈ N , the equaliser of f n f_n f n and g n g_n g n coincides with { 0 < 1 < ⋯ < n } \{0<1<\cdots<n\} { 0 < 1 < ⋯ < n } . Therefore, the directed colimit of the equalisers coincides with ω + 1 \omega+1 ω + 1 (it would be ω \omega ω in P o s \mathbf{Pos} Pos , but since we are in ω \omega ω -CPO we need to add a top element).
It follows that equalisers do not commute with directed colimits.
The same problem arises for the categories M e t \mathbf{Met} Met and C M e t \mathbf{CMet} CMet of (generalised) metric spaces and complete metric spaces respectively, with contractions as arrows: finite limits do not commute with directed colimits.
Example 9.26 ([34 Remark 2.3] ). Given ε ∈ ( 0 , ∞ ] \varepsilon\in(0,\infty] ε ∈ ( 0 , ∞ ] , denote by 2 ε 2_\varepsilon 2 ε the metric space with two points of distance ε \varepsilon ε . Both in M e t \mathbf{Met} Met and C M e t \mathbf{CMet} CMet we can consider the monomorphisms
2 ∞ ⟶ 2 1 / n , 2_\infty\longrightarrow2_{1/n}, 2 ∞ ⟶ 2 1/ n , for n ∈ N n\in\mathbb{N} n ∈ N , given by the identity on the two elements. These form a directed family indexed on the natural numbers whose colimit is the unique map
2 ∞ ⟶ 1 , 2_\infty\longrightarrow1, 2 ∞ ⟶ 1 , which is not a monomorphism.
(Mark Kamsma) Department of Mathematics and Statistics, Masaryk University, Faculty of Sciences, Kotlářská 2, 611 37, Brno, Czech Republic URL: https://markkamsma.nl Email address: mark@markkamsma.nl
(Giacomo Tendas) Department of Mathematics, University of Manchester, Faculty of Science and Engineering, Alan Turing Building, M13 9PL Manchester, UK Email address: giacomo.tendas@manchester.ac.uk