Lecture Notes in
Mathematics
Edited by A. Dold and B. Eckmann

883
Cylindric Set Algebras

Cylindric Set Algebras and Related Structures
By L. Henkin, J. D. Monk, and A. Tarski
On Cylindric-Relativized Set Algebras
By H. Andreka and I. Nemeti

Springer-Verlag
Berlin Heidelberg New York 1981


Authors

Leon Henkin
Department of Mathematics, University of California
Berkeley, CA 94720, USA
J. Donald Monk
Department of Mathematics, University of Colorado
Boulder, CO 80309, USA
Alfred Tarski
462 Michigan Ave.
Berkeley, CA 94707, USA
Hajnalka Andreka
Istvan Nemeti
Mathematical Institute, Hungarian Academy of Sciences
Realtanoda u. 13-15, 1053 Budapest, Hungary

AMS Subject Classifications (1980): 03 C55, 03 G 15

ISBN 3-540-10881-5 Springer-Verlag Berlin Heidelberg NewYork
ISBN 0-387-10881-5 Springer-Verlag NewYork Heidelberg Berlin
This work is subject to copyright. All rights are reserved, whether the whole or
part of the material is concerned, specifically those of translation, reprinting,
re-use of iltustTations, broadcasting, reproduction by photocopying machine or
similar means, and storage in data banks. Under w 54 of the German Copyright
Law where copies are made for other than private use, a fee is payable to
"Verwertungsgesellschaft Wort", Munich.
9 by Springer-Verlag Berlin Heidelberg 1981
Printed in Germany
Printing and binding: Beltz Offsetdruck, Hemsbach/Bergstr.
2141/3140-543210


Introduction

This volume
theoretical

is devoted to a comprehensive

treatment of certain set-

structures which consist of fields of sets enhanced by addi-

tional fundamental


operations and distinguished

elements.

The treatment

dimension

~

is largely self-contained.
Each of these structures has an associated
infinite ordinal;
Let
3

R

R

their basic form is well illustrated

be an arbitrary

set, and let

of all triples of elements of

of subsets of
relative to

tions

3R

~

R .

Thus

~

~ = 3 .

is a non-empty collection

intersection,

We shall assume that

CO, Cl, C 2

in the case

be a field of subsets of the set

closed under union,

3R .


, a finite or

~

of cylindriflcation,

and complementatlen

is closed under the three opera-

where

C 0 , for example,

is the

operation given by:

CoX = {<x,y,z> : (u,y,z> ~ X

C0X is the cylinder formed by moving
and

C2X

are similarly

t h a t the diagonal planes

for some


X

parallel

D02

(resp.,

and third (resp.,

D01, D02, D12

DI2 )

a r e in

3).

coincide.

is called a cylindric

3R

whose first

A collection
field of sets


fields of sets and certain closely related

structures are the objects of study in this volume.
as collections

We also assume

.

second and third) coordinates

Cylindric

CIX

~ ; h e r e , for example,

consists of all triples of

satisfying all of these conditions
(of dimension

to the first axis.

related to the second and third axes.

D01={<x,x,y>: x , y ~ R }
Similarly

u, with xER};


of sets, hut as algebraic

Considered not merely

objects endowed with fundamental


iV

Operations and distinguished elements, cylindric fields of sets are called
cylindric set algebras.
of dimension

~ , and

Cs
ICs

is the class of all cylindric set algebras
is the class of algebras isomorphic to them.

In much of the work, general algebraic notions are studied in their
application to cylindric set algebras.

We consider subalgebras, homomorphisms,

products, and ultraproducts of them, paying special attention, for example,
to the closure of


ICs

and related classes under these operations.

In

addition, there are natural operations upon these structures which are
specific to their form as certain Boolean algebras with operators, such as
relativization to subsets of
3S

with

3R

and isomorphism to algebras of subsets of

S ~ R , and there are relationships between set algebras of

different dimensions.
Although, as mentioned, the volume is largely self-contained, we shall
often refer to the book Cylindric Algebras~ Part I, by Henkin, Monk, and
Tarski.

Many notions touched on briefly in the present volume are treated

in detail in that one, and motivation for considering certain questions can
be found there.

Indeed, the present work had its genesis in the decision


by Henkin, Monk, and Tarski to publish a series of papers which would form
the bulk of Part II of their earlier work.

Their contribution to the present

volume is, in fact, the first of this proposed series.

As their writing
l

proceeded, they learned of the closely related results obtained by Andreka
and Nimeti, and invited the latter to publish jointly with themselves.
Thus, the present volume consists of two parts.

The first, by Henkln,

Monk, and Tarskl, contains the basic defintions and results on various kinds of
cylindric set algebras.
parallel to the first.

The second, by Andrlka and Nemeti, is organized
In it, certain aspects of the theory are investigated

more thoroughly; in particular, many results which are merely formulated


V

in Part I, are provided with proofs in Part II.


In both parts, many

open problems concerning the structures considered are presented.

The authors
Berkeley
Boulder
Budapest


Table

First

Part:
L.

Cylindric
set algebras
Henkin, J.D~ Monk, and
set

and related structures,
by
A. T a r s k i
..................

2.


Relativization

....................................

12

3.

Change

....................................

33

4.

Subalgebras

.......................................

56

5.

Homomorphisms

.....................................

66


6.

Products

7.

Ultraproducts

8.

Reducts

9.

Problems

base

..............................

i

Various

of

algebras

contents


1.

..........................................

References

Second

of

.....................................

4

73
86

...........................................

122

..........................................

126

............................................

128

Part: On cylindric-relativized

set algebras,
by
H
Andr~ka
a n d I. N ~ m e t i
..............................
concepts

O

Basic

i

Regular

2

Relativization

.....................................

153

3

Change

.....................................


155

4

Subalgebras

........................................

185

5

Homomorphisms

......................................

209

6

Products

7

Ultraproducts

8

Reducts


9

Problems

References

Index

of

symbols

Index

of

defined

and

cylindric

of

base

notations

131


set

algebras

.......................

132

.....................

145

...........................................
......................................

222
229

............................................

261

...........................................

310

............................................

314


...............................................

317

terms

.........................................

322


Cylindric

set algebras and related structures

by L. Henkln,

The abstract
the book [HMT]
mentioned,

J.D. Monk, and A. Tarskl

theory of cylindric algebras

by the authors.

primarily

is extensively


Several kinds of special

for motivational

purpose of this article

I)

