(
1,) and the Barwise Compactness Theorem
| This is a file in the archives of the Stanford Encyclopedia of Philosophy. |
|
version |
Stanford Encyclopedia of Philosophy |
content revised
|
In §1 we lay down the basic syntax and semantics of infinitary languages and demonstrate their expressive power by means of examples. §2 is devoted to those infinitary languages which permit only finite quantifier sequences: these languages turn out to be relatively well-behaved. In §3 we discuss the compactness problem for infinitary languages and its connection with purely set-theoretical questions concerning "large" cardinal numbers. In §4 an argument is sketched which shows that most "infinite quantifier" languages have a second-order nature and are, ipso facto, highly incomplete. In §5 we give a brief account of a certain special class of sublanguages of infinitary languages for which a satisfactory generalization of the compactness theorem can be proved. (This section links to a Supplement on the definition of admissible sets.) We conclude with historical and bibliographical remarks in §6.
(1,) and the Barwise Compactness Theorem
,
of
infinite cardinals such that
,
we define a class of infinitary languages in each of which we may
form conjunctions and disjunctions of sets of formulas of cardinality
<
, and quantifications over sequences of
variables of length <
.
Let -- the (finitary) base
language -- be an arbitrary but fixed first-order language with
any number of extralogical symbols. The infinitary language
(,
) has the following basic symbols:
(infinitary
conjunction)
(,
) is defined recursively as follows:
is a preformula;
and
are preformulas,
so are
and
;
is a set of preformulas such that
|| <
,
then
is a preformula;
is a preformula and
X
Var is such that
|X| <
, then
X is a preformula;
is a set of preformulas indexed by a set I,
say
= {i :
i
I},
then we agree to write
for:
or, if I is the set of natural numbers, we write
for:
If X is a set of individual variables indexed by an ordinal
, say X =
{x
:
<
},
we agree to write
(x)<
for
X.
The logical operators
,
,
are defined in the customary manner. We also introduce the
operators
(infinitary disjunction) and
(universal quantification) by
and employ similar conventions as for
,
.
Thus
(,)
is the infinitary language obtained from
by permitting conjunctions and disjunctions
of length <
and
quantifications[1]
of length <
. Languages
(,)
are called finite-quantifier languages, the rest
infinite-quantifier languages. Observe that
(,)
is just
itself.
Notice the following anomaly which can arise in an infinitary
language but not in a finitary one. In the language
(1,),
which allows countably infinite conjunctions but only finite
quantifications, there are preformulas with so many free variables
that they cannot be "closed" into sentences of
(1,)
by prefixing quantifiers. Such is the case, for example, for the
(1,)-preformula
x0 < x1where
contains the binary relation symbol <.
For this reason we make the following
Definition. A formula ofIn this connection, observe that, in general, nothing would be gained by considering "languages"
(,) with
>
. For example, in the
"language"
(,1),
formulas will have only finitely many free variables, while there
will be a host of "useless" quantifiers able to bind infinitely many
free
variables.[2]
Having defined the syntax of
(,),
we next sketch its semantics. Since the extralogical
symbols of
(,)
are just those of
,
and it is these symbols which determine the form of the structures
in which a given first-order language is to be interpreted, it is
natural to define an
(,)-structure
to be simply an -structure.
The notion of a formula of
(,) being satisfied in an
-structure
A (by a sequence of elements from the
domain of A) is defined in the same
inductive manner as for formulas of
except that we must add two extra
clauses corresponding to the clauses for
and
X in the
definition of preformula. In these two cases we naturally define:
These informal definitions need to be tightened up in a rigorous development, but their meaning should be clear to the reader. Now the usual notions of truth, validity, satisfiability, and model for formulas and sentences offor all
(,) become available. In particular, if
A is an
-structure and
Sent(,),
we shall write
A
for A is a model of
, and
for
is valid, that is, for all
A,
A. If
Sent(,),
we shall write
for
is a logical consequence of
, that is, each model of
is a model of
.
We now give some examples intended to display the expressive power of
the infinitary languages
(,) with
1. In each case it is
well-known that the notion in question cannot be expressed in any
first-order language.
Characterization of the standard model of arithmetic in
(1,).
Here the standard model of arithmetic is the structure
N = (N, +,
, s, 0),
where N is the set of natural numbers,
+,
, and 0 have their usual meanings, and s is
the successor operation. Let
be the first-order language
appropriate for N. Then the class of
-structures isomorphic to N coincides
with the class of models of the conjunction of the following
(1,) sentences (where 0 is a name of 0):
The terms snx are defined recursively by s0x = x; sn+1x = s(snx).
Characterization of the class of all finite sets in
(1,).
Here the base language has no extralogical symbols. The class of all
finite sets then coincides with the class of models of the
(1,)-sentence
Truth definition in
(1,) for a countable base language .
Let
be a countable first-order language (for
example, the language of arithmetic or set theory) which contains a name
n for each natural number n, and let
0,
1,
... be an enumeration of its sentences. Then the
(1,)-formula
Tr(x) =dfis a truth predicate for(x = n
inasmuch as the sentence
Tr(n)is valid for each n.
Characterization of well-orderings in
(1,1).
The base language
here includes a binary predicate symbol
. Let
1 be the usual
-sentence
characterizing linear orderings. Then the class of
-structures in which the interpretation of
is a well-ordering coincides with the class of models of
the
(1,1) sentence
=
1
2, where
Notice that the sentence(x
2 contains an infinite
quantifier: it expresses the essentially second-order
assertion that every countable subset has a least member. It can in
fact be shown that the presence of this infinite quantifier is
essential: the class of well-ordered structures cannot be
characterized in any finite-quantifier language. This example
indicates that infinite-quantifier languages such as
(1,1) behave rather like second-order languages;
we shall see that they share the latters' defects (incompleteness) as well
as some of their advantages (strong expressive power).
Many extensions of first-order languages can be translated
into infinitary languages. For example, consider the generalized
quantifier language
(Q0)
obtained from
by adding a new quantifier symbol
Q0 and interpreting
Q0x(x) as
there exist infinitely many x such that
(x). It is easily seen that the sentence
Q0x(x) has the
same models as the
(1,)-sentence
Thus
(Q0) is, in a natural
sense, translatable into
(1,).
Another language translatable into
(1,)
in this sense is the weak second-order language obtained by
adding a countable set of monadic predicate variables to
which are then interpreted as ranging
over all finite sets of individuals.
(1,1)
resemble second-order languages inasmuch as they allow
quantification over infinite sets of individuals. The fact that this
is not permitted in finite-quantifier languages suggests that these
may be in certain respects closer to their first-order counterparts
than might be evident at first sight. We shall see that this is
indeed the case, notably in the case of
(1,).
The language
(1,) occupies a special
place among infinitary languages because--like first-order languages--it
admits an effective deductive apparatus. In fact, let us add to
the usual first-order axioms and rules of inference the new axiom scheme
for any countable set
Form(1,) and any
, together with the new rule of inference
and allow deductions to be of countable length. Writing
* for deducibility in this sense, we then
have the
As an immediate corollary we infer that this deductive apparatus is adequate for deductions from countable sets of premises in
(1,). That is, with the obvious extension of notation, we
have, for any countable set
Sent(1,)
(2.1)This completeness theorem can be proved by modifying the usual Henkin completeness proof for first-order logic, or by employing Boolean-algebraic methods. Similar arguments, applied to suitable further augmentations of the axioms and rules of inference, yield analogous completeness theorems for many other finite-quantifier languages.
If just deductions of countable length are admitted, then no
deductive apparatus for
(1,) can be set up which is
adequate for deductions from arbitrary sets of premises, that is,
for which (2.1) would hold for every set
Sent(1,),
regardless of
cardinality. This follows from the simple observation that there is a
first-order language
and an uncountable set
of
(1,)-sentences such that
has no model but every countable subset of
does. To see this, let
be the language of arithmetic augmented by
1
new constant symbols
{c :
<
1}
and let
be the set of
(1,)-sentences
{}
{c
c
:
}, where
is the
(1,)-sentence
characterizing the standard model of arithmetic. This example also
shows that the compactness theorem fails for
(1,) and so also for any
(,) with
1.
Another result which holds in the first-order case but fails for
(,)
with
1 (and also for
(1,1),
although this is more difficult to prove) is the prenex normal
form theorem. A sentence is prenex if all its
quantifiers appear at the front; we give an example of an
(1,)-sentence which is not
equivalent to a conjunction of prenex sentences. Let
be the first-order language without extralogical
symbols and let
be the
(1,)-sentence
which characterizes the class of finite sets. Suppose that
were equivalent to a conjunction
of prenex
(1,)-sentences
i.
Then each
i is of the form
Q1x1 ... Qnxnwhere each Qk is
or
and
i
is a (possibly infinitary) conjunction or disjunction of formulas of
the form xk = xl or
xk
xl.
Since each
i is a sentence, there are only
finitely many variables in each
i,
and it is easy to see that each
i
is then equivalent to a first-order formula. Accordingly each
i may be taken to be a first-order
sentence. Since
is assumed to be equivalent to the
conjunction of the
i, it follows
that
and the set
=
{i : i
I} have the same models. But obviously
, and hence also
, have models of all
finite cardinalities; the compactness theorem for sets of first-order
sentences now implies that
, and hence also
, has an infinite model, contradicting the definition of
.
Turning to the Löwenheim-Skolem theorem, we find that
the downward version has adequate generalizations to
(1,) (and, indeed, to all infinitary languages). In fact, one
can show in much the same way as for sets of first-order sentences that if
Sent(1,) has an infinite model
of cardinality
||, it has a model
of cardinality the larger of
0 ,
||. In particular, any
(1,)-sentence with an
infinite model has a countable model.
On the other hand, the upward Löwenheim-Skolem theorem in
its usual form fails for all infinitary languages. For example,
the
(1,)-sentence
characterizing the standard model of arithmetic has a model of
cardinality
0 but no models
of any other cardinality. However, all is not lost here, as we shall see.
We define the Hanf number h(L) of a language
L to be the least cardinal
such that, if an
L-sentence has a model of cardinality
, it has models of arbitrarily large cardinality. The
existence of h(L) is readily established. For each
L-sentence
not possessing models of
arbitrarily large cardinality let
() be the least cardinal
such that
does not have a model of cardinality
. If
is the supremum of all the
(), then, if a sentence of
L has a model of cardinality
,
it has models of arbitrarily large cardinality.
Define the cardinals
() recursively by
Then it can be shown that
h(similar results holding for other finite-quantifier languages. The values of the Hanf numbers of infinite-quantifier languages such as
(1,1)
are sensitive to the presence or otherwise of large cardinals, but
must in any case greatly exceed that of
(1,).
A result for
which generalizes to
(1,) but to no other infinitary language is the
Craig Interpolation Theorem: IfThe proof is a reasonably straightforward extension of the first-order case.
Finally, we mention one further result which generalizes nicely to
(1,)
but to no other infinitary language. It is well known that, if
A is any finite
-structure with only finitely many
relations, there is an
-sentence
characterizing A up to
isomorphism. For
(1,) we have the
following generalization known as
Scott's Isomorphism Theorem. If A is a countableThe restriction to countable structures is essential because countability cannot in general be expressed by an
(1,)-sentence.
We construct the following definition. Let
be an
infinite cardinal. A language L is said to be
-compact (resp. weakly
-compact) if whenever
is a
set of L-sentences (resp. a set of
L-sentences of cardinality
) and each subset of
of cardinality
<
has a model, so does
. Notice that the usual compactness theorem for
is precisely the assertion that
is
-compact. One reason for according significance
to the
-compactness property is the following. Call L
-complete (resp. weakly
-complete) if there is a deductive system
P for L with deductions of
length <
such that, if
is a
P-consistent[3]
set of L-sentences
(resp. such that ||
), then
has a model. Observe that
such a P will be adequate for deductions from
arbitrary sets of premises (of cardinality
) in the sense of §2. It is
easily seen that if L is
-complete or weakly
-complete, then L is
-compact or weakly
-compact. Thus, if
we can show that a given language is not (weakly)
-compact, then there can be no deductive system for it
with deductions of length <
adequate for
deductions from arbitrary sets of premises (of cardinality
).
It turns out, in fact, that most languages
(,
) fail to
be even weakly
-compact, and, for those that are,
must be an exceedingly large cardinal. We
shall need some definitions.
An infinite cardinal
is said to be weakly
inaccessible if
(a)If in addition(b) |I| <
(c)then
is said to be
(strongly) inaccessible. Since
0 is inaccessible, it is normal
practice to confine attention to those inaccessible, or weakly
inaccessible, cardinals that exceed
0. Accordingly, inaccessible or
weakly inaccessible cardinals will always be taken to be
uncountable. It is clear that such cardinals--if they
exist--must be extremely large; and indeed the Gödel
incompleteness theorem implies that the existence of even weakly
inaccessible cardinals cannot be proved from the usual axioms of set
theory.
Let us call a cardinal
compact
(resp. weakly compact) if the language
(,) is
-compact (resp. weakly
-compact). Then we have the following results:
(3.1)Let Constr stand for Gödel's axiom of constructibility; recall that Constr is consistent with the usual axioms of set theory.(3.2)
(3.3) Suppose
(3.4)
(3.5) If Constr holds, then there are no compact cardinals.The import of these results is that the compactness theorem fails very badly for most languages(3.6) Assume Constr and let
(3.7) If Constr holds, then there are no cardinals
(,) with
1.
Some historical remarks are in order here. In the 1930s
mathematicians investigated various versions of the so-called
measure problem for sets, a problem which arose in
connection with the theory of Lebesgue measure on the continuum. In
particular, the following very simple notion of measure was
formulated. If X is a set, a (countably additive two-valued
nontrivial) measure on X is a map
on the power set PX to
the set {0, 1} satisfying:
(a)Obviously, whether a given set supports such a measure depends only on its cardinality, so it is natural to define a cardinal(b)
) = 0 for all x
(c) if A is any countable family of subsets of X, then
A) =
{
to be measurable
if all sets of cardinality
support a measure of
this sort. It was quickly realized that a measurable cardinal must be
inaccessible, but the falsity of the converse was not established until
the 1960s when Tarski showed that measurable cardinals are weakly compact
and his student Hanf showed that the first, second, etc. inaccessibles are
not weakly compact (cf. (3.3)). Although the conclusion that measurable
cardinals must be monstrously large is now normally proved without making
the detour through weak compactness and infinitary languages, the fact
remains that these ideas were used to establish the result in the first
instance.
can be generated from a simple set of axioms by means of a few
straightforward rules of inference. A major consequence of this
theorem is that, if the formulas of
are coded as natural numbers in some constructive way, then the set
of (codes of) valid sentences is recursively
enumerable. Thus, the completeness of a first-order language
implies that the set of its valid sentences is definable in
a particularly simple way. It would accordingly seem reasonable,
given an arbitrary language L, to turn this
implication around and suggest that, if the set of valid
L-sentences is not definable in some simple
fashion, then no meaningful completeness result can be
established for L, or, as we shall say, that
L is incomplete. In this section we are
going to employ this suggestion in sketching a proof that "most"
infinite quantifier languages are incomplete in this sense.
Let us first introduce the formal notion of definability as
follows. If L is a language, A
an L-structure, and X a
subset of the domain A of A, we
say that X is definable in
A by a formula
(x, y1,
. . . , yn) of L if there is a
sequence a1, . . . , an of
elements of A such that X is the subset of all
elements x A for which
(x, a1,
. . . , an) holds in A.
Now write Val(L) for the set of all the valid L-sentences, i.e., those that hold in every L-structure. In order to assign a meaning to the statement "Val(L) is definable", we have to specify
(i) a structure C(L)--the coding structure for L;Then, if we identify Val(L) with its image in C(L) under the coding map, we shall interpret the statement "Val(L) is definable" as the statement "Val(L), regarded as a subset of the domain of C(L), is definable in C(L) by a formula of L."(ii) a particular one-one map--the coding map--of the set of formulas of L into the domain of C(L).
For example, when L is the first-order language
of arithmetic, Gödel originally used as coding structure the
standard model of arithmetic 
and as coding map
the well-known function obtained from the prime factorization theorem
for natural numbers. The recursive enumerability of
Val()
then means simply that the set of codes ("Gödel numbers") of
members of
Val()
is definable in
by an
-formula of
the form
y(x, y),
where
(x, y) is a recursive formula.
Another, equivalent, coding structure for the first-order language of
arithmetic is the
structure[4]
<H(),
| H()> of
hereditarily finite sets, where a set x is
hereditarily finite if x, its members, its members of
members, etc., are all finite. This coding structure takes account of the
fact that first-order formulas are naturally regarded as finite sets.
Turning now to the case in which L is an infinitary
language
(,),
what would be a suitable coding structure in this case? We remarked
at the beginning that infinitary languages were suggested by the
possibility of thinking of formulas as set-theoretical objects, so
let us try to obtain our coding structure by thinking about what kind
of set-theoretical objects we should take infinitary formulas to
be. Given the fact that, for each
Form(,),
and its subformulas, subsubformulas, etc., are all of
length <
[5],
a moment's reflection reveals that formulas of
(,)
"correspond" to sets x hereditarily of cardinality <
in the sense that x, its members, its
members of members, etc., are all of cardinality <
. The
collection of all such sets is written
H(). H()
is the collection of hereditarily finite sets introduced
above, and
H(1) that of all
hereditarily countable sets.
For simplicity let us suppose that the only extralogical symbol
of the base language
is the binary
predicate symbol
(the discussion is easily extended to
the case in which
contains additional extralogical
symbols). Guided by the remarks above, as coding structure for
(,)
we take the structure,
(
Now we can define the coding map of
Form(,) into
().
First, to each basic symbol s of
(,)
we assign a code object
s
H()
as follows. Let
{v:
<
} be an enumeration of the individual variables of
(,).
Then, to each
Symbol Code Object Notation 1 2 3 4 5 = 6 v <0,
Form(,)
we assign the code object
recursively as follows:
for
,
Form(,),
and finally if
Form(,)
with | | < ,
The map
from
Form(,)
into
H() is easily seen to be
one-one and is the required coding map. Accordingly, we agree to identify
Val((,))
with its image in
H() under this coding map.
When is
Val((,))
a definable subset of
()?
In order to answer this question we require the following
definitions.
An
-formula is called a
0-formula
if it is equivalent to a formula in which all quantifiers are of the
form
xy or
xy (i.e.,
x(xy
...) or
x(xy
...)).
An -formula is a
1-formula if it is
equivalent to one which can be built up from atomic formulas and
their negations using only the logical operators
,
,
xy,
x.
A subset X of a set A is said to be
0 (resp.
1) on A if it is definable in the
structure <A,
| A> by a
0- (resp.
1-) formula of
.
For example, if we identify the set of natural numbers with the set
H() of hereditarily finite sets in the
usual way, then for each X
H() we have:
X isThus the notions ofX is
0- and
1-set may be regarded as
generalizations of the notions of recursive and
recursively enumerable set, respectively.
The completeness theorem for
implies that
Val() -- regarded as
a subset of
H() -- is recursively enumerable, and
hence
1 on
H(). Similarly, the completeness theorem for
(1,)
(see §2) implies that
Val((1,)) --
regarded as a subset of
H(1) -- is
1 on
H(1). However, this
pleasant state of affairs collapses completely as soon as
(1,1)
is reached. For one can prove
Scott's Undefinability Theorem forThis theorem is proved in much the same way as the well-known result that the set of (codes of ) valid sentences of the second-order language of arithemetic
2 is not second-order definable
in its coding structure . To get this latter
result, one
first observes that is characterized by a single
2-sentence, and then shows that, if the
result were false, then "truth in
" for
2-sentences
would be definable by an
2-formula,
thereby violating Tarski's theorem on the undefinability of truth.
Accordingly, to prove Scott's undefinability theorem along the above lines, one needs to establish:
(4.1) Characterizability of the coding structure(4.1) is proved by analyzing the set-theoretic definition ofA
(4.2) Undefinability of truth for
(4.3) There is a term t(v0, v1) of
(1) and
showing that it can be "internally" formulated in
(1,1).
(4.2) is established in much the same way as Tarski's theorem on the
undefinability of truth for first- or second-order languages. (4.3)
is obtained by formalizing the definition of the coding map
in
(1,1).
Armed with these facts, we can obtain Scott's undefinability theorem
in the following way. Suppose it were false; then there would be an
(1,1)-formula
(v0) such that,
for all
(1,1)-sentences
,
(4.4)Let
0 be the sentence given in (4.1).
Then we have, for all
(1,1)-sentences
,
so that, by (4.4),
If t is the term given in (4.3), it would follow that
Now write
(v0) for the
(1,1)-formula
(t(0,
)). Then
contradicting (4.2), and completing the proof.
Thus
Val((1,1))
is not definable even by an
(1,1)-formula,
so a fortiori
(1,1)
is incomplete. Similar arguments show that Scott's undefinability
theorem continues to hold when
1 is replaced by any successor
cardinal
+; accordingly the languages
(+,+) are all
incomplete.[6]
(
1,) and the Barwise Compactness Theorem(1,)
is the only one to be reasonably well behaved. On the other hand,
the failure of the compactness theorem to generalize to
(1,)
in any useful fashion is a severe drawback as far as applications
are concerned. Let us attempt to analyze this failure in more detail.
Recall from §4 that we may code the formulas of a first-order language
as hereditarily finite sets, i.e., as members of
H(). In that
case each finite set of (codes of)
-sentences is
also a member of
H(), and it follows that the
compactness theorem for
can be stated in the form:
(5.1) IfNow it is well-known that (5.1) is an immediate consequence of the generalized completeness theorem for
, which, stated in a form similar to that of
(5.1), becomes the assertion:
(5.2) IfIn §2 we remarked that the compactness theorem for
(1,)
fails very strongly; in fact, we constructed a set
Sent(1,) such that
(5.3) Each countable subset ofRecall also that we introduced the notion of deduction in
(1,);
since such
deductions are of countable length it quickly follows from (5.3) that
(5.4) There is a sentence[8]Now the formulas of
(1,
) can be coded as members of
(1), and it
is clear that
(1) is closed
under the formation of countable subsets and sequences. Accordingly
(5.3) and (5.4) may be written:
(5.3 bis) EachIt follows that (5.1) and (5.2) fail when "(5.4 bis) There is a sentence
" is replaced by
"(1,)" and
"()"
by
"(1)".
Moreover, it can be shown that the set
Sent(1,)
in (5.3 bis) and (5.4 bis) may be taken to be
1 on H(1).
Thus the compactness and generalized completeness theorems fail even
for
1-sets
of
(1,
)-sentences.
We see from (5.4 bis) that the reason why the generalized
completeness theorem fails for
1-sets in
(1,)
is that, roughly speaking,
H(1) is not "closed" under
the formation of deductions from
1-sets of sentences in
H(1).
So in order to remedy this it would seem natural to replace
H(1) by sets A
which are, in some sense, closed under the formation of such
deductions, and then to consider just those formulas whose codes are
in A.
We now give a sketch of how this can be done.
First, we identify the symbols and formulas of
(1,)
with their codes in
H(1),
as in §4. For each countable
transitive[9]
set A, let
We say thatA.
A is a
sublanguage of
(1,)
if the following conditions are satisfied:
(i)The notion of deduction in(ii) if
(iii) if
(iv) if
(v) if
(vi) if
A
is defined in the customary way; if
is a set of sentences of
A and
A, then a
deduction of
from
in
A is a deduction of
from
in
(1,
) every formula of
which is in
A. We say that
is deducible from
in
A if there is a deduction
D of
from
in
A; under these conditions
we write
A
. In general, D
will not be a member of A; in order to ensure that such a
deduction can be found in A it will be necessary to impose
further conditions on A.
Let A be a countable transitive set such that
A is a sublanguage of
(1,
) and let
be a set of sentences of
A. We say that A (or,
by abuse of terminology,
A) is
-closed if, for any formula
of
A such that
A
, there is a deduction D of
from
such that
D
A. It can be shown that the only
countable language which is
-closed for
arbitrary
is the first-order language
, i.e., when A =
H().
However J. Barwise discovered that there are countable sets A
H(1)
whose corresponding languages
A differ from
and yet are
-closed for all
1-sets of sentences
. Such sets A are called admissible
sets; roughly speaking, they are extensions of the hereditarily
finite sets in which recursion theory--and hence proof theory--are still
possible.[10]
From Barwise's result one obtains immediately the
Barwise Compactness Theorem. Let A be a countable admissible set and letThe presence of "
1" here indicates
that this theorem is a generalization of the compactness theorem for
recursively enumerable sets of sentences.
Another version of the Barwise compactness theorem, useful for constructing models of set theory, is the following. Let ZFC be the usual set of axioms for Zermelo-Fraenkel set theory, including the axiom of choice. Then we have:
5.5. Theorem. Let A be a countable transitive set such that A = <A,To conclude, we give a simple application of this theorem. Let A = <A,
| A>
be a model of ZFC. A model B
= <B, E> of ZFC is said to be a
proper end-extension of A if (i)
A
B, (ii) A
B, (iii)
a
A, b
B, bEa
bA. Thus a proper
end-extension of a model of ZFC is a proper
extension in which no "new" element comes "before" any "old"
element. As our application of 5.5 we prove
5.6. Theorem. Each countable transitive model of ZFC has a proper end-extension.The reader will quickly see that the first-order compactness theorem will not yield this result.Proof. Let A = <A,
It is easily shown that
- all axioms of ZFC;
- c
x = b), for each a
- a
[Supplement: Definition of the Concept of Admissible Set
(1,),
as well as for other infinitary languages, was proved by Karp
[1964]. The Hanf number calculations for
(1,)
were first performed by Morley [1965]. The nondefinability of
well-orderings in finite-quantifier languages was proved by Karp
[1965] and Lopez-Escobar [1966]. The interpolation theorem for
(1,)
was proved by Lopez-Escobar [1965] and Scott's isomorphism theorem
for
(1,)
by Scott [1965].
§3. Results (3.2) and (3.3) are due to Hanf [1964], with some refinements by Lopez-Escobar [1966] and Dickmann [1975], while (3.4) was proved by Tarski. Result (3.5) is due to Scott [1961], (3.6) to Bell [1970] and [1972]; and (3.7) to Bell [1974]. Measurable cardinals were first considered by Ulam [1930] and Tarski [1939]. The fact that measurable cardinals are weakly compact was noted in Tarski [1962].
§4. The undecidability theorem for
(1,1)
was proved by Scott in 1960; a fully detailed proof first appeared
in Karp [1964]. The approach to the theorem adopted here is based on
the account given in Dickmann [1975].
§5. The original motivation for the results presented in this section came from Kreisel; in his [1965] he pointed out that there were no compelling grounds for choosing infinitary formulas solely on the grounds of "length", and proposed instead that definability or "closure" criteria be employed. Kreisel's suggestion was taken up with great success by Barwise [1967], where his compactness theorem was proved. The notion of admissible set is due to Platek [1966]. Theorem (5.6) is taken from Keisler [1974]. For further reading on the subject of infinitary languages, see Aczel [1973], Dickmann [1975], Karp [1964], Keisler [1974], and Makkai [1977].
(1,
),
(1,
1), and Restricted Second-Order
Languages", Arch. Math. Logik 15: 74-78.
| John L. Bell jbell@julian.uwo.ca |
