## 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
Q

*n *= {(

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

*Q*0) cannot be (effectively) axiomatized. He
∀

*x*¬

*Q*0

*y *(

*y < x*)
(

*Q*0). 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*
(

*Q*0) 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 *⊆

*A*2 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, if

*L*∗ 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
(

*Q*1)) have a (nice) syntax? (For recent partial
results on this question, see [17] and [36]). Friedman (see [18]) proved that∆(L
(

*Q*1)) 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

*L*HYP ⊆ ∆(

*L*∗). This gave:
Barwise had already in [1] proved that

*L*HYP has the Interpolation Prop-
(

*Q*0)) has it. Barwise and independently
Makowsky [27] extended this to generalizations of

*Q*0 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 order

*L*-formulas of quantifier rank ≤

*k *with the free variables

*x*1

*, . . . , xn*. LetFml

*n *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 Fml

*n *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 Fml

*k*−

*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 length

*k *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 Fml

*n*0 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 that

*L *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

*d*0

*>D d*1

*>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

*D*and 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 Fml

*n *be the set of formulas of

*L*∞with quantifier rank ≤
and at most

*x*1

*, . . . , xn *free. It is easy to prove by
induction on that Fml

*n *has, up to logical equivalence, at most

*x*) ≡

*n *(N

*, *¯

*y*)
if the sequence ¯

*x *satisfies in M the same elements of Fml

*n *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. ∅

*E*0

*α *∅ for all

*α *≤ .

*x *satisfies in M the same elements of Fml

*n*0
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
(

*Q*0) and the admissible fragment

*L*HYP.

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

*M*of 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*. For

*A *=

*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
∀

*x*1∃

*x*2∀

*x*3 · · ·

*φn*(

*x*1

*, . . . , xp , *¯

*y*)
∃

*x*1∀

*x*2∃

*x*3 · · ·

*φn*(

*x*1

*, . . . , 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

*L*HYP of

*L*
is an interesting absolute logic (see Theorem 3).

and second order logic

*L*2 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 in

*H *(

*κ*+) 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 of

*KP*, 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 quantifiers

*Qn*. A lot of insight was gained about

*Q*0 and

*Q*1, 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
(

*Q*1

*, Q*2) 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

*s*0 ⊆

*s*1 ⊆

*. . . *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

*Q*1

*x φ*(

*x, *¯

*y*) and

*Qcf xy φ*(

*x, y, *¯

*x*) by means of the

*Q*1

*x φ*(

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

*Q*1) 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*(

*a*1))

*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

MED J MALAYSIA VOL 48 NO 1 MARCH 1993 EDITORIAL CHOLERA - STILL A MAJOR HEALTH PROBLEM V K E Lim, FRCPath, Department of Medical Microbiology & Immunology, Faculty of Medicine, Universiti Kebangsaan Malaysia, Jalan Raja Muda Abdul Aziz, 50300 Kuala Lumpur The recent outbreaks of cholera in several states of Malaysia serve as atimely reminder that cholera is still a major public heal

EXTRAWURST APRIL 2005: RED BULL In Forbes’ list of European billionaires, somewhere between the Russian oil barons andthe heads of French luxury goods dynasties is Dietrich Mateschitz, an Austrian who hasmade most of his rapidly growing $2bn from one of the unlikeliest brand successes of thelast twenty years. Herr Mateschitz is the father of Red Bull. Red Bull has grown from anunlikely-soundi