purposes,

developed

set algebras were

in that book.

It is the

to begin the examination of these set algebras

more detail.

The simplest and most important kind of set algebras are

the cylindric

set algebras

introduced


we shall refer to items from

in 1.1.5.

(Throughout

Recall that the unit element of any

set algebra

(Cs)

is the Cartesian power

and the other elements of
DKk

of

~

is

the set

A

and for each


of cyllndrlflcatlon

are subsets of

ix E ~U: x K = x k }

fundamental Boolean operations
mentatlon;

K < ~

of

~

~U

of a set

~U .

K,h < ~

(the base),

"

are union, intersection,

the fundamental operation


their definition is similar to that of a cylindric
(cf. 2.2.11),

U

cylindric

The diagonal element

for each

by translation parallel to the

set algebras

this article

~ - dimensional

CK

the

and compleconsists

Kth axis of the space.

Several other kinds of set algebras were briefly considered


cylindric

in [HMT], and

set algebra:

generalized cylindric

weak

set algebras

(of. 1.1.13), and what we shall now call generalized weak cylindric
algebras

(cf. 2.2.11).

unit elements

in

[HMT] by number without explicitly mentioning

that book).

~

in

The algebras


set

of each of these kinds have for their

subsets of a special kind of some Cartesian

space

~U , while

I) This article is the first in a series intended to form a large portion
of the second volume of the work Cylindric Algebras, of which Part I has
appeared ([HMT] in the bibliography).
The research and writing were supported in part by NSF grants MPS 75-03583j
MCS 77-22913.


the fundamental
a

Cs

operations

of any such algebra are obtained

, with unit element

to the unit element


~U

of the algebra discussed.

these several classes

of cylindric

general class of set algebras
algebras,
space.

, by relativization

set algebras

in any detail,

relativization
w h i c h are

directly relevant

first-order

discourse

ourselves to the aspects


to our d i s c u s s i o n

of

of those set algebras

A

forms an

for

~

free

regularity:

if
(Here
.)

~

Furthermore,

x E B
~gx

Regular


,

f E x

,

, the dimension

of

of [HMT]).

and any

A

field of sets,
(for the

Thus the above

set algebra
i. Ii.i

K < ~
~

~


cylindric

of variables

in the sense of

for the finitely many

in

structure

~ - dimensional

of a cylindric

is locally finite dimensional

stems from the

, the collection

see the Preliminaries

is the universe

except possibly

set algebras


Given any relational

is the length of the sequence

collection

1.6.1

set algebras.

the class of all cylindric-relativized

of cylindric

language

~ a formula of A]

notation used here,

see

that are

CA's

following construction.

g E x


of

set

of those algebras

from full cylindric

restricting

Much of the importance

occurs

2.2)

in w h i c h the unit elements may be arbitrary subsets of a Cartesian

We shall not discuss here, however,

~

To unify our treatment

that of the cylindric-relativized

These algebras are simply subalgebras

where


(in the sense of

set algebras we use here as the most

obtained by arbitrary relativizations

[~:

from those of

~

.

This algebra

, since

such that the

CK~
~
Kth

variable

has an additional property of

g E


C

set of

, and
x

, is

Ax~f = ~xlg

, then

~K E ~ : cKx f x}

set algebras will be discussed e x t e n s i v e l y

The article has nine sections.

=

later.

In section 1 we give formal defini-

tions of the classes of set algebras w h i c h are studied in this article
and we state the simplest relationships
found in later sections of the paper.
ships are established,


b e t w e e n them; the proofs are
In section 2 some deeper relation-

using the n o t i o n of relativization.

is concerned with change of base,

treating

Section 3

the question of conditions

;

of


under which a set algebra with base
different base
L~wenheim,

W

U

; the main results are algebraic versions

Skolem, Tarski theorems


are also found in section 7).
subalgebra is investigated
cular attention

is isomorphic to one with a
of the

