Projective Logics and Projective Boolean Algebras (*)

Projective Logics and Projective Boolean Algebras (*)

Non-Classical Logics, Model Theory and C o m p u t a b i l i t y , A.I. Arruda, N.C.A. da Costa and R. Chuaqui (eds.) 0 North-Holland P u b l i s h i ...

764KB Sizes 4 Downloads 49 Views

Recommend Documents

No documents
Non-Classical Logics, Model Theory and C o m p u t a b i l i t y , A.I. Arruda, N.C.A. da Costa and R. Chuaqui (eds.) 0 North-Holland P u b l i s h i n g Company, 1977

F'ROJECTIVE LOGICS AND PROJECTIVE BOOLEAN ALGEBRAS (*I by R I C A R D O hlORAIS

I, INTRODUCTION, Lusin and S i e r p i n s k i s t a r t e d , i n 1325, the development of the theory of p r o j e c t i v e sets ( c f . Lusin 1925 and Sierpinski 1925) b u t soon afterwards t h i s research p r a c t i c a l l y ended due t o the complexity of the problems and the lack of b e t t e r t o o l s t o work with. I t was not u n t i l t h e l a t e s i x t i e s t h a t some new r e s u l t s were ( c f . Fenstad 1971, Moschovakis 1973, and Kechris 1973) using t h e proposed, b u t s t i l l questionable, axiom of Addison and Moskovakis 1968). Recently A. Nerode thought of develop

obtained recently

" P r o j e c t i v e Determinancy"

a l o g i c LA t h a t would b e s u i t -

a b l e f o r t h e study o f t h e a n a l y t i c s e t s , o r p r o j e c t i v e s e t s of level L

WlW

(cf.

was t o Bore1 s e t s . This was done by h i s s t u d e n t P . J . Campbell,

1 , as and

f u r t h e r strengthened in E.Ellentuck 1975 u s i n g d i f f e r e n t methods. This paper follows a sugestion of Eilentuck of t r y i n g t h e g e n e r a l i z a t i o n of t h i s approach t o a l l l e v e l s of the p r o j e c t i v e hierarchy. [ * ) The a u t h o r i s i n d e b t e d t o P r o f e s s o r E l l e n t u c k f o r t o Rutgers U n i v e r s i t y (U.S.A.)

and

support.

20 1

h i s o r i e n t a t i o n , and

CAPES ( B r a z i l ) f o r

their financial

202

R I CARD0 MORAl S

11, PROJEC I V E LOGICS, 0, PRELIM NARI ES s

Let [hey]’ denote’the s e t of a l l n - t u p l e s (uZ, ...,w n ) of f i n i t e s e quences of natural numbers satisfying e ( ~ , )= ... = e ( ~ ~where ) , L(u)denotes the length of u . Throughout t h i s t ex t 6 and g will denote elements of %; n ; m, and k will and f o r The subsets

be natural numbers and u will stand both f o r elements of [neqJn”, elements of ney the s e t of f i n i t e sequences of natural numbers. most important tool developped in t h i s work i s a pair of families of of [hey]’, denoted respectively by FLLeen and F u l l ;

.

D E F I N I T I O N 1 . a) F E F L U , ( F 0 a Fd2l-n b e t ) i d and vney ii F c [neq]’ and F 402%6iu t h e 6aUvwing cvndition giuen by a 4.7XLng 0 6 quant.idiehn

w i t h n aetmnntionn: (3

I

d,)(v dz)*..(Q6,)(Q’k)((d,

I

k,**-,&,

k ) E F)

whme Q and 2’ ahe din-tinct yuanLL&iem. S , i m d ! d y we

b)

dedine

G E F u l l ; (G 0 a F L L e e - v ~ - n Z m n e t ) id and vney i d G c [ n e d n und

(v

61)(362 )-.*(Q’6,)(Qk)((d,

I

k 9 * * * r 6 n

I

k) E GI.

F and G will denote elements of F u l l and F u l l * respectively,and the word countable will always mean e i t h e r f i n i t e or denumerable. Finally, i f @ = {@iI i 8 I ) i s a countable s e t of formulas o f a formal I\ $ . or simply I \ ~ $ ~ language, the conjunction A @ will also be written i e 1 4. i f no confusion a r i s es .

1, THE

LANGUAGE L~~

We s t a r t with a f i r s t order logic L with countably many re la tion, funcbe the infinita rylogtion and constant symbols, and w l variables. Let L W1W

by adi c over L as defined in Keisler 1971, p . 6. We obtaion L from L Pn WIW joining two new operators P, and P; i n the following way: F o m a of L ar e those of L with the addition: i f @ i s amap from Pn W 1W [neq]” i n t o formulas of L then Pn(@) and P i ( @ ) are formulas of L Pn‘ Pn Extend the notion of n u t h 6 a o t i o n by defining:

203

PROJECTIVE LOGIC

i f f ( 1 F € F L L W M ) ( w w € F ) CR C$(w) [ h ]

[h]

(1) CR CP,($)

( 3 G € Full;)( W w € G) d ! = $ ( w )

iff

d bpi(@) I h ]

O c c m e ~ c ao f v a r i a b l e s and c o n s t a n t s i n P a ( @ ) and $(u) f o r

be those i n t h e c o l l e c t i o n o f a l l

w € [neq]'

[h!

P i ( @ ) are .

defined t o

D e f i n e d - w a e i d i t y and w a e i d i t y i n t h e usual way. The n o t i o n o f nub&mnula o f K e i s l e r 1971, p. 11 (2)

= {PM($)j

Sub(P,($))

i s extended by

uw S u b ( $ J ( v ) ) .

u

Uw S u b ( $ ( v ) ) *

S u b ( P ; ( @ ) ) = { P l ( @ ) }IJ

Extend t h e n o t i o n o f t,iouing Rhe c z e g d o a i n ~ i d e(cf. K e i s l e r 1971, p.11) as f o l l o w s : (3)

where

(P,[email protected])) 1

is

Pi(%)

(Pi($))1

is

P,([email protected])

I

l$ i s t h e map t h a t takes w i n t o

Axivmn o f L

P"

l$(w).

w i l l c o n s i s t o f t h e n i n e axioms f o r p r o p o s i t i o n a l

as p r e s e n t e d i n B e l l and Slomson 1969, p . 36, p l u s t h e s i x axioms f o r as i n K e i s l e r 1971, p. 15.

logic

Lwlw

The Rda ad [email protected] w i l l be (Rl)

Modus Ponens

(R2)

i f I-$

(R3)

i f f o r every

$ S @ t- J, +I$

(R4)

i f f o r every

F € FullM

(R5)

i f f o r every

G

P;($)

Vx$

t h e n + $+

+$



I-

if

x i s not free i n

t h e n I-$

AF$(w) + $

Full; I- J, + VG$(w)

+

$J

.

AQ.

I - P n ( $ ) + VJ.

then then

I- $ +

P,*($).

ble o n l y have t o w o r r y about i n t r o d u c i n g P,($) because t h e f a c t s a r e e a s i l y g o t t e n f r o m those about P,($) u s i n g t h e f o l l o w i n g

tance o f t h e axiom + $ 1

PROPOSITION 2 .

w

I-Pi(l$)

H

1 $

.

Now b e f o r e we proceed w i t h t h e s t u d i e s o f L

b.tatemk?VLt

abvut w

me Rnue meta

-

ins-

lP,($)

p o r t a n t p r o p e r t i e s o f t h e f a m i l i e s FuUM and

P R O P O S I T I O N 3.

about

l e t us c o l l e c t some

Pn FILee;

.

in-

Suppane t h a t dvti ewmy W E [ n e q ] ' , x(v) o a m e t a l& Q and Q' be bn in U e 6 i n i t i o n I . Then t h e ~vUviu&g

.

htatemenb.

204

RICARDO N O R A I S

a) ( 3 61)...(2dn)(2'k)A(d1

I

k,...,6n

b) ( V ~ , ) . . . ( 2 ' l i , , ) ( 2 k ) A ( d l I k , . . . , c) ( 3 F E F u U n ) ( W v E

F)A(w)

I

k)

