Abstract of Ph.D. thesis, University of California, Berkeley, June 1973
CONTRIBUTIONS TO THE MODEL THEORY OF F I N I T E STRUCTURES
Abstract
Ronald Fagin
This t h e s i s i s concerned w i t h t h r e e t o p i c s i n v o l v i n g t h e model t h e o r y of f i n i t e s t r u c t u r e s .
First,
we study t h e p r o b a b i l i t y t h a t a f i r s t - o r d e r sentence
is true i n f i n i t e structures.
Second, w e i n v e s t i g a t e
s p e c t r a and g e n e r a l i z e d s p e c t r a , i n c l u d i n g q u e s t i o n s
i n v o l v i n g t h e d e g r e e of t h e e x t r a p r e d i c a t e symbols.
T h i r d , w e a n a l y z e and e x p l o i t t h e i n t e r r e l a t i o n s h i p
between g e n e r a l i z e d s p e c t r a and automata, t o o b t a i n
r e s u l t s i n both fields.
W e b e g i n w i t h o u r r e s u l t s i n p r o b a b i l i t y theory..
Let
b be a f i n i t e s e t of ( n o n l o g i c a l ) p r e d i c a t e symbols.
By an $ - s t r u c t u r e ,
a p p r o p r i a t e f o r $.
w e mean a r e l a t i o n a l s t r u c t u r e
Let
4n (d)
s t r u c t u r e s w i t h u n i v e r s e (1,
b e t h e s e t of a l l
..., n}.
ld-
For each f i r s t -
o r d e r Id-sentence o , l e t p n ( o ) b e t h e f r a c t i o n of members
of
d n ( d ) f o r which
o is true.
W e show t h a t p n ( o )
always converges t o 0 or 1, as n+m.
s u b s e t of
an($) which
c o n t a i n s f o r each
e x a c t l y one s t r u c t u r e isomorphic t o
first-order
of members of
Let
a.
Bn(d,
fl
in
be a
dn(J)
For each
- s e n t e n c e o , l e t vn ( a ) be t h e f r a c t i o n
Bn(d) f o r
which o i s t r u e .
t h a t i f a l l p r e d i c a t e symbols i n
d
W e show
are of t h e same
d e g r e e , t h e n v ( a ) converges, and l i m p,(o)
n
= l i m vn(o).
2
N o w w e t u r n t o t h e second t o p i c .
L e t 0 be a
f i r s t - o r d e r s e n t e n c e , and l e t P1,
..., Pm be
( n o n l o g i c a l ) p r e d i c a t e symbols i n
0
which a r e n o t i n
( t h e s e a r e t h e e x t r a p r e d i c a t e symbols.)
Let
( o r g e n e r a l i z e d s p e c t r u m ) of
the c l a s s of f i n i t e J - s t r u c t u r e s i n which
(J'
.. . 3Pma.
s e n t e n c e 3P1
be t h e e x i s t e n t i a l second-order
The $-spectrum
-
those
0'
0'
When $=: 0 , w e can i d e n t i f y t h e J - s p e c t r u m of
is
is true.
(J'
w i t h the s e t of c a r d i n a l i t i e s of f i n i t e s t r u c t u r e s
i n which
of
0,
is true.
0
T h i s s e t , c a l l e d t h e spectrum
was f i r s t c o n s i d e r e d by H. Scholz ( J . of Sym-
b o l i c Logic 1 7 , 1 6 0 ) .
It. i s n a t u r a l t o ask whether t h e following t w o
s t a t e m e n t s are t r u e :
(S)
The complement of e v e r y spectrum i s a spectrum.
(GS) The complement of e v e r y g e n e r a l i z e d spectrum
i s a g e n e r a l i z e d spectrum.
T h e q u e s t i o n of t h e t r u t h of
G.
(S)
A s s e r i n 1955 ( Z e i t . f u r math.
d. Math. 1, 2 5 2 - 2 6 3 ) .
w a s f i r s t r a i s e d by
Logik und Grundlagen
The second s t a t e m e n t i m p l i e s
t h e f i r s t , and t h e t r u t h of n e i t h e r i s known.
A
l a r g e p o r t i o n o f t h i s t h e s i s i s concerned w i t h prob-
l e m s r e l a t e d t o these t w o s t a t e m e n t s .
Define
3k($)
t o b e t h e c l a s s of t h o s e J - s p e c t r a
where 2.11 t h e e x t r a p r e d i c a t e symbols a r e k - a r y ,
c a l l eL'ery $-spectrum
in
3,(&
monadic.
and
W e introduce
3
a F r a i s s g - t y p e game t o show t h a t t h e class of monadic
g e n e r a l i z e d s p e c t r a i s n o t c l o s e d under complement.
We show t h a t f o r each spectrum A t h e r e i s a
p o s i t i v e i n t e g e r k such t h a t ink:
n€A} i s a spectrum
W e use
i n v o l v i n g o n l y one b i n a r y p r e d i c a t e symbol.
t h i s as a t o o l f o r showing t h a t i f t h e r e i s a c o u n t e r -
example t o v a r i o u s con je c t u r e s a b o u t s p e c t r a , t h e n
t h e r e i s a spectrum i n v o l v i n g o n l y one b i n a r y p r e d i c a t e
symbol which i s a counterexample.
We show t h a t t h e r e i s an e x a c t t r a d e - o f f
between
t h e d e g r e e of t h e e x t r a p r e d i c a t e symbols and t h e
c a r d i n a l i t y of an " e x t r a u n i v e r s e . "
I n t h e case of
s p e c t r a , w e f i n d t h a t i f A i s a s e t of p o s i t i v e
i n t e g e r s , and i f k12, t h e n A is i n
{nfnl'kl:
nEA} i s i n
3P ($1
iff
w h e r e cx] i s t h e g r e a t e s t
i n t e g e r n o t exceeding x.
show t h a t i f p2.2 and
yk+l(@)
3P ($1
W e use t h e trade-off
=
3P + l (A),t h e n
to
Jk(J)
=
f o r each k2p.
Another r e s u l t is a "two-cardinal"
characterization
of s p e c t r a whose complements a r e s p e c t r a .
Ncw w e t u r n t o t h e i n t e r r e l a t i o n s h i p between
g e n e r a l i z e d s p e c t r a and automata.
Consider t h e follow-
i n g t w o statements of automata t h e o r y :
(S1)
The class of sets r e c o g n i z a b l e by a nond e t e r m i n i s t i c Turing machine i n e x p o n e n t i a l
t i m e i s c l o s e d under complement.
4
The c l a s s of sets r e c o g n i z a b l e by a non-
(CIS1)
d e t e r m i n i s t i c T u r i n g machine i n polynomial
t i m e i s c l o s e d under complement.
W e show t h a t
( G S ) and (GS1)
a r e equivalent.
This
supplerr.ents t h e known r e s u l t t h a t ( S ) and (S1) a r e
e q u i v a l e n t ( T h i s l a t t e r r e s u l t i s a p p a r e n t l y due t o
James E ' e n n e t t , b u t w a s n e v e r p u b l i s h e d ; it w a s a l s o
proved by J o n e s and Selman i n Proc. 4 t h ACM Symposium
o n Thy. of Computing, 1 5 7 - 1 6 7 . )
Us8ing automata t h e o r y , w e o b t a i n among o t h e r s
t h e foI.lowing r e s u l t s a b o u t ( g e n e r a l i z e d ) s p e c t r a :
w e f i n d c e r t a i n s p e c i f i c g e n e r a l i z e d s p e c t r a 4, i n c l u d i n g
a monadic g e n e r a l i z e d spectrum,
h o l d s i f f t h e complement of
0 is
such t h a t ( G S )
a g e n e r a l i z e d spectrum;
w e f i n d a s p e c i f i c spectrum A i n v o l v i n g o n l y one
b i n a r y p r e d i c a t e symbol such t h a t ( S ) h o l d s i f f t h e
complement of A i s a spectrum; we f i n d a spectrum A
i n v o l v i n g o n l y one b i n a r y p r e d i c a t e symbol, such t h a t
{n:
2%A}
i s n o t a spectrum; and w e show t h a t f o r
many s p e c t r a A, w e can f i n d a s e n t e n c e
0
which h a s
a t most: one model of e a c h f i n i t e c a r d i n a l i t y , such
t h a t A i s the spectrum o f
0.
W e a l s o prove v a r i o u s r e s u l t s i n automata t h e o r y
itself
,,
F o r example, w e show t h a t i f t h e c l a s s e s of
s e t s w h i c h a r e polynomial-time r e c o g n i z a b l e by determinist:-~and nondeterministic Turing machines are the
5
same, t h e n t h e f o l l o w i n g a p p a r e n t l y much s t r o n g e r
c o n d i t i o n holds:
there is a c o n s t a n t k such t h a t
e s s e n t i a l l y any s e t t h a t can b e r e c o g n i z e d nondeterm i n i s t i c a l l y i n t i m e T can be r e c o g n i z e d d e t e r m i n i s -
k
tically i n t i m e T
.
I
ACKNOWLEDGEmNTS
I want t o e x p r e s s my d e e p l y - f e l t thanks t o my
t h e s i s advisor, P r o f e s s o r Robert Vaught, f o r h i s
w a r m encouragement and t h o u g h t f u l guidance.
I also
thank t h e o t h e r members o f my t h e s i s committee:
P r o f e s s o r W i l l i a m C r a i g , whose h e l p f u l s u g g e s t i o n s
i n c r e a s e d r e a d a b i l i t y and reduced ambiguity, and
P r o f e s s o r Jack S i l v e r .
I want t o e x p r e s s my g r a t i t u d e
t o my good f r i e n d L a r r y C a r t e r , n o t o n l y f o r h i s
e x c e l l e n t comments, b u t a l s o f o r l i s t e n i n g t o m e
whenever I w a s e x c i t e d about a new i d e a .
g r a t e f u l t o P r o f e s s o r s R.W.
I am
Robinson, Richard Karp,
Robert Solovay, and Ralph McKenzie f o r h e l p f u l
discussions.
I am happy t o acknowledge my d e b t t o P r o f e s s o r
Donald K r e i d e r , whose magic i n t h e classroom f i r s t
made mathematical l o g i c f a s c i n a t i n g f o r m e , and t o
P r o f e s s o r Herbert Enderton, whose t r u l y i n s p i r i n g
t e a c h i n g t u r n e d m e towards w r i t i n g my t h e s i s i n l o g i c .
F i n a l l y , I thank t h e N a t i o n a l S c i e n c e Foundation
f o r t h e i r generous s u p p o r t .