(some results on change of base

In section 4 the algebraic notion of

for our various

set algebras,

paying parti-

to the problem about the minimum number of generators

for a set algebra.

Homomorphisms

of set algebras are discussed

tion 5, and products, along with the related indecomposability
are studied in their application
7, devoted to ultraproducts
results in the paper.


of set algebras,

In particular,

less trivial of the relationships
described

to set algebras

in section 6.

gives perhaps

in secnotions,
Section

the deepest

it is in this section that the

between the classes of set algebras

in section 1 are established.

set algebras are discussed in section 8.

Reducts and neat embeddings of
Finally,

in section 9 we list


the most important problems concerning set algebras which are open at
this time, and we also take this opportunity
of the problems

stated in

For reference

[HMT]

to describe the status

.

in later articles, we refer to theorems, definitions,

etc., by three figures, e.g. 1.2.2 for the second item in section 2 of
paper number I, which is just the present paper

(see the initial footnote).

The very most basic results on set algebras were first described
in the paper Henkin, Tarski [HT].
in Henkin, Monk

[HM]

.


Other major results were obtained

In preparing

the present comprehensive

sion of set algebras many natural questions arose.

discus-

Some of these ques-

tions were solved by the authors, and their solutions are found here.
A large number of the questions were solved by H. Andr~ka and I.N~meti.
Where their solutions were short we have usually included the results
here, with their permission,
theirs.

and we have indicated

that the results are

Many of their longer solutions will be found in the paper

[AN3]


4

Various


following

set algebras

this one, which is organized

I.i.i

parallel to our paper; a few

of their related results are found in

JAN2],

course of our article we shall have occasion
of their related results.

JAN4]

, or [N]

.

In the

to mention explicitly most

We are indebted to A n d r ~ k a and N~meti for


their considerable help in preparing this paper for publication,
The following set-theoretical
If

f E ~U

that

,

~ < ~ , and

(fK)>~ = fk
u

if

u E U , then

k # < , while

reasons we sometimes write

1.

D e f i n i t i o n I.I.I.
V ~ ~U

.


For all

notation not in [HMT]
fK
u

is

the

(fK)K = u .
u

f(K/u)

in place of

will be useful.

member of

~U

such

For typographical
fKu

y~arious set al$ebr~as


(i)

K,~ < ~

Let

U

be a set,

~

an ordinal,

and

we set

D[V] = [y E V : YK = Yk}

and we let

every

C IV]

be the mapping

SbV


into

SbV

such that,

V

u E U]

is implicitly understood we shall write

simply

A

= [yEV

K

for some

(ii)

: Yu E X

- dimensional

is an


iff there is a set

and a set

U

D

cylindric-relativized

V ~ ~U

such that

A

V

and

K < ~ ), and containing as elements

C IV]
K

(for each

closed under all the operations

(for all


<,~ < ~ ).

(iii)

is a c y l i n d r i c - r e l a t i v i z e d

with base

~
U

The base of

iff there is a set

V ~ ~U

A

is the set

or

C

field of sets

U, N,


V

the subsets

UxEvRgx

.

set al~ebra of dimension
such that

.)

is a non-empty

family of subsets of

D [V]

for

X -~ V ,

C[V]x
(When

from

C~



I.l.l

Various

set algebras

= u
~ K,~ < ~
cyllndric-relativized
Crs
.

' where

is the class of all c y l i n d r i c - r e l a t i v i z e d
In case

relativized

(iv)

A = SbV

, the set

A

p E ~U

U

be a set and

space with base

U

V

and base

set algebras

and the algebra

~

U .

of dimension

are called res-

field of sets and a full cylindric-

~

an ordinal.

and dimension

~U

is then called the

~

Moreover,

for every

we set

~u (p) = {x E ~ U

and we call

~U (p)

determined b y

: {~<~

(v)

(v) - (ix)

, respectively

field of sets,
all cylindric
(vi)
cylindric
p ~ ~U

field of sets,

A

the form ~
distinct

iEl

~y

i,j ~ I .
Gs

~

~

~

and dimension

Yi

that

is a c y l i n d r i c - r e l a t i v i z e d

, and unit element
~ - dimensional

V = ~U

.

V

cylindric

The class of

is denoted by

Cs

~ - dimensional weak

set algebra,

if there is a
~ - dimensional weak

Ws

, is called an

respectively

Yi ~ 0

The sets

U

The class of all

is denoted by

where

if

~

, is called an

respectively

field of sets,
i '

, base

of dimension

, respectively

lized cylindric

U

of this d e f i n i t i o n we assume

, is called an

V = ~U (p) .

set algebras

(vii)

~

set algebra,

, respectively

such that

cylindric

~

respectively
set algebras

A

is finite}

field of sets and

both with dimension

A

~ p~}

p

is a c y l i n d r i c - r e l a t i v i z e d

set algebra,

: x

the w e a k Cartesian space with base

For the following parts

symbol

~ - dimensional

set algebra.

Let

Cartesian

is an

field of sets with unit element

pectively a full c y l i n d r i c - r e l a t i v i z e d

A

A

for each

~-dimensional

set algebra,
i E I

'

if

and

V

has

Y. N Y . = 0
l
J

are called the subbases

denotes the class of all generalized

genera-

cylindric

of

~

.

for any two
The

set algebras


6

Various

of dimension
(viii)

A

weak cylindric
U
iEI ~i

'

, respectively
field of sets,

where

pi E ~Yi

for any two distinct
.

We use

algebras

g E x

Gws

K

~ = 0

, is called an

respectively
for each

x E A

x ~ A

in

Crs

all regular algebras w h i c h belong

~Lb~

Yi

V

~y~pi)

are called

~

generalized

has the form
~u
-j

0

the subbases of

~

be a cylindric

formal definition).
E K

K
,

Remark 1.1.2.

A

and

~

, are called regular.)
K reg

the class of

K

algebra and

The d e f i n i t i o n

b E A
~

to

I.I.5.
in

of cylindric

We denote by
b

