THEJ O ~ N A LOF SYMBOLIC LOGIC

Volume 41. Number I , March 1976

PROBABILITIES ON FINITE MODELS

RONALD FAG IN^

$1. Introduction. Let 9’ be a finite set of (nonlogical) predicate symbols. By

an 9’-structure, we mean a relational structure appropriate for 9’.Let dn(9’ be
)
the set of all 9’-structures with universe (1, . . -,n}. For each first-order 9’-sentence
u (with equality), let p,,(u) be the fraction of members of d,(- for which u is true.
We show that p,,(u) always converges to 0 or 1 as n --+ co, and that the rate of
convergence is geometrically fast. In fact, if Tis a certain complete, consistent set of
first-order 9-sentences introduced by H. Gaifman [6], then we show that, for each
first-order 9’-sentence u, pn(u)+, 1 iff T t u. A surprising corollary is that each
finite subset of T has a finite model. Following H. Scholz [8], we define the spectrum
of a sentence u to be the set of cardinalities of finite models of u. Another corollary
is that for each first-order Y-sentence u, either u or - u has a cofinite spectrum (in
fact, either u or N U is “nearly always” true).
Let 2?,,(9) be a subset of dL(9) which contains for each U in dn(.4P )
exactly one
structure isomorphic to 9L. For each first-order Y-sentence u, let v,(u) be the
fraction of members of B,,(9‘) for which u is true. By making use of an asymptotic
estimate [3] of the cardinality of gn(9) and by our previously mentioned results,
we show that v,(u) converges as n -+co, and that limn v,(u) = limn p,(u). If 9’
contains at least one predicate symbol which is not unary, then the rate of con-
vergence is geometrically fast.
The author thanks R. W. Robinson for bringing Oberschelp’s preliminary work
[7] on the cardinality of a,,(- to his attention, and Roland0 Chuaqui for pointing
out to him that Carnap [I] introduced the idea of considering limn v,(u). Carnap
proved, in the special case when 9’contains only unary predicate symbols, that
limn un(u) exists, and is 0 or 1.

$2. T h e probabilities pn. Let 9’ be a finite set of predicate symbols, let dn(9’)
be as before, and let a,(* be the cardinality of dn(9). For example, if 9’= {P},
.
where P is a binary predicate symbol, then a , ( q = 2“’.
Let 1,2,3,- . . be distinct constant symbols, and let 9” = 9’u {1,2,3,. . 0 ) .

For each s( in dn(9), let 9L‘ be the inessential expansion of 9L to 9” in which the
interpretation of i is i, if i I n, and n otherwise.

Received November 2, 1973.

This paper is based on a part of the author’s doctoral dissertation [2] in the Department of
Mathematics at the University of California, Berkeley. Part of this work was carried out while
the author was a National Science Foundation Graduate Fellow; also, part of this work was
supported by NSF grant GP-24532.
a The author is grateful to Robert Vaught, William Craig, and Ralph McKenzie for useful
suggestions which improved readability.
50
Q 1976, Association for Symbolic Logic
 PROBABILITIES ON FINITE MODELS 51

Let p< be the probability measure on dn(9) which weights each structure
equally. Thus, if Y = {P},with P a binary predicate symbol, then
p$((U U’ t P12))
E dn(9): = 1/2 if n 2 2,
pT({U E dn(a
:%’ t= P21 A P23 A P31)) = 1/8 if n 2 3.
If u is a first-order 9”-sentence, then abbreviate pz({U E dn(9‘) : U’ t= u)), the
fraction of members U of dn(9) for which 3’ is a model of u, by pn(a). This is
unambiguous, since if both 9’and .T contain the predicate symbols that appear in
U, then it is not hard to see that

: U’ I=u}) = g ( { U E dn(Y)
p;r”({U E dn(9‘) : 2f’ t= u)).

Note that I.,,(.) is defined for first-order 9’-sentences u, whereas pS(s9) is defined
only for (certain) sets d of 9’-structures.
Let X = {x,, . . -,x,} be a finite set of m distinct individual variables. Then a
+
complete open description M ( x , , . . -,xm)is a conjunction A{+: E A ) , where for
each k-ary P in 9’ and each k-tuple (z,, . . ., zk) of members of X,the set A contains
exactly one of Pz,. . -z, or -Pz1- . ‘z,. Note that the equality symbol = does not
appear in M . We abbreviate <xl,. . -,x,> by x (we also abbreviate the formula
Vx,. . .Vx& by Vx4.) The complete open description N ( x , y ) is said to extend the
complete open description M ( x ) if y is a new variable distinct from all the xi, and
if every conjunct of M ( x ) is a conjunct of N ( x , y).
Let T be the set of all 9’-sentences

where M ( x ) is a complete open description, and where N ( x , y) is a complete open

description extending M ( x ) . A set of sentences equivalent to T was introduced by
H. Gaifman [6].In [ 6 ] ,Gaifman shows the following:
THEOREM 1 (GAIFMAN).T is consistent and complete.
PROOF. One way to show that T is consistent is to create an infinite model of T
in w steps. We will show later (Corollary 5) that surprisingly enough, every finite
subset of T has a finite model. By the compactness theorem of first-order logic,
this is certainly enough to guarantee that T is consistent. We will now sketch
Gaifman’s proof that T is complete. The LoS-Vaught test [9] says that if T has no
finite models, and if every two countable models of T are isomorphic, then T is
complete. Clearly, Thas no finite models. To show that every two countable models
91 and 23 of T are isomorphic, we use Cantor’s “back-and-forth” argument, in
which we extend an isomorphism between finite substructures 3, E 3 and 3,E CD
by adding one more element to one, and then finding a suitable element in the other
by which the isomorphism can be extended. In fact, T is defined in precisely such a
way as to make this “back-and-forth” argument work. J -I
Gaifman introduces T in the context of a certain infinite “probability model”
(which was suggested to him by Rabin and Scott), that seems on the surface to be
intimately related to what we are doing. However, Gaifman never considers finite
structures, and our results d o not seem to follow from his.
If we let p(u) = limnpn(u), which we will show to exist, then p is a probability
52 RONALD FAGIN

measure on sentences, in the sense of Gaifman, and coincides with the probability
measure in Rabin and Scott’s example. For details, see [6].
The next theorem is the key tool in this section.
THEOREM 2. If u E T, then pn(u)+, 1.
PROOF.Assume for convenience that 9’= {P},where P is a binary predicate
symbol. The modification of the proof in the general case is clear. Let u be the
sentence (l), and let +(x) be

M(x) A b(( pf X t ) -+ - NW).

Let $ ( y ) be - ( A l A . . . A A2m+l), where for each i (1 5 iIm),

Piy if Pxty is a conjunct of N ( x , y),
Azi-i =
{-Piy if - P x f y is a conjunct of N ( x , y),
Pyi if Pyxt is a conjunct of N ( x , y ) ,
A2t =
{ -Pyi if -Pyxt is a conjunct of N ( x , y),
Pyy if Pyy is a conjunct of N ( x , y),
A2m+i =
{-Pyy if -Pyy is a conjunct of N ( x , y).
Assume that n > m. Then

~ , ( - U ) = ~ L ~ ( ~ I~# j~ . . . ~ X ~ ( A X , Z ~ , A M (+~- N
)A( XV
, YY
))))

I 2 . . u,,,)): 1 I a, I‘n, and a, # a, if i # j , for

{p,,(+(u~, 0 ,

1 i Im, 1 j I m},where we substitute a; for x,

I I
= 2pn(+(1, . . .,m)) by symmetry
= n(n - 1)- . .(n - m + l)pn(+(l,- . -,m)) 5 nmpn(+(l,- + -,m))

z i ) +w)))
since k(+~,--.,m)-+vy((~v

= nm fi
j=m+l
pn+(i) by independence
= nm(l - (1/22m+1))”-m by an obvious computation
- ,,mkn-m
, where k = (1 - (1/22m+1))< 1
+O as n - t co, by l’Hospital‘s rule.
Since p,,(u) + pn(-u) = 1, we have pn(u) +, 1. 0
COROLLARY 3. rfu is afirst-order 9-sentence, then T k u iZp,,(u) +, 1.
PROOF. =.: Assume that T k u. By the compactness theorem, there is a finite
subset ( u l , - . ., ur} E T such that k((ul A - - - A ur) -t u); and hence k(-u-+
v . v -ur)). Therefore, pn(-u) 5 pn(-ui v - - - V -or) Ip n ( N U 1 ) +
(-01
+ p,( - * *

ur) -+, 0. Since p,(u) + p,( - u) = 1, it follows that pn(u) +, 1.

* * *
 PROBABILITIES ON FINITE MODELS 53

t : Assume that p,(u) + , 1 and T Y U. Since T is complete, T I= NU. But as we

just saw, if T C N U , then p,(-u) +, 1. Therefore pn(u) +, 0, a contradiction. 0
We can now prove the main result of this section, which does not involve (in its
statement) the set T.
THEOREM 4. If u is afirst-order sentence with no function or constant symbols,
then p,,(u) converges to either 0 or 1 .
PROOF. Either T i . u or T I= N U . If T C u, then pn(u)+, 1. If TI=N U , then
pn(-O) +n 1, SO pn(u) +n 0- 0
We now prove two further corollaries of Theorem 2.
COROLLRY 5. If T’ is any finite subset of T, then T’ has afinite model. In fact,
(3N)(Vn > N)(T’ has a model of cardinality n).
PROOF. If T‘ has r sentences, then find N so large that pn(-u) < l / r for each
n > Nand each u in T‘. Then pn(-ul v . . . v mu,) Ipn(-ul) + + .. . p,,(-u,) <
I, and so pn(ul A . . . A u,) > 0. 0
CQROLLARY
spectrum.
-
6. If u is a first-order sentence, then either u or u has a cofinite

PROOF1. For each first-order sentence u, there is a sentence a* which has no

function or constant symbols, but which has the same spectrum as u (the sentence
U* is derived from u by well-known techniques of replacing functions by relations).
Therefore, by replacing u with u*, we can assume that u has only predicate symbols.
So, either pn(u) 3,1 or p , ( - u ) +, 1. If I.,,(.) --+, 1, then in particular
3N(Vn > N)(p,(u) > 0); hence u has a model of cardinality n for each n > N.
-
Similarly, if pn( U) +, 1. 0
PROOF2. Assume that u is a Y-sentence, where Y is a finite set of predicate
symbols, function symbols, and constant symbols. Let C contain the following
sentences:
3x,. .3xk(AI*,xi # x,), for each positive integer k ;
1

Vx(F(x) = XJ for each function symbol F i n 9;

VxRx for each predicate symbol R in F;
cI = c, for each pair of constant symbols cI, c, in 37
Then C is complete by the to;-Vaught test [9]. So, either Z C u or 2 k NU. Say
C C u. By the compactness theorem, there is a finite subset I;‘ of C such that I;’ k. U.
Let N be larger than any k for which some sentence in Z’ is 3x,. - .3xk(Ai+ jxI # x,).
Then X‘has a model of cardinality n for each n > N. Therefore, u has a model of
cardinality n for each n > N. 0
Actually, a stronger statement than Corollary 6 is true (if u contains no function
or constant symbols). Namely, either 3N(Vn > N) (u has “many” nonisomorphic
models of cardinality n), or 3N(Vn > N) ( N U has “many” nonisomorphic models
of cardinality n). We will deal with the trivial case when Y has only unary predicate
symbols later. So assume that 9’contains at least one predicate symbol which is
not unary. Assume that 9 contains k, distinct i-ary predicate symbols. Recall that
u,,(Y) is the cardinality of&,(a; then ~~(9‘) = 2zkl”‘.Assume that u is a sentence
such that p,(u) -+, 1. Then given any 0 with 0 I0 .c 1, we can find N such that
4(Y) contains at least 0(2zk{n’) models of u for each n > N. How many isomorphism
types does this represent? Any member of dn(Y) can be isomorphic to at most n !
distinct members of d,(Y), since there are only n! bijections of (1, - - -,n} onto
54 RONALD FAGIN

So given 0, with
itself. By Stirling’s formula, n! is asymptotic to (27~z)~‘”(n/e)”.
0 5 0 < 1, there is N such that, for each n > N, the number of different non-
isomorphic models of u of cardinality n is at least e(22k~n‘)/((2rrn)1’z(n/e~). The
denominator is dwarfed by 2“‘, if i 2 2, because ncn llz) = 2c10g2n)cn
+ 1/2). And, some
+

such term 2”‘ appears in the numerator. In the next section, we will show that in
fact, either u or - u is “nearly always” true when we consider isomorphism types.

$3. The probabilities v,. As before, let 9?,,(9‘)_C d,(q contain exactly one
representative of each ismorphism type of n-element 9-structures. Let b,(- be
the cardinality of 29,,(9‘).
Let <be the probability measure on B,,(Y)which weights each structure equally.
If u is a first-order 9’-sentence, then abbreviate <({a E ~%’,,(9‘) :91 I=Q}) by vF(u).

Here it is not necessarily true that if both 9’and 3- contain the predicate symbols
of u, then .$(’‘a) = <(U); it is easy to find counterexamples even for n = 2. How-
ever, we will often write v, for q.
We will show in this section that v,(u) converges as n -+ 03, and that limn v,(u) =
limn p,(u). The proof is divided into two cases: first, if 9’ is monadic (that is, if Y
contains only unary predicate symbols); and second, if Y is not monadic. Carnap
[l, p. 5671 showed that if 9’ is monadic, then limn vn(u) exists, and is 0 or 1. For the
monadic case, we will make use of the following simple lemma, which is proved
in Feller [4].
LEMMA7. The number of s-tuples (xl, . . ., x,) of integers x, such that xl + - -
+ x, = c and 0 I x, I c for each i is the binomial coeficient Cc+s-l.s-l.
P R O O F . [4, p. 361.
Our main tool in the interesting case, in which 9’is not monadic, is the follow-
ing result. Recall that a , ( q is the cardinality of dn(9‘) , in graph-theoretic
i.e.,
terms, a,,(* is the number of “labeled” 9’-structures with universe of cardinality
n; and b,(9‘) is the cardinality of an(*,i.e., b , ( q is the number of “unlabeled”
9’-structures with universe of cardinality n.
THEOREM 8 [3]. Assume that 9’ is not monadic. Then b , ( q is asymptotic to
an(9‘)/n!,that is,
(2) bn(9‘)n!/an(Y)--f I as n -+ 03.

F. Harary [5] stated (2) without proof for the case when 9’ contains only one
symbol, a binary predicate symbol. W. Oberschelp [7] proved (2) for the case when
Y is a set of r-ary predicate symbols for fixed r 1 2. Theorem 8 is a best-possible
result, since it is not hard to check that (2) fails if 9’ is monadic. Theorem 8 was
recently proven, independently, by A. Ehrenfeucht (unpublished) and the author [3].
THEOREM 9. Ifu is afirst-order sentence with no function or constant symbols,
then v,(u) converges as n +- 00, and lim, v,(u) = limn pn(u).
PROOF. Case 1. 9’ is monadic.
-
Assume that Y = {Pl, . -,P,,,), where each P,is unary. It is well known that Q is
equivalent to a first-order sentence Vt AfTff,where each q jis one of two types of
sentences:
(A) “There are exactly k points x such that AF=l+t(x),7’ where each +:(x) is
either Ptx or -Ptx.
 PROBABILITIES ON FINITE MODELS 55

(B) The negation of a sentence of type (A).

How many members of g,(q are models of the given sentence of type (A)?
For each 91 in 9?,,(9), the universe (1, . . -,n} of 91 is partitioned into 2" sets, where
i is in a given set depending on whether P B or -PFi for each Pt in 9'; in fact, the
partitioning uniquely characterizes an .%structure up to isomorphism. Assume
that n > k. From Lemma 7 with c = n - k and s = 2" - 1, the number of
members of 9?,,(.4p) which are models of the given sentence of type (A) is
C, - k + 2m -2,2m - 2, a polynomial in n of degree 2" - 2. The number of structures in
9?,,(9') altogether is C n + 2 m - l . 2 m - l , a polynomial in n of degree 2" - 1, again by
Lemma 7.
Therefore, if T ~ is , a formula of type (A), then Y,,(T~,)-+,,O. Hence, if T~~ is a
formula of type (B), then V,(T~,) -+ Therefore,
1. ,

vn (A ~ < j -+n
j
) (" 1 if
T ~ is
, of type (A) for somej,
if T ~ is, of type (B) for eachj.
And,
(y
vn /) TI,) +n (9if vn ~ i j +n
) 0 for each i,
1 otherwise.
Therefore, vn(V,A,T,,)converges to 0 or 1, and it converges to 1 iff there is
some i such that, for each j , the sentence T{, is of type (B). But in this case,
T C V, A,Trj,where T is the set of sentences of $2. Then pn(VlAjrlj)-+n 1.
So, we have seen that if 9 is monadic and u is a first-order 9-sentence, then
either v,(u) -+, 0 or v,,(u) +, 1, and that v,(u) -+, 1 implies that pn(u)-tn1. If
v,(u) 3, 0, then v,,(-u) --+, 1, .so p,(-u) +, 1, and so p,,(u) -+, 0.
Case 2. 9 is not monadic.
Assume that p,(u) -+, 1 ; we will show that v,(u) -+, 1. Let x be the number of
members of dn(9') which are models of (I,and let y be the number of members
of gn(9') which are models of u. Then y 2 x/(n!),as in the argument at the end of
the previous section. But y = vn(u)bn(9'), and x = pn(u)an(.Y). Hence v,(u)b,,(9') 2
pn(u)an(fl/n 1 7 and SO
(3) Vn(0) 2 pn(ol/(hdSP)n !/an(?))-
But the numerator of the right-hand side of (3) converges to 1 by assumption, and
the denominator converges to 1 by Theorem 8. Hence vn(u) +, 1, as desired. So if
pn(u) 3,1, then vn(u) +, 1. If p,(u) -+, 0, then pn(- u) -+ 1,,so by the above
vn(-u) 4, 1, and hence v,(u) 3, 0. 0
§4. Additional remarks and counterexamples.
1. If u is a second-order 9'-sentence, then p$'(u) and <(u) need not converge.
Let 9' = 0 , let P be a binary predicate symbol, and let u be
3p(vXg!y(X # y A PXy A pyx)),
where 3 ! y is read "there is exactly one y." Then

= vn(u) =
1, n even.
2. What happens if we allow 9 to contain function and constant symbols? We
to be the set of all 9'-structures with universe (1, - ., n}.
can still define dn(9') -
 .
56 RONALD FAGlN

Then a constant symbol c can denote any one of n possible values, a 1-place func-
tion symbol F can denote any of n" possible values, and so on. And, we can still
define pn to be the probability measure on dn(9') which weights each structure
equally. But if u is a first-order 9'-sentence, then p,,(u) need no longer converge to 0
or 1. For, if U is a unary predicate symbol, and if c is a constant symbol, then
p,(CIc) = +, and so p,(Uc) +, +. A more interesting example is given by the
sentence u = Vx(F(x) # x). Then
p,(u) = (n - l)"/nn= (I - l/n)" 3, I/e.
It is an open question as to whether, in this extended case, pn(u) and vn(u)
necessarily converge, and what the possible limits are.
3. We will now consider the rate of convergence of p,(u) and of v,(u). If
(x,: n E Z +> is a sequence, and if x, +, x, then we say that the convergence is
geometrically fast if there is some 8, with 0 I 8 < 1, and some constant N, such
that Ix - xni < 8" for each n > N.
Assume that 9 ' contains only predicate symbols. We will show that pW(u)
converges geometrically fast for each first-order 9'-sentence u. We will also show
that if 9'is not monadic, then vf(u) converges geometrically fast for each first-
order 9'-sentence u. In part 4 of this section, we will give a counterexample to show
that this fails if 9'is monadic.
THEOREM 10. If 9 'contains no function or constant symbols, arid i f u is afirst-
order 9'-sentence, then p$'(u) converges geometrically fast. I f 9 is not monadic, then
v$'(u) converges geometrically f i t .
PROOF. The proof of Theorem 1 shows that if u E T, then there is some k , with
0 5 k < 1, and there is some positive integer m, such that p,(-u) < nmkn-",for
sufficiently large n. Find E > 0 small enough that if 8 = (1 + e)k, then P < 1.
By l'Hospital's rule, n-"k"(l + E)" --f co as n -+ co. Hence, (1 + e)" > nmk-"' for
sufficiently large n. Then nmkn-" < (1 +
e)"k" = 8". So if u E T, then pn(-u) +, 0
geometrically fast.
Now assume that 7 is a first-order 9'-sentence such that T P T. By the compact-

-
ness theorem, there is a finite subset {ul,. . -,u,} 5 T such that P((ul A . . . A ur) -+
T), and hence k( 7 -+ (- 01 V . . v- - - -
or)). SO pn( 7) 2 pn( 0,) + -
. . . + pn( u,).
It is easy to see that since y,(-u,) +,O geometrically fast for each i, so does
pn(-ul) + + - . p,(- ur), and hence so does p,(- 7).
Now let u be any first-order 9'-sentence. Either T P u or T C NU. If T t= -u then,
by what we just showed, p,(u) converges to 0 geometrically fast. If T k U, then
11 - p,,(u)1 = pn(-u)), which converges geometrically fast.
We will now show that <(u) converges geometrically fast if 9 'is not monadic.
-
It is sufficient to assume that pn(u)+-,I ;if not, then we consider u. It is shown
in (31 that a,(9')/(bn(9')n!) converges to 1 geometrically fast. Since p,,(u) converges
to 1 geometrically fast, it follows fairly easily from (3) that vn(u) converges to 1
geometrically fast. 0
4. Assume that 9 = {V}, where U is a unary predicate symbol. Then b,(Y) =
n + 1, since 91 in d,(Y)is characterized up to isomorphism by the cardinality of
the interpretation of U in 9(.
+
Let u be VxUx. Then v,,(u) = l / ( n 1). So v,(u)+,O, but not geometrically
 PROBABILITIES ON FINITE MODELS 57

fast. This contrasts interestingly with the case 9’ = {P},P a binary predicate
symbol, in which ~ ( V X P X X-+,) 0 geometrically fast.
In general, if 9is monadic and u is a fkst-order 9-sentence, then we can show,
as in the proof of Case 1 of Theorem 9, that there are polynomials p and q such
that vf(u) = p(n)/q(n).
5. If u and 7 are sentences, and if pn(7) > 0 for each n, then does the conditional
probability pn(u 1 7 ) = pn(u A 7)/pn(7) converge? Let u1 be Vx3!y(x # y A
Pxy A Pyx), as in part 1 of this section, and let u2 be 3w(Vx # w)(3!y # w )
( x # y A Pxy A Pyx). Then the spectrum of u1 (u,) is the set of even (odd) positive
integers. Let cr = uI, and let T = u1 v u2. Then

So pn(u I 7 ) and Y,(U I 7 ) do not converge.

6. For certain sentences 7, it is true that pn(u I 7 ) converges for every first-order
sentence u. We will give three examples:
TI
72
= VX - P X X A v X v Y ( P X y ti PYX),
= vXvy(X # y --f (PXy f-) -PYX)) A YX - PXX,
73 = v X v J ’ ( u X 4 4 UJ’).
Let 9’= {PI,P a binary predicate symbol, and let T~ be as above. Let Q be a
graph predicate symbol, that is, a symbol whose interpretation in a structure i s a set
of unordered pairs. For each {P}-sentence u, let u‘ be the result of replacing every
occurrence of P in u by Q. Then &’)(uI r1) = p$‘)(u‘). Modify the set of sentences
T of $2 to be a new set T’, by a redefinition of a complete open description to be
consistent with Q being a graph predicate symbol. Then T‘ is consistent and
complete, and the old proof goes through to show that piop)(u’)converges to 0 or 1,
depending on whether T’ C u’ or T’ C NU’.
The case when T~ is as above is similar to the previous case. Then we are effec-
tively dealing with what graph-theorists might call a “tournament” predicate
symbol, and again, pn(u I T ~ converges
) to 0 or 1.
Let Y = {U}, U a unary predicate symbol, and let 73 be as above. Let &(u) =
pn(u I T ~ ) .Then p:(VxUx) = f, since if U k 73, then either 3
Vx - ‘ C VxUx or U t
Ux. And, for any first-order 9’-sentence u, the sequence <PA(.): n E Z is
eventually 0, f, or 1. For, u A V x U x is equivalent to some sentence ul A V x U x ,
+>
where ul involves only equality. So, for some N,, we know that either u A VxUx
has no models of cardinality n for each n > Nl, or it has a model of cardinality n
for each n > Nl. -
Similarly, find Na such that u A Vx Ux has either no models of
cardinality n for each n > N,, or a model of cardinality n for each n > Nz. Let
N = max(Nl, N2). Then, for each n > N,
d(u)= 0, if u A VxUx and u A Vx Ux each have no models of cardinality n;
&(u) = +,
N

-
if u A V x U x has a model of cardinality n but u A Vx Ux has no
model of cardinality n, or if u A Vx Ux has a model of cardinality n
-
but u f\ VxUx has no model of cardinality n;
A(.) = 1 otherwise.
So pn(u1 T ~ is) eventually 0, 3, or 1.
 .
58 RONALD FAGIN

SOME OPEN PROBLEMS. Characterize those sentences 7 such that pn(u I T )

converges for each u. Is there always convergence if T is universal? What are the
possible limits?
7. We will now briefly consider more general probability measures than pn and
and v,. Let Y = {P},P a binary predicate symbol, and let 9" = 9 'U {1,2,3, * - a}

as before. Let p and a be given, with 0 < p < 1 and 0 Ia < 1. We will define a
new probability measure p 5 a on Sa,(9) in which all structures need not be given
the same weight, which has the property that p F a ( u ) converges for each first-order
9'-sentence u and p;EP."(VxVyPxy)converges to a nonzero value.
Let f be a function from the reals to the reals defined by f ( x ) = (1 - a)pX a +
for each x . Given 91 = ({I, . . ., n}; Q ) in s9,(9'), where Q is the interpretation of
P in 91, assume that Q U ( - QU) holds for r (s) different pairs ( i , j ) with 1 i i I11,
1 Ij In ; thus r + s = n2. Then let the weight of 91 be f(n2), if s = 0, and
+
(1 -f(l))pr(l - p)S-l, if s > 0. So, if p = and a = 0, then pFa= p$'. The
measure pF" is such that if u is a conjunction of r distinct sentences Pij and s
distinct sentences -Pij, with no argument (i, j > appearing twice, then we can show
that
if s = 0,
(I -f(l))pr(l - py-' if s > 0.
We state without proof that it is possible to show that p.f."(u) converges for each
first-order 9'-sentence U, and that it converges to one of the four values a, 1 - a,
0, o r 1. And, &""(VxVyPxy) 9, a. We also remark that Y can be generalized to
be any finite set of predicate symbols.

BIBLIOGRAPHY

[I] R. CARNAP, Logical foundations ofprobabilify, University of Chicago Press, Chicago,

1950.
[2] R. FAGIN.Contributions to the model theory of finite structures, Doctoral dissertation,
University of California, Berkeley, 1973.
131 - ,The number offinite relational structures, IBM research report RC5587 (August
1975). Yorktown Heights, N.Y.. 10598.
[4] W. FELLER, An introduction foprobabifityf k o r y and its applications. I, 2nd edition, Wiley
and Sons, New York, 1957.
[5] F. HARARY. Note on Carnap's relational asymptotic relative frequencies, this JOURNAL,
V O ~ .23 (1958), pp. 257-260.
[6] H. GNFMAN, Concerning measures in firsi-order calculi, Israel Journal of Mathematics,
V O ~ .2 (1964). pp. 1-17.
[7] W. OBERSCHELP, Strukturzahlen in endlichen Relationssystemen, Contributions to M a t k -
matical Logic (Proceedings of Logic Colloquium), Hannover, 1966, pp. 199-213.
[8] H.SCHOLZ, this JOURNAL,vol. 17 (1952). p. 160.
[9] R L. VAUGHT,Applications to the Lowenheim-Skolem-Tarski theorem to problems of
completeness and decidability. Indagationes Mathematicar. vol. 16 (1 954), pp. 467-472.
IBM RESEARCH LABORATORY
SAN JOSE, CALIFORNIA 95193