# «COMPACTNESS AND ¨ LOWENHEIM–SKOLEM PROPERTIES IN CATEGORIES OF PRE-INSTITUTIONS ANTONINO SALIBRA University of Pisa, Dip. Informatica Corso Italia ...»

(i) I is adequately expressive for I, written I I, iﬀ there exists an adequate pre-institution transformation T : I → I.

(ii) I is fully expressive for I, written I I, iﬀ there exists a fully adequate pre-institution transformation T : I → I.

Clearly, and are pre-orders, which fact justiﬁes the following Definition 2.8. Let I and I be two pre-institutions.

(i) I and I have equivalent expressiveness iﬀ I I and I I.

(ii) I and I have fully equivalent expressiveness iﬀ I I and I I.

The formal notions of relative expressiveness introduced above are ﬁrst approximations to an appropriate generalization of classical notions of relative expressiveness of logical systems in the sense of abstract model theory (see [6]).

These systems have the limitation of being based on ﬁrst-order models; as a consequence, also the category of (ﬁrst-order) signatures is ﬁxed for all logical systems.

Our notions are more liberal in that only a functor is required between the signature categories, and model-independence is achieved in a most general manner.

To clarify this comparison, we show how a most classical notion of relative expressiveness between logical systems can be captured by a particular transformation of the corresponding pre-institutions.

74 A. SALIBRA AND G. SCOLLO Example 2.9. If L is a logical system in the sense of abstract model theory, a corresponding pre-institution IL = (Sig, Sen, Mod, ) is deﬁned as follows: Sig is the category of ﬁrst-order signatures having only renamings (5 ) as morphisms;

**Sen gives for every Σ ∈ Sig the set of Σ-sentences in L, and for every renaming τ :**

Σ1 → Σ2 ∈ Sig the corresponding translation of Σ1 -sentences into Σ2 -sentences;

Mod gives for every Σ ∈ Sig the class of ﬁrst-order Σ-models, and for every renaming τ : Σ1 → Σ2 ∈ Sig the corresponding ﬁrst-order reduction map, which turns each Σ2 -model into a Σ1 -model; ﬁnally, satisfaction in IL coincides with satisfaction in L.

Now, let L, L be logical systems in the sense of abstract model theory. According to [6] (p. 194, Deﬁnition 1.2), and [5] (p. 27, Deﬁnition 1.1.1), L is at least as strong as L, which is written L ≤ L, iﬀ for every ﬁrst-order signature Σ, for every Σ-sentence ϕ in L there is some Σ-sentence ψ ∈ L that has the same models. Let IL, IL be the pre-institutions that respectively correspond to L, L.

A transformation T : IL → IL which captures the classical notion of relative expressiveness mentioned above is as follows: whenever L ≤ L, deﬁne ET = {ψ | ∃ϕ ∈ E : Mod(ϕ) = Mod (ψ)}, MT = {M }.

ΣT = Σ, It is easy to see (using Lemma 2.6) that T is a fully adequate transformation.

Besides serving an illustrative purpose, the example also points at the aforementioned target of our present investigation, that is, an appropriate generalization of classical notions of relative expressiveness of logical systems in the sense of abstract model theory.

The classical notion recalled above has classical generalizations that have great

**methodological importance, and thus high relevance to our investigation. We recall (see Section 3.1 in [5]) that the above notion can also be stated as follows:**

L ≤ L iﬀ every elementary class in L is elementary in L (where a model class is elementary in L iﬀ it consists of the models of a sentence in L).

A classical generalization of the aforementioned notion of relative expressiveness is the following: L ≤RPC L iﬀ every relativized projective class in L is a relativized projective class in L (where a model class is a relativized projective class in L iﬀ it consists of the relativized τ -reducts of the models of an elementary class in L, for some signature inclusion morphism τ (6 )).

Now, the main methodological import of the ≤RPC notion lies not so much in its technical deﬁnition as in the reduction scheme that comes along with it, meaning: downward inheritance of model-theoretic properties along the expressiveness ordering. Under the ≤RPC ordering, the scheme holds for a great variety of model-theoretic properties, including compactness and L¨wenheim–Skolem o properties—to which we restrict our attention in the present paper.

(5 ) That is, bijective arity-preserving maps.

(6 ) If τ : Σ1 → Σ2 is a ﬁrst-order signature inclusion morphism and M is a ﬁrst-order Σ2 -structure, a relativized τ -reduct of M is any Σ1 -substructure of a τ -reduct of M.

## PRE-INSTITUTIONS