(see

2.2.1

in the introduction.

set algebras

Other parts of
1.1.13

and

regularity was defined only for cylindric

for a

I.I.i

2.2.11

in

l.l.l(v)

are consistent

o

Originally,

set algebras,

The general definition

in

in the form given

I.I.i

(ix)

is due to

H. Andr~ka and I. N~meti and turns out to have the desired meaning
set algebras

as well as

Ws's

and

The inclusions holding among the various

consider

in

I.i.i

the classes

~ > 0 ;

b ~ A}

with the informal definitions

introduced

and

(We assume here

, we denote by

to

A

being a class of cylindric algebras, we let

coincides with d e f i n i t i o n

cylindric

set

that

is regular.

the algebra obtained by relativizing

R~K = [ ~ b ~ : N

if

(gxU 1)I f = (~xU i)1 g

as well as

being any class included

Let

and

is regular provided

f C x , g C V , and

, all elements,

(x)

set algebra,

i E I

The sets

~ - dimensional

~.

are called regular if each
if

1.1.2

for the class of all generalized weak cylindric

An element

whenever

~

i,j E I .

of dimension

(ix)

set algebras

~ .

are indicated
of isomorphic

then the diagram collapses

in Figure

's

; see

1.1.13 -1.1.16.

classes of set algebras
1.1.3

for

images of the various

as indicated

in each case are proper inclusions.

Gs

for

in Figure 1.1.4

~ > 0

; if we

set algebras,
.

The inclusions


1.1.3

Various set algebras

7

C i s ~ .

crsreg

Gws
ic

Gwsreg

i

~

~

sa,~

~ ~

G!reg

C s ~ .

Ws ~reg = W s

C reg
0~

Figure 1.1.3

ICrs
I ~ C ~

eg

= I s

IGws

iCrs reg
= IGws reg

ICs

r

iCs reg
IWs

= IWs reg

Figure 1.1.4

In case

~ < w , the classes

and

; furthermore, under this assumption each member of any of

Gs

these classes is regular.
to subdirect products of
Gws's

and

Ws's

phic to a regular

.
Gs

Ws

and

Cs

coincide, and so do

In the general case,
Cs's

Every

Ws

Gs's

Gws

are isomorphic

and conversely; similarly for
is regular.

Every

Gs

is isomor-

and to a subdireet product of regular

Cs 's.

Proofs of these facts and the relationships in the diagrams will be
found at the appropriate places in this paper.
We begin our discussion by describing some degenerate cases of the


8

Various

notions
which

in

I.i.I

follow

, and giving

easily

omit proofs which

Corollary
element

V

1.1.5.

Let

N

V = 0

iff

be a

(iii)

If

of > 0

and

U ~ 0 , or

Corollar~
ofU (p) = ~U

.

Cs

the paper we

w i t h base

U

and unit

Hence

Crs I

for

1.1.7.

V = 0 .

frequently

~ < ~

,

U

make

such a s s u m p t i o n s

is any set, and

~ < 0~ we have
} , where

If

~

Gs

= Gws

p E ~d

, if

~of is the unique

as

, then

0 < ~ < w

Cs~

with universe

, where

the base

2

Gws

w i t h every

subbase

I ;

~I

and

Corollarx. 1.1.9.

Crs 0

(i)

(ii)

For

of ~ I ,

Crs

(iii)

For

of ~ 2 ,

Crs

N2

are the unique
Furthermore,

is

0 .

For any

,

_c CA
of

, where

Crs 0 = Gws 0 = Gs 0 = [~i,~2]

respectively.

of any

having

Gs

Crs I = Gws I = Gs I = Cs I = Ws I U [~}

with universe

and

is a

is a discrete

then

1.1.8.

Cs 0 = Ws 0 = [~2}
I

= 2 .

Cs 0 = Ws 0 .

only one element,

Corollary

IAI

.

U = 0 , then

If

= Ws~ U [

Corollary

then

V ~ 0 .

1.1.6.

I , and finally

full, and

the classes

Throughout

V = [0}

V ~ ~0}

of this theorem we w i l l

universes

Crs

IAI = I ; if

of = 0 , then

we have

between

seem trivial.

If

of > 0 ,

inclusions

from the definitions.

(ii)

is the

those

1.1.5

.

(i)

Because

set algebras

~ CA

of
of

Cs

U Gs

Crs0's

every

of

U Ws

Crs 0

~

U Gws

and
with
is

c CA


I.l.lO

Various
Proof.

Both

we construct

~ E Crs

IuI > 1 , taking
w i t h unit

cerning
tion,

l9

Crs

trivial.
by c h o o s i n g

, and letting
We have

0 .

Thus

~

role

(iii),

U

with

be the full

D IV] = 0

Crs

so that

V =

axiom

(C6)

results

con-

'

to satisfy

,

is complete

w h y we

is introduced

shall not give many

Just

as indicated

to unify

in the introduc-

some definitions

and

results,

in our discussion.

If

I.I.I0.

any set

~

fails

in these papers;

an a u x i l i a r y

To e s t a b l i s h

~ ~ 2 , then

Cs

~ Gs

and

R~Cs

~ Crs

c~

We shall
Gws

ffz2

9

O1

explains

this class

are

(l.l.l(iii)).

and the proof

Corollary

SR%Cs

for

Ivl
I0 ) =

the class

and plays

(ii)

~CA

V

'

~ ~ CA R

Corollary

and

v = ~u ~ -01
n [~U]

element

Ivl
whence

(i)

