[PDF] POSITIVE MODEL THEORY AND COMPACT ABSTRACT

View - Download POSITIVE MODEL THEORY AND COMPACT ABSTRACT

Previous PDF

Next PDF

POSITIVE MODEL THEORY AND COMPACT ABSTRACT

THEORIES

ITAY BEN-YAACOV

Abstract.We develop positive model theory, which is a non first order analogue of classical model theory where compactness is kept at the expense of negation. The analogue of a first order theory in this framework is a compact abstract theory: several equivalent yet conceptually different presentations of this notion are given. We prove in particular that Banach and Hilbert spaces are compact abstract theories, and in fact very well-behaved as such.

Introduction

Trying to extend the classical model-theoretical techniquesbeyond the strictly first- order context seems to be a popular trend these days. In [Hru97], Hrushovski defines Robinson theories, namely universal theories whose class of models has the amalgama- tion property. He subsequently works in the category of its existentially closed models, which serves as an analogue of the first order model completion when this does not exist. In [Pil00], Pillay generalises this to the category of existentially closed models of any universal theory. In both cases, one works rather in an existentially universal domain for the category, which replaces the monster model of first order theories. The present work started independently of the latter, trying to use ideas in the former in order to define a model-theoretic framework where hyperimaginary elements could be adjoined as parameters to the language, the same way we used to do it with real and imaginary ones since the dawn of time: as the type-space of a hyperimaginary sort is not totally disconnected, we need a concept of a theory who just can"t say "no". In the terminology of [Hru97], this means we must no longer require the set of basic formulas Δ to be closed for boolean combinations, but onlyforpositiveones. The notions of positive model theory, and in particular of positive Robinson theories, follow. As it turns out, positive Robinson theories are but one of severalalternative pre- sentations of the same concept. We prefer therefore to make thedistinction between any particular presentation and the fundamental concept itself, which we callcompact abstract theories, orcats. In the present paper we restrict ourselves to the development ofthe framework. General model theoretic tools, and in particular simplicity,are developed for it in [Ben02b]. Additional results, and in particular a better treatment of simplicity under the additional hypothesis of thickness, are given in [Ben02c].These tools are applied in [Ben02a] for the treatment of the theory of lovely pairs ofmodels of a simple theory in case that the theory of pairs is not of first order.

Date: June 11, 2002.

1

2ITAY BEN-YAACOV

It was pointed out that the definition of a universal domain fora positive Robinson theory is similar toAssumption IIIfrom [She75, Section 2].

1.Introduction to positive model theory

We introduce positive model theory, which in particular generalises first order model theory. Although it is related to classical first order logic, itsdevelopment requires a radical change in our point of view: we use at times the language of categories more than that of logic, and the usage of negation and of the universal quantifier is discouraged (not to mention unnecessary). The basic idea is to replace the notions of elementary extensions and embeddings by that of homomorphisms: for a designated set of "positive" statements, what was true for the domain must be true for its image, but not necessarily theconverse. In other words, any positive statement that"s true is already decided, whereas those which are not true will not necessarily remain so: they are simply "deferred" for a later decision. This fact, of being allowed to decide only what we want and defer everything else makes the compactness theorem almost trivial: a short and elegant proof is given below as a corollary of positive Morleyisation (which is, on the otherhand, more complicated than first-order Morleyisation). Due to this shift in point of view and language, and with an easy proof of the compactness theorem, an exposition from scratch seems reasonable, and would make this paper very much self-contained.

1.1.Language and categories of structures.We start with the basic definitions:

Definition 1.1.1. A(relational) signatureLis a set along with a functionν: L →ω. An elementP? Lis called aν(P)-ary predicate symbol. We also have a distinguished binary predicate symbol =? L.

2. LetLbe a signature. AL-structure is a setMalong with aν(P)-ary predicate