dn 1 k )

id6

4 5 6 (3 F i d 6 (36

Ffin)(Vv

E Fuu;)(Wv

E F)A(v) 8

G)X(u)

( W G E Full;) ( 3 w E G ) A(") ( 3 G E FuU;)

d) ( W F E F u l l n ) ( 3 u E F ) A ( u )

E

(Ww 8 G)A(w)

I t i s important here t o note the complete symmetry between t h e s e two f a m i l i e s of sets. I t i s tnis symmetry t h a t w i l l make possible the majority of our proofs, besides e l e g a n t l y reducing a l l the work i n h a l f . we Now, in order t o b e t t e r understand the behavior of t h e s e f a m i l i e s , have:

PROPOSITION 4 .

16

IT

> 1,

and H c : s e q ] "

E

= { ( " p . . . , " , )I

(5 I

[(",),

, Let

"2,..*>"11)

E

HI.

Then

a) H E F u U n

.id6

(36) (Hd E

b) H E Full;

.id6

( v 6 ) (HS

Fa;-,)

E FLLeeYl-,)

F i n a l l y the next proposition shows t h a t the f a m i l i e s F u l l M and n.

a r e well mixed t o g e t h e r . The proof i s by induction on

2,THE CONSISTENCY PROPERTY

F&f;

I

Let C be a countable s e t of constant symbols not appearing i n L . Let c E C t o L , and from bl c o n s t r u c t t h e l o g i c M PM A banic tm i s e i t h e r a constant symbol of bl o r a term of the form P" function d(t t k )where R L,...,t k a r e b a s i c terms and 6 i s a k - a r y symbol o f L . but The d e f i n i t i o n t h a t follows was taken from Keisler 1971, , p . 11, clauses here, besides adapting i t t o the present s i t u a t i o n (namely adding C9 and C9) we a l s o modified, t o simplify the proofs, the notion o f b a s i c bl be t h e f i r s t order l o g i c obtained by adding each

.

,,...,

teroi, and clauses C10 and C11.

DEFINITION 6. n e s:

A CoiuDtency PhUpULty D a be* S batin6y.ing

doh

each

205

PROJECTIVE L O G I C

to

The d e f i n i t i o n o f Consistency P r o p e r t y i s t h i s l o n g because we want have:

THEOREM 7 . and

40 E S ,

PROOF:

(Model E x i s t e n c e Theorem). 16 S 0 a C a ~ n O t e n c y P h u p e h t g

then

Without

han a modet.

40

l o s s o f g e n e r a l i t y we way assume t h a t each subset o f an e l -

elllent o f S i s a g a i n i n S . To c o n s t r u c t t h e model s a t i s f y i n g w i t h t h e s m a l l e s t s e t Y o f f o r m u l a s o f E.4

(i)

no

(ii) Y

Let and

T =

f o r which:

i s c l o s e d under subformulas.

(iv) i f [email protected] E Y If

c E C

then

a b a s i c term and

1

@(t)E Y then I$(t') E Y

c = t E Y.

be t h e c o u n t a b l y i n f i n i t e s e t o f sentences o f Y ,

{to,tl, . . . I be t h e s e t o f b a s i c terms. S t a r t i n g w i t h

h0

construct

an i n c r e a s i n q sequence o f elements o f S as f o l l o w s . Suppose we have 4nl+l

4,,, :

.

$1 8 Y .

and R i s a b a s i c t e r m t h e n

X = { I $ o , I$,,...

and we b u i l d

start

Y

(iii) I f t i s a t e r m , t '

(v)

Pn

oo we

h,,,,

R I CARD0 MORA I S

206 (1)

i f A,, U

{@,,,Ig

(2)

i f sm U

{a,}

=

A;+,

;

i s [email protected] then f o r some $ E @,

(2.1)

$ ,,

(2.2)

$m i s 3 x $ then f o r some c E C, A;+,

(2.3)

@m

(2.4)

i s P,($)

IAF$(v)}

U

{$,,,I

U {[email protected](v)}

f i n a l l y , s i n c e i n any case Am+,

Next d e f i n e

e sw

c = d

L e t [c]

u

= A;+,

sw

=

.

{c =

um sm

fml

&A+,

s+ ;,

=

E

S,

=

o;+~

=

sm u {$,,,I E S; t h e r e i s c E C such t h a t

8 S,

E S.

and d e f i n e an equivalence r e l a t i o n on C by: c+d

c E C and l e t A =

be the equivalence c l a s s o f

Now f o r each k - a r y r e l a t i o n symbol P,

6,

l

sm u {$m}U { $ ( c ) }ES,

G E F a ; ,

This i s the universe o f the model t h a t w i l l satisf.y symbol

@

E S,

i s any o t h e r formula,

$,

=

E S,

i s P i ( @ ) then f o r some

$,

(2.5)

U

u {$mlu I

= A,,,

F E FU.ee,,s;+,

then f o r some

u {@,,,I

= A,,

(3)

sm

we consider t h e f o l l o h i n g cases:

E S

= A,,

iff

let

S

o f L define a r e l a t i o n

so

I [c] i

.

o f L and each k - a r y

c E C}.

function

Rm on Ah and a f u n c t i o n F,, from

Ak

i n t o A by:

(a) (b)

,..., r e k ] ) E Rm Fm( [c,] ,. ..,[ch]) = [c,] ( [c,]

Note now t h a t i f is [email protected],

@ E 6,

then

iff

Pm(cl

,..., c),

iff

co =

b,,,(c,,

E

...,ck)

E

.

and

0 E Y

f o r each

(a)

@

(b)

@ i s any o t h e r formula, then

8 E @ ;

$ E Y.

Then use t h i s f a c t t o show t h a t the s t r u c t u r e

a satisfies

=
so

1

m 6 wl, {F,,,

I

m E w}, A >

.

Theorem 7 i s a n i c e t o o l t o use i n the p r o o f o f

THEOREM 8. (The Completeness Theorem f o r

L

)

Pn

16 @ 0 a s e n t e n c e

06

207

LOGIC

PROJECTIVE

To show t h a t e v e r y theorem i s v a l i d we Drove t h a t t h e r u l e s o f i n -

PROOF:

ference (R4) and (R5) p r e s e r v e v a l i d i t y . Rule (R4).

(a)

Suppose

3F E FuU,,

VF

E

F u l l R , 02 t=

U? b [email protected](u) A 1J,

A F @ ( w ) + J, t h e n i t i s n o t

t h e case

.

i m p l i e s t h a t 3 F E FuRe,,

B u t by D e f i n i t i o n 1, Ce CP,(@) and t h e r e f o r e i m p 1 i e s n o t UL C P,($)

A 1$ o r e q u i v a l e n t l y ,

that

U? I = A F $ ( w ) ,

CL c P,($)+$.

Rule (R5).

(b)

d C J, * VG $ ( w ) .Then a!= 1ji o r Suppose VG E F u l l ; , ( 3 u E G ) OZ k = $ ( w ) a n d h e n c e b y P r o p o s i t i o n 3, CR

( W G 8 FLU;) 11) or

U? C J ,* P,($).

( I F E FullR)(W w E F) CE [email protected](v), which i m p l i e s

Now we have t o show t h a t e v e r y v a l i d sentence i s a theorem. I n o r d e r t o do t h a t we l e t S be t h e s e t o f f i n i t e s e t s o f sentences n o f o n l y f i n i t e l y many

c E C

o c c u r i n n and n o t I-

MA.

M

YJn

such t h a t

We t h e n show S i s a Consistency P r o p e r t y and t h e r e s u l t f o l l o w s hence

lip,

t h e n @ i s n o t a theorem i n

cause i f @ i s n o t a theorem i n L

r7M

{ I $ } E S. By t h e Model E x i s t e n c e Theorem @:

beand

has a model and t h e r e -

fore @ i s not valid. We e x e m p l i f y t h e p r o o f t h a t S i s a Consistency P r o p e r t y be p r o v i n g (C8) and (C9). (C8)

Suppose P,($)

Full,

U {A,@(u)}

WF

(WF E F u l l , )

( I- A F @ ( w )

1An); t h e n by (R4)

since

E n,

P,(@)

P,(@)

P,*(@)

Suppose

I-An-,

( I-

S.

I- P,(@)

+

1A 0

and,

lAn, a contradiction.

E n b u t ( V G E FLU;)

I- l A ( n u { A , @ ( w ) } ) ( W G 6 FILL$)

I-

+

E

e

I- lA(n U { A F @ ( u ) } ) , and so

E n, we have

Since

(C9)

n b u t (WF E FuU,)(n

E

f o r every

(n U { A G @ ( u ) }g S ) ; t h e n again

G E Full;

and

so

An + V G l @ ( w ) ) , which i m p l i e s , by (R5),

P,([email protected]).

Therefore, by P r o p o s i t i o n 2, a contradiction.

I-

An + l P i ( @ ) o r , e q u i v a l e n t l y , I- l h n ,

206

R I CARDO MORA I C

There i s another p r o j e c t i v e l o g i c of i n t e r e s t t o us, namely: DEFINITION 9 . h ~ n bowm w,

The logic L

P

0 dedined t o be t h e u n i o n oh & L

o h i n othetr ~0oh.d~:

(a)

ln L

(b)

The &en

UA

n

Pn($) 0 a domda doh ewmy n .

P '

06

(R4)

(Vn E

(R5)

( i n E w ) id

id

w)

Pa

indmence (R4) and (R5) now head

( W F E FuUn) I- A F $ ( w )+ $

then

I-

(VG E FLU;)

then

I-$+ P,($).

I-$+ [email protected](w)

i s complete s i n c e a l l L are. P Pa There i s one important theorem p a r t i c u l a r t o L

Pn($) + $,

Obviously L

THEOREM 1 0 . (R4')

In L

P

0 a h.u&

t h e @f%LCLing

= 1)

id

V6 I- Ak'$(d

(b) (doh. n > 1)

id

Vd I-

(a) ( d o h n

whehe

$d

(w2,.

..,wn)

= $( 6

:

06 in&?kence: k) --f

I .t(w,),

P

+

$

$

w2,.

then

then

I-

+

PI(@) + $ ;

pn($)+

n-

;

.., w n ) .

We conclude this s e c t i o n with the remark t h a t t h e downward Skolem-Tarski theorem holds f o r both L and L P Pn *

111,

$J

Lowenheim-

PROJECTIVEBOOLEAN ALGEBRAS,

1 I NTRODUCTI O N , I

In t h i s s e c t i o n we d e f i n e a new kind o f Boolean a l g e b r a s , c a l l e d n-proj e c t i v e Boolean a l g e b r a s , which a r e g e n e r a l i z a t i o n s of t h e S u s l i n algebras introduced by L . Rieger in 1955 ( c f . Rieger 1955). Our work, however, i s patterned a f t e r a recent paper by E . E l l e n t u c k (Ellentuck 197+) i n which he s t u d i e s the S - a l g e b r a s o f Rieger based on his previous paper on S u s l i n l o g i c (Ellentuck 1975). R i e g e r ' s idea with t h e S u s l i n algebras was t o provide a s t r u c t u r e i n which one could model nn1 a n a l y s i s .

1. BASIC

nt

a n a l y s i s . Our algebras a r e intended t o help model

RESULTS,

Let B be a Boolean algebra.

209

PROJECTIVE LOGIC

The joim and nieeA of B w i l l be denoted r e s p e c t i v e l y by Sup and 7ng. The iizditzite j o i n of t h e family {bi 1 i E I } i s denoted by Sup bi or simply by Sup bi

i

is7

i f i t c l e a r which s e t 7 i s .

I f Q i s a map from [neq!" i n t o 6 we s h a l l use the n o t a t i o n Pit($) f o r the following element of 73, provided i t e x i s t s : Pi*($)

=

and, s i m i l a r l y ,

SUP

F

Ini( $ ( w ) , wEF

where, a s u s u a l , F runs over The symbols P,(@) and and t h e previously defined confusion.

DEFINITION 1 2 . (W

- PBA

ijoh n h h t )

F u l l n and G over

FU.eek

.

P;($) w i l l be used both f o r t h e above suprema formulas o f Lpn, b u t t h i s should l e a d t o no

A u - B C J C J ~d~ gU e~ b~ t ~ ~ U M w - I 3 4 O j ! L d W t 600tea~d g c b h n id Lt 0 it - PBA dot C V U i ~ i E W.

Formula ( 4 ) i s a very powerful d i s t r i b u t i v e law and not a l l algebras closed under Pit and P i s a t i s f y i t . In f a c t , t h e r e a r e complete B o o l e a n algebras i n which ( 4 ) f a i l s . In our work, however, we need t h i s d i s t r i b u t i v i t y t o t i e t h i n g s up ( s e e f o r example condition ( 6 ) below), and we a r e thus forced t o introduce i t a s p a r t of t h e d e f i n i t i o n . To g e t an example i n which ( 4 ) f s i l s s e e Morais 1976. Another way t o see the importance of ( 4 ) i s t h e next proposition which presents t h r e e e q u i v a l e n t formulations of ( 4 ) .

PROPOSITION 13. 7 6 B 0 c( Bootenti d g e b h a i n t o B , tt,t -I$ be t h e tNnp deijined by (-

whehe - 0 t h e nytnbat eqUiWdent:

604

Q)( w )

=

-$ (w)

c a t i i p L ~ i e n t d L oi ~n ~ B

aid

Q 0 a riiap

. Theit tlze

6hotti

[Aeq]'

60ttCJdt7g

ah&

210

RICARDO

MORAIS

Now, using these equivalences, we can get several properties of projective Boolean Algebras, namely:

PROPOSITION 1 4 . A u - B o o L ~ ~dMg e b h a B 0 n-PBA i6 m d Only i6 d a s e d u n d e h the P i a p e h a t a h and (4) holds. PROPOSITION 1 5 .

16

M > 1

PROPOSITION 17. Evehg

whehe

w

PROPOSITION 1 8 . PROOF:

Now

M-

PBA, then B 0 ( n - 1) - PBA.

an example.

The cornple*e B a o l e a ~d g c b m 2

= {O

,I} 0 w - PBA.

Since 2 i s complete we have just t o show ( 4 ) holds i n 2 .

P,($)

=

0

i f f sup In6 - $ ( w ) . = G uEG

.

B 0

- PBA ~ a t i n 6 i e A :

iotoak-n add

iff

i f f (by Proposition 3 )

holds

M

aMd

8 0

Sup In6 $(u) = 0

F uEF ( 3 G E FuRe;)(Wu

1 iff Pi( - $ ) = 1

i f f (WF E FuRen)(3w E F)(@(u)=O) E

iff

G)($(u) = 0 ) i f f In6 Sup $(u) = O G uEG

- P i ( - $ ) = 0 and therefore (6)

211

PROJECTIVE L O G I C

The most i m p o r t a n t example o f an w - PBA however i s g i v e n by t h e

fol

-

lowing: The Lindenbawl dgebaa L

THEOREM 1 9 . w

- PBA.

PROOF:

Let

1

@

I

06

P

,the w - pfihujedue Logic

LP

denote t h e e q u i v a l e n c e c l a s s o f t h e f o r m u l a @ i n L

P

.

i n t o L and d e f i n e a map $J from [bey]" P by choosing f o r each W E [hey]' a r e p r e s e n t a t i v e f o r -

L e t @ be a map f r o m [hey]" i n t o f o r m u l a s of L

P

mula @(u) o f t h e e q u i v a l e n c e c l a s s

(8)

P,(@) = !pn(@)l and hence

T,

We t h e n show

(li(w).

,

F i r s t we have t o p r o v e t h a t t h e f o r m u l a choice o f t h e map

Pn o p e r a t o r .

i s c l o s e d under t h e

P

Pn(@) does n o t depend on t h e

@.

I t s enough t o show t h a t f o r any o t h e r map

'Ju E [ ~ e y ] " I- @ ( w )

+

$(u) t h e n

I-

JJ

:

if

Pyz(@)+ P , ( ~ J ) .

By (R4) t h i s f o l l o w s f r o m (9)

VF E F a n I-

[email protected](u)

+

pn($)9

which i n t u r n f o l l o w s from, (WG E F u R e V : ) ( V F E

Fan)

(by R5), I-

[email protected](w)

+

VG$(u).

B u t t h i s i s t r i v i a l s i n c e by P r o p o s i t i o n 5, g i v e n any F and G , F n G # @ . T h e r e f o r e (9) h o l d s . Now t o f i n i s h t h e proof of Theorem 19 we have t o show t h a t t h e d i s t r i b u t i v e law (4) holds i n L

P'

We s h a l l need,

(10) P i ( @ ) = I P p 4 which i s e q u i v a l e n t t o ,

S U P I AG @ ( u ) I = I P i ( $ J ) I G and so we have t o prove: (i) ( W G E F f i i )

I

I- h G @ ( V )+

Pi(@)

and

(ii) I f (WG E Fufl;)

I- h G $ J ( u + )

11 t h e n

I-

P i ( @ )+ $

.

212

RICARDO MORAIS

PROOF of (i):

From p r o p o s i t i o n 5 g e t

(WG E FU.eei) (WF E F d n )

+

AF l$(v)

+

VG l $ ( v )

now a p p l y (R4) and use P r o p o s i t i o n 2. S t a r t w i t h the hypothesis

PROOF of ( i i ): (WG € FULL;)

I-

1

$J

+ VG 1 $(v),

t h e n a p p l y (R5), and use P r o p o s i t i o n 2. F i n a l l y ( 8

,

(10) and P r o p o s i t i o n 2

give

Pn(@)

=

-

P,*(

- 0)

and t h e r e f o r e ( 6 ) h o l d s , which i s e q u i v a l e n t t o ( 4 NOTE: L

PM

E v i d e n t l y e x a c t l y t h e same p r o o f shows t h a t t h e Lindenbaum a l g e b r a of

(denoted L

PM

) i s n - PBA.

3, FREE n - PROJECTIVE BOOLEAN ALGEBRAS, DEFINITION 2 0 .

An nP

-

BooLean d g e b t a 0 a a - ho-

Izornornotpkm b-een

momohpkinm t h a t pk,hedmve~t h e Pn opehatoh. An W P - homomotpkinm 0 a u - honiomohpkintn

&at p u e h v e n Pn d o t evehy n

DEFINITION 2 1 .

L e t B be m

- genehaten B i d

(a)

G nP

(b)

G dheely

E w.

n - PBA and G

c

B. Tken:

B 0 t h e nm&ent

n - PBA containing G

.

nP- genmaten B i d G nP-genehaten B UJ~C! in a d d i t i o n given m y o t h m n - PBA B' and m y map h : G + B' t h e h e i b an nP - homomohpkidm H : E + B' w h i c h extend6 h

.

- net

06

gen -

An n - PBA 0 a dhee nP- d g e b h a i d contaia n P - n e t ad g e n ma to a . S . i m . 2 d y , dedine a 6hee ~ P - u Q e b h a .

a

dhee

(c)

S .in i. 2 dy dedine W P - neA 06 genehatom and 6hee

WP

ehato4,5.

DEFINITION 2 2 .

I f i s a common p r a c t i c e . i n any t e x t about " f r e e " s t r u c t u r e s t o

first

t a l k about i t s uniqueness and a f t e r w a r d s t o prove i t s e x i s t e n c e .

The

l o w i n g two p r o p o s i t i o n s a r e proven i n t h e same way i t i s u s u a l l y

done f o r

general Boolean a l g e b r a s . See f o r example Halmos 1963, p. 42.

fol-

213

PROJECTIVE L O G I C

PROPOSITION 23. 76 B 0 u dhee n P - d g e b h u , G t h e he,t 06 6hee nP-genefu7Xoh.S and h .the given map 6honi G into .the n - PBA B',then t h e nP - hamomahpkinm H : B + B' t h a t extendh h 0 unique. PROPOSITION 24. Any &oo 6hee n P - d g e b h a whohe .the hame catr&&y atre nP-0oma5pkic.

h d

0 6 genmatom

have

Now t o p r e s e n t an example o f a f r e e U P - a l g e b r a ( t h e e x i s t e n c e o f a f r e e n P - a l g e b r a i s proved s i m i l a r l y ) we proceed as f o l l o w s . F i r s t d e f i n e a phOpOh.iJ%onCdl o g i c LK f o r each c a r d i n a l

K

and t h e n

show t h a t t h e Lindenbaum a l g e b r a L~ o f LK i s a f r e e U P - a l g e b r a

we

with

K

generators. LK i s g o i n g t o have a s e t o f

{Pa j

c1

< Kl

K

variables

,

and t h e p r o p o s i t i o n a l c o n n e c t i v e s 1 and A o p e r a t o r s P,? and P;

. As

in L

PM '

we i n t r o d u c e

and l e t t h e s e t o f f o r m u l a s be t h e l e a s t s e t such t h a t

.

(a)

pa

(b)

if @

(c)

i f 0 i s a c o u n t a b l e s e t o f f o r m u l a s t h e n A @ i s a formula.

(a)

i s a f o r m u l a f o r each o r d i n a l

c1

<

K

i s a f o r m u l a t h e n so i s l @

i f @ i s a map from

[heq]' i n t o f o r m u l a s t h e n P,(@) and Pi(@) a r e

formulas ( f o r every

n E w).

Define "riaving t h e negation h i d e " f o r formulas o f LK as we d i d

LPn

the

for

with the addition:

For axioms t a k e t h e n i n e axioms o f p r o p o s i t i o n a l l o g i c as i n B e l l and I- @l*[email protected] and I- A @ + @, where @ i s a c o u n t a b l e

Slomson 1969, p. 36, p l u s s e t o f f o r m u l a s and @ 8

@.

For r u l e s o f i n f e r e n c e t a k e those o f L p n w i t h t h e e x c e p t i o n o f (R2). A r e a l i z a t i o n o f LK i s a map 2 =

6

f r o m t h e s e t o f v a r i a b l e s i n t o t h e w-PBA

{ o , 1 1 , which i s i n d u c t i v e l y extended t o a l l f o r m u l a s as f o l l o w s :

(4 d([email protected])

=

- 6(@),

(b)

d ( A 0 ) = In6 d ( @ ) ,

(c)

6 ( P n ( @ ) ) = P n ( 6 ( @ ) ) and

$80

b(P;(@))

= P;(d(@))(

214

RICARDO M O R A I S

6(@) i s

where

the map defined by

6($)(u)

=

6 ( @ ( u ) ) for u

€ [neq]"

. 6.

We say t h a t a formula @ i s valid i f d ( @ ) = 1 in a l l realizations Now, before we prove t h a t LK i s an UP-algebra on K generators, need: 8 be an w P - d g e b h a and

PROPOSITION 2 5 . L e t ablu

06

LK & t o

B . EXtend

6

.to a l l d

o

6

we

any map dhom .the u a h i

m by~ trdu (a) X h h o u q h

-

(c).

Then

imfiu

I-dl

A($)

= 1.

In pa)Lticdah, by PhopohLi5on 18, eue-hy theohem oh LK 0 v a l i d . F i r s t note t h a t because of properties (a) and ( b )

PROOF:

(11)

d ( @ + $)

= 1

i f and only i f

d satisfies:

d(@) 5 6 ( $ ) .

I t i s routine t o show t h a t the axioms are mapped into 1 , b u t we check, as an example, t h a t the axiom $1 [email protected] i s mapped i n t o 1 f o r the case @ i s Pn($). By (11) we have t o show, B(PYl(VJ)1 ) = 6 ( 1 P n ( $ ) )

.

But 6(Pn($)1 1 = P;(

-6($))

6 ( P,*(l$))

= -Pn(6($)) =

= p;(6(1$)

-

=

6(Pn($)) = 6 ( 1 P n ( $ ) ) *

where the fourth equality follows from ( 6 ) . Similarly, using ( 1 1 ) i t i s easy t o prove t h a t the rules of inference preserve the property of being mapped into 1 . As an example we check f o r (R4). Suppose W F € FU.een,

6 ( h F @ ( u *) $ ) = 1

and

we

have

to

show

d ( P n ( @ ) * IrJ) = 1 Sy (11) and property ( b ) we have ( V F E F a Y l ) In6 Therefore

UEF

b(@(U))

5

A($)

*

d(@(u)) 5 d($). F u€F B u t by definition t h i s i s P n ( 6 ( $ ) ) 5 6 ( $ ) , and hence 6 ( P n ( @ ) )5 ~ ( J J ) T h u s by ( 1 1 ) , 6 ( P n ( @ ) * $1 = 1 . We therefore conclude t h a t every theorem of LK i s mapped into 1. SUP ,In6

.

PROJECTIVE L O G I C

215

We a r e now i n o o s i t i o n t o show THEOREM 2 6 .

LK 0 a

64ee wP - d g e b t u an exac.tQ

K

genmcLtau.

F i r s t i t i s c l e a r t h a t t h e same p r o o f used t o show t h a t

PROOF:

L

w-PBA (Theorem 19) can be r e p e a t e d h e r e t o show LK i s w-PBA. Next l e t G = { ! p a l la gebra B t o g e t h e r w i t h a map

h : G + B.

6

=

~ ( u J , )

6

and l e t t h e r e be g i v e n an a r b i t r a r y wP-al-

K)

Now u s i n g h d e f i n e a nap

and e x t e n d

f r o m t h e v a r i a b l e s o f LK i n t o B by

h ( / p a1

ly

i n d u c t i v e l y t o a l l f o r m u l a s o f LK

.

By P r o p o s i t i o n 25 and (11) i t i s easy t o show t h a t every equivalence class

was

P

I @ 1 , and

is c o n s t a n t

so t h e f o l l o w i n g i s a w e l l

in

defined

map

f r o m LK i n t o 8 :

H([email protected] This

I1

d(@).

=

H i s t h e d e s i r e d U P - homomorphism e x t e n d i n g h , and hence i t o n l y

remains t o show t h a t t h e c a r d i n a l i t y o f G i s given

a ,B <

K

with a # 6

i s n o t a theorem and hence

4, A

,

K

.

But t h i s i s e a s y ,

P r o p o s i t i o n 25 can h e l p t o show t h a t pa

I pa I

#

for H

I pB 1 .

REPRESENTATION THEOREM FOR FREE nP-BOOLEAN ALGEBRAS

pB

I

We s t a r t t h i s s e c t i o n w i t h a completeness theorem f o r L K . T h i s i s done t h e same way we d i d f o r L

Pn

and so we o m i t t h e p r o o f , a l t h o u g h we p o i n t o u t

t h e b a s i c p o i n t s . F i r s t we d e f i n e :

216

RICARDO M O R A I S

ththetle

1 5 S 0 a K - CoMnOtency P h O p M y and oo E S t h e n a h e ~ z c L t i o n 6 0 6 LK doh rukich d ( $ ) = 1 doh & @ E no

PROOF:

T h i s p r o o f i s p a t t e r n e d a f t e r t h e one f o r t h e Model E x i s t e n c e The-

PROPOSITION 2 8 .

.

orem (Theorem 7 ) . We s t a r t no and c o n s t r u c t a sequence (A,) o f S w i t h t h e d e s i r e d c l o s u r e p r o p e r t i e s . Then l e t map f r o m t h e v a r i a b l e s o f LK

d(PJ

d

Then e x t e n d quence (A,)

no =

i n t o 2 by

iff

= 1

o f elements o f

u nm

m

and d e f i n e a

Pa e

i n d u c t i v e l y t o a l l f o r m u l a s and because o f t h e way t h e

se-

was c o n s t r u c t e d we have

A($)

= 1

+ E nu .

for all

F i n a l l y , we have :

PROPOSITION 2 9 .

16 $ 0 not a

6(@) 0.

theatem 06 LK then doh

bOMe

tluLizaLLon,

J u s t l i k e we d i d f o r 1 we show t h a t t h e s e t o f a l l f i n i t e s e t s Pfl o f f o r m u l a s o f LK f o r which n o t I-1 h b i s a K - Consistency Property.Then

PROOF:

use P r o p o s i t i o n 28 t o g e t t h e r e s u l t .

An n P - d i d d 0 6 A& 0 a 0 - 6 i & l 06 A & 16 a 0- d i d d 06 b& 0 cloned undm Pn w e c a t t it an w P - 6ieLd 0 6 ~ t . t b .

DEFINITION 30.

cloned u n -

dm t h e opetlatoh Pn.

doh

n 8 o

Notice

evmy

t h a t we d i d n o t m e n t i o n any d i s t r i b u t i v e l a w here. T h i s however

i s no s u r p r i s e because we have:

PROPOSITION 31. Eumy nP THEOREM 3 2 .

- @Ld 06

n&

0 n - PBA.

(heSpecFOX each cahd+u?l K t h m e 0 an nP - 6.ietd 06 A & 06 b d ) that 0 n P - g e n m d e d [ ~ P - g e n e h a t e d ) by K 06

L L v d y U P - d.ieXd ia%

dements.

PROOF:

Let

X = ZK be t h e s e t o f maps f r o m

K

into

2 =

l o , 11 and d e f i n e

PROJECTIVE L O G I C

a <

f o r each

Next, l e t let

BKn

taining

217

K

Q

9, =

r6 e

= {g,

I

(respectively

ZK

I 6(.)

=

11

a<

K}

BK)

be t h e s m a l l e s t n P - a l g e b r a ( U P - a l g e b r a ) con-

which i s a s u b s e t o f t h e power s e t o f X,and

2. BKM and BK a r e

Since t h e power s e t o f X i s a complete f i e l d o f s e t s , well defined.

Q i s K t a k e a # B and choose 6 ( a ) # tj(0). Hence i f , say, d ( a ) = 1 t h e n 6 E g,

F i n a l l y , t o show t h a t t h e c a r d i n a l i t y o f any map but

6B

6 E

2K

gB,

f o r which and t h e r e f o r e

g,

'go.

Now copying what we d i d f o r LK we c o n s t r u c t a p r o p o s i t i o n a l l o g i c LKn f o r each n E w i n such a way t h a t t h e i r c o r r e s p o n d i n g Lindenbaum algebras

LKn a r e f r e e n P - a l g e b r a s .

Our r e p r e s e n t a t i o n theorem f o r

M P - a l g e b r a s i s an immediate consequence

o f the next very importdnt proposition.

PROPOSITION 3 3 . ~ ~ P - i A o m o t ~ p kt ioc BK L~ 0 iA MP - iAomohipkic t o BKn. PROOF:

; and 6 o t ~e v w y

We p r o v e o n l y t h a t L~ i s WP - isomorphic t o BK

The w P - i s o m o r p h i s m H : L~

--f

n E w, LKn

.

BK we a r e l o o k i n g f o r i s d e f i n e d i n d u c -

t i v e l y by: (a)

For every o r d i n a l

(b)

H ( I [email protected] 1 ) = H (

(c)

H(!AQl) =

(a

I

fl

@

c1 < K , H ( I I ) ' , where A'

p a / ) = 9., denotes t h e complement o f A .

H([email protected]:).

@ [email protected]

H(IPI1(@)l) =

uF v EnF

H([email protected](U)I).

T h i s d e f i n i t i o n makes H an U P - homomorphism, and we have t o show i t i s o n e - t o - o n e and o n t o . of

To show H i s o n e - t o - o n e we d e f i n e f o r each LK by

d'(P,) ( o f course e x t e n d i n g

6'

=

6

E ZK a r e a l i z a t i o n

6'

5(.)

i n d u c t i v e l y t o a l l formulas).

Next, by i n d u c t i o n on t h e c o m p l e x i t y o f @,we show

H([email protected]) = { 6 € ZK1f(@)=1).

218

R I C A R 0 0 MORA I S.

F i n a l l y , we have t o prove t h a t i f H( t h e 1 o f LK But i f

.

H( 101 ) =

2K t h e n f o r e v e r y

e v e r y r e a l i z a t i o n o f L, t i o n 29, and hence

]@I

satisfies

101) i s t h e

6

€ 2K

1 of

, 6' (0) =

@ T. h e r e f o r e

.

BK

then

1 $1

1 which means

is that

0 i s a theorem b y Proposi-

i s t h e 1 o f LK L a s t l y , s i n c e t h e image o f L , under H i s an U P - a l g e b r a which c o n t a i n s

2 , the U P - s e t o f generators o f

BK

,

Now g i v e n any U P - a l g e b r a 8 , l e t

we have t h a t H i s onto. K

be t h e c a r d i n a l i t y o f t h e s e t 8 .

Since LK i s a f r e e U P - a l g e b r a we can g e t an wP- homomorphism f r o m L, o n t o

B. Therefore the previons p r o p o s i t i o n gives: THEOREM 3 4 . (a)

(The R e p r e s e n t a t i o n Theorem f o r P r o j e c t i v e A l g e b r a s ) .

Any nP - dyebha h an nP - homomohpkic h a y e

n&. (b)

Any P - dgebha 0 an

UP - kotnomohphic

huge

06 an nP - 5 i e L d

06

an UP - 6 i e L d

o6

06

beh.

IV, CONCLUSION, Our r e p r e s e n t a t i o n theorem f o r f r e e p r o j e c t i v e Boolean a l g e b r a s p r o v i d e d US

w i t h a " b r i d g e " f r o m l o g i c t o s e t t h e o r y , b u t so f a r n o t h i n g was s p e c i

f i c a l l y shown so as t o g i v e a r e l a t i o n s h i p between t h e p r o j e c t i v e f i e l d

-

of

s e t s and t h e p r o j e c t i v e s e t s o f L u s i n and S i e r p i n s k i . Our t e r m i n o l o g y t h e r e f o r e l a c k s some j u s t i f i c a t i o n , which i s however g i v e n b y t h e f o l l o w i n g

and

l a s t theorem: THEOREM 3 5 .

Foh n > 0 ,

1

.i~ an n - phojeotiwe 6 i e l d

06 b&,

whehe

A,

6Zand6 doh "boLd6ace A". PROOF:

( f o r a d e t a i l e d p r o o f p l e a s e see M o r a i s 1976).

We w i l l show t h a t

i s c l o s e d under t h e Pn,

b u t t h i s i s not enough,

however, t o p r o v e t h a t . i t i s n - p r o j e c t i v e because t h e d e f i n i t i o n n - p r o j e c t i v e algebra s t a r t s w i t h a o - a l g e b r a .

B u t i t i s easy t o see

t h e same argument used below can be r e p e a t e d t o show t h a t L I ~ + ~i s

o f an that closed

under t h e P1 o p e r a t o r , and t h i s i n t u r n i s a g e n e r a l i z a t i o n o f c o u n t a b l e

219

PROJECTIVE L O G I C

unions and i n t e r s e c t i o n s ( c f . Kuratowski and Mostowski 1968, p. 341). L e t now @ be any map f r o m

x

E

1

i n t o Qn+l,

[AQQ;'

1

P,($) can be g i v e n b o t h by a Jn+l and a By P r o p o s i t i o n 3

x

P,($)

E

JA+l

a n d we

show

that

predicate.

has two e q u i v a l e n t f o r m u l a t i o n s , namely:

(a)

( 3 F E F U . e e n ) ( W w E F)(x E $ ( w ) )

(b)

(WG E FU.eei)(3v E G ) ( x E @ ( w ) ) .

and

We a r e g o i n g t o use (a) ( r e s p e c t i v e l y (b)) t o show t h a t g i v e n by a

+

F i r s t , since w onto

i s countable, there i s a

[bey]"

F and

s t i t u t e the sets

1- 1 r e c u r s i v e map

by means o f X

{O

G by t h e i r r e s p e c t i v e

tw

E [bey]"

, 1 1 , and as we d i d f o r

I g(w)

= 1) E

The e x p r e s s i o n range

(Wm

.

I n addition,

= 0

{ w 8 [neq]'

ik

.

)'i+lp r e d i c a t e .

@(k) E

[(tlange g

=

{O, 11

.

g(n1) = 1).

otl

I g(w)

= 1) E

1 4n+1 c $ + ~f o r

T h e r e f o r e i f we w r i t e W1 and

sub-

11 i s w r i t t e n Fulln

( ~ 6 1 ) ( ~ 5 * ) " ' ( Q 6 , ) ~ Q ' ~ ) ( 9 ( 6 1 1 m* ,* .

F i n a l l y since

we

we t h i n k t h e domain o f g as w .

@

F a n and g ( k ) = 1) + x E @ ( k ) ]

g = {O,

E w)(g(m)

The e x p r e s s i o n

which i s

X from

c h a r a c t e r i s t i c functions

T h e r e f o r e (a) i s e q u i v a l e n t t o ( 3 9 E "u) (Wk E w )

and

is

P,*($)

E

and so we can t h i n k t h a t t h e domain o f $ i s w . L e t _v be t h e

[bey:"

i n t e g e r a s s o c i a t e d w i t h w C [beq]" g : [hey;"+

x

1 ( r e s p e c t i v e l y iln+l)p r e d i c a t e .

1

i s equivalent t o

A,i)4

= 1)

a l l k we can make

x

E $(k)

a

31 f o r q u a n t i f i c a t i o n o v e r r e a l s and WO

and 30 f o r q u a n t i f i c a t i o n o v e r numbers, t h e statement ( a ) now reads:

31 WO [ ( W O A,31

... "

Q1 Q'O) j L 3 1

- Kuratowski

we s i m p l i f y t h e above t o 31 3 1 VO [ ( A

...

v n+1

) +

v

Q'l,QO]

.

n+1

n Then u s i n g t h e T a r s k i

...

a l g o r i t h m s ( c f . Rogers 1967,

1

p.

307)

R I CARD0 NORA I S

220

which i s a

zi+l predicate.

Now using (b), since

G €

FuRel

is

we, s t a r t w i t h

[

W130

... 2'1 20) +

(WOA W 1

u n

and end up w i t h a $+1

predicate.

JLi and s i n c e @ ( k )

V1

E

1 4n+l

1

... 21 2 ' 0 1

n+ 1

came

I t i s c l e a r by now t h a t one o f t h e most i n t e r e s t i n g notions t h a t

up along t h i s work was t h a t o f

Full;

and i t s counterpart FLLeen

symmetry between these two classes o f

. The

,

c ;n+l

generalizing Ellentuck's F u l l s e t s , sets

n o t o n l y helped c u t t i n g a l l our proofs i n h a l f b u t also, and more s i g n i f i c a n t l y , w i t h o u t t h i s symmetry most o f our p r o o f s

-

c o u l d n o t have

come

through, s p e c i a l l y our l a s t theorem i n which the simultaneous use o f

FuUn

FuRe;

and

was fundamental.

For these reasons we foresee an i n c r e a s i n g use o f these n o t i o n s i n

the

f u t u r e s t u d i e s o f p r o j e c t i v e sets.

To conclude t h i s work, among several i n t e r e s t i n g q u e s t i o n s f o r which a l l t h i s machinery i s applicable, we s e l e c t e d two t h a t we are p a r t i c u l a r l y i n t e r e s t e d i n i n v e s t i g a t i n g , namely: (1) (2)

L or L i f any? Pn P ' If. M. i s 3 universe o f s e t s and B i s an n - p r o j e c t i v e Boolean a l gebra, what can be accomplished i n s i d e t h e Boolean valued m o d e l

What k i n d o f i n t e r p o l a t i o n theorem holds i n

MB ?

REFERENCES Addison, J. A. and Y . Moskovakis 1968,

Some comequenca Nat. Acad. Sci.,

06

t h t axiom o d de6&abLe d e L m i n a t e n a s ,

B e l l , J. L. and A. B. Slomson 1969,

Proc.

Vol. 59, 708- 712.

Models and Ultraprqducts, North

- Holland,

Amsterdam.

Ellentuck, E. 1975,

The ~owzdatiom06 S w f i n Logic, The Journal o f symbolic Logic, v o l . 40, 567-575

PROJECTIVE

197+,

22 1

LOGIC

Fhee SwL& d g e b m , S u b m i t t e d t o Czech. Wath. J o u r n a l .

Fenstad, F. 1971,

The a x i a m

0 6 deLetuninateflcbb,

Proceedings o f t h e Second Scandinavian

L o g i c Symposium, Ed., J . E. Fenstad, N o r t h - H o l l a n d , Amsterdam,41-61. Halmos, P. 1963,

Lectures on Boolean Algebras, Van Nostrand K e i n h o l d Company, London.

Kechris, A. 1973,

i'leubwre and categohy i n eddeotiwe denchipLLwe

bet

theahy, Annals

of

Math. L o g i c , V o l . 5, 3 3 7 - 384. K e i s l e r , H. J. 1971,

Model Theory for Infinitary Logic, N o r t h - H o l l a n d , Amsterdam.

Kuratowski, K. and A. Mostowski 1968,

Set Theory, N o r t h - H o l l a n d , Amsterdam.

L u s i n , N. 1925,

S w l Lcb emembLcn p o j e o t i w e h de M. H e i d Lebcngue, C. R. Acad.

Sci.

de P a r i s . Morais, R. 1976,

Projective Logic, Ph. D. T h e s i s , Eutgers U n i v e r s i t y , U.S.A.

Moschovakis, 1970,

Y.

DeLmtirzaflcy und

pmLJ&Otld&Mgb

ad t h e co~dizuum,in Mathematical

Logic and Foundations of Set Theory, E d . Y . B a r - H i l l e l , H o l l a n d , Amsterdm, 24 - 62.

North-

Rieger, L . 1955,

Cancmning Suofin d g e b m (S - k e g e b m ) and t l z e i n (Russian), Czech. I l a t h . J o u r n a l , Vol. 5. 99

htphtbtntathion

- 142.

Rogers, H. 1967,

Theory of Recursive Functions and Effective Computability, MacGraw H i 11. Sierpinski, W. 1925, S w l une &abbe d'emembLcb, Fund. Math. Vol. 7, 2 3 7 - 2 4 3 .

-

l n s t i t u t o de Matematica U n i v e r s i d a d e F e d e r a l do R i o de J a n e i r o R i o de J a n e i r o , RJ.,

Brazil