We are thus in presence of a criterion to measure the “appropriateness” of generalizations of classical notions of relative expressiveness to our framework, viz. the extent to which reductions generalize. To be applicable, this criterion preliminarily requires, for each model-theoretic property under consideration, the reformulation of that property within our conceptual framework. Now, in the case of L¨wenheim–Skolem properties, we defer this task to Section 7 (as we o mentioned in Section 1, a structural enrichment of the notion of pre-institution is necessary). On the contrary, the reformulation of compactness for pre-institutions is fairly obvious, as it appears from the next deﬁnition.R e m a r k. The two notions of compactness are equivalent for pre-institutions that are closed under negation (see [6], p. 196, Lemma 2.1), where I is closed

**under negation whenever ∀Σ ∈ Sig, ∀ϕ ∈ Sen(Σ), ∃ψ ∈ Sen(Σ): ∀M ∈ Mod(Σ):**

M ϕ iﬀ not M ψ.

Since ﬁniteness of (sub-)presentations plays an essential rˆle in both notions of o compactness, one may expect that “suitable” pre-institution transformations for such notions ought to preserve that ﬁniteness somehow. The basic, most intuitive idea is that every sentence should be transformed into a ﬁnite set of sentences.

This idea is aﬀected by too much of “syntax”, though, in the following sense.

If one accepts the abstract model-theoretic purpose proposed in [11], that is “to get away from the syntactic aspects of logic completely and to study classes of structures more in the spirit of universal algebra” then two softenings of the basic idea are in place. First, “ﬁniteness” of the transform ϕT of any sentence ϕ should be measured excluding the “tautological” part of ϕT (“tautological” relative to T, in a sense made precise below), since model classes are insensitive to tautologies.

Second, and more generally in fact, “ﬁniteness” of sentence transformation should only be “up to logical equivalence” in the target pre-institution, since logically equivalent sentences specify identical model classes.

The following deﬁnition tells, for a given pre-institution transformation, which sentences of the target pre-institution are “viewed as tautologies” in the source pre-institution; we are thus considering a sort of “stretching” of the classical notion of tautology along the transformation arrow. The subsequent deﬁnition, then, formalizes the two “soft” forms of the property we are looking for, according to the rationale given above.

76 A. SALIBRA AND G. SCOLLO Definition 2.11. Let T : I → I be a pre-institution transformation, with I,

**I as in Deﬁnition 2.3. Then, for every Σ ∈ Sig:**

(i) a ΣT -sentence ψ is a T -tautology iﬀ ∀M ∈ Mod(Σ), ∀M ∈ MT : M ψ, (ii) TautT (Σ) is the set of T -tautologies in Sen(ΣT ).

Clearly, every ΣT -tautology (in the classical sense) is in TautT (Σ). This may contain more sentences, however; e.g. if ∅Σ is the “empty” Σ-presentation, then clearly (∅Σ )T ⊆ TautT (Σ), and the sentences in (∅Σ )T need not be ΣT - tautologies.

Definition 2.12. Let T : I → I be a pre-institution transformation, with I, I as in Deﬁnition 2.3.

(i) T is ﬁnitary iﬀ ∀Σ ∈ Sig, ∀ϕ ∈ Sen(Σ): ϕT − TautT (Σ) ﬁnite.

(ii) T is quasi-ﬁnitary iﬀ ∀Σ ∈ Sig, ∀ϕ ∈ Sen(Σ): (ϕT − TautT (Σ))/ ≡I ﬁnite.

The diﬀerence between ﬁnitarity and quasi-ﬁnitarity is illustrated by the transformation in Example 2.9, which is quasi-ﬁnitary but not necessarily ﬁnitary.

Finally, our last deﬁnition relates to equivalence of expressiveness between preinstitutions. If two pre-institutions enjoy equivalent expressiveness, it is sensible to wonder whether the transformations that establish the equivalence are “inverse” to each other in some sense. Among the several possibilities for such a sense, we formalize a notion of equivalence that requires the transformation of logical theories to be the identity; more precisely, the presentation obtained by applying such a transformation and then its inverse to any given presentation is required to have exactly the same consequences as the original presentation. As usual, if E is a Σ-presentation, Th(E) denotes the closure of E under consequence, whereas if M is a Σ-model, then Th(M ) denotes the largest Σ-presentation that is satisﬁed by M.

Definition 2.13. Let T : I → I be a pre-institution transformation, with I, I as in Deﬁnition 2.3. T is invertible if there exists a pre-institution transformation R : I → I such that for every presentation E in I: Th(E) = Th((ET )R ), in which case R is termed an inverse of T, and the two pre-institutions I, I have exactly equivalent expressiveness.

As a simple illustration, with reference to Example 2.9, it is easily seen that if L ≤ L and L ≤ L, then the transformation T : IL → IL is invertible (in fact, it has a fully adequate inverse), i.e. IL and IL have exactly equivalent expressiveness.