set algebras

be able

c RgCs ~

although
Rs
[HR]

for

P~Cs O

c Crs

~ a 2
=

for

and Prop.2.3

Corollar~f
C Gs

to strengthen

these

below by showing

(see 1 92 . 12 - 1.2,13).

Crs O

mnd

~ > 1

RgCs I

but we

=

Cs I

that

It is known

,

that

we have

shall not give an example

here"

see

and

Cs

of [AN3] (p.155),

I.I.II.

If

~ ~ w

, then

Ws

~ Gws

C Crs

~ Gws

Theorem

I 1.12.

Let

~

be a

9

where

results

Then

for all
for any X

with

unit element

~

~. (pi) N ~ U (pj) = 0
ui

j

~U! pi) E A
l

Gws

E A

the

Also

assume

following

~u(pi)

~iEl

for all distinct

i E I .

~

i,j E I .

Assume

-i

that

~ ~ i .
conditions

are equivalent:

'


10

Various
(i)

X = ~u~i(pi)

(ii)
and

&X

=

X
0

i E I ;
(under

=

) such that

X ~ 0

.

(i) =

(ii)

~ U ~ pi) = 0 .

y E Y

for some

is a minimal element of

Proof.
and

1.1.13

set algebras

and let

Clearly for any

Now suppose

x 6 ~, (pi)
ui

,

such that

.

(~F)?y

that

.

we have

0 ~ Y ~ ~.(pi)
ui

be arbitrary.

= (~F)~x

i E I

~us

There

and

0 ~ ~U~ pi)
Ay = 0 .

is then a finite

x E c(F)Y = Y, and hence

Fix
F ~

Y = ~u!Pi~
l

(ii) =
# 0 .
by

(i)

Assume

Since &~U! pi) = 0

(ii)

ui

established,

,

Gs

such that

X n ~U~ pi)

by 1.6.6

while by the implication

(i) =

Hence
(ii)

already

,

~,u i(pi) = X N ~.u i(pi)

Now we discuss regular

iEl

(pi)
&(X ~ U i
)= 0

we have

X = X n ~ (pi)
,

Ws

(ii), and choose

Thus

set algebras.

(i)

holds.

In the case of the classes

the definition assumes a simpler form mentioned

Cs

in the

introduction.

Corollary I.I.13.
X E A

.

~

be a

Cs

with base

U , and let

Then the following conditions are equivalent:

(i)

X is regular;

(ii)
gEX

Let

for all

f E X

and all

(i) .

Trivial.

g E ~U , if

~XI f = AXJ g

then

.

Pro0f.

(ii) =

the hypotheses
is obvious.

of

Suppose

(ii)

.

If

therefore

(&X
~, U I )~ fOgO = ( ~ X U I ) I g

The next two Corollaries

.

(i) =

(ii) .

Assume

(i)

0 E AX , the desired conclusion
0 ~X.

Hence

g E X

Then
by

f0
gO E X

since

0 ~X

(i) .

are proved in the same way as

1.1.13.

and
g E X
and


1.1.14

Various

Corollary
and

let

X E A

(i)

X

(ii)
g E X

1.1.14.
.

Let

Then

~

be a

the following

11

Ws

with

conditions

f ~
~U ~p~

unit element
are equivalent:

is regular;
for all

f E X

and all

g ! ~U (p)

, if

AXI f = &X1g

then

.

Corollary
where

Yi N y j

conditions

1.1.15.

= 0

Let

for

~I

i # j

be a

, and

Gs~

let

w i t h unit element

X E A .

Then the

~ i E l Y'l '

following

are equivalent:

(i)

X

(ii)

is regular;
for all

i E I , all

&XI f = ~X1g

then

No analogous

simplification

known.

cylindric

Weak

Corollary

Proof.

Suppose
X E A

f,g E ~U (p)

, there

Hence

[~N(F~X)]If=

I.I.14

,

X

' and all

g E CYYi , if

of the notion

set algebras

of regularity

are always

for arbitrary

Gws

regular:

Ws reg = Ws

that

~

is a

Ws

, f 6 X , g E ~U (p)
is a finite

F ~ ~

[~(F~AX)]Ig,

w i t h unit element
, and
with
so that

~X1f

= AX1g

(~NF)If

.

~U (p)
Since

= (O~NF)Ig

g E c(FN~x)X

9

= X .

Thus by

is regular.

Corollary
= Gs reg

f E X f3 ~Yi

g E X .

1.1.16.

A l s o assume

Gs

set algebras

1.1.17.

, and

Gws

If

~ < w

, then

Cs

= Cs reg

, Ws

= Ws reg

,

= Gws reg

reg
Corollary

1.1.18.

If

~ ~ w

,

then

Ws ~reg c Gws

~

~ Crs reg

and

's is


~2

Relativization

1.1.19

Cs~ eg c Gs~ eg c Gws~ eg .

Proof.

To produce a member of

Gws reg N Ws reg , let

two disjoint sets with at least two elements, and let
be arbitrary.

Let

~

be the full

Gws

U

p E ~U , q E

with unit element

Then it is easily checked, along the lines of the proof of
E Gws reg ~ Ws

It is also clear that

the two-element
Gws

with unit element

Crs

(provided that

Finally,

if

of the full

U

and

p

V

are as above and

Corollary 1.1.19.
and

~V

If we let

~

that
be

~ E Crs reg

For

~ m w

~

is the minimal subalgebra

~U U ~V

we have

, then

~ E Gs reg N Cs

Cs reg = Cs

, Gs reg c Gs

Gws reg c Gws

Proof.
regular.
Then

be

~U (p) U ~V (q)
1.1.16,

, we see that

V

has more than one element in its range).

