Mathematical Logic in Latin America: Symposium Proceedings

I

a. )}.

and its semantics are defined similarly, allowing

infinitary conjunctions. The quantifier rank of a formula of this language is the ordinal defined inductively by: qr (q, )

=

0,

if

q,

is a tomi c

qr (--, q,) = qr (q,) qr (1\ e) = sup {qr ( q, ) 1 q, E

(J }

qr (3 x
(0.. j xl"'"

where Let

~

then

x11. (4)1'''''

l' ... , nk ) is the type of 0.. j'

(n

be an ordinal, or the symbol

L:

w (Q.j')

'E] j

q, 11.)) = m1 x qr (q, -i ) + max n , , -i -<-

considered greater than all the ordinals,

~

consists of the formulas of rank less than ~. Two quantifier '"

~ -elementarily equivalent, ta , Qj)jE] == (~; tr.j)jE]' i f they satisfy the same sentences of this language. The proof of the following lemmas is similar to that of Lemma 3.2.1 in Caicedo 1978. structures are

LEMMA 1.1

I6.the numbetr. 06 tr.e1.a.ti.on, 6u.nc.:Uon,

COIl.6.tant,

a.nd

Qu.a.n~-iMetr.

.6yrnboL6 M MnUe, ~hen L~w(Q.j) jE] -l.6 eQu.-lvalent to Lww(Q.j) jE]" Motr.eovetr., 6otr. each MnUe nand k thetr.e -l.6 a MnUe numbetr. 06 non-eQu.-lva.fen.t 6O!tmula.6 06 Qu.a.nU6.(etr. tr.a.nk equ.a.f.to n w.Uh ~ mO!.>~ R va.tr.-<:a.bfu.

LEMMA 1.2 L ~w (Q.j)j E ]

G-iven

ta.,

Qj)jE]' thetr.e-l.6 ~mO.6t

a.6et 06

6otr.mu.fa.6 06

wh-lch Me 1l0n-eQu.-lva.fent -in th-l.6 .6.ttr.uc.tu.tr.e.

A

A Und.6.ttr.om-Mo.6tow.6U Qu.a.nU6.(etr. 06 type (n l' ... , n k) is a function 0.. which A n m n assigns to each set A a quantifier interpretation Q.(A)c fI(A 1) x .•. x or (A r), with the proper-ty that if 6: A -+ B is a biject1on, then for all (S 1'"'' Sk)'

(Sl,,,,,Sk)EQ.(A)

iff

(6'(Sl), ... ,6'(Sk))EQ.(B).

Itisreadily

seen that

this corresponds to the definition of a quantifier as a c'ass K of structures of the same type, closed under isomorphism (Lindstrom 1966),. by defining

Q(A) = {(Sl"'"

Sk)

I

(A, Sl"'"

A Lindstrom-Mostowski family of quantifiers {Qj L+

of

Sk)

E

I jE]}

K}. defines

an

extension

L0 JW in the sense of Lindstrom 1969 and Barwise 1974 by taking the sen-

86

XAVIER CAICEDO

tences of

Loow(Q.j )jEJ

as the .6tjn.ta.x., and defining for an ordinary structure

if.

a When the quantifier

(a; Qj(A))jEJ 1= 1>.

iff

interpreting the symbol

Qj

the language writing

1>

for

Loow(lJ../)jEJ

L+.

Qj is understood, we will abuse

The existential quantifier is the Lindstrom-Mostowski quantifier

3(A)

defined by the function well know.

=

{S

C

-

A

Is*-

0}.

of type (1 )

The following quantifiers are

CMd£na.t qua.ntiMe.M, type (1), for each ordinal a: Q.a(A) = {S:=.Allsl ;;;. wa}. for each ordinal a and finite 11., the quantifier of Q.~ (A) = {S :=.An 13 I ~A such that In ~S and III;;;. w } . a

Mag~do4-Maiitz qua.nti6~e.M,

type

(11.):

Chang qua.ntiMeJt, type (1) : Q.(A) = {S ~ A I HaJz.t.i.g qua.ntiMeJt, type (1,1): H(A) HenlUn qua.ntiMeJt, type (4) : Hen(A)

lsi = IA\}. {(S, T) I S ~A, T ~A, lsi = ITI}. 4 {S ~ A I 3 6, 9 : A -+ A such that 6Xg ~S}

Note that the logics obtained from these quantifiers do not incl ude those where the meaning of quantifier is not determined by the domain of the structure, like Sgro's topological logic (Sgro 1977). However, if we consider only logics for classical structures with a finite number of relations, functions, and constants, then any logic is a sublogic of some Lww(Q.j)jEJ' Even more, if the logic L is closed under substitution of relation symbols for formulas then L is equivalent to some Lww (Q.j ) j E ] '

§

2 BACK-AND-FORTH SYSTEMS,

Through this section (a, q) and (~, 4) will be quantifier structure where q 4 are interpretations for a quantifier symbol of type (11. " " , n ). A and k 1 B are assumed to be disjoint. Sequences in An u s'' (11. E w) wi 11 be denoted

and

a,

a, a', a', T, T ' , h, h'; the value of catenation is denoted by juxtaposition.

11.

will be clear from the context.

Con-

DEFINITION 2.1.- A baek-and-6olLth be;tween (a; q) and (~; 4) consists of a linearly ordered set p = (P, <), called the set ofpa4amete4.6, and a family

{E~

I pEP}

of equivalence relations in

An U

s"

for each

nEw, subject

properties (i) to (iv) below. Before stating the properties, we introduce some convenient notation. will denote

(a, a')

E

E~; the value of

11.

will be clear from the context.

a

to p

a' For

~

each k, It and a E A k , we can restrict the equivalence relation Ek+n to elements of A n in the following way: R, iff a R, a ii' E An). For

a a'

k = 0 and a = 0 we get lence relation.

EP 11.

restrict~d

to

a

An,

a' (a,

Obviously,

R,a

is an equiva-

BACK-AND-FORTH SYSTEMS ..., p

..

ra Ta = Ix

n

A Ia

E

... P

X

'V

a

is the corresponding equivalence class of in ing the language, [X]~ = u {[al~ I EX}.

a

87

.. a a}

An.

If X ~ An we write, abus-

B.

Analogous notation and observations are valid with respect to sequences in PROPERTI ES.

0

(z)

p 'V

0

(Extension property). Let p', then for all sequences a in (-U:)

pf., =

exist functions

n': .{.

n.

A .{.

n.

-+

= max A and

.6

B .{., 1 <;,i

{n T

1 , · •• , n I<} and p < PI <; in B such that a R, T

... < there

< 1<, such that:

• p ~ n· (A) a a 'V T (i(a) for all a E A .{., 1 « t. < L n,i p p (B) If X,[~A ,l<,i
implies

([ n'l (X 1) If , ... , [nrl< (X I<)]~)E ".

A and B. p (,iv) (Isomorphism property). If (a ... , an) 'V (b ... , b then the assign1, 1, n) ment a,it-'>b,i isapartial isomorphism from 01- to&. As (-U:), interchanging the roles of

(.i..u:)

DEFINITION 2.2.(01-; Cij)jEJ

each

jEJ.

(p, {E~I pEP, nEW})

isa

:to ($-;Jr.j}jEJ ifitisonefrom (OI-;Cij) The existence of such a relation is denoted by

baek-and-6oJvth

to

(:6-';"j)

(a;Cij)jEJ~

61tOm

for

()&..;\)jEJ

REMAR K. We assume that any back-and-forth sa ti sfi es the extensi on property for the existential quantifier. It is enough to postulate in (,i,i) , for each p' p a 'V T and p < p' the existence of a function 6: A-+B such that o a. 'V T 6 (a). Property (B) holds automatically. DEFINITION 2.3.- {E I nE w} is a bael<-a.nd-noJt:th wUhou:t pMamUeJt1> 61tOm n ioi, Cij)jEJ to ($-; "j )jE] if En is an equivalence relation in An U Bn for each n , and properties (,i) to (,iv) of Def. 2.1 hold, dropping the parameter conditions.

§

Such relation is denoted by (or; Cij) jE]

'V

(~; "j) jE]

.

3 CHARACTERIZATION OF ELEMENTARY EQUIVALENCE.

Let or and!tJ., be classical structures. C = {Cij I jE J} and D = {\ I jE J} are interpretations in 01- and~, respectively, of the quantifier symbols

XAVIER CAICEDO

88

{Q.[ jE]}. j

THEOREM 3.1. -

(ot; C) ~ (~; D) then (ot; C)

I6

Suppose (ot;C) ~ (~; D). Bn define:

E

a

{J

(ot, a; C)

iff

"val

iff

(:e-,1';D)

(ot, a; C)

iff

and a, a'EA Yl

For every {J
PROOF.

r ,1"

[o ,« ) "V (%--; D).

{J + 1

(Ol, a' , C ).

-

{J+l

==

(~,1";D).

{J+l

(:e-,

-

T

;

We show that this gives a back-and-forth with parameters (e ,«},

(J "V

D) • It is clear

that

is an equivalence relation and properties (i) and (iv) of Def. 2.1 hold. Since Given a E An, dE Ak, {J
eLi) and (-UA:) are symmetric, it is enough to show (u).

let

t~ a

= {<jJ(X)[qr(<jJ)<1J

and

(Ol,a;C) 1=

<jJ(a)}.

a

By Lemma 1.2, the conjunction /\ t may be considered a formula of Since the logic is closed under negations:

Loow (2..; )j E f (1)

Now we are ready to check the extens i on property. symbo 1 of type

) and

Yl

(Yll"'"

.

k

and {J < {J 1 < ... < {J -6 = {J'. (Ol, a; C)

1=

::I

-6

= m~x .{.

.{.

{J + n or;;;{J + -6 or;;;{J'. i

Since a "V

T

(Ol,a;C)

and so /\ t.( a

(g"

b),

rank or;;; {J

T; D)

and define

we have

a

{J' + 1

x..{. /\;t.a ( x.). .{.

::I

1=

6. (a)

.{. (Ol, a,

£;

=

b.

be a 1J'

Suppose that a"V

T ,

qua n t i f i e r with

T E

BYl

E A .{., (oz, a; C) 1= /\ t a. ( d ), and so last formula has qr = qr (/\ t.) + Yl • a .{. then:

For each

(x .{..).{J' This a

X. /\ t .

Yl.. .{. Yl.

Qf'

Let

Since

{J + 1 C) -

(~,T;D)

Choose t:»

a

bE

(2)

n.

B.{.

such that (~,T ; C) 1=

is a complete set of

formulas {J

(i6--, T, 6..{. (d); D ) and so a a"V

T

of

6 (d),

the first condition of the extension property.

n.

Now let x..{. c- A.{., i •V

aEX.

.{.

/\

c ; (Xl. a

=

1, ... , k.

By (1) : [ X .]{J

.{. a

For each i

let T;(x) ~

be the formula

89

BACK-AND-FORTH SYSTEMS Similarly, in ~ :

13

[ 6'.-L (X.) I = {x E B -L r

n.

-L

I

(lr,

T ;

D)

T;

F

~

(x )} .

Moreover, the formul a ~ xl , ..• , xk (T 1 ( xl) , .•• , Tk ( xfz )) has qr = 13 + .6 .;; 13 I Therefore, by (2) and the definition of quantifier, ([X J13 , ••• , [XI..]13 ) E q. 1 a '< a j implies succesively:

(01., a; C)

F

QjX 1 " " , xfz(T1(x1),

,TIt(XIt)) ,

(s-,

1=

Qj ~1 , .•• , Xfz (T1( xl)'

, Tit (x It)) ,

T; D)

([6'1

(x1)]~

, .•. , [6'fz

•

(Xfz)l~) E\. •

REMARK 3.2.It is clear from thedemonstration of the last theorem that the functions 61 " " , 6 in the extension property may be chosen homogeneously, k so they work for all quantifiers of type (n l' ... , n ) . Even more, it is possifz ble to choose for each p', a, and T, in advance, a family {6 n: An .... B n In E w} which works for all quantifiers.

16

PROOF.

(Ol; C)

Assume

a'VT

'V

(ex ,<)

(JIy; D).

'V

ex (01.; C) == (;G-; D).

(~; D) then

We prove by induction

qr(¢).;; 13 < ex, then for all

¢ ( !j) , that if

plexity of the formula

13

(ex ,<)

(al; C)

THEOREM 3.3.-

on the

com-

a

T

and

,

implies: (al; C)

(~;D) 1= ¢(r).

iff

¢(a)

1=

The result follows from property (~) taking follows from the isomorphism property (~v). let ¢ = Qj xl"'" suppose that (1) holds for ¢1'"'' ¢k' let p + .6 .;; 13. Define for each ~: conjunctions is trivial.

X.

-L

= {a

Y. = {b -L

< P + 1 < '"

Since

p

tions

6.: A -L

n.

-L ....

n.

ft. E A -L

E

n.

B

-L

(1)

a = T = 0. For atomic formulas, The inductive step for negations

xfz

p

(¢1"'"

= m~x

¢fz)

qr(¢~),

= m1x

qr';; 13 n~,

and then

-L

(01., a; C)

1= ¢. (Ci ) }

(:6-,

1= ¢. (Ii)}

T; D)

be of .6

(1) and

-L

-L

< p +.6 .;; 13 , then by the extension properties there are func-

B -L,

n.

g.: B -L

n.

-L ....

• p

A

•

aa'Vr6·(a)

• P

-L

•

Tb'Vag~(b)

If ( [Xl] ~ , ... , [X k J ~ ) E qj

then

-L

such that for all for all

n. Ci E A -L n.

bE

B

•

-L •

(I) (I I)

([6~(X1)]~,... ,[6~~Yk)]~)EItj" (III)

90

XAVIER CAICEDO

Xl. = [XJ.]~'

CLAIM 1.

Yl. = [Yl.j~.

If aal~aa· where (Ol,u;C) 1= tP.(a),then(~, T;D)l=tP.(fi.(a)) .{. .{. .{. because of (I), the fact that qr (tP) '" p , and the induction hypothesis. By transitivity: a at ~T fi. (a), and so we have again ia , a, C) = tP. (at). This shows .{. .{. [X..{. jPa eX.. The other direction is trivial, and the case of Y..(. is similar . - .{.

6'..{.

CLAIM 2.

(X.) c Y., .{. -.{.

g'. (Y.) -c x.{..• .{..{.

This follows from (I), (II), and the induction hypothesis for [fii (X;.l]~ = Yl.'

CLAIM 3.

tPl.'

[gi (YJ.)]~ = Xl.'

The inclusion from left to right follows from Claims 1 and 2. then

.P • P • T b'Vag.(b)'VTfi.g.(b) and so .{. .{. .{.

.P. b'Vfi.g.(b). T .{. .{.

Suppose

6E

Yl.

•

Butg.(b)Egt.(Y.)cX . .{..{. .{. .{.

and we have bE[fi'.(X.)]p . .{. .{. T By (III), (IV), and Claims 1 and 2, we have that (Ol, U; C) 1= Q.j ;1""';11. (tPl""'tPlz) iff (Xl'oo.,XIz)Eq. iff (Y1,oo.,YIz)E!Z.. iff ($-,T;D) 1= • •

Q.j "1"'"

j

"Iz (tP 1' ... , tP Iz ).

COROLLARY 3.4.00

(b)

(Ol; C ) =:

(:& ;

j

•

a ~ ,e) (Ol;C) =: ($--; D) J.fifi (Ol; C) 'V (~; D). (a ,e) l.fifi (01-; C) 'V (~; D ) fiM aU. MeUnaL6 a.

(a) D)

COROLLARY 3.5.Ifi the. fiamiliu C, D and the. !>.iJni1.aJU...ty typu ofi Oland lJ, Me. MnJ..te., the.n the. fioUowJ.ng coneUUoM Me. e.quJ.va.Ce.n.t: (or; C ) =: ( J,; D) (e.quJ.va.Ce.n.t fio!Z. MnUMy fioJunulM) , (w,e) (Ol; c) 'V (X-; D ) ,

(01- ; c)

(n ,e ) 'V

(Z-; D)

fiM

PROOF. (J.J.) => (ill) and (ill) Lemma 1.1 and Theorem 3.1. •

=>

aee

nEw.

(l.) ar.e trivial; (J.)

There are more convenient characterizations of Corollary 3.4 (b). THEOREM 3.6. (l.)

The. fioUowing Me. e.quJ.va.Ce.n.t:

(01-; C ) ~ ( ~; D ).

00_

=>

(J.J.) follows

from

elementary equivalency than

91

BACK-AND-FORTH SYSTEMS

(u) (Ol; C)

~

(-Lil) (Ol; C)

'V

PROOF.

(.i)

=>

( ;g,; D) (Xr; D) (-Lil).

wheJte P 1.1> non-well. ondened, (bac.k-and-6oJtth wUhout Pa.JLamet:eM).

The same as the proof of Theorem 3.1, but

simplifying

the definition of back-and-forth to: a 'V 0' iff (Ol, a; C) ~ (Ol, 0'; D), etc. Instead of t~ one defines t .. = {4> (y) I (Ol. 0; C ) F 4> (a)}, By Lemma 1. 2, a. a. fI t .. is a sentence of L (Qj') j' E ] ' The rest of the. proof is simpler because a. oow we do not need parameter conditions. Choose any non-well ordered set P and define 0 ~ t iff a » t , Let PI> P2 > ,., be an infinite descending sequence of P , One shows, as in the proof of Theorem 3.3, by induction on the complexity of 4> (y) , that for all n: => (U).

(-Lil)

(U)

=>

(i),

o

Pn 'V

implies:

r

(Ol; C ) F 4>(a)

iff

(~; D ) F 4>(r),

To use the extension property in the inductive step for one chooses

§

4

P n + .:\

< P n +.:\ _ I < .. , < P n ' •

Qj

xl.· ... xm(4) l' ,, . , 4>m )

INTERPOLATION AND MONADIC QUANTIFIERS,

A quantifier symbol of type n(x ,This includes the cardinal quantifiers Qa: "there are at least wa eln ments", as well as Chang's and Hartig's quantifier, but notthe Magidor - Malitz quantifiers. Throughout this section L M will denote the logic L oow (Q.). E ] , j j where Qj runs through all the possible Lindstrom-Mostowski monadic quantifiers.

»·

LEMMA 4. I . -

a =L

oow

16 Ol and :t; Me .:\:tJtuc..tu!l.u 06 poweJt at

(Q):tr impUu

I

a

=L;,t-

M

mO.6:t

wI' then

•

PROOF. Let 2n = {o I 0 : n ... 2 }, for seA 1et sa = Sand sl = A - S • For each nEw and F: 2n ... {K 'K cardinal, K" wI} define the quantifier:

~(A)={(SI,.. "S)',;/OE2nl n

l~~)I=F(O)}, Since a monadic structure n L« n ,(. (A, SI".'. Sn) is completely determined by the above set of cardinals, there corresponds to it a unique F such that (Tl'".,T n) E Q F (8) i.ff (8, T1,.", Tn) "" (A, SI" ." S). Let 3!K x 4>(x) mean that the truth set of, .4>(x) has exaclty K n elements (K';; wI)' Clearly, for structures of power at most wI' Ol=L (Q);6implies

a

=L

(Q

3,K)

Ir.

and so

oow l' , K definable from the former quantifiers.

oow 1 (Q),(",' because the QF' s are oow F F If ~O is 4> and 4>1 is I 4> :

a

=L

92

XAVIER CAICEDO

() () ) QF"l"'" ( '1>1"1"'1>" rt

rt

rt

=>

f\ I>E 2 rt

1 (,,)1> (i I 1 . [3.' F(I> ) x i
(en;

Q (A))F 'V (ho; QF (B))F' To conclude the proof, we show F that the given back-and-forth has the extension property with respect to each monadic quantifier, and apply Theorem 3.3.

By Therorem 3.6:

~r

Let

a

<~

~

'V T ,

I,

and let

6:

If

A -+ B be the function given

QF's

by the extension property for all the

homogeneously

(see Remark 3.2).

M=([X11~"",[Xh]~)EQ;(A),choose F

such that

MEQF(A),

thenM' =

([ 6' (Xl) J~ , ... , [6' (Xh) l~

(B, M')

and so

) E QF (B) by the extension property. Hence, (A,M) "" M' E Q.(B) by definition of Lindstrom-Mostowski quantifier . • j

The proof of the following lemma is analogous.

Qa

Let

runs over all the cardinal quantifiers.

en

L ww(Q), where

==

k

or == jJ.L M In Friedman 1973, Friedman gives a sentence '1>

LEMMA 4.2. -

L C

L = Loow(Qa)aEOr,where C

hnpUu,

of

Lw(v(Qa) (respectively,

Q is Chang's quantifier) containing a relation symbol

P, such

(a,

P) 1= ep.

that for every Ol

there is at most an interpretation

P for which

However, K = {en I (en, p) 1= ¢ for some P} is not elementary in L This is shown C' giving a pair of structures en EK,:f:.- f/- K which are elementarily equivalent in L It is observed that this is enough to show the failure of Beth's definability

C'

theorem for any logic between

Lww(Q",) (respectively

Lww(QJ) and

Lemma 4.2, we have: THEOREM 4.3.Beth (Lww(Q), LM)

Beth (Lww(Q",),L

6iLU6.

M)

6iLU6

60JLarty

a>O.

L C'

After

MAD,

For example, Beth's theorem does not hold in logic with the Hartig quantifier since it is between L ww (Q) and LW The first part of the last theorem is not true for a = 0

because

satisfying interpolation; (see Barwise 1974). ic

L

is a sublogic of w 1w hence, Beth's theorem.

L extending M

Lww(QO)

and

The same is true of l:!.(Lww(~))

The next theorem imposes a restriction in such logics. A log-

L+ has 4elat£vizat£ortO if for every monadic predicate V and sentence ¢ of L+ ¢ V such that ta , V) 1= ep V iff en,.. V 1= '1>. Here, V is

there is a sentence

an interpretation of

V and

m~ V

is the restriction of the universe and

rela-

tions of en to the set V. Almost all interesting logics have this property. An exception is logic with Chang's quantifier. The Lowenheim numbe4 of a logic L+ is the smallest cardinal of power at most

K.

K

L+ has a model it has one L+ satisfies the downward Lowenheim-Skolem

such that if a sentence of

It may not exist.

theorem if its Ulwenheim number is

co ,

BACK-AND-FORTH SYSTEMS

THEOREM 4.4. -

Le;t

L+

93

be a tog.£e between

L ww and L hav-i.ng Ile.eauv-i.M L+ has Lowenheim numbeJr. «, then 601l

16

za:tion and -baU66y-i.ng -i.ntVtpota:tion.

mI .;; "1m

any -bentenee ¢ hav-i.ng -i.nMnUe modetJ> Sup {] 1= q,} = x , 16 not have Lowenheim numbeJt such. !>entenc.e haJ> modetJ> 06 MbWuvt.Uy iMge -i..ty.

PROOF.

L+ doe!> c..etJLd,[nat-

q, with infinite models of size X, X < K

Suppose that there is

,

but not of any size between x+ and K (included). By definition of U5wenheim number, there is a sentence l/J with all its models of power greater than X. Let e be a sentence whose models are the equivalence relations. The classes K 1 (respectively K ) of models of e having as many equivalence classes as a model of 2 q, (respectively, a model of l/J) are PC classes of L+, defined by the projection of the sentences: 8 /\

"6

is a function onto V" /\ 'ifx 'r1 Y (x E Y +-+ 6(x) = 6(Y)) 1\

q, V (resp.

1/1 V).

Since these sentences do not have common model s of power 1ess or equal than", K 1 are disjoint PC classes of L+. However, they are inseparable in L+.If 2 has X has equivalence classes of power X', and (A', E ') E K has (A,E) E K 2 1 X' equivalence classes of power X', an easy back-and-forth argument shows tha t and K

(A, E) =L (A', E'), and so (A, E) =L (A', E'). C M terpolation fails in L+. • COROLLARY 4.5. -

Le;t L+ be a tog-le between

tiv-lzaUon and -baU66y-i.ng -i.nteJtpotaUan, then Sk.atem theOllem.

From this we conclude that in-

L ww (12. ) and

L hav-lng IletaM L+ -6aU6Mu the dOwnwalld Lowenheim-

0

PROOF. There is a sentence in Lww(Q.O) ' and therefore in L+, which has models of power w but not larger. By Theorem 4.4 it must have Lowenheim number w .•

§

5

COFILTER QUANTIFIERS, A SIMPLER BACK-AND-FORTH.

n Let 12. be a quantifier symbol of type (n), q ~ 9(A ) is a eoMUeJr. -lnteJr.pllUaUon 06 Q. if it satisfies Monoton-i.U.ty: SEq and S ~ s' imply S' E q, and V-f.,f,Wbu.tiv-i..ty: SuS' E q implies SEq or S' E q. Obviously, q is a

q

cofilter interpretation iff the "dual" interpretation = {S I A - S €I- q } is a filter over A. In terms of the language, (m; q) must satisfy the schemata:

\!X(¢4l/J) 4(Q.xq,4Q.xl/J),and

q

tifier is w-eompte;te if u {Sn I nE w} E q implies

QX(¢V1/I)4(Qx¢VQxl/J).

is an

w- complete filter. for some n. •

Sn E q

Acofilter

quan-

Equivalently, if

Qa is w-co'mplete if its cofinality Ql' Magidor-Mal itz quantifiers are not

The cardinal quantifiers are cofilter, is greater than

w,

as is the case of

cofilter, however the quantifier

n H

o'

where

H~ xl'"

xn ¢(x 1"'"

eto x

is equivalent to the cofilter

quantifier

means "there is an infinite set n)

1

such

XAVIER CAICEDO

94

tha~

a 1, ..•• an

for all distinct


E

r

there is a permutation

'/1

for whi ch

holds".

The back-and-forth characterization of elementary equivalence may be simp1 ified in the case of logics with cofi1ter quantifiers:

DEF I NITION 5.1. A -6.{mp!e bac.k-and-60Jt.th 6/tom (al; q) to (~, Jr.) is defined as in Def. 2.1 (respectively Def. 2.3), except parts (A) and (B) of the extension property which are changed now to:

Ci-t)

aE An

For all

bE Bn such that:

there is

• P (A+) aa'VTb.

(B+) [ajP E q a

implies

[lij~ EJr..

(M:i+) The analogue in the other direction.

In the following theorem, the subscript S(Fin) indicates that there

tot,

p1e back-and-forth from classes of each

Ek

forth where each

q)

is finite.

Ek

(:&-; Jr.) where the number of

to

Similarly,

S(w)

is a sim-

e q uiva 1 ence

indicates a simple back -and-

has at most countab1y many equivalence classes.

THEOREM 5.1. - Le:t C and D be MnUe 6amL.UeJ.> 06 c.G6ille.!L quan..ti..Me.!L btte.!Lp/te:tatiOft6 and a.Mume the numbe.!L 06 /te!atiaft6 in Mc.h -6tJr.uc.tu!Le. is MMte, then: (a)

1'1

(aL; C) == (i:-; D)

r 6 in

ad~a1'1

the quan.ti Me.M

1'1

(b)

(al; C ) ==

(e.)

t

6

(z, ;

(oz; C)

(oZ; c)

in6

~

(

.t

D)

S(w)

i66

Me

(1'1,<)

'V (JY;D). S(Fin) w - c.amp.i'.e:te.:

(aL; C)

(aL; C)

(h-, D) with

P

(1'1,<) 'V

S (w)

(

lr ; D ) •

nan we!./'. OfLde.!Led, then

:c- , D ) .

PROOF. (a) Since a back-and-forth is a simple back-and-forth, from left to right follows from Theorem 3.1 and Lemma 1.1, plus the observation that the equivE~

qr at most k. For the q and Jr. are cofilter interpretations, then properties (~+ -M:i+) imply the original extension property. Given a ~T choose for each a· E An some 6 (a) = b such that (A+) and (B+) hold. Assume as in ~­ BofDef. 2.1 that XCA n and [Xjk E q• Since [Xjk =u{[ajklaEX}, and a k a the number of equivalence classes of the relation 'V must be finite, the union is alence classes of

result definable by formulas of

other direction one shows that if

of a finite number of classes. By the di stri butivity of q, [aj ~ E q fo r some dEX. By (B+), [6(a)jk EJr.. Bymonotonicityof n , [6'(X)jk EJr.. T

T

(b) and (e) are similar; the converse of (e) fails because the number of finable subsets may be too large. •

de-

95

BACK-AND-FORTH SYSTEMS

§

6 APPLICATIONS TO Lw w (Q1) .

Let al;. be a structure of type T;.' then [Oz.0" •. , a n] is the structure that has the disjoint union u {A;. 1;. .;; I'd as universe and whose relations are the corresponding copies of the relations of each al;.' A relation R between tures is PC in L+ if there is a sentence in L+ such that Oln)

R(Olj"'"

iff [0l1"'"

Oln'x;.]

struc-

1= ¢.

Let t : T ~ T' be an ;'nt~pnetat£on between si~ilarity types (languages) as t denotes the restri cin Barwise 1974. If oi is aT' -structure, then a tion (projection) of al to a T-structure, via t. In the case of a himple interpretation, we write a I' T.

r

LEMMA 6.1. Let C be a Mme 6amil.y 06 Und6tnam-MOhtoW.61U. quant-iMenh such. that L w w(Q1' C) hM neiativ-izaUon.6. Let t-i: T~ T.i. be .i.ntenpltetat£On.6 wh~e T .i..6 Mme. Then the 60llowing Iteiation between htJtuctunU al, $-, a.nd p

and

u

PC

.i.n the g.i.ven log-ic:

(al I'" t

1

; Qj' C)

p

'V

s(w)

(i&- I' t 2 ; Qj' C ).

PROOF. It is a routine exercise to write down sentences stating that some P {E~ I pEP, nEw} form a simple back-and-forth from a r t j to k I' t • 2

The only second order statement in the original definition, the extension property, has become first order. Q and the quantifiers of C are needed to state the ex1 tension property. Qj is also needed to put a countable bound on the number of equivalence classes. The infinite family of relations En(p, x j , ... '''n' Y1'''' ,Y n ) expressing the E~ 's may be reduced to a single one by a suitable encoding of the finite sequences, see Caicedo 1978 for details. Relativization is needed to express the meaning of each quantifier in o; I't j and :t:-l't 2 instead of [OZ,~,P, ... ] .

•

Let B(U, V, P, <) be the sentence given by the lemma where U, V, P, and <denote respectively the universe of al, the universe of and the ordered set of parameters P. If we drop the finiteness conditions, e becomes a set of sentences.

e-

In the next lemma, a class K is PC if there exists a cou.ntable set of sentences T and an interpretation :t such that K = {Ol t t I a 1= T}. L+ satisfies LS(w if every sentence (theory) having a model has one of power at most "'1' 1) LEMMA 6.2. L+

ex:tencUng

Mntence 06

L

WW

Lww(Qj)' then

(~; Qj ) w£:th

th~e

P non-weU Md~ed.

theo~e.6 Ol: and PROOF.

Let K j and K be PC &M.6e.6 06 It countably compact log.i.c 2 (Q 1) and hav.i.ng neiativ.i.zaUo n.6• 16 they aILe .i.n.6epaJtable by It

Let

:t;

may

t.: .{.

T

aILe

a

E K j , I(;- E

In CMe

+

L

K~huch:thcLt

.6ati.6Me.6

be chosen. 06 pow~ at mO.6t "'1'

~

T.

.{.

and K..{.

= {Ol ~t...(. I oi

LS(w j )

1= T .}, with ..(.

(Ol;

Qj )

P

'V

S( "')

60n countable

T...(.C L+.

By

countable compactness, we may assume the number of symbols in T and T.i. to be fi(lite

96

XAV IER CAICEDO

(see Flum 1975). Suppose K and K 2 are inseparable in L ww(Q.1)' Since there 1 are finitely many non equivalent sentences of rank at most n- in th-is logic, there

~

exist alnE K 1,

n E K 2 such that

~Lww(Q.1) .i:-n ·

Otherwise, we could sep(n,<) arate the classes by a sentence of rank n. By Theorem 5.1 (oZn;Q.1) 'V (-6- ; Q.1) ' n al n

Sew)

In this way, each finite part of the following theory of 8(U, V,

Here,

U T = {1>U 11>

of the full set.

P,<)U{T~, T~}U{P(cn)' E

n.

Making

L+ has a model:

c n + 1
By compactness, there is a model

a

= al' r t

1

and

J,

= Xo'

rYe= ra',

;t', P , ... ]

~ .t 2 , we have the result. -

It is the The next theorem is analogous to Lindstrom's theorem for L w w' best possible result in the sense that it is possible to have proper countabl y compact extensions of L ww(Q.1) by non-monadic quantifiers satisfying LS(w for 1), example logic with the Magidor-Malitz quantifiers Q.~.

THEOREM 6.3. - Le..t L+ be. a .togic betwe.e.n ltel.a.tiviza.tioYilJ, In L+ .6a-tW 6.{.v.. compac.tYle..6.6 and then

L+

L ww (12 ) and L having M 1 LS (w 1) n0lt cowu:a.b.£.e. the.oJti.e..6,

~ L ww(Q1)' +

1> E L - L ww (12 ) , then the cl asses K 1 = Mod (1) ) , 1 K = Mod ('(jl) are inseparable in lww(Q'l)' By Lemma 5.3 and Theorem 3.6, there 2 exists OZ F (jl and i&- F I (jl such that al ~ L /tY , a contradiction. M

PROOF.

Suppose

The next theorem shows that interpolation fails strongly in Theorem 4.3 for a = 1.

THEOREM 6.4.I

n they

Le..t

(jl

have. an inte.Jtpo.tant in

and

!J;

LM.

It implies

be.6entencv..on

L the.y have. One. in M,

L w w(Ql).6uch.tha.t(jlI=!J;. L ww (0. ) , 1

PROOF. Let r be the common language of 1> and !J;; if they do not have an interpolant in L w w ( Q1 ) ' then the PC classes K = {OZ r- T I or 1= 1>} and 1 K = {tr t T \;e, F 1/1} are inseparable. By Lemma 5.3, there are structures OZ I=(jl 2 and Z, F 1/1 such that (J1.. t r ~ L :t, ~ T. Therefore, 1> and !J; do not have interpolants in

L W

•

M

L ww (12 1 ) , In T ha.6 a (uncountab.tel model., it ha..6 a (u,ncouYl.ta.b.£.e) model. .6aU~nying at mo.6.t coun.tab.£.y n0lt each nEw. many n-.typv.. in L W THEOREM 6.5. -

PROOF.

Take

Le..t

K

1

T be. a couYl.ta.b.te. the.oJty in

= K 2 = Mod(T)

in Lemma 5.3.

Theyare

obviously insepa-

97

BACK-AND-FORTH SYSTEMS

rable; then we have of power at most

a-6-;'.

(a, Q1) If

wI'

t

i~wJ,

(JtJ-; Q1) with P non-well ordered, in

AIt , find

bEBIt such that

ia , a)=\

a

and f(;..

;-6;

then

(Q )(i6, b)=L (Q)(Ol, a'); see Theorem oow 1 oow 1 3.6. By Lemma 4.1, ta , =L (m, Therefore, it and satisfy the same M type in L Since the number of equivalence classes of - is countable, the same

Hence,

a)

a').

M.

is true of the number of types.

a'

•

In L w w we have that a theory with infinite models has an uncountable model satisfying at mostcountably many types OVe!L ea.eh eoun;ta.b£.e ~u.b~e.t. Thi sis no't true here as shown by the counterexample:

Q x P(x), --, Q x R(x), 1 1 If x If y(P(x) /\

p(y) /\

"<

-w

ct

UltcaJt OILdeJt" ,

x =1= Y -+ 3 z(R(z) /\ x

< z /\ z < y».

Any model satisfies uncountably many types over the interpretation of R. The last three theorems hold for any countable compact logic having relativizations and satisfying Linds.-Most. cofilter quantifiers.

LS(w

where

L w w(Q1' C ) C is a finite family of

1), In Theorems 5.5 and 5.6 one must change

LM for

L w w (Q1' C) all monadic quantifiers. However, we do not know of any concrete example. On the other hand, one can show analogues of these theorems for Stationary logic L(aa)·, see Caicedo 1977 b. So, any countable theory of L ~ct) has a model satisfying at most countablY many types in the infinitary logic L(ctct)M' L(ctct) is maximal in L(ctct)M' with respect to compactness and LS(w ) , and any pair of sentences of L(ctct) with an interpolant in the result obtained by adding to

1

L(act)M have one in

§

L(aa).

7 AN EXTENSION OF Lww(QO<w) WHERE ELEMENTARY EQUIVALENCE IS

PRESERVED BY PRODUCTS.

In Badger 1977, L.Badger shows that elementary equivalence of structures is not

Lww(o.o<W) obtained by adding the MagidorMal itz quantifiers under the infinite interpretation to first order logic (cr. Magidor and Malitz 1977). His proof is based on the undefinability of well order in the logic. Actually, his proof gives the stronger result: no extension of this logic where well order is undefinable satisfies preservation of elementary equivalence by products. In this section, we define a natural extension of the above logic where elementary equivalence is preserved by finite products. Badger's counterexample does not work there because well order is definable. preserved by products in the logic

Q8

For ea(h It define an It- variable quantifier symbol R It where R It xl' ... , x lt

98

XAVIER CAICEDO

The same quantifier is obtained if one asks the set (I, <) to be well ordered or just of type (w,<). By Ramsey's Theorem this is a cofilter quantifier. Let

Lww(R <w) result by adding these quantifiers to first order logic; it extends logic with Magidor-Malitz quantifiers because:

where

runs over all permutations.

n

The extension is proper because well

is definable there by the sentence I R

2xy(y<x), and it is not

L w w(Q.o<W) by Badger's Theorem 4.10 in Badger 1977.

order

definable in

Usi ng our back - and - forth

for cofilter quantifiers we show: THEOREM 7.1.-

pIWduc.M

06

L ww (R<w )- e£emen..:taJ1.y equ-i.valenc.e.u, pJtU>eJtved by Mn.-Ue

~:tJw.c.:twz.e.6.

PROOF.

Let

x.-

IJl and

IX

(respectively

.."

and

I

IV

)

be

L

ww

(R<w ) - el e-

mentary equivalent. Since every sentence has finitely many relation and quantifier symbols, there is no loss of general ity in assuming that the similarity type is I m finite and restricting our considerations to C = {R , ... , R }. By Theorem 5.1: w (en; C) 'V ( it:-; c ), and the same is true for en 1 and x,. I Let S(F.tn) k. B I = (w, <, {E. I n, k. E w} ), ,t = 1,2, be the corresponding back-and-forths.

.<.,n

~

x

x'

For each pair of sequences = (xl'"'' xn), = (X'I'"'' x'n) define ((x 1 x'I) , ... , (x n x'n Define E ~ in (A x A,)1t U (B x B,)n by:

».

x+ x'~ y + y' We claim that the system forth from each

IJl x OZ'

E~ .

iff

B+ = (w,<,

to!6 x ~

I

,

xEk.I ,n y

{E~ liz,

It

and

E w})

X'Ek. 2 ,n

x + x'=

y'

is a simple

bacf<-and-

with finitely many equivalence classes for

The fact that

Ek. is an equivalence relation, and properties (,t) and (,tv) of n Definition 2.1 follow easily because they are expressed by universal Horn sentences, that are preserved by cartesian products, and we defined the new relations as the "product relations" are ordinarily defined in the cartesian product. EIz has finitley many equivalence class~ because for any the equivalence clas~ of this sequence with respect to En has the form: .. .. k .. .. ... .. 1<. .. ... k. [x+x'] = {u + U' IUE I x l and u' E l x"] l . Iz Therefore, if E~ has M classes and E~ has N classes, E has MN

x+ y

classes. IJ

=

X+

x'

pose that

It remains ton show the extension

E (A x AI)n and

k + Jt < Iz'.

T

=

Y+

proper't~

yIE(BxB,)n

(u+ -Lu. +) for ea:h R": Let

be such that

IJ~T, and sup-

By definition: ~

x

Iz' 'V

~

y

and

x'

Iz' 'V

y'

(l)

BACK-AND-FORTH SYSTEMS

Let

b=

a + a'

E (Ax A' )"l.

b'

(6 1"", bJt) and

By the extension property in B and 1 b~) E B,Jt such that:

B 2'

there

exist

= (bi, ... , ..

.. tjb

k.

of.

xa

of.

'V

and

[Gi11ERJt(A)

[a' l~, From (2):

99

~

E

k

x'a'

'V

(2)

[bl~ERJt(B)

implies

(A') implies

....

tj'b'

[b'l~,

E

R

Jt

(B').

(3)

.. .. k ..... (0. a + a' ) ~ (r , b + b').

It remains to show that (4) below implies (5):

s=

t

a-

.l'lk E RJt(AxA') o

(4)

[b+ b'lk E RJt(BxB')

(5)

r

Assuming (4), we get a linear order (1, <) of type tha t for all (u 1 wI) < ... < (u Jt W Jt) ; n 1,

(x,

U

l' ...•

(x', W 1'"

.•

U

Jt)

W Jt)

k 'V

k 'V

(w,<) with

1 ~AxA'. such

('x, Gi)

(x', ci')

If J and J' are the projections of 1 in A and A' respectively. one of them, say J. must be infinite. Choose a function 9 : J ...J' such that (u,e(u))EI for )). all u. E J, and define a linear order in J by: "i < u iff (u 2 1,g(u1)J«u2,g(u2 It must have type (w,<). Moreover u < < uJt in J implies (u )) 1 l,g(u 1Jt , uJt) E [iil~. < ... < (u Jt, g(u,,!)) in 1, and so (u 1 ' Hence, [aJ~ E R (A) • k Jt and [b 1. E R (B) by (3). Let (L. <) of type (w,<) with L c B be such that tj u1 < ...
(u W) < ... < (uJtw) in 1. Hence, «u W ) ••• (uJtW)) E S and so (x',w •••• ,w) 1 1 k • k • 'V (x', a~) 'V (tj', b'I"'" b~). By the isomorphism property of back-andforth. this impl ies b\ = ••• = b~ = b'. Define the infinite set 1+ = t x {b'} c Bx B', and order it by: (u b') < (u b') iff u < u • Then 2 1 2 1

ai, ... ,

(u b')<

<

«u 1 b' )

(uJtb'))

1

CASE 2.

Both

Then we also have

(u

Jt b') implies (u 1 ... UJt)E E

[6 +6'1:.

[bl~.

and so

This shows (5).

J, J' are infinite.

[b'l~, tj

E

RJt(B'), by (3).

Let (L', <) be a linear

order

XAVIER CAICEDO

100

of type (w,<) for which ui < ... < u~ implies (ui, ... ,U~)E [b']~' Let 6: L..... L' be a one to one order preserving function and define 1+ = {(u, 6(u)) I uE L} with the order (ul' 6(u 1)) < (u 2' 6(u 2)) iff "i < u2 iff 6(u 1) < 6(u 2). If (ul' 6(u 1 ) ) < ... < (uJt' 6(u Jt)) <6(u1),···, 6(u Jt))

E [

and shows (5) again.

then

(u 1" ' " uJt)

b' I~, which proves

E

~

[b

k

Ilj

and

«ul' 6(u 1)),··· (u Jt' 6(u Jt))

E

[b+b' I~

With this we finish the proof that

(oz. Now apply Theorem 5.1.

oz. ';

x

C)

w 'V

S (F,cn)

(~x ~ '; C )

•

REFERENCES. L. Badger 1977

An EhJten6eucht game 60ft .the muU.£va.tU.a.te qu.a.ntiMeJt 06 MaU.tz and 60me a.ppl-tca..t,(OYl6, Pac. J. of Math. vol. 72, pp. 293 - 304.

J. Barwise 1974

Auom6 60Jt Ab!.l.tJta.d Model. TheOftlj, Ann. of Ma th. Logi c vol. 7, pp , 221 - 265.

J. Barwise, M. Kaufmann, and M. Makkai 1977

Stationary Logic, University of Wisconsin, preprint.

X. Caicedo 1977 a On extensions of Lw wlQ.l)' preprint. 1977b A back-and-forth characterization of elementary equivalence in Stationary Logic, preprint. 1978

Maximality and interpolation in abstract logics, Ph.D. disserta-

tion' University of Maryland.

A. Ehrenfeucht 1961

An appl-tc.a.ti.on 06 game.!.l .to .the eompR.etene.!.l6 pJtobR.em 60Jt 60Jtmal,(zed .theoJUe.!.l,

Fund. Math. vol. 49, pp. 129 - 141.

J. Flum 1975 Ffu.t oMeJt R.og,cc and i l l ex.teYl!.lioYl6, Logic Conference Kiel, Notes in Math. vol. 499, pp. 248 - 310.

Lee t .

R. Fraisse 1955 SUIt que1.qUe.!.l da.!.l!.l,cMc.a.ti.oYl!.l des Jte.e.a..t-c:OYl!.l, ba.!.lee6!.lUlt des ,(/.)omOJtpJu:.ome.!.l Jte6.tJtein.t6, Alger-Mathematiques, vol. 2, pp. 16 - 60, 273 - 295. H. Friedman 1973

Beth'!.l .theoJtem,cn ea.Jtd-tnaU.tlj R.ogie, Israel J. of Math., vol. 14, pp. 205-

21'3.

BACK-AND-FORTH SYSTEMS

101

J. Keisler

LoMe w.U:h the quanti6.i.eJr. "theJr.e emu uneoun..ta.bty ma.ny", Ann. L09iC, vol. 1, pp. 1 - 94.

1969

0

f Ma t h•

C. Karp 1965

Fi/Ute quantiMeJr. equi.va.tenc.e, The Theory of Models, Addison, Henkin and Tarski (eds.), North-Holland Pub. Co. Amsterdam, pp. 407 - 412.

M. Kaufmann 1978

Some

results in Stationary Logic, Ph. D. dissertation, University of

Wisconsin.

A. Krawczyk and M. Krynicki 1976

Ehlten6euc.h:t gamC6 6M geneJr.a.Uzed quantiMeM, Set Theory and Hierarchy Theory, Lect. Notes in Math. vol. 537, pp. 145 - 152.

P. Lindstrllm okdeJr. pkedic.a.te togic with geneJr.a.Uzed quanti6ieM, Theoria, vol. 32, pp. 186- 195.

1966

F~t

1969

On exten6ion6 06 Etementaky Logic, Theoria, vol. 35, pp. 1 - 11.

M. Magidor and J. Malitz Compact exten6ion6 06 L(Ql, Pakt I, Ann. of Math. Logic, vol. 12, pp. 217261.

1977

J.A. Makowski 1977 a Some Mode£. TheMy 60k monotone quantiMeM, Arch. Math. Logik, vol. 18, pp. 115 - 134. 1977b Elementary equivalence and definability in Stationary Logic, II Mathematisches Institut der Freien Universit~t, Berlin, preprint. 1978

Quantifying over countable sets: Positive v s , Stationary Logic.

II Mathematisches Institut der Freien Universitat, Berlin, preprint.

J.A. Makowski, S. Shelah and J. Stavi 1976

tJ.-

togiCA and geneJr.a.Uzed qua.ntiMeJr., Ann, of Math. Logic, vol. 10, pp , 155 192.

A. Mostowski 1957

On a geneJr.a.Uza.ti.on 06 quanti6ieM, Fund. Math., vol. 44, pp. 12 - 36.

J. Sgro 1977

ComptetenC6~

theok~

60k topotogic.a..e.

mod~,

Ann. of Math. Logic, vol. 11,

XAVIER CAICEDO

102 pp. 173 - 193. S. Vinner 1972

A geneJUtUzation 06 EhJLen6w.cM'
Departamento de Matematica Universidad de Los Andes Apartado Aereo 4976 Bogota D. E. Colombia

MATHEMATICAL LOGIC IN LATIN AMERICA A.I. Arruda, R. Chuaqui, N.C.A. da Costa (eds.) © North-Holland Publishing Company, 1980

FOUNDATIONS OF STATISTICAL METHODS USING A SEMANTICAL DEFINITION OF PROBABILITY Rolando Chua-qui.

ABSTRACT. The purpose of this paper is to construct models for the main methods of statistical inference and estimation using the semantical definition of Probability introduced in the author's A ~em~nt{eal de6~­ t£on 06 P~ob~b~y appearing in Non-classical Logics, Model Theory and Computability, North-Holland, 1977, pp. 135 - 167. Using the simple probability structures introduced there as building blocks, a new type of compound probabil ity structures (cps) is defi ned. Different forms of cps give an account of the classical frequency methods, Bayesian methods, and stochastic processes. INTRODUCTION. There are two main competing schools of statisticians who sponsor different methods of statistical inference and estimation: the classical methods based mainlyon the laws of large numbers, and Bayesian methods, based on Bayes theorem. (For a comparative account of these methods, see, for instance, Barnett 1973. use Barnett's terminology for the different schools of statisticians.) The main purpose of this paper is to construct model s for both types of methods using the semantical definition of Probability introduced in Chuaqui 1977. These models can serve as a basis for a discussion of the justification of these statistical methods, and a choice between them in each particular case, This is not possible in a purely axiomatic approach. Chuaqui 1977 is presupposed for the present paper, especially Sections 1-3 and In particular, the notation introduced in Section 2 will be used throughout this paper. Section 4 of Chuaqui 1977 contains some measure-theoretical results that will not be used here and Section 5 is mostly superceded by the contents of this paper, especially its Section 5. A new version of compound probability structures is presented in it. 6.

This paper is divided into five sections. Section 1 contains some remarks on Truth and Probability, which give some of the intuitive background for my definition. Section 2 briefly introduces Conditional Probability. Section 3 presents a frequency model for classical statistical methods. Section 4 introduces a Bayesian model for Bayesian methods. This section supercedes the remark made in page 165 of Chuaqui 1977 where doubts were expressed as tv the possibility of giving an account of Bayesian methods with the semantical definition. As it will be seen in Section 4, it turns out that this is possible. Finally, Section 5 pres~nts the general form of compound probability structures. The structures discussed in Sections 3 and 4 are particular cases. 103

ROLANDO CHUAQU I

104

Stochastic processes can be put into the general framework of Section 5. However, a detailed discussion of these models and their applications to stochastic processes will be left for another paper. I would like to thank Professor Newton C.A. da Costa for many useful suggestions and profitable discussions which served to improve the paper. 1.

TRUTH AND PROBAB III TY.

I would like, in this section, to expand some of the remarks made in Chuaqui 1977 about the relationship between Truth and Probability. In my view, Probability lies between Truth and Falsehood and not between Logical Truth and Contradiction. I believe this to be correct for all uses of probabilities. However, as was stated in p. 135 of Chuaqui 1977, not all uses of the word 'probable' satisfy conditions compatible with the Calculus of Probability (cf. Lucas 1979). My attempt (i.e. the semantical definition) is to give a formally correct account of the cases where Probability is compatible with the axioms of the Calculus. My present claim with respect to the virtues of the semantical definition is that it can give a good account of statistical methods of inference and estimatio~ and of stochastic processes. My conjecture is that models can be built according to this definition for all uses of Probability in Physical Theory. In what follows, I restrict the use of the word 'Probability' to cases where there is an appropriate measure compatible with the Calculus. Because of the connection between Probabil ity and Truth, the following material conditions must be satisfied by any formal definition: 1) Probability has to be applied to the same type of things as Truth. In Model Theory, using Tarski's definition, we introduce the concept of the truth of a sentence under an interpretation. That is, a sentence is not true or false in i! self, but relative to an interpretation. Thus, it is not that the interpreted sentence ~ is true or false, but that ~ is true or false under a given interpret~ tion. The same sentence may be true under one interpretation and false under another one. This conception was an important-advance in Logic,especially developed in Model Theory. I propose the same relativization of the notion of Probability to an interpretation. In this way we do not speak of the probability of a sentence (interpreted or not), but of the probability of a sentence given an interpretation.These interpretations should be different from the usual ones in Model Theory. Under a probability interpretation, a sentence can be true, false, or have any probability between 0 and 1. Interpretations in Model Theory are represented by poss i b1e models or relational structures. The corresponding entities for Probability are what I have called probability structures. These structures are of two kinds. In Section 3 of Chuaqui 1977, the basic structures, namely simple probability structures, were defined. These structures form the basic building blocks for the other type: compound probability structures. A first attempt to define the latter was made in Section 5 of Chuaqui 1977. I present here a new modified definition for these compound structures. In general, a probability interpretation is constituted by the triple (K, D, ~) where K is a probability structure (simple or compound), D is the field of subsets of K consisting of sets of the form Mod (~) (the set of models of the sentence ~ which are in K), and u is a probabilify measure on D. Then, the probability of a sentence ~ is given by, l'K(~)=u(ModK(~)) .

FOUNDATIONS OF STATISTICAL METHODS

105

2) Low probability means 'almost falsehood' and high probability, 'almost truth'. Thus, a sequence of sentences whose probabilities tend to zero (given an interpretation, i.e. a hypothesis) has the same effect as a false sentence (given the same hypothesis): the actual occurrence of such a sequence forces us to reject the hypothes i s (cf , Lucas 1970, ch, V). This manner of considering Probability and Truth, puts it on a par with other physical measurements. When we measure, say, length we obtain not the 1 actua 1 ' length but an approximation, and we know that the approximations tend to the actual length. In a similar way, in order to determine truth (or falsehood) we approximate it by probability. 3) The basic elements of a probability interpretation (K, B,~) are the probability structure K and the language L. K represents what is assumed (or known) to be true; L gives what is considered possible to be known. Thus, for instance, if an individual constant a appears in L, this means that the object denoted by a can be identified. K and L represent all the objective information which we put into the probability interpretations. B is determined by K and L and ~ should also be. We should assign the same probabilities to physically symmetrical events (i. e. events which are symmetrical according to the laws of nature). An attempt was made in Chuaqui 1977 to capture this feature and obtain ~ with the concept of Ginvariance for simple probability structures. The group G giving the invariance is determined by K and L, as it should be (see Chuaqui 1977, Section 3). In the present paper, a symmetry relation ~ for compound probability structures (also determined by K and L) is introduced, which represents physical symmetry for these cases. 2.

CONDITIONAL PROBABI LITY.

Given a probability structure K with a probability measure P defined on the corresponding Lindenbaum algebra of sentences, we can introduceK the concept of conditional probability. If ~, ~ are two sentences, we may define, as usual, 2.1

,

whenever

PK(1/! )

'* 0 .

Remember that PK ( ~) = u (Mod K ( P » where u is the correspondi ng measure on sets of models. Thus, this definit-ion is equivalent to defining PK (p I 1/) as, 2.2 PK(oi> I 1/!)=P (1l)=jl' (Mod ModK(1/!,(1l), ModK(1/!) where the measure u ' defined on subsets of Mod K (1/-.) is the restriction of u to Mod K (~ ). A few remarks about this concept are in order. 1) We could be tempted to write P(p IK) instead of PK(
106

ROLANDO CHUAQUI

2) If there is a ut~que inv~riant measure ~ on the cr-field of subsets of K (a simple probability structure; flf, we may be able to define conditional probability directly using 2.2 ~nd the probability structure MadK (\f). If there is a GMad (If) -invariant measure ~ , it will coincide with the restriction of~, ~'.. K 3) I would like to remark that this uniqueness of invariant measures for simple probability structures is not a rare phenomenon. As a matter of fact, in all cases which I have considered and are of actual use, there is a unique invariant measure. I have not been able to think of examples where a real situation is described and the measure is not unique. 4) It may be possible, in some cases, to lift the restriction that PK( 1J-) f O. This would be possible, if there were a probability measure defined directly on subsets of ModK( \f). For instance, in Example 3 of Chuaqui 1977, Section 6, it would be natural to define, I/2, for a f b,

PK(I{a) II{a) v I{b))

although PK{I{a) v I{b)) = O.

3. FREQUENCY MODEL, In this section, I construct a model to give an account of classical statistical methods of hypothesis testing and estimation. These methods are described in Barnett 1973, Chapter 5. In this case, the basic model is constituted by repetitions of the same experiment. The compound probability structure is obtained as follows: Let K be the set of outcomes of a probability structure. This K represents the experiment which is repeated. Each repetition is indexed by an element of an infinite set T. Since there is no causal connection between the repetitions of the same experiment, no relation is assumed between the elements of T. We also could say that we have the causal structure (T,~> with:::' the identity relation. (t~t'may be interpreted as: what happens at t influences what happens at t'.) Our compound probability structure is, then, TK (i .e. TK is the set of compound outcomes). I assume that there is a symmetry relation ~ between subsets of K which represents invariance under the natural laws of the phenomenon (see Chua qui 1977, Sections 1,3). I shall define a new equivalence relation ~ which serves the same purpose for TK: 'U will be based on ~K and the automorphisms of (T,= > (i.e. the permutations of T). Then, we can obtain a ~ - invariant measure ~T on subsets of TK, if there is a ~K -invariant measure ~ on subsets of K. For A::' TK and t

E T, let

A.t

=

{oW: oEAL

If A, B ~TK, we define, A ~ B iff there is a permutation of T, h, such that for all At

t we have

'UK Bh (t) •

As in the case of simple probability structures, events will be sentences ( or rather elements of the Lindenbaum algebra) of an appropriate language. Then, we

107

FOUNDATIONS OF STATISTICAL METHODS der me

for

sentences

and P (
rK

l/J of this language

,

In the

K

language



'V T l/J by ModT (4))'VMod T (l/J), KKK

that we need, it should

be

possible

to talk about sequences of simple outcomes (i.e. of elements of K). Let L be the language for K. We call Lsthe language for TK that we shall introduce. For each F E TK , tion for formulas of satisfies $. T Let FE K; then and R¢ = { .e : F (t) 1=

we shall define a relational structure Ot- F and satisfacLSin O(,r Then, we shall say that F satisfies ¢, if O(.,F ~ = (T,

R¢> pES ' where \ is the

set

of sentences of L

L

p}.

The language L has the logical symbols and variables for [wlw plus the indiS vidual constant 0 (which stands for the number zero), the unary operation S (for succesor), and the binary relation < (for less than). As nonlogical constants we have the unary predicate p for each sentence :p of L. An assignment for L is a function from the variables into the natural numS bers. For each one-one sequence x E wT , assignment and formula ~. of L we S define O(.FF x 1). {read satisfies ¢ in (Otf-, x I) by recursion as follows. In the fi rst p1 ace, for each term T • we extend n to T:

[n]

n,

n

n (0)

= 0

n (ST) =n (T) +

Then: (i) (ii)

if

is T < a (or T = a), then x ~ [n] iff n(T) < n (a) (or 6(T) i f . is 4> (T), then 1);

"'F F

6(0)) ;

otl

x 1/.{ 6] iff X: (T)E R¢; 6 (iii) for negation, disjunction, and conjunction, same clauses as usual; (i v) if l/J = 3 v e, then

"n.

~ F x l/J[ 6J if there is an I'l E W such that Ot. -r:F x l/J! n( t1 (~) is the assignment which coincides with 6 in every variable except rly) v where it assigns n .

1\

For each one-one Mod

x E wT , and sentence 1); of ot F F x ~} •

(1j;) = { F :

where (possi-

s'

L

r K,x: As for simple probability structures, we define

T

(p ). Mo~ K K, x The a-field 11)- of subsets of TK where the measure should generated by these sets ModT (1/) • K. x 1j.

r'V ¢ if K, x

A measure on this a-field

Mod

r K, x

11-

(1jJ)

invariant under

T

K

is

be defined is that

the product measure ~T

of

the measure u defined on the a - field M generated by the sets ModK (¢ ) for 4> a sentence of L,and invariant under "'K' We then defi ne PK, x ll/JJ=

108

ROLANDO CHUAQUI

llT (ModK, x (~.))

for every sentence

\j.

of Ls

.

Bernoulli's law of large numbers can be expressed and proved in this representation. We have, for each real number E > 0, a sentence of LS that expresses that the re 1ati ve frequency of the truth of the sentence jl of Lin the n fi rst terms of the sequence x differs from PK (~) by more than E. This sentence can be written by (*) V (3:mV(v
-

I~ PK (.p)1 ~E where 3~mv e(v) is "there are exactly m v's such that elvl". We abbreviate by 1 FiLn(.pJ - PK(.p) I ~ E.

(*)

Then, Bernoulli's law of large numbers can be expressed as usual by: Fan eveny E > a and eveny 6equence x E wT, lim P
have

to use the full

wl'JJ

The sentence which says that the limit of the relative frequency of the truth of1> in the sequence x is different from PK (1)), abbreviated by h n (
Thus, Borel's law of large numbers can be expressed by PT (Fnn(<jJ) -+PK (et>1) " O. K, x These laws can be proved in the usual way, since the measure . ~is the product measure wjl. All other laws of large numbers and central limit theorems also can be obtained. In this type of models, the classical methods of estimationand hypothesis testing can be justified. I shall illustrate this with an example. My discussion follows closely Lucas (1970), Ch. V. Let us suppose we have a coin that looks unbiased and that we have no other relevant information about it. The natural simple probability structure which describes the possible outcomes of tossing the coin is that which assumes the coin's being symmetrical with weight distributed evenly between the faces. Thus, we assume a simple probability structure K defined as KoofExample 5 in Chuaqui 1977, Section 6. The reasons for assuming this model may be varied, just as the reasons for accepting any scientific hypothesis are varied. Among these reasons we may count, for instance, past experiences with similar coins. We now proceed to test this hypothesis. In order to do so, we toss the coin The probability that the frequency of, say,heads in these tossings is computed by building the compound probability structure wK (it is really enough with nK) and proceeding as in the Frequency Model constructed above. If this probability of the actual outcome is very low we reject the orign times for some large number n,

FOUNDATIONS OF STATISTICAL METHODS ina1 hypothesis that K is the adequate simple probability structure, The ability level at which we reject the hypothesis is arbitrary. However, the is justified (cf. Lucas, 1970, Ch. V) because given any significance level obtain an n large enough where this level can be attained. Thus, there is quence of events with probability approaching zero,

109

probmethod we can a se-

If we reject the original hypothesis, using methods of estimation, we may assume a new simple probability structure K' as a model for the coin tossing, This K' has to assign a reasonable probabil ity (using again WJ<') to the actual 0 bserved frequency. In general, we prefer a K' which maximizes this probability. This sole criterion, however, does not determine uniquely K'. In particular, we limit the class of possible simple probability structures to those which satisfy the laws of physics. It would take us too long to discuss methods of estimation, so I will not enter into this matter further.

4. BAYESIAN MODEL The model for Bayesian methods (see Barnett stituted as follows:

1973, Chapter 6) is con-

The index set T has two different elements, say to' t 1, ordered by a relation which is a simple ordering. Suppose that to :s.t 1 , At each point in T we make a choice, the choice at t l depending on that at to' At to we have a probabi 1ity structure Ka. For each outcome Ol,E KO that may be chosen at to' the r e is a probability structure Kat from which an outcome is chosen at Xl when Ol is chosen at to' We ass~me, for simplicity, that there is one language L that is appropriatefor Ka and all the Kot's. We assume equivalence relations'Vr and'VKa. defined between subsets of Ka and Kotand invariant measures ~O and O~~defined on the appropriate fields of sets.

~,

The set of compound outcomes tl is the set of those functions 6 whose domain is T and such that 6[t O) E KD and 6[t l ) E K ). 6[to As in the case of the frequency model, we define for each A cHand t E T, ~ =

{6 (tl : 6

We also introduce, for at A(ot)

=

{g{t

E A}

E~,

) : 9

E

A ~H A

A

g{t

= ()t}

O) We now define an equivalence relation 'V between subsets of H that represents the relation of physical similarity. In this case,
If A , B ~ H , we define: A'V B iff the following four conditions are simultaneously satisfied:

(il

110

ROLANDO CHUAQUI (ii)

For every Ot

E At

A(O[)

(iii)

For every(}ZE

"v

"i<. t

=

f

0

we have

B (~).

0

we have

Ka;.

- At

0

we have

Kat at

"v

We now have to obtain an ~ (A) is defined by

~(A)

IJL

o "'K

B(~)

then

t

K

o

For everyOlE B

It is easy to see that

n B

At - B t

A(~)

(tv)

o

is an equivalence relation between subsets of H. "v -

invariant measure

~or..(A(or.))

d

~

on subsets of

tl.

Let

A~

H,

~O·

At

o

For B to be ~ - measurable, it must belong to the a-field of subsets of H genera ted by the sets A ~H such that At is ~O - measurable and the function h : At ... [0,1] defined by 0

o

is

~O

h(Ot) = ~ot. (A(oc)),

- integrable.

The measure

~

is clearly

"v -

invariant.

Let us now see which are the subsets of II for which we wish ~ to be defined. Events will also be, in this case, sentences in a language. Let L be the language for ~ and the Kat's. For each

6 E H we define the structure, ot

6=

(T, ~ , R¢ ) ¢ E S

where S is the set of sentences of Land R ¢ = {t : t: E T and 6(t) F

¢}

Our language LH will contain the usual logical symbols (in L"w or L ) plus w w1w the binary predicate;:, and a unary predicate q; for each L - sentence ¢. For a sentence 1/1 in LII' we defi ne Mod (1/1) = {6 : 6 E Hand G7l: F 1/1}' H

6

The a- fi el d Ma wi 11 be that generated by sets of the form Mod a (ljJ). I do not Know, however, whether all sets in ftlH will be ~- measurable. If these sets are ~ - measurable, Beyes theorem is easily derivable using conditional probability as defined in Section 1. Most uses of Bayesian methods can be justified on the basis of this model . Again, I shall illustrate this by an example. In this case, the example is taken from applications to medical diagnosis (see Lusted 1968). We assume that a doctor faces a patient who has one of the diseases EO' ... , En_1 and presents symptoms

111

FOUNDATIONS OF STATISTICAL METHODS He wants to know what is the probability of the

S ..

1 PIE .IS.J for J. < n • .-L

patient's

having E;. ~

i.e.

j

KO is the class of structures of the form Oto =( P,EO .... ,En_l,O) where P is the set of all relevant patients. EJ. is the subset of P with disease EJ. and 0 is a subset of one element of P (i .e. the patient who faces the doctor). The constant part of K Ois (P, EO ' ... En_l ) and the variable part is constituted by the stru£ tures (P, 0). For 0 ~ E. , Kor; has the structures (E., So, ... , S i- 0') where .{.

0

_.-L

m-

Sj is the subset of EJ. that contains the patient~

with disease EJ. and presenting symptoms Sj ; 0' is a subset of one element of{ EJ. (the actual patient). Keto has

- -

-

-

constant part <EJ.' SO' .... Sm_l) and variable parts <EJ.' 0'). In order to have just one language L for K Oand each Kor we expand the structures adding empty relations. 0 In this language L , to say that the patient has disease EJ. ' we can use 3 x (EJ.(X)

A

Of x) r.

where EJ. and 0 are the predicates which correspond to EJ. and O."The patient has disease EJ. and symptoms Sj " is translated by 3x(EJ.fx) A O(X)) A 3xfSj(x) A 0' «n. Ka is a simple probability structure for the choosing of a sample of one element from a population (see Chuaqui 1977, Section 6, Example 1). Similarly for K (JC' Thus, we have probabi 1i ty measures "o for K and).lOt for K", and we can O

o

0

define our measure ).l.

0

Let us abbreviate by EJ. the predicate in Ldcorresponding to 3X(EJ.(X) and by Sj' that corresponding to 3X(Sj(X) A O(X)). The probability we are interested in is

A

Notice that to and t 1 are definable in L a- Therefore E[(to)and Sjft1) be expressed by sentences. This probability can be computed by Bayes theorem P(E,(tO)) . P(S,(t I E.lt O)) P(E-ft ) IS.(t =.(. 1 1) .-L O l)) .-L j kk. < n PIEk. (to)) • PISjft l) I Ek. (to))

O{X))

can

We notice that in this case the structures KOand Kat have been clearly deo termined and that it is possible to estimate and test the corresponding hypothesis. For instance, the proportidn of patients with disease EJ. can be estimated from the actual frequency of observed cases of this disease. In a similar way we can proceed for Kat . It is Clear that we can also use other factors for the ac-

o

ceptance of this hypothesis.

~or

instance, biological knowledge about the disease.

The main difficulties with Bayesian rrethods in other cases are precisely

the

112

ROLANDO CHUAQUI

lack of one or both of these requirements: that there be no clear models for the determination of the probabilities or that it be impossible to test the hypothesis, especially that which'determines the a priori probabilities. The first of these is dangerous because it may happen that in the appropriate model there is no probability measure possible to define. The other problem, namely the impossibility of testing the hypothesis especially applies to KG' which determines the "a priori" probability) is crucial. But it greatly diminishes the reliability of the method.

( this not so

It is to be noted, that according to my model there may be other methods of testing hypotheses besides those based on sampling or frequencies.

5. COMPOUND PROBABILITY STRUCTURES. The general notion of a Compound Probability Structure, which will be introduced in this section, includes both models described in the previous sections and models for stochastic processes. I will only describe these structures and explain how probability is defined for them; the detailed application to stochastic processes is left for another paper. First we generalize the causal dependence (or independence) expressed by T in the models discussed so far. DEFINITION 4.1.- Let R be a binary relation on a set T. Then< T, R> is a caU6al ~ee or simply a ~ee iff the following conditions are simultaneously satisfied: (i)

R is a well-founded partial ordering on T.

(t i )

For each .t ET, RI'R* {.t} is a countable well-ordering.

When Ris a partial ordering, we shall write and x f Y, and b.t instead of R* {.t}.

~R

instead of R, x
S. RY

A tree < T,S. R> is a generalization of the notion of causal dependence. Thus, what happens at some .t E T probabilistically determines what happens at a succeeding 6R~.t. On the other hand, if.t and 6 are not comparable according to s. R ' what happens at .t is independent of what happens at 6. I believe it is intuitively correct that causal ordering is well-founded and inversely well-ordered. DEFINITION 4.2.(t)

For trees (

T,~

R> ,<S,s. P

By recurs ion on ordi na1Sa, T'a = the set of minimal elements of T - U

{TS

{TS

(i i)

To

= U

(i i i)

To

= U {T

(iv) ( T,s-R)

:6 c o } .

6 c a}

S

6 C

~ ( S,s-

implies

6

ET.

a}.

p> iff T

~S.

R ~ p. and

we define:

113

FOUNDATIONS OF STATISTICAL METHODS (v)

Let t E T, then Tt={~: s ETand~
T = T U { t} • t t

It is .:lear that if (T, R ) is a tree and t E T , then ( T RI' Tt ) t, R I' Tt)~ T. Also, the elements of T~ are pairwise incomparable, thus, represent independent moments. T t,

DEFINITION 4.3.(i)

x, y

Let (

T,~

R

be a tree and S

5 is ~R - ~ected iff for every

~

T.

and and,

Then,

x, y E 5,there is a z E 5,

such that

~Rz.

(ii) S is a eomponent of Tiff S is maximal ~R -directed (i,e,S is and if S ~ S' ~ T with 5'::. R -directed, we have 5 = 5'),

directed

THEOREM 4.4,Let (T,~ R) be a :Ute.e.. Then (i) Fotr. e.VVLy x E T theAe i6 a eompone.nt 06 T, 5 ~ueh that XES. (i t ) 16 5 and S' Me. eompon~ 06 T with S n 5' f 0, then 5 = S'. PROOF. (i)

May be easily obtained using Zorn's Lemma.

(ii) Let 5 and S' be components of T, x E 5 n S' and y E 5. Since x, y E 5 and 5 is directed, there is a zE5 such that x, y 2.R z, We have to consider two cases: 1. There is no u E S' such that x < R u, Then S' U {z} is directed hence z E S'. Since y ~ z, S' U {y} is ~R-directed and yES'. 2. There is a u E S' with x
S'.

2.2. There is a u E S' with x ~R u and z ~R u. rected and, hence, z E S'.

Then again, 5' U {z} is di

Now, since y ~R z, S' U {y} is directed and, thus y E S'. We have that S ~ 5'. Similarly we prove S' ~ S. DEFINITION 4,5.- (F, R) is a ea~a£ conditions are simultaneously satisfied: (i)

R is a relation on U F;

~:UtuctW1.e

iff the

following

proved

three

114

ROLANDO CHUAQUI F, then (T, R I' T>

is a tree;

(f i )

if

(iii)

if TEF and (S, RI' S > '" ( T, RI'S > ,then S E F.

T

E

It follows immediately that if T E F and x E T, then T and

x

Ix E F.

DEFINITION 4.6.- K =( I, H) is a compound pltOba.b.u..u:y hbtu.cxWte (i)

I =(

(i i )

H is a set of functions such that if 6 E H, then

if:

R> is a causal structure.

F,~

Va

6E

F.

(iii) For each 6 E Hand;t EVa 6=T the set H(6,x) = {g(x) : 9 E Hand 9 I'T " 6 I'T } is a simple probability structure of a fixed simix x larity type v. (f v)

For each T

E

F , there is an 6

E

H, such that Va 6 " T,

is called the causal structure for K and ,I the set

K.

of compound outcomes of

DEFINITION 4.7.-

Let K= (I, H> be a compound probability structure, Va 6. Then, 6 : 6 E A and VA 6 z: T J,

A CH, T E F, 6 E if and x E

(i)

AT = {

(i i)

A(T) "

{6 I'T : 6 E A }

I

(iii) let A ::. H T ' then, A(6,;t) " {g(x) : 9 E A and 9 I' T;t " 6 I' T } • x We now assume that for each simple probability structure H (6,x)there is given a symmetry relation between its subsets ~ 6,t. We extend this definition to an equivalence relation -v between subsets of H, A, B,such that A ::. ~ and B £ H T" for

T , T'

E

F.

First we introduce a definition of isomorphic simple probability structures. DEFINITION 4.8.- Let K and K' be simpl e probabi 1 i ty structures with universes A and A'. Then, (i)

K~

9

K'

iff K'

9

E

AA',

={ g* q{,

:

9-1

at.

E

A' A and

E K}.

Let ~ K ' ~K' be equi va1ence re 1at ions between subsets of K and K', B £ K and C £ K'. Then B '" C iff K ~ K' and g**B ~ K' C. 9 9 If B"'g C, then Band C are symmetric with respect to '1<:' and the isomorphism g. It is clear that since probabilities are based on the symmetry relations "v K and ""K,if there is an 'OK-invariant measure ilK on subsets of K and K ~Kl then (i i)

FOUNDATIONS OF STATISTICAL METHODS

115

there is an isomorphic measure 11 K, on the corresponding subsets of K ' , I.e. if B S.K and C £K' with 11K (B) defined, then IlK'(C) is defined and 1JK(B) "IlK'(Cl. When there is an'VK-invariant measure 11 K on subsets of K and an"'K' - invariant measure 11K' on subsets of K' and K it K' these measures might not be isomorphic. 9 If 11K' is a wu.qu.e. 'V K, - invariant measure, then 11K and 11K' must be isomorphic. Since, as I mentioned before, (Section 2, Remark 3) uniqueness is not of rare occurrence, its assumption would not be a very strong restriction. In what follows, we assume that if K ~9 K' , then the corresponding invariant measures 11 K and 11K' are isomorphic. T'

E

Next we introduce the notion of isomorphism between the sets liT and d T, for T, F.

DEFINITION 4.9,- Let T, T' E F, conditions are simultaneously satisfied:

Then H

T

;; HT,(h, k) iff the

following

(i)

h is an isomorphism of (T,

(f t )

every t E T and T 6,6' EdT' if 6 I'Tt = 6' f' Tt,. then k(6)I'T'h(tJ ., k(6)f'T'hW' Let:t E T and 6 E H • Then, ifot E H (6,t), ot = jlt) for some j E tIT T T with j f\ T = 6 I'Tt l define gtot) = k(j(t)) for all atE H [6,t). We t T require'that 9 = 9* for some 9 such that

onto (T'

~

I

~ i ,

k is a one-one function of tIT onto H , such that for

(iii)

1ft 6,t) ;;9 H (k( 6), h[t)). We call this

9, 96,t.

Now we define our equivalence relation

'V

DEFINITION 4;10;-

E

Let S, S', T, T'

•

Then

F.

(1) A'V B (T, T', S, S', h, k) iff the following conditions are satisfied: (S,~):;, (T,

(i)

A£I:I

(ii)

h is an isomorphism of ( T, ~)

T,

B£H

T"

~ H (h I'S, k). S S' For every tES and 6 E

s ».

onto ( T', ~) and S'

(iii) H (tv)

A( 6,t)..

(v)

For every t

E

96,t

T - Sand

H

S'

B (k [ 6).

hW )

6 E ,I T '

A[ 6,t)'V 6,t of(6,t)

(vi)

For every t

E

T' - S' and

6'

E

H , ,

T

h*S

116

ROLANDO CHUAQUI B16' ,t') '1,6' ,t' d16' ,t'). (2) A'VB iff for some T, T', S, S', h, k.we have A'VB

IT, T', S, S', h, k.l.

We have that A'VB is determined by the isomorphisms of the corresponding trees, the equivalence relations '1,6 t and the isomorphisms between the simple probabil ity structures H (6,t). ' THEOREM 4.11 (i ) 'V.u, aYl equivaleYlce Jte1..a.UOYl (t t ) I6A'VB IT, T', S, S', h, k.), theYl, 60JteveJtyU~Tw.uhUEF AlUl 'V Blh*Ul IU, h" U, U o s , H" uns', h I'U, k.l'd U)'

we have

IYl paJtt£culaJt we have that 60Jt eveJty t E T. A1Ttl 'V B1T'h{t)) and Al'Ftl 'V B(T'h(tl)'

The proof is easy. We now define a measure u on subsets of Ii which are subsets of .-IT for some T, and invariant under 'V. First define P on subsets of :iT for a fixed T. We asT sume that for t E T and 6 E HT,there is a measure 1l ,t defined on subsets of H 16,t)and invariant under

DEFINITION

6

'V 6,t'

4.12.-

(i) Fi rst defi ne measures P and "e on subsets of Ii T ITtl t each t ET a with a ordinal, by recursion on o.

and H T ITt)

for

(0) a = 0 , then Ilt=~t =1l6,~ 1l6,t is the measure on H (6,t). Notice that in case t E TO' >l16,t) = HI6' ,t) and 1l6,t = P6',t for any 6, 6' EdT' (1) a=e + l. Pi': is the product measure, II ( ~
iJt

j

(A1Tt)) =

1l6,t lAI6,t)) d ilt

A(T )

t

(This definition is possible provided A1T

t)

are 1l6,;(; -measurable and the function gl6 l'Ttl (2) in a. Let measure

0= t~

"s

U

=

1l6,t(A(6,tl) is

-measurable, the sets AI6,t)

t

"c - integrable.)

a> O. Let S be a component of T and

e.

E Sn T

with

t~

<

t

e E wa

< t for all ~ < w.

t~+l

a sequence cofinal Define for A(S)

the

~

lA(S)) = lim~ ... ooPt. IAIT t.)) ~

(This limit ~t.(A1T~)) ~J.lt. ~

is Il

g defined by

~

~

exists and is independent of the )) for all ~<w,l l(A(Tt

+

~+1

choice of

e~

and

t~,

because

FOUNDATIONS OF STATISTICAL METHODS Define

~t

n

117

as the product measure, is a component of T

(~S : S

t)

Define ~t in the same way as for succesor ordinals. (ii) Definition of ~T" Let a be the first the length of T). There are two cases

s+

y

such that

T'y = 0 (a is

Defi ne ~T as the prod uct measure T )• S (2) a = U a> O. Let S be a component of T. Define ~S as in the tion of ~T for limit ordinal. ~T is defined as the product measure (1)

0

=

n

1.

(~.6:.6 E

n( (i i i) Defi ne

~S : S

E F.

by

= ~T (A).

We assume, as before, that if H(6,t) '!! .-I(6', isomorphic to ~6' ,t' (see remarks before Def. 4.9). THEOREM 4.13.-

Le.t AS. H

A'\, B we. have. ~T(A) = ~T' IB)

T,

,

A(T '\, B1T'h(t)) t)

then

t'),

~6,t

BS H

a.nd,

, A and B ~- me.a.6Ullable.. Then T, he.nce., )l(A) = ~ (B).

Let A'V B(T,T' ,S,S' ,h,k,G);

(*)

defini-

a component of T ) •

on subsets A of H which are subsets of 1i T for some T

~

u (A)

PROOF.

called

is

-i6

by 4.11, we have

and A(Tt) '\,

for every t E T.

(T'hlt))

We shall prove by induction on a for t ETa' that

(0)

B{Th(tl1 (i)

0=

=

~h[t) (B(T'h(t)))

~tfA[Tt))

=

~h[t) [B(r' h(t))

and

).

O. Then IJt = ~t = )l6,t' A{Tt] = B(T'hW] = O,and A(Tt] = A{6,t), hIt)) for any 6 E A, 6' E B. There are two cases:

= B(6', t

~t (A[6,t))

(ii)

)It[A[Tt))

E

.=..

ThenA[6,tJ "'96,tB(k(6), hit)) and hence, (B(I<[6) , h(t))).

by

assumption,

= ~hW

t ¢ S. Then

h[t)

¢ S'. Hence

iJt (A{6,t)) = 1 = iJh(t) (B[6', h(t))) • (1)

(j

=

s

+ 1.

By induction hypothesis and (*), we have iJ.6 (A(T.6)]

= iJ

(B(T'h{.6]]

h(.6)

1 for any s

: .6 . 6[A[T)) .6

~

E

E

TS' .6 <

c,

To and .6 < t : .,

~h{.6) (B[T'hfd hf .6 ) E T'Sand h{S)
118

ROLANDO CHUAQUI

We also have, il"t(A(ft))

=

j

116,t(A(6,t)) d llt

A(Ttl

=1

il"hlt) (BCf'hrtl))

116,hlt) (B(6,h(t))

dllh(tl'

B(T'hit; )

We have by (*) and the induction hypothesis llt(A(Tt))

= llh(t) (B(T'h(t))'

In order to prove ii"t(A(Tt )) = ilhrtl(B(f'h(t))) cases:

we have to distinguish two

(i) t E S; then hIt) E S'. Since (S,~) ~ ( T, ~), if ¢ ~t, ¢ES. Similarly for h(t!. Thus, H(6, ¢) ~ rlUd6), h(¢)) and, hence llt is isomorphic to llhltJ' Also, for 6 E A,

But, 11..

(A(T

t))

e

BIT'h(t))'

Hence the result follows. (ii) t

~

S; then

h{t) ~

S'

Then, 116,t(A{~,t))= 1 = 116',h(tl(B(n',h(tl)).

Hence, (3) a = U a> O.

By induction hypothesis and (*) we have

ll¢{A(T¢)) = llh(¢J (B{T'h{o)))

Hence, from the construction of llt(A(Tt))

The result for ~t and

llt

for any .s < t: and

llhlt)

= llh{t) (B(T'h(t)))' il"h(t)

is obtained as in the case of succesor ordinals.

From these results we easily obtain the theorem. •

FOUNDATIONS OF STATISTICAL METHODS

119

Finally, we have to introduce an appropriate language, in order to defi ne which are the events. The procedure is similar to that used in the Frequency Mod el (Section 3). For each FE H, we define the corresponding model at F

u F, s, R ' RI{>) ¢ESem,

= (

Where Sem is the set of sentences of the original language { t: F(tl F }.

L,

and

R



=

The language Ld for H conta~ns variables for countable ordinals, a binary predicate ~ and a unary predicate for each E Sem, .We define as in Section 3, 01- F x I/J [6J for x a sequence having the following characteristics. x is a s~ quence with domain a countable ordinal and range in T, where T = Vo FE F. x has the further properties: (i)

implies x(a)~R x(Bl ,

a ~B

(f t ) if for some t E T there are a, B such that there is a y such that x(y) = t.

x{o)~ t

The definition of c7l'F F x I/J [6J follows the same lines of easy to reconstruct. As there, i f

Mo~

PK(J

x( J

= {

~x{B),

then

Section 3 and it is

F : otl' F x 1>}, we defi ne

= 11 ( M0<1c, x ( l l .

REFERENCES. V. Bar.nett

1973

Comparative statistical inference,

John Wiley and Sons Ltd., London.

R. Chuaqui 1977

A .6ema.ntiea.l de6inition 06 plloba.bility,

Arruda, North-Holland Pub. Co., Amsterdam, pp. 135-167. Model Theory and Computability,

in Non-Classical Logics, da Costa, Chuaqui (eds) ,

P. Halmos 1950

Measure Theory,

Van Nostrand, New York.

J. R. Lucas 1970

The concept of probability,

Oxford U, Press, Oxford,

L. B. Lusted

1968

Introduction to medical decision making, Charles C. Thomas, Spring-

field.

120

ROLANDO CHUAQUI

Instituto de Matematica Pontificia Universidad Cat6lica de Chile Santiago, Chile.

MATHEMATICAL LOGIC IN LATIN AMERICA A.I. Arruda, R. Chuaqui, N.C.A. da Costa (eds.) ©North-Holland Publishing Company, 1980

PARAMETERS IN THEORIES OF CLASSES Manue£ CO!lJULdd

S We wi 11 denote by CE and CE the jm~ predicative and predicative comprehension schemas re-

ABSTRACT.

spectively, and by

CE and

o

CES the corresponding 0

versions of this schema without parameters. Us i ng some ideas from Levy (P~etenh in Comp~ehen6ion

Axiom Schema!.> 06 Set TheMrj, Proceedings of

the Tarski Symposium, L. Henkin and others (eds.).

American Mathematical Society, 1974, 309 - 324) we prove that there exist finite sets of sentences C,

S

C such that CE and CE may be rep 1 aced, 2 assuming the pa iring axiom (there exist the unordered pair of two sets, and it is a set), by CEo + C, and S CE + C respectively. 2

and

INTRODUCTION. The essential component of all the theories of classes known from the literature is the comprehension schema. This schema allows us to define some particular classes and operations. A priori, it might be thought that this possibility is based upon the parameters that occur in this schema. Contrary to expectations, we will prove in this paper that a class theory with a comprehension schema without parameters is equivalent, on the basis of some very weak hypotheses, to a class theory with unrestricted comprehension schema. Specifically if we call CE and CE S respectively the impredicative and predicative versions of the comprehension schema for classes, we will replace them by sets XE1 and XE2 in which no parameters occur. In these sets it appears only one schema, Zermelo's Aussonderungsaxiom without parameters in its impredicative and predicative forms. If we consider instead of this schema the impredicative and predicative comprehension schema for classes without parameters, denoted by CE 5. pred 50 that replace CE and CE and CEo respectIvely we get sets xE2 and xE2 and whose schemas will be CEo and CE5 respectively. These sets are easily obtained from ~XEl and XEired The proof in theories with proper classes is a modification of the proof in Levy 1974. From these results we get some unexpected facts such as the finite axiomatizabi1ity of CEo over CEo Also we obtain a simplification of the proof of an unpublished result by Tarski (cf. Tarski 197+). The paper begins with an introductory section called "Class- theoretical pre121

122

MANUEL CORRADA

liminaries". Section 1 is concerned with the above mentioned problems for impredicative theories of classes. The analogous problems for predicative class theories are discussed in Section 2.

§O. CLASS-THEORETICAL PRELIMINARIES, We use throughout terminology from ~~-theo~etieal ~y~t~, i.e. systems admitting classes that are not elements of any element of the universe; this classes are called p~op~ ~~~. All the systems formalized in this paper will be formalized in the formal ism of first order logic with equality with a descriptor operator U. Details of how to build such a formalism are given explicitely in da Costa, 1979. The variables will be denoted by lower case italic letters. q,. 1/1. e• . . • will be used as metalogical variables that represent formulae. The notions of formula and term are defined recursively as usual. If x is a variable and q, is a formula, then Uxq, is a term. T, TO' T 1 •••• will be metalogical denotations for terms. For every q" the set of all free variables of q, , fv q, , is defined as usual. fv T is the set of all free variables of the term T. The set of all formulae is denoted by W, and the set of all terms by A. The set of all formulae with at most n free variables is denoted by wn ' Given three sets ne w, ~ e wand we w ; if n is derivable from ~ on the basis of w we write ~ .... rL. ~ and n- are called logieaUy equivaLent on the

bM~

00 W, in symbols

Gi ven a

T

~

w

~=wn,

if

~ ....

w

nand

n ....

~

w

e Wand awe w we set

Assume q, is a possible definition in ~ + W. Then q, has the form <-+ W. We will write Class w~ [T] instead of 3xw E Cnw[~]'

x=

Set-theoretical notions and symbols are either standard, or specified. Relations are treated as in Godel 1940. If ~ is a relation the Jt-image of x, Jt*{x} is the class {y: t q,« > E Jt} where (y,x> is the usual ordered pair. We use the following abbreviation: S x = 3u[x Eu).

S x expresses the fact that the object represented by x is a set: w S= {q,S: q,E w} is the set of all predicative formula, where q, S is the formula obtained from the formula