P M?Mν(P)for every predicate symbolP? L, called theinterpretationofPin M. The symbol = is always interpreted by equality. Remark1.2.Classically one also allowsfunction symbols: however, as a function can be represented just as well by the predicate defining its graph,this is not necessary and would only serve to complicate things. Definition 1.3.LetX={xi:i < ω}(where all thexiare distinct) and call its ele- mentsvariables. In fact, we could have simply takenX=ω, but we follow traditional notation. We differ somewhat from the standard definitions in the fact thatwe consider the set of free variables of a formula (including the dummy ones) a part of the information in the formula: for us aL-formula is something of the form?(x?I) for some finiteI?ω, wherex?Iis shorthand for{xi:i?I}. IfI=nthen we writex1. IfPis an-ary symbol, thenP(x wherebyM|=P(a2. If?(x?I) is a formula,J?ωis finite, andf:I→Jis a map, thenψ(x?J) = f ?(?(x?I)) is a formula obtained bychange of variables: Fora?J?MJ, writef?(a?J) = (af(i):i?I)?MJ, and for a setA?MIdefine f ?(A) =f?-1(A)?MJ: thenψ(MJ) =f?(?(MI)), wherebyM|=ψ(a?J)??

M|=?(f?(a?J)).

In actual notation, we may writef?(?) as?(xf(0),... ,xf(n-1)), but it must be understood that this is a formula in the variablesx?J.

3. Ifk < ωand?i(x?I) is a formula for everyi < k, thenχ(x?I) =?

iρ(x?I) =? i4. IfI∩J=∅and?(xI?J) =?(x?I,x?J) is a formula thenψ(x?I) = ?x?J?(x?I,x?J) is a formula constructed byexistential quantification, andψ(MI) is the projection of?(MI×MJ) onMI, wherebyM|=ψ(a?I) if and only if there isa?J?MJsuch thatM|=?(a?I,a?J).

5. If?(x?I) is a formula, thenψ(x?I) =¬?(x?I) is a formula constructed bynega-

tion, andψ(MI) =MI??(MI). A formula?(x?I) isI-ary, and the variablesx?Iare itsfree variables. A 0-ary formula, that is without free variables, is called asentence, or aclosed formula. Asub-formulaof?is any formula appearing along its construction. L

ω,ωis the set of allL-formulas.

Notation 1.4.If the set of free variables of a formula is clear from the context or is irrelevant, we just write?(¯x),?(x) or even?. Also, we may write ¯a?Mor evena?M, when it is clear that these are tuples inMI whereIis clear from the context, and we may similarly replace?(MI) with?(M). Definition 1.5.TwoI-ary formulas?andψareequivalentif?(MI) =ψ(MI) for everyL-structureM. Convention 1.6.We consider equivalent formulas as equal. Definition 1.7.Analmost atomic formulais a change of variables on an atomic formula. Lemma 1.8.Every formula is equivalent to one constructed from almost atomic for- mulas along the same construction tree without any further changes of variables (beyond the almost atomic formulas).

Proof.Easy.qed

Definition 1.9.1. A set Δ? Lω,ωis apositive fragmentofLif it contains all the atomic formulas inLω,ωand is closed under change of variables, sub-formulas, and positive combinations.

2. Let Δ be a positive fragment. Then Σ(Δ) is its closure under existential quan-

tification, and Π(Δ) ={¬?:??Σ(Δ)}.

4ITAY BEN-YAACOV

3. The minimal positive fragment, which consists of positive combinations of almost

atomic formulas (or, in a more traditional terminology, quantifier-free positive formulas), is noted Δ

0. We also note Σ1= Σ(Δ0), Π1= Π(Δ0).

4. Let Δ be a positive fragment. Then a mapf:M→Nbetween twoL-structures

is a Δ-homomorphismifM|=?(a) =?N|=?(f(a)) for everyn < ω,n-ary formula?(x5. A mapf:M→Nbetween twoL-structures is a Δ-embeddingifM|=?(a)?? N|=?(f(a)) for everyn < ω,n-ary formula?(x6. The category ofL-structure where the morphisms are the Δ-homomorphisms is notedMΔ. If the positive fragment Δ is clear from the context, we omit it. Convention 1.10.WhenMΔis clear from the context andf:M→Nis a mor- phism, then we say thatNcontinuesM. Whenfis clear from the context, and it is also clear that we work inN, we may some- times omitf, identifying elements ofMwith their images inN. This is convenient but requires attention, asfis not necessarily injective! Remark1.11.If Δ is a positive fragment, then so is Σ(Δ) (since we only consider formulas up to equivalence). Moreover, replacing Δ with Σ(Δ) does not change any of Σ(Δ), Π(Δ), or the notion of Δ-homomorphism (which is always a Σ(Δ)- homomorphism). However, it may well change the notion of a Δ-embedding, which is why we consider this an unnatural notion (see also below). The motivation is straightforward: first of all, given the definition of anL-structure, the natural notion of morphism is that of a map that preserves the truth (though not necessarily falsehood) of every predicate, that is every atomic formula. Clearly, if a map preserves the truth of a set of formulas it does so for every formula obtained thereof by positive combinations and change of variables, so we may pass to the generated positive fragment. We get the notion of a Δ

0-homomorphism and the categoryMΔ0,

where indeed we shall work most of the time. In fact, one sees easily that for every positive fragment Δ, a Δ-homomorphism preserves the truth of every formula in Σ(Δ), so we can add any such formula to Δ and pass to the generated positive fragment without changingMΔ. However, one may also desire (weird as it may seem) not only to preserve the truth of some??Δ, but its falsehood as well, which means to preserve¬?. Adding¬?to Δ and passing to the generated positive fragment would have precisely this effect. Doing this repeatedly (possibly an infinite number of times) we obtain any category M Δ, and at the very end we findMLω,ω, where first order model theory takes place. We see from this that the addition to Δ of formulas constructed by negation is the only one that does not come for free, which is why we try to avoid negations. This stands in contrast to the classical exposition of model theory, where one considers Δ- embeddings rather than Δ-homomorphisms, and then it is quantification that does not come for free. Nevertheless, even in our context the truth of a Σ(Δ)-formula is slightly more complicated to verify than that of a Δ-formula, in particular when Δ = Δ0, which is why we keep the distinction between the two: we aim to show later on that POSITIVE MODEL THEORY AND COMPACT ABSTRACT THEORIES 5 in certain cases Δ and Σ(Δ) have the same power of expression, and then restrict ourselves to Δ. Convention 1.12.Δ is a positive fragment, and a morphism is one ofMΔ, that is a

Δ-homomorphism.

M

mapsgi:Mi→N. ForR? L, we defineN|=R(¯a) if and only if there isi?Iand¯b?Misuch thatMi|=R(¯b) and ¯a=gi(¯b). We note lim-→Mi=N, now asL-structures.

Lemma 1.14.With the notations of Definition 1.13, ifΔis a positive fragment and (Mi)is aΔ-inductive system, then for every?(¯x)?Δ:lim-→Mi|=?(¯a)if and only if there isi?Iand¯b?Misuch thatMi|=?(¯b)and¯a=gi(¯b). Proof.For atomic formulas, this was the definition. We can now use the fact that a positive fragment is closed for sub-formulas and work by induction on??Δ. Positive combinations and existential quantifiers are easy. As for negation, assume that¬?(¯x)?Δ and lim-→Mi|=¬?(¯a). Then there arei?Iand¯b?Misuch that g i(¯b) = ¯a, and then necessarilyMi|=¬?(¯b), since?(¯x)?Δ. Conversely, assume thatMi|=¬?(¯b) but lim-→Mi|=?(gi(¯b)). Then there arej?Iand ¯c?Mjsuch that M

j|=?(¯c), andgj(¯c) =gi(¯b). Then there isk≥i,jsuch thatfik(¯b) =fjk(¯c) = ¯a,

say, soMk|=?(¯a) andMk|=¬?(¯a) (here we finally use the fact that¬??Δ), contradiction.qed

And we conclude:

Proposition 1.15.With the notations of Definition 1.13, ifΔis a positive fragment and(Mi) Δ-inductive system, then everygiis aΔ-homomorphism, andlim-→Miis the injective limit in the sense ofMΔ. Let us imagine once more we walk alongMΔ. At some point we stand at the structureM, and we ask ourselves whether?(a) holds, where??Σ(Δ) anda?M. Assume indeed thatM|=?(a): if we follow a morphismf:M→N, thenN|= ?(f(a)). If we follow several morphisms one after the other this is still true, and by Proposition 1.15 we can even pass to the limit of a chain of morphisms. On the other hand, ifM?|=?(a), we do not have a definitive answer yet on what will happen when we follow a morphism (unless¬??Δ, of course), so we have to continue and see what happens. However, we shouldn"t go too far either: for example, if Δ = Δ0, we may end up in a structure where everything is true, in particular equality, so the structure would be reduced to a single point! This means we need some means to give definitive negative answers, without using negations. For example, by restricting ourselves to those structures where two certain positive statements cannot be true simultaneously: then saying that one is true is a definitive decision for the falsehood of the other. This leads us quite naturally to the notion of a Π-theory. Definition 1.16.A(Π-)theoryis a set of Π-sentences, that is a set of statements of the form "for no tuple ¯ado we have?(¯a)", for certain formulas??Δ.

6ITAY BEN-YAACOV

IfMis a structure then ThΠ(M) it its theory, that is the set of all Π-sentences true inM.

IfMis a class of structures, then ThΠ(M) =?

M?MThΠ(M).

Amodelof a theoryTis a structureM|=T, meaningM|=?for every??T. Two theories areequivalentif they have the same models. Definition 1.17.IfTis a theory (that is, a Π-theory), thenM0(T) is the (full) sub-category ofMΔwhose objects are models ofT. Given a theoryTwe can give definitive positive answers, which may also imply definitive negative answers for other questions. It makes sense now to look for a model ofTwhere every reasonable question has a definitive answer. Definition 1.18.A modelM|=Tisexistentially closed (e.c.)if every Δ- homomorphismf:M→NwithN|=Tis a Σ-embedding. In other words, we require that for every?(¯x)?Σ(Δ) and every ¯a?M, ifN|=?(f(¯a)) thenM|=?(¯a).

The category of e.c. models ofTis notedM(T).

Assume thatM,N? M(T),f:M→Nis a morphism, ¯a?Mis some tuple, and?(¯x)?Σ(Δ). Then, by definition,M|=?(¯a)??N|=?(f(¯a)). But then, if fis actually an inclusion, then we can write ratherM|=?(¯a)??N|=?(¯a). This justifies: Notation 1.19.IfM? M(T), ¯a?Mand?(¯x)?Σ(Δ), then by slight abuse of notation we write|=?(¯a) or ¯a|=?instead ofM|=?(a). Next step is to show that enough e.c. models exist: Lemma 1.20.EveryM|=Tcontinues to some e.c. modelN? M(T).

Proof.SetM0=M.

Having constructedMi, let{(?j,¯aj) :j < λi}be an enumeration of all pairs (?,¯a) where?(xδi= lim-→j<δMj i. In the end, takeMi+1=Mλii.

ThenMω= lim-→i<ωMiis clearly e.c..qed

Remark1.21.Lemma 1.20 is easily seen to be equivalent to the Axiom of Choice.

1.2.Positive Morleyisation and compactness.Positive Morleyisation is a an

adaptation to positive model theory of a first order construction of Michael Morley, which allows us to reduce the case of a general positive fragment to that of Δ0. It re- quires more work than in the first order case, but then it is more powerful: for example, the compactness theorem follows as a trivial corollary. Definition 1.22.LetIbe any set of indices, and{xi:i?I?ω}new distinct symbols. For ann-ary formula?(x0. We recall the notation Σ1=

0), Π1= Π(Δ0).

Lemma 1.25.LetTbe aΠ1-theory, andΦ(x?I)a set of almost atomicI-ary formulas, withIpossibly infinite. If every finite subsetΦ0?Φis consistent withT(in fact, it suffices that it be consistent with eachψ?T), thenΦis consistent withT. Proof.TakeM0={ai:i?I}where these are all distinct elements, and define≂as the equivalence relation generated by{ai≂aj:xi=xj?Φ}. TakeM=M/divsim, and for everyn-ary predicate symbolRtakeRM={([ai0],... ,[ain-1]) :R(xi0,... ,xin-1)?

Φ}. ThusM|= Φ([a?I]).

Assume that there isψ?Tsuch thatM?|=ψ. This means that there is something true inMthatψforbids, and it is true inMdue to a finite part Φ0?Φ. This means that Φ

0is inconsistent withT, and in fact withψ, contradicting the hypothesis.qed

We wish to make the notion of a definitive negative negation more explicit in some special case: Lemma 1.26.LetTbe aΠ1-theory, and assume thatTis closed for logical conse- quence: anyΠ1sentence which is true in every model ofTis inT. LetM|=Tbe e.c.,Rann+k-ary predicate symbol, and¯a?Mn. ThenM?|=?¯y R(xProof.One direction is clear, sinceM|=T. For the other, enumerateM={bi:i?I}, and letf:n→Ibe such that ¯a=f?(¯b). Set Φ(xi?I,¯y) ={R(f?(¯x),¯y)} ? {R?(h?(¯x)) :R?? L,h:ν(R?)→I,M|=R?(h?(¯b))}

If Φ(¯x) is consistent withT, say satisfied by¯b?,¯cin a modelM?, then the map sending¯bto¯b?is a Δ0-homomorphism ofMintoM?. Since thenM?|=R(f?(¯b?),¯c) andMis

e.c., we must have alsoM|=?¯y R(f?(¯b),¯y), that isM|=?¯y R(¯a,¯y), contradiction.

8ITAY BEN-YAACOV

Therefore Φ is inconsistent withT, and by Lemma 1.25 there is a finite Φ?0?Φ which

is inconsistent with someψ?T. Write Φ?0(¯x,¯y) = Φ0(¯x)? {R(f?(¯x),¯y)}. Since Φ0is

finite it is equivalent to?(x?J) (with the implicit change of variables) where??Δ0is a conjunction of almost atomic formulas andJ?Iis finite such thatm?Jenumerates every element of ¯a(that is,Jcontains the image off). Thenψ?Tis inconsistent with?(x?J)?R(f?(x?J),¯y) andM|=?(b?J), as required.qed Definition 1.27.LetLbe a given signature, and Δ a positive fragment. Define L QE(Δ)=L ? {R?:n?ω,?(xQE(Δ)

0is the minimal positive fragment ofLQE(Δ). Similarly, ΠQE(Δ)1= Π(ΔQE(Δ)0).

IfMis aL-structure, expand it to aLQE(Δ)-structureMQE(Δ)by definingRM?=?(Mn) (that is,M|=R?(aM(T)}andTQE(Δ)= ThΠQE(Δ)1(MQE(Δ)(T)). In other words,TQE(Δ)is the Π(ΔQE(Δ)0)-

theory of the class of all theLQE(Δ)-structuresMwhich are, asL-structures, e.c. models ofT, and in addition interpret eachR?as?.

We callTQE(Δ)then Δ-MorleyisationofT.

Lemma 1.30.LetΔbe a positive fragment, andΔQE(Δ)

0as above. LetTbe aΠ(Δ)-

theory andT?aΠQE(Δ)

1-theory, such thatM= (M?L)QE(Δ)for everyM? M(T)

(namely,?(M) =RM?for every??Δ). Assume also thatMQE(Δ)|=T?for every

M? M(T)andM?L|=Tfor everyM? M(T?).

Then the functorM?→MQE(Δ)is an isomorphismM(T)? M(T?). In other words, M

QE(Δ)(T) =M(T?).

Proof.LetM? M(T). Then we know thatMQE(Δ)|=T?, and we need to show thatMQE(Δ)is e.c. as such. So letN|=T?andf:MQE(Δ)→Nbe a ΔQE(Δ)0- homomorphism, and we need to show that is it a Σ

QE(Δ)

1-embedding. We may assume

thatN? M(T?), wherebyN= (N?L)QE(Δ), sof?L:M→N?Lis a Δ-homomorphism, andN?L|=T. SinceMis an e.c. model ofT,f?Lis a Σ(Δ)-embedding, andfis a

QE(Δ)

1-embedding as required:

Mquotesdbs_dbs44.pdfusesText_44

[PDF] espace fermé définition

[PDF] convertir photo en basse definition

[PDF] espace compact pdf

[PDF] lexique juridique marocain pdf

[PDF] les lois de la donation au maroc

[PDF] conversion pixel octet

[PDF] habiter un espace de faible densité

[PDF] exo7 matrice exercice

[PDF] habitude alimentaire definition

[PDF] guide de bonnes pratiques d'hygiène en pâtisserie

[PDF] propriété d archimède exercices

[PDF] partie entière inégalité

[PDF] espace numérique éducation

[PDF] portail numérique éducation

[PDF] partie entière d'un nombre négatif