with unit element

Gs

~ ~ Gs
{p}

and

By

Let

~i

~2(P) E A

in a regular

Cs

I.I.Ii

it suffices to exhibit a

be the full
and

Cs

A~2 (p) = 0 .

the only elements

with base

2 .

Hence

~2 (p)

X

such that

Cs

which is not

Let

p = <0 : K < ~ }

is not regular,, since
AX = 0

are the

zero element and the unit element.

2.

Relativization

Our basic kinds of set algebras have been defined in terms of relativlzation of full cylindric set algebras.

We want to present here some results,

1.2.5, 1.2.9, and 1.2.11, which involve relativization and exhibit important connections between

Cs's

and

Gws

mentary characterization of unit sets of
in 2.2.11.

's.
Gws

First we establish an ele's, which was mentioned


I .2. i

Relativization
T h e o r e m 1.2.1.

Let

~

F = [XEA

Under these premises,

13

be a

Cs

: sK}XAsKXX = X

cient for any given set

F=A

V

belongs

V

to

A

to

, assuming

imposed on

is necessary and suffi-

F :
~ ~ I

(so that in this case

);
(ii)

V

(iii)
ing

belongs
V

to

belongs

to

A

and is a Cartesian
A

space, assuming

and is the unit element of a

~ = 2 ;

Gws

, assum-

~ e 3 .

Under the same premises we obtain an additional
(iv)

assuming

2 K ~ < m

are jointly equivalent
a

o

assumption

(i)-(iii)

to belong

U , and let

for all K , ~ < ~ }

dependent on an additional

, each of the following conditions

(i)

with base

Cs

in case

Proof.

, the conditions

to the condition

~ = 2 , or a

Gs

of

(ii) .

~ • 3

and consider a set

a

, say

V = ~U'EI ~W~ pi)

i,J

I

sK~V .

with

i ~ J .

Now suppose

~.wj(Pj)

Pick a

is a finite

therefore we define
for every

quently

i = j

conclude

that

where

and

such that
g

of

V E F , as desired.

(i)

U .

is obvious, and so

n --j~w(PJ) = 0

of

(iii)

,

fKfk E ~W!pi)l

that

f = (~F)I

f

and

pi = ( ~ F ) I

g~ = f~

V ~ sSV N

E W i n W..
pj

for all

g E ~W~ pi) n ~W j(pj)
Hence

for any

we clearly have

say,

by stipulating that

f E ~w~Pi) ~ V 9

VEF

w h i c h is the unit element of

and notice

~ E ~ ~ F ' we get

and

is the unit element of

the sufficiency

K,~ < ~ ,

(~F)~

C(o~,I)V = V

~ m 3 , with base

o~pi)

f E s~V N sKXV", thus
,

F ~ ~

g~ = f~

V E A

Given any

~ E ~ ~ [K,~]

V

in case

To establish

assume
Gws

that

The necessity and sufficiency

is the sufficiency

conclusion:

f~K E
There

.

If

~ E I~
9

Conse-

V = sK~V N sK~V, and we

, and


14

Relativization

We wish now to demonstrate

1.2.1

the necessity

To this end, we show first that every set
a

Gws

of both

V E F

(ii)

f E V

of

and N~meti.)

let

Yf = [ u E U

We need the following

If

f E V

For,

if

< < c~

(2)

If

f ~ V

(3)

If

f E V , u E Yf

For

we may assume

,

,

: fOEv}

facts about

(I)

Yf

then

f E ~ Yf

then

f E V = s0V

and

u E Yf

9

,

, then

, and

that

.

so

E V

and hence

Yf = Yf(0/u)
_

K < ~

K ~ 0 .

fO

f<

, then

Then

fKu E V .

f0 E V ~ s~V
~

f E V ~ s~V

whence

V

fK

, so

fOE E V .

~ ~V

=V

U

UU

O
f~ E ~ V

~ce

fK E Yf

"

U

Also,

(iii).

is the unit element

(This portion of the proof is due to Andr~ka

For each

and

as

desired.

(4)

If

Indeed,

f E V , K < J , and

(4) clearly

the hypothesis
have

fO,f0~V~
U

of (4).
s~V

V

v E Yf(K/u)

follows
Then

so that
~

u E Yf

from (2) if

fKu E V

E =0

by (3).

fKu E V

.

From

Consider

(5)

~Y~f) t: V .

(6)

If

f,g Q V

and

f Q ~Y(g)
g

(7)

If

f,g E V

and

~"Yf(f) ~ ~Y(g)
g

