Intuitionistic Logic, Model Theory and Forcing (Studies in Logic and the Foundations of Mathematics)

STUDIES I N LOGIC AND THE FOUNDATIONS O F MATHEMATICS

Editors

A. HEYTING, Amsterdam A.MOSTOWSK1, Warszawa A. ROBINSON, New Haven P. SUPPES, Stanford

Advisory Editorial Board Y . BAR-HILLEL, Jerusalem K. L. D E BOUVBRE, Sanra Clara H. HERMES, Freiburg i/Br. J. HINTIKKA, Helsinki J. C. SHEPHERDSON, Eristol E. P. SPECKER, Zurich

N O R T H - H O L L A N D P U B L I S H I N G COMPANY AMSTERDAM-LONDON

INTUITIONISTIC LOGIC MODEL THEORY AND FORCING

MELVIN CHRIS FITTING Herbert H. Lehman College The City University of New York

1969

N O R T H - H O L L A N D P U B L I S H I N G COMPANY AMSTERDAM-LONDON

Q

NORTH-HOLLAND PUBLISHING COMPANY, AMSTERDAM, 1969.

All Rights Reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without the prior permission of the Copyright owner.

@$g#.g$ Library of Congress Catalogue Card Number: 79-102718 SBN 7204 2256 6

PUBLISHERS

NORTH HOLLAND PUBLISHING COMPANY - AMSTERDAM NORTH HOLLAND PUBLISHING COMPANY LTD - LONDON

PRINTED I N THE NETHERLANDS

ACKNOWLEDGMENTS

I would like to express my thanks to Professor Raymond Smullyan for his guidance and encouragement during the preparation of this thesis. I would also like to thank the library staff at the Belfer Graduate School of Science for much friendly unconventional assistance. This work was supported by National Aeronautics and Space Administration Training Grant NSG(T)144, and by Air Force Office of Scientific Research Grants AFOSR68-1375 and AFOSR433-65. With the exception of a few minor corrections and changes, this work duplicates the author’s Doctoral Dissertation, written at the Belfer Graduate School of Science, Yeshiva University, and submitted June 1968.

to my parents

INTRODUCTION