3. Basic facts. In this section, we recall a number of facts and results from [18], which complete the background needed for the further analysis and results presented in this paper. The interested reader is referred to Sections 3 and 4 of [18] for the proofs of the facts recalled here.

## PRE-INSTITUTIONS

(iii) T ◦ T is adequate if both T and T are adequate.

(iv) T ◦ T is fully adequate if both T and T are fully adequate.

(v) Pre-institutions, together with transformations as morphisms, form a category PT, of which a subcategory APT is obtained by taking only adequate transformations as morphisms, of which a subcategory FAPT is obtained by taking only fully adequate transformations as morphisms.

The following fact shows that pre-institution transformations ensure “contravariant” inheritance of the rps and eps properties. This fact seems to be only the ﬁrst phenomenon of a wealthy situation; the compactness theorem (see below) is another such case. Inheritance is “contravariant” in the sense that, if T : I → I is a pre-institution transformation and I has the property under consideration, then I has that property as well.

These results demonstrate the usefulness of our notion of transformation, in that they support interesting proof techniques. For example, if a proof of a certain theorem in a pre-institution I is sought, and the theorem is known to hold in a pre-institution I, it will suﬃce to ﬁnd a transformation T : I → I, since this allows the transfer of the known result back to I.

Another, perhaps more interesting application of these results is concerned with negative results on comparing the expressiveness of pre-institutions, in the sense of Deﬁnition 2.7. The proof technique, which has a “contrapositive” ﬂavour, simply consists in showing that some of the properties whose contravariant inheritance is ensured by (possibly “suitable”) pre-institution transformations is

**enjoyed by I but not by I. In such a case, then, one can infer that no (“suitable”) pre-institution transformation T : I → I exists (where “suitable” means:**

with some additional property, such as adequacy). An application of this proof method is presented in Section 5.1 of [18].

Proposition 3.2. Let T : I → I be a pre-institution transformation, with I, I as in Deﬁnition 2.3.

78 A. SALIBRA AND G. SCOLLO (i) If I is rps, then I is rps.

(ii) If I is eps, then I is eps.

(iii) If I is ps, then I is ps.

The reason why (full) adequacy of the transformation is required as a criterion for (full) expressiveness is apparent from the following fact, where denotes logical consequence, deﬁned in the usual semantical way.

Proposition 3.3. Let T : I → I be a pre-institution transformation, with I,

**I as in Deﬁnition 2.3. Then ∀ϕ ∈ Sen(Σ), ∀ψ ∈ Sen (ΣT ), ∀E, Ej ∈ Pre(Σ):**

(i) ET ϕT ⇒ E ϕ, (ii) E ϕ ⇒ ET ϕT if T is adequate.

(iii) j∈J (Ej )T ψ ⇒ ( j∈J Ej )T ψ if T is adequate.

(iv) ( j∈J Ej )T ψ ⇒ j∈J (Ej )T ψ if T is fully adequate.

Furthermore, the following fact (7 ) tells that, with respect to consequence, T -tautologies behave as tautologies relative to presentation transforms, if the transformation T is adequate.

Proposition 3.4. Let T : I → I be an adequate pre-institution transformation, with I, I as in Deﬁnition 2.3. Then ∀Σ ∈ Sig, ∀E ∈ Pre(Σ): ET TautT (Σ).

P r o o f. Let E ∈ Pre(Σ), M ∈ Mod (ΣT ), and assume M ET. By adequacy of T, there exists M ∈ Mod(Σ) such that M E and M ∈ MT. Then M ψ for every ψ ∈ TautT (Σ), according to Deﬁnition 2.11. We conclude that ET TautT (Σ).

The Galois connection nature of invertible pre-institution transformations is revealed by the following characterization.

Proposition 3.5. Let T : I → I and R : I → I be two pre-institution transformations, with I, I as in Deﬁnition 2.3. The following conditions are

**equivalent:**

R is an inverse of T, (a) T is an inverse of R, (b) ∀Σ ∈ Sig, ∀E ∈ Pre(Σ), ∀M ∈ Mod(ΣT ): M ET ⇔ (M )R E, (c) ∀Σ ∈ Sig, ∀E ∈ Pre (Σ ), ∀M ∈ Mod(ΣR ): M ER ⇔ MT (d) E.

Suﬃcient conditions for exactly equivalent expressiveness may be of help in the construction of such equivalences. Of the two conditions given below, the second one is stronger, but may turn out to be more useful in practice.

Proposition 3.6. Let T : I → I and R : I → I be two pre-institution transformations, with I, I as in Deﬁnition 2.3. The following conditions are

**suﬃcient for R to be an inverse of T :**