yf c yf~K/u
~[~

~ ~0

now any

VH

we get

' then

(5)

Y g ~ Yf

, then

and

(6):

.

~'(f)
~f

= ~Y(g)
g

B

, and assume

fOE E s ~ V n s O v = v

~rv

(4)

and

Assume

fOK,f OK E V . Hence
UN

, as desired.

, then

v E Yf
.

. We

Thus


1.2.2

Relativization

In fact,

(8)

f E

If

~,(f)
if

f,g E V

Let indeed

By

(8) ,

In case

~ =2

f,g E V

then

yf ~ Y

~ 0

g

It follows
(iv)

~f

and

Y

~ Yf

g

by

N

~y(g)
g

.

Then by

is the unit element of a

, we have

~.~f(f) = ~yf

Gws

that

V

~Yf ~ ~y

~ 0 .

g

~ (f) = ~Y (g)

~f
g

, as desired in (iii).

f EV 9

f0
0 n s0V
1 ~ V , and consequently,
gl E SlV

and hence

Therefore

Furthermore,

C(a~I)V = 1

if

gl E Y f 9 Thus by (I),

~Yf = ~y

is a Cartesian space, as desired in

is clear since the condition

(g)
g

Yf U Yg = Yh ' so that

by (7),

for all

= ~Y

~ (f)
~y(g)
yf
=
g

(6) ,

~y(g) ~ ~ (h)
Therefore,
g
Yh
"

V

~y~f)

(6) , whence

~_ (f)
~y(g)
yf
A
~ 0 , then
g

and

~. (f)

h E

~-(f) c ~y h)
~f
-

, so that

18

g

by

(ii)

is equivalent

(8)
Finally,

to

UpEvRgp = U .
Theorem 1.2.2.
with base a s~t

Assume

that

U , and let

~

~ ~ 3 .
be a

Let

Crs

~

be the full

with unit set

Cs

V ~ ~U .

Then the following conditions are equivalent:
(i)

~

(ii)

is a

Gws

s~V n s~V = V

Proof:

By

characterization
For

~ ~ I

and

be the full
~(~)X

.

U1

~ ~ 3

(operating

Theorem 1.2.2

the corresponding
for

of those elements of a
U0

K,k ~ ~

of those unit elements of

On the other hand,

let

for all

in

~ ).

1.2.1.

Remark 1.2.3. For

Cs

;

Gws

's which are members of a

result is trivial,

in view of 1.1.8.

~ = 2 , there is no elementary characterization
Cs 2

which are unit elements of a

be disjoint
Cs 2

gives a simple elementary

In fact,

sets each having at least two elements.

with base

One easily checks

Gs 2

that

U o U U I , let
9

X = 2 U o U 2 U I , and let

is atomic and actually possesses

Let
B=
just


16

Relativization

three atoms

2

D01,X ~ DO1 , and

1.2.4

(U 0 U U I) ~ X

completely determined by the fact that

and that its structure

CoY = CIY = 1

It follows directly that there is an automorphism of
changes

the atoms

interchanges

X ~ DO1

the elements

unit element of a
all first-order

and
X

and

(in arbitrary

of interest
V ~ A

of such elements of

that if

~

sentences

Cs2's).

is a unit element of a

As

with field included in
Im [AN3]

V

is the
satisfies

DOI U ( 2 ( U o U U I) ~ X)

(or even higher-order)

with base

iff

Gs 2

X

that hold for all

Cs2's is possible.

Cs 2

is a full

As

DO1 U 2(U 0 U U I) ~ X

is not itself such a unit element, no elementary
characterization

which inter-

DO1 U 2(U 0 U U I) - X .

(and indeed higher-order)
Gs2's

~

Y .

2(U O U U 2) ~ X , and which therefore

Gs 2 , this implies that

unit elements of

for each atom

is

It is also

U , then an element

is an equivalence

relation

U .
a m

it is shown t.hat for

terization of the unit elements of

Gs's

there is no elementary characwhich are members of a given

The other main results of this section are related to the following
obvious

theorem.

Theorem 1.2.4.

similar to

For any algebra

CA

's the following

three conditions are equivalent:
(i)

~ ~ Crs

(ii)

;

~ ~ ~L.~

for some full

Cs ~

and some

V s B ;

~ V

(iii)

~ C ~5..~
v

for some

Cs ~

and some

V E B.

The question naturally arises whether the condition
can be replaced by
general
for

~ = ~L V~ .

is negative.

our classes

Ws

For arbitrary

~ ~ ~L@

C r s 's

in

(iii)

the answer in

Here we want to carefully consider this question
'

Gs ~

, and

Gws

We begin with the following

Cs .

1.2.5

Relativization

simple

result.

T h e o r e m 1.2.5.
Ws

with base

U

~(~)A

for

~

Proof.
first note
H~nce

Ws

if we let

V

~

that

Obviously

~ ( ~ ) V = 0 , and hence
: XNV~A]

Remarks 1.2.6.

so

~i~

In fact,
Thus

and let

~[ be the full

so that

V ( C .

9/

Gws

Cs

~ ~

~U~ q)

if

of

~D

i ~ j .

~V~D

in the subbase

~

.

with

U , we can take

For the converse

: XNV

s

E Su~ .

does not extend to

Let

V

~U p) U

tu ," note that

be the minimal
0

subalgebra

,

~i

U0 U U1 = w ,
of ~ [ V ~

(cf. 2.4.61),

~LV~

.

Thus

and hence

generated by its diagonal ele-

is any

but not in

Just constructed

sense.

elen~ent of

Cs ~

a

Cs

cl

with

V 6 D

and with

~D

is in

The Gws

following

for some

is

U 0 = 00 , U I = • , I , p = <0 : K < ~ >

c0(-v) N v = Uu[ q)

is included

~

, as desired.

1.2.5

It has characteristic

w , then in

9/ ~ ~ 6 V ~

with base

9]

On the. other hand,

so that

assuming

with base

~U p) N ~U q) = 0 .

Cs~

We let

let

is simply the B o o l e a n subalgebra

base

9/ = ~L 2