In 1963 P. Cohen established various fundamentd independence results in set theory using a new technique which he called forcing. Since then there has been a deluge of new results of various kinds in set theory, proved using forcing techniques. It is a powerful method. It is, however, a method which is not as easy to interpret intuitively as the corresponding method of Godel which establishes consistency results. Godel defines an intuitively meaningful transfinite sequence of (domains of) classical models Ma, defines the class L to be the union of the M a over all ordinals a, and shows L is a classical model for set theory [4; see also 31. He then shows the axiom of constructability, the generalized continuum hypothesis, and the axiom of choice are true over L, establishing consistency. In this book we define transfinite sequences of S. Kripke’s intuitionistic models [13]in a manner exactly analogous to that of Godel in the classical case (in fact, the M a sequence is a particular example). In a reasonable way we define a “class” model for each sequence, which is to be a limit model over all ordinals. We show all the axioms of set theory are intuitionistically valid in the class models. Finally we show there are particular such sequences which provide: a class model in which the negation of the axiom of choice is intuitionisticallyvalid; a class model in which the axiom of choice and the negation of the continuum hypothesis are intuitionisticallyvalid; a class model in which the axiom of choice, the generalized continuum hypothesis, and the negation of the axiom of

14

INTRODUCTION

constructability are intuitionistically valid. From this the classical independence results are shown to follow. The definition of the sequences of intuitionistic models will be seen to be essentially the same as the definition of forcing in [3]. The difference is in the point of view. In Cohen’s book one begins with a set M which is a countable model for set theory and, using forcing, one constructs a second countable model N “on top of” M. Forcing enables one to “discuss” N in M even though N is not a sub-model of M. Various such N are constructed for the different independence results. Cohen points out [3, pp. 147, 1481 that actually the proofs can be carried out without the need for a countable model, and without constructing any classical models; this is the point of view we take. It is the forcing relation itself that the center of attention [see 3, page 1471, though now it has an intuitive interpretation. A similar program has been carried out by Voptnka and others. [See the series of papers 22, 23, 24, 27, 6, 25, 7, 8, 26, 281. The primary difference is that these use topological intuitionistic model theory while we use Kripke’s, which is much closer in form to forcing. Also the VoptSnka series uses Godel-Bernays set theory and generalizes the F, sequence, while we use Zermelo-Fraenkelset theory and generalize theM, sequence. The Voptnka treatment involves substantial topological considerations which we replace by more “logical” ones. This book is divided into two parts. In part I we present a thorough treatment of the Kripke intuitionistic model theory. Part I1consists of the set theory work discussed above. Most of the material in Part I is not original but it is collected together and unified for the h s t time. The treatment is self-contained. Kripke models are defined (in notation different from that of Kripke). Tableau proof systems are d e h e d using signed formulas (due to R. Smullyan), a device which simplifies the treatment. Three completeness proofs are presented (one for an axiom system, two for tableau systems), one due to Kripke [13], one due independently to R. Thomason [21] and the author, and one due to the author. We present proofs of compactness and Lowenheim-Skolemtheorems. Adapting a method of Cohen, we establish a few connections between classical and intuitionistic logic. In the propositional case we give the relationship between Kripke models and algebraic ones [16] (which provides a fourth completeness proof in the

INTRODUCTION

15

propositional case). Finally we present Schiitte’s proof of the intuitionistic Craig interpolation lemma [17], adapted to Kleene’s tableau system G3 as modified by the use of signed formulas. No attempt is made to use methods of proof acceptable to intuitionists. Chapter 7 begins part 11. In it we define the notion of an infuifionistic Zermelo-Fraenkel (ZF) model, and the intuitionistic generalization of the Godel M a sequence. Most of the chapter is devoted to showing the class models resulting from the sequences of intuitionistic models are intuitionistic ZF models. This result is demonstrated in rather complete detail, especially sections 8 through 13, not because the work is particularly difficult, but because such models are comparatively unfamiliar. In chapter 8 the independence of the axiom of choice is shown. In chapter 9 we show how ordinals and cardinals may be represented in the intuitionistic models, and establish when such representatives exist. Chapter 10 establishes the independence of the continuum hypothesis. In Chapter 11 we give a way to represent constructable sets in the intuitionistic models, and establish when such representatives exist. Chapter 12 establishes theindependence of the axion of constructability. Chapter 13 is a collection of various results. We establish a connection between the sequences of intuitionistic models and the classical Ma sequence. We give some conditions under which the axiom of choice and the generalized continuum hypothesis will be valid in the intuitionistic class models (thus completing chapters 10 and 12). Finally we present Vop6nka’s method for producing classical non-standard set theory models from the intuitionistic class models without countability requirements [261. The set theory work to this point is self-contained, given a knowledge of the Godel consistency proof ([4], in more detail [3]). In chapter 14 we present Scott and Solovay’s notion of boolean valued models for set theory [19]. We define an intuitionistic (or forcing) generalizationof the Ra sequence (sets with rank) analogous to the Cohen generalization of the M a sequence, and we establish some connections between intuitionistic and boolean valued models for set theory.

CHAPTER 1

PROPOSITIONAL INTUITIONISTIC LOGIC SEMANTICS

0 1. Formulas We begin with a denumberable set of propositional variables A , B, C, ..., three binary connectives A ,v ,3 , and one unary connective -, together with left and right parentheses (, ). We shall informally use square and curly brackets [, 3, {, for parentheses, to make reading simpler. The notion of well formed formula, or simplyformula, is given recursively by the following rules: FO. If A is a propositional variable, A is a formula. F1. If Xis a formula, so is X. F2, 3,4. If X and Yare formulas, so are (XAY), (Xv Y ) , ( X I Y ) . N

Remark 1.1: A propositional variable will sometimes be called an atomic formula.

It can be shown that the formation of a formula is unique. That is, for any given formula X , one and only one of the following can hold: (1). Xis A for some propositional variable A. (2). There is a unique formula Y such that X is Y. (3). There is a unique pair of formulas Y and 2 and a unique binary connective b ( A , v or 3 ) such that Xis (YbZ). We make use of this uniqueness of decomposition but do not prove it here. We shall omit writing outer parentheses in a formula when no con-

-

20

PROPOSITIONAL INTUITIONISTIC LOGIC, SEMANTICS

CH. 1 6 2

fusion can result. Until otherwise stated, we shall use A , B and C for propositional variables, and X , Y and Z to represent any formula. The notion of immediate subformula is given by the following rules: 10. A has no immediate subformula. 11. X has exactly one immediate subformula : X . 12, 3,4. (XA Y), (Xv Y ) , ( X I Y ) each has exactly two immediate subformulas: X and Y. The notion of subformula is defined as follows: SO. X i s a subformula of X. S1. If X is an immediate subformula of Y , then X is a subformula of Y. S2. If X is a subformula of Y and Y is a subformula of 2,then X is a subformula of Z . By the degree of a formula is meant the number of occurrences of logical connectives ( , A ,v ,I) in the formula.

-

N

0 2.

Models and validity

By a (propositional intuitionistic) model we mean an ordered triple (9, 9, k), where B is a non-empty set, W is a transitive, reflexive relation on 9, and k (conveniently read “forces”) is a relation between elements of 9 and formulas, satisfying the following conditions: For any re9 PO. if T I=A and TWA then A k A (recall A is atomic). PI. Tk(Xr\ Y) iff r k X a n d r k Y. P2. Tk(Xv Y ) iff TkXor l‘k Y. P3. T k - X iff for all A E such ~ that r W A , A F X . P4. r k ( X x Y ) iff for all A E 9 such that r W A , if A k X , then A k Y.

Remark 2.1: For T e 9 , by r* we shall mean any A E such ~ that TWA. Thus “for all r*, q(T*)” shall mean “for all A e 9 such that I‘WA, cp (A)” ;and “there is a T* such that cp (r*)” shall mean “there is a A E 3 ’ such that TWA and cp (A)”. Thus P3 and P4 can be written more simply as: P3. Tk-Xiff for all T*, r * ) c X P4. r k ( X = Y ) iff for all r*,if r*I= X , then r*k Y.

A particular formula X is called valid in the model (9, W,k) if for all r E 3, T k X . X is called valid if X is valid in all models. We will show

CH. 1 fj§ 3,4

MOTIVATION. SOME PROPERTIES OF MODELS

21

later that the collection of all valid formulas coincides with the usual collection of propositional intuitionistic logic theorems. When it is necessary to distinguish between validity in this sense and the more usual notion, we shall refer to the validity defmed above as intuitionistic validity, and the usual notion an classical validity. This notion of an intuitionistic model is due to Saul Kripke, and is presented, in different notation, in [13]. See also [18]. Examples of models will be found in section 5, chapter 2.

53. Motivation Let (9, 9, k) be a model. Y is intended to be a collection of possible universes, or more properly, states of knowledge. Thus a particular r in 9 may be considered as a collection of (physical) facts known at a particular time. The relation W represents (possible) time succession. That is, given two states of knowledge r and A of '3, to say r W A is to say: if we now know r, it is possible that later we will know A . Finally, to say r I. Xis to say: knowing r,we know X , or: from the collection of facts r, we may deduce the truth of X. Under this interpretation condition P3 of the last section, for example, may be interpreted as follows: from the facts r we may conclude - X if and only if from no possible additional facts can we conclude X . We might remark that under this interpretation it would seem reasonable that if r k X and r@Athen A i= X,that is, if from a certain amount of information we can deduce X,given additional information, we still can deduce X,or if at some time we know Xis true, at any later time we still know Xis true. We haverequired that this holds only for the case that Xis atomic, but the other cases follow. For other interpretations of this modeling, see the original paper [13]. For a different but closely related model theory in terms of forcing see [5].

0 4. Some properties of models Lemma 4.1: Let (9, W ,k) and <S,9, I=') be two models such that for any atomic formula A and any r e Y, r C A iff r k' A. Then k and C' are identical.

22

PROPOSITIONAL INTUITIONISTIC LOGIC, SEMANTICS

-

CH. 1 5 4

Proofi We must show that for any formula X ,

r x r vx. This is done by induction on the degree of X and is straightforward. We present one case as an example. Suppose X i s Y and the result is known for all formulas of degree less than that of X (in particular for Y). We show it for X : r P X c> r P Y (by definition) e (W*) (r*pC Y) (by hypothesis) 9 (W*) (r* pc’ Y ) (by definition)

-

-

erv-y

OrP’x.

Lemma4.2: Let B be a non-empty set and 9 be a transitive, reflexive relation on 9. Suppose k is a relation between elements of B and atomic formulas. Then k can be extended to a relation I=’ between elements of B and all formulas in such a way that ( B , W , C’) is a model. Proofi We define I=‘ as follows: (0). if 1 A then r*V A , (1). I’C’ ( X A Y) if r C‘X and r k’ Y , (2). r C ’ ( X v Y ) i f r ~ ’ X o r r ~ ‘ Y , (3). r C’-X if for all r*, r*pC’X, (4). r C’ ( X I Y)if for all r*,if r*C’X, then r*k’ Y. This is an inductive definition, the induction being on the degree of the formula. It is straightforward to show that (9, 9,C’) is a model. From lemmas 4.1 and 4.2 we immediately have Theorem 4.3: Let 9 be a non-empty set and 9 be a transitive, reflexive relation on 9. Suppose k is a relation between elements of B and atomic formulas. Then i= can be extended in one and only one way to a relation, also denoted by b y between elements of 9 and formulas, such that (9, 9, k } is a model, Theorem 4.4: Let (9, 9, I=} be a model, X a formula and r,AEB. If r k X and T 9 A , then A I= X. Proofi A straightforward induction on the degree of X (it is known already for X atomic). For example, suppose the result is known for X , and I‘C-X. By definition, for all r*, r * y X . But TWA and 9 is transitive so any 9-successor of A is an 9-successor of r. Hence for all A*, A* pC X , so A P -X. The other cases are similar.

CH.

1@ 5 , 6

0 5.

23

ALGEBRAIC MODELS. ALOEBRAIC AND KRIPKE VALIDITY

Algebraic models

In addition to the Kripke intuitionistic semantics presented above, there is an older algebraic semantics: that of pseudo-boolean algebras. In this section we state the algebraic semantics, and in the next we prove its equivalence with Kripke’s semantics. A thorough treatment of pseudoboolean algebras may be found in [16].

Definition 5.1 : A pseudo-boolean algebra (PBA) is a pair (9?,<) where 9 is a non-empty set and < is a partial ordering relation on 9 such that for any two elements a and b of 37: (1). the least upper bound ( a ub) exists. (2). the greatest lower bound ( a n b) exists. (3). the pseudo complement of a relative to b (a*b), defined to be ~ that a n x < b, exists. the largest X E such (4). a least element A exists. Remark 5.2: In the context mathematical one.

* is a

Let - a be a*

-A.

A

and v be

mathematical symbol, not a meta-

Definition 5.3: h is called a homomorphism (from the set W of formulas to the PBA (9,<)) if h: W+W and (1). h (XA Y ) = h ( X )nh ( Y ) , (2). h (XVY )= h (X)v h ( Y ) , (3). h ( - X ) = - h ( X ) , (4). h ( X x Y ) = h ( X ) = > h ( Y ) . If (g,<) is a PBA and h is a homomorphism, the triple (37, <, h ) is Calledaa (k&vhnzzk)mo&/fhr the set offonnulas K If Xis a formula, Xis called (algebraically) valid in the model (37, < ,h ) if h ( X )= v Xis called (algebraically) valid if X is valid in every model.

.

A proof may be found in [16] that the collection of all algebraically valid formulas coincides with the usual collection of intuitionistic theorems.

0 6. Equivalence of algebraic and Kripke validity First let us suppose we have a Kripke model (we will not use the name “Kripke model” beyond this section). We will define an algebraic

24

PROPOSITLONAL INTUITIONISTIC LOGIC, SEMANTICS

m.116

model (A?, f , h ) such that for any formula X

h(X)= v

iff forall r E 9 , r t X .

Remark 6.1 : The following proof is based on exercise LXXXVI of [2]. If b c 9, we call b W-closed if whenever l% b and r W A , then A E b . We take for the collection of all 98-closed subsets of 9.For the ordering relation < we take set inclusion G. Finally we define h by

h ( x ) = { r & I r t x ) .. It is fairly straightforward to show that
u (x

2

a) s b xEb

u (x a), u (x a) , x E b u (3’ a), A

A

but

X E ~ so ,

x is 9Z’-closed.Hence XEP, XGP.

The reader may verify that 0 ~ 9 3 and is a least element. Next we remark that h is a homomorphism. We demonstrate only one of the four cases, case (4).Thus we must show that h ( X D Y )is the largest

CH. 1

06

EQUIVALENCE OF ALGEBRAIC AND KRlPKE VALIDITY

X E Bsuch that

h(X) n x < h(Y).

First we show h ( X ) n h(X that is

25

3

(rI r w }n (rI r k x

Y )< h(Y), 3

1 rk Y ) .

Y >c {r

But it is clear from the definition that

if r C X and r F . X 3 Y Y , then r k Y . Next suppose there is some b e 9 such that h ( X ) n b g h ( Y ) but h ( X 3 Y)Y. Since r f X 3 Y, there must be some r* such that r*I=Xbut r*pl Y.Since b is %closed, T*eb. But also r*eh ( X ) , so I'*Eh(X) nb, and so by assumption r * ~ (hY ) , that is I'* /= Y, a contradiction. Thus h (A72Y ) is largest. Thus (97, <, h ) is an algebraic model. We leave it to the reader to verify that the unit element v of 9 is 9 itself. Hence h(X)= v

rkx. algebraic model (g,<, h).

iff forall r e g ,

Conversely, suppose we have an define a Kripke model (9, 92, F.) so that for any formula X h(X)=v

iff forall r e g ,

We will

rtx.

Lemma6.2: Let 2F be a filter in 9 and suppose ( a * b ) $ S . Then the filter generated by S and a does not contain b. Proofi If the filter generated by 9and a contained b, then ([16] p. 46, 8.2) for some CES, c n a < b . So c<(a*b) and hence (a==-b)ESby [16], p. 46, 8.2 again. Lemma6.3: Let S be a proper filter in a and suppose -a#F. Then the filter generated by S and a is also proper. Proofi By lemma 6.2, since -a=(a* A). Lemma 6.4: Let S be a filter in and suppose a # F . Then S can be extended to a prime filter B such that ~ $ 9 ' . Proofi (This is a slight modification of [16], p. 49, 9.2, included for completeness.) Let 0 be the collection of all filters in 9 not containing a. 0 is partially ordered by C . 0 is non-empty since F e O .

26

PROPOSITIONAL INTUITIONISTXC LOGIC, SEMANTICS

CH. 1 8 6

Any chain in 0 has an upper bound since the union of any chain of filters is a flter. So by Zorn's lemma 0 contains a maximal element 8. Of course a 4 8 . We need only show 8 is prime. Suppose B is not prime. Then €or some a l , a 2 M

a , u ~ ~ €a,$B, 9 , a,#B. Let 9, be the filter generated by B and a,, and 9, be the lilter generated by B and a,. Suppose a E Y 1 and ~€9,. Then [16, p. 46,8.2] for some c , , c , E ~ , a,nc,
Now we proceed with the main result. Recall that we have (99, <, h). Let 9 be the collection of all proper prime filters in 9l. Let W be set inclusion E , For any TE9 and any formula X,let r F' X if h ( X ) E ~ . To show the resulting structure (9, 9,k) is a model, we note property PO is immediate. To show P1: r k ( X ~ Y ) iff iff iff iff

~ ( X Y)ET A

h(X) nh(Y)dh ( X ) ~ rand h ( Y ) e r T C X and rCY

(using the facts that h is a homomorphism and r is a Uter). Similarly we show P2 using the fact that r is prime. To show P3: Suppose T b X . Then h ( X ) E r, so

-

-

-

(Vde9) (T G A implies h ( X)EA ) , (Vd E 9) E A implies h ( X )4 A ) , (VA E 9)(TWA implies A j! X ) ,

(r

i.e. for all T*, T* pC X (using the fact that h (- X ) E ~ and h (X)E A imply -h(X)nh(X)~d, so A E A and A is not proper). Suppose T y -X. Then h ( - X ) $ r , or - h ( X ) $ r . By lemma 6.3 the filter generated by r and h ( X ) is proper. By lemma 6.4 this filter can be

cn. 1 $6

EQUrVALENCE OF ALOEBRAIC AND KRIPKE VALIDJTY

27

extended to a proper prime filter A . Then r C A and h(X)€A.So ( 3 A ~ 9(I'WA ) and AtX),i.e. for some r*, I'*kX. P4 is shown in the same way, but using lemma 6.2 instead of lemma 6.3. Thus ('3, W ,k> is a model. Finally, to establish the desired equivalence, suppose first h (X)= v . Since v is an element of every filter, for all TEB, T k X . Conversely suppose h ( X )# v . But { v } is a filter and h ( X ) # { v}. By lemma 6.4 we can extend { v } to a proper prime filter T such that h(X)#T. Thus I ' E 9 and r f X . Thus we have shown

Theorem 6.5: X i s Kripke valid if and only if X is algebraically valid.

CHAPTER 2

PROPOSITIONAL INTUITIONISTIC LOGIC PROOF THEORY

0 1. Beth tableaus In this section we present a modified version of a proof system due originally to Beth. It is based on [2,§ 1451, but at the suggestion of R. Smullyan, we have introduced signed formulas and single trees in place of the unsigned formulas and dual trees of Beth. By a signed formula we mean T X or FX where X is a formula. If S is a set of signed formulas and H is a single signed formula, we will write Su { H } simply as {S, H } or sometimes S, H. First we state the reduction rules, then we describe their use; S is any set (possibly empty) of signed formulas, and X and Yare any formulas: T A

S,T ( X A Y)

F

S, F ( X A Y) S , F X S , FY

A

I

S, T X , T Y

T v

S,T(XvY) TY

F v

S,F(XvY) S, F X , FY

S,T(-X) S, F X S , T ( X 3 Y) S,FX(S,TY

F-

S,F(-X) STYT x S,F(Xr>Y) ST,T X , F Y

S, T X

T TI>

IS,

F=Y

I

In rules F - and F z above, ST means { TX T X E S ] .

CH.211

BETH TABLEAUS

29

Remark 1.1 : S is a set, and hence (S, TX} is the same as {S, TX, T X } . Thus duplication and elimination rules are not necessary.

If U is a set of signed formulas, we say one of the above rules, cal1 it rule R, applies to U if by appropriate choice of S, X and Y the collection of signed formulas above the line in rule R becomes U. By an application of rule R to the set U we mean the replacement of U by U,(or by U,and U, if R is F A , T v or T D ) where U is the set of formulas above the line in rule R (after suitable substitution for S, X and Y ) and U,(or U,,U,)is the set of formulas below. This assumes R applies to U.Otherwise the result is again U.For example, by applying rule F Z Ito the set { TX, FY, F ( Z 3 W ) }we may get the set ( TX, TZ, FW}. By applying rule T v to the set { TX, FY, T ( Z v W)} we may get the two sets ( T X , FY, T Z } and (TX, FY, T W } . By a conjiguration we mean a finite collection {S,, S,, ..., S,,} of sets of signed formulas. By an application of the rule R to the configuration {S,, S2,..., S,} we mean the replacement of this configuration with a new one which is like the first except for containing instead of some Si the result (or results) of applying rule R to S,. By a tableau we mean a finite sequence of configurations V,, V,, ..., Vn in which each configuration except the first is the result of applying one of the above rules to the preceding configuration. A set S of signed formulas is closed if it contains both TX and FX for some formula X.A configuration (Sl, S,,..., S,,} is closed if each Si in it is closed. A tableau V,,V2,...,V,, is closed if some Vi in it is closed. By a tableau for a set S of signed formulas we mean a tableau V,, V2, ...,W,,in which V, is ( S } . A finite set of signed formulas S is inconsistent if some tableau for S is closed. Otherwise S is consistent. X is a theorem if (FX)is inconsistent, and a closed tableau for { F X } is called a proof of X . If X is a theorem we write t, X. We will show in the next few sections the correctness and completeness of the above system relative to the semantics of ch. 1. Examples of proofs in this system may be found in 0 5. The corresponding classical tableau system is like the above, but in rules F- and F I , S, is replaced by S (see [20]). The interpretations of the classical and intuitionistic systems are different.

30

PROPOSITIONAL INTUITIONISTIC LOGIC, PROOF THEORY

CH.202

In the classical system TX and FX mean X is true and X is false respectively. The rules may be read: if the situation above the line is the case, the situation below the line is also (or one of them is, if the rule is disjunctive: F A , T v , Tz).Thus TX means the same as X , and FX means -X. Classically the signs T and F are dispensable. Proof is a refutation procedure. Suppose X is not true (begin a tableau with FX). Conclude that some formula must be both true and not true (a closed configuration is reached). Since this can not happen, Xis true. In the intuitionistic case TX is to mean X is known to be true (Xis proven). FX is to mean X is not known to be true (X has not been proved). The rules are to be read: if the situation above the line is the case, then the situation below the line is possible, i.e. compatible with our present knowledge (if the rule is disjunctive, one of the situations below the line must be possible). For example consider rule F x . If we have not proved X= Y, it is possible to prove X without proving Y,for if this were not possible, a proof of Y would be ‘inherent’ in a proof of X, and this fact would constitute a proof of XI Y. But we have S, below the line in this rule and not S because in proving X we might inadvertently verify some additional previously unproven formula (some FZES might become TZ). Similarly for F - . The proof procedure is again by refutation. Suppose X is not proven (begin a tableau with FX).Conclude that it is possible that some formula is both proven and not proven. Since this is impossible, X is proven. We have presented this system in a very formal fashion because it makes talking about it easier. In practice there are many simplifications which will become obvious in any attempt to use the method. Also, proofs may be written in a tree form. We find the resulting simplified system the easiest to use of all the intuitionistic proof systems, except in some cases, the system resulting by the same simplifications from the closely related one presented in ch. 6 9 4. A full treatment of the corresponding classical tableau system, with practical simplifications, may be found in [20].

0 2. Correctness of Beth tableaus Dejinition 2.1 : We call a set of signed formulas

{TXI, ..., TX,,FYi,

..., FY,}

m.2$3

31

HINTMKA COLLECTIONS

realizable if there is some model (9, W ,1) and some r e g such that C X I , .., k X,,,r pC Y,,..., pC Y,. We say that realizes the set. If {Sl, S,, ..., Sn} is a configuration, we call it realizable if some Si in it is realizable.

.

Theorem 2.2: Let gl,V2,...,V,, be a tableau. If V iis realizable, so is Vi+l. Pro08 We have eight cases, depending on the rule whose application from gi. produced gi+l Case(1): V i is { ..., { S , T ( X v Y ) } ,...I and Vi+, is { ..., {S,TX), {S,TY),...}. Since Vi is realizable, some element of it is realizable. If that element is not (S,T(Xv Y)}, the same element of Vi+ is realizable. If that element is (S,T(Xv Y)}, then for some model (Q,@, k) and some r e g , r realizes {S,T(Xv Y)}. That is, r realizes Sand rC(X v Y). Then r k X or I ' k Y, so either r realizes {S,TX} or {S,TY). In either case Vi+,is realizable. Case (2): Ci is (..., ( S , F ( - X ) } ,...} and %i+l is { ..., {ST,TX},...}. V iis realizable, and it suffices to consider the case that {S,F( X ) } is the realizable element. Then there is a model (9, 9,I=) and a re9 such that r realizes S and r pC - X . Since r pC - X , for some r * E 9 , r*k X . But clearly, if r realizes S, I'* realizes S, (by theorem 1.4.4). Hence r* realizes { S J X } and V i + lis realizable. The other six cases are similar. N

CoroZZury2.3: The system of Beth tableaus is correct, that is, if FIX,

X is valid. Proofi We show the contrapositive. Suppose X i s not valid. Then there is a model (9, W,C) and a r E Q such that r y X . In other words ( F X } is realizable. But a proof of X would be a closed tableau V,,V2,..., Vn in which is ( ( F X } } . But Vl is realizable, hence each Vi is realizable. But obviously a realizable configuration cannot be closed. Hence y IX.

8 3. Hintikka collections In classical logic a set S of signed formulas is sometimes called downward saturated, or a Hintikka set, if

T X AYES F X v YES

e- T X E S

*

and TYES, F X E S and F Y E S ,

32

PROPOSITIONAL INTTUITIONISTIC UxiIC, PROOF THEORY

TXVYES* FXAYES * T - X E S => T X ~ Y E => S F-XES * FXDYES

~~-1.263

T X E S or T Y E S , F X E S or F Y E S , FXES, F X E S or T Y E S , TXES, T X E S and F Y E S .

Remark 3.1 : The names Hintikka set and downward saturated set were given by Smullyan [20]. Hintikka, their originator, called them model sets.

Hintikka showed that any consistent downward saturated set could be included in a set for which the above properties hold with * replaced by c>. From this follows the completeness of certain classical tableau systems. This approach is thoroughly developed by Smullyan in [20]. We now introduce a corresponding notion in intuitionistic logic, which we call a Hintikka collection. While its intuitive appeal may not be as immediate as in the classical case, its usefulness is as great. DeJinition 3.2: Let 9 be a collection of consistent sets of signed formulas. 9 We call 9 a Hintikka collection if for any T X AYEr T X E r and T Y E T , F X v Y E r => F X E r and F Y E r , T X v Y E r * T X E r or T Y E r , F X A Y E ~ F X E r or F Y E r , T-XEr =+ F X E r , T X = Y E r =- F X E r or T Y E r , F-XET * forsome d E 9 , f T C A and T X E A , F X 3 Y E r => for some A E ~rT , c A , T X E A ,F Y E A . Definition 3.3: Let 9 be a Hintikka collection. We call (9, 9, C) a model for 99 if (1). (9, W ,1) is a model, (2). r T EA *TBA, (3). TxEr a r u ,

FxEr =>rpcx.

Theorem 3.4: There is a model for any Hintikka collection. Pro08 Let 9 be a Hintikka collection. Define W by: r W A if r T s A .

1211.284

33

COMPLETENESS OF BETH TABLEAUS

If A is atomic, let r I = A if T A E ~and , extend k to produce a model (9, W,I=>. To show property (3) is a straightforward induction on the degree of X. We give one case as illustration. Suppose Xis Y and the result is known for Y. Then

-

T

-

YEr

=>

( V ' 4 ~ 9 (I", ) 5 '4 * T

-

YEA)

* (V'4€9)(r,cd+FY€A) * (VA E 9)(TWd + '4 pc Y ) =>

rk-Y,

and F - Y E ~e. ( 3 A ~ 9 ) ( r , ~ d a n d T Y ~ d ) => (34 E 9)(r9'4 and A P Y ) =>

rpc

-

Y.

It follows from this theorem that to show the completeness of Beth tableaus we need only show the following: If y ,X, then there is a Hintikka collection 9 such that for some r e g , F X e r .

5 4.

Completeness of Beth tableaus

Let S be a set of signed formulas. By Y ( S ) we mean the collection of all signed subformulas of formulas in S. If S is finite, Y ( S ) is finite. Let S be a finite, consistent set of signed formulas. We define a reduced set for S (there may be many) as follows: Let Sobe S. Having defined S,,,a finite consistent set of signed formulas, suppose one of the following Beth reduction rules applies to S,,: T A, F A , T v , F v , T - or T D . Choose one which applies, say F A . Then S,, is { U,FXA Y } . This is consistent, so clearly either { U,FXA Y, FX} or {U,F X A Y, FY} is consistent. Let S,,,, be { U,FXA Y, F X } if consistent, otherwise let S,,,, be {U,F X A Y, FY}. Similarly if T A applies and was chosen, then S,, is { U, T X A Y } . Since this is consistent, { U , T X A Y, TX, T Y } is consistent. Let this be S,,,,. In this way we define a sequence So,S,, S,, ... . This sequence has the property S,,CS,,~. Further, each S,, is finite and consistent. Since each S , , s Y ( S ) ,there are only a finite number of different possible S,,. Consequently there must be a member of the sequence, say S,,, such that the application of any one of the rules (except F- or F D ) produces S,, again. Call such an S,, a reduced set of S, and denote it by S'. Clearly any finite, consistent set of

34

PROPOSITIONAL I"IST1C

LOGIC, PROOF THEORY

c1i.284

signed formulas has a finite, consistent reduced set. Moreover, if S' is a reduced set, it has the following suggestive properties:

T X A YES' * FX v Y E S ' 3 T X v YES' 3 F X A Y E S ' T-XES' * TXZYES' * S' is consistent.

TXES' FXES' TXES' ~F X E S ' FXES', FXES'

and T Y E S ' , and F Y f S ' , or T Y f S ' , or F Y E S ' , or

TYES',

Now, given any finite, consistent set of signed formulas S, we form the collection of associated sets as follows : If F- XES , {ST,TX}is an associated set. If F X 3 Y E S , {S,,TX,FY} is an associated set. Let d ( S ) be the collection of all associated sets of S. d ( S ) is finite, since U E ~ ( Simplies ) U C Y ( S ) and Y ( S ) is finite. d ( S ) has the following properties: if S is consistent, any associated set is consistent and F -XES FXD YES

=- for some =>

U E ~ ( S S,s ) U, T X E U , forsome UECCP(S) S , E U, T X E U , F Y E U .

Now we proceed with the proof of completeness. Suppose y ,X. Then { F X } is consistent. Extend it to its reduced set So. Form &(So). Let the elements of &(So) be U,,U,,..., U,.Let S, be the reduced set of U,, ..., S, be the reduced set of U,.Thus, we have the sequence So, S,, S,, ..., S,. Next form d ( S , ) . Call its elements Un+,,Un+,,..., Urn.Let S,+, be the reduced set of U,,,, and so on. Thus, we have the sequence So,S,, ..., S,,, Sn+,,..., S,. Now we repeat the process with S,, and so on. In this way we form a sequence So, S,, S,, .... Since each S i s 9 ( S ) , there are only finitely many possible different S,. Thus we must reach a point S, of the sequence such that any continuation repeats on earlier member. Let Q be the collection {So,S,, ..., Sk}.It is easy to see that 9 is a Hintikka collection. But FXESoE 9. Thus we have shown:

Theorem 4.1 : Beth tableaus are complete.

CH.285

35

EXAMPLES

Remark 4.2: This proof also establishes that propositional intuitionistic logic is decidable. For, if we follow the above procedure beginning with FX,after a finite number of steps we will have either a closed tableau for {FX}or a counter-model for X. Moreover, the number of steps may be bounded in terms of the degree of X . The completeness proof presented here is in essence the original proof of Kripke [13]. For a different tableau completeness proof see ch. 5 9 6, where it is given for first order logic. For a completeness proof of an axiom system see ch. 5 5 10, where it also is given for a iirst order system. The work in ch. 1 Q 6 provides an algebraic completeness proof, since the Lindenbaum algebra of intuitionistic logic is easily shown to be a pseudo-boolean algebra. See [16].

9 5. Examples In this section, so that the reader may gain familiarity with the foregoing, we present a few theorems and non-theorems of intuitionistic propositional logic, together with their proofs or counter-models. We show (1). Y I A V - A , (2). kr--(Av -A), (3). Y p - A 3 A , (4). I-,(AvB)r>-(--A/\ -I?), (5). 1 f 1 - - ( A V B ) + - A V -4). For the general principle connecting (1) and (2) see ch. 4 5 8. (1). Y I A V - A . A counter example for this is the following: g = {r,A } rwr, r a ,

AWA.

A !=Ais the != relation for atomic formulas, and 1 is extended to all formulas as usual. We may schematically represent this model by

r

I

A!=A

36

PROPOSITIONAL INTUITIONISTIC LOGIC, PROOF THEORY

czz.285

We claim r pC A v - A . Suppose not. If rt A v - A , either rC A or r C - A . But r pC A . If rC - A then since I ' g A , A pC A . But A 1A, hence rpCAv - A . (2). I-,--(AV -A). A tableau proof for this is the following, where the reasons for the steps are obvious: {{I; - - N ( A v - A ) } } , {{T ( A v A)}} { { T - ( A v - A ) , F ( A -A))), { { T - ( A v - A ) , FA, F A } } , {{T ( A v A), T A ) ) , { { F ( A v A), T A } } , {{FA, F A , T A } ) .

-

9

-

- -

-

N

(3). y1- - A 3 A . The model of example (1) has the property that TI= - A but (4). k , ( A v B ) = , - ( - J A A -B). The following is a proof:

-

r pC A.

-- -- --

y 1-

-

{ { F ( ( A v B ) 2 ( A A B))}} , {{ T ( A v B), P ( A A B ) ) } , { { T ( Av B), T ( - A A -q}}, { { T ( A v B), T - A , T - B } } , { { T ( A v B), FA, T - B } } , { { T ( Av B), FA, F B } } , { { TA, FA, FB}, { TB, FA, FB}}.

- -

( A v B) 3 ( - A v -B)# A counter example is the following: (5).

s={r,A,Q}, ~ A QWQ, , TWA, rBQ

rwr, A

A t= A , SL C B is the C relation for atomic formulas, and C is extended as usual. We may schematically represent this model by

r

ACA

n

SLkB

~11.295

EXAMPLES

37

Now A 1 A, so A ! = A vB. Likewise Dk A v B. It follows t h a t r k - - ( A v B ) But if r k - - A v - - - B , either r ! = - - A or r ! = - - - B . If T k - - A , it would follow that D k A. I f r I= -3, it would follow that A != B. Thus TY-NAV-NB.

-

CHAPTER 3

RELATED SYSTEMS OF LOGIC

0 1. fiprimitive intuitionistic logic, semantics This is an alternative formulation of intuitionistic logic in which a symbol , which is then re-introduced as a formal abbreviation, - X for X 3 f . For presentations of this type, see [15] or [17]. Specifically, we change the definition of formula by adding f to our list of propositional variables and removing from the set of connectives. is re-introduced as a metamathematical symbol as above. Our definition of subformula is also changed accordingly. The definition of model is changed as follows: replace P3 (ch. 1 5 2) by P3‘: r f f. This leads to a new definition of validity, which we may calif-validity.

f is taken as primitive, instead of

N

-

-

Theorem 1.1: Let X be a formula (in the usual sense) and let X’be the corresponding formula with written in terms off. Then X is valid if and only if X’ is $valid. Pro08 We show that in any model (3, W ,k) N

rcx

iff

rcx’

(where we use two different senses of I). The proof is by induction on the degree of X (which is the same as the degree of X’).Actually all cases

~ ~ 3 1 2

f-pRIMITIvE

nmxnomnc LOQXC,PROOF THEORY

39

are easy except that of N itself. So suppose the result is known for all formulas of degree less than that of X,and Xis Y. Then N

rCx+rCNy -vr* r*pcy

-vr* r * y y f , but clearly this is equivalent to r k Y' x f since r*f f.Hence equivalently rw. 0 2. f-primitive intuitionistic logic, proof theory In this section we still retain the altered definition of formula in the last section with f primitive. We give a tableau system for this. The new system is the same as that of ch. 2 0 1 in all but two respects. First the rules T - and F - are removed. Second a set S of signed formulas is called closed if it contains TX and FX for some formula X , or if it contains This leads to a new definition of theorem, which we may call f-theorem.

u.

Theorem 2.1: Let X be a formula (in the usual sense) and let X' be the corresponding formula with written in terms off. Then Xis a theorem if and only if X' is anf-theorem. N

This follows immediately from the following:

-

Lemma 2.2: Let S be a set of signed formulas (in the usual sense) and let S' be the corresponding set of signed formulas with replaced in terms off. Then S is inconsistent if and only if S' isf-inconsistent. Proojl We show this in two halves. First suppose S is inconsistent. We show the result by induction on the length of the closed tableau for S. There are only two significant cases. Suppose first that the tableau for S i s %fly Q,,..., Qn; Ql is { { U ,F - X } } and Q, is {(UT, TX}}.Then by the induction hypothesis {U;,TX') is $inconsistent. Hence so is { U ,F X 3f }, i.e. S'. The other case is if V1 is { { U,T - X } } and V , is ({ U,F X ) } . Then by the induction hypothesis { U', FX'} isf-inconsistent. Hence so is { U ,T X ' 3f }, i.e. S'. The converse is shown by induction on the Iength of the closed $-tableau for S'. If this f-tableau is of length 2, either S' contains TX and

40

RELATED SYSTEM OF IxxjIC

CH.3 g 3 , 4

FX for some formula X,and we are done, or S' contains Tf,which is not possible since we supposed S' arose from standard set S. The induction steps are similar to those above. The results of this and the last sections, together with our earlier results give: X' isf-valid if and only if X ' is anf-theorem. This is not the complete generality one would like since it holds only for those formulas X' which correspond to standard formulas X . The more complete result is however true, as the reader may show by methods similar to those of the last chapter.

fi 3.

Minimal Iogic

Minimal logic is a sublogic of intuitionistic logic in which a false statement need not imply everything. The original paper on minimal logic is Johannson's [9]. Prawitz establishes several results concerning it in [15], and it is treated algebraically by Rasiowa and Sikorski [16]. Semantically, we use the f-models defined in 0 1, with the change that we no longer require P3', that is, that r y f. Proof theoretically, we use thef-tableaus defined in $2, with the change that we no longer have closure of a set because it contains Tf.We leave it to the reader to show that X is provable in this tableau system if and only if X is valid in this model sense, using the methods of ch. 2. Certainly every minimal logic theorem is an intuitionistic logic theorem, but the converse is not true. For example ( A A - A ) = I B is a theorem of intuitionistic logic, but the following is a minimal counter-model for it, or rather for ( A A ( A3f))3 B :

s={r}, r m, r u , rcf, and C is extended as usual. It is easily seen that I ' k A A ( A ~ f )but , r)CB.

fi 4.

Classical logic

-

Beginning with this section, we return to the usual notions of formula, tableau and model, that is, with and not f as primitive.

CH.355

MODAL LOGIC,

s4;

SEMANTICS

41

Some authors call a set Y of unsigned formulas a (classical) truth set if

X AYEY X v Y E Y -X€Y X z Y e Y

o o o o

X X X X

E Y and E Y or #Y, $ Y or

YEY, YEY, YEY.

It is a standard result of classical logic that Xis a classical theorem if and only if X is in every truth set. There is a proof of this in [20].

Theorem 4.1: Any intuitionistic theorem is a classical theorem. Proofi Suppose X is not a classical theorem. Then there is a truth set Y such that X q Y . We define a very simple intuitionistic counter-model for X , ( 9 , W , t.}, as follows: 9=p.),

YWY, Y t .A - A E Y , for A atomic, and I:is extended as usual. It is easily shown by induction on the degree of Y that 9 bY e Y€Y. Hence 9y X , and X is not an intuitionistic theorem. That the converse is not true follows since we showed in ch. 2 9 5 that y I A v - A . Thus we have: minimal logic is a proper sub-logic of intuitionistic logic which is a proper sub-logic of classical logic.

5 5. Modal logic, S4; semantics In this section we define the set of (propositional) S4 theorems semantically using a model due to Kripke [12] (see also [18]). S4 was originated by Lewis [14], and an algebraic treatment may be found in [16]. A natural deduction treatment is in [15]. The definition of formula is changed by adding 0 to the set of unary connectives. Thus for example ( A v 0 - A ) is a formula. 0 is read “necessarily”. 0 is sometimes taken as an abbreviation for 0 and is read “possibly”. (In [14] 0 was primitive.) The S4 model is defined as follows: It is an ordered triple (9, 9, b> where $9’ is a non-empty set, 9 is a transitive, reflexive relation on 9,

--

--

42

01.386

RELATED SYSTEMS OF LOGIC

and C is a relation between elements of 9 and formulas, satisfying the following conditions : M1. I ' C X A Y iff I'CX and f C Y , M2. f k X v Y iff f C X or f C Y , M3. f C - X iff r F X , M 4 . I ' C X x Y iff fpCXor I'CY, M5. r C U X iff forallf*, I'*CX. Xis S4 valid in (9, W,C) if for all f E B , I'bX. Xis S4 valid if Xis S4 valid in all S4 models. The intuitive idea behind this modeling is the following: 3 ' is the collection of all possible worlds. f W A means A is a world possible relative to r. r CX means X is true in the world f. Thus M5 may be interpreted: Xis necessarily true in f if and only if Xis true in any world possible relative to f. This interpretation is given in [12].

0 6. Modal logic, S4; proof theory We define a tableau system for S4 as follows: Everything in the definition of Beth tableaus in ch. 2 0 1 remains the same except the reduction rules themselves. These are replaced by MTA

S,TXAY S, T X , T Y

MF

MTv

S, T X v Y S, T X S, TY

MFv

S,FXvY S , F X , FY

MT-

S,T-X S, FX

MF-

S,F-X S, T X

MTD

S,TX=,Y s, F X TY

MFx

S-~ ,FX3Y S, T X , FY

MTO

S,TOX

MFO

S,FOX

I

IS,

A

S,FXA Y S , F X S , FY

I

so, FX

S, T X

I

where in rule M F O So is ( T U X T U X E S } . Again the methods of ch. 2 can be adapted to S4 to establish the identity of the set of S4 theorems and the set of S4 valid formulas. This is left to the reader. The original

CH.357

s4 AND

INTUITIONISTIC u)(iIC

43

proof is in [12]. We are more interested in the relation between S4 and intuitionistic logic.

0 7.

S4 and intuitionisticlogic

A map from the set of intuitionistic formulas to the set of S4 formulas is defined by (see [ 181) = U A for A atomic, M(A) M ( X v Y)=M ( X ) v M(Y), M ( X A Y) = M ( X ) A M ( Y ) , M(-X) =U-M(X), M ( X 3 Y )= 0 ( M ( X )3 M ( Y ) ) . We wish to show Theorem 7.1: If Xis an intuitionistic formula, X is intuitionistically valid if and only if M ( X ) is S4-valid. This follows from the next three lemmas.

Lemma7.2: Let (3,92, PI) be an intuitionistic model and (Y, 92, ks4) be an S4 model, such that for any r e 8 and any atomic A

r c, A o r c , , M ( A ) . Then for any formula X

r C,X o

C,,M(X).

Pro08 A straightforward induction on the degree of X.

Lemma 7.3: Given an intuitionistic counter-model for X,there is an S4 counter-model for M ( X ) . Pro08 We have (8,92, C,), an intuitionistic model such that for some r E 9 r pC ,X.We take for our S4 model (3, 9,Cs4) where , C, is defined by A k S 4 A if A k , A for A atomic and any A in 9, and kS4 is extended to all formulas. If A is atomic A Cs4M(A) 0 A cs4 C lA e (VA*) A* Cs4 A o (Vd*) A* I=, A csAk,A and the result follows by lemma 7.2.

44

RELATED SYSTEMS OF LOGIC

~ ~ 1 . 3 8 1

Lemma 7.4: Given an S4 counter-model for M ( X),there is an intuitionistic counter-model for X . Pro08 We have <S, 9,ks4>, an S4 model such that for some r )1s4 M ( X ) . We take for our intuitionistic model (9, W , kI) where bI is defined by A CIA if A kS4M(A) for A atomic and any A in 9, and kI is extended to all formulas. Now the result follows by lemma 7.2.

CHAPTER 4

FIRST ORDER INTUITIONISTIC LOGIC SEMANTICS

0 1. Formulas We begin with the following: (1). denumerably many individual variables x,y, z, w, ... (2). denumerably many individual parameters a, b, c, d,... (3). for each positive integer n, a denumerable list of n-ary predicates A", B", C",D", ... (4). connectives, quantifiers, parentheses, A , v, 3 , -, 3, V, (, ). An atomic formula is an n-ary predicate symbol A" followed by an n-tuple of individual symbols (variables or parameters), thus A"(tll, ...,.),lt A formula is anything resulting from the following recursive rules : FO. Any atomic formula is a formula. F1. If X is a formula, so is X . F2,3,4. If X and Yare formulas, so are (XA Y ) , ( X v Y ) , (Xr>Y). F5,6. If X is a formula and x is a variable, (Vx)X and ( 3 x ) X are formulas. Subformulas and the degree of a formula are defined as usual. The property of uniqueness of composition of a formula still holds. We note the usual properties of substitution, and we use the following notation : If X is a formula and tl and j3 are individual symbols, by X(,") we mean the result of substituting j3 for every occurrence of tl in X (every free occurrence in case tl is a variable). We usually denote this informally as follows: we write X as X ( a ) and X ( i ) as X ( p ) . It will be clear from the

-

46

FIRST ORDER 1 " I S T I C

LOGIC, SEMANTICS

CH.4 4 2,3

context what is meant. We again use parentheses in an informal manner and we omit superscripts on predicates. Although the definition of formula as stated allows unbound occurrences of variables in formulas, we shall assume, unless otherwise stated, that all variables in a formula are bound. Notation like X(x) however, indicates that x may have free occurrences in X . $ 2. Models and validity In this section we define the notion of a first order intuitionistic model, and first order intuitionistic validity, referred to respectively as model and validity. This modeling structure is due to Kripke and may be found, in different notation, in [13] (see also [18]). The notions of ch. 1, if needed, will be referred to as propositional notions to distinguish them. If B is a map from Y to sets of parameters, by 4 (r)we mean the set of all formulas which may be constructed using only parameters of B(r). By a (first order intuitionistic) model we mean an ordered quadruple (3,W,k, B), where Y is a non-empty set, W is a transitive, reflexive relation on 3,C is a relation between elements of 9 and formulas, and B is a map from Y to non-empty sets of parameters, satisfying the following conditions : for any r E Y QO. q r ) 5 p(r*), Q1. T C A *A E @(I') for A atomic, 42. r k A r*k A for A atomic, 4 3 . rk(XA Y ) e T k X a n d r k Y, 44. r k ( X v Y ) - ( X v Y ) E @ ( r )and r k X o r r k Y, Q5. T k - X e - X E @ ( r ) and for all r* r * F X , 46. rC(Xr> Y ) o ( X 3 Y ) E @ ( and ~ ) for all r*,if r*kX, I ' * k Y, 4 7 . I ' k (3x)X(x)-=for some a d ( T ) r k X ( a ) , QS. r k (Vx)X(x)efor every r* and for every a @ ( r * ) r*CX(a). We call a particular formula X valid in the model (9, W,k, 9 )if for all r E Y such that X E@ (r) r C X. X is called valid if X is valid in all models.

-

$ 3 . Motivation

The intuitive interpretation given in ch. 1 5 3 for the propositional case may be extended to this first order situation.

CH.484

47

SOME PROPERTIES OF MODELS

In one's usual mathematical work, parameters may be introduced as one proceeds, but having introduced a parameter, of course it remains introduced. This is what the map B is intended to represent. That is, for re9 r is a state of knowledge, and B(r)is the set of all parameters introduced to reach r. (Or in a stricter intuitive sense, B (r)is the set of all mathematical entities constructed by time r.)Since parameters, once introduced, do not disappear, we have QO. 42-6 are as in the propositional case. 47 should be obvious. Q8 may be explained: to know (Vx) X ( x ) at r, it is not enough merely to know X(u) for every parameter a introduced so far (i.e. for all u E B ( r ) ) . Rather one must know X ( u ) for all parameters which can ever be introduced (i.e. for all a& (r*)

r*c x(a)).

The restrictions Q1, and in 44, Q5 and 4 6 are simply to the effect that it makes no sense to say we know the truth of a formula X if X uses parameters we have not yet introduced. It would of course make sense to add corresponding restrictions to 4 3 , 47 and QS, but it is not necessary. The original explanation of Kripke may be found in [13]. For a different but related model theory in terms of forcing see [ S ] .

5 4.

Some properties of models

Theorem 4.1: In any model (9, W ,C, B), for any

r E 9 ,

xdyr).

if I'k-X,

Proofl A straightforward induction on the degree of X, Theorem 4.2: In any model (9, W , C, Y), for any formula X , if

r u , r*!=x.

Proofi Also a straightforward induction on the degree of X. Theorem4.3: Let 9 be a non-empty set, W be a transitive reflexive relation on '3, and B be a map from 92 to non-empty sets of'parameters such that B(r)sP(r*)for all reg. Suppose C is a relation between elements of 9 and atomic formulas such that r I= A A E @ (r).Then k can be extended in one and only one way to a relation, also denoted by k, between 9 and formulas, such that (9, 92, !=, 9)is a model. Proofi A straightforward extension of the corresponding propositional proof. Definition 4.4: Let (9, W,C, 9)be a model and suppose a is some

48

FIRST ORDER 1 ” I S T l C

LOQIC, SEhfANTlCS

CH.455

parameter such that a# UreSS((r). By (9, W ,I:,9)(3 we mean the model <S, W ,C’, P’) defined as follows: Y ( r )is the same as S(r)except for containing a in place of b if B (r)contains b. For A atomic rkA=>rk‘A(:), and I:’ is extended to all formulas. Lemrna4.5: Let(g, 9, k,8>bearnodel,a$Ur,.S(r),(9, W , I : ‘ , Y ) be (9,W ,I:,9’) (:). Then for any formula X not containing a

r k x O F c ’x )(: . Proof: By an easy induction on the degree of X. Definition 4.6: Let (9, 9, k, 9)be a model and suppose a is some paraBy (9, W , b y@ ) b E a we mean the model meter such that a$ UregB(r). (9, W ,I=’, P’> defined as follows: 9‘ (r)is the same as S (r)except for containing a as well as b whenever S(r)contains b. For A atomic I‘ I:A => r C’ A’, where A’ is like A except for containing a at zero or more places where A contains b, and I:’ is extended to all formulas.

Lemma 4.7: Let ( 9 , W , k, 9) be a model a$ U r s S 9 ( r ) ,and let ( 9 ,W,k’, S’) be <S, 9, k, 8 ) b = , . Then if X is any formula not containing a, and if X ’ is like X except for containing a at zero or more places where X contains b

r cx 0r ~ x ’ .

Proof: Again an easy induction on the degree of X.

0 5.

Examples

We show that two theorems of classical logic are not intuitionistically valid: (1). k c (VX) ( A (4 v - A (41, but the following is an intuitionistic counter-model for it. We take the natural numbers as parameters. Let 9 = {ri i = 0,i , 2 , ...}, T i W F j iff i < j S(rJ = {1,2,..., i, i 11

I

+

m.465

49

EXAMPLES

r,CA(i) iff i < n and k is extended to all formulas. We may give this model schematically by

I We claim no rik

--

etc.

(Vx) ( A ( x ) v --A (x)). Suppose instead that

rikNN(vx)(A(x)v -A(x)).

Then for some j > i

r jc (VX) ( A( x ) v

-

A (x)) .

Butj+lE@(Tj), so rjkA(j+l)vwA(j+l). But rjpl A ( j + 1)sincej+ 1>j, and if rjk - A rj+lpl A ( j + l ) , a contradiction.

( j + l),then since I'j9Wj+l,

(2). k c (V.1 ( A v N x ) ) = ( A v ( w q x ) ) , but an intuitionistic counter-model is the following, where parameters are again integers: 3 = {Tt,

r,> 9

r m Z ,w r l , r,wr, , @(b) = {l),@(r2) = {1,2)

Y

r1wi),r,c~(i), ~ , c A ,

and C is extended to all formulas. Schematically, this is

::g

:::,A

To show this is a counter-model, first we claim

rl C ( V X ) ( Av B ( x ) ) .

50

FIRST ORDER INTUITIONISTIC LOGIC, SEMANTICS

cnI.4Q6,7

This follows because rl t B ( 1 ) . Hence r,CAvB(l)

and r , C A , s o r,CAvB(l)

and r , k A v B ( 2 ) .

rl )cA and moreover r,)c( V x ) B ( x ) rl y A v (VX) B(x). But

since r , v B ( 2 ) . Thus

Q 6. Truth and almost-truth sets In classical first order logic, a set 9 ' of formulas is sometimes called a truth set if o X E Y and Y e Y , (1). XA Y E Y (2). X v Y e 9 e X E or ~Y E Y , (3). N X E Y -3 X4Y, (4). X = Y E Y o X # Y or Y E Y , (5). (3x) X(X)ESP o X ( a ) e Y for some parameter a, (6). (Vx) X ( X ) E Y e-X ( a ) e Y for every parameter a, where there is some k e d set of parameters, X and Y are formulas involving only these parameters, and (5) and (6) refer to this set of parameters. We now call Y an almost-truth set if it satisfies (1)-(5) above and (6a). (Vx) X ( X ) E Y * X ( U ) E Y for every parameter a. It is one form of the classical completeness theorem that for any pure (i.e. with no parameters) formula X, Xis a classical theorem if and only if X is in every truth set. We leave the reader to show Theorem 6.1: If X is pure and contains no occurrence of the universal quantifier, X is in every truth set if and only if Xis in every almost-truth set.

Q 7. Complete sequences The method used in this section was adapted from forcing techniques, and is due to Cohen [3].

m.468

51

A CONNECTION WITH CLASSICAL. LOOIC

Definition 7.1 : In the model (59,g,I.,

@)¶

r,AEQ

=>

we call QE B an W-chain if

r W A or A W r .

If V is an W-chain, by V we mean { X I for some r E V ,

-

rC X I .

If V is an W-chain, V is called complete if for every formula X with parameters used in v' X v XEW.

Lemma 7.2: Let +? be a complete W-chain in the model (9, W,k, 9'). Then V' is an almost-truth set. Pro08 This is a straightforward verification of the cases. We give case (4) as an illustration. Suppose (XDY)EW. Then for some r& rCX3 Y. Now either X $ V or XEW.If XEV, then for some A EV A I.X. Let i2 be the 3-last of r and A . Then 51k Xand Q C X x Y,so 51k Yand YEW'.Thus X#U' or YE%?.

Conversely suppose (XI Y)#V'. Then -X#W, since Q' is closed under modus ponens and contains X D (X3Y) as is easily shown. But X v N X E V , hence XEW. Further Y # V , since again Y I ( X = Y ) E Q ' . N

Lemma 7.3: Let <'3,W, C, 9')be a model, I ' E 9 and X E @ ( ~ There ). is some r * E 9 such that r*C X v - X . Proofi Either some r*k X and we are done, or no I'* C X in which case I' I= X and we are done.

-

Theorem 7.4: Let (9¶9,C, 9') be a model and I'EB. Then r can be included in some complete W-chain V such that v' is an almost-truth set. Proofi There are only countably many formulas, X,, X,,X,, . We define a countable W-chain fro,I',, rz,...) as follows: Let robe r. Having defined r,, if X,+l@(r,*) for any r:, let r,,, be r,. If X,+, d(r*)for some r;, then rz, by lemma 7.3, has an @-successor r,**such that r ~ * I . X , +vl N X , , + ~Let . rn+, be this r:*. Let V be {ro, rl,rZ,...}. Clearly V is complete, and by lemma 7.2 V' is an almost-truth set.

...

8 8. A connection with classical logic The first theorem of this section is essentially theorem 59(b) of [I0p. 4921, but there it is proved prooftheoretically and here semantically.

52

FIRST ORDER I " I S T I C

c1i.498

LOGIC, SEMANTICS

- --

Theorem 8.1: Let X be a pure formula. If X is in every classical almosttruth set, - X is intuitionistically valid. Proo$ Suppose -Xis not valid. Then there is a model <S,9, k, 9'> and a S such that I' y X . Then for some I'* E 9 r*C X. Now r* can, by theorem 7.4, be included in an %chain Gp such that V is an almost-truth set. But -XE%', so that X e W . N

Theorem 8.2: If X is intuitionistically valid, then X is classically valid (for X pure). Proo$ As before, if Xis not classically valid, there is a truth set Y not containing X. But it is easily shown that if 9= {Y}, YWY,Y!= Y iff Y E9, and B (9) is the set of all parameters occurring in 9, the resulting (9, W,C, 9>is a model in which X is not valid.

--

Theorem 8.3: If X is a pure formula with no occurrence of the universal X is intuitionisticquantifier, then X is classically valid if and only if ally valid. Pro08 X intuitionistically valid => -X classically valid *X classically valid. Conversely X classically valid =+-Xis in every truth set 3 X is in every almost-truth set 3 - X is intuitionistically valid. N

-

-

N

Remark 8.4: This result will be of fundamental importance in part 11. Corollary 8.5: First order intuitionist logic is undecidable. Proofi Classical first order logic is undecidable, and every classical formula is classically equivalent to a formula with no universal quantifiers.

Remark8.6: That theorem 8.3 cannot be extended to all formulas is shown by example (1) in 0 5.

CHAPTER 5

FIRST ORDER INTUITIONISTIC LOGIC PROOF THEORY

5 1. Beth tableaus The following is an extension of the system of ch. 2 Q 1 to the first order case (see [2]). Everything is as it was there, except that four reduction rules are added to the list. These are

T3 S , T ( 3 x )X ( x ) provided a is new S , TX (a) F3 S , F (3x) X (x) s, F X ( 4 TV S , T ( V x ) X ( x ) s, T X ( 4 FV s, F(Vx) X ( x ) ST,F X (a) provided a is new (Note the S, in rule FV.) In rules F3 and W ,a may be any parameter whatsoever. In rules T3 and FV, the parameter a introduced must not occur in any formula of S,or in the formula X ( x ) . The corresponding classical tableau system is like the above, but in rule FV S, is replaced by S. As in ch. 2 Q 1 interpretations differ. Classically the interpretation is as it was in the propositional case. The restrictions on parameters in T3 and FV are for obvious reasons. In the intuitionistic system the difference between T3 and FV may be explained

54

FIRST ORDER INTUTIONISTIC UXjIC, PROOF THEORY

CH.582

as follows. Suppose we have proved (3x) X ( x ) . Since (intuitionistically) the only existence proofs are constructive, there must already be an instance X ( a ) which we have proved. Thus rule T 3 . But suppose we have not proved (Vx)X(x). We might have proved all instances so far encountered, but it must be possible (i.e. compatible with our present knowledge) that we will at some time encounter an instance for which we will have no proof. However, this might happen at some time in the future, by which time we may have proved some things we do not now (some F Z E S might become TZ). Hence the restriction to S, in rule FV. As in the propositional case, we proceed to show correctness and completeness (in two ways) of this system. The following two examples illustrate proofs in the system: (1). k I ( V X ) X ( x ) 3 - ( 3 x ) - X ( x ) . The proof is { { F ( W XIXI = ( 3 4 x ( x ) > l , { { T ( V x )x ( x ) , F ( 3 4 X ( X ) } } {{T(Vx)x ( 4 W X ) X(X)H {{T(WX(x), -x(a>>>, { { T X ( a ) , T x(a>>> 9 { { T X ( a ) ,FX(a)%

-- --

(2). + ( 3 x ) - [ X ( x ) 3 The proof is

9

9

Y(x)]3(Vx)[-Y(X)~-X(x)].

{{F-(3x)-CX(x)= y ( ~ ) l ~ ( ~ ~ ) [ - y ( ~ ) ~ {IT ( 3 4 [ X (4=Iy ( 4 3 , F (Vx) [ Y (x) 3 x (.)I}} { { T - W - C X ( x ) = Y(x)I,J,[- Y ( a ) = - X ( a ) ] } } , { { T (3x1 C X ( 4 = Y(X)], T Y("), F X ( a ) } >3 { { T (3.) C X ( 4 = Y(X)l, T Y ( a ) , T X ( a ) l } W 3 x ) [X(X)= Y ( x ) l ,T Y ( 4 , T X ( a ) } } { { F [ X ( a ) 3 Y(a11, T Y ( a ) , T X ( a ) } ), { { T [ X ( a )= Y ( a ) l , T Y(a), T X ( a ) ) ) , { { F X ( a ) , T Y ( a ) , T X ( a ) } ,{ T Y ( a ) , T Y ( a ) , T X ( a ) ) ) , W X ( a ) , T Y ( a ) , T X ( a ) } ,{ T Y ( a ) ,m a ) , T X ( a ) } } .

-

-- ---

5 2.

-

-

-

-

x(~)l}~,

9

9

9

-

Correctness of Beth tableaus

Dejinition 2.1: Let S = { T X , ,..., TX,, FY, ,..., FY,} be a set of signed

~~1.552

CORRECTNESS OF BETH TABLEAUS

55

formulas, ($9, W , I=, 9)a model, and r E 9 . We say I' realizes S if XjE@(I'), yj~@(r), and r C X , , rgc Y, (i=1 ...n , j = l ...m). A set S is realizable if something realizes it. A configuration Q is realizable if one of its elements is realizable.

Lemma 2.2: Let Q stand for either the sign T or the sign F. If S,QX(b) is realizable and if a is a parameter which does not occur in S or in X (so a # b ) then S,QX(a) is realizable. Proo$ Suppose in the model (9,W , 'F, 9 ) I' realizes S,QX(b). Choose a new parameter c # ( J r e g 9 ( I ' ) ( we can always construct a new parameter). Let (9, W , k', 9') be (9, 99,C, 9)(:) (see ch. 4 9 4). Since a does not occur in S or X , by lemma 4.4.5, in this new model r realizes S,QX(b). But now a$UrEgPi'(r), so we may define a third model ($9, W,k", 9"') as (8, 9, C', Pi'),,=a, By lemma 4.4.7 in this third model r realizes S,QX(a). Lemma 2.3: If S,T(3x)X ( x ) is realizable, and if a does not occur in S or X ( x ) , then S,TX(a) is realizable. Proofi Suppose in the model ($9, 9,I=, 9) r realizes S,T(3x) X(x). Then I ' b ( h ) X ( x ) , so for some b&'(r) r b X ( b ) . Thus r realizes S,TX(b). If a=b we are done. If not, by lemma 2.2 we are done. Lemma 2.4: If S,F(3x) X ( x ) is realizable and if a is any parameter, S,FX(a) is realizable. Prm$ Suppose in the model (9, W,'F, 9) r realizes S,F(3x) X ( x ) . Then I' pC ( 3 x ) X ( x ) . If a O ( r ) , r pC X ( a ) and we are done. If a#9(r), a cannot occur in S or X by the definition of realizability. But 9(r)#B so there is a b@(I') with b # a and r pC X(b). Thus S,FX(b) is realizable Now use lemma 2.2. Lemma2.5: If S,T(Vx)X(x) is realizable and if a is any parameter, S,TX(a) is realizable. Proofi Similar to that of lemma 2.4. Lemma 2.6: If S,F(Vx) X ( x ) is realizable and if a is any parameter which does not occur in S or X ( x ) , then S,,FX(a) is realizable. Proofi Suppose in the model (9, W,C, 9) r realizes S,F(Vx) X ( x ) . Then r )I (Vx) X ( x ) . But X ( X ) E @ ( ~so ) , there is a r*such that I'* pC X ( b ) for some b E B ( r * ) . Of course r*realizes S,. If b=a we are done. If not, since S,,X(b) is realizable, by lemma 2.2 we are done.

56

FIRST ORDER INTUITIONISTIC LOGIC, PROOF THEORY

cH.5$3

Theorem 2.7: Let Vl, V,, ..., V nbe a tableau. If V i is realizable, so is Vf+lProo$ We pass from V i to V,+, by the application of some reduction rule. All the propositional rules were dealt with in ch. 2. The four new (first order) rules are handled by lemmas 2.3-2.6.

X is provable, X is valid. Proofi Exactly as in the propositional situation.

Corollary 2.8: If

0 3. Hintikka collections This section generalizes the definitions of ch. 2 0 3 to the first order setting. Recall that a finite set of signed formulas is consistent if no tableau for it is closed. We say an infinite set is consistent if every finite subset is. 9,by 9(r)we Let B be a collection of sets of signed formulas. If mean the collection of all parameters occurring in formulas in r. If r , A e B , by TWA we mean P ( r ) G P ( A )and T,GA.

Definition 3.1: We call B a (first order) Hintikka collection if, for any rE9, r is consistent and

TXAYET * T X e r and T Y E r , FXvYeT = . F X e r and F Y E r , TXvYeT = s T X e r or T Y E T , or F Y E r , FXAYer *FXer *FXer, T NxEr TXIYET - F X E ~ or T Y e r , F -X& *forsome A e Q r W A and T X E A , F X ~ Y E *forsome ~ A E Q , r W A and T X e A , F Y e A , T ( V X ) X ( X ) E =r F T X ( a ) e T for all aeP(r), F ( 3 x ) X ( x ) E f =S F X ( a ) E r for all aeP(r), T ( 3 x )X ( X ) E=5~ T X ( a ) € f for some a e 9 ( r ) , F (Vx) X ( x ) E r =5 for some A E 9 TWA and forsome U E B ( A )T X ( a ) f A . Definition 3.2: If B is a Hintikka collection, we call (9, W,C, 9)a model for B if (1). (9,W ,t=, 9)is a model,

CH.564

HINTIKKA ELEMENTS

51

(2). B and 9 are as above, (3). for all rE9 T X E r a r t X a n d FXEr-TpCX. Theorem 3.3: There is a model for any Hintikka collection. Pro08 Suppose we have a Hintikka collection 9. B and W are as defined above. If A is atomic, let T t A if TAET, and extend =l to all formulas. The result <S,9, k, B ) is a model. We claim it is a model for S. We show property (3) by induction on the degree of X. The propositional cases were done in ch. 2 Q 3. Of the four new cases we only do two as an illustration. Suppose the result known for all subformulas of the formula in question. Then T ( V x ) X ( x ) E ra ( V d ~ 9 ) ( r 9 =A T(VX)X(X)EA) (since rTE A if r W A ) ( V A E ' ~ ) ( ~ W A ( ( V a ~ p ( ( d )T) X ( a ) € A ) ) + (VA E q ( r m => (paE B ( A ) ) A c x (a)))

-

.=,

r c ( v ~x )(XI

Conversely

F (Vx) X (x) E r =5 (34 E 9)(TWA and (3a E B(A)) ( F X (a). A)) * ( 3 4 ~ 9 ) ) F W and(3aeB(A))(AyX(a))) d r y (vX> x ( x ) . Thus, as in the propositional case, to establish the completeness of Beth tableaus we need only show that if Xis not provable, there is a Hintikka collection 9 and a re9 such that F X E r .

0 4. Hintikka elements DeJinition 4.1 : Let r be a set of signed formulas and P a set of parameters. We call a Hintikka element with respect to P if r is consistent and T X A Y E ~ * T X E ~and T Y E r , FXvYer ~ F X and E ~F Y E r , T X V Y E T = > T X E ~or T Y E I ' , FXhYBr *FXEr or FYEL", T-XEr => F X E r , TX=YEr *FXEr or T Y E r ,

r

58

F'IRST ORDER INTUITIONISTIC LOOK, PROOF THEORY

CH.554

T(Vx) X ( x ) d =-T X ( a ) E r for each U E P , F ( 3 x ) X ( x ) ~ =r FX(a)ET for each U E P , T ( 3 x )X ( x ) E r TX ( a ) E r for some U E P . Theorem4.2: Let r be an at most countable, consistent set of signed formulas. Let S be the set of all parameters occurring in formulas in r. Let a,, u2, a3,... be a countable list of parameters not in S. Let P=Su {u,, u2,a3,...}. Then r can be extended to a Hintikka element with respect to P. Proofi Order the (countable) set of all subformulas of formulas in r, using only parameters of P : X,, X,, X,, .... We define a (double) sequence of sets of signed formulas: Let r0=r. Suppose we have defined r,,which is a consistent extension of T o , using only hitely many of a,, a,, a3,.... Let A,' =r,,.We define A,,,..., 2 A:+' and let r,,,=A",'.We do this as follows: Suppose we have defined A: for some k (I GkG'n). Consider the formula x,. ~t

most one of

neither is, let A:+

TX,. FX, can be in A'C, (since it is consistent). If If one is in A:, we have several cases.

=A :.

Case (la). x k iS Y v Z and TxkEd:. Then one of At,TY or At,TZ is consistent. Let A:+ be Af:,TYif consistent, and A:,TZ otherwise. Case (lb). xk iS Y v Z and F&€d:. Then A:,FY,FZ is consistent. Let this be A:+'. The cases (2a). T X A Y , (2b). FXA Y, (3). T - J X , (4). T X 3 Y, are all treated in a similar manner. Case (5a). xk is (3x) X(x) and T&€&. Since Af: uses only finitely many of a,, u,, u3,..., let ui be the first one unused. Let A:+' be Ak,,TX(a,). Since a, is new, this must also be consistent. Case (5b). xk is (3x) X ( x ) and FX,EA:. Let At+' be A: together with FX(a) for each aES, and each @=aiwhich has been used so far. Then A:+ is again consistent. Case (6). T(Vx)X ( x ) , is treated as we did case (5b). Case (7). If the signed formula does not come under one of the above cases let A:+' =A:.

'

CH.555

COMPLETENESS OF BETH TABLEAUS

59

Thus we have defined a sequence r0,rl,r2, .... Let n=Urn.We claim Kl is a Hintikka collection with respect to P . The verification of the properties is straightforward.

0 5. Completenessof Beth tableaus Supposing X to be not provable, we give a procedure for constructing a sequence of Hintikka elements. First we order our countable collection of parameters as follows:

S,:

1

1

1

a,, a z , a 3 ,

...

s2: a : , a3; , a 3: , ... s3: a.: , a.z , a.3 , ... .. .. ..

where we have placed all the parameters of X in S,, and let Pn= =s, v s, v ... v s,. For this section only, by an F-formula we mean a signed formula of the form F - X , F X 3 Y or F ( V x ) X . We many assume once and for all an ordering of all formulas. Now we proceed: Step(0). X is not provable, so { F X } is consistent. Extend it to a Hintikka element with respect to P,. Call the result rl. Step (1). Take the first F-formula of rl. If this is F - X , consider rlT,TX.This is consistent. Extend is to a Hintikka element with respect to P z , call it rz.If the first F-formula is F X 3 Y, extend rlT,TX,FYto a Hintikka element with respect to P J Z . If the first F-formula is F ( V x ) X ( x ) , extend Tl,,FX(a:) to a Hintikka element with respect to P J Z . In any event rzis a consistent Hintikka element with respect to P2. Now call the first F-element of rl “used”. The result of step (1) is

{rl,rz1.

Supposeat theend of step (n)we have the sequence {rl,rz,r3, ..., rzn} where each Tr is a Hintikka element with respect to P,. Step (n+ 1). Take the first “unused” F-formula of T i , proceed as in step (I) depending on whether the formula is F - X , FX= Y or F ( V x ) X. Produce from rlT,TX or rlT,TX,FY or rlT,FX(a;“+’)a Hintikka element with respect to Pzn+l, call it rz,,+i, and call the formula in question “used”. Repeat the same procedure with the first “unused” F-formula of rz,producing a Hintikka element with respect to Pzn+z,

60

FIRST ORDER INlTJITIONISTIC LOGIC, PROOF THEORY

c~.5§6

call it r2A+2. Continue to rzn, producing a Hintikka element with respect call it rzn+l. The result of the n+lst step is thus to PZn+,,

Let '3 be the collection of all r,,generated in the above process. We claim 4 is a Hintikka collection. Each r n E % is a Hintikka element with respect to P,,, so B(T,,) is P,,. Since r,,is a Hintikka element with respect to s(I',,), to show B is a Hintikka collection we have only three properties to show. Suppose for some r,,€'3,F(Vx) X(x)Er,,. By the above construction there must be some r&'3 such that r , , T E r k , B(r")=g(rk)and Fx(a)Erk for some parameter a. Thus (3fke%)r,wrkand F X ( u ) M k for some a&(rk). The cases F- and F= are similar. Thus '3 is a Hintikka collection and F X E ~ , Eso~ our , completeness theorem is established. We note that in the Hintikka collection '3 resulting, every formula is a subformula of X . We remark also that the construction of 54 and of this section could be combined into a single sequence of steps. This proof is a modification of the original proof of Kripke [13].

0 6.

Second completeness proof for Beth tableaus

The following is a Henkin type proof and serves as a transition to the completeness of the axiom system presented in the next few sections. A proof along the same lines but using unsigned formulas was discovered independently by Thomason [21] and by Aczel [l]. The similarity to the aIgebraic work of ch. 1 $ 6 is also noted. Recall that a finite set of signed formulas r is consistent if no tableau for it is closed. An infinite set is consistent if every finite subset is, Defhition 6.1. : Let P be a set ofparameters and f a set of signed formulas. We call r maximal consistent with respect to P if (1). every signed formula in r uses only parameters of P, (2). r is consistent, (3). for every formula X with all its parameters from P,either T X E ~ or F X E r or both r , T X and r,FX are inconsistent.

SECOND COMPLETENESS PROOF FOR BETH TABLEAUS

c ~ . 5 § 6

61

Lemma6.2: Let I‘ be a consistent set of signed formulas, and P be a non-empty set of parameters containing at least every parameter used in r. Then r can be extended to a set A which is maximal consistent with respect to P. Proofi P is countable, so we may enumerate all formulas with parameters from P: XI, X2, X3, ... Let A o = r . Having defined A,,,consider X,,,,. If A,,,TX,,+, is consistent, let it be A,+l. If not, but if A,,FX,,+, is consistent, let it be A,,+l. If neither holds, let A,,+, be A,. Let A = A,,. The conclusion of the lemma is now obvious.

u

Definition 6.3 : Let r be a set of signed formulas and P a set of parameters. We call r good with respect to P if (1). r is maximal consistent with respect to P, (2). T(3x)X ( x ) ~ r * T X ( a ) € rfor some UEP.

Lemma 6.4: Let r be a consistent set of signed formulas, and S be the set of parameters occurring in r. Let {u,, a2,a3,...} be a countable set of distinct parameters not in S, and let P = S u {al, a,, u3,...}. Then r can be extended to a set A which is good with respect to P. Proof: P is countable, order the set of formulas with parameters from P: X,, X,, X3, . We proceed as follows: (1). Let A0=T. (2). Extend A, to a set A , maximal consistent with respect to S. (3). Take the fist X , (in the above ordering) of the form T(3x)X ( x ) suchthatT(3x)X(x)EAl butfornoaESisTX(u)EA,. LetA2=A,,TX(al). Since a, is “new”, A z is consistent. (4). Extend A 2 to a set A3 maximal consistent with respect to S u (al}. (5). Take the first Xi of the form T(3x) X(x) such that T ( 3 x ) X(x)eA3 but for no a ~ S {al} u is TX(ar)€A3. Let A4=A3,TX(a2). Again A4 is consistent. (6). Extend A4 to a set A s maximal consistent with respect to S u {ai,az} And so on. Let A = A,. We claim A is good with respect to P. First A is consistent since each A,, is consistent. If X has all its parameters in P,then for some n all the parameters of X are in S u {ul, u2,..., a,,}.But in step (2n) we extend Azn to AZnfl, a set maximal consistent with respect to S u {al, a2,..., a,,}. Thus TX or

u

62

FIRST ORDER INTUITIONISTIC LOGIC, PROOF THEORY

c1i.556

FX is in A,,,, and hence in A , or neither can be added consistently. Thus A is maximal consistent with respect to P. Finally suppose T(3x)X ( x ) ELI. We note that the formula dealt with in step ( 5 ) is different from the one dealt with in step (3), and the one dealt with in step (7) is different again. Thus we must eventually reach T(3x)X ( x ) , and so for some ~ E TPX ( ~ ) E AHence . A is good with respect to P.

Now let us order our countably many parameters as follows: S,:

1

1

1

a2, a$,

... ...

a:, a ; ,

...

a,, a 2 , a 3 ,

s,: a : , s ~ :a : ,

...

2

. ..

. ..

and let P,=S, u S, u ... u S,. Let 93 be the collection of all sets of signed formulas which are good with respect to some P,.We claim B is a Hintikka collection. Suppose r E 9 . Then r is good with respect to some Pi, say P,. Then P(r)(the collection of all parameters of r)is P,. Suppose T X A YET but TX$r. If I",TXA Y is consistent, so is r,TXr\ Y,TX, and so I' is not maximal. Thus TXEI'. Similarly TYEr. Hence T X A YEr-TXEr and T Y E r . Similarly we may show

Moreover

T ( 3 x ) X ( x ) ~ r+ T X ( a ) E r for some a € P ( r ) , since r is good with respect to P,.

CH.5g7

AN AXIOM SYSTEM, d i

63

Suppose F - X E r . Since is consistent, rT,TX is consistent. Extend it to a set A which is good with respect to P,,+l.Then B ( T ) = 9 ( A ) and rTS A , so r W A and TXEA . Similarly, if F X 3 YEr, there is a A E such ~ that r9A, TXEA and FYEA . Finally, if F(Vx) X ( x ) E r , since a;+ does not occur in r, T T , F X ( d +’) is consistent. Extend it to a set A which is good with respect to P,,+l. Again r9A and FX(a:+’)EA for 4” E ~ ( A ) . Thus 9 is a Hintikka collection. To complete the proof, suppose X is not provable. Then { F X } is consistent. Since it has only finitely many parameters, they must all lie in some P,,. Extend { F X } to a set r good with respect to P,,.Then re9 and FXd‘.This establishes completeness. Remark 6.5: The model resulting from this Hintikka collection is a “universal” model in that it is a counter-model for every non-theorem. This is not the case for the model of 5 5. We will show later that, in a sense, this Hintikka collection is the analog of a classical truth set.

0 7. An axiom system, d , The following system was chosen to give a fairly quick completeness proof. It is very close to the system of [lo] p. 82. Axiom schema: 1. X ” ( Y ” X ) , 2. ( X 3 Y ) 3 ((X” ( Y 3 2))2 ( X I . Z ) ) , 3. ((x”z)A(Y3z))~((xV Y)s>z), 4. ( X h Y ) ” X , 5. ( X A Y ) 3 Y, 6. X I ( Y D ( X A Y)),

7. X”(XV Y), 8, Y ” ( X v Y), 9.

(XA

-” -

-x)3Y,

10. (X” X)3 X, 11. X ( a ) ( 3 x ) X ( x ) , 12. (Vx) X ( x ) 3 X ( a ) .

64

FIRST ORDER INTUITIONISTIC LOOIC, PROOF THEORY

CH.557

Rules: 13.

X(u)3 Y (3x1 X ( x ) y Y 3 X(u) = l

14.

Y

y = (VX) X ( x ) X, X 3 Y 15. Y . In rules 13 and 14 the parameter u must not occur in Y. In a deduction from premises the parameter u must not occur in the premises either. We use the usual notation, if X can be deduced from a finite subset of S, we write S k X . We use k X for 0 !-X . In the next three sections we establish the correctness and completeness of d,. We introduce a second system d 2 ,equivalent to d,, to aid in showing correctness. For use in showing completeness we need the following three lemmas : Y

Lemma 7.1: The deduction theorem holds for d l . Proof: The standard one (e.g. [lo] $5 21, 22). Lemma 7.2: i- ( W A Y ) 2 X ,

Proof: (1). ( W A Y ) = X (2). ( W A Z ) X X (3). W = ( Y v Z ) (4). w (5). Y v z (6). W D ( Y = ( W AY ) ) (7). Y 3 ( W A Y ) (8). W x ( Z D( W A2)) (9). z 3 ( W A 2) (10). Y X X (11). Z 3 X (12). ( Y V Z ) X X (13). X (14). W 2 X

by hypothesis, theorem , by hypothesis, theorem, by hypothesis, theorem , premise, by (31, (41, rule 15 , axiom 6 , by (41, (61, rule 15, axiom 6 , by (41,(81, rule 15, via (11, (3, via (21, (9) , via (10, (1l), axiom 3, by (51, (121, rule 15, deduction theorem cancelling premise (4).

CH.558

A SECOND AXIOM SYSTEM, d a

65

Lemma 7.3: If a does not occur in W, Y ( x ) or X , k ( w A Y ( Q ) ) = X , k W D ( 3 X ) Y(X) kW3X

Proofl (1). ( W A Y ( U ) ) D x (2). w D ( 3 x ) Y ( x )

I

by hypothesis, theorems ,

premise , by (21, (31, rule 15> axiom 6 , by (31, (9,rule 15, via (11, (61, by (7), rule 13, by (4), (81, rule 15, deduction theorem cancelling premise (3).

5 8. A second axiom system, d 2 We introduce a second, very similar, axiom system, and prove equivalence. -01, has the same axioms as d,, as well as rules 13 and 14. It does not have rule 15. Instead it has rules 14a.

X(a) (VX)

X(X)

15a. (Vx,) ...(Vx,,) X, (3xl) ...(gx,,)X x Y Y provided all parameters of (Vxl) ...(Vx,,) X are also in Y (n may be 0). To show the two systems are equivalent, it suffices to show 14a and 15a are derived rules of d,, and 15 is a derived rule of -01,. To show 14a is a derived rule of d,, suppose in -01, we have X(a). Let T be any theorem of -01, with no parameters. By axiom 1, X ( a ) ~ ( T = X ( a ) )so , by rule 15, T 3 X ( a ) . Since a is not in T,by rule 14, T x ( V x ) X ( x ) . But also T, so by rule 15, (Vx) X ( x ) . To show 15a is a derived rule of d l , suppose in -01, we have (Vxl)... (Vx,,) X ( x , , ..., x,,) and (3x,) ( j x , , ) X ( x l , ..., x , , ) Y, ~ and all

...

66

FIRST ORDER INTUITIONISTIC LOGIC, PROOF THEORY

CH.599

parameters of (Vx,) ...(Vx,,) X(x,, ...,x,,) are in Y. From (Vx,). ..(VxJ X(x,, ..., x,,), by axiom 12, X(a,, ..., a,,). From axiom 11, X(a,, ...a,,) 2 (3x,) ...(3xJ X ( x , , ..., x,,), so by rule 15, ( j x , ) (3x,,) X(x,, ..., x,,) and by rule 15 again, Y. Finally to show rule 15 is a derived rule of d2,suppose we have X and X I Y in d2. Let a,, u2 ..., a, be those parameters of X not in Y. Since we have X(a,, ..., a,,), by rule 14a, (Vxl) ...(Vx,,)X ( x , , ..., x.). Similarly, since X(a,, ..., an)3Y and a,, ..., a,, do not occur in Y, by rule 13, (3x,) ...(3xn) X ( x , ,..., x,,)= Y. Now by rule 16a, Y. Thus d,and d2are equivalent. For use in the next section we state the straightforward

...

Lemma 8.1: If in d 2we can prove X(a), there is a proof of the same length of X(b) for any parameter b. (note: a does not occur in X ( b ) =

x (a)(;)). 5 9.

Correctness of the system d 2

Theorem 9.1: If X is provable in d,, X is valid. Pro08 By induction on the length of the proof for X.If the proof is of length 1, X is an axiom and we leave the reader to show validity of the axioms. Suppose the result is known for all formulas with proofs of length less than n steps, and Xis provable in n steps. We investigate the steps involved in the proof of X . Axioms have been treated. Suppose X ( u ) x Y in rule 13 is provable in less than n steps where a is not in Y. Then X(a)=, Y is valid. Then ( 3 x ) X ( x ) 3 Y is provable. We I=, 9 ) and any r& and wish to show it is valid. Take any model <%,W, suppose ( O x ) X ( x ) = Y ) E @ ( ~Suppose ). r*C (3x) X ( x ) . Then I'* !=X(b) for some b. But X(a)= Y is provable, so by lemma 8.1 (X(a)= Y)@ is provable with a proof of the same length, hence by hypothesis, valid. Since a is not in Y, this is X ( b ) 3 Y . By validity, r*C X ( b ) z Y, hence r * C Y.Thus r k ( 3 x ) X ( x )3 Y. Rules 14 and 14a are similar. Rule 15a: Suppose (Vx,). ..(Vx,,) X and ( 3 ~ ~.. (3x,,) ) . Xs>Y are both provable and valid. Then Y is provable. We wish to show Y is valid. Let ('3, 9, I=, @) be any model and r e g . Suppose YE@((^). Then

m.5510

COMPLETENESS OF T H E SYSTEM d i

67

(Vx,) ...(Vx,) X and (3xl)...(3x,,) X= Y are both in 3 (r), and since they are valid, r k (Vx,) ...(Vx,) X and r k (3xl). ..(3x,) XI Y. By the latter, either I' pC (3x1) ...( 3 ~ "X) or rC Y. If r y (3x1) ... (h,,) X, for any contradicting r k (Vxl) ...(Vxn) X. a,, ..., a,EB(r), r pC X(a,, ..., a,,), Hence r k Y.

8 10. Completeness.of the system .dl The following Henkin type proof was discovered independently by Thomason [21], Aczel [l], and the author. We work in the system d,.Let r be a set of unsigned formulas and P a collection of parameters. Suppose all the parameters of I' are among those in P. Definition 10.1: By the deductive completion of r with respect to P we mean the smallest set of formulas A involving only parameters of P, such that for any X over P

rt-X*XEA. We call r deductively complete with respect to P if it is its own deductive completion with respect to P. We say r has the Or-property if

x vYEr-xEr

or Y E r .

We say r has the 3-property if, for some parameter a,

( 3 x ) x ( x ) E r =+ x ( + r . We call I' nice with respect to P if (1). f is deductively complete with respect to P, (2). r has the Or-property, (3). r has the 3-propertyY (4). r is consistent. Remark 10.2: Consistency here has its usual meaning.

Lemmu 10.3: Let r be a set of formulas and X a single formula. Let P be the set of all parameters of I' or X. Let {al, a,, u3,...) be a countable

68

FIRST ORDER INTUITIONISTIC LOGIC, PROOF THEORY

CH. 5

8 10

collection of distinct parameters not in P,and let Q = P u {al,a,, a3...}. If r y X , then r can be extended to a set A which is nice with respect to Q such that X$A. Pro08 Let Z , , Z , , 2,... be an enumeration of all formulas with parameters from Q of the form Y v Z or (3x) Y(x). Since r y X, I' is consistent. We define a sequence {r,}as follows: Let T o be the deductive completion of r with respect to P . Then ro is consistent and T o y X . Suppose we have defined r, so that r, is deductively complete with respect to P u {q,a2,..., a,> and r, y X . Let A:=T,. Suppose we have defined A! (jcn)so that it is consistent and A: Y X. Let A!" =A! if (1) 2,441, or (2a) Z j E A,: Z j = Y v Z and Y EA! or ZEA!, or (2b) Zj€A:, Zj=(3x)Y(x) and Y(a)EAiforsomea. This leaves the two key cases: (3). Suppose ZjrzA; and Z j is Y v Z but Y$AL, 2 4 4 ; . We claim we can add one of Y or 2 to A! so that the result still does not yield X . For otherwise

A:,Y !- X A,! Z t X AikYvZ

(since Y v ZEAL).But then by lemma 7.2 A!t X,a contradiction. So add to A! one of Y or Z so that the result does not yield X. Call the result A!+ (4). Suppose Zj€A: and Zj is (3x) Y(x), but Y(a)$Ai for any a. Take the first unused a, of {a,, a,, ...}. We claim we can add Y(a,) to Ad and the result will not yield X. This is as above but by lemma 7.3. Thus A!, Y(ai) p.' X. Let A:+' be A,! Y(ai). Thus in any case A!" is consistent and X$A:+'. Let r,,, be the deductive completion of A: with respect to P u {a,, a,,. .., ak> where ak is the last parameter used in A:. Let A = r,, then A has the following properties : A uses exactly the parameters of Q. X$A since X $ r , for any n. A is deductively complete with respect to Q . A has the Or-property. For if Y v Z EA, say Y v Z = Z,, then Y v ZEA , for some m. We can take m>n. Then Y v Z = Z , e A C , so either Y or Z is in A;,%A. Similarly, A has the 3-property.

'.

u

CH.

5 8 10

COMPLETENES OF THE SYSTEM d i

69

Lemma 10.4: If r is nice with respect to P: (1). X A YE^ (2). X v YE^ (3). - X E r

+XErand YEr, +XEI'or YE^, *X#r, (4). A '= YE^ =.X$ror YE^, (5). (3.) X ( x ) E r CJ X ( a ) E r for some u E P , (6). (Vx) X ( x ) E r X(a) E r for every a E P.

Proofi (1). By axioms 4, 5 and 6 , since r is deductively complete with respect to P. (2). X v Y d j X E r or YEr, since r has the Or-property. The converse holds by axioms 7 and 8. (3). If - X E ~ ,X $ r since r is consistent (using axiom 9). (4). If 1 2 YE^, either X # r or YE^ since r is deductively complete with respect to P . (5). If ( 3 x ) X ( x ) ~ I ' X , ( a ) ~ rfor some a 6 P since r has the 3property. The converse is by axiom 11. (6). By axiom 12.

Lemma 10.5: Suppose r is nice.with respect to P , and {ulyu2,u3...} is a set of distinct parameters not in P . Let Q = P u {al, u2, u3...I. Then (1). If X has all its parameters in P but - X # r , I' can be extended to a set A nice with respect to Q such that X EA. (2). If X= Yhas all its parameters in P but Xx Y#T,I'can be extended to a set A nice with respect to Q such that XEA and Y#A. (3). If X ( x ) has all its parameters in P but (Vx) X ( x ) # r , r can be extended to a set A nice with respect to Q such that for some ~ E Q , X(a)#A. Proofi (1). Since - X # r , {r,X } is consistent, for otherwise T,XF-X. So by the deduction theorem C-X= - X , and by axiom. 10 rF - X , so - X E ~ Since . ( r , X } is consistent, there is some Y such that r , X y Y. Now use lemma 10.3. (2). r , X y Y for otherwise, by the deduction theorem r l - X = Y, so XI>YEr. Since r , X y Y,use lemma 10.3. (3). a, # P . We claim r y X(ul). Suppose r l - X ( a l ) .For the conjunction, call it W, of some finite subset of r, 1 FVzX(al). But a, does not

I0

FIRST ORDER INTUITIONISTIC LOGIC, PROOF THEORY

CH. 5 8 10

occur in W.By rule 14 t- W D (Vx) X(x), so C r (Vx) X(x), (Vx) X ( x ) E r . Since r y X(al), use lemma 10.3.

Now we proceed to show completeness. We arrange the parameters as follows : S,: a il , a,,l a l3 , ...

s,:

a : , a:, a : ,

s3: a.: , a., , a.3 , .. .. .. 3

3

... ...

and let P,=Sl uS,u...uS,, . Let 3 be the collection of all nice sets Let with respect to any Pi. If r e g , r is nice with respect to, say, P,,. 9’(r)=Pn. Let r W A if B(T)EB(A) and rc A. For any X, let r C X iff X d ‘ . By lemmas 10.4 and 10.5 ( 9 , W , I=, 9’) is a model. Finally, suppose y X. All the parameters are in, say, P,. Since 0 y X, by lemma 10.3we can extend 0 to a set r, nice with respect to P, such that X#r.Thus r e g , X E @(r)and r y X. Remark 10.6: This is a “universal” model in the sense of Q 6.

In ch. 6 5 4 we will show that the set of all theorems using only parameters of P, is itself a nice set with respect to P,. This would make the final use of lemma 10.3 above unnecessary.

CHAPTER 6

ADDITIONAL FIRST ORDER RESULTS

0 1. Compactness We call an infinite set S of signed formulas realizable if there is a model (9, W ,C, 9')and a re9 such that for any formula X

T X E S *X E @( T ) and T t X , F X E S X E @ ( r ) and r y X . There is a similar concept for sets of unsigned formulas U. We say Uis satisfiable if there is a model (9, 92, C, 9') and a I ' E g such that for any formula X X E U + X X E @ ( ~and ) rkX.

Lemma 1.1: Let U be a set of unsigned formulas and define a set S of signed formulas to be { TX I XEU}.Then (1). U is satisfiable if and only if S is realizable (2). U is consistent if and only if S is consistent. Pro08 Part (1) is obvious. To show part (2), suppose U is not consistent. Then some finite subset {ul, ..., us}is not consistent, so from it we can deduce any formula. Let A be an atomic formula having no predicate symbols or parameters in common with {ul, ..., u,}. Then kl(U1 A * * * A U n ) 3 ~ .

72

ADDlTIONAL FIRST ORDER RESULTS

~~1.661

Hence there is a closed tableau for

so there is a closed tableau for

By the way we have chosen A , there must be a closed tableau for { T(u, A A u,)} and hence for { Tu,, ...,Tu,}. Thus S is not consistent. The converse is trivial.

-..

Because we have this lemma, we will only discuss realizability and consistency of sets of signed formulas. Lemma 1.2: Let S be a set of signed formulas. If S is realizable, S is consistent. Pro08 If S is not consistent, some finite subset Q is not consistent. That is, there is a closed tableau Vl, V, ..., V, in which gl is {Q}. If Q were realizable, by theorem 5.2.7 every gi would be, but a closed configuration is not realizable. Lemma 1.3: Let S be afinite set of signed formulas. If S is consistent, S is realizable. Pro08 Let S be { TX,, ..., TX,, FYI,..., FY,}. S is consistent if and only if (F(X1 A

**.

A

x,) 13 (Y1 V * * * V Y,)}

is consistent. If this is consistent, (XIA AX,)^ (& v v Y,) is a . non-theorem, so by the completeness theorem, there is a model (9, 2,k, 9)and a r E 3 such that X j € @ ( r ) ,$ ~ @ (and r)

rpc(xlA...Ax,)D(Y~ V - v Y,). But then for some r* r*tx,A - A x,, r*)cY, v . - v Y,, so r*realizes S. This method does not work if S is infinite, but the lemma remains true, at least for sets with no parameters. The result can be extended to sets with some parameters, but we will not do so.

m.651

73

COMPACTNESS

Lemma 1.4: Let S be an infinite set of signed formulas with no parameters. If S is consistent, S is realizable. Proofl The proof can be based on either of the two tableau completeness proofs. If we use the first proof, that of ch. 5 0 5, change step 0 to: “Sis consistent. Extend it to a Hintikka element with respect to PI. Call the result r1”.Continue the proof as written. The lemma is then obvious. If we use the proof of ch. 5 0 6 the result is even easier. S is consistent, so by lemma 5.6.4, we can extend S to a set I‘ which is good with respect to P,.The result follows immediately. Theorem 1.5: If S is any set of signed formulas with no parameters, S is consistent if and only if S is realizable. Corollary 1.6: If every finite subset of S is realizable, so is S. Corollary 1.7: If U is any set of unsigned formulas with no parameters, U is consistent if and only if U is satisfiable.

Remark 1.8: The last corollary could have been established directly by adapting the completeness proof of ch. 5 Q 10. Definition 1.9: For a set of formulas U, by X E u.

r b U we mean I‘ C X for all

Corollary 1.10 (strong completeness): Let U be any set of unsigned formulas with no parameters. Then UtIX if and only if in any model <S,W , C, P),for any I ‘ E S , if l-k- U, I‘k-X. Proofi Ut, X if and only if { TY Y EU >u { F X } is inconsistent,

I

Corollary 1.11: (cut elimination, Gentzen’s Hauptsatz): If S is a set of signed formulas with no constants and {S, T X } and {S, F X } are inconsistent, so is {S}.

Remark 1.12: This may be extended to sets S with some parameters. To be precise, to any set S which leaves unused a countable collection of parameters. It follows that in the completeness proof of ch. 5 Q 6 a set A maximal consistent with respect to P actually contains TX or FX for each X with parameters from P.

74

ADDITIONAL FTRST ORDER RESULTS

CH. 682

$2. Concerning the excluded middle law If S is a set of unsigned formulas, by S t , X and S k , X we mean classical and intuitionistic derivability respectively. Let X(a,, ..., a,) be a formula having exactly the parameters al, ..., a,. By the closure of X we mean the formula (VxiJ

(Vxi.) X(xil, ' " 9 xi,)

(where x i j does not occur in X ( a l , ..., a,,)). Let M be the collection of the closures of all formulas of the form X v -X. We wish to show:

Theorem 2.1: If X has no parameters,

t C Xe M F I X . We first show:

Lemma 2.2: Let (9,92,k, 9')be a model, r E 9 , and suppose Y E M rk-Y. Then r can be included in a complete .%chain V such that %" is a truth set (see ch. 4 Q 6). Pro08 Enumerate all formulas beginning with a universal quantifier:

XI,x2,x,,....

Let T o=r. Having defined r,,,consider X , + l . If X,+ $ @ (r:)for any T:, let I'n+l=I',,. Otherwise there is some r,*such that X,+,E@(~,*). Say X,,, is ( V x ) X ( x ) . We have two cases: (1). If r,*b-(Vx)X(x), let

r,+,=r:.(2). If r,*pC (Vx) X ( x ) , there is a r,**and an a ~ P ( r , *such *) that r,** y X(a). Let r,+,be this r,**. Let the %chain V be {r0,rl,r2,...I. Since YEM=-Tb Yand T = T 0 ,

V is a complete %chain by the definition of M, and so V' is an almosttruth set. Thus we have only one more fact to show:

Y (ct) E V' for every parameter CI of

Q'

+ (Vx) Y (x) E V' .

Suppose (Vx) Y (x, al, ..., a,,) $ V' (where al, ..., a, are all the parameters of Y ) . If some ai is not a parameter of W, we are done. So suppose each at occurs in V'. Then for some r,,€V, all ai@(I',,) and r. j! (Vx) Y(x, al, ..., an). But by the construction of Q, there is a rm(m2n) such that r, pC Y(b,al, ..., a,) for some b~P(r,,,).But

r t (vxl) ...(vx,)

(VX) [Y (x, x ~..,., x,) v

Y (x, x ~..., , x,,)]

~1-1.683

and r9Wm, so

75

SKOLEM-LOWENHEM

r,t

Y ( b , cxl ,... a,) v

N

Y ( b , 011, ..., a n ) ,

thus rmk-Y(b, a,, ..., a,). -Y(b, a1,..., cx,)~%‘, so Y(b,a,..., cxn)$V’ for a parameter b of V’. Now to prove the theorem itself: If M t , X then for some finite subset {ml, ..., m,} of M

t,(ml A A mn)3 X . By theorem 4.8.2 (and the completeness theorems) kc(ml A * . * A m,)

3

x.

But kcml A .--Am,, hence tCX. Conversely, if MY ,X,let S be the set of signed formulas

I

{ F X ) u {TY Y E M } . Since MY ,X, S is consistent. Then by the results of the last section, S is realizable. Thus there is a model (’3, W ,k, 9’) and a r E B such that Y E M TC ~ Y, X e @ ( T ) and ry X. But X has no parameters, so X v X E M .Thus k X v X , so C X. Now by lemma 2.2 there is a truth set containing -X. Hence Y .X. N

-

-

0 3. Skolem-Ldwenheim By the domain of a model (9, 9, k, 9’) we mean ursgY(r). So far we have only considered models in which the domain was at most countable. Suppose now we have an uncountable number of parameters and we change the definitions of formula, model and validity accordingly, but not the definition of proof.

Theorem 3.1: X is valid in all models if and only if X is valid in all models with countable domains. Pro08 One half is trivial. Suppose there is a model (9, W , k, 9’) with an uncountable domain in which X is not valid. The correctness proof of ch. 5 # 2 or 9 is still applicable. Thus Xis not provable. Since Xis not provable, if we reduce the collection of parameters to a countable number (including those of X), X still will not be provable. Then any of the completeness proofs will furnish a counter-model for X with a countable domain.

76

c1i.694

ADDITIONAL FIRST ORDER RESULTS

This method may be combined with that of Q 1 to show Theorem 3.2: If S is any countable set of signed formulas with no parameters, S is consistent if and only if S is realizable in a model with a countable domain. Theorem 3.3: If U is any countable set of unsigned formulas with no parameters, U is consistent if and only if U is satisfiable in a model with a countable domain.

Remark 3.4: In part 11, we will be using models with domains of arbitrarily high cardinality.

5 4.

Kleene tableaus

The system of this section is based on the intuitionistic system G3 of [lo]. The modifications are due to Smullyan. The resulting system is like that of Beth except that sets of signed formulas never contain more than one F-signed formula. Explicitely, everything is as it was in ch. 2 Q 1 and ch. 5 Q 1 except that the reduction rules are replaced by the following, where S is a set of signed formulas with at most one F-signed formula.

KT v

S,TXvY S, T X ]S, T Y .

KFV

ST,FXVY ST,

FX

ST,F X v Y KTA

S,TXAY S, T X , T Y

KTKT

3

KT 3 KT V

S,T-X ST, FF S,TX3Y ST,F X I s, T Y S, T ( h )X ( X ) S, TX(a> S, T ( V X )X (x) S, T X ( a )

where in KT3 and W V the parameter a does not occur in S or X ( X ) .

c~.6§4

77

KLEENE TABLEAUS

There are several ways of showing this is actually a proof system for intuitionistic logic. We choose to show it is directly equivalent to the Beth tableau system, that is, we give a proof translation procedure. We leave it to the reader to show the almost obvious fact that anything provable by Kleene tableaus is provable by Beth tableaus. To show the converse, we need

Lemma 4.1: If a Beth tableau for { TX,, ..., TX,, FYI,..., FY,) closes, then there is a closed Kleene tableau for

{TX,, ..., TX,, F ( Y , v ..*v Y,)}. Proofi The proof is by induction on the length of the closed Beth tableau. If the tableau is of length 1, the result is obvious. Now suppose we know the result for all closed Beth tableaus of length less than n, and a closed tableau for the set in question is of length n. We have several cases depending on the first step of the tableau. If the first step is an application of rule F A , the Beth tableau begins

{{% FXi, .-.,FXn, FY A z}}, {{ST,FXI, * - * , FXn, F Y } {ST, F X I , * * * , FXn, F Z } } 2

3

and proceeds to closure. Now by the induction hypothesis there are closed Kleene tableaus for {&, F(X1v v Xn v Y ) } and {ST,F ( X , v v Xn v Z ) } . We have two possibilities: (1). If Y is not “used” in the first tableau, or if Z is not “used” in the second tableau, a Kleene tableau beginning

---

{{ST, F(X1 {{ST, F ( X 1

x,

v *’* v v (Y v *..v Xn))}

A

Z))}}

9

9

must close. (2). If both Y and Z are “used”, a Kleene tableau beginning {{snF(Xi v * * . v Xn v ( Y {{ST,

F(‘Y

A

A

z))}],

Z)>>

9

{{ST, F Y I , {ST,FZ}} Y

must close. The other cases are similar and are left to the reader.

78

ADDITIONAL FIRST ORDER RESULTS

CH.685

Thus the two tableau systems are equivalent. Now we verify a remark made at the end of ch. 5 0 10. Lemma 4.2: (Godel, McKinsey and Tarski): t,X v Y iff tlX or tl Y. Proofi Immediate from the Kleene tableau formulation. Lemma 4.3: (Rasiowa and Sikorski): If tl(3x) X ( x , al, ..., a,) where a, ,..., a, are all the parameters of X , then klX(b, a,, ..., a,) where b is one of the ai.If X has no parameters, b is arbitrary and kl(Vx) X(x). Pro08 A Kleene tableau proof of (3x) X ( x , a,, ..., a,) begins

{ { W x ) X(X, a,, a,)}}, {{FX(b, a,, --.a,)}}, a*.,

Y

and proceeds to closure. If b is some ai,we are done. If not, we actually have a proof, except for a different first line, of (VX)

8 5.

X ( X , 01,. * * Y a,).

Craig interpolation lemma

Theorem 5.1: If FIX= Y and X and Y have a predicate symbol in common, then there is a formula 2 involving only predicates and parameters common to X and Y such that k , X > Z and kIZ 3 Y; if X and Y have no common predicates, either tl X or t, Y.

-

The classical version of this theorem was first proved by Craig, hence the name. The intuitionistic version is due to Schiitte [17]. Essentially the same proof was given for a natural deduction system by Prawitz [15]. We give basically the same proof in the Kleene tableau system. For another proof in this system see [ll]. We find it convenient to temporarily introduce two symbols t and f into our collection of logical symbols, letting them be atomic formulas, and letting them combine according to the following rules.

x v t=

tv

x =t,

Xvf=f vx=x, X A t= t A X=X, x A f = f AX=f, -t=f, -f=t,

CH.645

CRAIG INTERPOLATION LEMMA

79

x 3 t = f 3 x = t, t3X=X X3f=-X, (3x)t = (Vx)t = t ,

( 3 x ) f = (Vx)f = f . By a block we mean a finite set of signed formulas containing at most one F-signed formula. When we call a block inconsistent, we mean there is a closed Kleene tableau for it. By an initialpart of a block we mean any subset of the T-signed formulas. We make the convention that if S is the finite set of unsigned formulas {XI,..., X,,)then TS is the set {TX,, ..., TX,,}. We further make the convention that for a set S of formulas, S, and S, represent subsets such that S, nS, =8 and S, u S, =S. By [S] we mean the set of predicates and parameters of formulas of S, together with t and$ Now we define an interpolation formula X for the block (TS,P Y ) (where S is a set of unsigned formulas and Y is a formula) with respect to the initial part TS,, which we denote by { TS, F Y } / {TS,}, as follows ( X may be t or f,but we assume t and f are not part of S or Y ) : Xis an ( T S , FY}I(TS,} if (1). [XI E CSll" CSZY y1, (2). { TS,, F X } is inconsistent, (3). (TX,TS,, FY} is inconsistent (we have temporarily added to the closure rules: closure of a set of signed formulas if it contains Tf or Ft). Lemma 5.2: An inconsistent block has an interpolation formula with respect to every initial part. Proofi We show this by induction on the length of the closed tableau for the block. If this is of length 1, the block must be of the form

{ TS,TX,FX}. We have two cases: Case (1). The initial part is ( T S , , T X } . Then X is an interpolation formula. Case (2). The initial part is { T S , ) . Then ( TS,, TX,FX} is inconsistent and t is an interpolation formula. Now suppose we have an inconsistent block, and the result is known for all inconsistent blocks with shorter closed tableaus. We have several cases depending on the k s t reduction rule used.

80

ADDITIONAL FIRST ORDER RESULTS

c~.6§5

K T v : The block is { T S , TX v Y, FZ}, and { T S , TX, F Z } and { T S , TY, F Z } are both inconsistent. Case (1). The initial part is { T S , , TX v Y } . Then by the induction hypothesis there are formulas U, and U, such that

U,is an {TS, T X , FZ}/{TS,,T X } , U2is an { T S , T Y , F Z } / { T S , , T Y } . Then U, v U, is an { TS, TX v Y, F Z } / {TS,, TX v Y } . Case (2). The initial part is { T S , } . Again, by hypothesis, there are U,, U2such that U,is an { TS, T X , F Z } / { T S , } , U,is an {TS, T Y , F Z ) / { T S , } . Then U, A U2is an {TS, TX v Y, F Z } / { TS,}. KF v : The block is { T S , FX v Y } , and { T S , F X ) or { T S , FY} is inconsistent. Suppose the first. Let the initial part be { T S , } . By hypothesis there is a U such that

U is an {TS, F X ) / { T S , ) . Then U is an { TS, FX v Y } / {T S , } . K T A : The block is { T S , TX A Y, F Z } , and { T S , TX, TY, F Z } is inconsistent. Case (1). The initial part is { TS,, TX A Y } . By hypothesis there is a U such that U is an {TS,T X , T Y , F Z } / { T S , , T X , T Y ) . Then U is an { T S , TX A Y, F Z } / {TS,, TX A Y ) . Case (2). The initial part is { T S , } . By hypothesis there is a U such that U is an { TS, T X , T Y , F Z } / { T S , } . Then U is an { T S , TX A Y, F Z } / {T S , } . KF A : The block is { T S , FX A Y } , and { T S , FX) and ( T S , FY} are both inconsistent. Suppose the initial part is { T S , } . By hypothesis there are U,, U2such that U, is an { TS, FX}/{T S , } , U, is an { T S , F Y } / { T S , } . Then U,A U, is an { T S , FX

A

Y}/(TS,}.

c~.685

CRAIQ INTERPOLATION LEMMA

81

KF- : The block is { TS, F - X ) , and { TS, T X } is inconsistent. Suppose the initial part is { TS,}. By hypothesis there is a U such that U is an ( T S , T X } / {T S , } . Then U is an {TS, F - X } / { T S , } . KT- : The block is {TS, T - X , FY), and { TS, F X } is inconsistent. Case (1). The initial part is { TS,}. By hypothesis there is a U such that

-

U is an { TS,FX}/{ TS,}.

Then U is an { TS, T X , FY}/{TS,}. Case (2). The initial part is {TS,, T - X ) . By hypothesis there is a U such that U is an { T S , F X } / { T S 2 } . We claim that U is an { T S , T X , F Y ) / {T S , } .

-

-

First we verify its predicates and parameters are correct. By hypothesis [UJc[S2]n[Sl,X], so immediately [-U]c[S,,-X]n[Sz, Y ] . We have the following two blocks are inconsistent:

{TSz,F U } {TS,, T U , F X ) . 3

It follows that the following two blocks are also inconsistent:

{TS,, T {TS2, T

- u, N

X,F U}, FY) N

3

and we are done. K F 3 : The block is { TS, F X 2 Y } , and { TS, T X , F Y } is inconsistent. Suppose the initial part is {TS,}.By hypothesis there is a U such that

u is an ( T S , TX,F Y ) / { T S , } . Then U is an { TS, FX =I Y ) / {TS,}. K T 2 : The block is { TS, TX 3 Y, F Z ) , and { TS, F X ) and { TS, TY, F Z } are both inconsistent. Case (1). The initial part is {TS,). By hypothesis there are U,, U2 such that U, is an { T S , FX}/{T S , } , U2 is an {TS, TY, F Z } / { T S , ) ,

82

ADDITIONAL FIRST ORDER RESULTS

c~.6$5

Then U,A U2 is an { TS, TX 3 Y, F Z } / {TS,}. Case (2). The initial part is {TS,, T X = Y}. By hypothesis there are U,, U2 such that U , is an { T S , F X } / { T S 2 ) , U2 is an { T S , T Y , F Z } / { T S , , T Y } . We claim U,= U2 is an { TS, TX 3 Y, F Z } / {TS,, TX 2 Y}. By hypothesis cull [S21 n [ S l y XI CU2l CS,, y] n [S2, 21 so [ul= U2]E [SlyX = Y] n [S2, Z] . 9

We have that the following four blocks are inconsistent: (1). w 2 , (2). {W,,TS,, (3). { TSI, TYY W), (4). { m2,TS2, and we must show the following two blocks are inconsistent:

fw, w, m,

The first follows from (2) and (3), and the second from (I) and (4). KF3 : The block is { TSyP(3x) X ( x ) } , and { TS, FX(a)}is inconsistent. Suppose the initial part is { TS,}. By hypothesis there is a U such that U is an { T S , FX (a)}/{ T S , } . Then [U]E[Sl]n[S2, X(a)]. Case (1). a# [U]. Then U is an { TS, F(3x) X ( x ) } / {TS1} Case (2). UE [ U ] , U E [SJ Again U is an { TS, F(3x) X ( x ) } / {TS,} Case (3). U E [U], a$ [S2]. Then ( 3 x ) U(z) is an {TSY F (3.1 x ( x ) } / { T S J* K T 3 : The block is { TS, T(3x)X(x), FZ}, and { TS, TX(a), FZ} is inconsistent, where a# [S, X ( x ) , Z ] .

m.685

CRAIG INTERPOLATION LEMMA

83

Case (1). The initial part is { TS,, T(3x) X ( x ) } . By hypothesis there is a U such that U is an {TS,T X ( a ) , F Z } / { T S , , T X ( a ) } . Then U is an { TS, T ( 3 x ) X ( x ) , F Z } / {TS,, T(3x) X ( x ) ) . Case (2). The initial part is { TS,). By hypothesis there is a U such that

u is an { TS,T X (a), F Z } / {TS1}. Then U is an { TS, T ( 3 x ) X ( x ) , F Z } / {TS,}. KFV: The block is { TS, F(Vx) X ( x ) ) , and { TS, FX(a)} is inconsistent, where &[S, X ( x ) ] . Suppose the initial part is {TS,}. By hypothesis there is a U such that U is an {TS, F X ( a ) ) / ( T S , ) . Then U is an { TS, F(Vx) X ( x ) } / {TS,}. KTV: The block is { TS, T ( V x ) X ( x ) , F Z } , and { TS, TX(a), F Z } is inconsistent. Case ( 1 ) . The initial part is { TS,, T ( V x ) X ( x ) } . By hypothesis there is a U such that U is an {TS,T X ( a ) , F Z } / { T S , , T X ( a ) } . Case (la). a # [ U ] . Then U is an { T S , T ( V x )X ( X ) , F Z ) / { T S , , T ( V x )X ( X ) } *

Case (lb). a E [ U ] , aEISl, X ( x ) ] . Again U is an {TS, T ( V x ) X ( x ) , F Z } / { T S , , T ( V x ) X ( x ) } . Case (Ic). a ~ [ v ] a#[S,, , X(x)]. Then (Vx) U(:) is an { TS, T ( V x ) X ( x ) , F Z } / {TS,, T ( V x ) X ( x ) } . Case (2). The initial part is { TS,}. By hypothesis there is a U such that

u is an { T S , T X ( U ) ,FZ)/{TSl}. Case (2a). a # [ U ] . Then U is an { TS, T ( V x ) X ( x ) , F Z } / { TS,). Case (2b). a€ [ U ] , a€ [Sz, X ( x ) , Z ] . Again U is an { TS, T ( V x ) X ( x ) , F Z } / {TS,}. Case (2c). a € [ U ] , a$ [Sz, X ( x ) , Z ] .

84

ADDITIONAL FIRST ORDER RESULTS

c~.656

Then (3x) U ( l )is an { TS, T ( V x ) X ( x ) , F Z } / {TS,). Now to prove the original theorem 5.1 : Suppose t I X 3 Y. Then { TX, F Y ) is inconsistent. By the lemma, there is a U such that U is an { TX,F Y } / {T X } . We have three cases: (1). U = t . Then since { Tt, F Y } is inconsistent, t, Y . (2). u=f. Then since (TX, F f ) is inconsistent, { F - X } is also inconsistent cf is not in X).Thus t-,-X. (3). U # t , u z f . Then U is a formula not involving t orf, all the parameters and predicates of U are in X and Y, and since { T X , FU} and (TU, F Y } are both inconsistent, tIX=, U and kI U 2 Y.

5 6.

Models with constant B function

In part I1 we will be concerned with finding countermodels for formulas with no universal quantifiers, and we will confine ourselves to models with a constant B function. To justify this restriction, we show in this section Theorem 6.1: If X is a formula with no universal quantifiers and y ,X, then there is a counter-model (’3, 9, k,P) for Xin which B is a constant function. Definition 6.2: For this section only, let a,, u2, a3,... be an enumeration of all parameters. We call a set r of signed formulas a Hintikka element if r is a Hintikka element with respect to some initial segment of a,, u2, a3,... (see ch. 5 Q 4). Lemma 6.3: If S is a finite, consistent set of signed formulas with no universal quantifiers, S can be extended to a Jinite Hintikka element. Proof: Suppose S is the set ( X , , X,, ..., Xn} where each X i is a signed formula. We d e h e the two sequences {pk},{&) as follows: Let

P, = 0, Qo = x,, ..., X”. Suppose we have defined Pkand Qkwhere Pk = Y,, ..., q , Q k = w,,..., w,,

85

MODELS WITH CONSTANT 9 FLINGTION

CH.686

and Pk u Qk (considered as a set) is consistent. To define Pk+, and Qk+l we have several cases depending on W, : Case atomic: If W, is a signed atomic formula, let pk+l

= Y,,

. * a ,

Y,, WI

Qk+l

= W2, ..*,Ws.

Case T v : I f W, is TX v Y, either TX or TY is consistent with Pk u Qk, say TX. Let Pk+i

= Y1, ...,

x, TX V

= w2, ...,

Y,

w,,T X .

Case F v : If W, is FX v Y then FX, FY is consistent with Pku Qk. Let Pk+l

= Y1, ..-,Y,, FX

V

Y,

Qk+l

= W2,

..., W,,F X , F Y .

CasesTA, F A , T - , T I aresimilar. Case T3 : If W,is T(3x) X(x), let a be the first in the sequence a,, a2,... not occurring in Pk or Q k . Then TX(a) is consistent with Pk u Qk. Let Case F 3 : If W, is F(3x) X(x), let {a,,, ..., sit} be the set of parameters occurring in P k u Q k such that no FX(a{,) occurs in PkuQk. Then {FX(ai,),...,FX(a,,)} is consistent with PkuQk. Let Pk+l

=pk>

Qk+l

=

W ~ , * *w,,FX(ai,),...,FX(ai,),F(3x)X(x), .Y

After finitely many steps there will be no T-signed formulas left in the Q-sequence because each rule T v , T A , T-, T 3, T3 reduces degree, and no rule F v , F A , F 3 introduces new T-signed formulas. When no T-signed formulas are left in the Q-sequence, no new parameters can be introduced since rule T3 no longer applies. After finitely many more steps we must reach an unusable Q-sequence. The corresponding P v Q-sequence is finite, consistent, and clearly a Hintikka element.

Remark 6.4: The above proof also shows the following which we will need later: Let R be a finite Hintikka element. Suppose we add (consistently) a finite set of F-signed formulas to R and extend the result to a finite Hintikka element S by the above method. Then

R, = s*.

86

ADDITIONAL FIRST ORDER RESULTS

c~.656

Since R s S , certainly R T s S T .That STGRT also holds follows by an inspection of the above proof; no new T-signed formulas will be added. Now we turn to the proof of the theorem itself. We have no universal quantifiers to consider, so we may use the definition of associated sets in ch. 2 9 4. Suppose X is a formula with no universal quantifiers, and y ,X. Then { F X } is consistent. Extend it to a finite Hintikka element S:. Let T,,,.., T,,be the associated sets of S:. Extend each to a finite Hintikka element, Sy, ..., S: respectively. Thus we have

s:, sy, ...)s:. For each parameter Q of some S: and each formula of the form P(3x) X ( x ) in St, adjoin FX(u) to S8 and extend the result to a Hintikka element S;. Do the same for S:, .... S,",producing S:, ..., S: respectively. Thus we have now

s;, s:, ..., s; .

Let T,,+iy...,T, be the associated sets of SAYS ; , . . . ,S:.Extend each to a Hintikka element, S:+,, ..., Sz respectively. Thus we have now

st, s:, ...)s,1,s,,,0 1, ..., sl),. For each parameter u used so far, and for each formula of the form F(3x) X ( x ) in S;, adjoin FX(u) to St and extend the result to a finite Hintikka element St. Do the same for each. Thus we have now

s;, s:, ...) s,",s;+ 1, ..., s;

.

Again take the associated sets, and extend to finite Hintikka elements, producing now 2 1 0 s;,~:,...r~n,Sn+l,...,S~,Srn+l ,...,s~.

Continue in this manner. Let 4)

W

s o = U S:, s l =U s:, k=O

k=O

By the remark above, for each n, S,T=S;T=S;T=.*..

Thus if S: has as an associated set S;, S,,, ES,.

etc.

c~.6$6

MODELS WITH CONSTANT

9 FUNCTION

87

It now follows that {So,S,, ..,} is a Hintikka collection. For example, suppose F- YES,..Let k be the least integer such that F- YES:. By the above construction, there is some set S," such that S: is an associated set of S: and TYES:. But then Sjk,sS,?, so by the above SjTcS,,and TYES,.The other properties are shown similarly. Moreover, 9(S,,)=9(Sm)for all m and a, as is easily seen. (Recall that 9's) is the collection of all parameters used in S.) Now as in ch. 5 0 3 there is a model for this Hintikka collection, and this model will have a constant B map, so the theorem is shown.

CHAPTER 7

INTUITIONISTIC M , GENERALIZATIONS

6 1. Introduction Here and in the rest of part I1 we restrict our considerations to the following language: a countable collection of bound variables x, y, z, ..., a collection of parameters (or constants) of arbitrarily high cardinality f, g, h, ..., one two-place predicate symbol E (we write ~ ( xy,) as (xE~)), and the usual connectives, quantifiers and parentheses. In all the models (9, W ,k, 9)which we will consider in part 11, the map B will be constant, and so we will simply write the range 9’ of 9 instead of 9, thus (9, W,by 9’),where a(r)= 9’for all I ’ E S . We call a model (9, PZ, b, 9’) an intuitionistic ZF model if classical equivalents of all the axioms of Zermelo-Fraenkel set theory, expressed without the use of the universal quant@er, are valid in it. As a special case, suppose {S, W ,C, 9’)is an intuitionistic ZF model and 9 has only one element r. Then this is (isomorphically) a classical model for ZF. If we define a truth function on all formulas over Y by u(X)=T u(X)=F

if if

rcx, ryx,

ZF map to T. Thus the notion of intuitionistic ZF model is a generalization of the classical notion. Suppose (9, 9, k, 9’) were an intuitionistic ZF model such that v will be a classical truth function, and all the axioms of

92

INTIIITIONlSl'K M a GENERALIZATIONS

~11.711

-AC was valid in it, where AC is some classically equivalent form of the axiom of choice expressed without use of the universal quantifier. It follows that the axiom of choice is classically unprovable from the axioms of ZF. For otherwise ZF kcAC , so for some finite subset A,, ..., A , of ZF A,,

..., A,k,AC.

We may suppose A,, ..., A , stated without the universal quantifier.

kc(A, A . * * A A n ) 2 A C . So by the results of ch. 4 4 8 kl--((Al

A-..AA,)=,AC),

equivalently, kI(Al

A

A

A,)

3

--

AC.

But <S,92,k, 9'>is an intuitionistic model in which A,, ..., A,, -AC are valid, a contradiction. Thus to show the classical independence of the axiom of choice it suffices to construct an intuitionistic ZF model in which AC is valid. Similar results hold for the independence of the continuum hypothesis and of the axiom of constructability. In this chapter we will define intuitionistic generalizationsof the classical Ma sequence of Godel [4], which provide intuitionistic generalizations of L , the class of constructable sets. We will show these generalizations are intuitionistic ZF models. In later chapters we will give specific intuitionistic generalizations of L establishing the independence of the axiom of choice, the continuum hypothesis and the axiom of constructability. The specific models constructed, and most of the general methods will be those of forcing, due to Cohen [3]. It is the point of view that is different. No classical models are constructed, complete sequences and countable ZF models are not used. In [ 5 ] , Gregorzyk noted the foundations of a connection between forcing and intuitionistic logic. In [13] Kripke discussed the relationship between forcing and his models.

-

Remark 1.1 : For the rest of part I1 we shall distinguish informally between constants, bound variables, and free variables. We shall use

c~.7$2

THE CLASSICAL Ma SEQUENCE

93

x, y, z, ... for both bound and free variables. This is an informal distinction. Formally, free variables and constants are both parameters in the sense of part I since free variables are simply place holders for arbitrary constants.

0 2. The classicalMu sequence Let V be a classical ZF model, In [4]Godel defined over V the sequence Ma of sets as follows. M,=B. Ma+, is the collection of all (first order) definable subsets of Mu. MA= Ua< A Ma for limit ordinals, 1. Let the class L be U a E V M UGodel . showed that L was a classical ZF model. As an introduction to the intuitionistic generalization, we re-state the Godel construction using characteristic functions instead of sets. Now of course “E” is to be considered as a formal predicate symbol, not as set membership. Let M be some collection and let v be a truth function on the set of formulas with constants from M. We say a (characteristic) function f is dejinable over ( M , v ) if domain ( f ) = M , range ( f ) E { T , F ) , and for some formula X ( x ) with one free variable and all constants from Myfor all aEM f(a>= lJ ( X (4)* Let M’ be the elements of M together with all functions definable over (MY

0).

We define a truth function v’ on the set of formulas with constants from M‘ by defining it for atomic formulas. I f f , gEM’ we have three cases : (1). f, gEM; let v ’ ( f E g ) = v ( f E g ) . (2). f e M , g E M ’ - M ; let v ‘ ( f E g ) = g ( f ) . (3). f E M ’ - M ; let X ( x ) be the formula which definesf over (My v). If there is an h e M such that ~ ( ( V X ) ( X E ~= X ( X ) ) ) = T ,

and U’(hEg) = T ,

94

INTUITIONISTIC M a GENERALIZATIONS

CH.763

let u’(fEg) = T .

Otherwise let U’(fES) =F .

(Case (3) reduces the situation to case (1) or case (2).) We call the pair ( M ‘ , v ‘ ) the derived model of ( M , v ) . Now let M, =0 and let uo be the obvious truth function. Thus we have (M,, v,). Let ( M a + l ,v a + l ) be the derived model of (Ma, v,). If A is a limit ordinal, let M A = U a c A M , . Let v , ( f E g ) = T if for some a < l , v , ( f ~ g ) = T .Otherwise let u , ( f ~ g ) = F . Thus we have (MA,vA). Let L=

u Ma. U € V

Let v(fEg)=Tif for some aeV, u , ( f e g ) = T . Otherwise let u ( f e g ) = F . Thus we have the “class” model (L,v ) . The reader may convince himself that this construction is essentially equivalent to Godel’s, so that if A is any axiom of ZF, v(A)=T. Thus ( L , u ) is a classical ZF model, though not a standard one. For a boolean generalization of this type of sequence see ch. 14 5 7.

0 3.

The intuitionisticMa sequence

Suppose we have a model (9, 9 , C, 9)(recall that Y is a set, the range of the B map, and that there is only one predicate symbol E). For convenience, let P be the collection of all W-closed subsets of 3. We say a functionf’is definable over (3,92, k, 9)if domain (f)= 9, range ( f ) c P , and for some formula X ( x ) with one free variable, all and no universal quantifiers, for any U E Y constants from 9,

f(4= {rI r C X ( 4 >‘ Let 9’ be the elements of Y together with all functions definable over (3,9, k, 9). We define a C’ relation by giving it for atomic formulas over 9‘. Iff, g E Y ’ we have three cases: (1). f, g E Y ; then let r k ’ ( f e g ) if r k ( f e g ) . (2). f e y , g E Y ‘ - Y : let r k ’ ( f e g ) i f r e g ( f ) . (3). f € Y ‘ - Y ; let X ( x ) be the formula which defines f over

THE INTUITIONISTIC Me SEQUENCE

CH.783

(9, W,t, 9). Let

and

95

rC’(f E g ) if there is an h ~ such 9 that r t (3x) (x E h = x (x))

- -

r t’(h€ 9).

(This reduces the situation to case (1) or case (2)) We call the model (9, 9, t’, Y >the derived model of (9, 9, k, 9). Now let V be a classical (first order) model for ZF. We define a sequence of intuitionistic models in V as follows: Let (9, W,to,Y o )be any intuitionistic model satisfying the following five conditions: (1). (9, W,co,

V

YO)€

(2). Y ois a collectionof functions suchthat, iff€ Yo, domain (f) E Y o and range (f) E P. (3). forf, g € y o , rC0(fEs)iffrw(f). (4) (extensionality). for f , g, h e Y o , if r t , - ( 3 x ) - ( x ~ f = x ~ gand ) r ko (f ~ hthen ) r to ( g ~ h ) . ( 5 ) (regularity). 9,is well-founded with respect to the relation xsdomain ( y ) .

-

N

Remark 3.1: Ifweconsider the symbols v , A , -, 3 , V, 3, (, ), E, x,, x2, x g ,... to be suitable “code” sets, formulas are sequences of sets, and hence sets. It is in this sense that (1) is meant. See also fj 14.

Next let ( 9 ,W, Y,,,) be the derived model of (9,9, C,, 9,). If A is a limit ordinal, let 9A=Ua
Theorem 3.2: (8, W , t, 9)is an intuitionistic ZF model. Remark 3.3: If as a special case we let Y obe empty and 9= {r),and we identify T with (r)and I; with 0, the result is the characteristic function version of the Ma sequence in Q 2. (The truth functions become v=(X)= {r rt,X).) Thus as a special case of the above theorem, L is a classical ZF model.

I

96

CH. 7 4 4

INTUITIONISTIC M a GENERALIZATIONS

Notation: Sometimes we will write g X E 9 ' , + , - 9,where by the subscript X we mean g is the function defined over the model (9, 9, k, 9,) by the formula X ( x ) . Then part (2) of the definition of k' for the derived model may be restated as: If f €9, gxE9"-9,

5 4.

then TC'(f€g,)

if r I = X ( f ) .

Dominance

Definition 4.1 : Let X ( x , , ...,x,) be a formula with no constants and with all its free variables among xi, ..., x,. We call X dominant if forany r e g , any a and any cl, ..., C,E 9,

r k, x (cl, ..., c,) 0r k X(C,, ..., C"). Definition 4.2: Let (1). ( f c g ) stand for - ( 3 x ) ~ ( x ~ f = x ~ g ) , (2). ( f = g ) stand for ( f c g ) ~ ( g s f ) . Theorem 4.3: ( x E ~ ) ,( x C y ) and (x=y) are dominant. Pro08 That ( x ~ yis) dominant is obvious. If ( x c y ) is dominant, so is ( x = y ) . That ( x c y ) is dominant follows from the next three lemmas: Lemma4.4: I f f , g E 9 ' , a n d r t = ( f c g ) , t h e n r k, ( f s g ) . Proofi Suppose for some I'* and some h ~ 9 , ,r*k,(hEf). By the dominance of ( x ~ y )r* , k (h~f).But r*k (3x)-(xEfxxEg), so b y intuitionistic logic r*k N -(h.sg). By dominance again r*k , -(hEg). ~ Thus Tk,(Vx) ( x e f ~ Wxeg), which is equivalent to Tka-(3x)(x€f>x€g).

-

-

Remark 4.5: The reader may show the two simple facts used above, and often later: Xis dominant implies -Xis dominant and t,(VX)(X(X)3"

Y(x)).

Y(x))r+x)-(X(x)3

Lemma 4.6: Iff, g E 9 , and r I = , ( f c g ) then rC,+,(fcg). Pro08 rC,(fcg). Suppose for some I'* and some hcY,+, r*k , + , ( h e f ) . If h e y a , by dominance r*t = , ( h ~ f )But . r*k,(fcg) so -(hEg). as above r*C-, -(htzg), and by dominance r* If h ~ Y , + , - 9 , , since f e Y , a n d r * k , + l ( h ~ f ) , it mustbethecasethat h is hx for some formula X over 9,, and there is some k E Y , such that

-

CH.755

97

A LI'ITLE ABOUT EQUALITY

r*k a + l ( k E f )and r*k , - ( 3 x ) - ( x ~ k f X ( x ) ) . Since both k, f EY,,by dominance r * k , ( k E f ) . Thus r*I=,- -(keg), and by dominance r* ( k E g ) . That is for any r**there is some r***such that r*** ( k E g ) . But also ~ * * * ~ , - ( ~ x ) - ( x E ~ E X ( kX e) y) , , so by

-

-

definition I'***ka+l(hxEg). Thus r * k a + l - - ( h x E g ) . Hence I'l=a+l(Vx)( x ~ f 2 - x E g ) , so r t U + , - ( 3 x ) - ( x € f ~ x € g ) . Lemma 4.7: Iff, g € Y a and r k a ( f s g ) , then r k ( f s g ) . Proofi First, by transfinite induction, for any >cc, I=, (fsg). The successor ordinal step is given by lemma 4.6. Suppose 1 is a limit ordinal, A >a, and the result is known for all fl such that cc
-

5 5.

A little about equality

-

Theorem 5.1: Iff€ 9, andgxE 9'a+l - 9, then I ' k p (3x) ( x ~ f = X ( x ) ) if and only if Tk,+, ( f = g x ) . This follows from the next two lemmas: Lemma5.2: If f e y , ,

gxE9,+l-Y,

andrC,+,(f=gX), then

rca-(3x)-(xe f d ( x ) ) . Proofi Suppose for some r* and some h € Y Y , ,r * I = , ( h ~ f )Then . - ( k g X ) . Thus for any r**there is a r*** (kf), so r* such that r*** \ , + I (hEgx). But ~ E Y , gxE9',+1-9,, , SO r***EgX(h), that is r***C,X(h). Thus r*Fa- -X(h), so r k , ( V x ) ( x f -~ X(x)) or r k a (3x) ( x ~ fX(x)). 3 Similarly r k a (3x) ( X ( x )3 X E ~ ) ) . The result follows since -(3x)-Xl (.)A - ( 3 x ) - X 2 ( x ) t I - ( 3 x ) - ( X l (.)A

-

r*

- -

- -

-

x2 (.>>.

Lemma 5.3: If fey,, g X E 9 a + 1 - 9 0 . and I ' k a - ( 3 x ) - ( x E f = X ( x ) ) , then rh+l( f = g x ) . Pro08 rk,-(3x)( x ~ f = X ( x ) ) .Suppose for some I'* and some h E Y U + l , T*k,+,(kf). If h ~ y , trivially , r*I=,+, -(h€gx). If h e y a + ,-9,, then sincefE9, h must be h, for some formula Y over 9,. and there is some ~ E Ysuch , that r*k,+,(kEf) and

-

98

INTUlllONlSTIC M a OENERAZIZATIONS

m.786

Y(x)).By dominancef* k,(k€f), so f* C,- -X(k). So for every f** there is a f*** such that r***t=,X(k). Thus f***ka+l(kegx).But alsof***~,N(3x)N(X€k3Y(x)),so by definition f***ka+l(hyEgX). Thus f * k a + l - -(hegx). Hence fl=.+l(fEgx). In a similar manner it can be shown that f k a + l ( g x cf ).

f* I=,+x)-(xEk=

For later use we show the following most useful corollary:

Theorem 5.4: If f k,(fEg), then there is an h~ dornain(g) such that f k,( f=h) A (h€g). Proofi By induction on u : If u=O, and r k o ( f E g ) , by definition f must be in the domain of g. Suppose the result is known for a, and f t = a + l ( feg). We have three cases : (1). Iff, g E Y , , the result is by induction hypothesis. (2). Iff E .Yayg E 9,+ - Y,, the result is trivial since f~ domain (g). (3). Iff ~ 9 , -+ 9,, by definition and theorem 5.1 for some kE 9, f t = a + l (kEg)A ( k = f). Since ft=a+l ( k e g ) , by case (1) or case (2) there is some he domain(g) such that rka+l (hEg)n (h=k). But trivially if f C , + , ( h = k ) A ( k = f ) , then f k , + , ( h = f ) . The limit ordinal step is simple. Remark 5.6: By dominance of (xEg) and (x=g), the result follows also for the class model.

5 6.

Weak substitmtivity of equality

Theorem 6.1: Let X(x) be a formula with one free variable and no universal quantifiers. If fC,(f =g) and rk,-X( f), then rI=,-.X(g). Similarly if f k (f=g) and r k X(f ), then 'I t X(g). Pro03 Suppose the result is known in the model ( 9 , W , I=,, 9J (or in (9, 9, t, 9)) for all atomic formulas X ( x ) . It then follows for all formulas X ( x ) by the following intuitionistic theorems :

-

N

X

-

- Y 1,

N

N

(Vx) [

-

X(x)=

N

--

( X A Z) E (Y A Z), ( X v Z ) = (Y v Z), -(-X) =+ Y ) , ( X 3 2) = (Y 3 Z ) , - ( 2 2 X ) 3 - ( Z 3 Y), Y ( x ) ] 11 (3x) X ( x ) = ( 3 x ) Y (x).

3

N

N

-

m.786

99

WEAK SUBSTITUTIWCY OF EQUALITY

Thus we must show the result for atomic formulas. Over (9, 92, ko, y o ) an atomic formula must be either ( E X ) , @a) or ( a d ) for a, bE.Yo. The case ( a ~ bis) trivial. For the case ( U E X ) , we are given: rt0-(3x)( x e f r x e g ) and r k o - ( a E f ) . The result r k o - ( a E g ) follows by intuitionistic logic. For the case ( X E U ) the result is condition (4) on < S , % COY 9 0 ) in § 3. . show it for Suppose the result is known for all formulas over Y a We .Ya+l).Again an atomic formula must atomic formulas of (a,9, be either ( a ~ x ) (,X E U ) or ( a d ) for a, ~EY,,,.As above ( X E U ) is the and r k a + l - ( f ~ a ) . only difficult case. Thus we are given rCa+l(f=g) We have eight subcases : (1)

a,f, g E y a ,

(2) a , f e y a , (3). 0, g E y a ,

(4). a e y a , (5).

gEya+l-ya, f € Y a + l - y a ,

f,g E Y a + l - y a ,

Y a + 1 -y a ,

(6). a, g E y a + l - g a , (7). a , f E Y a + , - Y a , (8).

f,

EY a y

f E y a ,

gEya,

a,f, g E Y a + l - y a *

We treat these cases separately. Case (1). The result follows by dominance of ( x ~ y and ) ( x = y ) , and the induction hypothesis. Case (2). Suppose I' pC a + l ( g a z ) . Then for some I'* I'* (sea). By theorem 5.4 there is an ~ E Ysuch , that I ' * k . + , ( g = h ) ~ ( h ~ a ) . But I'* Ca+l ( f = g ) , hencer* k a f l (f=A). Bydominancer* C , ( f = h ) ~( h ~ u ) . By induction hypothesisI'* ka- - ( f ~ a ) .By dominancef* ka+l - ( f ~ a ) ,

-

-

so r F a + l N ( f 4 . Case (3). Suppose I'pC a + l - ( g E u ) . Then for some I'* I ' * t a + l ( g ~ a ) .

-

Now by theorem 5.1 and the definitions r*t a + l ( f e u ) , SO rpC a + l ( f e u ) . Case (4). This is an elaboration of (2) and (3). Case (5). a is a x ~ Y a + , - Y aSuppose . I ' Y a + l - ( g E a X ) . Then for some r* I ' * k a + l ( g E a x ) , S O r * k , X ( g ) . But r * k a + l ( f = g ) , SO by dominance r*C a (f =9). By hypothesis r*k a X( f ), so it follows that I ' * C a + l - -(f~u,). Hence rpl a+l(fEax). Case (6). Suppose I' pl a + l - ( g E a ) . For some r* I'* ka+l (sea). By theorem 5.4 for some ~ E YI ' *,k , , , ( g = h ) r r ( h ~ a ) . But I ' * k a + , ( f = g ) But r * k a + l ( f = g ) .

--

100

INTLnnONISTlC

cH.707

GENERALIZATIONS

-

so r*CU+,(f=h). By dominance r * k a ( f = h ) . Moreover a must be a ~ ~ ~ , + , - 9 a . S i n c e ~ * k(hea), , + , r*C,X(h). ByhypothesisT*t=,X ( J ) , and so r*C.+,-- ( f € a x ) . Thus rF .+,-(feux). Case (7). Suppose ry - ( g ~ a ) Then . for some r* r*ka+, (s e a ). But r*k a + , (f= g ) , so by theorem 5.1 and the definitions I'* k a + , (fE a ). Thus rpr . + , - ( f ~ a ) . Case (8). This is an elaboration of (6) and (7). Thus, we have the result for successor models. The result for atomic formulas in limit models and in the class model is straightforward.

.+,

Q 7. More on dominance

-

Defnition 7.1 : A formula Xis called stable if FIX-= -X. Definition 7.2: A formula X (with no universal quantifiers) is said to have its quantifiers bounded if every subformula beginning with a quantifier is of the form ( 3 4 ( ( x E A y (4)

4

f

where u is a variable or a constant. Moreover, if Y is stable we say X has strongly bounded quantifiers. Theorem 7.3: Let X be any formula with no constants, no universal quantifiers and all its quantifiers strongly bounded. Then Xis dominant. Proofi By induction on the degree of X . If X is atomic the result is just the dominance of (xey). Suppose X is not atomic and the result is known for all formulas of Y or ( Y I Z ) are lesser degree. The four cases X is ( Y v Z ) , (Y AZ ) , simple. Suppose X ( y , z, ...) is ( 3 x ) [ ( x ~ yA) Y ( x ,y, z, ...)I where Y is stable and by hypothesis dominant. Suppose a, b, ...€9.. If TC,X(a, by...) then ~ ~ , ( ~ x ) [ ( x E uY)(Ax ,a, b, ...)I. For some f €YUr k a ( f E a ) AY ( f ,a, by...). By hypothesis both of these are dominant, so r != ( f e z )A Y ( f ,a, b, ...). r C ( 3 x ) [ ( x ~ aA) Y (x , a, b, ...)I. Hence r k X ( a , by...). Conversely suppose r t= X ( a , b y . .). . r k ( 3 x ) [ ( x ~ aA) Y (x , a, by...)I. Then for some f ~ 9 r , k ( f ~ aY(f, ) ~a, by...). U E ~ . ,so by theorem 5.4 there is a g E 9 , such that r k ( f = g ) r \ (gtza). By weak substitutivity of equality r k Y ( g ,a, b, ...). But Y is stable so r k Y (g , a, b, ...). Now

-

N

-

~~1.708

101

AXIOM OF EXTENSIONALITY

by dominance

r ! = a ( g E aA) Y(g, a, by...), r C , ( 3 x ) [ ( x ~ a )A Y ( x , u , b, . . . ) I .

Hence Tk,X(a, b, ...). We define the following formula abbreviations :

-

for (3x) (x E y ) , for (3x) ( X E Y A x = 0), ( 3 w ) [ W E Y = (w E X v w = x)] , y = x’ for X’EY for ( 3 w ) ( w ~ y A w = x’), W C Y for - - ( 0 ~ y ) ~N ( ~ x ) - [ x E ~ I > x ‘ E ~ ] , ( 3 w ) [ W E . = ( w = y v w = z)], x = { y , z> for x= Uy for N ( ~ Z ) N [ Z E X = ( ~ W ) ( W E Y A Z E W ) ] .

y=0 0EY

- -

-

N

Theorem 7.4: The above formulas are dominant. Proo$ y=O and 0 ~ are y directly by theorem 7.3. y=x’ is equivalent to the conjunction of the following two formulas:

-

(3W ) [ W E y A

N

-(3W)-[(WEXV

(WE X V W

= X)]

,

w=x)=,wEy].

The dominance of the fist is by the above theorem. That of the second is simple to show. In a similar fashion the remaining formulas follow, making use of k,

and t-1

-

(3X)

- (&)

N

[x(X)

[x(X)

3

Y(X)] 3

Y(X)]

N

(3X)

N

(3X) [x(X) A

-

- - [x(X)

2

Y(X)]

Y(X)]

A

(3x1 [ Y W

3

X(4l

0 8. Axiom of extensionality Theorem 8.1: The following is valid in (59,9, !=, 9):

-

(3x) (3y)

-

{

N

(3w)

-

[w.x

=W€Y] 3

N

(32)

N

[x..

= YEZ])

In addition it is valid in every model (9, W ,ka, 9.J. Pro08 For any T c 9 and any f, g E 9, if k (f = g), by weak substitutivity of equality, != (fed)= (gd). But this holds for every d ~ 9 ,

-

-

102

CH. 7 $5

INTulTIONlSTIC M a OENERALIZATIONS

-

-

9,10

so I' C (Vz) [ (fez)= "(9 EZ)], and by intuitionistic logic r k (32) - [ ~ E z E ~ E z ]Thus . the result follows. (The same proof also works for every a.)

0 9. Null set axiom Theorem 9.1: The following is valid in ( 9 ,W,i=, 9):

In addition it is valid in any model ( 9 ,W,C,, 9J for a>O. Pro08 Suppose we show the formula is valid in ( 9 ,9,C,, 9,)If. r& rk1(3x)-(3y) ( V E X ) , so for somefeSP1 r k l N ( 3 y ) ( y ~ f ) , i . e . r k l [email protected] result then follows by dominance of x=0. Let X ( x ) be the formula -(x=x). There is an f x E 9 , -9,. We claim ( 3 y ) (y~f,). for any TEB r C, ( 3 y ) ( y ef,). Suppose otherwise r pC Then for some r* r*C, ( 3 y ) ( y ~ f ~For ) . some ~ E Yr* , k1 ( d ~ f , ) . By theorem 5.4 there is an e e 9 , such that r*1, (d=e)/r (eef,). Since r*k1(e~fx),by definition I'*C,X(e), i.e. I ' * k o - - ( ~ X ) - ( X E ~ E X E C ) which is not possible by intuitionistic logic.

-

,-

0 10. Unordered pairs axiom Theorem 10.1: The following is valid in the class model and in any limit model : (3x) ( 3 y ) (32) ( 3 w ) [ W E 2 E (w = x v w = y ) ] .

-

- - -

Pro08 If we show that for any f, g E 9 , there is an h E 9 a + l -9, such that h= {f, g } is valid in (9, 92, Yo.+,), the result will follow by dominance of x= { y , z}. Let f , g E 9 , . Let X(x) be the formula ( x = f )v (x=g). There is an h,E9a+l-Ya. We show hx= {f,g } is valid in ( 9 , W , Ca+ly 9 a +Let l). reg. Suppose r*i=a+l(aeh,).Then there is some b e Y , such that r*i=,+,(a=b)A(bEh,). Since~*C,+,(b~h,), r*i=,X(b). r * k , ( b = f ) v (b=g). By dominance I'*!=a+l(b=f)v(b=g).But r*k.+,(a=b), so by intuitionistic logic I'* F a + , ( a = f ) v (a=g). Thus I'i=a+l (Vx) ( x € h x 2 (x=fvx=g)). Conversely supposer*t=,+,(u=f)v (a=g).Theneitherr*t,+,(a=f)

CH. 7 § 11

103

UNION AXIOM

or r*ka+l (a=g). Say r*k,+, (a=f). It is trivial to show r*I=,+, (feh,) so by weak substitutivity of equality r*k,+, (aeh,). Thus rC,+,(Vx) ((x=f vx=g)= - x ~ h , ) . The result follows easily.

--

-

'$11.Union axiom Theorem 11.1: The following is valid in the class model and in any limit

-

model:

(3X)

N

(3y)

N

(32)

-

[ Z € y 3 (3W) (Z€W A W E X ) ] .

Pro08 If we show that for any f E Y a there is a g r s Y a + l - Y a such that g = U f is valid in ( 3 , W,ta+,,Yo.+,), the result will follow by dominance of x = Uy. Let f e y " , . Let X ( x ) be the formula (3w) ( X E W A w ~ f ) .There is a gx~Ya+,-Y We a .claim g x = U f i s valid in ( S , 9,I=,+,, 9 a +Let l).

reg. Suppose r * k a + , ( 3 w ) ( ~ E W A W E ~ ) Then . for some k E Y , + , r*t a + (hek) , A (k ~ f ) .Since f * t a + (k~f), , there is some t E Y , such that I'* (k= t )A ( t e f ) . By weak substitutivity of equality r * t , + , - - ( h ~ t ) .Thus for every r** there is a r***such that r*** k, + (hE t ). But t~ 9,so there is an S E 9, such that r*** k,+ (s=h) A (set). But r * * * k , + , ( h E k ) ~ ( k € f ) and r * * * k , + , ( s = h ) A ( k = t ) , so r*** ka+l [ ( s e t ) A ( t ~ f ) ] .Now s, t, f EY,, so by dominance r***ka- - [ ( s ~ t ) ~ ( t ~ fr*** ) ] . k , ( 3 w ) - - [ ( S E W ) / \ ( w e f ) ] . By intuitionistic logic, r*** k , - ~( 3 w ) [ S E W . w ~ f ]that , is r*** t,- -X(s), so r***ka+lN -(sEg,). But r***k,+,(S=h), SO r***k,+,-(hEgx). Thus for every r**there is a r*** such that r*** tor+, (beg,). Then I'* t a + , -(hEg,). So we have shown

-

-

-

rka+l(vX)[(3W)(X€W

N

A W€f)z--X€gx].

Conversely suppose r*ka+,(hEgx). There is some k e y " ,such that r * k , + , ( h = k ) ~ ( k e g , ) . So r*C,X(k) or r * k a ( 3 w ) ( k e w ~ w ~ fFor ). some t e Y a r * k , ( k c t ) A ( t E f ) . By dominance r * k , + , ( k € t ) h ( t E f ) . r * t a + , ( 3 w )( ~ E W A W E ~ hence ) , r*ka+l" ( 3 ~ )( ~ E W A W E ~ ) . So we have shown

r t,+,( V X ) [ x Eg, The result follows easily.

= I

--

( 3 w ) ( x Ew

A

w€ f ) ]

104

CH.

INTUITIONISTIC kfa GENERALIZATIONS

7 8 12

5 12. Axiom of infinity Theorem 12.1: The following is valid in (9, 9, k, 9) and in bay 9 , ) for a > o : (3, (3X) [ @ E X A (3Y) (YEX 3 Y ' E X ) ] .

- -

Proof.- If we show there is an fE 9,+1 - 9,such that o C f is valid in (9, W,t=o+l, c400+l>, the result will follow by dominance of o ~ x . Let X ( x ) be the formula -(3Y)

-

{[-(3Z) " ( Z E y

3 Z'EY) A

0 € Y ] 3 X€Y).

There is an fx E 9, + - 9,. We claim o Efx is valid in 9,+, This ).follows from the next four lemmas: (9, 92, Lemma12.2: I f I ' k a f = O ~ g = O t h e n r k , f = g . Proof.- r k a - ( 3 x ) ( x f ~) A -(3x) ( x e g ) so by intuitionistic logic r ~ , - ( ~ x ) - ( x E ~ = x E r~k ), f,= g . Lemma 12.3: I'k,+lOE fx. Proof.- By the results of 5 9 for some g e 9 , rk,g=0. Suppose for some r* r*C, -(&) - ( z E k 2 z ' E k ) A 0 ~ k . Then r*k,OEk, that is r * k o ( 3 w ) ( w = ~ A w E ~ )so , for some S E Y , r * k , S = @ ~ s E kBylemma . 12.2r*k,s=gY s o r * C , - - ( g ~ k ) . We have shown r k,(vx) {[- (32) ( Z E X 3 Z'EX) A EX] 3 EX))

-

--

or equivalently r t = , D ( ~ x ) - { [ - ( 3 z ) N ( z E ~ ~ Z ' E X ) ~ ~ E ~ 1 ~ g E x ) ,

r kco x (91, ka+lS E f X .

But I'ka+lg=O,

so by definition rt=,+lOefx.

Lemma 12.4: If g E 9 , , there is an h E 9 a + 1 - Y , such that h =g' is valid in ( 3 , W , k a + l , y a + l > . Proofi Let Y(x) be the formula ( x E g ) v ( x = g ) . There is an h y E 9a+l - 9,. We will show

rka+l- (

3 w ) - [ ~ ~ h y ~ ( ( ~ ~ g ~ ~ = g ) ] .

105

(2).

r*k,+

(s = g ) . Since trivially

r*

Ca+

( g E hy) ,

r*ka+l --(dy). Thus we have

rkaCl N ( 3 W ) N [ ( W E gw~ = g ) = , w ~ h ~ ] Lemma 12.5: If I‘b,+l

( g € f x ) ,then (g’e f x ) . Proof: r k o + l ( g e f X ) ,so there is an h g Y , such that r k , + l ( g = h ) r \ (h€Jx). Since h ~ 9 , ,for some tc
By intuitionistic logic it follows that rk,-(3y)-{[-(3z)-(zEy~z’Ey)A8€y]~~~y),

that is rC,X(k), TC,+l(kefx). rk,+lh’~fx*

But TC,+,k=h’, so by definition

106

CH. 7 8 13

INTLJITIONISTIC M a OENERALIZATIONS

0 13. Axiom of regularity Theorem 13.1: The following is valid in all models: - ( 3 x ) - ( ( 3 y ) ( y E : x ) ~ ( 3 y ) [ y E x A -(3z)(z=

AZEY>l>.

Proofi All the elements of the class 9’are functions. We have assumed 9, is well-founded by the relation xedomain ( y ) . It then follows that 9 is also well-founded by xdornain ( y ) .

The formula Iv

-

{(YY) (Y EX)

3

(3Y) [Y

EX A

-

(3.) (z E X

A Zf

YIII

(*>

is equivalent to - { ( 3 y ) ( Y ~ x ) A - ( ~ Y ) [ Y E x A - ( 3 z ) ( ~ EZxE Y~1 1 1

which is obviously dominant. Then for somegE9’,, r k , ( g e f ) . SupposefE9,and r ! = , ( 3 y )(pf). We claim rka--(3y)[yEf

A-(IZ)(ZEf

AZEy)].

Suppose otherwise. Then there is some r*such that

r*ka

-

( 3 y ) [ y ~ fA

-

(32) (

Z E ~A Z E ~ ) ] .

We define a set W to be

1

(x x E 9,and for some

r** r**i=,(x~f)}.

W is not empty since g E W. The relation xEdornain (y) well-founds W. Let s be a “smallest” element of W. That is, S E W, but for no f E W is iEdornain(s). Since SE W, for some r** r**!=,(sE~). We claim r**k,-(3z)(ZEf

A ZES).

Suppose not. Then for some r***

r***k,(jZ) Thus for some r E 9,

( Z E ~A ZES).

r***k , ( r E f )

A

(re$).

Since r*** k,(res), there is some fEdomain(s)such that r*** k,(r=t)~ A (~Es).But then r*** = !-, ( t c f ) , so for some I‘****

-

r**** i=,(t~j),

CH. 7 9 14

107

DEPINAEILITY OF % MODELS

so t~ W , a contradiction. Thus r**ka-(3z) ( z ~ f ~ z But ~ s r** ) . k,(s€f) so r * * C a ( g y ) [ y g f A -(gz)(z€f A Z ~ Y ) ] , and this contradicts

r*C, Thus

-

(gy) [ y ~ fA

rka--(3y)[y€f

-

(3.1

( Z E ~A Z E Y ) ~ .

A -(32)(Z€f

A Z€v)].

But r was arbitrary. We have shown that for each f €9, the following : is valid in (g,W,C,, 9,) (3Y)(YEf)-+Y)[Yd

A+Z)(ZEf

AZEY)I.

The theorem now follows by the dominance of (*).

5 14.

Definability of the models

One of our initial assumptions was that (B, 92, ko, Y o ) € V. The definition of the sequence was an inductive definition. It should be clear that the definition can be carried out in V itself. That is, not only is (59, W,I,,Y",)E V for each CIEV,but moreover

Theorem 14.1: There is a formula F ( x , y ) over V which defines the sequence of (3, L%?, Pa, Ye).That is, for x , YE V F(x, y ) is true over V if and only if x is some ordinal CI and y is (3,92, k, 9,)(In . fact F ( x , y) can be absolute, as should be obvious.) Of course (3,92, kY9)is not in V, since, in particular, Y is not a set. But we do have

Theorem 14.2: Let X(xl, ..., xn) be any formula with no constants and no universal quantifiers. There is a (classical) formula R, (z, xl, ..., x,) with constants from V such that for any r e 9 and el, ..., c,EY, r i=X ( c , , ..., cn) if and only if R, (r,cl, ..., en) is true over V. Proofi By induction on the degree of X. Suppose X is atomic, ( x ~ y ) . Let R,(z, x, y ) be the formula Z € g A

(301)(0?'dhd(Ct)A

X € Y a A

Y€YaA

Zk,(XEy))

108

a.7815

INTUITIONISTIC M s GENERALIZATIONS

(where we have used the obvious abbreviations allowed by the above theorem). Suppose X is not atomic but the result is known for all formulas of lesser degree. IfX(x, ,..., xn) is Y(xl,..., x n ) v Z ( x l,..., x,,), by hypothesis there are formulas Ry(w, xi, ..., xn) and R,(w, x1,..., x,,). Let R,(w, xl, ..., x,) be the formula R,(w, xl, ..., x n ) v&(w, xl, ..., x,,). The case X is Y AZ is similar. Suppose X ( x l , ..., x,,) is Y(xl,..., x"). By hypothesis there is a formula RY(z,xi,..., xn). Let R,(z, xl, ..., x,,) be the formula

-

-(2W)(W€g

A Z B W A Ry(W,Xl,

...,&))a

The case X is YD Z is similar. Suppose X ( x , ,..., xn) is ( 3 y ) Y ( y , x1,...,x,,). By hypothesis there is a formula RY(w,y, xl, ...,x,,). Let R,(w, xl, ...,xn) be the formula (3y) (3a) [ o r d i n u l ( a ) ~ y € Y , A R,(w, y, xl,

0 15.

..., x,,)].

Power set axiom

We wish to show in this section that the power set axiom is valid in (9, B, c, 9). Then for some smallest ordinal uo Let co be afixed element of 9. C~EY,,. Thus uo is also fixed. We first want to show that for a fixed I'EY there is a Po such that for any CEY, if r C ( c ~ c , ) there , is some deYb, such that r i=(c= d). After showing this we will show that in fact there is one Po which will do for all r e g . For the above fixed co, a. and r,for cl, c2 E Y such that r k (cl c co) A (czcco), if for all r* and for all ~ E Y , , r*c((tEcl)

=(tEC2)),

then r I.(cl =c2). The proof is as follows: Suppose for some r* and some ~ E TY * k ( k c , ) . Since I'i=(clsco) r*t- -(hec0). Then for any r**there is a r***such that I"*** t ( k c , ) . But c O ~ Y a oso, there is some t E Y , , , such that I ' * * * k ( h = t ) ~ ( t e c , , ) . Since r***k ( k c , ) , r*** k ( t q ) . Now by hypothesis, since ~EY,,,r * * * i = - - ( t E ~ J ; SO r * * * k - - ( h ~ Thus ~ ~r)*. C - - ( k ~ ~ ) . We have shown r i= (Vx) (XEc1 3 XE c2) or r k (cl E c2). Similarly r k (c2 c c ~ ) .

--

--

CH. 7 15

109

POWER SET AXIOM

Thus (speaking intuitively) to decide if two subsets of co are equal at r we can confine ourselves to elements of Yaoprovided we look at all r*. Now let P be the collection of all elements c e Y such that TC (czc,). We define (intuitively) a function U on P by

I

U ( c ) = {(r*, t ) t e Y a 0 and r * C ( t E c ) } . By the above result, for cl,c ~ E Pif, U(cl)= U(cz),then r k (cl =cz). Let B be the range of Uon P. U:P+ B is a function but not one-to-one. So we cut down its domain to a new domain P' on which U is one-to-one. Thus for ueB, for U - l (u) choose some single element x from the class of all y e P such that U ( y ) = u . Let P'={U-'(u) U E B } .Let U' be U restricted to P'. Then U is an isomorphism between P' and B. Suppose we could show for some posV P ' E Y ~Then ~ . if CEYand I'!=(CEC,), CEP,so there is some deP' such that U(c)=U(d), so T t (c=d) and d e Y p 0 .Thus we would have the desired result. We now show P' z Y p o for some Po€ V.

I

Lemma 15.1: There is a formula F ( x ) over V such that X E Piff F(x) is true over V. Pro08 Let R, (z, x , y ) be the formula defining z k ( x s y ) as given in the last section.Let F ( x ) be R, (I',x , co). Lemma 15.2: There is a formula G(x, y ) over V such that y ~ U ( xiff ) G ( x , y ) is true over V. Proofi Let R, (2,x , y ) be the formula defining 2 k ( x ~ y )Let . G(x, y ) be F ( x ) A (3r,s) [ y = ( r , s ) A r , g

A

~

€A r.@r 9 A~ R E ( r~ , s ,x)].

Lemma 15.3: For any c e Y U ( c ) e P ( gx Y a o ) V. e ( P ( x ) is the power set of x in V.> V (and is defined by G(c, x)). Proofi U(c) is a subset of B x Lemma 15.4: B EV. Pro08 By lemma 15.4 ( U ( x ) ~€9') is a subset of P ( S x Y a o ) eV. (It is a definable subset, defined by

I

(3a) (ordinal ( a ) ~ ( 3 c( )c e Y a ~ G ( cx))) ,

).

Lemma 15.5: There is a formula H ( x , y ) such that X E ~ for , y a subset of 9, if and only if H ( x , y ) is true over V (that is, a choice function). Proof: That Y can be well ordered in .V is straightforward.

110

INTUITIONISTJC M a OENERALIZATIONS

CH. 74 15

Theorem 15.6: P' G Y,, for some Po E V. ProoJ The function U - l (u) can be defined by: U-' (u) is that x such that H ( x , y ) where y = { z e P I U(z)= U(u)}, which can be formalized. Now P' is the range of U-' (u) on B. By the axiom of substitution in V P ' E V. Hence P' G Y f lfor o some Po E V,since P' -c Y and Y is a class. Thus we have our first assertion. We have written it out fairly completely as illustration. From now we will only indicate the steps. Above, for b e d r we produced an appropriate But the procedure can itself be defined over V. Since Y E V ,by the axiom of substitution again, there is a maximum floeV which works for all 3.Thus we have shown : There is a j3,~ V such that for any CEY and any reg,if TI=( c s c , ) , then for some d~ 9,, r k (c =d). Now we can show the following, from which the power set axiom follows, since co was arbitrary:

a,.

Theorem 15.7: The following is valid in ('3, W ,b, 9'): (3y)

- (32)

[(ZEY)

=(z c coy '

Proofi Let X ( x ) be the formula ( x c c 0 ) , with c , E ~ ~ ,Let . Po be as above, and let y=max(ao, Po). Then Y E V. Considerf,EY,+, -9,. We claim ~ ( ~ Z ) - [ ( Z E ~ ~ ) = ( Z C C ~is) valid. ] Let Y and suppose r*pC ( h ~ f , ) Then . for some r** r**b (hefx), so there is some ~ E Ysuch , , that r * * k ( t = h ) ~ ( t E f , ) . By dominance T**ky+l(tEf x ) , r * * k Y X ( t ) , so r**k,(fcco), by permanence r * * b ( t ~ c , ) .Thus r**C-- ( h ~ c , ) ,so T*W-(hsc0). We have shown

-

r c(vx) [- ( h E c,> or equivalently,

rc

- r* - c (3x1

2

-

(h~j-~)]

. co). Then for some r** r** k (hcco).

[ ( h ~ j -=)~()h G c,)]

Conversely suppose pl (h There is some t E Y B o such that r * * k ( h = t ) . So r * * b ( ( t c c , ) stable.) By dominance r**k Y ( t c c,,),

r**c, x (t) ,

( x c y is

CH. 7 9 16

X-EQUIVALENCE

111

and the theorem follows.

Remark 15.8: Above we obtained Po by two applications of the axiom of substitution. These could have been combined into one step as in Cohen [3]. This proof was based on that one, which followed a suggestion of Solovay. We find this two step approach more intuitive, but the treatment in Cohen is more elegant.

0 16. X-equivalence Definition 16.1: Let X be a formula with no universal quantifiers and all constants in 9,.We call (3,92, Fa, 9,) X-equivalent to ( 9 , W , t, 9') if for every Y which is an instance of a subformula of X with all constants in 9,for , any re9

rc,y-rcy.

Theorem 16.2: Let X be as above, with all its constants in 9,There . is is X-equivalent to an ordinal PEV, a
Definition 16.3: Let BE V and X be a formula with all its constants in Sps. We call X (for this section only) /?-dominantif for any I ' E g

r c,x r ~ x . Lemma 16.4: Any atomic formula over 9, is j-dominant. If X and Y are p-dominant, so are -X, ( X v Y ), (XAY)and ( X 2 Y ) . Proofi Straightforward.

112

INTUITIONISTIC M a GENERALIZATIONS

Lemma 16.5: Suppose for every a G Y , k b (3x1 q x ) , k (3x1 x(x).

r

CH. 7 $16

X ( a ) is p-dominant. Then if

r

Pro08 r k , ( 3 x ) X ( x ) implies r k p X ( a )for some, aE9’,. By hypothesis

r k X(a), SO r k ( 3 x ) X ( X ) .

Now for the proof of the theorem. Recall Xis a formula over 9,. There Y,, ..., & with free variables but are only a finite number of formulas no constants, such that every subformula of Xis an instance of some Yi. By theorem 14.2 there are formulas RY1,RY2,..., Ryn over V such that

c,

-

r b q c , , * - * , Ck) RYt(C c1, Ck) is true over V. We define informally a sequence in V. Using the above RY,, the sequence can be formally defined over V. We note again that there is a formula over V which well-orders the class 9’. Let Do = 9,. Suppose we have defined D,, which is some 9, for BE V. D, can be well-ordered in V, so all subformulas of X with constants from 0, and of the form ( 3 x ) Z ( x ) can be well-ordered (isomorphically)in V. If (3x) Z(x) is a subformula of X and has all its constants from D,, and if there is a r e 9 such that rk(3x)Z(x), for some C E YrkZ(c). Choose the smallest c in the well-ordering of Y such that r k Z ( c ) . Let K,+, be D, together with all such c. K,+, can be defined as the range of a function, definable over V, whose domain is the collection of ordered pairs (x, y ) where X E and ~ y is a formula of the form (3x) Z ( x ) , a subformula of X over 0,. This domain is a set, hence K,,, is a set. But K , + I ~ 9 ’ .Thus thereisaleastyEVsuchthat K m + , ~ S PLetD,+,=Y,. Y. In this way, we define the sequence Do, D,, D,, ... But this sequence can be defined formally over V. Thus UD, is an element of V. But by the definition U D , must be some Y bfor BE V (since D , c Dkfl). We have produced an Y @V, E ol
-

em.,

The proof is by induction on the degree of Y. All the cases but one are immediate by the above lemmas. The only non-trivial case is the following. Suppose (3x) Z ( x ) is a subformula of X , has all its constants in Y,, and Fk (3x) Z ( x ) . All the constants of (3x) Z ( x ) lie in UD,, but there are only finitely many, so for some integer k, all the constants of

CH. 7 8 17

113

AXIOM OF SUBSTITUTION

( 3 x ) Z ( x ) lie in

Dk.By definition there is a C E D , + , C Y ~such that

r k Z(c). By induction hypothesis rk,Z(c),

so rC, ( 3 x ) Z ( x ) .

5 17. Axiom of substitution As we did for the power set axiom, we wish to show the axiom of substitution is valid over (9, 9, C, 9’). The proof is essentially that of [3]. Let X ( x , y ) be a formula with no universal quantifiers, and constants which defines a function at r, that is, such that from 9,

rF

- (3x1

(3! Y ) x(x, Y ) ,

where (3 !y ) 2 (y ) abbreviates

( 3 4 (Z(4A (w = Y))l* Let c, be afixed element of 9’. Let a, be the smallest ordinal such that co E: YaO. We want to show there is some f E 9’such that (3Y) r a y )

rb

- (jx)

A

= ( 3 ~ ()w E C ,

A x(W, x ) ) ] .

[ X E ~

That is, roughly, .f is the range of X on co at r. By 0 14 there is a formula R,(z, x, y ) over V such that d I.- -X(x, y ) iff Rx ( A , x , y ) is true over V. Let g(A, c) be the smallest ordinal P such that for some c’EY, A I. X ( c , c’) if there is such, and 0 otherwise; g is definable over V (using RJ. Since a, E V , Q x Y a 0 eV. By the axiom of substitution in V, the range of g on Q x Yacis a set in V. Thus also (range g on 9 x SPpl,)€ V. Let Po be this union. Then Po is an ordinal, Po€ K

--

u

Lemma 17.1: Suppose r*b ( 3 x ) (XEC, A X ( x , d)). Then there is some C’E Y,, such that r*I=(c’ =d ) . Pro08 r*k ( 3 x ) ( X E C , AX(X,d ) ) so for some C E Y r*k(CECg)

A

x(C,d ) .

c o ~ Y aso o there is some t€Ya0such that I ‘ * k ( t c c , ) ~ ( t = c ) . Hence r * k - - X ( t , d ) . Now
r*C-

N

X(t,d) ahd

r*k -

(3x)

-

( 3 ! y )X ( x , y ) ,

114

Ma

I"IST1C

so by intuitionistic logic

m.7§17

OENERALIzAnoNS

r*I=

=d)

(C'

( ( x = y ) is stable).

Let cp(x) be the formula ( 3 w ) [ W E C , A X ( W ,x ) ] . There are only a finite number of constants in cp(x) (recall that X may have constants), hence all lie in some 9,(take y>/3,). By theorem 16.2 there is some SEV, yG6,such that ('3, 9, C,, 9,) is cp-equivalent to (9, W ,t, 9>. Since cp is a formula over 9,, cp is also a formula over 9,. Thus it + - 9, We . claim defines a function f v E 9,

rk

- (3X)

[X E f

v

E

(3 W ) (W E Co

A

x ( W , X))] ,

which is what we wanted. We' now proceed with the proof. Suppose r*pc- ( c ~ f J . Then for some r** r**k(cEf,). Since f,E9,+i-9,, there is some d E 9 , such that r * * C ( c = d ) ~ ( d ~ By f~). dominance r**ka+l(d~f,).r**C,cp(d), But (9, W ,Cay 9,) is cpequivalent to ('3, 9, C, 9)hence

r**I= cp(& r**C""'p(C),

r*y -cp(c>, r*y - ( 3 w ) ( w e c ,

AX(W,~)).

Thus we have shown

r C (VX)

[ (3W ) (W € CO A

Conversely suppose

N

r*y - ( 3 w )

x(W, X))

3 N (X

E

f,)] .

( w ~ c , n X ( w c)). , Then for some

r**k(3W)(W€C,

r**

A x ( W , C)).

By the above lemma, there is some c ' E such ~ ~ that ~ r**k (c'=c). Hence r * * P - N ( g w ) ( w ~ c , ~ X ( wc')), , that is, r**C--cp(c'). But C ' E ~ ~ ~ C and Y ,('3, E ~ W ,,C,,~ Y 6 )is cp-equivalent to (S,W ,C, 9), hence

-- --

r**c, r**k , + l r**C

But

cp(c')

"

(C'EfQ?),

(C'Ef,).

r**k(c'=c),

y

m.7§17

so

AXIOM OF SUBSTITUTION

r**k

ru

(C E

&,) ,

r*gc 4 E f p ) . We have shown

The assertion now follows.

115

CHAPTER 8

INDEPENDENCEOFTHE AXIOM OF CHOICE

0 1. The specific model The model given here is adapted from the one of Cohen [3]. We have changed it from showing directly that there is an infinite set with no countable subset to showing directly that there is a set with no choice function. The change was made because the notion of countability requires much more machinery in these models. See [3, p. 1361 for a brief introduction to the model. Following ch. 7 9 3, a sequence of models and a class model are defined if the 0th model is fixed. We now define a specific ( ' 3 , W , k0, Yo). All the work is relative to a classical.mode1 V. Let e be some formal symbol. By aforcing condition we mean a finite consistent set r of statements of the form (nem) and -(nem) (n>O, m a 1). ((nem) can be some ordered triple in V, say ( n , 0, m ) . Anything convenient. Similarly -(nem) can be some other triple, say ( n , 1, m ) . We have written it like this for reading ease.) Let 99 be the collection of all forcing conditions, and let W be set inclusion E. Before defining Y o we , define the following partition of the integers:

I, = {1,3, 5,7, ...>, Il= {2,6, 10, 14,...}, I2 = (4,12,20, 28, ...}, in general

etc . In = {2"(2k

+ 1) I k = 0, 1,2, ...>.

m.8§1

117

THB SPECIFIC MODEL

This partition has the properties that each I,, is infinite, and if n E I,,, n >m. Now we define Y o .It consists of the functions A

A

A

0,1, 2, **.,

to, ti,

s1, 82, s3,

t , *.*, ~

whose definitions are the following: For each integer n the function A has domain k
R(E)

T, A

@,T, ..., n -

1}, and for

= 9.

Each s,, has as domain (0,1, 2, ...} and A

h

,

.

I

sn(h) = { r e g ( m e n ) E r } .

Each tn has as domain {s,, s2, s3,...} and tn(sm) =

I

9 if mEI,,, 8 otherwise.

T has as domain { t o , t,, t z , ...} and T(t,,)= 9. From this technical definition ko for atomic formulas becomes

iff m < n , iff ( m e n ) E T , rkO(s,,,Etn) iff mEIn, r bo (t,, E T ).

rko(htE)

rko(&Esn)

We now examine the five properties of ch. 7 5 3. (l), (2), (3) and ( 5 ) are trivial. (4) is satisfied in the very strong sense that for any r E 9 and any a, b € Y 0 ,if r bo (3x1 [ X E a = x E bl ,

- -

then a and b are the same function. This is proved by examining the various possible choices for a and b. We show only the most difficult case and leave the rest to the reader.

Theorem 1.1: If m#n, -(sm=sn) is valid in (9, 9, ko, Po>. Proo$- We show for a n y r E 9 ry o(sm=s,,). SupposeI'k,(sm=sn)for some Since r is a forcing condition, it is finite, so we may choose an integer k such that neither (kern), -(kern), (ken), -(ken) belong

118

INDEPENDENCE OF THE AXIOM OF CHOICE

c~.8§2

to r. Let A be r u {(kern), -(ken)}. Then A E S and I'WA. By definition A k0 (&EX,,,). Since A C, (3x)- (xEs,,,=xEs,,), by intuitionistic logic Aka- -(&Es,,). Then for some A* A*Fo(ft~s,,), which means (ken)EA*. But (ken)Ed*, a contradiction.

-

-

Thus all five conditions are met so the resulting class model <S,5% k, 9) is an intuitionistic ZF model.

0 2. Symmetries Let G be the collection of all permutations n of integers such that n permutes the elements of one I,, and is the identity on all I,,,for m f n . We may extend any R E G to 9 as follows: n(A) = A ,

(4

n = sn (n) n(tJ = t,,, n(T)= T .

9

Let X be the formula X ( x , cl, ..., cn) where n has been defined for cl, ..., c,,. Let n(X) be X ( x , ~ ( q ) , . .n(c,,)). ., If f x E 9 a + l - 9 a , let n( fx)bef,(,,. Thus n is extended to 9. We also extend n to B by N

We note that

( n e m)s r o (n e n (m))E n (r), (n e rn) B r o ( n e n (m))E II (r). N

r E S implies n (r)E 8.

Theorem 2.1: For any formula X with all constants in Yaywith no universal quantifiers, any r e 3,and any 'ICE:G

r c,x e n ( T )Ca7C(X), and

r c x o n (r)c 7z ( X ) .

Pro08 A straightforward induction on a and the degree of X. Dejinition 2.2: Let N be some collection of integers. By GNwe mean the subset of G leaving N invariant.

Lemma 2.3: Let f€9. There is a finite set N of integers such that if ZEGN, n(f)=f.

~~.8@3,4

119

FUNCTIONS.AXIOM OF CHOICE

ProoJ IffeYo, we have two cases. If f i s not some s,,, let N=0. If f i s s,,, let N = {n}. Suppose the result is known for all g E 9,LetfE . Y,, - Ya. Thenf is fx for some X ( x , el, ..., cn), where cl, ..., ~~€9,. By hypothesis there are , Let finite sets Nl, ...,N,, of integers such that if Z E G ~ n:~(ci)=c,. N = N , u-.-uN,. Then if m G N ,n ( f X ) =f n c X , = f x .

0 3. Functions We introduce the following formula abbreviations:


x= z> (x, ~ ) E Z ordpr(x) relution(x) function(x)

--- - -

for (3w) [wEx A w = {y, z} A x = {y, w > ] , for ( 3 w ) [ W E Z A w = (x, y ) ] , for (3y) [ y ~ 3 x (32) ( 3 w ) ( y = ( z , w ) ) ] , for (3y) EX 3 ordpr(y)], for relarion(x) A (3y) (32) ( 3 4 ) (3u) N

[(( y, 2 ) EX A (u, u ) E X A y = u) 3 z = u] ,

dornain(x)=y

for

-(32)(3w)-

- -

[(Z,W)EXIZE~] A

(32)

[ Z E Y I( 3 w ) ((2, W > E X ) ] .

Theorem 3.1: All the above formulas are dominant.

0 4. Axiom of choice Let AC (T) be the formula

- (W

(3x) {fmction(x) A dornain(x) = T A

[YET= ( 3 4 ( z vA

(v,Z)E41).

-

That is, AC (T) says that T has a choice function. In this section we show that AC (T)isvalid in (9, W ,I=, 9'). In fact, it is valid in (g,W,t,, 9,) for every a ; the same proof holds for each case. We first show a preliminary Lemma 4.1 : Iff E 9 'and r k (fE t,,) then for some m E I,,

r l a (f = sm). Pro08 r I = ( f e t , )so there is some bEdornain(t,,) such that

r q j =b)A(bEf,,).

120

INDEPENDENCE OF THE AXIOM OF CHOICE

~ ~ 1 . 8 8 4

Now suppose there is some r E 5 ? such that I'kAC(T). Then for some FE9,

r i=function ( F ) A domain ( F ) = T A

-

(3Y)"

C Y E T I

(32) ( Z E Y

A

(YY

Z)EF)I.

There is a finite set N of integers such that if Z E G ~ z(F)=F. , Let n=l+maxN.

-

ri=( 3 ~ ) [ Y E T

3

( 3 2 ) (W

A

(Y, Z>EF)I

and r k (t, E T ) hence

rk

(3.1 ( z E t,

A

(tny Z> E F ) .

Then for some I'* r*C(3Z)(ZEtn

A

(t,, z ) E F ) .

For some a E : Y r*C(mEt,)

A

(t,,a)EF.

By the above lemma, for some mEZn, I'*b (a=$,). Hence

r*

N N

(
Q E F )3

for some r**,r**k (t,, s,)EF. Now mEInyso m > n = l +maxNy hence m#N. Choose an integer k > n such that k f m and neither ( p e k ) nor - ( p e k ) belongs to r**for any integer p , but kEI,. (T** is finite but I,, is infinite, so this is possible.) Let TL be the permutation 7c(m)=k, n(k)=m, on all other integers 7c is the identity. Since myk$N, xeGN.Now SO

7~

(r**) i= 7~( EF)

9

n(r**)C
n(Sm)>En(F),

n:(r**) c (t,, sk) E F . But A =r** u n: (r**) is itself a forcing condition. It is finite, and since r**and 7c (r**) must be the same except for statements involving m and k , and m is not (a second element of any statement) in .n(T**) and k is not in r**,z(T**) and are compatible. Thus A E and ~ r**WA and n(T**)WA. So A C function F , (since r t= function F ) A i= (tny S r n ) E F , A k {t,,, Sk) E F .

r**

c~i.894

AXIOM OF CHOICE

121

It then follows by intuitionistic logic that

a != or since (x =y ) is stable,

--

(s, = Sk),

A k (s, = s~). But m # k , contradicting theorem 1.1. Thus for all I ' E ~ so

As we showed in ch. 7 9 1 the axiom of choice is now classically independent.

CHAPTER 9

ORDINALS A N D CARDINALS

0 1. Definitions Continuing ch. 8 0 3 we introduce the following formula abbreviations: range(x)=y for - ( ~ z ) ( ~ w ) - [ ( W z , ) E X D W EA ~ ] (3w) [ W E Y 2 (3.)
- -

-

-

N

H

-

=JJJ

- -

N

(3W) [ W E y A

N

(324)N ( U E y 3 ( W € U V W = U ) ) ] ) ,

ordinaf(x) for trans(x) A welord(x).

Theorem 1.1: All of the above formulas are dominant.

The proof is again primarily an application of ch. 7 9 7.

0 2. Some properties of ordinals In this section we establish some useful analogues of classical theorems. We use a method of proof which we call a classical-intuitionistic argument. Rather than stating it generally, we illustrate its use by writing out in full the first proof below.

CH.963

-

123

GENERAL ORDINAL REPRESENTATIVES

Theorem 2.1: (3x)- (ordered(x)= weZord(x))is valid over (9, W,C, 9) (and by dominance, over any (3, 9, ka, S p a ) ) . Proofi It is a standard classical result that

ZF, axiom of regularity I-,-

(3x)

-

(ordered(x)= welord(x)).

So for some finite subset of ZF with no universal quantifiers I-, (A,

A

A

- -

A,, A axiom of regularity) 3

(3x)

By the results of ch. 4 Q 8 together with

t-, and

-

-(X k*

3

Y )3 ( X

N "

3N

(ordered(x) 3 welord(x)).

-

Y)

x =-x

we have

kI (A,

A

...A A,, A axiom of regularity)

- 3

( 3 x ) (ordered(x)3 welord(x)).

Since ( 9 ,9, C, 9)is an intuitionistic ZF model, = welord(x)) is valid.

-

(3.4- (ordered(x)

Theorem 2.2: If r C ordinal(f) and r C g E f then r C ordinal(g). Proo$ By a classical-intuitionisticargument we have :

-

(3x) ( 3 y )

-

[(ordinal(x) A y e x ) 3 ordinal(y)]

is valid in ('3, W,k, Y>. The result now follows by stability of ordinal( y). Theorem 2.3: If

r C ordinal (f ) A ordinal ( 9 ) then rk--(fEgvf=gvg€f).

0 3. General ordinal representatives We define inductively representatives for the classical ordinals. Later we discuss their existence and uniqueness. Definition 3.1 : Suppose we have defined genera2 representatives in Y for all ordinals p
124

ORDINALS AND

cmmbJs

(2). if l-k (hef ), there is some r*,some represents 8, such that r*!= (g =h).

m.913

a< a, and some g E9’which

Theorem 3.2: If f €9’ is a general representative of some ordinal, ordinal( f )is valid in (a, 92, k, 9’). Proox Suppose f represents the ordinal tl and the result is known for all representatives of ordinals p ( a ~ fA )(k f ). For any r*, r*!= ( a ~ fA )( b ~ f )By . properSuppose r!= ty (2), there is some r**and some a‘, b ’ E Y such that a’ represents fl and b’ represents y where P
--

r**k--(dEb’

v a ‘ = b’ v b’Ea’).

so r**C--(uEb

v a = b v bEa).

Thus as above rk--(aEb

v a = b v bEa).

Again r is arbitrary, so ordered( f ) is valid. 111. ordinaZ( f ) is valid in (9, 9, I., 9 ) By the above trans( f ) A ordered( f ) is valid. Then welord( f) is also valid by theorem 2.1 (weZord(x) is stable). Thus ordinuZ(f) is valid.

Theorem 3.3: I f f , g E Y are both general representatives of the same ordinal, ( f = g ) is valid in ( S , W,by 9). Proofi Suppose f and g both represent tl. If I ’ b f h G f ) , for any I’* r*!= ( h ~ f )By. property (2), there is some r**,some P
--

$8 4,s

CANINOCAL ORDINAL REPRESENTATIVES. ORDINALIZED MODELS

125

so rk--(h€g). Similarly if T k ( h ~ g ) ,I ' l = - - ( h ~ f ) . But trary, so the result follows.

r is arbi-

CH. 9

0 4. Canonical ordinal representatives Again we postpone a discussion of existence. Dejnition 4.1 : We call f E 9'a canonical representative of the ordinal tl if (1). f i s a general representative of a, (2). forno g E d o m a i n ( f ) a n d f o r n o r c S r k ( f = g ) , (3). if r k - - ( g ~ f ), r C ( g ~ f )for gEdomain(f).

Theorem 4.2: Suppose f E .Y,+ - 9,is a canonical representative of some ordinal. Then f is fx where X ( x ) is the formula ordinal(x). Proofi We must show for any UEY,

rka+l(ue f ) iff I'k,ordinul(a). ( a ~ f )By . theorem 3.2 r C ordinal(f), so by theorem 2.2 Suppose r (and dominance) r k,ordinal(a). Suppose r!=,ordinal(u). By theorem 3.2 r k ordinal(f). So by theorem 2.3 (and dominance) rk--(aEfVu=fvfEu).

Thus, for every r*there is some r**such that r**+Ef)

v (u = f ) v ( f + .

If r * * k ( f e u ) , since U E ~ , there , is some 9 ~ 9 'such ~ that r**k(f=g) contradicting part (2) of the above delinition. Similarly r**Y f = a . Thus r**k ( a ~ f )So. r k ( a ~ f )and , by part (3) above r C ( uf ~). Now by dominance r ku+l (a€f ). N

-

$ 5 . Ordinalized models We give a condition on our model (actually on (9, 9, k0, Yo)) which will insure existence and uniqueness of canonical representatives for the ordinals. We call ( 3 , W,k, 9'>ordinalizedif (I). no ordinal has more than one canonical representative in Y o ,

126

ORDINALS A N D CARDINALS

CH.965

(2). i f f e y 0 and r b ordinal(f) for some rg9, then there is some r* and some h E 9 , which is a canonical representative of an ordinal, such that r*C (f=h). Remark 5.1: By dominance, whether (9, 9,C, 9)is ordinalized can be decided by considering only (9, W ,C,, Yo). Theorem 5.2: If < 9 , W , C, 9’) is ordinalized and f, g E Y are both canonical representatives for the same ordinal, f and g are identical. Proofi Suppose first that g E 9 , and f ~ 9 ,-+ 9,~ . By theorem 3.3 (f=g) is valid, contradicting part (2) of definition 4.1. There is a similar contradiction i f f € 9,and g E 9a+1 - 9,. Thus, either f, g E Y o ,or for some a , f , g€9’,+, - Y,. Iff, g e 9 , , by part (1) of the above definition they are identical. Iff, g E 9,+ - Yaythey are identical by theorem 4.2

Thus if an ordinal has any canonical representatives, it has only one. From now on, by representative we will mean canonical representative, and we will denote the representative of c1, if it exists, by 62. We give the following temporary definition. We say BEY has the representative property provided: if a is the smallest ordinal not representable by an element of 9’,,a is representable by an element of 9’,+l. In other words, has the representative property provided: if for all yea, ~ E Y ,but , 62$9’,, then & ~ 9 ’ , + ~ - 9 ’ ~ ,

Lemma 5.3: If (9, 9, C, 9’) is ordinalized and if all ordinals ep have the representative property, so does p. Proof.- Let a be the smallest ordinal not representable in 9,We . must show 62~9’,+,-9,. Let X ( x ) be the formula ordinal(x), and let f x E 9 D + 1 - 9,. We claim fx is &. Suppose r C (h~f,). Then there is some g E 9, such that r C (g =h) A ( g E f x ) . But then r k , X ( g ) , rC,ordinal(g). We now have three cases. 9, C, 9) is ordinalized, there is some r * and Suppose j= 0. Since (9, some k e y , which is an ordinal representative (and by hypothesis, of an ordinal e a) such that r*C ( k = g ) . Thus f* != (k=h). Suppose /3 is a successor ordinal. By hypothesis 8- 1 has the representative property. Let y be the smallest ordinal not representable in 9,-i.Then 9 €9, Now . (theorem 3.2)

r k ordinal(?) A ordinal(g),

121

If r*C ( g E f ) , by definition of 9 there is some r**and some 6 < y such that r** C ( 8 = g ) and so r**C (8=h). If r*k ( g =9) then r*C (h=9). Finally, we can not have T*k (PEg) for, since g E 9’@ there is some k E Y c - l such that r * k ( ? = k ) A ( k E g ) . But P E S ~ - Y and ~ - ~this contradicts part (2) of definition 4.1. for some q
N

-

-

N

-

Theorem 5.4: Suppose < S , W ,C, 9 ) is ordinalized. Then every ordinal in V is uniquely representable by an element of 9. Proofi Immediate by lemma 5.3. Remark 5.5: Although it seems unlikely, it is conceivable that some ordinal not in Y might be representable by an element of 9. In fact this can not happen. Suppose for some y$V PEY.For some UE V 9 ~ 9 ’ ~ . The class of elements of 9’ which are ordinal representatives is definable over V. The intersection of this class with Yais a set, i.e. an element of V. But the relation r k a ( x e y ) well-orders this set, the relation is in V, and the order type must be y (or greater). Hence ye V.

128

ORDINALS AND CARDINALS

cn.9 % 6,7

Thus exactly the ordinals of V are representable in ordinalized (9,2,kY y>.

9 6. Properties of ordinal representatives Theorem 6.1: If ( S , W , C, 9)is ordinalized and a, PE V, then if for some r c 9 rC(&=B), a = p ; and if a=p, (a=)) is valid. Pro08 If a
--

-=

Theorem 6.2: If (9,9Zyk, 9)is ordinalized and a, BE V, then if for some r E S rk(&B), ~ E B and ; if a ~ p ,(&€I)is valid. Proof: If rC(&e)), by part (2) of definition 3.1 for some r*and some y
0 7. Types of ordinals We introduce the following formula abbreviations: successor ordinaZ(x) for ordinul(x) A ( 3 y ) ( Y E X A x = y’), limit ordinuZ(x) for ordinaZ(x)A ( 3 y ) ( y ~ 3x EX), integer(x) for ordinul(x) A limit ordinal(x) A (3y) EX A limit ordinul(y)), x is w for limit ordinuZ(x) A ( 3 y ) ( y e x A limit ordinal(y)). N

N

N

-

N

m.988

129

CARDINALUED MODELS

Theorem 7.1: The above formulas are dominant. /\

Theorem 7.2: If (9, W,C, 9')is ordinalized, a+ 1=&'is valid. Proox We must show for all rE9

- -

A

+ 1 = (xed v x = a>]. Suppose T C f e a + 1. Then for every I'* r*C f €a+ 1. There is some r**

rc

(3x1

[XE

a

A .

and some /?
/A

But /?
r C ( f e & vf =a), then f C-J - ( f e a + l ) . The result follows.

-

Corollary 7.3: If (9, W,1, 9') is ordinalized, successor ordinaZ(a+ 1) is valid.

Theorem 7.4: If (9,9, C, 9')is ordinalized, and for some f ~9' and some re9 rksuccessor ordinulf, then for some r* and some u + l /---

r*C (f=a+ 1). Pro08 r C successor ordinal f,so for some g E 9' r C ordinalg A g Ef A f =g'. Since rkordinalg, there is a r* and an ordinal a such that r*C g =&. Then r*by=&', r*Cf=a+ 1. /\

In a similar manner we may show

Theorem 7.5: Suppose (9, 9, C, 9 ')is ordinalized. Then (1). If 1 is a limit ordinal, limit ordinul(1) is valid. (2). If r k limit ordinul(f), then for some r* and some limit ordinal1 r*c ( f = Q (3). If n is an integer, integer(t3) is valid. (4). If r C integer (f),then for some r*and some integer n r*I=( f = A). (5). Q is o is valid. (6). If r1f is a,then fur some r* r*k(f=b).

0 8. Cardinalized models Let cardinaZ(x) be an abbreviation for

-

ordinuZ(x) A ( 3 y ) (32)

EX AfUtzCtiOtz(z) A 1-1(z) A domain(z)=y A range(z)=x]

We remark that curdinaZ(x) is not dominant (probably) but it is stable.

130

0RDmAI.S AND CARDINALS

CH.989

Suppose (9, W,I=, 9)is ordinalized. We call it cardinalized if for W,C, 9). every CLEV, if a is a cardinal of V, cardinal(&)is valid in (9, By the classical-intuitionistic technique of Q 2

- (3x)

and

[integer ( x ) 3 curdinaZ(x)]

( a x ) N [x is o 2 cardinal(x)]

are both valid in (9,9, C, 9). But then by Q 7 for any integer n cardinaZ(f3)is valid. Also cardinal(&) is valid. Thus the troublesome cardinals of V are the uncountable ones. In the next section we give a condition due to Cohen which will take care of such cardinals. Remark 8.1 : To say (S,W,b, 9’) is cardinalized is to say the cardinals of V are among those of (9, 9, !=, 9). In fact, we will show in ch. 13 that the cardinals of (9, W,C, 9)are the same as the cardinals of L, the class of constructable sets of V.

9 9. Countably incompatible 9 The following argument is from [3]: DeJinition 9.1 : Two elements r, A E S are called compatible if they have a common W-extension, that is, if some r*is some A*. Otherwise r and A are incompatible. 9, V is called countably incompatible if any subset of S of mutually incompatible I‘ is at most countable in V.

Lemma 9.2: Suppose (9, 9, C, 9’) is ordinalized, 93 is countably incompatible, &, )~9, card(@)
-

(3f) [function(f) A 1-1(f)A domain(f) = & A runge(f) = j ]

is valid in <S,W,C, 9). Proofi Let f be some k e d element of 9. We remarked earlier that the class of ordinal representatives was definable over V. Let F(x) be the formula defining it. Let A ( x , y , z) be the formula [ X E ~ A Y E Y A F ( ~ ) A~ Zz !E= S( f m c t i o n ( f ) A l - l ( f ) ~ d o ~ a i n ( f ) = & ~ r a n g e ( (f x) ,=y )) ~~ f ) ] .

CH.999

COUNTABLY INCOMPATIBLE

Suppose for 9, 8, A , A', c that A ( c , 9, A ) and A (c, true over V. If A and A' are compatible, some A* 1( c ,

9 ) ~ Af

131

g

8, A')

are both

(c, @ E f .

Hence A* k 9 = 8 so y = 6. Thus if y # 6, A and A' are incompatible. Thus for any fixed CE Y and any A E 59 there are only countably many ordinals y such that A (c, 9, A ) is true over V, by the countable incompatibility hypothesis. Let B(x, y ) be the formula @ A ) ( d ~ Ag A ( x , Y,A ) ) . Then for fixed CEY, the set defined by B(c, y ) is at most countable. For any ordinal a, let a' be {p y
I

I

Let C' be the class in Vdefined by C(x), and let C be {y ~ E C ' } Since . C' is a definable subset of Po, C E V. For a bound on the cardinality of C we note that for any CEN', there are at most KO x such that B(c, x). Thus card C
then there is some A* and some ~ E such C that A* k @=I$).For since A k (c, d ) ELthere must be some A* such that A* t ( ~ E B and ) hence a A** and a 8 ~ j such ? that A** k (d=8). Thus

A** k (function (f)A 1-1 (f)A domain (f)= & A r a n g e ( f ) = fi so A ( c , 8, A**) is true over V , B ( c , 8) is true over I/, c (8) is true over V , 6EC. Now suppose there were some I ' E 5 9 such that

A

(c,

8)~f).

132

cH.959

ORDINALS AND CARDINALS

Since curd(C)<curd(/?),but CG/?, there is some YEP, y$C. Since YE/?,

r k ( p ~ f i ) .Then since r t= (range (f)=B), for some r* I-* k(3c)

(CE& A

( c , ?J)Ef),

so for some CEY,

r*!=
*

That is I'* k (function (f)A 1-1 (f)A domain (f)= & A runge(f) =

By the above there is some r**and some ~ E such C that but then y = 6, so y E C, a contradiction. Since f is arbitrary, the result follows.

A

(c, p) ~ f )

r**t= (?=a^),

Theorem 9.3: Suppose (8,9,t=, 9') is ordinalized, 92 is countably incompatible, and /? is a cardinal of V. Then cardinaZ(fi) is valid in (3, =%t=, 9).

Proo$ By the last section we need only consider B > K , = o . r pC curdinuZ(fi).Then for some a, f, r*,

Suppose

r * k ( d E f i ~ f u n c t i o n ( fA) ~ o L w ~ ~ z ( ~ ) =r &u nAg e ( f ) = B ) .

Since r*k ( a ~ f i ) ,a ~ p so , curd(a)< curd@) (p is a cardinal). Now, by lemma 9.2 we are done.

Remark 9.4: A simple corollary of this theorem (which should be obvious anyway) is the following. If L is the class of constructable sets of V, not only is L a classical ZF model, but, if a is a cardinal of V, a is a cardinal of L. This follows by noting that in the intuitionistic formulation of the classical Ma sequence (remark 7.3.3) 8 is trivially countably incompatible, since 8 is finite, and since Mo =(by the model is ordinalized.

CHAPTER 10

INDEPENDENCE OF THE CONTINUUM HYPOTHESIS

0 1. The specific model Again the model is adapted from Cohen [3], with practically no change. We define a particular (3,g,ko, Y o ) . Recall V was some classical ZF model. Let 6~ V be that ordinal which is N2 in V. 6 remains fixed for the rest of this chapter. As in ch. 8, let e be some formal symbol. By a forcing condition we mean a finite, consistent set of statements of the form (neu) or -(neu) where n is any integer and ct is any ordinal <S. Let 3 be the collection of all forcing conditions, and let W be set inclusion E. Y oconsists of functions which we write as 8, a,, {a}, {a, a,} and (a, a,) for each u<6, and W.The definitions are the following: For each u <6 the domain of is {b fi
I

a@) = 3. a, has domain

@,I,2,. ..} and

I

u,(R) = ( r e g ( r n e n ) E r } .

{a} has only

in its domain, and

{a} (a) = 3.

134

{a, a,}

INDEPENDENCE OF THE CONTINUUM HYPOTHESIS

CH.

10 5 2

has only 61 and a, in its domain, and

(4a,} (h) = 9 (a, aa} (a,) 9 (a, a,) has only {a} and {a, aa}in its domain and (4a,> ({a>>= 9 , (a. a,) ((4a,}) = 9 Finally W has as domain all (a, a,) for a<6, and Y

*

*

W ( ( & a,>> = 3. From this ko for atomic formulas becomes rko(W), if a e p , r t o ( R ~ a , ) ,if ( n e a ) E r ,

{&I)

c o (a E Y r t o ( & E { & , a,}),

r t o (a, E (4a,}) r ko ({@E (a, %>> r t o ((4a,} E (4a,>) r t o ( E W ) . Y

Y

Y

Thus (9, W, toyY o )is determined. We examine the five properties of ch. 7 0 3. (l), (2), (3) and ( 5 ) are trivial; (4) is satisfied in the same sense as in the model of ch. 8, that is, if r ko (a= b), a and b are identical. The proof is the same as in ch. 8. Thus (9, W, k, 9’)is an intuitionistic ZF model. That (9, 92, I=, 9’)is ordinalized is straightforward. For a <6 9, is the representative of a, and if for some ~ € 9 r’toordinal ~ a, a must be & for some a<& Finally, in the next section we show (9, 9,C, 9’) is cardinalized.

0 2. Countable incompatibilityof 9 Theorem 2.1 (Cohen): 9 is countably incompatible. (and hence (9, 9, t, 9’>is cardinalized). Proofi We give the argument informally, but 9, V and W EV so the

m.1053

CARDINALS AND

w

135

argument can be formalized. We note that for this model to say r,Aeg are compatible is to say T v A E 3. Let &'cS ( H e V ) , and suppose any two elements of &' are incompatible. We show &' is countable. Suppose &' is not countable. For each n > O , let A?,, be {re&' r contains < n statements}. Since &'= UZn, some Snmust be uncountable. Thus let S,,be uncountable. Let k be the largest integer such that for some re&',, I' has k statements and uncountably many are such that rcA. (k must exist since Q E ~ ,and , there are uncountably many A E ~ , such , that ~ E A , has < n statements, so there is a largest k.) and every Pick some particular re%,, such that r has k statements and r is a subset of uncountably many elements of %,,. Let X be [ rc A } . We have the following facts: (1). Any two elements of X are incompatible. (2). X is uncountable. (3). AEXimplies rc A . (4). r has k elements. (5). For any P E Xwith more than k elements, there are only countably many A E X such that Szc A . Now choose some AEX, A #I-. Then A -r= {XI,..., X,). Since A is incompatible with all other elements of X , by (3) there must be uncountably many elements of X containing Xi for some Xi. (Xi is -(ma) if Xiis (nea), and Xi is (nea) if Xiis ~ ( n e a ) . ) Let Sz=ru(Xi}.Then SzGP,, since X i # r . But there are uncountably many A E & ' ~such that Sz E A and Sz has k 1 statements, a contradiction.

I

+

8 3. Cardinals and W

We now have that

(9, W ,k, 9')is a cardinalized model. We introduce the following abbreviations: 1'

I.

x is ut least Ki for cardinal x A ( 3 y ) x h at least K, for cardinal x A ( 3 y )

EX A y is w) EX A y is at least K,)

Recall that in V, 6 was K,. We wish to show (8 is at least K,) is valid in (9, R, k, 9').We showed in ch. 9, that (Q is w)is valid in (9, W,C, Y ) . Let y be the ordinal of V which is K,. Since y is a cardinal, (cardinal f)

136

INDEPENDENCE OF THE CONTINUUM HYPOTHESIS

CH. 10 8 4

is valid, and since OEY, (&?) is valid. Thus (9 is at Zeast K,) is valid in (3,W, C, 9’). Finally 6 is a cardinal of V, so (cardinaZ8) is valid, and YES, so ( 9 ~ 6 is) valid. Thus (6 is at Zeast K,) is valid in (9, 9, C, 9). Now we list a few properties of W. The proofs are straightforward. Lemma 3.1: (a, a,) = (a, a,) is valid in (3,W, I=,9’) (where the first of these expressions is the function in Yo,and the second is the expression of ch. 8 0 3). Theorem 3.2: (function W A 1-1 W A domainW=8)isvalidin(BY9,C , 9 ) . Theorem 3.3: - ( 3 x ) lid in (3,W,C, 9’).

5 4.

[xErange(W)I - ( 3 y ) - ( y ~ x z integery)] isva-

Continuum hypothesis

Let (card8 (0) 2 K,) be an abbreviation for ( 3 x ) { x is at least

K, A

- -

-

(3 W ) [function( W ) A 1-1 (W) A domain( W )= x A ( 3 y ) (yerange( W ) 3 (32) ( z ~ 3 y integer(z)))]}. N

By the results of 0 3 (cardB(w)>K,) is valid in (9, W, ’F, 9’). Hence (continuum hypothesis) is valid in (9, W ,I=, 9’). Now, as we showed in ch. 7 0 1 the continuum hypothesis is classically independent of the axioms of ZF. Of course we would also like that it is independent of ZF together with the axiom of choice. That the axiom of choice is valid in this model will be shown in ch. 13.

-

CHAPTER 11

DEFINABILITY AND CONSTRUCTABILITY

0 1. Definitions We introduce the following formula abbreviations : purtfun(f) for function ( f ) A (3n) [integer (n) A domain (f)E n] , purtrel ( R ) for ( 3 x ) ( 3 y ) [(XI'? A ~ E R3)(partfun( x ) A parvun ( y ) A

-

-

dUmQ&(X) =duS%%&(y)],

- -

n EDomain ( R ) for (3x) [(purtfun(x)A X E R )3 nEdomainfx)], R is atomic(1) over X for (3m)(3n) {integer (m) A integer (n) A /3f) -1jgR Ffi~rf%z//) A ~ o w Y ~ z ~ [= / )(9 $4

-

f (4EX A f ( n k X A f ( m b f (411) R is atomic(2) over X for (3n) (3u) {integer(n) A aEX A ( 3 f ) [ f e R -= (purtfun(f) A domain(f) = (a>A f(n>EXAf(nka)l)$ R is atomic(3) over X for (312)( 3 4 {integer (n) A U E XA (3f) [ f s R 3 (purlfun(f) A domuin(f) = {n)A f(4EXA a E f ( m R is atomic(4) over X for (3U)(3b) { - - U € I A - - b € X A -(3f)- [ f G R r ( p u r v u n ( f ) r r domain (f)= 0 A u ~ b ) ], }

- - - --

7

Y

138

cH.1181

DEPINABKITY A N D CONSTRUCTABILITY

R is atomic over X for ( R is atomic (1) over X ) v ( R is atomic (2) over X ) v ( R is atomic(3) over X) v ( R is atomic(4) over X ) , R is not-S for partrel(S) A (3x) [xEDomain(R)= xEDomain(S)] A -(3 f ) - [ ~ E R F N ~ E S ] , (frDomain(S))ES for (3s) [gES A (3x) [xeDomain(S)I>f ( x )= g (x)]], R is S-and-T for partrel(S) A partrel ( T ) A (3x) [xEDomain(R)= (xEDomain ( S ) v xEDomain ( T ) ]A Of) [f E R = ((f1Domain (S))ESA (f Domain ( T ) ) ET ) ], R is S-or-T for partrel ( S ) A parfrel( T ) A (3x) [xEDomain(R)3 (xEDomain(S)v xEDomain( T))] A -(3 f ) - [ f ~ R ~ ( ( f r D o r n a i n ( S ) )( f~rSDvo m a i n ( T ) ) ~ T ) ] , R is S-implies-T for partrel ( S )A partrel( T ) A (3x) [xeDomain(R)= (xEDomain(S)v x ~ D o m a i n ( T ) )A] (3 f) [f E R = ((f Domain (S))ES3 (f/Domain (T ) ) ET ) ], f = g 1Domain ( R ) for domain ( f )= Domain ( R ) A ( 3 x ) [xEDomain(R)3 f ( x ) = g (x)], R is (3n)S over X for partrel(S) A integer(n) A (3x) [xEDomain(R)3 (xEDomain(S)A x = n)] A (3 f) [fE R = (3g) (g ES A f = g /Domain (R)A g ( n ) c X ) ] , R is a deJinable relation over X for (3F) (3n) (funcfion(F)A integer(n) A domain(F) = n A (3x) [xEn 3 F ( x ) is atomic over X v ( 3 y ) ( Y E X A F(x) is noz-F(y)) v ( 3 y ) (32) EX A Z E X A F ( x ) is F(y)-and-F(z))v ( 3 y ) (32) ( y ~ Ax Z E X A F ( x ) is F(y)-or-F(z)) v ( 3 y ) (32) EX A Z E X A F ( x ) is F(y)-implies-F(z))v ( 3 y ) (3k) ( Y E X A integer(k) A F ( x )is ( 3 k ) F ( y )over X ) ] A (3m) (mEn A F(m) = R ) } , N

N

N

-

-

N

N

r

N

N

N

N

N

N

r

N

N

N

N

N

N

N

-

N

N

CH.

11 $ 2

ADEQUACY OF THE DEPINABILITY FORMULA

139

X is dejnable over Y for (3R)(312)(partrel(R) A integer (n) A R is a definable relation over Y A (3x) [xsDomain ( R ) = x = n] A ( 3 x ) [ x E X = ( x E Y A (3 f ) (f E R A f (n) = x ) ) ] } .

-- --

Remark 1.1: In the above we have used a few additional minor but obvious abbreviations. This approach to first order definability using partial relaitons is due to Smullyan. Intuitively, if we have the formula X ( x , , x,, x 5 ) which is true over the set Y for an instance x2 =a, x, =by x5 = c, we can consider instead of the instance the partial function f with domain {2, 4, 5 ) such that f (2) =a, f (4) =b, f (5) =c. Instead of the formula X itself, we can consider the collection of all partial functions with domain (2, 4, 5) which represent true instances of X as above. This collection is called a partial relation. We leave to the reader the verification of the fact that classically (Xis definabZe over Y) does indeed represent first order dehability. In the next sections we consider to what extent it represents it in our intuitionistic models. We also leave to the reader such elementary facts as

ZF tIR is atomic over Xxpartrel(R) ZF t,partreZ(S)A R is not-SzpurtreZ(R) ZF t, partrel(S) Apartrel(T) A R is S-and-Tzpartrel(R) etc.

5 2.

Adequacy of the definability formula

In this section we state two theorems of considerable use, whose classical analogues are reasonably intuitive. For the intuitionistic case the theorems are less obvious. The proofs are tedious and we relegate them to an appendix.

Theorem 2.1: Let (9, W ,b y 9>be ordinalized and suppose for some re9 and some g, f€9r b f is definable over g . Then there is some r* and some dominant formula X ( x ) with no universal quantifiers such that (1). every quantifier of Xis bound to g, (2). if a is a constant of X other than a quantifier bound, r*k (aeg), (3). r*c ( 3 ~ ) - 1x.f = ( x e g A X(X))].

-

140

DEFINABILITY AND CONSTRUCTABILITY

CH. 11 $

3

Theorem 2.2: Let (Q, W , C, 9’) be ordinalized and f, g E 9’.Suppose X(x) is a formula with no universal quantifiers such that for some r E 5 9 (1). every quantifier of X is bound to g, (2). if a is a constant of X other than a quantifier bound r k (3). r- pX)- [ x E = ~ ( X E g A ~(x))]. Then r (f is defiplable over 9).

--

--

(aEg),

CuruEZury 2.3 (to theorem 2.1): Let {’3, 9, I=,9’)be ordinalized, g E Y U , and f is definable over g. Then for some k E Y , + , - Y , and some

r*

rC r*k ( f = k ) .

Proof: r k f is definable over g, so there is a dominant formula X(x) and a r*as in theorem 2.1 above. Suppose the constants of X(x) other than g are a,, a,, ...,a,. r*k (a, Eg) so there is an h , ~ 9 ’ ,such that r*C (a, =h,). Similarly we find h,, ...,h , ~ 9 for , a,, ..., a,. Let X’ be

B y weak substitutivity of equality

r*k

-

(3~)

[x(x) = x’(x)] .

Let Y ( x ) be X‘(X)AXE~. Then all constants of Y are in 9,. Let kyE YU+, 9,We . claim r*k (ky=f ). We leave the verification of this to the reader, after noting that by a classical-intuitionisticargument we have rI= f cg and g E Y , .

-

8 3.

odominance

This definition of o-dominance is not to be confused with that of ch. 7 0 16 which was used only that section. We consider only ordinalized models. We call a formula X(xl,..., x,) with no constants w-dominant, if for any a E V such that Q E ~ ’ , , and for any constants ci,..., c,E~’,

rk,x(C,,..., c,)

iff

rkx(c,,..., c,).

We wish to show all the formulas of Q 1 are w-dominant.

CH. 118 4

THE

141

Ma SEQUENCE

Lemma 3.1: If (9, 9, !=, 9)is ordinalized, - ( 3 x ) - [ x ~ d ~ i n t e g e r ( x ) ] is valid. Proof: Suppose r != ( a d ) .Then for any r* r*k ( a d ) . But r*1ordinal a so there is some r**and some ordinal a such that r**C (a=&). Then r**k (&~d). Then it must be that CLEW,hence a is some integer n. Thus r**!=(a=A).But I‘**Cinteger(R), so r**k--integer(a). Thus r != integer (a). Conversely, if r != integer (a), for any r* r*k integer (a). Then there is some r**and some integer n such that T**k(a=A). But ~ E Wso r**C (hcd). Thus r**!= (aed), r C (a€&). Since r is arbitrary, the result follows.

--

--

--

--

Now replace in all the formulas of § 1 integer(x) by XEQ. By the above lemma, the resulting formulas are weakly equivalent to the originals (i.e. their negations are equivalent) which is sufficient for our purposes. We call a formula with constants dominant if the corresponding formula with free variables replacing the constants is dominant. We leave it to the reader to show the formulas produced above are dominant. For example, partfun (f)is

function (f) A (3.) (integer (n) A domain (f) E n). This becomes fUnCtiOn(f) A (h)(nEd

A

dOmUh(f) E n),

and the corresponding formula with no constants is function(y)

A

(3n) ( n ~ Ax domain(y) ~ n ) ,

which is dominant. It then follows that the formulas of 0 1 are o-dominant.

6 4. The M , sequence

-- - - - - z4w))llll

Let ( f i x M ( a ) ) be an abbreviation for ordinal(a) A ( 3 F ) {function ( F ) A domain ( F ) = a’ A (3X) [XEa’ 3 [ ( X = 0 A F ( X ) = 8) V ( 3 y ) ( X = y ’ A (32) [ z ~ F ( x=) z is dejinubZe over F(y)]) v (limit ordinaZ(x) A (32) [ z ~ F ( x=) ( 3 ~( W ) EX A

F(a) =f>*

142

CH. 11 $ 4

DEFINABILITY A N D CONSTRUCTABILITY

Remark 4.1 : By a classical-intuitionistic argument we have

-

- -

( [ x is M ( z ) A (3w) ( w ~ =y w is definable over x)]

ZF 1, (3x) ( 3 y ) (3.)

7

3

y is M ( z ’ ) ) .

, Lemma 4.2: Suppose < S , W,k, 9)is ordinalized, 6,8,f E Y ~and (f is M(&))is valid. Then there is some g E 9 ’ p + z - 9 ’ p + l such that /---

( g is M ( a + l ) ) is valid. Pro08 Let X ( x ) be the formula (x is definable over f), and let

/-

We claim ( g x is M ( a + l ) ) is valid. Since ( x is M ( y ) ) is stable, we may show w ( g x is M ( a + 1)) is valid. Using the above remark, it sufficesto show (3w)- [ w E g x = w is definable overf ] is valid. Suppose rk(cEgx). Since gXE9’fl+2-9’,+1, r k ( c = d ) A (dEgx) for some dE9,+l. So r I,+ 2(dwx), r C +1 X ( d ) l” kp + (d is dejnable over f ) . So by w-dominance r k (d is definable over f), r k (c is definable over f).

gxE9’p+z-9’fl+1.

--

,

Y

--

Conversely, if r k (c is definable over f ), by corollary 2.3 for some dE9’,+1-9’pY rk-(c=d). SO

rk and by w-dominance

N

r C, +

-

(d is definable over f),

- --- -

(d is definable over f), Tk,+1X(d), rcp+2 (dw,), r k (dw,),

r+-+&.

Since r is arbitrary, the result follows. Lemma 4.3: Suppose ( 9 ,W ,k, 9)is ordinalized. Let a~ V, and let 6 be the largest non-successor ordinal
+

CH.

11 0 5

143

REPRESENTATIVES OF CONSTRUCTABLE SETS

Pro08 By induction on a. If a =0, the result becomes : there is an YEY,+ such that (fis M (0)) is valid. But by a classical-intuitionisticargument - ( 3 ~ ) - [ : - ( 3 y ) ( y ~ x ) ~ xis M ( x ) ]

--

is valid, and since 6~ Y,, we have (6 is M(6)) is valid, or by stability (0 is ~(6)). Next suppose the result is known for a. The result for a+ 1 follows by lemma 4.2. Finally suppose a is a limit ordinal and the result is known for all ordinals < a (here a=@. We must show for some 9a+w+l fis M(&)is valid. But it follows from the methods of ch. 9 that & ~ 9 ~ + ~ so & ~ 9 Let~X (+ x ) be~the . formula ( 3 y ) ( y € b A ( 3 z ) ( z is M ( y ) A

XEZ))

We claim (fx is M(B)) is valid. and letfxE9’a+,+1 Since ( h i t ordinal (a)) is valid, we must show

- - -

[ x € f X = ( 3 y ) ( Y E & A (32) (z is M ( y ) A ~ E Z ) ) ] is valid. But this is o-dominant, so we must show it is valid in ( 9 ,9,l=a+o+l, Ya+W+i>, but this follows from the validity of (3x)

(3X)

[x(X)

(3y) ( y € &

A (32) (Z

iS

M(y) A

XEZ))]

in ( 9 ,92, ka+,, Ya+J (this is valid trivially because it is an identity). Theorem 4.4: Suppose ( 9 ,W ,k, 9’) is ordinalized and U E V. There is some f~ Y such that (fis M(&))is valid in { g,@, 1, 9).

0 5. Representatives of constructable sets Somewhat as we did with ordinals in ch. 9 0 3 we associate with constructable sets elements of 9 which will represent them. We find it sufficient to work with general representatives, and do not single out canonical ones. We make the following preliminary definitions. We call a formula with no universal quantifiers E-stable if every subformula beginning with a quantifier is of the form (3x) Y ( x )where Y ( x )is stable. Classically any formula is equivalent to many E-stable formulas. For a formula X by Xy we mean the formula X with all quantifiers bound to y. That is, if a subformula of X is of the form (3x) Y(x),the corresponding subformula

144

DEFINAEIILITY AND CONSTRUCTABILITY

CH.

11 8 6

of X y has the form (3x) [ x ~ Ay Y y( x ) ] . Clearly if X is E-stable, X y has strongly bounded quantifiers and so by ch. 7 $ 7 X y is dominant. Now suppose <S,93,I=, 9)is ordinalized. Suppose we have defined representatives in Y for all the elements of Ma. Let CEMa+,-Ma. Then C is a classically definable subset of Ma. Let X ( x ) be any E-stable formula which defines C over Ma. Suppose the constants of X are C, ..., C., These are all in Ma. Let ,..., enbe any representatives in Y of C, ,..., C, respectively, and let 2? be

el

By theorem 4.4 there is an f€9’such that (fis M(B)) is valid in {S,W ,t, Y).Chooseonesuchf.Le Y(x)bethe formula [ x ~ f ~ s ~ ( x ) ] . There are only finitely many constants in Y(x).Let contain them all. Consider g Y ~ . 4 p B +-, Yfl.We call gr a representative of the constructable set C. In this way we may associate representatives in 9’to every element of L, the class of constructable sets in V. Representatives as defined are of course non-unique. They depend on the particular formula X chosen, on which f, on which representatives for the constants of X , and on which b. However, we will show later that iff and g both represent the same constructable set, (f=g) is valid in (9,w,1, y>. We shall use the ambiguous notation that is any one of the representatives of the constructable set C. Since an ordinal 01 is also a constructable set, B is doubly ambiguous, but it will be clear from context whether we mean the ordinal or the constructable set representative. Moreover, as we show later, these two notions are closely connected.

e

0 6. Properties of constructable set representatives Let (x is constructable) be an abbreviation for the formula (32) ( 3 y ) (ordinal(z) A y is M ( z ) A x ~ y ) .

In this section we show:

Theorem 6.1: Let { 9 , 9 ,1, 9’>be ordinalized and suppose for some re9 rk(?ly) ( y is M ( & ) A ~ EThen ~ ) . there is some r*,some CEM,, and some e representing C such that I‘* t= (f=

c).

CH.

11 Q 6

145

PROPERTIES OF CONSTRUCTABLE SET REPRESENTATIVES

Corollary 6.2: If (9, 9, C, 9) is ordinalized and r C ( f is constructable), then for some r*,some constructable set C, and some representative e of c r * b ( f = e ) .

c

-

Theorem 6.3: If (9, 9, C, 9)is ordinalized, CEM,, and is any representative of C, then - ( 3 y ) ( y is M ( & ) Ae ~ y is ) valid in (9,w,b, 9).

- - (e

Corollary 6.4: If (3, W,C, 9)is ordinalized, C is a constructable set, and e is any representative of C, is constructable) is valid in (9, 9, b, 9). Proof of theorem 6.1 : By induction on a. If a=O, since Mo=O, it follows that - ( 3 y ) ( y is M @ ) Af E y ) is valid, so the result is trivial. /\

Suppose the result is known for a and r b ( 3 y ) ( y is M(a+ 1) A f ~ y ) . By a classical-intuitionistic argument

ZF I-,

-

3

-

(3 f ) (3a) ( 3 y ) [(successor ordinal(a) A y is M ( E )A f EY) (32) (38) (ordinal@) A a = 8' A z is M(B) A f is dejinable over z)]. /\

Moreover, (successor ordinal (a+ 1)) is valid, so

rC

--

(32)(38) (ordinal(p) A a + 1 = 8' A z is M(B)A f is definable over z ) .

It then follows that for some g E Y and some r*that r*C g is M ( & )A f is definable over g. But we have shown there is an he 9'such that (h is M ( & ) ) is valid. Thus r*b h is M ( & )and by a classical-intuitionistic argument I'*b (g =h). Thus r*C ( f is definable over h). There is some r**such ( f is dejnable over h). Now by theorem 2.1 there is some that r**I= dominant formula X ( x ) with only existential quantifiers, with all quantifiers bound to h, and some r***such that if a is a constant of X ( x ) other than a quantifier bound, then r*** I=( a d ) and r*** b (3x) [ X € f E ( x € h A X(X))]. There are only a finite number of constants a,, ..., a, in X . Consider a,. r***C (a,~ hA )(h is M( a)). By induction hypothesis there is some r**** and a CEM, such that I'****b (a, = Consider a, similarly, starting with r****, and so on to a,,. Thus we get some T***...*=A and some C,,..., C,EM, such that A != (a, = A A (a,= en).

--

-

N

el). el)

146

DEFINABILITY AND CONSTRUCTABILITY

CH.

11 5 6

Now let X’ be

Then by weak substitutivity of equality A ~ - ( ~ x ) - [ x=E( x~E h ~ \ X ’ ( X ) ) ] . Let Y ( x ) be the formula x ~ A hX‘(x). Let Y pcontain s all the constants of Y ( x ) and f, and consider g y E 9 ’ p s + 1 - 9 ’ p . By definition, for some CEMa+l gy represents C. We claim A k (f=gy). By dominance, we must show A k8+1 (f= g y ) , or equivalently

A kp or

- (3.) - [ x ~f

dkg”(3x)-[x€f

E

Y(x)]

E(XEhAX’(x))].

But this is dominant so we must show Ak-(Ix)-[xEf which we have. If

ct

=(xEh

Ax’(X))]

is a limit ordinal, the result is trivial.

Lemma 6.5 (for theorem 6.3): Suppose (9, 9, k, 9’) is ordinalized. Suppose that for any CEM, and for any representative of C - ( 3 y ) ( y is M ( & ) Ae ~ y is) valid in (99, 9, k, 9). Then for any

e

-

e

-

/---

~ E M , , , and for any representative of C - ( 3 y ) ( y is M ( c t + l ) ~ c ~ yis) valid. Pro08 Let CEM,,,, and let represent C. Since represents C, i s f y E Y y + l-9’?, where Y ( x ) is ( x E ~ A ~ ’ ( x where ) ) , X ( x ) is E-stable, X ( x ) defines Cclassically over Ma,and (h is M(&))is valid in (3, 9, !=, 9’). But (3x)- [ X E ( x ~ Ah8 ” ( x ) ) ] is valid (remember that 8’ ( x ) is dominant, and h ~ 9 , ) Moreover, . suppose a is some constant of rZh(x) other than a quantifier bound. By definition a must represent some element of Ma, so by hypothesis - ( 3 y ) ( y is M ( d ) ~ a ~isyvalid. ) But again (h is M ( & ) ) is valid, so by a classical-intuitionistic argument ( a ~ his) valid. Now by theorem 2.2 is deJinabZe over h) is valid and ct + 1 = ct‘ is valid, so by another classical-intuitionistic argument ( 3 y ) ( y is M ( a + 1) A e ~ yis) valid.

e

e

e

c=

N

-

--

/\

--

-

- -(e

Now theorem 6.3 follows by a straightforward induction on 01.

m.1187

147

THE PRINCIPAL RESULT

0 7. The principal result This section is devoted to showing the following:

Theorem 7.1: Let ( 9 ,9, k, 9’)be ordinalized. Then (1). If C,DEL,and C?, B are representatives of C, D respectively, then C G Diff - ( e ~ bis)valid, and CqD iff - ( e ~ bis)valid. (2). Iffand g both represent the same constructable set, (f=g) is valid. (3). Iffrepresents the ordinal CI in an ordinal sense and g represents tc in a constructable set sense, (f=g) is valid.

-

We first show

Lemma 7.2: Let ( 9 ,W,i=, 9’)be ordinalized. Let X be an E-stable formula with no universal quantifiers, with all quantifiers bound to Ma, and with all constants other than quantifier bound elements of Ma. By X’ we mean (in this lemma) any formula which is like X except for having some representative in place of C, for every non-quantifier-bounding constant of X,and having all its quantifiers bound to h instead of Ma, where ~ E isYsuch that (h is M(&))is valid. Then for the following to hold for all such formulas X,it is sufficient that they hold for atomic X:

e

X is true over Ma + X is false over Ma

-w

X’ is valid in <S,W , i=,9), X’ is valid in ( 9 ,W,k, 9’).

Proofi By induction on the degree of X.Suppose the result is known for all formulas of degree less than that of X.We have five cases: (1)-(4). Since ( Y A zy = Y’ A z’, (Y v = Y‘ v Z ’ , (- Y)’ = Y ’ , (Y3Z)’=Yf3Z’,

zy

-

the four propositional cases follow easily. (5). Suppose X is (3x) (XE MaA Y ( x ) ) (where Y ( x ) is stable) and the result is known for Y. X ’ is (3x) ( x ~ Ah Y’(x)).

X is true over Ma * for some C E Ma Y (C) is true.

- - Y‘(e) -

But then by induction hypothesis sentative.)!C Since CEMa, by theorem 6.3

is valid (for any repre-

N

( 3 y ) ( y is M ( & )A e ~ yis)

148

DEFINABILITY AND CONSTRUCTABILITY

---

valid. It follows that is valid, which implies Conversely

( e ~ his) valid. Thus

CH.

11 8 7

- - - -X’. - - (e) ( e ~ hA )

Y‘

- ( 3 x ) ( x ~ Ah Y ’ ( x ) )is valid, i.e.

X is false over Ma * for every C E Ma Y ( C ) is false over M a .

Suppose for some r

r j!

-

X‘. Then for some r*

r*I.X’

and

r*k(gX)(XEh A Y’(X)).

For some U E Y r*I.( u ~ Ah Y’ (u)). But r*I.h is M(&),so by theorem 6.1 for some CEMa and some r**

r**k (u = C), But by hypothesis

-

T**C-Y’

Y’(C).

(e)is valid. Thus -X’ is valid.

Now we show part (1) of theorem 7.1. The proof is by induction on the order of D ( D is of order a i f D E M , + -Ma). ~ Suppose D is of order a and the result is known for all constructable sets of lower order. D EMa+, -Ma so D is a definable subset of M,. Let B be some corresponding element f r ~ Y f l + l - Y ,where , Y ( x ) is the formula ( x ~ AhZ h(x)), where (h is M(&))is valid and Xdefines D over Ma. CED i f f X ( C ) is true over Ma. By induction hypothesis, the conclusion of the above lemma is known for all atomic formulas over Ma, and hence for all formulas. Thus

-

C E D s X (C) is true over Ma s-

-

w

X’

(e)is valid .

-- -[ci~h~8~(e)] -- ( e ~ f i )

But CEMa and (h is M(&)) is valid so - ( e ~ h ) is valid. Thus - [ e ~ h ~ L ? ~is(valid. e ) ] By dominance is valid in (9, W , k, Y,), that is Y ( e ) . Then is valid in {S,W , 1=,+1, Y,+l) and hence in (9, 9, I., 9). The second half is similar, and the result follows. Next we show part (2). Suppose f and g both represent the same constructable set D E Ma+l - Ma. Suppose r I.( U E f ). Since D EMa+l, by ( 3 y ) ( y is M(a+ 1) ~ f ~ yBy)aclassical-intuitionistic . theorem 6.3 r I. argument r I. ( 3 y ) ( y is M ( & )A m y ) . Then for any r* I‘* I. (3y) ( y is M ( & ) A u E ~Now ) . by theorem 6.1 there is some C E M , and some

-

--

N

A

--

CH. 11 $7

149

THE PRINCIPAL RESULT

r**such that r**k(a=C).

But then r**k--(Cef), so by part (I) of the theorem, CED is true (since f represents 0). But since g also represents D , r**b (CEg). So r**I= (aEg), r k (ueg). Since r is arbitrary and the argument withfand g is symmetric, part (2) holds. Finally, to show part (3) we proceed by induction on the ordinal a. Suppose the result is known for all pea. Let O(a) be some ordinal representative of a, and C ( a ) be some constructable set representative. If TCucO(a), for any r* r*i = u ~ O ( a ) But . r*kordinaZ O(a), so r*k ordinal a. Now by the results of ch. 9, there is an ordinal p and a r** such that T**ku=O(P). Thus r**kO(j?)EO(ct) so it must be the case that pea. But then by part 1 above r** C C ( f l ) ~ C ( a )and , by induction hypothesis r**CO(p)=C(p). Thus r * * k - - ( o ( p ) ~ C ( a ) ) ,T**k(UE C (a)), so r k ( U E C (a)). Since r is arbitrary, 0 (a)c C(a) is valid. The converse inclusion is similar.

--

-

N

-

--

--

CHAPTER 12

INDEPENDENCE OF THE AXIOM OF CONSTRUCTABILITY

5 1. The specific model Once again the model presented is adapted from Cohen [3]. Let e and a be formal symbols. By a forcing condition we mean any finite consistent set of statements of the form (neu) or -(neu) for any integer n. Let 9 be the collection of all forcing conditions, and let W be set inclusion E. Y oconsists of the functions 0, 1,2, ..., and a. The definitions are as follows: For each integer n, A has as domain {&I, ..., n - l}, and if m c n, . . A _

/\

R(r2) = 8. a has as domain

{a, I,2,...}, and U ( A ) = {r I ( n e a ) E r } .

Then ko for atomic formulas is simply rk,(fi~A)if m e n , r t = , ( A ~ a ) if ( n e a ) E r .

We leave to the reader the verification that (9, 9,to,Y o )satisfies the five properties of ch. 7 § 3. Property (4)is shown just as in chs. 8 or 10. Thus (9, 9,k, 9)is an intuitionistic ZF model. We also leave to the reader the straightforward verification that (9, W , k, 9) is ordinalized.

aI.1292

151

AXIOM OF CONSTRUCTABILITY

0 2. Axiom of constructability

-

Theorem 2.1: (3x)- [x is constmcfable] is valid in (9, 9, k, 9>. Proof: We show in particular that (a is constructable) is valid. 9 r C. (a is constructable). By corollary 11.6.2 for Suppose for some some constructable set C EV and some r* r*k (a= We will show this is not possible. Let r*+be (n (nea)Er*}. We have two cases: Case (1): every integer of C is in r*+. Choose some integer n such that (nea) is not in r* (recall that I'* is finite). Let r**be r * u ( ( n e a ) } . Then r**e9and T*WT**. But n$C, so r**C Since (nea)ET**, r**k (fiea),which is not possible. Case (2): some integer of C is not in r*+. Let n be such an integer. Let r**be T * u { - ( n e a ) } . Again r * * E 9 and T*%'T**. But nEC, so I'**k- ~ ( f i ~Since c ) .-(nea)ET**,itfollowseasily thatr**C.-(fiEa), which is again impossible. Hence r j! (a is constructable), and since r is arbitrary, the theorem follows.

e).

I

- (nee).

Now we have classical independence by the results of ch. 7 Q 1. In ch. 13 we will show that the axiom of choice and the generalized continuum hypothesis are both valid in this model, so the full independence is established. Remark 2.2: This proof actually shows the stronger fact that every set of integers is constructable is independent, since a s w is valid in the above model.

CHAPTER 13

ADDITIONAL RESULTS

9 1. 9, representatives

-

Definition 1.1 : We say SEYrepresents 9, if (1). g E 9 , implies -(gEs) is valid in (9, 9, k, 9), (2). if Tt; (ges), then for some r* and some h ~ 9 r* , k (g =h).

Lemma 1.2: Suppose X ( x , , ...)x,) is a formula with no universal quantifiers, and with all constants from 9,Then . for any cl,. .., C,E 9, and any r E 9 r k a - X ( c l ,..., c,) iff r C - X s ( c , , ..., c,)

(Xsis X relativized to s). Proof: A straightforward induction on the degree of X.

Lemma 1.3: Suppose s represents 9,Then . for any f €9: (1). If f E 9 , + , , - ( f i s definable over s) is valid. (2). If r k (f is definable over s) then for some r* and some h E 9 , + , r*c (f=h). Proof: Supposef ~ 9 ~Iff+EY,, , . the result is simple. Iff ~ 9 ,-+ 9,~ , then f is fx for some formula X over 9,. We claim -(3x)- [ x e fx= ( x e s h X S ( x ) ) ]is valid in (9, 9, !=, 9). We leave this to the reader, using the above lemma. It then follows by theorem 11.2.2 that - ( f i s definable over s) is valid. Suppose conversely that r k (fis definable over s). By theorem 11.2.1

-

-

CH. 13 8 2

153

DEFINITION FUNCTIONS

there is some I‘* and a dominant formula X ( x ) with no universal quantifiers, bound to s, with every non-quantifier-bounding constant a such that r*k ( a ~ s )such , that

r*k

- (3x1

=

[ X E ~ (XES A x ( X ) ) ] .

Now for any a of X ( x ) r*k (ass), so for some u ’ E ~ ’ , and some r** r**k (a=ar). Similarly with all constants of X ( x ) (other than s). Thus we have A=T**”’* such that if b is any constant of X ( x ) other than s, there is some b ‘ E Y , such that A k (b=b’). Now let X’ be like X except for containing u’EY, for each a of X . Then it follows that k

- (3X)

[XEf

(XES A x’(X))].

Let X ” be like X ’ except for having unbounded quantifiers. Then X ” is a formula over 9,Let . IZX,r~9a+1 - 9,. We claim A C (f=h,..). This follows immediately by lemma 1.2.

Lemma 1.4: If s represents 9, and t represents 9’a+1, then N

(3x)

-

[x

Et

= x is definable over s]

is valid in (3,W,k, 9’). Proof: By lemma 1.3 and definition 1.1.

-

Lemma 1.5: If s represents 9, and (3x) [xer = x is definable over S] is valid in (8, W , k, Y ) ,then r represents 9’a+1. Proof: Again straightforward. N

Remark 1.6: Every 9,is, of course, representable. Let X ( x ) be the formula x =x , and let f x eSpa+ - 9,Then . fx represents 9,.

5 2.

Definition functions

Let (F is a p length s function) be an abbreviation for domain ( F ) = p A (37) {Y E B = C(Y = 0 A F(7) = 4 (36) [6 E y A y = 6’ A (3X) ( X E F(7) F x is definable over F(6))] v [limit ordinal (7) A (3x) ( x e F(y) = (36) (6 E y A x E F(S)))]]).

function ( F )

ordinal (8)

- A

A

”

N

N

N

N

154

CH. 13 5 3

ADDITIONAL RESULTS

The following is left to the reader. Lemma 2.1: If

r I=[(a E y ) A F is a B length s function A G is a y length s function] then r t= ( F c G). For the rest of this section we assume our models are ordinalized. Lemma 2.2: Let

- 9,represent 9,. Then for any p > O

S E ~ ,

,

there is

/-

+ - 9, + such that [ F is a p + 1 length s function] is valid in an FE9, (9, 9, C, 9), and for any y < 8, if r C (h =F(?)), then h represents 9,. Proofi By induction on p. If B=O, let X ( x ) be the formula x = (0, s) and consider F,E 9, - 9,. Suppose the result is known for B. Then there is an FE 9,+ - .Spa+ satisfying the lemma. Let f ~ Y ~ + ~ -represent 9 , + 9p+l. ~ Let X ( x )

,

/---

be the formula x e F v x = ( P + l , f ) and let G x ~ 9 , + 4 - Y p + 3 If .8 is a limit ordinal and the result is known for all lesser ordinals, let X ( x ) be the formula (3y)(3F)(y E fl A F is a y length sfunction

A

x E F)

and let G , E ~ , + ~9fi+2. We leave verifications to the reader. Theorem 2.3: Let S N

- Y orepresent Yo.Then

E ~ ,

( 3 x ) ( 3 8 ) ( 3 F ) [ Fis a p’ length sfunction N

A XE

F(p)]

is valid in (9,9, t , 9).

5 3.

Restriction on ordinals representable

We devote this section to a brief sketch of the proof of Theorem 3.1: Suppose (9, 9,C,, Y o ) is itself an ordinalized intuitionistic ZF model, where Q>O. Then exactly the ordinals < B are representable in 9,. Proof: Trivially Q must be a limit ordinal, so by the work of ch. 9 at least the ordinals t i 2 are representable in 9,. We show now that

fit+,%.

c~.13$4

155

A CLASSICAL CONNECTION

Since f2>0 there is an SEY,-Y,(and hence SEY,) such that s represents Y o (see Q 1). By the work in Q 2 the following is valid in (9, W ,,,c 9,): (3x) (3p) ( I F ) [ F is a p’ length s function A x E F ( P ) ] .

- -

Suppose 0~9’~. It then follows that

]

~(3~)-(3p~Q)(3P)[Fisa/3‘lengthsfunctionA X E F ( / ? ) ] (1) is valid in (9, 9, ,k, 9,). Moreover p length s functions form a chain, that is the following is valid in (9, W , ,k, 9,): (3a E 0)(3p E a)( I F ) (3G) [ ( a EP A F is an a length s function A G is a fi length s function)I F G G] (see Q 2). It then follows that the following is valid in (9, 9,,k, 9,)(using obvious abbreviations)

-

N

N

N

I

(3y) ( y = U { F F is a

p’ length s function, for p E Q}).

From (1) and (2) the validity of which is not possible.

5 4.

-

(2)

- ( ~ z ) - ( ~ x ) - ( x E z )follows,

A classical connection

The result of ch. 11 Q 7 may be extended to Theorem 4.1: Suppose (9, W , k, 9)is ordinalized. Let X be any formula with no universal quantifiers, no free variables, and all constants from L. Let X’be like X except for having constants where X has C, and having all its quantifiers bound to the formula (x is constructable). Then X is true over L iff X’is valid in (9,92, k, 9). X’ is valid in (9, 9, C, 9’). X is false over L iff

e

N

--

Proofi By induction on the degree of X . If X is atomic, the result is theorem 11.7.1. Suppose the result is known for all formulas of degree less than that of Y, Y v Z or Y A Z are simple. X. The four cases X is Y x Z ,

-

156

ADDITIONAL RESULTS

w.1315

Suppose X is (3x) Y(x). Then X’ is ( 3 x ) (x is constructable A Y’(x)). If X is true over L, for some C E L Y ( C ) is true over L. By induction Y’ is valid. But by corollary 11.6.4 is conhypothesis y’(~)) structable) is also valid. Hence @)( - X is constructable A is valid. But this implies (3x) ( x is constructable A Y’ (x)) is valid, i.e. -X’. Conversely suppose X is false over L. Then Y ( C ) is false over L for every C E L . By induction hypothesis Y ‘ ( e ) is valid for every C E L . Now suppose for some TeG I ’ y -X’. Then for some r* f * C X ’ or r*k (3x)(x is constructable A Y’(x)). For some U E Yr*C (a is con) .corollary 11.6.2 for some r**and some C E L structuble A y ( ~ )By r**C (a= so r**I= Y’ a contradiction.

--

-

(c)

- --(e-

-

--

N

e),

--

(e),

Remark 4.2 : Suppose (’3, W,, C, 9,)were itself an ordinalized intuitionistic ZF model. We showed in § 3 that exactly the ordinals <sZ are representable in 9,. It then follows that for any CEM, &9,, and conversely. This may be shown by adapting the methods of ch. 11. Now the above theorem may be restricted to Theorem 4.3: Suppose (’3, W,k,, 9,)is an ordinalized intuitionistic ZF model. Let X and X’ be as above, save that X has constants only from M,. Then X is true over M, iff X is false over Mn iff

- -- X‘

X ’ is valid in (9, W,k,, 9,) , is valid in (9, W,C,, 9,).

Pro08 This may be shown exactly as theorem 4.1 was shown. It is simple to establish that the theorem 7.1 relativizes to (G, W,k,, 9,) in the obvious manner.

0 5.

Sets which are models

Classically certain of the Ma themselves may be ZF models. For example M,, where 52 is the first inaccessible cardinal, is such a model. We now examine the intuitionistic counterpart. Theorem 5.1 : Suppose Ma is a classical ZF model, and (’3, W ,to, Y o ) EM,.Then (9,9, ka, Y a )is an intuitionistic ZF model. Proof: In the proofs of ch. 7 V was any arbitrary classical ZF model.

CH. 13 0 6

157

RESTRICTION ON CARDINALS REPRJSENTABLE

If we take V to be Ma, all the results still hold. But now the class model
-

5 6.

Restriction on cardinals representable

In ch. 9 5 8 we called (9, 92, k, 9) cardinalized if all the cardinals of V were cardinals of 9.We now want to verify the remark made there that the cardinals of Y were the same as the cardinals of L. More precisely: Theorem 6.1: Suppose (9, W , k, 9’) is ordinalized, and for some E E V and some r e 9 I‘l.(cardinal (a)). Then a is a cardinal of L, the class of constructable sets of V. Pro08 Suppose a is not a cardinal of L. Then for some BEE and some F E L the following formula is true over L:

[function ( F ) A 1- 1 ( F ) But BEN,so

--

- -(BE&)

A

domain(F) = fl A range(F) = a].

is valid in <S,9, k, 9). By theorem 4.1

[function ( F ) A 1- 1(F) A domain ( F ) = /3

A

range ( F ) = a]’

is valid in ( 9 , W,k, 9’)But . this is

--

[functionL(E) A 1- 1

(f)A

domainL(f)= fi A rungeL(f)= a]

where the superscript L means the formula has been relativized to ( x is constructable). But classically

ZF C,

- (3x)

[ ( x is constructable

A

functionL(x)) 3 function(x)]

and similarly for 1-1, domain and range. By corollary 11.6.4

- - (8

- - (a

is constructable) A

is constructable) A

N

- (B

is constructable)

158

CH. 13 8 7

ADDITIONAL RESULTS

is valid. Hence N

N

[function (f)A 1-1 (l?) A domain (l?) = fi

A

range (l?) = 6 11

is valid. This contradicts r k (curdinal(61)). Remark 6.2: In the above it does not matter whether d and fi are ordinal or constructable set representatives. See theorem 11.7.1.

5 7.

Axiom of choice

By F ( X ) we mean the collection of all classically definable subsets of the set X . Suppose we can define classically a sequence of sets as follows: Yo

=x,

ya+1 = 9(ya) 9, = U 9,(for limit ordinals A), 3

a<,

and let the class Y =Uga.If X can be well ordered by some relation R , then it is easy to show there is a class which well orders S, or, any set in S can be well ordered. Formally we have ZF t,

--

( 3 X ) N (3x)

-

( 3 8 ) ( 3 F )[ ( F is a 8’ length X function A x E F(8)) A (3R)( R well orders X ) ] 3 (3y) ( 3 t ) ( t well orders y).

-

N

Now by a classical-intuitionisticargument we have Theorem 7.1: Let <3,9, k, 9’)be ordinalized. Suppose ~ € 9Y, o represents 9,. The if r k (3R)( R well orders s) then r k axiom of choice.

Now we consider the specific models constructed earlier. In the model of ch. 12, if X ( x ) is the formula x =x and sx E 9, - yo,sx represents Yo.We wish to show ( 3 R ) ( R wellorders sx) is valid in ( 3 9 9 , t, 9). Let Y ( x ) be the formula (3y)(32) {[integer ( y ) A integer (z) A y E z A x = ( y , z>] v [integer ( y ) A z = a A x = ( y , z ) ] } , and let R , E Y ~ + ~ - Y Then ~ + ~( R. , well orders sx) is valid. Thus the axiom of choice is valid in the model of ch. 12.

CH. 13 4 8

CO"uuM

HWOTHESIS

159

In the model of ch. 10, as above ,s represents 9,. A reasonable wellordering of 9,would be (schematically) 0, 1,2,..., a,, a,, a2,..., {Q},{I},{2>,..., (0, a,}, {I,Ul}, a z } , . . . , (0, a,), (1, a,>, (2, a,>,

...,

{Z

w.

We leave it to the reader to show that this well-ordering can be expressed in the model. The only nontrivial part of the well-ordering is ao, a,, a,, ...) since the subscripts are not part ofthemodel. But Wi&tei?i provides this ordering. Thus the axiom of choice is valid in the model of ch. 10.

0 8.

Continuum hypothesis

In this section we show that the generalized continuum hypothesis is valid in the model of ch. 12. More generally we show the following: Theorem 8.1: Suppose ('3, 9?,C, 9) is ordinalized, (3,9?,I=, EL, and 9 and 9,are countable in L. Then the generalized continuum hypothesis is valid in (3,9, !=, 9').

We devote the rest of this section to the proof. We remarked in ch. 7 9 14 that the definition of the sequence of intuitionistic models is absolute. If L is the class of constructable sets of V, since ('3, 9, I,, EL, the construction of the sequence is the same over V or over L. Thus in this case we may assume in all the preceding work V was L. (We use the continuum hypothesis in L.) Trivially card(Y,+,)= EE0.card(9'J in L. Since ('3, 9, k, 9)is ordinalized and 9,is countable in L, it follows by the work of ch. 9 that for any ordinal a of L, if a d w and if B is the least ordinal such that & ~ 9then ' ~curd , (u)=card(Yg)in L. We use P ( x ) to denote the power set operation both in L and in <'3,9, k, 9) in an obvious way. Lemma8.2: Under the conditions of the theorem, if a,j?EL and

curd(u)> tc, in L, and if for some r&

( P = card(&), r k ( c u ~ ~(a)) then card(P (a))> card( 9 ) in L. Proofi As we showed in ch. 7 $15, for k e d a there is some y E L such

160

ADDITIONAL RESULTS

CH. 13 8 8

that if r k - ( f E & ) ,there is some g E Y , such that r k (f=g). Assume r is fixed. Y , E L . We have the axiom of choice in L so we can define a set P E L such that P s Y , and if rk-(fC&),there is some gEP such that r k ( f = g ) , and iff,gEP and f# g , ry (f=g). Now as in ch. 7 $15 the following is definable (as a class) over L: the function U such that for UEP V ( U )= {(r*, t)

1 ~ E Y ~ A, , r*k(tEu)},

where CI,, is the least ordinal such that & E L Y ~ ~In. this case since P E L , U is a set in L, i.e. UEL. As we showed in ch. 7 , for U,VEP,if U(u)= U(u),then T t (u=u)and hence u=u here. Thus u=u if and only if U(u)= U(u) for U,UEP.Thus if R is the range of U on P, since U is 1-1, curd(P)=curd(R) in L. But R E P('3 x LY",,) so curd ( R ) < c u r d ( P ( B x YOLO)). Since ~ ~ r d (x' 3YOLO) = card(9) * c~rd(Y,,) = KO * curd(a) =curd(a), then curd ( R ) < curd (P (a)), curd(P) < curd(P(or)).

r k (curd(P(&))= curd(&), so for some FE9, r k [function( F ) A 1-1 ( F ) A domain ( F ) = fi A range ( F ) = P (a)],

We have

We can thus define a function GEL to satisfy domain (G)=P and for G(6) is that element e of P such that r k (F($)=e) (there is only one such element e for each 6). G is a function in L, rangeGsP, and it is easy t o see G is 1-1. Thus curd(P)<curd(P) in L. So curd(/3)< curd(P(a)) in L. Now we show the theorem itself. Suppose for some r E 9,r pC generalized continuum hypothesis. Then for some CI, By y E L and some r*

F* k cardinal(&)A curdinul(b) A curdinul(?)r\ &€/3 A / s € f A ( & € & v A = & ) Acurd(P(&))= curd(?).

m.1309

CLASSICAL COUNTER MODELS

Then by 9 3 a, p and y are cardinals of L. Moreover ~ E B ,BEY, or o = a, so card(a)2 KOin L. By the above lemma

161 o E a

card(P(cr)) card(y) in L . Thus B is a cardinal in L between a and P ( a ) contradicting the continuum hypothesis in L.

0 9. Classical counter models In the foregoing we have obtained independence result in set theory without constructing any classical models. In more traditional treatments of forcing, classical models are constructed by a method due to Cohen; for example see [3], but countable classical ZF models are used. Essentially this method was used in ch. 4 5 7 to prove the theorem there. It is possible, using an ultralimit construction, to construct suitable nonstandard classical models without countability requirements. The following method is from Vopgnka [22] and is simply translated from the topological intuitionistic models used there to the Kripke semantic models we use. It can be applied in more general settings but we only give it in a form which applies directly to intuitionistic ZF models. Let (9, 92, I.,9)be a class model over the classical model V and suppose the axiom of choice is true over V. As we showed in ch. 1 0 6, if 8 is the collection 92-closed subsets of 9, (8,E ) is a pseudo-boolean algebra. Let F be any maximal filter in 8.See [16] pp. 44, 66. Define the class S to be the collection of all functions f such that domain (f)E F, range (f ) E 9. Define E E S x S by: f Eg is true if and only if

{re9 1 r~ d o m ( f ) ,

r e dom(g),

r b ( f ( r )g(r))} ~ EP.

We claim that for any formula X ( x , , ..., xn) with no universal quantifiers X(f,,...,L) is true over S if and only if

{ ~ ~ ~ ~ ~ ~ ~ o m ( f , ) n . . . nrdc o~m( (hf (~, .r). )., , L ( ~ ) ) ) E F . The proof is by induction on the degree of X . We have the result for atomic formulas by definition. The propositional cases are straightforward, using the various properties of maximal filters. We show the

162

m.1369

ADDlTfONAL RESULTS

existential quantifier case. Suppose X is (3.) result is known for formulas of lesser degree.

Y(xyfl,...,h) and the

Suppose ( 3 x ) Y ( x y f i...,A) , is true over S. Then for some g e S Y ( g y f i ...,fn) , is true over S. By inductive hypothesis

{I' I r E d o m ( g ) n d o m ( f l ) n-n dom(f,), I' c Y(g

f (I'),.. f"(I'>)lE F .Y

But this set is contained in

{I'I r ~ d o m ( f ,n...n ) dom(L),

b ( 3 x ) Y(xyfl(~)y...yL(~))l

so this is an element of F. Conversely suppose

{I'

Ir

E

dom (fl)n

n dom (f,)

r k ( 3 4 y ( x yfl(0,...,h (0)) E I;.

Let this set be A . We define a function g on A EF as follows. Suppose r e A , then I ' t = ( 3 ~Y(x, ) fl(I'),***,fn(p))So for some a E Y I= Y (a, fl(I'),* * * 9 f n (I'll

-

choose one such a, and let g (I')=a. Thus, by definition, for T E A

iff l-b y(g(~)Yfl(I'),...Yf"(I')).

I ' b ( 3 X ) Y(%fl(I'),...,f"(I'))

Thus A=

{r1 I ' ~ d o m ( f , ) n . . . ndom(f,)n dorn(g),

I' k Y(g (I'),fi (0, .. f"(I'NE F. .Y

So by hypothesis Y ( g , f i ,...,f,)is true over S, so (3x) Y ( x , f , , . . . , f , ) is true over S. As a special case we have: If X has no universal quantifiers and no constants, X is true over S iff (I' r t= X } E F. Since the unit element of <9,G) is g,we have ~ E FThus . if X has no universal quantifiers and no constants, and Xis valid in (gyW,by 9 ) , X is true over S.

I

C H A P T E R 14

ADDITIONAL CLASSICAL MODEL GENERA LIZ AT I 0 NS

0 1. Introduction All of the preceding work in part I1 has been with intuitionistic Ma generalizations, but other kinds of generalizations are possible. In this chapter we briefly examine some of them. Classically two particular models have proved of great use: the model of constructable sets, and the model of sets with rank. We have discussed an intuitionistic generalization of the first. In a similar fashion an intuitionistic generalization of the R, sequence is possible. Scott and Solovay have developed what they call boolean valued models for set theory [19]. These are really boolean valued generalizations of the classical R, sequence, in a sense to be given later. A similar boolean valued generalization of the Ma sequence is possible.

0 2. Boolean valued logics This section is intended as a preliminary to boolean valued models for set theory. The subject is treated completely in [16]. Also see ch. 1 !j 5. In a pseudo boolean algebra, if -a, the pseudo-compliment of a, has the property a v -a= v , then -a is called the compliment of a. A pseudo boolean algebra in which every element has a complement is called a boolean algebra. Let a be a boolean algebra and let u be a map from W, the set of

164

ADDITIONAL. CLASSICAL MODEL GENERALIZATIONS

~~1.1453

formulas, to g.u is called a (propositional) homomorphism if

v(X A Y ) u ( X v Y) v(-X) v ( X 3 Y)

= = = = =

u(X) n u(Y), u(X)uv(Y), -v(X), U(X)* v ( Y ) = -u(X) u v(Y).

In addition v is called a (Q)-homomorphism if

U((W

-w))=

fl

aET

V(X(4)Y

where T is the collection of all parameters. The inhite sups and infs corresponding to quantifiers are assumed to exist. It can be shown that for X a formula with no parameters, X is a theorem of classical logic if and only if u ( X ) = v for any Q-homomorphism into any boolean algebra. One way of generating a theory (a collection of formulas called true, closed under modus ponens, and containing all valid formulas) is to give a boolean algebra 93 and a Q-homomorphism u, and to call a formula X true in the theory being described if v ( X )= v .

0 3.

Boolean valued R, generalizations

This generalization is from [19], though the particular formulation of it is different. As usual V is a classical ZF model. Let g be a complete boolean algebra such that &“EV. (B is complete if all sups and infs exist. Any boolean algebra can be imbedded in a complete one. See [16].) We define a transfinite sequence R:, and simultaneously a sequence of homomorphisms v, from W : to 9 where W: is the collection of all formulas with constants from R:. (Note that to define a homomorphism it is sufficient to define it for atomic formulas.) Let R;=O; u0 is trivially defined. Having defined R:, iff is a function from to 99,call f extensional if for each g, hE R,”

f(dn % ( ( W ( X ~ S = x + ) s f h ) ) .

CH. 14 8 3

1N'IWITIO"IC

R a GENERALIZATIONS

165

Let R,"+l be the elements of R," together with all extensional functions from R: to 8.Supposef,g E R,"+ : (1). iff,g E R let ~ va+l V

Egl=

Egl

va(f

(2). if f e Rz and g E Rz+ ua+1

- R:

let

(feS>=Scf)

- R," let ua+,(fEg)= U { g ( h ) n x f~ (f(x>*ua(XEh)))* R," h dom (g)

(3). iff E Rf+

E

E

Remark 3.1 : If an equality symbol is defined in the usual way, condition (3) is the same as ua + 1 tf E g ) =

U

h E dom (g)

(9 (h) n

va

+ 1 (f = g>> *

IfAisalimitordinal, let R!= Ua
u ( f 4 = o.(feg). Thus we have a class R" and a Q-homomorphism u from W" to a.As we remarked in the last section, all the classically valid formulas map to v. In 1191 moreover, it is shown that all the axioms of ZF (as well as the axiom of choice, if true in V ) map to v . Thus R" is called a boolean valued model for ZF. Finally in [19] a specific model of this kind is produced in which the continuum hypothesis does not map to v ,which establishesindependence. Similarly for the axiom of constructability.

0 4.

Intuitionistic R, generalizations

Let V be a classical ZF model. We d e h e a (class of) transfmite sequence of intuitionistic models (9, 92, ka, RZ> and a class model ( 9 , W , k, 92') as follows: Let 9 be some non-empty element of V, and let W be some arbitrary

166

ADDITIONAL CLASSICAL MODEL QENERAUZATIONS

CH. 14 8 4

reflexive, transitive relation on 9,also a member of V. Let 8 be the collection of all 9-closed subsets of 9.As we showed in ch. 14 6 8 under the ordering E is a pseudo-boolean algebra. An element a& is called regular if - -a=a. We call a function with range 9 'regular if every member of the range is regular. We define a sequence of intuitionistic models (9, 9,C,, R:) as follows. Let R: = 8, so (9, W , C0, R:) is trivial. Suppose ( 9 , W , C,, RZ) has been defined. If f is a regular function from R," to 8,call f extensional if, for each g, hE R," f(g>

{rI

Ca

(9 = h>>E f (h) *

Let R:+i be the elements of R: together with all extensional functions from R," to 8.If I' 9E andf,g ER:+ 1, let TI=,+ (f E g) if (1). f,gER: and rka(fEg), (2). feR:, gERZ+,,-~:andT€g(f),

(3). f ER:+

- R," and for some hedomain (9)

TEg(h) and r ~ ( f ( x ) . = > {l dd C , - - ( x ~ h ) ) ) for every XE R: Remark4.2: The expression in part (3) is an element of the pseudoboolean algebra 8, .=> is the operation of 9'.The definition could have been stated without such a use of 9, but less concisely. Thus we have (9, W , C,+ I, R,"+.)l If I is a limit ordinal let R:=

u R:. a
For f,gER: let TC,(f Eg) if for some aer2 (9, 9,CL, R;). Finally let R"= R:

rka(f Eg). Thus we have

u

aoV

and forf, gER' let rC(fEg) if for some U E VrC,( f Eg). Thus we have a sequence of models
w,k, R”> IS AN INTUITIONISTIC ZF MODEL

~~1.1405


0 5.

R“) is an intuitionistic ZF model

<9,W,k,

167

As we remarked in the last section, 9, the collection of all %closed subsets of 97, is a pseudo boolean algebra. Moreover it is complete, i.e. all sups and infs exist. This follows since in this case a sup is an infinite union, and the union of W-closed subsets is an 9’-closed subset, and similarly for infs. The results of ch. 1 9 6 concerning the relationship of 9’ and (97, 9,k,, RZ) may be stated as : for any formulas X and Y {r r k,X} €9 and {r rk,x} u {r n a y }= {r rc,x v Y } ,

I

I I I {rI rk,x} n {rI = {r I rt,x A Y } , {r I r k,x} =, {rI r t, Y} = {rI r t a x Y } , - {rI rk,x] = {rI rc, -x}. 3

In this case the relationship extends to

Similar results hold between the class models. Now we construct a boolean valued R, sequence as in 0 2. An element a E 9is called dense if - a = A or equivalently,if a= v . Let F be the collection of all dense elements of 9. F is a a t e r and (see [16] p. 132-5.8) 9 ’ / F = 9 is a boolean algebra. Moreover ~ E V(B/F . is the collection of all equivalence classes of 9’ where a and b are equivalent if ( a * b ) ~ F and ( b * a ) ~ F . ) In fact, denoting the equivalence class of a s 9 by l a l ~ gwe , have I 4 u I4 = la u bl,

--

I4 n lbl = la n bl, la1 * lbl = la =- bl - la1 = I- 4 , Y

and the unit of 9 is I v [ = 191. Furthermore 39 is complete and for any index set T

168

CH. 14 8 5

ADDITIONAL. CLASSICAL MODEL GENERALIZATIONS

Remark 5.1 : This relation does not extend generally to 0, but since in a boolean algebra is equivalent to - U -, the above is sufficient for completeness.

n

We include the proof of this last statement as it is so useful.

Lemma 5.2: For u,bELP

- - (U

=>

b) = (U

=>

I

Proof: By [16] p. 62, -371

- - (U

Conversely

- - b).

j.

b) < ( U

=>

-- b). v

--(--c=.c)=

[16] p. 132, -5.7, and an--b<--b.

so

- - [(u ([16] p. 60-14) ([16] p. 60-18)

n - - b) * b] = v

,

- - [(u n (u => - - b)) =. b] = v , - - [(u * - - b ) => * b)] = v , (U

([16] p. 60-37)

b)*-- ( ~ * b ) = V , (u*--b)< --(a*b). (U=.--

Lemma 5.3: In B for any index set T

n --(uX3b)=--

xeT

n (a,+b).

XET

Proof:

- - 0 (uX*b)=

([16] p. 136, -7)

XET

(lemma 5.2) ([16] p. 136, -7) (lemma 5.2)

(s,w,b, R ” ) IS AN INTUITIONlSTIC ZF MODEL

CH. 14 9 5

169

Theorem 5.4: U X E T l ~ x l = I U , E T ~ x l . Pro08 In B for any x E T

so \

u

--(a,*

a,)=

v

XGT

,

u a&F.

(a,=>

xeT

So for all X E T

Conversely suppose for some b E B , for all X E T

1 4 G lbl . Then for all X E T

--(~,*b)=

V .

and since B is complete,

n --(.,=>b)= v , - - n (a,=>b)= v , XE

T

xsT

([I61 p. 136-7)

--(U

a,-b)=v,

XET

so

I

u

XE

T

ax1

G Ibl-

Thus a=BIF is a complete boolean algebra. As shown in 0 2, this determines the sequence R:, the homomorphisms v,, and the class model R” and v. We now wish to investigate the relationship between this and the intuitionistic model from which it arose. First we claim there is an isomorphism between RZ and R: (and between R’ and R”) of a rather substantial kind. We show this by induction on a. RZ and Rf are identical. Suppose we have a mapping between RZ and R,“(pairing f ER: with f ‘ER:). If g&‘R=s, let g’&YR=abethe function whose value at f ’ER; is 9’ (f’)= 19 (f)l*

It follows from the proof of theorem 5.5 below that 0 is extensional if and only if g r is extensional. We will assume this now.

170

ADDITIONAL CLASSICAL MODEL GENERALIZATIONS

1x1455

This map from RI,. to R,“+ is one to one. For suppose g,hE Rz+ - RI are distinct functions. If g and h are different, there must be some f ER: such that g ( f ) # h ( f ) .If I g ( f ) k l h ( f ) lthen by definition

s ( f )=+

or or by lemma 5.2

-- ( d f )

W E F ,

W)) =v

9

(df* ) - - h ( f ) )= “

*

But h is a regular function, so

(df) * W)) =v s ( f )G

Similarly

w.

7

h (f)G 9 (f)

9

so

s ( f >= h ( f b Secondly, this map from R:+, to R:+l is onto. For let heR?+, -R?. Let s be any function from Rf to B defined by: for f E R I , s(f) is some particular element of h (f’). Let g be the function defined by g ( x ) = - - s ( x ) . Then g is regular, with domain RZ, so g ER,”+ - RZ. Moreover, for f E Rz

s’(f’)= Is(f)l = I-

- 4f)l = - - Is(f)l = IWl = h(f’),

and so h i s g f for gERZ++-RZ. Next we establish the essential identity of the two models. Theorem 5.5: Let X be a formula over RZ with no universal quantifiers. ThenX=X(f, ,...,f,)forfl, ...,fn€R:. LetX’=X(f; ,...,fi)wheref[~Rt is the image offi as above. Then

I rc,x>l*

U,(X’> = I{r

(Similarly for the class models)

corollary 5.6. If X is any formula with no universal quantifiers and no constants, X is valid in the boolean model R: (that is u,(X)= v) if and

CH. 14 0 5

(9,2, k, Rg) IS A N

-

INTUITIONISTIC ZF MODEL

171

only if - X is valid in (9, W , C,, R:). (And similarly for the class models.) Pro08 The unit element of 93 is IS1 so

Corollary5.7: (8, 9,k, Rg> is an intuitionistic ZF model (and the axiom of choice is valid if it is true over V). Pro08 By corollary 5.6 and the results reported in 0 2. We now turn to the proof of theorem 5.5. Suppose the result is known for atomic formulas over It:. It then follows for all formulas over R: by induction on the degree. For example suppose X is Y and the result is known for Y. Then

-

172

ADDITIONAL CLASSICAL MODEL GENERALIZATIONS

~~1.1485

The other cases are similar. Thus we must show the result holds for atomic formulas. Suppose the result holds for all formulas over R:. Let S,g E R:+ We have three cases : Case (1) : Ag E R: The result is then trivial. Case(2): fER:, gER:+:-R: Then va+ 1

(f’ E g ’ ) = g’ (f’) = Is ( f >I = IV I n z + l f E g ) l .

Case (3) : fE Rz+ - R: We first note that the following holds in any complete pseudo boolean algebra:

n

U -(aX-bX).

( - U ~ - - Q = -

xeT

XET

Now for any hEdornain(g) let Bh

and

=

{rI

(h))

c~.14§6

EQUIVALENCE OF THE

And so Va+l

(f'w? = =I

u u

& GENERALIZATIONS

173

h , E d o m ( 8 , ) 19hl

g h ~ = ~ ( r ~ r k a + l f E g } l a

h E dom ( 6 )

The case of limit ordinals, and of the class models, is straightforward.

5 6.

Equivalence of the R, generalizations

In the last section we showed that for any intuitionistic R, generalization there is a corresponding equivalent boolean valued R, generalization. In this section we show, under restricted conditions, a converse. Let 33 be a complete boolean algebra. A maximal (=prime) a t e r F is called a Q-filter if, whenever UxaTaxeF,a,EF for some ~ E Tfor , any index set T. We say 33 has property (1) if every non-zero element of L@ belongs to some Q-filter ([16] pp. 86-88). Suppose we have a boolean valued R, sequence as in 0 3, and suppose the algebra L@ has property (1). Let 93 be the collection of all Q-filters of 33, and let W be c (which is actually equality, since all Q-fiIters are maximal). As we showed in 9 3, this determines an intuitionistic R, sequence. We now proceed to show these two models are equivalent. Let s be the function from 33 to (W-closed) subsets of 93 defined by: .(a) is the collection of all Q-filters with a as an element. Since 33 has property (l), s is an isomorphism between 9 and the power set of B (any subset is W-closed), where the boolean operations in 9 are the ordinary set-theoretic ones ([16] p. 87). We d e h e a reasonable isomorphism between R,"and RI as follows: Rf and RZ are identical. Suppose an isomorphism has been defined between R," and R," (pairing f ER: with f 'ER,").If g ~ 3 3 ~let~ g' " be that element of P R w Y defined by g' (f')= .(g (f)). It follows from the proof of theorem 6.1 below that g is extensional if and only if g' is extensional, so we have an isomorphism between R,"+,and

R:+

1'

Now we give the key theorem.

174

ADDITIONAL, CLASSICAL MODEL ClENERALXZATIONS

CH. 14 8 6

Theorem 6.1: Let X be a formula over Rf. Then X = X ( f i , ...,&) for fi,...,f,ER:. Let X ‘ = X ( f ; ..., where C E R : is the image of f i as

,c)

above. Then

{rI r k,x’}= s(u,(x)). (Similarly for the class models.) Proofl Suppose the result is known for all atomic formulas over R .: It then follows for all formulas X by induction on the degree of X . Suppose the result is known for all formulas of degree less than that of X. If X i s -Y,

(r I rc,x’) = (r I re,

N

Y’}=-

{r1 r b , y }

(where this is the complement in the boolean algebra of all subsets of 9. Since T 9 A implies r=A, it follows that either rk, Y’or TI=,- Y’, so this follows.) =

- S(U,(Y)) = s(-

u,(Y)) = S ( U , ( N Y ) )= s(u,(X)).

Similarly, if Xis (3x) Y(x),

= s (u4 ( P X ) = s (u4

y (4))

(4)

*

The other cases are similar. Thus, we must show the result for atomic formulas. Suppose the result holds for all formulas over R:. Letf,g E Rf+ We have three cases: Case (1) : f , g E R: Then the result is trivial. Case(2): feR:, gER:+l-R:

CH. 14 8 7

BOOLEAN VALUED

Ma

OENERALIzAnoNS

175

The limit ordinal and class cases are straight-forward. From this theorem, the essential equivalence of the two models follows. As a special case, suppose V, the underlying classical ZF model, is countable. Then ([16] p. 87-9.3) if YE V is a complete boolean algebra, B also has property (1). Thus if we assume there is a countable ZF model, the two R, generalizations are equal in power. The following results would be interesting, but are as yet undone: (1). A direct proof that <S,W,t, R’) is an intuitionistic ZF model. (2). A more general set of circumstances under which a boolean valued R, sequence has a corresponding equivalent intuitionistic R, sequence. (3). A direct proof that there are intuitionistic R, generalizations providing counter models for the continuum hypothesis, or the axiom of constructability (preferably not using countability of V). § 7. Boolean valued M , generalizations

Let V be a classical ZF model, and let B’EVbe a complete boolean algebra. We define simultaneously a sequence M,“ of boolean valued functions, and a sequence u, of homomorphisms from M,“ to 8. This is a direct generalization of the sequence of ch. 7 Q 2. Let Mf be some arbitrary collection of functions with domains subsets of MF and ranges subsets of 8.We assume Mf is well-founded

176

ADDITIONAL CLASSICAL MODEL GENERALEATIONS

CH.

14 6 7

with respect to the relation xedomainy. We assume M ~V.Euo is defined by the condition : for f,g e Mf 00

(fel)= 9 (f).

We require that Mf and uo satisfy the equality condition .O((V.)

(XEf

< Uo(&),

= x w ) ) rl "(f+

for anyf, g, h e Mf. Suppose we have defined M," and ua. If X ( x ) is any formula over M," with one free variable, by fx we mean the function whose domain is M ,: whose range is 99, and which is defined by f x (4= t),( X (4) for all X E M,". Let M,9d,l be M," together with all fx for all formulas X ( x ) over M,". We define u,+ for atomic formulas as follows. If f,g E M,"+ (I). iff,geM,", let ua+ 1 (fE 9) = Va (f Eg) ; 9

(2). iff€ Mt,g E M,"+

- M," ua+ 1

(3). iffxEMzl-M,",

let (feg) =

(f);

let

(where ua+l ( h e g ) has been defined in case (1) or case (2)). If I is a limit ordinal, let M f = U M,". axil

If f,g E M f , then for some a
(fEg) = ua (fEg)

Finally let Ma=

*

u M,". asV

If f,g E M", for some a e V f,g e Ma. Let u ( f e g ) = ua(fEg)*

CH. 1468

EQUIVALENCE OF THE kfa GENERALIZATIONS

177

Thus we have a boolean valued generalization of the Ma sequence, and of L.

8 8.

Equivalence of the Ma generalizations

Let (9, W ,bay Y a )be any intuitionistic Ma generalization, satisfying the conditions of ch. 1. We proceed almost as we did in Q 5. If f , g E Y a + l - Y a call f and g equivalent if (f=g) is valid in {9,W , ka+ly 9’a+1). Let 9:be some subset of Y acontaining only one from each collection of equivalent elements. 9is the collection of all W-closed subsets of 9.9 under E is a pseudo boolean algebra. If I; is the filter of all dense elements of 9,9?=9’/F is a boolean algebra. Define M f from Y oby induction on the well-founded relation XE domain (y), so that for f,g E Y othe corresponding elements f ‘,g’E Mf satisfy d ( f 9= 19(f)l* Under this definition ME and 9;are isomorphic by induction on the well founded relation xEdomain ( y ) . For if g‘=h’, then for allf’edom (9’) =dom(h‘), g’(f‘)=h’(f‘), so Igcf)l=Ihcf)l. It follows that for a1 T E Y Tko- -(fEg)= - ( f e h ) , and so rkoN(3x)N(xEg=xeh), so Tk,g=h.Then if g,h are in 96, g is h. Next we may show 9’; and M,” are isomorphic, and the mapping still satisfies g’ (f’)=Ig (f)!.Then following the procedure of 8 5, we may show

-

--

Theorem 8.1: If X is any formula with no universal quantifiers and no constants, Xis valid in the boolean valued model M” if and only if X is valid in (9, W , k, Y}. Similarly, following the procedure of Q 6 , we may show Theorem 8.2: Let A? be a complete boolean algebra satisfying property (l), and let Mf and vo satisfy the conditions in Q 6 . Then there is an intuitionistic sequence such that if X is any formula with no constants, X is valid in M” if and only if X is valid in (9, W , k, 9’}. Again the following results would be interesting: (1). A direct proof that M a is a boolean valued ZF model. (2). A more general set of circumstances under which a boolean

178

ADDITIONAL CLASSICAL MODEL GENERALIZATIONS

CH. 1458

valued Mu sequence has a corresponding equivalent intuitionistic Mu sequence. (3). A direct proof that there are boolean valued Ma sequences which establish the various set theory independence results.

APPENDIX (to ch. 11 52)

0 1. Corresponding formulas Dejinition 1.1 : Suppose r kpurtrel (R). We say R corresponds to the formula X over g with respect to r if there is a r* and a finite set of integers {il, ... in} such that Xis X(x,,, ..., xi,) and (1). X is dominant, (2). all the quantiliers (existential only) are bound to g, (3). for any constant a of X not a quantifier bound, I'* C (aEg), (4). r*b-(3x)- [xeDomain(R)=((x=i, v vx=i,)], (5). r*C ( 3 4 ... ( 3 4 " ) [X(Xi,, ..., Xin)Z

-

-

( g f ) ( f € R ~ f ( i , )Xii = A * - -A f ( T n ) = X i n ) ] . Lemma 1.2: Suppose ( 9 ,92, k, 9') is ordinalized. If r k ( R is atomic over g ) then R corresponds to an atomic formula over g, with respect to r. Proof: There are four cases, all treated similarly. We show only one. Thus suppose r k (R is atornic(2) over 9). Then for some a,beY

- f - ( -f ~ --

r k [integer (b) A

N

(a E g ) A

(3 ) R E (partfun (f)A domain (f)= {b) ~ f ( bE)a ) ) ] . Since k integer@), there is some r* and some integer n such that r*k (b= A). Since I'* k (aeg),there is some r**such that r**C (aeg). Let A=T**. Then d C [integer (fi) A u E g A - ( 3 f ) ~ ( f € R ~ ~ a r t f u n ( f ) ~ d o m a i n ( f ) =~f(A)eu))]. {Tt)

180

01

APPENDlX

Now we claim R corresponds to the formula (x,eu) over g. If we take the set of integers to be {n}, properties (1)-(4) are immediate. Property (5) becomes A ( 3 ~ ~ [x,€u ) G (3f)(f R A f(A) = x,)] .

.

- -

We show this in two parts: Suppose A * k ( 3 f ) ( f € R ~ f ( A ) = b Then ). for s o m e f E 9 A * C ( f e R ~ f ( f i ) = b )Since . A* C ( ~ E R by ) , the above A* C - f ( A ) ~ a .But also A*tf(A)=bAfunction(f), so A * k ( b ~ a )Thus . At

- (3x)

-

-

[(gf) (fE R

A

f (A)

= X)

2

xE U]

.

Conversely suppose A* t ( b ~ a )Let . Z ( x ) be the formula x = ( A , b), - 9,. The reader may verify and let w, be in some suitable

A* t [partfun (wz)A domain (w,)= A But A*kbea,

SO

A

w,(A) = b] .

A * ~ - - ( w ~ E R Thus ).

-- - -

A*k(3f)(--fcRAf(R)=b), d* k (3f) (f€ R A f (A) = b) , d C ( 3 ~ ) [ X E U =I (If) (fER A f(A) = x ) ]

.

Lemma 1.3: Suppose (9, W, k, 9)is ordinalized. If S corresponds to a formula X over g with respect to r, and r I=( R is not+) then R corresponds to the formula -X over g with respect to r. Proat Suppose without loss of generality that the finite set of integers for S is (1,2, ..., n}. We keep the same set for R. By hypothesis X is dominant, hence so is -X, thus property (1). Properties (2), (3) and (4) are immediate. Property (5) becomes

r*k N pX1) ...(3.”) But we are given

r*c

-

(3X,)

-

-

[- x ( X l ,

...,x,)

3

( g f ) ( f € RA f ( j ) = X l

A.*.Af(A)=X,,)].

...( ~ X J [x(xl, ..., XJ = (3f)(fES

Af(T)=Xl

A.*.Af(A)=X,)],

and r t ( R is not-S). We show property ( 5 ) in two parts. Suppose I‘*WA. If A C (3f) (fE R A f (1)= c1 A A f (A) = c,) , a . 0

APPENDIX

91

181

CORRESPONDING FORMULAS

then for s o m e f d A k(fER

But so A k

-

rC

Af(T)

= C1 A

- (3f)

~ f ( h )= c,).

[f ER = -f 4,

( ~ E SWe ) . claim that from this follows AC-X(cl,

..., c,).

For otherwise for some A* A*kX(c,, ..., c,). Then

-* --

(3f) (fE S A f (I)= c1 A

A* C

A

f (A)

= c,)

,

so for some gES

A k But

(9 E s) A g (I)= C1 A*k--(gES)

and

A* k

N

(3x)

-

A

.--A g (A) = C, .

A(~ER)

[ x E Domain(R) = x E Domain(S)] ,

so it follows that

A* C domain (f) = domain (g), A* t domain(f)= {I,..., A}. And A* C f (I)= g (I)A

- A f (A) = g (A),

thus But A* C Thus

N

(f&)

A

N

-

A*kf = g .

-

(g ES), a contradiction. Hence A k X(cl, ..., en).

I ' * C - ( ~ X ~ ) . . . ( ~ X , ) -[(gf)(fER

Af(T)

= X i A**-Af(fi)=Xn)3

..., c,). Then (3f) (fE S h f (I)= ~1 A

-X(Xl,...,X,)].

Suppose conversely A C -X(c,,

Ak

-

A

Let Y ( x ) be the formula x=(T,cJ

V*..VX=(A,c,),

f (A)

= C,)

.

182

$1

APPENDIX

and consider g r in some suitable 9’a+1 - Ye.The reader may verify that A C bartfun ( g y ) A domain ( g y ) = (1,...,f i } A 9y (1)= c1 A

k--

It follows that A C

--

( g y E Y ) . Hence A I.

dk--(gyER)Agy(T)=cl

d so

rc

-

(3f) c f E R

- -x

(3xl) ...(3xn) [

a

A

(xl,

...,x,)

(gf)(fER

( g y E R ) . That is

A.**A

f (T) = C 1

A

g ( A ) = cn].

A

*..

gy(A)=C,.

Af(fi)

= Cn]

,

3

A..*Af(fi)=X,)].

Af(T)=X1

We may in a similar fashion show

(a, W , C, 9)is ordinalized. Suppose S corresponds to a formula X over g and T corresponds to a formula Y over g with respect to r. Then (1). if TI=R is S-and-T, R corresponds to X A Y over g , (2). if rC R is S-or-T, R corresponds to X v Y over g , (3). if rC R is S-implies-T, R corresponds to X = Y over g . Lemma 1.4: Suppose

Finally we show Lemma 1.5: Suppose (9, 9, C,

9’) is ordinalized. Suppose S corresponds to a formula X ( x , , ...,xn) over g with respect to r, and r k R is ( 3 j ) S over g. Then R corresponds to the formula (3xj) [ ( x j ~ g A )

--

X(x1, *.*, xn)]

over g with respect to r. Proofi The finite set of integers for S is (1, ..., n}. We may take j to be 1. Then let the set of integers for R be (2, ...,n>. Now property (1) follows by theorem 7.7.3. Properties (2) and (3) are immediate, and (4) is straightforward. Property ( 5 ) becomes

r*b

(3x2)

We are given

r*P

-

-

...(b,)

( 3 q ) ...(3XJ

-

XI) (X1 E g

A

--

=(jf)(fER [X(X1,

...)x,)

x(Xl,

..., X n ) )

Af(2)=Xz

A*..Af(fi)=X,)].

3

(3f)(fESAf(T)=Xl

A.*-Af(h)=X,)].

APPENDIX

51

183

CORRESPONDING FORMULAS

We show property (5) in two parts: Let I'*BA. Suppose A k (3f) (fE R A f (2) = c 2 A A f (A) = c,)

.

Then for some f~Y d kf ER

A

f (2)

= C2

A

A

f (A)

= C,

.

But A k R is (31)s over g , so A k

--

(3h)(h € 9 A f = h 1 Domain ( R ) A h (I)E 9 ) .

Then for any A* there is a A** such that A** k h E s A f = h t DomUin(R) A

h(1)E 9).

For some U E Y d**Ch(l)=UAUEg.

It now follows that A** k h (I)= a

A

h (2)

= C2 A

-- --

so

*.*

A** k X ( U ,~ 2 ..., , c,), A** C ( 3 1)~[ X (X 1, C 2 , .. Cn) A** C(3x1) [ X ( X , , C 2 , ..., C,) A k - - ( 3 x i ) [ X ( X i y C 2 , . . . , C,) A

-

.

h (h) = C,

A

Eg ]

A Xi

9

A X i Eg]

9

,

X1Eg],

This establishes one half. Conversely suppose

A C (3x1) [ x i E g

A

N N

X

( X i 9 C2,

-.

3

C,)]

9

then for some U E 9' ACaEg

Thus AC

--

(3f) (f E

sA

A--X(U,Cz,

f(l)= a A f@)

..., C,). = C2

A

***

A

f(h) = C,).

So for any A* there is a A** such that

A ** k (3f) (f € s A f (I)= U A f (2) = C 2 A *.- A f (A) = C), A * * C . ~ E S~ f ( 1 =)a ~ f ( 2 = ) c2 A . . . A ~ ( A ) = c,.

184

APPENDIX

Let Y ( x ) be the formula v..*vx=(A,c,),

and let hy be in some 9’a+i - 9,The . reader may show A** t partfun (hy )

A

h, =f 1Domain R A f

(I)E g .

so

A**t h,ER,

A * * C ( h y ~ RA h y ( 2 ) = c2 A - . . A hy(A) = cn), A** k (3) ( h E R A h (2) = c2 A A h ( f i ) = c,) , A k - - ( 3 h ) ( h E R ~ h(2)=c2 A - . . A h(A)=c,).

This establishes the second half.

Theorem 1.6: Suppose (9, W ,kY5”) is ordinalized and

r t ( R is a definable relation over g ) . Then R corresponds to a dominant formula X over g with respect to

r.

Proofi TC ( R is a definabIe relation over g ) so, for some F E Y , some n and some r* integer 1

r* t function ( F ) A integer (A) A domain (F) = A A

- -

[x E A

=I F ( x ) is atomic over g

v F ( x ) is not-F(y)) v v (3y)(3k)(y E x A integer&) A F ( x ) is ( 3 k ) F ( y ) over X ) ] A (3m)(mE fi A F(m) = R). (3x)

(3y)(y E x

A

Now n is some particular integer. We examine 0, 1, ...,n- 1. That is

r*CSEA, SO

--

I’* I=

[F(S) is atomic over g v ( 3 y ) ( y ~ 0A F(6) is not F ( y ) ) v

So for some r**

r**I= F(0) is atomic over g v ...

In fact, since r * * k + y ) ( y E S ) ,

r**I= F(6) is atomic over g .

..-I.

APPENDIX

82

COMPLETENESS OF "HE DEFINABILITY FORMULA

185

r**C TER, so similarly there is a r***such that r***!= F(T) is atomic over g v ( 3 y ) ( yE T A ~ ( 1is)not-F(y)) v

Next

and also

r***I=~ ( 6 i)s atomic over g .

We proceed similarly for each m
.

Now by the above lemmas F(6) corresponds to a dominant formula over g with respect to A (hence to r).So F(T) corresponds to a dominant formula over g with respect to A (r),and so on to P(n - 1). Finally /\

d k (3m)(m E ti

A

F(m) = R),

so in some A* A* P & € t i

A

F(&) = R).

8 2. Completeness of the definabilityformula Theorem 2.1: Suppose (9, 9,I=, 9')is ordinalized and for some f , g E 9 and r != (fis definable over 9). Then there is some r* and some dominant formula X ( x ) with one free variable, no universal quantifier, all quantifiers bound to g, such that if a is a constant of X ( x ) not a quantifier bound, r*k (aeg) and

r*!= Pro08

(3~)

[XEf

+cg

A

x(x))].

r C (fis definable over g ) so for some r* R E Y , integer (n),

I'* C partrel(R) A integer (ti) A R is a definable relation over g A (gx) [xE Domain ( R ) E x = 121 A (3X) [ X . f E ( X E g A (3h)(h E R A h ( h ) = X ) ) ] .

- N

N

By theorem 1.6, R corresponds to a permanent formula X over g with respect to r. X must be one-placed, X=X(x,). Moreover, X is dominant, has no universal quantifiers, and has all quantifiersbound to g. There is some r**such that for any a of X not a quantifier bound

186

83

APPENDIX

r**k w g , and r**c

- -[x (~XJ

(XJ E

( 3 ~(f ) ER

A

f ( f i ) = x,)].

Now if T**WA and A k CEJ then ( c Eg

A

(3) ( hER

Al=--(c~g

A

X(c)).

Ak

so

N

A

h (A) = c)) ,

Conversely, if A k cEg A X ( c ) , then Akceg ~ - - ( 3 f ) ( f ~ R ~ f ( f i ) = c ) . At--[CEg SO

A ~ - - c E $ Thus

r**c

~ ( j f ) ( f E RA f ( f i ) = C ) ] ,

- (3~)

=

[ X E ~ (X

Eg

A

x(X))].

Thus we have established theorem 11.2.1.

0 3. Adequacy of the definability formula The proof of theorem 11.2.2 is rather like that of theorem 11.2.1, so we only sketch the general steps. Dejinition 3.1: Suppose X ( x i l ,..., xin)is a formula with no universal quantifiers, with all quantifiers bound to g E Y , and such that if a is a constant of X other than a quantifier bound, r k ( a e g ) . We say X corresponds to the partial relation R with respect to r if (1). ~ k - ( 3 x ) - [ x ~ D 0 m a i n ( R ) - ( x = ~v ., . . v x = i n ) ] , (2). r k (3xi,)...( ~ X J [x(x,,, ..., xi,) E ( 3 f ) ( f E R .f(t,) =xi A .f(Q = X i n ) ] , (3). r k ( R is a dejinable relation over g ) .

--

--

-

---

We wish to show Theorem 3.2: Suppose ('3, 9, k, 9')is ordinalized and X is a formula with no universal quantifiers, with all quantifiers bound to g E Y , and such that for r e g , for any constant a of X other than a quantifier bound r k - ( a ~ g ) . Then X corresponds to some partial relation R with respect to r.

-

APPENDM

53

187

ADEQUACY OF THE DEFINABILm FORMULA

To show this we must show a sequence of lemmas similar to those of 4 1. For example:

9’)is ordinalized, g , a E Y , and r C - -(aeg). Then the formula x,Ea corresponds to a partial relation R with respect to r such that I’ k R is atomic (2) over g . Lemma 3.3: If (9, 92, k,

Proofi Let Y ( x ) be the formula partfun(x) A domain(x) = {A)

A

x(A)E

u.

Let R , E ~ ’ ~ .ri”, + ~(where a,AEYa).Then

r k R,

is atomic (2) over g ,

and x,&a corresponds to R,. Similarly we may show the analogues of the other lemmas of 0 1. Finally, to show theorem 3.2, in a sense we reverse the procedure of the proof in § 1. We proceed through subformulas of X , using the lemmas referred to above, concluding with X . Given theorem 3.2, theorem 112.2 is straightforward.

BIBLIOGRAPHY

[l] Aczel, P. H. G., Some results on intuitionisticpredicate logic, abstract in J. Symb. Logic., 32 (1967) 556. [2] Beth, E. W., Thefoundations ofmathematics, North Holland, Amsterdam (1959); also, Harper and Row, New York (1966). [3] Cohen, P., Set theory and the continuum hypothesis, W. A. Benjamin, New York (1966). 141 Godel, K., Consistency proof for the generalized continuum hypothesis, Proc. Nation. Acad. Sci. U.S.A. 25 (1939) 220-224. [ 5 ] Gregorzyk, A., A philosophically plausible formal interpretation of intuitionistic logic, Zndag. Math. 26 (1964) 596-601. [6] Hajek, P. and P. VopMca, Some permutation submodels of the model V, Bull. Acad. Polon. Sci. 14 (1966) 1-7. [7] Jech, T. and A. Sochor, On 0 model of the set theory, Bull. Acad. Poton. Sci. 14 (1966) 297-303. [8] Jech, T. and A. Sochor, Applications of the 8 model, Bull. Acad. Polon. Sci. 14 (1966) 351-355. [9] Johansson, I., Der Minimalkalkiil, ein reduzierter intuitionistischer Formalismus, Comp. Math. 4, (1937) 119-136. [lo] Kleene, S. C., Introduction to metamathematics, Van Nostrand, New York (1952). [ll] Kleene, S. C., Mathematical logic, Wiley, New York (1967). [12] Kripke, S., Semantical analysis of modal logic I, 2.math. Logik u. Grundl. Math. 9 (1963) 67-96. [13] Kripke, S., Semantical analysis of intuitionistic logic I, in Formal systems and recursive functions, North Holland, Amsterdam (1965), 92-1 30. [I41 Lewis, C. I., and C.H. Cooper Langford, Symbolic logic, 2nd ed., Dover, New York (1959). [IS] Prawitz, D., Natural deduction, a proof-theoretical study, Acta Universitatis Stockholmiemis, Stockholm Studies in Philosophy No. 3, Almqvist and Wiksell, Stockholm (1965). [16] Rasiowa, H. and R. Sikorski, f i e mathematics of metamathematics, Panstwowe Wydawnictwo Naukowe, Warszawa (1963).

BIBLIOGRAPHY

189

[17] Schiitte, K. Der Interpolationssatz der intuitionistischen Pradikatenlogik, Math. A m . 148 (1962) 192-200. [18] Schiitte, K., Votfstandige Systeme modater und intuitionistischerLogik, Springer, Berlin (1968). [19] Scott, D. and R. Solovay, Boolean-valued models for set theory, Summer Inst. Axiomatic set theory, Univ. of Cal., Los Angeles, 1967; to appear in Proc. Am.

Math. SOC. [20] Smullyan, R. First order logic, Springer, New York (1968). [21] Thomason, R. H., On the strong semantical completeness of the intuitionistic predicate calculus, J. Symb. Logic 33 (1968) 1-7. [22] Vophka, P., The limits of sheaves and applications on constructions of models, Bull. Acad. Pofon. Sci. 13 (1965) 189-192. 1231 Vopbka, P., On V model of set theory, Bull. Acad. Polon. Sci. 13 (1965) 267-272. [24] Vophka, P., Properties of V model, Bull. Acad. Polon. Sci. 13 (1965) 441-444. [25] Vophka, P., V models in which the generalized continuum hypothesis does not hold, Bull. Acad. Polon. Sci. 14 (1966) 95-99. [26] VopEnka, P., The limits of sheaves over extremally disconnected compact hausdorff spaces, Bull. Acad. Polon. Sci. 15 (1967) 1-4. [27] Vophka, P. and P. HAjek, Permutation submodels of the model V, Bull. Acad. Polon. Sci. 13 (1965) 611-614. [28] VopBnka, P. and P. Hijek, Concerning the V models of set theory, Bull. Acad. Pofon. Sci. 15 (1967) 113-117.

SUBJECT INDEX

almost-truth set 50 atomic formula 19,45

inconsistent 29 intuitionistic ZF model 91

boolean valued logic 163 boolean valued ZF model 165 bounded quantifier 100

maximal consistent 60 minimal logic 40 modal logic 41 model (algebraic) 23, 163 model (first order intuitionistic) 46 model (propositional intuitionistic) 20

cardinalized model 130 complete sequence 51 wn6guration 29 consistent 29 constructable set representative 143 countably incompatible 130 Craig interpolation lemma 78

nice 67 ordinalized model 125 ordinal representatives, canonical 125 ordinal representatives, general 123

deductively complete 67 degree of a formula 20,45 dominant 96 downward saturated 31

pure 50 pseudo-boolean algebra 23

E-stable 143

Q-homomorphism 164

forces 20 forcing condition 116, 133, 150 formula 19,45

realizable 31, 55, 71 reduction rules 28

good 61 Hintikka collection 32, 56 Hintikka element 57 Hintikka set 31 homomorphism (algebraic) 23, 164

s 4 41 satisfiable 71 signed formula 28 stable 100 strongly bounded quantifiers 100 subformula 20, 45

SUBJECT INDEX

tableau 29, 42, 53, 76 truth set (first order) 50 truth set (propositional)41

valid (propositional intuitionistic) 20

universal model 70

X-equivalent 11 1

valid (first order intuitionistic) 46

m-dominance 140

well-formed formula 19

191