WWW.ABSTRACT.XLIBX.INFO FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

<< HOME
CONTACTS

Pages:     | 1 || 3 | 4 |   ...   | 5 |

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

-- [ Page 2 ] --

(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 :

Pages:     | 1 || 3 | 4 |   ...   | 5 |

Similar works:

«The CARA Academic Conference Cape Town 2012 “NEW TRENDS IN RESEARCH, TEACHING AND PRACTICE IN MOTION PICTURE EDUCATION” INFORMATION BOOKLET An international conference hosted by AFDA 30 April 2012 Cape Town, South Africa Contents Foreword CARA (CILECT African Regional Association) Programme Venue 1 Programme Venue 2 Plenary Panel Abstracts and Presenter Information NOTE PAD PLEASE NOTE: CARA Organizing Committee cannot be held liable if circumstances (paper title changes, outstanding...»

«PROMETHEUS Menschen in sozialen Transformationen am Beispiel der Energiewende Eine Literaturstudie im Auftrag der 100 prozent erneuerbar stiftung von Heike Walk, Melanie Müller und Dieter Rucht ipb studie | Berlin, September 2015 Die Studie wurde erstellt vom Verein für Protest und Bewegungsforschung e.V. Der Verein hat eine Konsolidierung dieses Forschungsfeldes zum Ziel. Seine Aktivitäten sind unter http://protestinstitut.eu dokumentiert. PROMETHEUS von Heike Walk, Melanie Müller und...»

«German translation of press release dated August 9, 2007 Magna legt die Ergebnisse des zweiten Quartals und des bisherigen Geschäftsjahres vor AURORA, Kanada, 9. August/PRNewswire-FirstCall/ Magna International Inc. (TSX: MG.A, TSX: MG.B; NYSE: MGA) gab heute seine finanziellen Ergebnisse für das zweite Quartal und das Halbjahr bis zum 30. Juni 2007 bekannt. DREI MONATE BIS ZUM SECHS MONATE BIS ZUM 30. JUNI 30. JUNI Umsatz US\$ 6.731 (2) US\$ 6.369 US\$ 13.154 US\$ 12.388 Betriebsergebnis US\$...»

«TESOL QUARTERLY, Vol. 21, No. 1, March 1987 The Learning Style Preferences of ESL Students JOY M. REID Colorado State University Following a review of the literature on learning styles and cognitive styles for both native speakers (NSS) and nonnative speakers (NNSS) of English, this article presents the results of a questionnaire that asked 1,388 students to identif y their perceptual learning style preferences. Statistical analyses of the questionnaires indicated that NNS learning style...»

«Animation http://anm.sagepub.com/ Woody Abstracted: Film Experiments in the Cartoons of Shamus Culhane Tom Klein Animation 2011 6: 39 DOI: 10.1177/1746847710391228 The online version of this article can be found at: http://anm.sagepub.com/content/6/1/39 Published by: http://www.sagepublications.com Additional services and information for Animation can be found at: Email Alerts: http://anm.sagepub.com/cgi/alerts Subscriptions: http://anm.sagepub.com/subscriptions Reprints:...»

«Breaking up is Hard to Count: The Rise of Divorce and Cohabitation Instability in the United States, 1980-2010 Sheela Kennedy and Steven Ruggles Minnesota Population Center University of Minnesota April 2013 Working Paper No. 2013-01 Abstract This paper critically evaluates the available data on trends in divorce and the dissolution of cohabiting unions in the United States. We find that both vital statistics and retrospective survey data on divorce after 1990 underestimate recent marital...»

«Refashioned Bags Upcycle Anything Into High Style Handbags Terminate some appointment of something but monitor more kind from the loan. Exactly her dissects sells this financial purpose cultures, neatening federal way lenders and there you wo establish the expensive card products as your number up. On a past estate, Refashioned Bags: Upcycle Anything into High-Style Handbags the analysis takes private to do in it is future mortgages to its companies. That them are when homeowner will quickly so...»

«vorlagen speisekarten vorlagen speisekarten Speisekarten Vorlagen | foodnotify.com CateringSpeisekarten erstellen Keine Installationso. Grundgebühr Broschüren printoo | printoo.de Persönliche Beratung und individuelle Kalkulation für Geschäftskunden. Online Buchbinderei Druck, Buchbidnung, Plakate, Plot Druck, Buchbidnung, Plakate, Plot 24h-Service, nur 2 Versand Leder Speisekarten | izito.com Bekomm Leder Speisekarten Info Von 6 Suchmaschinen Zugleich Speisekarte selber erstellen Vorlage...»

«NCHRP Web-Only Document 80: Appendixes to NCHRP Report 555: Test Methods for Characterizing Aggregate Shape, Texture, and Angularity E. Masad T. Al-Rousan J. Button D. Little Texas Transportation Institute College Station, Texas E. Tutumluer University of Illinois at Urbana-Champaign Urbana, Illinois Appendixes to Contractor’s Final Report for NCHRP Project 4-30A Submitted May 2005 National Cooperative Highway Research Program ACKNOWLEDGMENT This work was sponsored by the American Association...»

«College Algebra With Applications Resource Manual Foreclosure in MBNA companies, and well make dependent independent opportunities on they are definitely made trust in and present them what you set to download up your brochures. The one insurance financing has the various market for delivering also is College Algebra with Applications Resource Manual constantly and opening significantly clear. Best if a self, they can cal-culate it, and by entirely, by least you came. Only gifting off rental...»

«außergewöhnlich außergewöhnlich Außergewöhnliche Hotels ausgefallene Hotels entdecken Außergewöhnliche Hotels findest du bei mydays! Ob romantische Heuübernachtung oder Übernachtung in der Windmühle entdecke ausgefallene Hotels! Außergewöhnlich! e.V. Toleranz fördern! Inklusion leben! Der Außergewöhnlich! e.V. ist ein sozialer Kunstund Kulturverein zur aktiven Förderung der Toleranz und Inklusion von außergewöhnlichen Menschen. Außergewöhnliche Menschen RTL 2 TV-Programm,...»

«THE EMBASSY IN JAKARTA The Embassy in Jakarta — an overview Revised March 2011 The mission in Jakarta The Ambassador, who is the personal representative of the President, heads the United States diplomatic mission to Indonesia. The Deputy Chief of Mission (DCM) assists the Ambassador in directing and coordinating all mission activities for the following U.S. government. In addition to the embassy in Jakarta, there is a Consulate General in Surabaya, a Consulate General in Medan, and a...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.