This is a file in the archives of the Stanford Encyclopedia of Philosophy. 
version 
Stanford Encyclopedia of Philosophy

last substantive content change

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 wellbehaved. In §3 we discuss the compactness problem for infinitary languages and its connection with purely settheoretical questions concerning "large" cardinal numbers. In §4 an argument is sketched which shows that most "infinite quantifier" languages have a secondorder 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.
Let  the (finitary) base language  be an arbitrary but fixed firstorder language with any number of extralogical symbols. The infinitary language (, ) has the following basic symbols:
_{}^{}or, if I is the set of natural numbers, we write for:
_{0} _{1} ...
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
=_{df} { : }and employ similar conventions as for , .X =_{df} X,
Thus (,) is the infinitary language obtained from by permitting conjunctions and disjunctions of length < and quantifications^{[1]} of length < . Languages (,) are called finitequantifier languages, the rest infinitequantifier 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
x_{0} < x_{1} x_{1} < x_{2} ... x_{n} < x_{n+1} ...,where contains the binary relation symbol <. For this reason we make the following
Definition. A formula of (,) is a preformula which contains < free variables. The set of all formulas of (,) will be denoted by Form((,)) or simply Form(,) and the set of all sentences by Sent((,)) or simply Sent(,).In 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 firstorder 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:
is satisfied in A (by a given sequence) for all , is satisfied in A (by the sequence);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 of (,) 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 .X is satisfied in A there is a sequence of elements from the domain of A in bijective correspondence with X which satisfies in A.
We now give some examples intended to display the expressive power of the infinitary languages (,) with _{1}. In each case it is wellknown that the notion in question cannot be expressed in any firstorder 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 firstorder 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 s^{n}x are defined recursively by s^{0}x = x; s^{n+1}x = s(s^{n}x).
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
_{}v_{0} ... v_{n}x(x = v_{0} ... x = v_{n}).
Truth definition in (_{1},) for a countable base language . Let be a countable firstorder 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) =_{df} _{} (x = n _{n})is a truth predicate for inasmuch as the sentence
Tr(n) _{n}is valid for each n.
Characterization of wellorderings 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 wellordering coincides with the class of models of the (_{1},_{1}) sentence = _{1} _{2}, where
_{2} =_{df} (v_{n})_{n} x [_{} (x = v_{n}) _{} (x v_{n})].Notice that the sentence _{2} contains an infinite quantifier: it expresses the essentially secondorder 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 wellordered structures cannot be characterized in any finitequantifier language. This example indicates that infinitequantifier languages such as (_{1},_{1}) behave rather like secondorder languages; we shall see that they share the latters' defects (incompleteness) as well as some of their advantages (strong expressive power).
Many extensions of firstorder languages can be translated into infinitary languages. For example, consider the generalized quantifier language (Q_{0}) obtained from by adding a new quantifier symbol Q_{0} and interpreting Q_{0}x(x) as there exist infinitely many x such that (x). It is easily seen that the sentence Q_{0}x(x) has the same models as the (_{1},)sentence
_{}v_{0}...v_{n}x[(x) (x = v_{0} ... x = v_{n})].Thus (Q_{0}) is, in a natural sense, translatable into (_{1},). Another language translatable into (_{1},) in this sense is the weak secondorder language obtained by adding a countable set of monadic predicate variables to which are then interpreted as ranging over all finite sets of individuals.
The language (_{1},) occupies a special place among infinitary languages becauselike firstorder languagesit admits an effective deductive apparatus. In fact, let us add to the usual firstorder axioms and rules of inference the new axiom scheme
for any countable set Form(_{1},) and any , together with the new rule of inference
_{0}, _{1}, ..., _{n}, ...and allow deductions to be of countable length. Writing ^{*} for deducibility in this sense, we then have the
_{}_{n}
(_{1},)Completeness Theorem. For any Sent(_{1},), ^{*}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 firstorder logic, or by employing Booleanalgebraic methods. Similar arguments, applied to suitable further augmentations of the axioms and rules of inference, yield analogous completeness theorems for many other finitequantifier 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 firstorder 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 firstorder 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 firstorder language without extralogical symbols and let be the (_{1},)sentence which characterizes the class of finite sets. Suppose that were equivalent to a conjunction
_{iI} _{i}of prenex (_{1},)sentences _{i}. Then each _{i} is of the form
Q_{1}x_{1} ... Q_{n}x_{n} _{i}(x_{1},..., x_{n}),where each Q_{k} is or and _{i} is a (possibly infinitary) conjunction or disjunction of formulas of the form x_{k} = x_{l} or x_{k} x_{l}. 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 firstorder formula. Accordingly each _{i} may be taken to be a firstorder 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 firstorder sentences now implies that , and hence also , has an infinite model, contradicting the definition of .
Turning to the LöwenheimSkolem 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 firstorder 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öwenheimSkolem 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 Lsentence has a model of cardinality , it has models of arbitrarily large cardinality. The existence of h(L) is readily established. For each Lsentence 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
(0) = _{0}Then it can be shown that(+1) = 2^{()}
() = _{}() for limit .
h((_{1},)) = (_{1}),similar results holding for other finitequantifier languages. The values of the Hanf numbers of infinitequantifier 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: If , Sent(_{1},) are such that , then there is Sent(_{1},) such that and , and each extralogical symbol occurring in occurs in both and .The proof is a reasonably straightforward extension of the firstorder 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 countable structure with only countably many relations, then there is an (_{1},)sentence whose class of countable models coincides with the class of structures isomorphic with A.The 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 Lsentences (resp. a set of Lsentences 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 Pconsistent^{[3]} set of Lsentences (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) < ^{+} < , (where ^{+} denotes the cardinal successor of ), andIf in addition(b) I < and _{i} < (for all i I) _{} _{i} < .
(c) < 2^{} < ,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 cardinalsif they existmust 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) _{0 } is compact. This is, of course, just a succinct way of expressing the compactness theorem for firstorder languages.Let Constr stand for Gödel's axiom of constructibility; recall that Constr is consistent with the usual axioms of set theory.(3.2) is weakly compact (,) is weakly compact is weakly inaccessible. Accordingly, it is consistent (with the usual axioms of set theory) to assume that no language (,) with _{1} is weakly compact, or, a fortiori, weakly complete.
(3.3) Suppose is inaccessible. Then is weakly compact (,) is weakly compact. Also, Also is weakly compact there is a set of inaccessibles before . Thus a weakly compact inaccessible cardinal is exceedingly large; in particular it cannot be the first, second, ..., n^{th}, ... inaccessible.
(3.4) is compact is inaccessible. (But, by the result immediately above, the converse fails.)
(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 (,) with _{1}.(3.6) Assume Constr and let be inaccessible. Then is weakly compact (_{1},) is weakly compact for all .
(3.7) If Constr holds, then there are no cardinals for which (_{1},) is compact. Accordingly, it is consistent with the usual axioms of set theory to suppose that there is no cardinal such that all languages (_{1},) are complete. This result is to be contrasted with the fact that all firstorder languages are complete.
Some historical remarks are in order here. In the 1930s mathematicians investigated various versions of the socalled 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 twovalued nontrivial) measure on X is a map on the power set PX to the set {0, 1} satisfying:
(a) (X) = 1,Obviously, whether a given set supports such a measure depends only on its cardinality, so it is natural to define a cardinal 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.(b) ({x}) = () = 0 for all x X, and
(c) if A is any countable family of subsets of X, then (A) = {(Y): Y A}.
Let us first introduce the formal notion of definability as follows. If L is a language, A an Lstructure, and X a subset of the domain A of A, we say that X is definable in A by a formula (x, y_{1}, . . . , y_{n}) of L if there is a sequence a_{1}, . . . , a_{n} of elements of A such that X is the subset of all elements x A for which (x, a_{1}, . . . , a_{n}) holds in A.
Now write Val(L) for the set of all the valid Lsentences, i.e., those that hold in every Lstructure. 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 oneone mapthe coding mapof the set of formulas of L into the domain of C(L).
For example, when L is the firstorder language of arithmetic, Gödel originally used as coding structure the standard model of arithmetic and as coding map the wellknown 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 firstorder 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 firstorder 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 settheoretical objects, so let us try to obtain our coding structure by thinking about what kind of settheoretical 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,
() =_{df} <H(),  H()>.
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 Form(,) we assign the code object recursively as follows:
Symbol Code Object Notation 1 2 3 4 5 = 6 = v_{} <0,> v_{}
v_{} = v_{} =_{df} <v_{}, =, v_{}>,for , Form(,),v_{} v_{} =_{df} <v_{}, , v_{}>;
=_{df} <, , >and finally if Form(,) with   < ,=_{df} <, >
X =_{df} <, {x: x X}, >;
=_{df} <, {: }>.
The map from Form(,) into H() is easily seen to be oneone 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 is _{0} on H() X is recursiveThus the notions of _{0} and _{1}set may be regarded as generalizations of the notions of recursive and recursively enumerable set, respectively.X is _{1} on H() X is recursively enumerable.
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 for (_{1},_{1}). Val((_{1},_{1})) is not definable in (_{1}) even by an (_{1},_{1})formula; hence a fortiori Val((_{1},_{1})) is not _{1} on H(_{1}).This theorem is proved in much the same way as the wellknown result that the set of (codes of ) valid sentences of the secondorder language of arithemetic ^{2} is not secondorder 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 (_{1}) in (_{1},_{1}): there is an (_{1},_{1})sentence _{0} such that, for all structures A,(4.1) is proved by analyzing the settheoretic definition 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 secondorder languages. (4.3) is obtained by formalizing the definition of the coding map in (_{1},_{1}).A _{0} A (_{1}).(4.2) Undefinability of truth for (_{1},_{1})sentences in the coding structure: there is no (_{1},_{1})formula (v_{0}) such that, for all (_{1}, _{1})sentences ,
(_{1}) ().(4.3) There is a term t(v_{0}, v_{1}) of (_{1},_{1}) such that, for each pair of sentences , of (_{1},_{1}),
(_{1}) t(,) = .
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 (v_{0}) such that, for all (_{1},_{1})sentences ,
(4.4) (_{1}) () Val((_{1},_{1})).Let _{0} be the sentence given in (4.1). Then we have, for all (_{1},_{1})sentences ,
(_{1}) _{0} Val((_{1},_{1})),so that, by (4.4),
(_{1}) (_{1}) (_{0} ).If t is the term given in (4.3), it would follow that
(_{1}) (t(_{0}, )).Now write (v_{0}) for the (_{1},_{1})formula (t(_{0}, )). Then
(_{1}) (),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]}
Recall from §4 that we may code the formulas of a firstorder 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) If Sent() is such that each subset _{0} , _{0} H() has a model, so does .Now it is wellknown 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) If Sent() and Sent() satisfy , then there is a deduction D of from such that D H().^{[7]}In §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 of has a model but does not.Recall 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]} Sent(_{1},) such that , but there is no deduction of in (_{1},) from .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) Each _{0} such that _{0} (_{1}) has a model, but does not;It follows that (5.1) and (5.2) fail when "" 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.(5.4 bis) There is a sentence Sent(_{1},) such that , but there is no deduction D H(_{1}) of from .
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
_{A} = Form((_{1},)) A.We say that _{A} is a sublanguage of (_{1},) if the following conditions are satisfied:
(i) _{A}The notion of deduction in _{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.(ii) if , _{A}, then _{A} and _{A}
(iii) if _{A} and x A, then x _{A}
(iv) if (x) _{A} and y A, then (y) _{A}
(v) if _{A}, every subformula of is in _{A}
(vi) if _{A} and A, then _{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 firstorder 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 theoryand hence proof theoryare still possible.^{[10]}
From Barwise's result one obtains immediately the
Barwise Compactness Theorem. Let A be a countable admissible set and let be a set of sentences of _{A} which is _{1} on A. If each such that A has a model, then so does .The 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 ZermeloFraenkel set theory, including the axiom of choice. Then we have:
5.5. Theorem. Let A be a countable transitive set such that A = <A,  A> is a model of ZFC. If is a set of sentences of _{A} which is definable in A by a formula of the language of set theory and if each such that A has a model, so does .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 endextension of A if (i) A B, (ii) A B, (iii) a A, b B, bEa bA. Thus a proper endextension 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 endextension.The reader will quickly see that the firstorder compactness theorem will not yield this result.Proof. Let A = <A,  A> be a transitive model of ZFC and let be the firstorder language of set theory augmented by a name a for each a A, and an additional constant c. Let be the set of _{A}sentences comprising:
It is easily shown that is a subset of A which is definable in A by a formula of the language of set theory. Also, each subset such that A has a model. For the set C of all a A for which a occurs in belongs to A  since does  and so, if we interpret c as any member of the (necessarily nonempty) set A  C, then A is a model of . Accordingly, (5.5) implies that has a model <B, E>. If we interpret each constant a as the element a A, then <B, E> is a proper endextension of A. The proof is complete.
 all axioms of ZFC;
 c a, for each a A;
 x(x a _{}x = b), for each a A;
 a b, for each a b A.
[Supplement: Definition of the Concept of Admissible Set
§3. Results (3.2) and (3.3) are due to Hanf [1964], with some refinements by LopezEscobar [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].
John L. Bell jbell@julian.uwo.ca 