Topavlog08.files.wordpress.com

BARWISE: ABSTRACT MODEL THEORY AND GENERALIZED §1. Introduction. After the pioneering work of Mostowski [29] and Lind-
str ¨om [23] it was Jon Barwise’s papers [2] and [3] that brought abstract modeltheory and generalized quantifiers to the attention of logicians in the earlyseventies. These papers were greeted with enthusiasm at the prospect thatmodel theory could be developed by introducing a multitude of extensions offirst order logic, and by proving abstract results about relationships holdingbetween properties of these logics. Examples of such properties are κ-compactness. Any set of sentences of cardinality ≤ κ, every finite
subset of which has a model, has itself a model.
L¨owenheim-Skolem Theorem down to κ. If a sentence of the logic
has a model, it has a model of cardinality at most κ.
Interpolation Property. If φ and
are sentences such that |= φ → such that |= φ → , |= is the intersection of the vocabularies of φ and Received January 6, 2003; revised January 10, 2003.
Research partially supported by grant 40734 of the Academy of Finland.
Lindstr ¨om’s famous theorem characterized first order logic as the maximalℵ0-compact logic with Downward L ¨owenheim-Skolem Theorem down toℵ0. With his new concept of absolute logics Barwise was able to get similarcharacterizations of infinitary languages Lκ . But hopes were quickly frus-trated by difficulties arising left and right, and other areas of model theorycame into focus, mainly stability theory. No new characterizations of logicscomparable to the early characterization of first order logic given by Lind-str ¨om and of infinitary logic by Barwise emerged. What was first called softmodel theory turned out to be as hard as hard model theory.
Mostowski [29] characterized first order logic model theoretically among extensions of first order logic obtained by adding one so called simpleunary generalized quantifier (see below). Lindstr ¨om first in [22] extendedMostowski’s characterization to non-unary generalized quantifiers and thenin [23] to extensions of first order logic satisfying only some fairly mild con-ditions. For these results Mostowski’s proofs used methods going hardlybeyond what is needed in predicate logic with only unary predicates. Lind-str ¨om took advantage of the full power of first order model theory of thetime. Barwise [2] extended Lindstr ¨om’s methods to the then new infinitarymodel theory, combining them with ideas from the emerging generalizedrecursion theory. His main accomplishment was a characterization of infini-tary languages Lκ and their fragments.
A question, asked, among others, by Feferman [13], Friedman [15] and Shelah [33], right from the beginning of the study of abstract logic andgeneralized quantifiers was Open Problem. Is there a proper ℵ0-compact extension of first order logic
Different attempts to solving this question dominate also this review of Barwise’s work in the area of abstract model theory generalized quantifiers.
The volume [8] edited by Barwise and Feferman is a good handbook for the developments in abstract model theory and generalized quantifiersthrough the 80’s.
§2. Generalized quantifiers. At least two kinds of extensions of first or-
der logic were already well-known in the 50’s, namely infinitary logics Lκand higher order logics. In both cases mainly negative results were known:results of incompactness, incompleteness, etc. With the appearance of gen-eralized quantifiers in the early 60’s extended logics with compactness andcompleteness theorems emerged.
Mostowski defined generalized quantifiers as follows: A (simple unary) generalized quantifier is a collection Q of pairs (I, X ), X ⊆ I , satisfying thecondition (I, X ) ∈ Q, |X | = |Y | and |I − X | = |J − Y | ⇒ (J, Y ) ∈ Q, BARWISE: ABSTRACT MODEL THEORY AND GENERALIZED QUANTIFIERS Qn = {(I, X ): |X | ≥ ℵn} . Such a quantifier Q can be thought of as a logical operation by adding the following rules to the rules of ordinary first order logic: • If φ(x, ¯y) is a formula, then so is Qxφ(x, ¯y).
• A |= Qxφ (x, ¯a) ⇔ (A, {b : A |= φ (b, ¯a)}) ∈ Q.
Let us denote the resulting extension of first order logic by L (Q0) cannot be (effectively) axiomatized. He ∀x¬Q0y (y < x) (Q0). Let P denote the ordinary first order Peano axioms. Now for any first order sentence φ of number theory we have (N, +, ·, 0, 1, <) |= φ ⇔ (∀ A |= P) (A |= ( → φ)) . Since there is no arithmetical method to decide the left hand side there cannot be any complete and arithmetical provability predicate for L either. Barwise [3] extended this argument to its full power by showing thatinside L (Q0) hides in implicit form an infinitary logic, namely the smallest of first order logic, for which the above argument clearly fails, is axioma-tizable. A positive answer was provided by Vaught [38] using an indirectargument. Keisler [20] gave a simple explicit axiomatization based on theprinciple that a countable union of countable sets is countable. Shelah[33] extended L Barwise, in co-operation with Kaufmann and Makkai [9, 10] showed thatstationary logic has a natural explicit axiomatization, much like Keisler’s forL Mostowski also gave a model theoretic characterization of the first order quantifiers: Any extension obtained from first order logic by adding a simpleunary generalized quantifier, which satisfies the condition Every sentence with an infinite model has a model in every infinitecardinality. H¨artig [16] and Rescher [32] introduced the quantifiers |{b : A |= φ (b, ¯ |{b : A |= φ (b, ¯ both of which went beyond what could be expressed with Mostowski’s quan-tifiers. Lindstr ¨om tells in [24] how he came, after unsuccessful attempts toview the quantifiers of H¨artig and Rescher as examples of Mostowski’squantifiers, upon the following even more general concept, which has sub-sequently become the standard definition of generalized quantifiers: Definition 1. Suppose L is a relational vocabulary and Q is a class of L- structures such that Q is closed under isomorphism. We add a new quantifiersymbol Q to first order logic as follows: To simplify notation, let us assumethat L consists of one unary predicate and one binary predicate only.
A |= Qx, yzφ (x, ¯a) (A, {b : A |= φ (b, ¯a)} , {(b, c) : A |= (b, c, ¯a)}) ∈ Q. H¨artig’s and Rescher’s quantifiers correspond to the choices I = {(A, X, Y ) : |X | = |Y |} R = {(A, X, Y ) : |X | ≤ |Y |}. An example of a generalized quantifier in a vocabulary with a binary predi-cate, and one that plays a role in Barwise’s study of absolute logics, is WO = {(A, R) : R ⊆ A2 well orders its field}. We return of generalized quantifiers in Section 9.
§3. Abstract logic. Lindstr ¨om’s definition of abstract logics was merely
a list of general properties the definable model classes of any abstract logicshould have. No mention was made of the syntax of the logic. In this wayLindstr ¨om achieved extreme generality. Barwise liked to emphasize the roleof syntax even in abstract model theory. This is how Barwise defined abstractlogics in [2]: Let L be a vocabulary and let the concept of L-structure be the usual one. A name changer is a bijection from L onto another vocabulary L′ mapping n-ary predicate symbols to n-ary predicate symbols, n-ary functionsymbols to n-ary function symbols, and constant symbols to constant sym-bols. Associated with a name changer is a natural operation on structures,mapping an L-structure A onto an L′-structure A .
Definition 2. An abstract logic for a vocabulary L is a pair (L∗, |=∗), where
L∗ is a set of objects called sentences of L∗ and |=∗ is a relation between L-structures and sentences of L∗. We call |=∗ the satisfaction relation of L∗.
The satisfaction relation is assumed to obey the following basic IsomorphismCondition: If L is a vocabulary and φ is an L∗-sentence then for all M: BARWISE: ABSTRACT MODEL THEORY AND GENERALIZED QUANTIFIERS A system of logics is an operation ∗ which associates every countable vocabulary
L with an abstract logic for L such that the following conditions are satisfied :
(2) If K ⊆ L, then K∗ ⊆ L∗ and for every φ ∈ K∗ and every L-structure M, M ↾ K |=∗ φ if and only if M |=∗ φ.
(3) If : L → K is a name changer then for every L∗-sentence φ there is a K ∗-sentence φ such that M |=∗ φ if and only if M |=∗ φ .
In many results other assumptions are used, such as closure under con- junction, negation and first order quantification.
This differs insignificantly from Lindstr ¨om’s definition in [23]. Lindstr ¨om identifies a sentence with the class of its models. Thus an abstract logic fora vocabulary L will be a collection of classes of L-structures, each closedunder isomorphism, and an abstract logic will be a collection of L-classes ofstructures for various L, each closed under isomorphisms. Correspondingto the above conditions (2) and (3) there are obvious conditions on reductsand changing the vocabulary.
Since Barwise wanted to put definability conditions on the logics, with the usual inductive definition of syntax and semantics in mind, he had to be
explicit about syntax. Later in [3] he went further and used category theoretic
concepts to emphasize the functorial nature of syntax. He considered the
category C of all vocabularies with interpretations (by means of terms) of
vocabularies as morphisms. Such morphisms induce canonically operations
on structures corresponding to what is usually meant by interpretation of a
structure in another. The syntax of an abstract logic L∗ is a functor ∗ on
some subcategory of C to the category of classes. Elements of L∗ are called
sentences. The functor is supposed to satisfy an Occurrence Axiom, which
says, roughly, that for every sentence φ there is a smallest vocabulary L such
that φ ∈ L∗. The semantics of L∗ is a relation |= such that the Isomorphism
Axiom (Condition (1) of Definition 2) is satisfied. The syntax and semantics
of L∗ are tied together by the Translation Axiom which is like Condition (3)
of Definition 2.
Barwise compares in [3] his category theoretic approach with that of Lind- Lindstr ¨om avoids syntactic considerations altogether since he dealsdirectly with classes of structures, rather than with the sentenceswhich define them. We find this approach unsatisfactory on twogrounds. In the first place, it seems contrary to the very spirit ofmodel theory where the primary object of study is the relationshipbetween syntactic objects and the structures they define. Secondly,it fails to make explicit that the closure conditions on the classes ofstructures (like formation of indexed unions and its inverse) arise out of natural syntactic considerations, considerations which seemimplicit in the very idea of a model-theoretic vocabulary.
It is undoubtedly true that Barwise’s category theoretic approach captures essential features of the interaction between syntax and semantics. Thisapproach has certainly not yet been fully exploited. It may be that we haveto know much more about extensions of first order logics in general beforethe fine points that Barwise’s approach brings forward can flourish.
One challenge any attempt to develop a theory of syntax for model- theoretically defined languages has to face is the so called ∆-operation,arising as follows: A model class is said to be PC (L∗) if it is the class ofreducts of elements of an L∗-definable model class. If a model class and itscomplement (among structures of the same vocabulary) are PC (L∗), we saythat the model class is ∆(L∗). We can view ∆(L∗) as an abstract logic in anatural sense, and it indeed satisfies all the required properties. Moreover, ifL∗ is κ-compact (or axiomatizable), then so is ∆(L∗), and if L∗ satisfies theL ¨owenheim-Skolem Theorem down to κ, then so does ∆(L∗).
The Interpolation Property implies ∆(L∗) = L∗. Thus ∆(L∗) is an attempt to approach the Interpolation Property without losing such properties asℵ0-compactness. This lead to the question, does ∆(L∗) itself satisfy theInterpolation Property? Also, the question arose, whether we can buildup some kind of real syntax for ∆(L∗), if we know L∗ has a nice syntax.
In particular, does ∆(L (Q1)) have a (nice) syntax? (For recent partial results on this question, see [17] and [36]). Friedman (see [18]) proved that∆(L (Q1)) does not have the Interpolation Property, answering a question Keisler has asked. On the other hand, Barwise proved that ∆(L have the Interpolation Property. The story is the following: Mostowski hadproved in [30] that if L∗ is a logic extending first order logic in which ( , <) isdefinable and which has the Interpolation Property, then for every recursiveordinal α there is a sentence the class of countable models of which (codedas a subset of the Baire space ) is not a Borel set of class α. Barwise generalized this to: If L∗ is a logic extending first order logic in which ( , <)is definable, then LHYP ⊆ ∆(L∗). This gave: Barwise had already in [1] proved that LHYP has the Interpolation Prop- (Q0)) has it. Barwise and independently Makowsky [27] extended this to generalizations of Q0 involving an arbitraryset X of integers, leading to a characterization of L about the ∆-operation competes with the beauty and simplicity of the earlyresult Theorem 3.
§4. Back-and-forth properties.
model-theoretic characterization of first order quantifiers to the context ofhis own more general concept of generalized quantifiers using an adaption BARWISE: ABSTRACT MODEL THEORY AND GENERALIZED QUANTIFIERS of the back-and-forth technique, which he had previously rediscovered. Thistechnique became a favorite of Barwise, too.
Let L be a finite relational vocabulary. It is easy to prove by induction on k that there are, up to logical equivalence, only finitely many first orderL-formulas of quantifier rank ≤ k with the free variables x1, . . . , xn. LetFmln denote the finite set of these formulas. Let us consider two models M and N of the vocabulary L. For any finite sequence ¯ another sequence ¯y (of the same length n) of elements of N we write x)≡n (N, ¯y) x satisfies in M the same elements of Fmln that the sequence ¯y satisfies in N. In the special case that n = 0 the set Fml0 consists of sentences.
In this case the relation ≡0 is an equivalence relation on L-structures with finitely many equivalence classes, each definable by a sentence in Fml0 .
Lemma 4. A class of L-structures is first order definable if and only if for some k it is the union of equivalence classes of ≡0 .
Proof. Suppose a class K of L-structures is first order definable by φ with quantifier rank k. Clearly K is closed under ≡0 and therefore is the union of equivalence classes of ≡0 . Conversely, every equivalence class of ≡0 is first order definable by a sentence in Fml0 . Therefore also the union of some of these finitely many classes is first order definable.
The relation ≡n has the following important back-and-forth property: x)≡n (N, ¯y) and a is an element of M , then there is an element b of N such that (M, ¯ x, a)≡n+1(N, ¯y, b).
x)≡n (N, ¯y) and b is an element of N , then there is an element a of M such that (M, ¯ x, a)≡n+1 (N, ¯y, b).
Fra¨ıss´e [14] generalized this to the concept of a back-and-forth sequence, which came to play a central role in the study of infinitary logics. A back-
and-forth sequence of length k for M and N is a sequence {Ei : i ≤ k} of
binary relations between ¯
x ∈ M k−i and ¯y ∈ N k−i such that B1 ∅ Ei ∅ for all i ≤ k.
B2 If ¯ xEi ¯y, then the sequence ¯x satisfies in M the same elements of Fmlk−i that the sequence ¯y satisfies in N.
xEi ¯y and a is an element of M , there is an element b of N x, a)Ej(¯y, b).
xEi ¯y and b is an element of N , then there is an element a of x, a)Ej(¯y, b).
Theorem 5 (Fra¨ıss´e). M and N satisfy the same first order sentences of quantifier-rank ≤ k if and only if there is a back-and-forth sequence of lengthk for M and N.
Proof. Let us first assume M ≡0 N. Then {≡k−i : i ≤ k} is a back-and- forth sequence of length k for M and N. On the other hand, if {Ei : i ≤ k}is a back-and-forth sequence of length k for M and N, then it is easy toprove by induction that ¯ x≡k−i ¯y for all i ≤ k.
By putting together Lemma 4 and Theorem 5 we get a syntax-free charac- terization of first order logic, which proves quite useful in the forthcomingmodel-theoretic characterization.
Lemma 6. A class K of L-structures is first order definable if and only if there is a natural number k such that whenever A ∈ K and there is a back-and-forthsequence of length k for A and B, then B ∈ K.
A back-and-forth set for M and N is a binary relation E between arbitrary
x ∈ M < and ¯y ∈ N < of the same finite length such that xE ¯y, and the length of ¯ x is n, then the sequence ¯ same elements of Fmln0 that the sequence ¯y satisfies in N.
xE ¯y and a is an element of M , there is an element b of N such that x, a)E(¯y, b).
xE ¯y and b is an element of N , then there is an element a of M such x, a)E(¯y, b).
If E is a back-and-forth set, then we get a back-and-forth sequence of any xEi ¯y hold if and only if ¯ xE ¯y. The simple “back-and-forth” proof of the following fundamental lemma is usually credited to Cantor: Theorem 7. If M and N are countable and have a back-and-forth set, then §5. Lindstr¨om’s Theorem. We defined above the concept of a back-and-
forth sequence of length k for structures M and N. In the following theoremwe take advantage of a generalization of this concept. Let (D, <) be anylinear order. A sequence {Ei : i ∈ D} is a back-and-forth sequence of type(D, <) for structure M and N if the above conditions (B1)-(B4) hold when“i ≤ k” is replaced by “i ∈ D” and “i < j” is replaced by “i <D j”.
Theorem 8 (Lindstr ¨om [23] characterization of L ℵ0-compact logic that satisfies the L¨owenheim-Skolem theorem down to ℵ0.
Proof. Suppose L is a finite vocabulary and (L∗, |=∗) is an abstract logic for L. Assume that L∗ is an ℵ0-compact extension of first order logicsatisfying the L ¨owenheim-Skolem theorem down to ℵ0, and φ is an L∗-sentence, not equivalent to a first order sentence. (The assumption thatL is finite can be eliminated but we omit this detail.) By Lemma 6, forany natural number k there are L-structures M |=∗ φ and N |=∗ φ and aback-and-forth sequence of length k for A and B. Let : L → L′ be a namechanger with L∩L′ = ∅, and (φ) the corresponding translation of φ into an(L′)∗-sentence. Let D be a new unary predicate symbol and < a new binary BARWISE: ABSTRACT MODEL THEORY AND GENERALIZED QUANTIFIERS predicate symbol. Let K be a vocabulary which contains L ∪ L′ ∪ {D, <}together with some other necessary predicates (that we do not specify in thissketch). Let be a K∗-sentence such that a K-structure N is a model of 1. N ↾ L |=∗ φ2. N ↾ L′ |=∗ (φ)3. (D, <)N is a linear order.
4. N ↾ (K \ {L ∪ L′}) codes a back-and-forth sequence of type (D, <)N for N ↾ L and (N ↾ L′) −1.
has models with (D, <)N arbitrarily long finite linear order. By applying the assumptions about L∗ we can find a countable K-structure N which is a model of such that (D, <)N is non-well-founded.
Let d0 >D d1 >D . . . be an infinite descending chain in (D, <)N. Let forany ¯ It is easy to see that E is a back-and-forth set for N ↾ L and (N ↾ L′) −1. ByTheorem 7, N ↾ L ∼ = (N ↾ L′) −1. This contradicts the assumption that the satisfaction relation of L∗ is closed under isomorphism.
Let us look at the proof more closely. The role of the L ¨owenheim-Skolem theorem is to make Theorem 7 available. On the other hand, it is only needed
to conclude that if M |=∗ φ and there is a back-and-forth set for M and N,
then also N |=∗ φ. Barwise calls this property of L∗ the Karp property.
It is a consequence of the L ¨owenheim-Skolem theorem down to ℵ0 (and
equivalent to it under the assumption of Interpolation Property, as Barwise
proved in [3]), and we may reformulate Theorem 8 as follows:
is the largest ℵ0-compact logic that has the Karp property. What is the role of ℵ0-compactness? We obtain a sentence property that it has models N with (D, <)N of any finite length, but models with (D, <)N non-well-founded. Let us put this in an abstract form,
following Barwise [3]: The well-ordering number wo( ) of a sentence
any abstract logic for a vocabulary containing a unary predicate symbol Dand a binary predicate symbol <, is the smallest (if any exist) ordinal suchthat if has a model N with (D, <)N well-ordered in type > , then model N with (D, <)N non-well-ordered. The well-ordering number wo(L∗)
of an abstract logic L∗ is the supremum of all wo( ), where
ℵ0-compact logic L∗ has, of course, w(∗) = is the largest logic with the Karp property, the well-ordering Lopez-Escobar [26, 25] proved that the well-ordering number of the infini- tary logic Lκ is < (2κ)+. Thus L∞ is what is called a bounded logic, i.e.,
∈ L∞ (even if wo(L∞ ) itself does not exist). The result of Lopez-Escobar raises the question whether there is an infinitaryanalogue of Theorem 8. Barwise studied this question in [2] and [3]. Beforeexamining these results in detail, we review some preliminaries in infinitarylogic.
§6. Infinitary back-and-forth properties. We refer to [21] for the definition
of quantifier rank in the logic L∞ . Let Fmln be the set of formulas of L∞with quantifier rank ≤ and at most x1, . . . , xn free. It is easy to prove by induction on that Fmln has, up to logical equivalence, at most x) ≡n (N, ¯y) if the sequence ¯x satisfies in M the same elements of Fmln that the sequence ¯y satisfies in N. Thus ≡0 is an equivalence relation in the class of all L- equivalence classes. Thus we have, analogously Lemma 9. 1. A class of L-structures is L∞ -definable if and only if for some it is the union of equivalence classes of ≡0.
2. Suppose κ = κ. A class of L-structures is Lκ -definable if and only if for some < κ it is the union of equivalence classes of ≡0.
A back-and-forth sequence of length for M and N is a sequence {En :
x ∈ M n and ¯y ∈ N n such that 1. ∅ E0α ∅ for all α ≤ .
x satisfies in M the same elements of Fmln0 that the sequence ¯y satisfies in N.
α y and a is an element of M , there is an element b of N x, a)En+1(¯y, b).
α y and b is an element of N , then there is an element a of x, a)En+1(¯y, b).
The proof of the following result is almost identical to the proof of Theorem 10 (Karp [19]). M and N satisfy the same L∞ -sentences of if and only if there is a back-and-forth sequence of length §7. Characterizing infinitary logics. Let us return to the problem whether
Theorem 8 has a generalization to infinitary logic. By combining Lemma 9and Theorem 10 with the remarks we have already made, we obtain: Theorem 11 (Barwise [3]). Assume κ = with the Karp property, the well-ordering number of which is ≤ κ.
BARWISE: ABSTRACT MODEL THEORY AND GENERALIZED QUANTIFIERS Theorem 11 characterizes some infinitary logics, but there is the awkward What about all Lκ , where κ < κ = ℵn? Barwise succeeded in characterizing also these logics by thinking ofthem in terms of definability constraints, as in generalized recursion theory,rather than cardinality constraints. This idea had already proved useful inhis other work (see [21]).
On the other hand, we can leave κ = κ as it is, but ask if the rather strong Karp property can be weakened. A combination of a L ¨owenheim-Skolemtype property and the boundedness property (and κ = κ) is used in [37] tocharacterize, not Lκ , but a new infinitary language between Lκ and Lκκ,one with the Interpolation Property.
§8. Absolute logics. Barwise wanted to give a generalized recursion the-
oretic definition of when we should call a logic, looking at it from outside,first order. Clear cases of first order logics were weak second order logic(with variables for finite sets), L (Q0) and the admissible fragment LHYP.
Intuitively a logic is, from outside, first order if the truth of a sentence ina structure should depend only on what kind of elements the domain Mof M has, not on what kind of subsets M has. This leads to the followingdefinition: Definition 13. Let T be a true set theory extending the Kripke-Platek axioms KP. An abstract logic L∗ is absolute relative to T if there are Σ1-
predicates R(x, y) and S(x, y, z) and a Π1-predicate P(x, y, z) such that
1. For all φ : φ ∈ L∗ if and only if R(φ, L).
2. For all φ ∈ L∗ and all L-structures M, M |=∗ φ if and only if S(M, φ, L).
3. The following is a theorem of T : For all languages z, all z-structures M and all φ such that R(φ, z), S(M, φ, z) if and only if P(M, φ, z).
An abstract logic is strictly absolute if it is absolute relative to KP (or
KP +Infinity).
In specific results absolute logics are assumed to satisfy various closure conditions like closure under conjunction and other logical operations. Insuch cases the operations manifesting the closure are assumed to be absolute,too.
If L∗ is an abstract logic and A is an admissible set, we use L∗ to denote the sub-logic of L∗ consisting of sentences which are elements of A. ForA = H (κ) we denote L∗ by L∗ .
to KP. The weak second order logic is strictly absolute. The unboundedlogic L∞ (WO) is absolute relative to KP +Σ1-separation. If we add the ∀x1∃x2∀x3 · · · φn(x1, . . . , xp , ¯y) ∃x1∀x2∃x3 · · · φn(x1, . . . , xp , ¯y) to L∞ an interesting (also unbounded) logic, denoted by L∞G emerges.
This logic is absolute relative to KP +Σ1−separation. The smallest admissi-ble fragment LHYP of L is an interesting absolute logic (see Theorem 3).
and second order logic L2 are not absolute relative to any true first order set theory T . These logics would be absoluterelative to a second order set theory but that is beside the point here as weplan to take advantage of results of first order set theory, such as: Theorem 14 (Levy Reflection Principle). If φ( ¯ x ∈ H (κ)(φ( ¯ x) → H (κ) |= φ( ¯ We can make some immediate observations about absolute logic L∗ by means of Theorem 14: If φ ∈ L∗κ+ has a model, then it has a model inH (κ+) and therefore a model of cardinality ≤ κ. Thus L∗κ+ satisfies the L ¨owenheim-Skolem Theorem down to κ. We can prove the Karp Propertyalmost as quickly: Suppose there is a back-and-forth set E for M and N,but for some φ ∈ L∗ we have M |=∗ φ and N |=∗ Theorem 14 such objects L, φ, M, N, E must exist already in HC . But thenM and N are countable, hence isomorphic by Lemma 7, a contradiction. Weknow from [3] that Interpolation Property together with the Karp Propertyimply L ¨owenheim-Skolem Theorem down to ℵ0. Thus we may concludethat no absolute logic extending L can have the Interpolation Property.
Theorem 15 (Barwise [2]). If L∗ is a strictly absolute logic and A is an admissible set, then L∗ is contained in L Proof. The first observation is that it suffices to prove this for countable admissible sets. Why? Suppose the claim fails. Thus there is an admissibleset A and a sentence φ ∈ L∗ such that for all ). This can be written as a Σ1-property of A. If an A with this property exists at all, one such exists in HC by Theorem 14.
The second observation is that Barwise proved in [1] that if A is a count- able admissible set, then LA satisfies the Interpolation Property, whence∆(LA) = LA. Thus it suffices to prove that if A is a countable admissibleset, then L∗ is contained in ∆(L A). Suddenly the claim has become much easier. To find an explicit LA-definition for a given φ ∈ L∗ is like looking fora needle in a haystack, compared to writing an “implicit” ∆(LA)-definition,where new predicates can set things in their right places and provide extratools.
BARWISE: ABSTRACT MODEL THEORY AND GENERALIZED QUANTIFIERS Finally, suppose L is a finite vocabulary, L∗ is a strictly absolute logic and φ ∈ A is an L∗-sentence. We take a new vocabulary K containing L and thenew symbols ε, ¯ L. It is possible to write down a sentence Φ of KA such that the following conditions are equivalent for any infinite L-structure A: 1. A |=∗ φ.
2. There is an expansion M of A which is a model of Φ and which satisfies 3. Every expansion M of A to a model of Φ satisfies S( ¯ The point of our assuming that L∗ is strictly absolute rather than just absoluteis the following: When we consider the expansions M of A as set-theoreticalstructures, we have no way of knowing that they are well-founded. Stillwe want to form the Mostowski collapse of M in order to get e.g., from to the real φ. Fortunately we have included in Φ an infinitary sentence guaranteeing that at least the transitive closure of ¯φ So we take the standard part M0 of M, knowing that it is still a model ofKP, and collapse M0. It follows that φ is ∆(LA)-definable.
We get from Theorem 15 as a special case the promised characterization of infinitary languages Lκ for any κ: Corollary 16 (Barwise [2]). If L∗ is a strictly absolute logic and κ > Corollary 17. L∞ is the largest strictly absolute logic.
What about logics that are absolute but not strictly absolute? Since abso- lute logics have the Karp property, we can infer from Corollary 12 that L∞is the largest bounded absolute logic. The logic L∞G is absolute but not asub-logic of even L∞∞. Maybe all absolute logics are sublogics of L∞G .
The problem comes with Interpolation: ∆(L∞G) = L∞G . So we have tosettle with the result (LAG = L∞G ∩ A): Proposition 18 (Oikkonen [31]). If L∗ is an absolute logic and A is an admissible set, then L∗ is contained in ∆(L Burgess [11] developed further the theory of absolute logics using methods of descriptive set theory. For example, he showed that formulas of allabsolute logics have similar approximations as do formulas of L∞G .
§9. New generalized quantifiers. Early work on generalized quantifiers
was dominated by questions related to the so-called cardinality quantifiersQn. A lot of insight was gained about Q0 and Q1, but the rest have remainedhard to tackle. For example, we have still the following innocent lookingopen problem: Open Problem. Is L
Chang [12] gave a positive answer using GCH. Shelah [35] has recently (Q1, Q2) may fail to be ℵ0-compact.
Maybe other kinds of quantifiers are easier to tackle? Indeed, Shelah [33] introduced a host of new axiomatizable extensions of first order logic. A
particularly nice new quantifier was the cofinality quantifier
A |= Qcf xy φ(x, y, ¯a) ⇐⇒ {(c, d ) : A |= φ(c, d, ¯a)} is a linear order of its field of cofinality ℵn. (Qcf ) is that it is, irrespectively of n and unlike (Qn), fully compact, i.e., κ-compact for all κ, and axiomatizable. As is characteristic of each new quantifier that was ever proposed, L fails to have the Interpolation Property. In his search for new logics, Shelah[33] introduced the logic L (aa). This logic has a generalized second order quantifier aa s φ(s) where s ranges over countable subsets of the domain.
Intuitively aa s φ(s) says that almost all countable sets s satisfy φ(s). Nat-
urally there are many candidates for interpreting “almost all”, but the one
that works here well is the following: A family which contains “almost all”
countable subsets should at least cover every countable subset, i.e., if A ⊆ M
is countable, there should be s ∈ X with A ⊆ s. In such a case we call
X “unbounded”. Another requirement is that X should be “closed” in the
following sense: Whenever s0 ⊆ s1 ⊆ . . . is an increasing -sequence of
elements of X , also ∪n< sn should be in X . A set which is both unbounded
and closed is called c.u.b. A family which meets every c.u.b. family is called
stationary. The c.u.b. families form a normal filter on any set. Normality
means that the following Fodor’s Lemma holds: If X is a stationary family
and f is a function on X such that f(x) ∈ x for each x ∈ X , then there is
a stationary Y ⊆ X such that f is constant on Y . The interpretation of aa
is thus:
M |= aa s φ(s) ⇐⇒ {s : M |= φ(s)} contains a c.u.b. set. We can express both Q1x φ(x, ¯y) and Qcf xy φ(x, y, ¯x) by means of the Q1x φ(x, ¯y) ↔ ¬ aa s ∀x(φ(x, ¯y) → s(x)) and, assuming φ(x, y, ¯z) defines a linear order without last element, Qcf xy φ(x, y, ¯z) ↔ aa s ∀x(∃y φ(x, y, ¯z) → ∃y(s(y) ∧ φ(x, y, ¯z))). Theorem 19. [9, 10] The logic L(aa) is complete relative to the axioms A0 aa s φ(s) ↔ aa s′ φ(s′)A1 ¬ aa s(false)A2 aa s (s(x)), aa s′ (s ⊆ s′)A3 aa s φ ∧ aa s A4 aa s (φ → ) → (aa s φ → aa s )A5 ∀x aa s φ(x, s) → aa s ∀x(s(x) → φ(x, s)) BARWISE: ABSTRACT MODEL THEORY AND GENERALIZED QUANTIFIERS ), where s is not free in φ, infer (φ → aa s ) together with the usual axioms and rules of first order logic.
Axiom A5 can be seen as a formulation of Fodor’s Lemma giving the axioms a special air of naturalness. For some time there was great enthusiasmabout this nice fragment of second order logic. Unfortunately even this logicfails to have the Interpolation Property [28]. There is even an implication inL (Q1) alone with no interpolant in L of the study of generalized quantifiers is the following relative InterpolationProperty for L Theorem 20. [34] Stationary logic interpolates cofinality logic: If φ and In his paper [6] Barwise makes the observation that whenever a new ℵ0- compact logic is proposed, it gives rise to an infinitary version with all
the nice properties that the original admissible fragments enjoy. In this
paper Barwise turns this observation into a theorem. He formulates an
Omitting Types Property for an abstract logic L∗ and proves that if L∗ is an
ℵ0-compact logic and L∗ satisfies Omitting Types Property, then L∗
many nice properties, e.g., a completeness theorem, boundedness theorem,and the admissible fragments are Σ1-compact.
Barwise made also other contributions to the theory of generalized quanti- fiers, dealing with questions not directly related to issues discussed above. Heapplied approximations of branching quantifiers in model theory [4], andisolated monotonicity [7] and branching phenomena ([5]) among naturallanguage quantifiers.
§10. Conclusion. When Barwise entered the abstract model theory scene
around 1971, he quickly published the main ideas in a couple of very readablepapers, making the area attractive to young logicians. He arrived at hisconcept of absolute logic by trying to characterize what does it mean thatthe semantics of a logic depends on the underlying set theory in first orderway only. When this is the case, he saw, we can combine metamathematicalmethods and absoluteness arguments to prove theorems about the logic. Hewas right. The use of properties of (often non-standard) models of set theoryto get model theoretic results, became a standard method. Subsequentlyabstract model theory got stuck with hard problems related to constructinguncountable structures with pre-described properties. Barwise turned toapplications of generalized quantifiers in linguistics and computer science.
The emergence of finite model theory and descriptive complexity theory ledto sharply increased interest in infinitary logic. Will abstract model theoryalso experience a rebirth in the finite context? [1] Jon Barwise, Infinitary logic and admissible sets, The Journal of Symbolic Logic, vol. 34
, Annals of Mathematical Logic, vol. 4 (1972), pp.
, Axioms for abstract model theory, Annals of Mathematical Logic, vol. 7 (1974),
, Some applications of Henkin quantifiers, Israel Journal of Mathematics, vol. 25
, On branching quantifiers in English, Journal of Philosophical Logic, vol. 8
, The role of the omitting types theorem in infinitary logic, Archiv f¨ur mathema-
tische Logik und Grundlagenforschung, vol. 21 (1981), no. 1–2, pp. 55–68.
[7] Jon Barwise and Robin Cooper, Generalized quantifier and natural language, Linguis-
tics and Philosophy, vol. 4 (1981), pp. 159–219.
[8] Jon Barwise and Solomon Feferman (editors), Model-theoretic logics, Perspectives in
Mathematical Logic, Springer-Verlag, New York, 1985.
[9] Jon Barwise, Matt Kaufmann, and Michael Makkai, Stationary logic, Annals of
Mathematical Logic, vol. 13 (1978), no. 2, pp. 171–224.
, A correction to: “Stationary logic”, Annals of Mathematical Logic, vol. 20
[11] John P. Burgess, Descriptive set theory and infinitary languages, Zbornik Radova,
vol. 2 (1977), no. 10, pp. 9–30, Set theory, foundations of mathematics (Proc. Sympos.,Belgrade, 1977).
[12] Chen-Chung Chang, A note on the two cardinal problem, Proceedings of the American
Mathematical Society, vol. 16 (1965), pp. 1148–1155.
[13] Solomon Feferman, Two notes on abstract model theory. II. Languages for which the set of valid sentences is semi-invariantly implicitly definable, Fundamenta Mathematicæ, vol. 89
(1975), no. 2, pp. 111–130.
Etude de certains op´erateurs dans les classes de relations, d´efinis `a partir d’isomorphismes resteints, Zeitschrift f¨ur mathematische Logik und Grundlagen der
Mathematik, vol. 2 (1956), pp. 59–75.
[15] Harvey Friedman, One hundred and two problems in mathematical logic, The Journal
of Symbolic Logic, vol. 40 (1975), pp. 113–129.
Uber einen Quantifikator mit zwei Wirkungsbereichen, Colloq. Found.
Math., Math. machines and appl. (Tihany, 1962) (Budapest), Akad. Kiad ´o, 1965, pp. 31–36.
[17] Lauri Hella and Kerkko Luosto, Finite generation problem an n-ary quantifiers, Quantifiers, logics, models and computation (M. Krynicki, M. Mostowski, and L. Szczerba,
editors), vol. 248, Kluwer Academic Publishers, 1995, pp. 63–104.
[18] John E. Hutchinson, Model theory via set theory, Israel Journal of Mathematics,
vol. 24 (1976), no. 3–4, pp. 286–304.
[19] Carol R. Karp, Finite-quantifier equavalence, Theory of models (Proc. 1963 internat.
sympos. Berkeley) (Amsterdam), North-Holland, 1965, pp. 407–412.
[20] H. Jerome Keisler, Logic with the quantifier “there exist uncountable many”, Annals
of Mathematical Logic, vol. 1 (1970), pp. 1–93.
[21] H. Jerome Keisler and Julia Knight, Barwise: Infinitary logic and admissible sets, this Bulletin, vol. 10, no. 1, pp. 4–36, this issue.
[22] Per Lindstr ¨om, First order predicate logic with generalized quantifiers, Theoria, vol. 32
, On extensions of elementary logic, Theoria, vol. 35 (1969), pp. 1–11.
BARWISE: ABSTRACT MODEL THEORY AND GENERALIZED QUANTIFIERS , Prologue, Quantifiers, logics, models and computation (M. Krynicki,
M. Mostowski, and L. Szczerba, editors), vol. 248, Kluwer Academic Publishers, 1995,pp. 21–24.
[25] E. G. K. Lopez-Escobar, An addition to: “On defining well-orderings”, Fundamenta
Mathematicæ, vol. 59 (1966), pp. 299–300.
, On defining well-orderings, Fundamenta Mathematicæ, vol. 59 (1966), pp. 13–
[27] Johann A. Makowsky, Securable quantifiers, k-unions and admissible sets, Logic
colloquium ’73 (Bristol, 1973) (Amsterdam), Studies in Logic and the Foundations of Math-
ematics, vol. 80, North-Holland, 1975, pp. 409–428.
[28] Johann A. Makowsky and Saharon Shelah, The theorems of Beth and Craig in abstract model theory. II. Compact logics, Archiv f¨ur mathematische Logik und Grundlagen-
forschung, vol. 21 (1981), no. 1–2, pp. 13–35.
[29] Andrzej Mostowski, On a generalization of quantifiers, Fundamenta Mathematicæ,
, Craig’s interpolation theorem in some extended systems of logic, Logic,
methodology and philosophy of science III (Proc. third internat. congr., Amsterdam, 1967)
(Amsterdam), North-Holland, 1968, pp. 87–103.
[31] Juha Oikkonen, Hierarchies of model-theoretic definability—an approach to second- order logics, Essays on mathematical and philosophical logic (Proc. fourth Scandinavian logic
sympos. and first Soviet-Finnish logic conf., Jyv¨askyl¨a, 1976), Synthese Library, vol. 122,
Reidel, Dordrecht, 1979, pp. 197–225.
[32] Nicholas Rescher, Quantifiers in many-valued logic, Logique et Analyse (N.S.), vol. 7
[33] Saharon Shelah, Generalized quantifiers and compact logic, Transactions of the Amer-
ican Mathematical Society, vol. 204 (1975), pp. 342–364.
, Remarks in abstract model theory, Annals of Pure and Applied Logic, vol. 29
, The pair (ℵn, ℵ0) may fail ℵ0-compactness, Proceedings of the logic colloquium
2001, Lecture Notes in Logic, Association for Symbolic Logic, to appear.
[36] Saharon Shelah and Jouko V ¨a ¨an ¨anen, ∆(l(a1)) is not finitely generated, assuming , A new infinitary logic, to appear.
[38] Robert L. Vaught, The completeness of logic with the added quantifier “there are uncountably many”, Fundamenta Mathematicæ, vol. 54 (1964), pp. 303–304.
E-mail: [email protected]URL: www.math.helsinki.fi/∼logic/people/juoko.vaananen/

Source: http://topavlog08.files.wordpress.com/2008/03/1001-004.pdf