A ~ [XEC

The last part of

~ > o~ .

q = (I : ~ < ~ )

ments.

we have

be the full

V = ~U (p)

B C [XEC

is a

More specifically,

.

Say

Gws~'s with

R6Cs

and unit set

V E B ; in fact,

and

17

Let

widely-distributed

be a

(Pi)
UiEl W i

is

We call

~

UO .

~
if

Usually a

Gws

J

Hence

9/ ~ ~L ~D .
V

in that the subbase
Gws

is normal,

, ~ ~ o~ , and suppose
~ (Pi)
(P.)
Wi
n ~W i j = 0

W i = W.
J

W i ~] W. = 0

A .

is unusual,

~
, with

normal if

,

or

whenever

W i [~ W. = 0
J

U1

in the

the unit

whenever

i,j E l

for all

i ~ J ; compressed
,

i,j

if

;

and


18

Relativization

W i = W.
J
Cs

for all

i,j

Thus every

blished

in section

Gws

7

is a normal

~

is a direct

is a

P~Cs

It follows

of this p a p e r

widely-distributed

to a

Gs

Gws

factor of a

with

that

show below

in 1.2.9

It

is also clear

Cs

w h i c h has

Gws

at least

Gs

Gws

Gws

c P~Cs

Henkin,

lemmas

~ ~ w

, since

~

; so

by 2.2.10,

can always be

the same base as
3 ~ ~ < w

and

~
~

~ ~ w

.

We

is a
we have

the last part of 1.2.5 holds

then

Gs

~ ~ ~

that in case

of course,

, since we have

that

that every compressed

with

in case

Gws

~ Gws

= Gs

.)

We also have

1.2.9

is due

to

jointly by H e n k i n and Monk.

two lemmas about a r b i t r a r y
recall

is i s o m o r p h i c

the same base as

having

1.2.11 has b e e n obtained

We n e e d
these

(Thus,

~ < ~

in case

while

Cs

~

, we show in 1.2.11

= P~Cs

's with

from a

that this is true

On the other h a ~

Gws

same base.

o b t a i n e d by r e l a t i v i z a t i o n

for

, and every

from results w h i c h will be esta-

that e v e ~

We do not k n o w w h e t h e r a normal

Gs

Gws

~

is a c o m p r e s s e d

Gws

.

1.2.7

CA

~[b ~

's.

In c o n n e c t i o n w i t h

is a

CA

for e v e r y

kJ

~ CA R
all

and every

K ,k <

~

Lemma

1.2.7.

~Lb ~

K,h < ~

(ii)

Let

for all

of the a l g e b r a

(i)

If

If

be any

K,k < c~ .
.

, any

The

F C ~

F • A C ~

Let

sKbk " s~b = b

for

and

, let

b E A

, and assume

that

+i '_i 'c K'
I

F,~ ~ ~

then
b

b

etc.

conditions

9 C(FU[~})x

9 C(F)X =

O (F)
I
X

be the operations

(i)-(vi)

, and any

F ~ g = O , then

, then
=

CA

following

finite

F U [F.] ~ cY

(iv) c(r)C l(r ) X
If

SJ

F U & c ~

If

(iii)

(v)

that

.

sKb 9 sXb
K = b

for any

h a v i n g the p r o p e r t y

b ~ A

x,y < b
C(F)b

hold

then

:

9 C(A)b = b

.

~ cK(b 9 c(F)x )
9

c(r)x
, then

C(F)X

I
9 c(~)y = C ( F ~ a ) ( c (IF ) x 9 c(~)y)

1.2.7

Relativization
(vi)

If

F c ~

Furthermore,
K,~ < ~

let

,

eKk

!

then

assume

19

-C(F)X = C(F)(b .-e(F)X ) + -C(F)b

that

~ < w

c(~K,k])b.

and that

c(r

= 1 .

.
For all

Then the following conditions (vii)-(xii) hold.

(vii) c(~.f~])b = I
(viii)
(ix)
(x)

c(F)b = N~,~Ec~F e ~
e e

~k

= e

"

whenever

KX

~ < c~ and

~ @ K,~

.

dKk g eKk

(~i) d k = c(~{~,k})(b.dk)
(xii)

Suppose

F U [~0 } c ~

that

~ E ~o- I , ~ E ~

w = c(r)x

, and

c o(C(F)X -~
~,e.+-+t

Proof.

for

F = 0

or

then

IF1 = 1 = IA I ; say

so

(i)

holds
K E A

holds

for sets
and

h E ~ N

ccru{~o} )x

by induction

A = 0 , so suppose
F = [K]

in this case.
F'

) =

(i)

b ~ c b 9 c b < c sKb
K
k
K ).

, AI

with

(F U A )

b ~ c(r)b
= C(F)b

= c(r)b
= e(r)b

9

9

Then

E~..le~

- e~ 0~

(i). We prove

vious

9~

-%0 ~

"

on

and

A = [k}

.

IF U A 1 .

F ~ 0 # A 9
9

If

It is obIF@A1

= 2 ,

Then

9 cks~b = sKkb 9 skb = b
K
'
Now suppose
IF'UAII

<

that

IFUA I > 2

IFUA[

Say

c(a)b ~ c(r)b

9

c(F)s~b
b

s~(c(F)b c(A~K])b)

9

9 s~b g c(F)b

9 cKb = b .

9

and that

IA I > 1 .

Then

9 sKxC(F)b 9 sKc
9

, ~ 0 ~ F U [~I ..... ~ - I ] '

c(a)s~h

(i)
Choose