A Theory of Sets

A THEORY OF SETS

PURE AND APPLIED MAT H EMAT I C S A Series of Monographs and Textbooks

Edited by

PAULA. SMITHand SAMUEL EILENBERC Columbia University, New York I : ARNOLD SOMMERFUD. Partial Differential Equations in Physics. 1949 (Lectures on Theoretical Physics, Volume V I ) I1 : REINHOLD BAER.Linear Algebra and Projective Geometry. 1952 I11 : HERBERT BUSEMANN A N D PAULKELLY.Projective Geometry and Projective Metrics. 1953 I V : STEFANBERCMAN AND M. SCHIFFER. Kernel Functions and Elliptic Differential Equations in Mathematical Physics. 1953 V : RALPHPHILIP BOAS,JR. Entire Functions. 1954 V I : HERBERT BUSEMANN. The Geometry of Geodesics. 1955 VII : CLAUDE CHEVALLEY. Fundamental Concepts of Algebra. 1956 V I I I : SZE-TSENHu. Homotopy Theory. 1959 IX : A. OSTROWSKI. Solution of Equations and Systems of Equations. 1960 X : J. DIEUDONNB. Foundations of Modern Analysis. 1960 X I : S. I. GOLDBERG. Curvature and Homology. 1962 XI1 : SICURDUR HELCASON. Differential Geometry and Symmetric Sp,aces. 1962 XI11 : T. H. HILDEBRAN~. Introduction to the Theory of Integration. 1963 XIV : SHREERAM ABHYANKAR. Local Analytic Geometry. 1964 XV : RICHARD L. BISHOPA N D RICHARD J. CRITTENDEN. Geometry of Manifolds. 1964 XVI: STEVENA.GAAL.Point Set Topology. 1964 XVII : BARRYMITCHELL. Theory of Categories. 1965 XVIII: ANTEONYP. MORSE.A Theory of Sets. 1965 In preparation : A. M. OSTROWSKI. Solutions of Equations and Systems of Equations. 2nd Edition. GUSTAVECHOQUET. Topology. Josk LUIS MASSERA A N D JUAN JORGE SCHAFFER. Linear Differential Equations and Function Spaces. 2. I. BOREVICH AND I. R. SRAFAREVICH. Number Theory.

A THEORY OF SETS by Anthony P. Morse DEPARTMENT OF MATHEMATICS

UNIVERSITY OF CALIFORNIA BERKELEY, CALIFORNIA

I965

ACADEMIC PRESS

New York and London

COPYRIGHT 0 1965, BY ACADEMICPRESSINC. ALL RIGHTS RESERVED. NO PART OF THIS BOOK MAY BE REPRODUCED IN ANY FORM, BY PHOTOSTAT, MICROFILM, OR ANY OTHER MEANS, WITHOUT WRITTEN PERMISSION FROM THE PUBLISHERS.

ACADEMIC PRESS INC.

111 Fifth Avenue, New York, New York 10003

United Kingdom Edition published by ACADEMIC PRESS INC. (LONDON) LTD. Berkeley Square House, London W. 1

LIBRARY OF CONGRESS CATALOG CARDNUMBER: 65-22765 PRINTED IN THE UNITED STATES OF AMERICA.

To Barbara

This Page Intentionally Left Blank

FOREWORD BY

TREVOR J. MCMINN

Here in a formal inferential system is ensconced an axiomatic logic and set theory. With rudiments and simple versatile prescriptions, ground is prepared for shaping a wide selection of formal inferential languages. Then upon this ground is fashioned a particular formal inferential language that is lean, mechanical, vigorous, and more than adequate for the purposes a t hand. At the same time, within the language, on axiomatic foundations broadly and deeply laid, logic and set theory are deductively built in strikingly unified combination. The axioms are amenable to replacement of schematic expressions by almost any formula, guarantee a non-elemental universe, enable the set of x such that ...x . . . to be defined, and ensure the elementhood of many sets. The set-theoretic structure is substantial, with numerous interesting topics, including the most essential ones, taken up and dealt with in efficient dependent order. The initial treatment of each is thoroughgoing, and, on occasion, new results are introduced.2 Altogether these topics provide a firm base and house a variety of useful tools for farreaching mathematical theories. The system is described in spare and trenchant English which reflects the author’s endeavor each time to hit the nail on the head and drive it home with one stroke. Together with a scattering of similarly phrased informal interpretive asides, suggestive headings, and stage directions, the formal language then takes over the task of elucidating mathematical ideas. A title given to a section, subsection, rule, definition, or theorem hints a t subjects entertained, roles played, historical origins, or mathematical emphasis. Generally speaking a n entitled section embraces only one topic and lists a t the beginning each definition first used in the section. With many results identified as numbered theorems, the reader is led with measured pace through the book. No single step is hard to take, few proofs are long, and all are perspicuous. 1 2

The Table of Contents fairly summarizes the topical sweep. Some, but by no means all, of these results are touched upon in the author’s preface.

vii

...

Foreword

Vlll

This high degree of organiFation makes reference easy for one familiar with the formal language apd imparts to the text a skeletal appearance somewhat belying the full-bodied mathematical treatment. The book is the result of successive refinements of lectures given by the author over the years at the University of California at Berkeley. In the process the system has evolved from one of little formality and traditional separation of logic and set theory to the present one of complete formality and unified logic and set theory. The axioms for set theory have undergone a metamorphosis from ones like those appearing in the Appendix to J. L. Kelley’s General Topology to the present more primitive ones. I n recent years the formal language has been actively used by the author and students in course work in set theory and analysis and the axiom system has been tested with experience. Readers at various levels of mathematical education may well profit from this elegantly handled aed bold-spirited enterprise. A scholar who already largely understands the author’s objectives is still apt to discover much that is original and ingenious in his way of attaining thetn. A student perplexed by fundamental questions stands a good chance of finding them answered. One less interested in the foundations of set theory than in its superstructure should be amply rewarded for effort spent in learning necessary preliminaries by the impetus given to his understanding of the subsequent beautiful edifice. Because of a paucity of instructional elaboration of the book’s linguistic-logical-mathematical subtleties, the less expert reader is provided in ensuing paragraphs of this foreword with some expansive, semitechnical, and advisory comments. These may help him to see better both the forest and the trees. They have been devised to give him an inkling of what the author is up to in Chapter 0, the first part of Chapter 2, and in the Appendix, to highlight some special virtues and characteristics, and to suggest points of view and ways of approach. Chapter 1 needs little comment, and the problems in understanding the latter part of Chapter 2 are almost purely mathematical. The more technical of these comments will probably be of most help when read concurrently with a study of relevant sections of the book itself. This commentary is followed by a brief description of the axiomatic structure of some of the other set theories which have originated since the turn of the century together with comparative remarks to place the present system among them.

*

*

*

Foreword

ix

I n that initial part of Chapter 0 which ends with the section on Indicia1 and Accepted Variables, the author's concern is to set forth construction rules for a written language capable of conveying mathematical meaning. The language itself consists of inscriptions called expressions which are linear arrays of certain more or less connected inscriptions called symbols. Expressions in the language are of various sorts (for example, the definor, the punctuator, schemators, definitions, axioms, constants, variables, definienda, forms, formulas, primitive constants, primitive forms, schematic forms, schematic expressions, simple expressions, etc.) . Certain rudimentary expressions (for example, 'u' - a schemator, 'u'xx" a schematic form, ' =' the definor, a primitive constant, ' (x = y) ' a primitive form, ' (0 = A x x ) ' a definition, ' (x tt (0 E X ) ) ' a n axiom, etc.) are specifically listed and, together with certain of their parts, are somewhat arbitrarily identified as being of one sort or another. Two very simple methods of combining expressions (replacement and schematic replacement) for the purpose of constructing further expressions are mentioned and illustrated. Prescriptions (in the form of agreements and rules) are laid down for telling us of what sort the rudimentary and constructed expressions are. Some are statements of relation between certain expressions (for example, Rule 0.2: A variable is free in a form if and only if it occurs therein less than twice). Others (for example, Rule 0.4) are descriptions of a test applied to a pair of expressions to see if one bears a certain relation (in this case freeness) to the other. Still others (for example, Rule 0.3: A is a formula if and only if some variable is free in A ) tell whether a n expression is of a certain sort in terms of its relations to other expressions. We want to know what is in the language and in its various components and what relations certain members bear to others. The specific identifications, constructive replacements, and prescriptions are our sole means of finding out. Quite mechanically, one step at a time, through prescribed replacements, new expressions in the language are constructed from those that have already been constructed or from the rudimentary ones. As these new expressions arise, they are cataloged and their relations to some of the others are noted. The expressions we are mainly interested in are constants, variables, forms, and formulas. I n order to simplify the formalization no attempt has been made to prove facts about expressions in the language. When it has seemed

X

Foreword

necessary or fruitful to use such facts, they have merely been assumed as numbered rules (for example, Rules 0.13-0.16). A rule is thus thought of in Chapter 0 as being meta-axiomatic. Although the relations of freeness, indiciality, and acceptedness between certain expressions are categorically described by the agreements and rules, they are not explicitly defined. Thus, although a method is here prescribed for demonstrating freeness or lack of it in any given case by considering expressions bearing certain relations to others, freeness is not prescribed in the explicit form ‘ Q is free in A if and only if...’. I n the later section on Chains such prescriptions are made explicit. The author’s second concern in Chapter 0, set forth in the section on Rules of Inference, is to establish the process of mathematical inference. Among all formulas are singled out for special attention those called theorems. At the outset all listed definitions and axioms are theorems. Starting from these, through certain prescribed changes embodied in the rules of inference, other theorems are constructed in somewhat the same mechanically iterative manner in which formulas are constructed from the rudimentary expressions. Here again tests are prescribed for telling us whether a given formula is a theorem. However, this is not to say that a test may be easily made. Hardly so. I t amounts to exhibiting a n ordered list of theorems, each of which results from some of its predecessors by the application of a rule of inference, terminating with the formula in question. Such a list is a formal proof. Together with definitions dispersed throughout, the whole of formal mathematical literature consists of just such an ordered list headed by the axioms. I n this section on Rules of Inference the notion of theorem, like freeness, is not explicitly defined. Unlike freeness, it is not categorically described. Thus no prescription is given here for determining that a given formula is not a theorem. However, in the section on Demonstrations the notion of theorem is made explicit. It is to be hoped, quite naturally, on the basis of the axioms adopted in Chapters 1 and 2 that not all formulas are theorems, that is, that the resulting system is consistent. I n the foregoing nutshell description of the author’s formal system none of its nicer features is really evident. Some of these deserve special mention.

xi

Foreword

The strictly linear structure of expressions that has been adhered to throughout facilitates their technical analysis and enables them to be read serially from left to right as a machine might well be made to do. A high degree of simplicity has been achieved in the statement of rules and agreements for constructing the language by holding down the number of sorts of expressions treated. Here no distinction is made between sentential variables and nominational variables, much less between set variables and point (element) variables. Also no distinction is made between statement-like expressions and name-like expressions (elsewhere these are commonly known as formulas and terms, respectively). Together these are here simply formulas. Thus among the formulas are ‘ (0 E X ) ’, ‘ ( X E 1) ’, ‘ ( X -+ X ) ’, ‘ ((0 = V X E 1 X ) A AX(X-+ x ) ) ’,

‘Vx(0 E x ) ’,

‘{x}’,

‘ ( x , x ) ’, ‘ Ex(0 E X ) ’, ‘ A x ; (0 E X )

x’.

Except at the very first, each new form is introduced as a definiendum (the left side of a definition). Yet regardless of whether or not the definition is properly constructed, once the constants appearing in the form are known (see page 4), the grammar of the form, that is, a tally ofwhich variables are free and which are indicial, is easily determined by simply counting occurrences of each variable. The use of schematic expressions enables many definition schemas, axiom schemas, and theorem schemas to be rendered as a single formula in the system and thus amenable to treatment as such. Once the legitimacy of a substitution or a schematic substitution has been established the substitution or schematic substitution itself is carried out by a straightforward replacement or schematic replacement which does not distinguish occurrences. The requirement that schematic expressions not only have the same schemator but be entirely the same to qualify for schematic replacement considerably simplifies the mechanics of schematic substitution. Allowing mixed expressions in which there appear variables neither free nor bound (see A. 18) provides a great deal of freedom in substitution. For example, in 2.35 is found the theorem ‘(x~Exux+-+_ux~x~U)’

(1)

in which ‘ x ’ is neither free nor bound. From it one easily obtains as theorems ‘ ( x E Ey uy e,ux A x E U)’ (2)

xii

Foreword

and

‘(X

E

E?J UY - t)VZJ(X=ZJA UZJ) A x E u) ’.

(3)

An interesting aspect of (1) shared by neither (2) nor (3) is that a theorem is obtained from ‘ ( x E ExP-

P Ax

E

U)’

by replacing ‘ x ’ by an arbitrary variable and ‘ P by an arbitrary formula. Worthy of note is the all-embracing scope of the author’s preparatory setting. I t is a novelty that his formal inferential system is not specially tailored to his logic and set theory. Without changing this system in any way, one could, by introducing appropriate mathematical definitions, equally well formally pursue radically different mathematical disciplines with quite different primitive concepts. With the language at hand we, of course, interpret it by attaching meaning to the expressions in it. This is essentially an intellectual process for which no prescription can be given. Only the use of words appearing in definitions common also in every day usage suggests the proper attachment of intuitive mental concepts which one already possesses. An interesting feature of the author’s development is that only a scant few basic concepts are appealed to. Once the appropriate conceptual meaning has been attached to ‘ = ’ (“definitionally equivalent to”), ‘+’ (“implies”), ‘A’ (“for each”), an adequate start has been made for logic; and once the appropriate conceptual meaning has been attached to ‘ E ’ (“ is in ”) , and ‘ me1 ’ (“ choice ”) , an adequate start has been made for set theory. We are specially interested in those formulas devoid of schemators in which every variable actually appearing is bound (see A. 18). It is with these latter, known as sentences or names, that we associate, on the one hand, mathematical ideas or propositions, and, on the other hand, specific concrete mathematical things in another, ideal (mental) world, the mathematical world which, of course, no one should confuse with the world of inscriptions. Thus the formula ‘ (0 E 1) ’ is a sentence expressing a mathematical idea, namely, that the empty set belongs to the set whose only member is the empty set, and 0 is a name for a mathematical thing, the empty set. Other formulas, like ‘ ( x E y) ’ and ‘ { x } ’, with free variables actually appearing in them, although neither sentences nor names are akin to them in that they can be made into sentences or names by replacement, for instance, by replacing ‘ x ’ by ‘0’

...

Foreword

Xlll

and ‘y’ by ‘ 1 ’ in the aforementioned to get ‘ (0 E 1 ) ’ and ‘{O}’, or by quantifying, for instance, by writing ‘AxVy(x E y) ’

or

‘Ax{x}’

Each is capable, by being transformed in certain ways into sentences or names, of conveying many specific and concrete meanings, all of a more or less similar nature. The significance of theorems lies in their interpretation. A theorem, in addition to any idea it may convey as a formula, inspires in us, at least provisionally, belief that the idea conveyed is right. Theorems need not be sentences. For example, the formula ‘ ( x = x) ’ is a theorem. We believe every specific idea conveyed as the result of replacing ‘ x ’ in this theorem by a name as well as by universally quantifying it. I t is a peculiarity of the author’s system as axiomatized in Chapter 2 that frequently in one breath a mathematical idea is expressed and a set is named. Each set is either true or false and each sentence is a name for some set. I t turns out that 1 is true, that (1 , 2 ) is false, that (0 E 1) is the mathematical universe, and that (0 E 0) is the empty set. I t also turns out, rather less surprisingly, that 1 is the set whose only member is the empty set, that ( 1 , 2) is an ordered pair of natural numbers, that (0 E 1) is true, and that (0 E 0) is false. I n trying to swallow this unified notion of logic and set theory one may find at first that it sticks in his craw. A purist might argue that it is contrary to good principles of nomenclature to have a formula express an idea and name an object at the same time. I n support of unification one may take the view that the idea expressed and the object named are always so different that practical confusion will not crop up over the ambiguity as to which of the two is intended. The damage to one’s preconceptions turns out to be not as great as one might at first think, and in most instances it is pretty clear whether a given formula is to be thought of as statement-like or as name-like. I t turns out that if and only if

V x E 3((0 E X )

A UX) -

for some x in 3, 0 is in x and ux;

it also turns out that

V x E 3((0 E X )

-

A UX)

xiv

Foreword

equals ux. the union as x runs over 3 of the intersection of (0 E x ) with Of the two interpretations of ‘ V x ~ 3 ( ( E0 X ) A ( x # 1 ) ) ’ thus suggested, the first is probably intended and we know what idea (incidentally right) is conveyed. Of the two interpretations of

‘VXE~((~EX)AX)’

likewise suggested, the second is probably intended and it can be checked that ( 2 = Vx E 3((0 E X ) A x ) ) . To take another instance, in Chapter 1 we are mainly interested in knowing that 0 is false, whereas in Chapter 2 we are mainly interested in the fact that 0 is the empty set. In any event, whatever the interpretation that is made, it has no bearing on the consistency of the system considered as a game played according to rules with expressions. Aside from the sheer elegance of this unified structure, attested to in part by the features mentioned in the author’s preface, numerous technical benefits result, among which is the possibility of exploring areas of logic and set theory simultaneously. An example may help to indicate this possibility. Since (p + q ) is equal to (-p v q ) , we can say that the set (p -+ q) is the complement ofp, union q, and, by way of an axiom (2.5.0), that ( p + q ) is true if and only if 0 belongs to the complement of p or to q. Since (-6 v p) is the universe, and 0 belongs to the universe, we see that (p + p ) is true. To give a glimmering of other technical advantages of unification we note that in the theorem

‘((0 E x )

= Ey(0 E x ) ) ’

the left side is more concise than the right. The author’s third concern in Chapter 0 is to formulate a practical theory of notation that will simplify formulas and leave them uniquely readable without sacrificing mathematical consistency. This is a noteworthy effort that goes beyond the mere listing of shorthand devices and rules of thumb. The language retains its machine-like precision, is eminently usable, and incorporates many of the usages of traditional mathematics. Furthermore, this effort goes beyond the adopting of

xv

Foreword

conventions for a language germane only to elementary set theory. Having in mind a language with wider applicability in later branches of mathematics, the author has adopted several conventions that harmonize simplifications in this unexploited language with the herein developed language of elementary set theory. Due to the use of constants other than introductors in forms, like ‘ + ’ in ‘ ( x + y) I , a great variety of new forms can be introduced from a fixed collection of constants by varying the arrangement of them with variables and schematic expressions in a matrix. An example of this economy is given in the combinatorial sum definition

‘( ( A++ B) = E x

+ y ( x E A A y E B ) )’.

-

Other abbreviational nuances that are both interesting and useful can be gleaned from the theorems

‘ .( ,y , 2 E A

‘ ( x ,y , t ,EA f-f

( x ,y

.(

, t) , E A

,y , 2) E A ) ’, x E A ~y E A A

t)

z E A ) ’.

The theory of notation systematically exploits some of these possibilities. The author’s fourth concern in Chapter 0, treated in the section on Demonstrations, is to devise a framework for analyzing formal proofs. I n this setting the notion of a theorem is explicitly defined in terms of the notion of a formula. Certain expressions are called demonstrations. A demonstration, roughly speaking, is the ordered concatenation of the theorems listed in a formal proof. Certain formulas in a demonstration are identified as subformulas. A trifle more precisely, a demonstration is built up iteratively starting from definitions or axioms by juxtaposing on the right a formula obtained from subformulas of what is already at hand by inference from these subformulas. A theorem then is a subformula of some demonstration. The author’s fifth and last concern in Chapter 0, treated in the section on Chains, is to explicitly define indiciality, acceptedness, freeness, and parentheticality. One way of doing this would involve intuitive set theory somewhat in the spirit of A.29-A.38. The way adopted by the author uses concatenations of certain expressions each initiated by a symbol, the punctuator, counted among the constants but never allowed to appear in a form, and each a beginning expression or an expression obtained by certain replacement operations from preceding such expressions in the array. Such arrays are called chains. Chains are thus

xvi

Foreword

built up iteratively by juxtaposition on the right somewhat as demonstrations are. The expressions juxtaposed minus the punctuator are called links. Four kinds of chains are considered. I n the case of a free chain each link is the concatenation of a variable with a form in which the variable is free or with an expression, obtained by replacement operations from preceding links, in which the variable is free. I n furtherance of a correct notational theory, the author has included an appendix on definitions. Since from definitions we learn what are constants, variables, and forms, and since definitions are theorems, one can easily arrive at contradictions both metamathematical and mathematical by accepting improperly constructed ones. I n the Appendix rules governing the correct formulation of definitions are so made that: parentheses are constants; ‘ x ’ is a variable; the end of a definition is determined by an internal routine; each definition is a formula; the notion of a formula is categorical; no formula, which is meaningful, but not a theorem prior to the addition of a definition, becomes a theorem after the addition of the definition; every formula has a primitive translation. Also circularity is avoided since the theorem

‘(OE

(Oh

I))’,

which does not violate the last two above requirements, is, quite rightly, not allowed to be a definition. At this point some words ofreassurance should perhaps tie extended to the reader impatient with precise linguistic foundations and anxious to come to grips with the mathematical content of Chapter 2 . Once he has got the hang of constructing a few formulas not dependent upon the theory of notation, he will avoid, and with good reason, the laborious task of intricately checking to see if a given expression is a formula. H e will probably be able to see intuitively a t a glance if it is one and from which forms it was obtained and how. With the exception of certain orienting definitions like 0.0.0, 0.0.1, and 2.0 there are no tricks that would lead him to think, contrary to his upbringing, that expressions like ‘ ( x E’, ‘ ( + x +)’> ‘/lux’ are formulas. Expressions that have been simplified by taking advantage of the theory of notation may give somewhat more trouble, but since efforts have been made to make them seem at first blush reasonable, even they

xvii

Foreword

can mostly be deciphered intuitively with only a n occasional reference to the theory. For instance, it seems reasonable that useful meaning should be ascribed to the expressions ‘ V x ;_ uxvx’, _

‘Ax E Y ux’, -

‘sng x ’ ,

‘ ( x =y

A a

E b c c)’

and that they be included among the forms. The first and last of these can probably be guessed a t here, and there is perhaps a fifty-fifty chance that the others can be too. In reading a formula, from left to right, advantage should be taken of the fact that no formula is an initial segment of another in order to pick off one by one the formulas which have been inserted into a form. If the candidacy of a form, for such insertions, is not clear at the start it will soon become so. I t may well comfort the reader to know that if he can contrive one valid reading of a formula, then that reading is correct. A case in point is the form

‘(P -+q

-+r)’,

which, because of 0.37 and in keeping with the spirit of ordinary implicational proofs, means the same as and not the same as I t might be noticed that

‘((P+ 4 )

A

(P - 6 ) ’

‘((P

A

(4

+

‘(P

can be obtained from the form

q)

+

+

r ) ) ’.

4 +r)’

‘ ( x +Y) ’

by replacing ‘ x ’ by p + q and ‘y’ by ‘ r ’ , as well as by replacing ‘ x ’ by p and ‘y’ by ‘ q + r ’ . However as it turns out, neither of these readings is valid since neither ‘p --f q nor ‘ q 3 r ’ , lacking parentheses, is a formula. I n this connection

‘(P

-+

4

+ 9 ’ > ‘((P+d

-+r)’,

‘(P

+

(4 - + r ) ) ’

are different from each other both in appearance and meaning. At any rate, a thorough grasp of the Theory of Notation is far from essential for comprehending Chapters 1 and 2.

xviii

Foreword

In the same vein, though some of the rules of inference may look complicated, a moment’s reflection should convince the reader that they cannot all be utterly simple when stated precisely. He need examine but one application to be assured that they only accurately prescribe in general what he would almost certainly be inclined by mathematical second nature to allow in any instance. Thus by indicial substitution (0.28) we infer that since ‘ (Ax ux - t)Ax gx) ’ is a theorem, then ‘ (Ay uy t,A x gx) ’ is a theorem. This is seen by letting

9 be

‘2’’

Q be ‘ ( z t,Ax UX) - ’, T be ‘ (Ax ux H Ax yx) ’, A be ‘Ax ux’, a be ‘ x ’ , B be ‘Ay uy - ’,

T’ be ‘ (Ay uy e,Ax gx) ’, and by checking that

9 is free in Q,

A is a form, a is indicial in A ,

‘y’ is accepted in A . Having once checked in detail the validity of an application of a rule of inference, the reader will not likely do it often again. And there is 1 1 0 reason why he should. In actual mathematical literature formal proofs are rarely exhibited. Ordinary proofs are considered as commentaries designed to convince one of the possibility of constructing formal ones. This treatise on set theory is no exception. However, a certain formality is retained here in that, although many gaps are permitted in the shortening of a formal proof to a n ordinary one, an effort has been made, up through 2.37, to make each entry formally correct and a theorem. Thereafter in

XiX

Foreword

establishing implications a somewhat relaxed, but thoroughly sound method is frequently employed. Sentences structurally incorporating formulas along with ordinary English words and phrases are punctuated in the customary way. Formulas not so incorporated stand without further punctuation. Many readers will find it expedient to plunge directly into Chapters 1 and 2, grasping by context and preconceptions the gist of what is being said, and resorting to Chapter 0 only when necessary to pick up indispensable basic notions and notation^.^ All readers are strongly urged to explore Chapters 1 and 2 before attempting to completely master Chapter 0. The informal passages give succinctly the necessary clues, while the formal passages encapsule much mathematical content in small compass. Because of this the reader is well advised to read slowly and carefully and, whether he scans or delves, to take for granted that the author’s words have been weighed, his formulas accurately cast, and that he means exactly what he says.

*

*

*

Set theories are largely characterized by the provisions that are made for constructing sets from properties and for relating membership in a set so constructed with satisfaction of the property, on the one hand, and, on the other, by the provisions that are made for determining what sets are capable of belonging to some set, that is, of being elements. In short, in a given system, if A is the set of x such that ...x . . ., then we are interested in knowing just what are members of A and whether or not A is an element. Since the paradox revealed by Russell in 1901 precludes the allencompassing provision of taking as a classification axiom each formula obtained from ‘VAAX(XEA~,P)’ (4) by replacing P by a formula in which ‘ A ’ does not appear, other so far successful provisions have been engineered. Those of Russell and Whitehead4 lie in restricting the kinds of formulas which may be considered as replacements for ‘P’. Only suitably restricted ones are considered meaningful and only for one of these does (4) give rise to an axiom. Use of the Index of Consonants may shorten subsequent’referentialsearches. Russell, B. A. W., and Whitehead, A. N., Principia M a t h t i c a , 3 vols., Cambridge Univ. Press, 1910, 1912, 1913. 3

4

xx

Foreword

The Zermelo-Fraenkel provisions lie in accepting as a classification axiom each formula obtained from

‘ABVAhx(x E A H P A x

E

B)’

(5)

by replacing ‘ P ’ by a formula in which ‘A’ does not appear. Then, because of the dependence of A upon B, other axioms are adopted to assure the existence of at least one set and indeed of more than one. Thereafter (5) is used to get a great variety of sets. However, no universal set is forthcoming from ( 5 ) . An important feature is the total lack of restriction placed upon the capability of a set being an element. Stemming from von Neumann’s idea that it is not so much the existence ofsets constructed from arbitrary properties that induces paradoxes as the lack of restraint in allowing them to be elements, are the systems of von Neumann-Bernays-Godel,6 Quine, and Morse. The von Neumann-Bernays-Godel set-theoretic axiom system is both finite and unschematic. An axiom provides for the existence of a set with a certain property, and further axioms provide for the existence of other sets dependent upon given sets. In addition an axiom provides for the existence of an element, and further axioms provide for the existence of other elements dependent upon given sets or elements. I t then can be shown that a classification theorem is obtained from

‘ VAAx(x E A

P A V B ( x E B ) )’

t)

by replacing ‘ P ’ by such a formula rp that: A does not appear in rp; quantification in rp is restricted to elements. Whether or not the set A is in turn an element must be determined from the axioms about elements. An early consequence is the existence of a unique universal set. Were it to be an element, a Russell type paradox would ensue. I n Quine’s system a classification axiom schema is described which amounts to accepting as an axiom each formula obtained from

VAAx(x E A ++ P

A

V B ( x E B ) )’

(7)

by replacing ‘ P’ by a formula in which ‘A’ does not appear. I n addition 5 Fraenkel, A. A., and Bar-Hillel, Y., Foundations of Set Theory, North-Holland Publishing Co., 1958. 6 Godel, K., The Consistency of the Axiom of Choice and of the Generalized Continuum Hypothesis with the Axiom of Set Thory, Princeton Univ. Press, 1940. 7 Quine, W. V., Mathematical Logic, rev. ed., Harvard Univ. Press, 1951.

xxi

Foreword

there is described an elementhood axiom schema which amounts to accepting as an axiom each formula obtained from

V A ( A x ( xE A

tf

P

A

V B ( x E B ) ) A V B ( A E B))

(8)

by replacing ‘ P by such a formula y that: A does not appear in y; ;quantification in y is restricted to elements; the variables appearing in cp different from ‘ x ’ and not bound therein are conjunctively restricted to elements. For example, a suitably restricted replacement for ‘ P arising from

‘p is stratified

‘ ( A w ( w= W ) A

is

( x E Y V x E 2 ) )’

( V B ( y B )A V B ( z B ) A A w ( V B ( W B ) + W = W ) A

(XEyVXEZ))’.

The elementhood axiom schema does not preclude the elementhood of comprehensive sets. A universal set is defined which turns out to be a member ofitself. One consequence of this is that the hereditary property of a subset of an element being an element does not hold. Although the present axioms are finite in number some of them do involve schematic expressions. Among these of particular interest is 2.5.3 which enables the set of x such that . x . . . to be defined. With a universal set U earlier defined the related subsequent useful Theorem of Classification (2.35)

..

‘(x E E x y

--f

ux -

A

x

EU)’

(9)

is analogous to theorems described by Quine9 as consequences of his $29 (7). Axiom 2.5.7, which, in contrast with 2.5.3, is replaceable by axioms not involving schematic expressions helps guarantee considerable elementhood. The elementhood of the universe is not guaranteed. Indeed, as with the von Neumann-Bernays-Godel system if this were so, a contradiction would arise. Closely related to (9) is the formula ‘ ( x E Ex ux -

tf

ux - A VB(x E B))’

similar to the one which appears on page xxv of the preface. I t was formulated by Morse as an axiom of classification in his 1939 lectures 8 9

Quine, W. V., op. cit., $28. Quine, W. V., Mathematical Logic, Harvard Univ. Press, 1940, under *230, p. 171.

xxii

Foreword

at the University of California. Kelley later borrowed and put to good use this simple formula. He, in effect, accepts as an axiom each formula obtained from ‘ ( x E E x P - P A VB(x E B ) ) ’ (10) by replacing ‘ P’ by a formula. Kelley’s system, which incorporates many features of an equivalent earlier unpublished system of Morse, is very much the same in pure set theoretic content as the system at hand, although it is far from clear upon glancing at the axioms that it is. For purposes of further comparison let us say a schema is concise if and only if it can be replaced by a single formula with the same effect. This formula, of course, may have schematic expressions appearing in it. The classification schema (4), widely accepted before 1901, is made concise by ‘ VAAx(x E A t)gx) ’. I t is highly unlikely that the restrictions of Russell and Whitehead can be rendered into a schema that can be made concise. The classification schema of Zermelo-Fraenkel (5) is made concise by

‘ABVAAx(x E A t)ux - Ax

E

B ) ’.

An interesting feature of the von Neumann-Bernays-Godel system is that when translated into the present language with logic left intact the purely set-theoretic axioms are not only finite in number but devoid of schematic expressions as well. However it is unlikely that the classification metatheorem (6) can be made concise. The classification schema of Quine (7) is made concise by

‘ VAAx(x E A t)ux A VB(x E B ) )’. However it is unlikely that his elementhood schema (8) can be made concise. The classification schema (10) used by Kelley is made concise by

‘( X

E

Ex F X

gx

t)

A

VB(x E B ) )’.

Although the present system and Quine’s’ revised system may both be consistent, they are radically different, chiefly as to provisions for elementhood. 10 Kelley, J.

L., General Topology, Van Nostrand, 1955, Appendix.

Foreword

xxiii

The von Neumann-Bernays-Godel system has been shown to be equiconsistent with the Zermelo-Fraenkel system. The system used by Kelley is definitely stronger than the von Neumann-Bernays-Godel system. The present system is slightly stronger than Kelley’s. Their striking set-theoretic similarities though suggest that the former is consistent with the latter. I a m told that Alfred Tarski and later David C . Peterson have verified this relative consistency. Thus the present unified system is just as sound as the more conventional ununified system used by Kelley. For those interested, a more precise account will now be given of the similarities, unearthed by the proof of relative consistency, between the present system and that of Kelley. We shall take advantage of0.70-0.75. Let us agree here that : Pis statemental if and only if P is either a schematic expression, or a variant of ‘Axgx’) or ‘(gx+vx)’, or ‘NLJX’, or ‘ ( x E ~ ) ’ ; N is nominal if and only if N is either a variable or a variant of ‘ Ex ux’; C is generated by T if and only if C is not a subformula of T and there is such a subformula B of T that C is obtained from B either by replacing some free variable of B by some nominal formula or by schematically replacing some schematic expression of B by some subformula of T ; S is a statementary if and only if S is a string and each subformula of S is either a statemental formula or a formula generated by some substring of S; C is statementant if and only if C is a subformula of some statementary ;and finally C is nominant if and only if C is either a variable or a n expression obtained from ‘ Exy ’ by replacing ‘x’ by some variable and y ’ by some statementant expression. A statementant expression is statement-like and a nominant expression is name-like. I t turns out that if H is a statementant expression devoid of schemators, then H is a theorem in the present system if and only if it is a theorem in the translated’* system of Kelley. T. J. M. University o f Nevada Reno, Nevada 11 Novak, I . L., (I. N. Gal), AConstmtionfor Modelsof ConsistentSystm, Fundamenta Mathematica, 37, 1951, pp. 87-110. (Submitted in 1948 as a Thesis to Radcliffe College, Cambridge, Massachusetts.) Rosser,J. B., and Wang, H., Nan-standard Modelsfor Formalbgic,Journal of Symbolic Logic, 15, 1950, pp. 113-129 (Errata, p. IV). 12 It is assumed here that Kelley’s system has been translatedinto the present language with logic left intact. This translated system is, in effect, the more conventional system alluded to in the second paragraph of the preface which follows.

This Page Intentionally Left Blank

PREFACE This book provides graduate students and professional mathematicians with a formal unified treatment of logic and set theory. The formalization can be used without change to build just about any mathematical structure on some suitable foundation of definitions and axioms. I n addition to most of the topics considered standard fare for set theory several special ones are treated. I t is hoped the book will be found useful as a text for a substantial one-semester course in set theory and that the student will find continuing use for the formal and highly flexible language. The first and more fundamental part of Chapter 0 terminates with a detailed account of our rules of inference. Here the lack of distinction between formulas and terms both unifies and simplifies the formalization. O u r axioms reflect this unity and, in keeping with the Remark preceding 2.33, each theorem of logic is an immediate consequence of a corresponding systematically verifiable theorem of set theory. Nevertheless without changing Chapter 0 in any way we could equally well use more conventional axioms which would preserve the usual sharp distinction between logic and set theory. The more conventional system we have in mind differs but little from the present one in the separated worlds of logic and set theory. I t is somewhat more concise axiomatically. I t has ‘ Ex u-x ’ as an additional set-theoretic primitive form, and in harmony with Theorem 2.35 it uses

‘ ( ( x E Exux)++ (U -X A ~ ~ ( x E z J ) ) ) ’ as an axiom of classification. I t also fails quite naturally in our view to answer some of the simplest questions about the interplay of logic and set theory. The last and less fundamental part of Chapter 0 is dominated by our XXV

xxvi

Preface

Theory of Notation. Many notations in common use in present day mathematics are automatically preserved. Among these are and

‘(x+y-z+w)’

‘ Ix + y - 2 + wI ’,

but not among these are ‘ IxytI ’ and ‘ lxlylzl’. We abandon the classical functional notation If(.) ’ since its use would lead to almost instant technical disaster. Mindful of such danger von Neumann introduced the technically sound notation ‘ [f x ] ’ which could well be used as an alternate to our shorter notation ‘.fx’. More specifically no harm would be done by adding

‘ “f’X I

= .fx)’

to our list of definitions. O n the other hand, if

‘ (f( x ) = . f x ) ’ were added the resulting system would perforce be inconsistent. Our Theory of Notation is followed by a short section on demonstrations, and Chapter 0 is then concluded with a section on chains. Taken together these last two sections of Chapter 0 are independent of the Theory of Notation and make quite explicit the notion of formula and the concept of theorem. Because of the importance we attach to definitions we formulate in the Appendix the rules we follow in making them. Earlier, S. Lehiewski worked painstakingly along these lines. We shall employ the terminology ‘ point’ and ‘set’ instead of the more usual terminology ‘set’ and ‘class’. We feel justified in this since to us a point is a set capable of belonging to a set. We think of a set which is not a point as very large indeed. Many problems which appear to be solvable by definitional induction may, because of the sheer size of the sets involved, not yield to ordinary definition by induction. I n this connection the more general principle 2.101 may be of real use. Specifically we use 2.101 to advantage in proving 2.183, which is a rather natural but far reaching direct extension theorem. I n 2.1 15 we formulate our very powerful Maximal Principle which like that of Hausdorff does not limit the competition to points. An easy

Preface

xxvii

consequence of 2.1 15 is 2.1 18 of which Hausdorffs Maximal Principle 2.11 9 is a special case. That 2.118 is not an easy consequence of 2.119 is, we feel, brought out by 2.120. The difficulty here arises from the possibility that no point is maximal. For purposes of further comparison let us agree that Kuratowski’s Lemma and Zorn’s Lemma are, respectively, Theorems 25(d) and 25(e) given by J. L. Kelley on page 33 of his General Topology, Van Nostrand, Princeton, New Jersey, 1955. From 2.118 which has no premise we learn that the conclusion in Kuratowski’s Lemma is essentially independent of the premise. In 2.121 and 2.123 we have useful inductive variants of Zorn’s Lemma. There is indeed a connection between Zorn’s Lemma and our 2.122 in that, roughly speaking, the conclusions are the same but the premise of the former implies that of the latter. We feel that the entitled theorems of Chapter 2 capture, short of inconsistency, the intuitive simplicity of Frege’s beautiful, but inconsistent system . I am grateful to students and colleagues for comments and advice. I am doubly grateful to those students who, down through the years, have found a treatment akin to this both interesting and comprehensible. The axioms for logic, which are easy to work with, were suggested by Alfred Tarski. Also due to him, in collaboration with Knaster, is the approach to Theorem 2.149 and the use of 2.149 in checking the CantorBernstein Theorem 2.154. Beyond this I have profited greatly from many most illuminating conversations with Tarski about the fundamentals of mathematics. I have received considerable help from David C. Peterson in preparing the final manuscript for publication. I owe him a special debt for valuable detailed criticisms and suggestions. I am grateful for support given by the Miller Institute. June, 1965 Orinda, Calzfornia

A. P. M.

This Page Intentionally Left Blank

CONTENTS FOREWORDvii

PREFACExxv

0. Language and Inference 1 Introduction 1 Replacement 1 Expressions 2 Rudiments 3 Schematic Replacement 6 Orienting Definitions 6 Free Variables and Formulas 7 Indicial and Accepted Variables 10 Rules of Inference ; Theorems 12 Initiation 12 Detachment 13 Substitution 13 Schematic Substitution 13 Indicial Substitution 13 Universalization 13 Theory of Notation 15 Demonstrations 27 Chains 29

1. Logic 33 Definitional Axioms for Logic 33 Axioms of Definition for Logic 34 Axioms for Logic 34 xxix

xxx

Contents

2. Set Theory 41 Preliminaries 41 Orienting Definitions 41 Logical Definitional Axioms for Set Theory 43 Set-Theoretic Definitional Axioms for Set Theory 43 Axiom of Definition for Set Theory 43 Axioms for Set Theory 43 The Theorem of Extent 45 Some Aspects of Equality 49 Classification 5 1 The Theorem of Classification 52 The Role of Replacement 53 The Theorem of Replacement 54 The Theorem of Heredity 55 The Theorem of Subsets 55 The Theorem of Amalgamation 56 The Theorem of Unions 57 Singletons 57 Ordered Pairs 59 The Ordered Pair Theorems 63 Substitution 63 Unicity 66 The Theorem of Unicity 67 Relations 67 Functions 71 Ordinals 73 Definition by Induction 76 The General Induction Theorem 78 The Ordinary Induction Theorems 79 Choice 79 The Theorem of Choice 81 Maximality 8 1 Maximal Principle 83 Hausdorff’s Maximal Principle 85 The Inductive Principle of Inclusion 87 Well Ordering 88 The Well Ordering Theorems 89

Contents

Natural Numbers 90 Sequences 91 Reiteration 93 Set Functions and Fixed Points 94 The Theorem of Bipartition 98 Equinumerosity 9% The Cantor-Bernstein Theorem 99 Cardinals 100 Cardinality 101 The Theorems of Cardinality 102 Cantor’s Power Theorem 104 Cardinal Arithmetic 105 Direct Extensions 106 Families of Sets 107 Tuples 110

A. The Construction of Definitions 113 The Structure of Basic Forms 1 13 The Structure of Definitions 1 15 Adherence and Translatability 1 17

INDEXOF CONSTANTS 121

GENERAL INDEX 125

This Page Intentionally Left Blank

CHAPTER 0

LANGUAGE A N D INFERENCE INTRODUCTION A mark is a more or less connected inscription. Among our marks are the Latin letters, the Greek letters, and the ten Arabic numerals. We think of a subscript, or a superscript which is not a quotation mark, as touching any inscription immediately to the left of it. Underlining is thought of as touching any inscription immediately above it. If one nonitalicized Latin letter is printed close beside another as in a word then they are thought of as touching. In this connection the ten Arabic numerals are to be thought of as nonitalicized Latin letters. For our present purposes we agree that c is a symbol if and only if c is a mark which is not a quotation mark. An expression is a linear array of symbols. As will be seen, quotation marks play a central role in this chapter. We do not include them among our symbols since this would quickly lead us by way of Agreement 0.9 into a contradiction. The possibility of such a contradiction would arise primarily from the inclusion of quotation marks among our symbols rather than imagined technical defects in 0.9. To discuss an object we must employ a name for it and not the object itself. We agree here that a name for an expression is formed by placing the expression between single quotation marks. Replacement.

If A is the expression ‘ ( x +y

+x)’,

then: if in A we replace ‘ x ’ by ‘ 1 ’ we obtain ‘(1 + y + 1)’; ifin A we replace ‘r’ by ‘ x ’ we obtain A ; ifin A we replace ‘y’ by ‘ x ’ we obtain

‘( x + x

1

+ x ) ’;

0. Language and Inference

2

if in A we replace ‘ x ’ by ‘ t ’ we obtain ‘(t+y+t)’;

if in A we replace ‘r’ by ‘ t ’ we obtain A; if in A we replace ‘ x ’ by ‘r’ and ‘ y ’ by ‘s’ we obtain ‘ (r s + r ) ’;

+

and ifin A we replace ‘ x ’ by ‘ y ’ and ‘ y ’ by ‘ x ’ we obtain

‘( y +

If x is

+y)

’.

‘ ( x +y + x ) ’

and if in x we replace ‘ x ’ by x we obtain

‘( ( x + y

+ x ) +y + ( x +y + x ) ) ’ .

Expressions. The inscription ‘ ma’ is a two symbol inscription in which precisely one symbol appears and that symbol appears precisely twice. The inscription ‘ ap’ is a two symbol inscription in which precisely two symbols appear and each of these appears precisely once. ‘wh’ is a two symbol expression and not a symbol whereas ‘wh ’ is a symbol. Among our symbols are : ‘+’, ‘*’, ‘:’, ‘...’, a , ‘p’, ‘9’’‘,’, ‘.’, ‘264’’ ‘98.64’’ ‘38A’, ‘ X I ’ , ‘XS”, ‘~12’.

Also among our symbols are wordlike nonitalic inscriptions such as: ‘sb’,

‘psb’,

‘inf’,

‘sup’.

If C is the expression obtained from ‘ (ap)’ by replacing ‘ a by A and ‘p’ by B then: ifAis ‘ x ’ and B is ‘ y ’ t h e n c i s ‘ ( x y ) ’ ; if Ais ‘x’ and B is

‘y’thenCis‘(xy)’;ifAis‘x’andBis ‘y’thenCis‘(xy)’;ifAis‘34’ and Bis‘27’ thenCisC(3427)’andnot‘(3427)’;ifAis‘sin’andBis ‘ cos ’ then C is ‘ (sin cos) ’ and not (sincos) ’ ; and if A is ‘ x ’ and B is ‘2 ’ then C is ‘ (x 2) ’. If C is the expression obtained from ‘ a p ’ by replacing ‘ a by A and ‘ p ’ by B then: ifA is ‘w h’ and Bis ‘ a t ’ then Cis ‘w h a t’; ifAis ‘up’ and B is ‘pa’ then C is the four symbol expression ‘ uppa’; if A is ‘wh’ and B is ‘ at ’ then C is the two symbol expression ‘wh at ’ ; if A is ‘ wh’ and B is ‘ a t ’ then C is the four symbol expression ‘ w h a t ’ ; if A is ‘27’

Introduction

3

and B is ‘682’ then C is the two symbol expression ‘27 682’; and if A is ‘x” and B is ‘y2’then C is the two symbol expression ‘x’ y2’. Rudiments. Our definor is ‘ = ’. Our punctuator is ‘ 1’.

Unlike our definor, which will appear frequently, our punctuator will never appear in the mathematical language we are trying to describe. Instead it will be used, in the final section ofthis chapter, to facilitate the analysis of expressions in which it does not appear. Our schemators are :

Inference starts with definitions and axioms. Each definition and each axiom will be an expression explicitly described or explicitly introduced by an appropriate marginal label. The scope of such a marginal label will end just before the next heading, aside, or marginal notation. I n addition we have so constructed the definitions themselves that no definition can be an initial segment of a different definition. We shall now explain the precautions we have taken to achieve this somewhat limited goal. We agree S isframed if and only if S is an expression in which ‘ I’ does not appear. We agree S isformative if and only if S is a framed expression in which ‘ = ’ does not appear. We agree that: Sisparenthetic if and only ifSis ‘ ( ) ’ or Scan be obtained from ‘ ( x ) ’ by replacing ‘ x ’ by an expression in which no parenthesis appears; S evolves T i f and only if T can be obtained from S by replacing a symbol which is not a parenthesis by a parenthetic expression; S is parenthetical if and only if S is a framed expression which can be built by successive evolvment from some expression in which no parenthesis appears. Thus if A and B are parenthetical expressions and C is obtained from A by replacing a symbol, which is not a parenthesis, by B, then C is parenthetical. We have so constructed our definitions that if D is one of them then D can be obtained from ‘ ( x = y) ’ by replacing ‘y’ by a parenthetical expression and ‘ x ’ by a formative expression.

0. Language and Inference

4

As is well known, parenthetical expressions have a straightforward arithmetical characterization. T o ‘ ( ’ is assigned the value 1 ; to each symbol which is not a parenthesis is assigned the value 0; to ‘ ) ’ is assigned the value - 1. Now if S is any framed expression, then : S is parenthetical if and only if the total value of S is 0 and that of each initial segment is non-negative. Among the parenthetical expressions are: ‘xyz’,

‘x(y

-+ x ) ( a

--+ b ) t = 2, ‘ ( x -+ ( y -+ 2))’.

We agree that c i s j x e d by D if and only if D is a definition that can be obtained from ‘ ( x = y) ’ by replacing ‘y ’ by a parenthetical expression in which c does not occur and ‘ x ’ by a formative expression in which c does occur. We agree that c is a constant if and only if c is ‘ = ’, or c is or c is a schemator, or c is a symbol fixed by some definition. Definitions 0.0 inform us that parentheses, the implicator ‘ -+’, the universal quantifier ‘A’, and the semicolon are among our constants; and Definitions 2.0 inform us that the membership sign ‘ E ’ and the Zermelo Selector ‘mel’ are among our constants. We agree that CL is a variable if and only if a is a symbol which is not a constant. The light face italic Latin letters together with the superscripted and subscripted symbols derived therefrom are variables. We agree that D lifts A if and only if A is a formative expression and D is a definition which can be obtained from ‘ ( x = y) ’ by replacing ‘x’ by A and ‘tj’ by a parenthetical expression. We agree that D raises A if and only if A is a formative expression and D is a definition which can be obtained from ‘ ( x ~ y )by’ replacing L x ’ by A and ‘y’ by a parenthetical expression different from A . Thus our definition

‘B’,

‘ ((P/I4 ) = -(P

+

4))

’

both lifts and raises ‘ (p A q ) ’. Our definition

‘ ( ( x -+ x ’ ) = ( x -+ x ‘ ) ) ’ lifts but does not raise ‘ ( x --f x ’ ) ’. We agree that A is a dejiniendum if and only if some definition lifts A .

5

Introduction Thus from our definition

‘ (0 3 Axx) ’

we learn that ‘ 0 ’ is both a definiendum and a constant. From our definition ‘ ( x = x ) ’ we learn that ‘ x ’ is a definiendum. We agree that B is a variant of A if and only if B can be obtained from A by replacing variables by variables and conversely A can be obtained from B by replacing variables by variables. We agree that A and B are diverse if and only if A and B are expressions and B is not a variant of A . We agree that Cis a form if and only if C is a variant either of‘ ( x = y ) ’ or of some definiendum. From our definition

‘ ( ( P A q ) = -(P -4)) ’ we learn that ‘ (p A q ) ’ is a definiendum and that ‘ ( x A y) ’ is However, ‘ ( x A x ) ’ is not a form. From our definitions ‘ ( V Xux e -AX -UX) - ’ +

a form.

and

‘ (VX E x’ vx vx) ’ - e v x ; ( x E x‘) we learn that ’ Vy u y ’ and ‘ V t E y v t ’ are forms. However, ‘ V x vx’ is not a form. Forms are to be read as a whole. The individual constants are usually incidental. The expression ‘ (p + q ) ’ has nothing to do with limits and the expression ‘ (yx + A as x + a ) ’

has nothing to do with implication. We agree that C is primitive if and only if either C is a schemator, or C is ‘ = ’, or C is ‘ ( x _= y) ’, or C is such a definiendum that no definition raises a variant of C. Our primitive constants consist of our definor and our schemators. We agree that S is primal if and only if S is one of the expressions : ‘(XEY)’,

cx’, ‘XI’, CXI,’,

-

‘UX’) ‘U’XX”, -

‘vx’, (wx’, ‘v’x“’, ‘W’X”’, -

cUIXXIXn’,

-

rVIxXlXW~,

-

etc.

cWnXXIXW5,

-

6

0. Language and Inference

We agree S is schematic if and only if S can be obtained by replacing variables by variables in some primal expression in which a schemator appears. In an informal way we sometimes think ux if and only if x has the property y . Alternatively, in an informal way we sometimes think that is the set corresponding to x under u . In most given instances one ux thought is more reasonable than the other. We agree that A is simple if and only if A is an expression in which no variable appears more than once. Schematic Replacement. We agree that B is obtained from A by schematically replacing S by R if and only i f S is a schematic expression, and there is an expression Q in which the first symbol in S does not occur and a symbol q such that A is obtained from Q by replacing q by S and B is obtained from Q by replacing q by R.

The only reason for making the first two definitions of 0.0 below is to establish certain constants. The only reason for making the remainder of the definitions is to lift certain important forms. 0.0

.0 .1 .2

.3

ORIENTING DEFINITIONS. (( + x ) E X ) (A ; x = x) ((X'X')

=(x+x'))

(Ax u x = Ax UX)

.4 (x = x )

ux) .5 (ux - =.6 ( y x = vx) . 7 ( E X = wx)

.8

(x' EE x')

.9 (y'xx' = u'xx') = v'xx') .10 (v'xx' .11 (w'xx' = w'xx') .12 (x" = x") .13 (y"xx'x" = U"XX' X") .14 (y"'x' = VWXX'Xrn) -

Free Variables and Formulas

7

.15 ( ~ " x x ' x "= ~"xx'x") .16 (x"' = x'") .17 (_u "xx'x"x =-u Mxx'x''x ") etc. 111

Through rules and agreements we shall try to make clear when a given variable isfree, indicial, or accepted in an expression. * We shall also try to make clear just what expressions are formulas, and we shall give rules of inference for establishing theorems. Theorems, of course, are of particular interest to us. Our rules of inference enable us, step by step, to use theorems already known to us to discover new theorems. Formalization describes with care an explicit process for arriving at theorems. Our rules are to be taken for granted although some of them can be derived from others. Our rules are akin to, but different from, axioms and theorems. Our agreements are akin to, but different from, definitions. Mathematics is made up of statements about sets. Metamathematics is made up of statements about expressions. Axioms, theorems, and definitions belong to mathematics. Rules and agreements belong to metamathematics. To give a rough idea of the roles played by schematic expressions, free variables, indicial variables, and accepted variables, we say that in a theorem a free variable is replaceable by a wide variety of formulas, a schematic expression is replaceable by a still wider variety of formulas, and an indicial variable, such as an index of summation or a dummy variable of integration, is replaceable by accepted variables.

FREE VARIABLES AND FORMULAS 0.1

RULE.

If a is free in A then a is a variable and A is an expression.

0.2 R U L E . A variable is free in a form if and only if it occurs therein less than twice.

0.3 A G R E E M E N T . in A .

A is a formula if and only if some variable is free

Roughly speaking, a variable is free in a formula if and only if every occurrence is a free occurrence.

8

0. Language and Inference

0.4 RULE. If A is a formula, Cis a formula, B is different from A and is obtained from A either by replacing some free variable of A by C or by schematically replacing some schematic expression by C, then a variable is free in B if and only if it is free in both A and C. The remainder of this section and the last two sections of this chapter, 0.70-0.85, shed light on the precise structure of formulas and the explicit nature of theorems. However, the reader may omit all of this material except 0.9, according to his pleasure, since the rest of this chapter, which includes the mechanics of proof, is entirely independent. 0.5 AGREEMENT. variable.

A is strict if and only if A is a formula and not a

0.6 AGREEMENT. F is fundamental if and only i f F is either a schematic form, or a strict formula devoid of schemators from which some form can be obtained by replacing variables by schematic expressions. Of the eight expressions

‘ (x

--f

t ) ’,

‘Ax yy’,

‘u’xy’, -

and

‘Ayx’,

‘ ( x -+ x) ’,

‘x’,

‘Axx’,

‘Ax ux’,

the first three are fundamental formulas and the last five are formulas which are not fundamental.

0.7 AGREEMENT. a is an introductor if and only if a is a constant which is the initial symbol of some definiendum. 0.8 AGREEMENT. a definiendum.

a is a noun if and only if a is both a constant and

0.9 AGREEMENT. (AB) is the expression obtained from ‘xy’ by replacing ‘x’ by A and ‘y’ by B. I n other words, (AB)is the concatenation of A and B. For example, (‘sin’ ‘x’) is ‘sin x ’ . 0.10 AGREEMENT. A is aprefix if and only if A is either an introductor or a n expression of the kind (a B)where a is a n introductor and B is an expression devoid of introductors. 0.11 AGREEMENT. A is a su@x if and only if A is either a noun or an expression of the kind ( a B ) where a is an introductor and B is an expression.

Free Variables and Formulas

0.12 AGREEMENT. fundamental. 0.13 RULE. introductor.

9

C is reducible if and only if C is strict and not

A formula is strict if and only if its initial symbol is an

0.14 RULE. A formula is fundamental if and only if it is either a simple prefix or an expression of the kind (Act) where A is a simple prefix and ct is the initial symbol of A . 0.15 RULE. I f F is a strict formula devoid of schemators, and A is a form obtained from F by replacing variables by schematic expressions, then: F is a simple formula, every variable which appears in A also appears in F, a is free in F if and only if ci is free in A , and A can be obtained from F by replacing variables which do not appear in A by schematic expressions. 0.16 RULE. If C is a formula, Q is an expression, a is a variable which appears precisely once in Q, M is a formula, and C is obtained from Q by replacing a by M , then: .O if Q is a formula and M is a strict formula, then ct is free in Q; .1 if Q is fundamental and Cis reducible, then either ci is free in Q or M is free in Q ; .2 if M is a variable then Q is a formula; and .3 if A is a prefix, B is a n expression, whose initial symbol is a, and Q is ( A B ) ,then Q is a formula.

Thus ‘A(x -+ x)y’

is not a formula since otherwise we could learn that ‘ t’ is both free and not free in ‘At,’.

0.17

RULE.

No formula is a n initial segment of a different formula.

0.18 RULE. If A is a prefix, B is a suffix, and (AB) is a reducible formula, then some initial segment of B is a formula. Remark. I n order that the foregoing rules and agreements unite in harmony, we must in making definitions take some technical precautions such as, for example, those outlined in A.Q-A.8 of the Appendix.

10

0. Language and Inference

INDICIAL AND ACCEPTED VARIABLES 0.19 RULE. If a is indicial in A, then a is a variable and A is a formula; if a is accepted in A , then a is a variable and A is a formula. 0.20 RULE. A variable is indicial in a form if and only if it occurs therein more than once. 0.21 RULE. A variable is accepted in a form if and only if it occurs therein less than twice. Thus a variable is accepted in a form, as opposed to a formula, if and only if the variable is free in the form.

0.22 RULE. If A , B, and C are formulas with A different from B and B different from C, and ifB can be obtained from A by replacing a free and accepted variable of A by C, then : a is accepted in B if and only if a is accepted in A , and a is indicial in B if and only if a is indicial in A and does not appear in C. 0.23 RULE. If A , B, and C are formulas with A different from B and B different from C, S is a schematic expression, some variable in S is indicial in A , and if B is obtained from A by schematically replacing S by C, then: a is indicial in B if and only if a is indicial in A , and a is accepted in B if and only if a is accepted in A and does not appear in C. If some variable is indicial in a form then it is quite reasonable to assign special significance to the posi’tions occupied by the free variables and the schematic expressions, and to the positions outside of schematic expressions occupied by individual variables. For example, in ‘Vx E A ux’

we might say ‘ x ’ in its first appearance is in an indicial position, ‘A’ is in a free position, and ‘ u x ’ is in a position subservient to the indicial. Indicia1 and accepted variables can be looked at, less mechanically, in another way. Suppose F is a form which is neither a schematic form nor a variable. Variables free in F are of course accepted in F and all other variables are indicial in F. Now i f F is obtained from F by simultaneously replacing free variables which appear in F by formulas and schematically replacing schematic expressions which appear in F by

Indicia1 and Accepted Variables

11

formulas then : a variable is indicial in F if and only if it is indicial in F and does not appear in any of the formulas replacing free variables, and a variable is accepted in F‘ if and only if it is accepted in F and does not appear in any of the formulas schematically replacing schematic expressions. Remarks. A variable which does not occur in a formula is free, accepted, but not indicial therein. I n the expression ‘Ax(x

--f

y) ’

‘ x ’ is indicial and not free, whereas ‘y’ is free but neither indicial nor accepted. Because ‘ x ’ is free in ‘Ay uy’ - and in ‘ (x E t ) ’ it follows that ‘ x ’ is free in ‘Ay(x E t ) ’.

I n the expression ‘AxAyy’, ‘ x ’ is indical and not free while ‘y’ is neither free nor indicial nor accepted. I n the expressions ‘AyAyy’,

‘ V y ~ A x x y ’ , and

‘Vy~xy’,

‘y’ is indicial and ‘ x ’ is accepted. In the expression ‘Vx E x x ’ , ‘ x ’ is neither free nor indicial nor accepted. In the expression

‘ (Axx + Axx) ’ ‘ x ’ is accepted but neither free nor indicial.

If A is any formula exhibited previously, then a variable is free in A if and only if in A it never immediately follows ‘ A ’ or ‘ V’. A variable b is indicial in A provided A is obtained from ‘Axz’ or ‘ Vxz’ or ‘ Vx E y z ’ by replacing ‘ x ’ by b, ‘y’ by a formula in which b does not appear, and ‘ z ’ by a formula. Furthermore, if A is obtained from ‘Axz’ or ‘ V x z ’ or ‘ V x E y z ’ by replacing ‘ x ’ by a variable a, ‘y’ by a formula, and ‘ z ’ by a formula C, then : a variable is accepted in A if and only if it differs from a and does not appear in C. O u r Rule of Inference 0.28 is, of course, to be understood in the light of 0.19-0.23. There is a natural temptation to simplify 0.28, by abandoning acceptedness, using a simpler notion of indiciality, and, in 0.28, replacing the words ‘ is accepted ’ by ‘ does not appear ’. T o assess the consequences of this proposed simplification let us adopt the unordered summation notation

‘ C x E A ux’. -

0. Language and Inference

12

I t is then natural to expect that

(EnE 4 n = 6 = E m E 4 m).

Also it seems clear that ‘ E x E y x’

is a formula. Inasmuch as

‘ (Y

AxY) ’ is a formula in which ‘y’ is free it seems inescapable that -+

‘ ( x -+ A x x ) ’ is a formula, but not, we hope, a theorem. Thus, since ‘y’ is free in

‘ Z x E y x’

we feel compelled to admit that

‘Ex Ex

x’

is also a formula. If 0.28 were simplified in the way we momentarily have in mind, then we would be unable to interpret the formula

‘Ex E x x ’ . But with 0.28 and 0.19-0.23, as they stand, at our disposal we notice that

(CYExY=EYExY) and use 0.28 to infer that

( E x E x x = Ey E xy).

RULES OF INFERENCE; THEOREMS 0.24 INITIATION. Every formula asserted to be a definition or an axiom is a theorem.

It should not be assumed that a formula is a definition just because it looks like one. Although always a theorem, a formula variant of a definition is seldom a definition. In particular the formula

‘ (0 = Ayy) ’, which is a variant of Definition 1.0.3., is not a definition.

Rules of Inference; Theorems

13

Definitions are more than mere shorthand devices. Since we accept formulas of this sort as theorems we should use care in making them. Presumably only by mistake would someone fashion a n axiom which is not a formula.

0.25 DETACHMENT. If a theorem is obtained from ‘ ( p + q) ’ by replacing ‘ p ’ by a theorem and ‘q’ by a formula T, then Tis a theorem. 0.26 SUBSTITUTION. If T is a theorem in which b is free and A is such a formula that each variable in it is free in T, then the expression obtained from T by replacing b by A is also a theorem. 0.27 SCHEMATIC SUBSTITUTION. If T is a theorem, S is a schematic expression, and A is such a formula that each variable in it is either free in T o r occurs explicitly in S, and T is a formula obtained from T by schematically replacing S by A , then T‘is a theorem.

0.28 I NDlClAL SUBSTITUTION. Ifq is free in Q, Tis a theorem obtained from Q by replacing q by a formula A in which CY is indicial, B is obtained from A by replacing cc by a variable which is accepted in A , and finally T is obtained from Q by replacing q by B, then T is a theorem. 0.29

UNIVERSALIZATION. If T is a formula obtained from

‘Axy’ by replacing ‘ x ’ by a variable and ‘y’by a theorem, then T is a

theorem.

We shall eventually categorically describe theorems in Rule 0.75. This rule is independent of the intervening Theory of Notation. Examples. By detachment we learn that if

‘ ( A x ( x +x )

+ ( x +x ) ) ’

is a theorem and if ‘Ax(% + x ) ’

is a theorem, then ‘ ( x -+ x ) ’ is a theorem. By substitution we learn that if is a theorem then

‘((Y+t)

+Ax(y+t))’

‘((Y+Y)

+AX(Y+Y))’

14

0. Language and Inference

is a theorem. However, replacing ‘ t ’ or ‘y’ by ‘ x ’ is not allowed by substitution. By schematic substitution we learn that if

‘ (Ax ux -+ yx) ’ is a theorem then

‘ (Ax(x -+ x )

-+ (x -+ x))

’

is also a theorem. Note, however, that from the supposition that ‘&Y

+Y)’

is a theorem we cannot employ either substitution or schematic substitution to infer that

‘ (Ax(x -+ x)

( x -+ x)) ’

-+

is a theorem. By indicia1 substitution we learn that if

‘ (VX E y x -+ v x E y x ) ’, and

‘ (Ax -ux + UX) ’, ‘ (Ax(x

-+ x) -+ ( x

-+ x ) ) ’

are theorems, then L ( v xE y x

and

-+

vy E y y ) ’ ,

‘ @Y UY + y). ’, ‘ (AYY(Y -+Y)

+

(x

+

4)’

are theorems. However, from the assumption that

‘ (AY UY

+

3-4’

is a theorem we cannot directly employ schematic substitution to learn that ‘(AY(Y +Y) -+ ( x - + x ) ) ’ is a theorem. This is because ‘uy - ’ and ‘ yx’ are not the same.

15

Theory of Notation From universalization it follows that if ‘ ( x ‘Ax(x

is a theorem.

--f

--f

x ) ’ is a theorem then

x) ’

We henceforth try to bear these foregoing rules in mind.

THEORY OF NOTATION The reader may find some of our notations different from those to which he has become accustomed. We find ourselves a little reluctant to introduce nonlinear notations and somewhat more reluctant to introduce notations which make it very easy to reach a contradiction. As we have indicated before, reluctance of the latter sort caused us to use the functional notation ‘.f x ’ in place of the customary, and incidentally more cumbersome, notation ‘f(x) ’. Although most of the formulas we use can be deciphered intuitively, we nevertheless suggest a somewhat cursory perusal of and occasional reference to this section. We formulate herein a general and flexible theory of notation which permits useful simplification of a vast number of complicated expressions and justifies many of the informal conventions of present-day mathematics. Attention paid to the examples should make considerably easier the reader’s understanding of the rudiments of the theory. An occasional reader may, in his mind’s eye, prefer to alter somewhat agreements given in the spirit of 0.30, or even recast them as rules. We shall make no real use of 0.50-0.64 until we reach 2.57.

0.30 AGREEMENTS. .2 O u r symbol of type 2 is :

‘ -+’. .4 Our symbol of type 4 is: ‘t-t’.

.5

O u r symbols of type 5 are : ‘A’,

‘V’.

0. Language and Inference

16

Our symbols of type 6 are:

.6

13’,

LE’,

‘ c 3 ,

<=)

,

‘#’,

‘wellorders’,

‘ orders ’, ‘eq ’, ‘topologizes’, ‘ < ’, ‘ > ’, ‘ < ’, ‘ ’, ‘ metrizes ’, ‘simplymetrizes ’, ‘measures ’.

Our symbol of type 7 is:

.7

‘ 1

I .

Our symbols of type 8 are :

.8

,.

‘ 9 i 9

C Y

.9 Our symbols of type 9 are :

‘ @’, ‘ +’, ‘ ‘ 0,’.

‘

0 2 ’ 9

‘0 3 ’ ’

‘ 04)’ ‘ 0 5 ’ 9 ‘ 0

6 ’ ~

. 1 1 Our symbols of type 11 are: ‘-’, ‘ 03’,‘ 06). .13 Our symbol of type 13is:

‘/’. , I 5 Our symbols of type 15 are : ‘ n ’, ‘ u ’, ‘:’ ‘i’, ‘.’, ‘ ol’, ‘ 02’,‘03’, ‘04’,‘ 0 5 ’ ,‘06’,‘O,’, ‘.’, ‘*’, l-l-.

‘o’,

. 1 7 Our symbol of type 17 is : ‘

5

a .

.19 Our symbol of type 19 is :

‘ #’. 0.31

AGREEMENTS.

.O A symbol is a binarian if and only if it is a symbol of some type. 1 Asymbol is a binariate ifand only if it is either ‘ x ’ or one of the primed symbols derived therefrom.

.

is a nexw if and only if c is a n expression in which each symbol is a binarian.

0.32 AGREEMENT.

In 0.33 we use 0.9.

c

Theory of Notation

17

0.33 AGREEMENT. A is aparade if and only ifA is such an expression in which some binarian appears that A can be obtained from one of the expressions

' ( X X ' ) ), ' ( X X ' X " )

),

' (X#'X"X")

...

),

by replacing each biniariate a which is different from ' x ' by some expression which either is a itself or is of the kind (ca)where c is a nexus.

A not unusual sort 'of parade is

' ( X c X'

c X")

,.

A less common sort is '(xu~'nnx"-tx"c~""3XF")~.

Our theory of notation and subsequent mathematical definitions will make possible a unique interpretation of the two parades just mentioned as well as a host of others. 0.34 AGREEMENT. A is of power n if and only if A is a nexus in which some symbol of type n appears and no symbol of type less than n appears.

For example, are of power 6. 0.35 D E F I N I T I O N A L SCHEMA. We accept as a definition each expression which can be obtained by replacing ' A ' by an expression of odd power in any one of the expressions:

'((X

A X' A X " ) SZ ( ( X A X ' ) A X " ) )

',

' ( ( X A X ' A X " A X m ) E ( ( X h X ' A X " ) AXm))',

etc. 0.36

.o

.1 .2

DEFINITIONS. ((x) E

X )

((XX') ((XX'X")

(X A X')) ( X A X' A X " ) )

etc.

18

0. Language and Inference

0.37 DEFINITIONAL SCHEMA. We accept as a definition each expression which can be obtained by replacing ‘ +’ and each primed symbol derived therefrom by expressions of power 2 in any one of the expressions :

etc. I n each of these expressions note well that the sixth symbol from the end is ‘ x ’ and not one of the primed symbols derived therefrom. More usual and very similar to each other are 0.38 and 0.39 below. 0.38 DEFINITIONAL SCHEMA. We accept as a definition each expression which can be obtained by replacing ‘t)’ and each primed symbol derived therefrom by expressions of power 4 in any one of the expressions :

etc.

0.39 DEFINITIONAL SCHEMA. We accept as a definition each

expression which can be obtained by replacing ‘=’ and each primed symbol derived therefrom by expressions of power 6 in any one of the expressions :

etc. 0.40 AGREEMENT. The extension of A is the expression obtained from ‘xyx’ by replacing ‘ y ’ by A . 0.41 AGREEMENT. D occurs in C betwixt A and B if and only if there are such symbols CL and fi that: A is a binariate or an expression in which no binariate appears; B is a binariate or an expression in which no binariate appears; a is a binariate provided A is not, and is a binariate provided B is not; and some segment of the extension of C can be obtained from ‘yadbz’ by replacing ‘ y ’ by a, ‘ a ’ by A, ‘ d ’ by D, ‘ b’ by B, and ‘ z’ by 8.

Theory of Notation

19

If A is the expression then in A :

0.42 A G R E E M E N T . B is a bisegment of A if and only if B is a nexus which occurs in A betwixt two binariates. 0.43 A G R E E M E N T . We agree that B is minimal in A if and only if B is a bisegment of A and no bisegment of A is of lower power than that of B.

0.44 A G R E E M E N T . We agree B is ofprime importance in A if and only if either B is a parenthesis ; or B is of even power and is minimal in A ; or B is ofodd power, is minimal in A , and, among those expressions which are minimal in A , B is the expression whose first appearance in A betwixt two binariates is deferred the longest. 0.45

AGREEMENTS. .O We agree that a is left in A if and only if a is a binariate and there are such expressions B and C that : a occurs in A betwixt B and C; B is of prime importance in A ; and C is not of prime importance in A . .1 We agree that a is right in A if and only if a is a binariate and there are such expressions B and C that: a occurs in A betwixt B and C; B is not of prime importance in -4; and C is of prime importance in A .

0.46 AGREEMENTS. .O We agree that the left enlargement of A is the expression obtained from ‘ ( x ’ by replacing ‘ x ’ by A .

0. Language and Inference

20

.1 We agree that the right enlargement of A is the expression obtained from ‘ x ) ’ by replacing ‘ x ’ by A.

Thus the left enlargement of ‘ x ’ is ‘ ( x ’ and the right enlargement of

‘y’ is ‘y) ’.

0.47 AGREEMENT. The complicate of A is the expression obtained from A by first replacing each binariate which is left in A by its left enlargement and then in this result replacing each binariate which is right in A by its right enlargement.

0.48 DEFINITIONAL SCHEMA. IfAisaparade thenweaccept as a definition the expression obtained from ‘ ( x ~ y ) ’by replacing ‘ x ’ by A and ‘y’ by the complicate of A.

From 0.39 we learn that

‘((X

C X‘ = X I 3 X ” )

( ( X c X’

=X”) A (X” 3 X ” ) ) )

’

is a definition. If A is the rather weird expression ‘(x

+ X‘X”

-+- x “

< n u x””)’

then the bisegments of A are ‘ +’, and ‘ < n u ’; ‘ +’, and the parentheses are of prime importance in A; ‘ x ” and ‘ x ” ’ are left in A ; ‘ x ” ’ and ‘x””’ are right in A; and the complicate of A is ‘+a’,

‘+a’,

‘ ( x -+ (x‘x”)

-P

(x“

< n u x””)) ’.

If A is the expression

‘ ( X u X’ n X” u x “ ) ’ then ‘ n ’ is of prime importance in A, ‘ x ’ and ‘ x ” ’ are left in A, ‘x” and ‘ x ” ’ are right in A , and the complicate of A is

‘( ( x u

x’)

n (x” u x ” ) )

’.

However, if A is the expression ‘(x

n X ’ u x” n

X I ) ’

then ‘ u ’ is of prime importance in A and the complicate of A is

‘((x n x’) u

(x”

n x ” ) ) ’.

Theory of Notation

21

If A is the expression

'(X A< then

'A<<

X' A < <

X" A <

X'" A < <

X"")'

' is of prime importance in A and the complicate of A is A<<

'((XA<X')

If A is the expression

(X"A<X")

A<<X"")'.

' ( x E x' n x " ) '

then ' E' is of prime importance in A and the complicate of A is

'( X

n x'!) ) '.

E (x'

On the other hand, if A is the expression

'( X then

'A'

E X'

'

A X")

is of prime importance in A and the complicate of A is

'( ( X

E

X ' ) A X")

'.

If A is the expression

' ( x --f x'

-+ X " l v x"") '

= X" E X m

then the complicate of A is

' ( x + (X' If A is the expression

+ (X"" v x"")) '.

= x" E x " )

' ( x + x'

+ x") '

*

x"

*

x")

then the complicate of A is

' ( x + (x'

and we know that

' ( ( x + x'

*

x"

+x") '

+ x " ) = ( x + (#' ' x") + x " ) ) '

is among our definitions. If A is the expression

' ( x = x'

E x"x " 3

XI'"

u g " p )'

then the complicate of A is

' ( x = x'

E

(X"X")

3

(X""

u x""x"")) '.

22

0. Language and Inference If A is the expression ‘(x

u u u x’)’

then the complicate of A is A . A convenient negating device is : 0.49 DEFINITIONAL SCHEMA. We accept as a definition each expression which can be obtained from

‘ ( ( X *E 9) (x

E 9 + A ZZ)) ’

by replacing ‘E’by a nexus different from

‘m’.

As we have said before, we shall make no real use of 0.50-0.64 until we reach 2.57. 0.50 AGREEMENTS. .O Our expressions of class 0 are:

‘E’,

.1

‘One’,

‘The’.

Our expressions of class 1 are: ‘A’, ‘A’, ‘far R’, ‘large’, ‘small’, ‘big’, ‘alm # Mcp , ‘alm q’, ‘Alm ‘p’, ‘A1 cpB.

.2

Our expressions of class 2 are: ‘V’,

.3

‘Ad’,

‘C’.

Our expressions of class 3 are: ‘sup’,

‘inf’,

‘ad’,

‘osc’.

.4 Our expressions of class 4 are those expressions which are of either class 0 or class 1 or class 2 or class 3. .5 Our expression ofclass 5 is:

‘1’.

.6

Our expression of class 6 is : ‘Al’.

0.51 AGREEMENT. A symbol is a notarian if and only if it is the initial symbol of some expression of some class.

Theory of Notation

23

0.52 A G R E E M E N T . A is a march if and only if some parade in which no binariate is adjacent to a binariate can be obtained from ‘ (p) ’ by replacing ‘p’ by A . Thus of the three expressions ‘xx’ EX“’,

‘XI

3x

,

and

‘x E X ’ c c x ” 3 x””

only the third is a march. I t will turn out that a march is never a formula.

0.53

AGREEMENTS. verb if and only if u is a binarian of type 2 or 4 or 6. .1 C is verbal if and only if C is an expression in which some verb appears. .2 Cis verbless if and only if C is an expression in which no verb appears. u is a

.O

0.54 A G R E E M E N T . s is a subject of A if and only if s is such a verbless expression, whose terminal symbol is a binariate, that either A is s or A can be obtained from xyz by replacing x by s, ‘y’ by a verbal nexus, and ‘ 2 ’ by an expression. Clearly an expression can have at most one subject.

0.55 AGREEMENT. C is of order n if and only if C has a subject in which precisely n binariates appear. 0.56 D E F I N I T I O N A L S C H E M A . We accept as a definition each expression which can be obtained by replacing ‘ E ’ by a n expression of class 0, ‘A’ by a n expression of class 1 , ‘ V ’ by a n expression of class 2, and ‘sup’ by an expression of class 3 in any one of the following expressions : ‘ ( E x ;_u x_v x = EX(UXAVX))’ - ‘ (Ax ; _ux _vx = Ax(0 E _ux + vx)) - ’

‘ ( V X ; -UX -VX E vX(0 E -UX A _VX)) ’ ‘ (sup x -vx = sup x ; ( x = x ) yx) ’.

We suggest that the semicolon in any form whose initial symbol is of class 4 be read “subject to the condition that”.

0.57

.o

.1

DEFl N I T I O N S . (St tx UX v X ( 2 =X A UX)) (substitute z for x in ux E st zx ux)

24

0. Language and Inference

DEFlNIT10 NAL SCHEMAS. .O We accept as a definition each expression which can be obtained by replacing ‘p’ by a march whose terminal symbol is ‘x” in

0.58

‘ (St

Zp

U’XX‘ E vXvX’(Z = (4) A U‘XX’)) ’.

.1 We accept as a definition each expression which can be obtained by replacing ‘p’ by a march whose terminal symbol is ‘x”’ in ‘ (St Zp U””’X’’

vXVX’vX”(2= (p) A U”#X’X”))

’.

etc. Thus among our theorems are :

‘ (St Z X

fJ U’XfJ ‘ (St 2 X +tJ U’XtJ I

VXvtJ(2 = ( X VXVfJ(Z

I

= (X

tJ) A U’XtJ)) ’, +fJ) A U’XtJ))’.

0.59 AGREEMENTS. .O A is a 1 stencil if and only if A can be obtained by replacing ‘ E’ by an expression of class 0, ‘V ’ by an expression of class 1 or 2 or 3, and ‘A’ by an expression of class 4 in any one of the expressions:

‘ (Ep ; qr = Ez st zp ( q A r ) )’, ‘ (Vp ; qr = V t ;st ztq st ztr) ’,

‘ (Apr 3 Ap ; (x = x ) r) ’.

.

1 A is a 2 stencil if and only if A can be obtained by replacing ‘A’ by a n expression of class 4 in any one of the expressions :

‘ (Ap ; qr = As ; ((PI A ‘ (Apr = As ; (b)r) ’.

4) r) ’,

0.60 DEFINITIONAL SCHEMAS. .O We accept as a definition each expression which can be obtained from a 1 stencil by replacing ‘p’ by a verbless march of order 2, ‘ 1 ’ by ‘ x , x”, ‘ q ’ by cu‘xx’’, and ‘ r ’ by ‘v‘xx”. -

.1 We accept as a definition each expression which can be obtained from a 1 stencil by replacing ‘p’ by a verbless march of order 3, ‘ t ’ by ‘ x , X I ,x”, ‘ q ’ by ‘ ~ “ x x ‘ x ”and ) , ‘r’ by ‘~“xx’x’’). etc.

Theory of Notation

25

0.61 DEFINITIONAL SCHEMAS. .O We accept as a definition each expression which can be obtained from a 2 stencil by replacing p by a verbal march M of order 1, ‘5’ by a subject of M , ‘ q ’ by ‘ux), and ‘ r ’ by ‘vx’. .1 We accept as a definition each expression which can be obtained from a 2 stencil by replacing p by a verbal march M of order 2, ‘s’ byasubjectofM, ‘q’by‘u’xx”,and‘r’by‘v‘xx”. etc. Thus, among our theorems are :

‘ (E x y ;u‘xy v’xy = Ez st z x ,y (fxy I

‘ (E x y y’xy s E x y ; (X I

I

’,

A

y’xy)) ’,

= X) v’x~)

‘ (E x + y ;-u’xy -v’xy = Ez st z x + y

(g’xy A v’xy)) ’, ‘ (A x + y ;u’xy v’xy 3 A z ; st z x ,y g‘xy st z x ,y v ’ x ~’,) ‘ (A x ,y ; g xy v’xy v’xy) ’, - = Az ; st z x ,y y’xy st z x ,y ‘ ( A x ~ A u B-u x = A x (; ~ E A U B)ux)’, -

‘ (A x u y E A u’xy = A x u y ; (x u y E A ) u’xy) ’, ‘ (A x u y ;-u‘xy -v‘xy = A z ; st z x ,y g‘xy st z x ,y I’x~)’, ‘ (Ax c A ; (xyz c B ) -ux = Ax ; ((x c A ) A (xyz C B ) )-ux) ’. A convenient combinatorial device is : 0.62 DEFINITIONAL SCHEMA. We accept as a definition each expression which can be obtained from

‘ ( ( Ann B ) = E x n y ( x

E

AAy

E

B))

by replacing ‘ n ’ by a verbless binarian. Remark. I n 0.30-0.48 we were primarily interested in parenthetical simplification. In 0.49-0.62 we have been primarily interested in notational uniformity as well as brevity. I n 0.63-0.64 we shall again be interested primarily only in parenthetical simplification.

0.63 DEFINITIONAL SCHEMA. We accept as a definition each expression which can be obtained from

“IPI = I(P)O’ by replacing

I

p by a march and ‘ ’ by an expression of class 5.

26

0. Language and Inference For example ‘(Ix

+ x’ +

X”I

= I ( x + x’ + x ” ) I ) ’

is among our definitions. 0.64 DEFINITIONAL SCHEMA. We accept as a definition each expression which can be obtained from

‘ (A1 CPBYY! = A1 cp(B)YUY) ’

by replacing ‘B’ by a march and ‘Al’ by an expression of class 6. I n trying to make sure that our definitions conform to the Appendix we now pick up some loose ends. 0.65 DEFINITIONAL SCHEMA. We accept as a definition each expression which can be obtained from ‘(A;x=x)’

by replacing ‘A’ by a notarian not of class 5. 0.66 DEFINITIONAL SCHEMA. We accept as a definition each expression which can be obtained from

‘(I

+XI

by replacing ‘ +’ by a binarian and 0.67

=x)’

‘ I ’ by a symbol of class 5.

DEFINITIONAL SCHEMA.

We accept as a definition each

expression which can be obtained from

‘ (Ax ux = A x ux) ’ by replacing ‘A’ by an expression of either class 0 or class 1 or class 2. 0.68 DEFINITIONAL SCHEMA. We accept as a definition each expression which can be obtained from

‘ (sup x ; _ u x-v x = s u p x ; _ ux -v x ) ’ by replacing ‘sup’ by an expression of class 3. 0.69 DEFINITIONAL SCHEMA. We accept as a definition each expression which can be obtained from

by replacing

‘ I ’ by an expression of class 5 .

27

Demonstrations

Remark. By added effort we could in the spirit of the foregoing give a much more sweeping theory of notation than the one herein given. We could, for example, so arrange things that expressions like

‘ (J”_UX . v x dx = J”

(UX

-

. -VX)

dx) ’

would automatically become theorems. Remark. We urge the reader to take for granted that c is a constant if and only if c is either our definor, or our punctuator, or a semicolon, or a schemator, or a parenthesis, or a binarian, or a notarian,* or a symbol fixed by 0.57.0, or a symbol fixed by 0.57.1, or a symbol fixed by the first formula in which it appears among those listed in the chapters which follow. I n this connection we should like to point out that no symbol is ever fixed by an expression in which ‘ = ’ does nut appear.

DEMONSTRATIONS 0.70 A G R E E M E N T . C is entailed by A and by B if and only if A , B , and C are formulas for which there are such a formula &, such a variable t, and such a schematic expression S that either: .0 B is obtained from ‘ (p + q ) ’ by replacing ‘ p ’ by A and ‘ q ’ by C; or .1 t is free in A , each variable in Q is free in A , and C is obtained from A by replacing t by Q ; or .2 each variable in Q is either free in A or occurs explicitly in S, and C is obtained from A by schematically replacing S by & ; or .3 there are such formulas A‘ and B and such variables a and /3 that t is free in Q, CL is indicia1 in A‘, /3 is accepted in A‘, A is obtained from Q by replacing t by A’, B is obtained from A’ by replacing a by 8, and C is obtained from Q by replacing t by B ; or .4 C is obtained from ‘Axy’ by replacing ‘ x ’ by t and ‘y’ by A . 0.71 A G R E E M E N T . S is a string if and only if S can be obtained from one of the expressions G X > ,

GXXI,,

<xxIxI,

)...

by replacing variables by formulas. 2 To illustrate the flexibility of our theory of notation we have included among our binarians and notarians a good many symbols seldom used in elementary set theory.

0 . Language and Inference

28

I n other words, a string is a linear arrangement or concatenation of formulas. With the help of 0.9 it can be seen that if S is a string and T is a n expression then ( S T )is a string if and only if T is a string. Also if S is a string which is not a formula then there are a unique string T and a unique formula A such that S is ( TA). I n this connection let us examine some specific expressions. If

R is ‘11x1 -+yl’, T is ‘ Ix’, and A is ‘ 1 +yI’,

I

then: because of 0.63, 0.66, and 0.69, R and A are formulas for which R is ( TA); the expression T , however, is not a string. Accordingly if

S is ‘ x I I x I -+yI’, T is ‘ x ’ , A is ‘11x1 +-y\’, T‘is A‘ is

‘xIIx’, ‘1 +yI’

and

then

S is a string which is not a formula, S is (TA),Sis ( F A ’ ) , A is a formula, A’ is a formula, T is a formula and therefore a string, but T ’ is an expression which is not even a string. Nevertheless, if S is a string which is not a formula then there are a unique formula A and a unique expression T for which S is ( AT ). 0.72 AGREEMENTS. .O S is a substring of T if and only if T is a string and S is a string which is an initial segment of T . .1 T terminates with A if and only if A is a formula and T is either A or an expression of the kind (SA) where S is a string. .2 A is a subformula of T if and only if some substring of T terminates with A .

Chains

29

0.73 AGREEMENT. C is enlisted by S if and only if there are such A and B that: A and B are subformulas of S , C is not a subformula of S, and C is entailed by A and by B. 0.74 AGREEMENT. S is a demonstration if and only if each subformula of S is either a definition or an axiom or a formula enlisted by some substring of S.

The next rule categorically determines just what expressions are theorems. If we had accepted it earlier as an agreement then we could have derived our rules of inference. It is of interest in this connection that: if A and B are demonstrations then ( A B ) is also a demonstration; if S is a demonstration which enlists C then (SC) is a demonstration. 0.75 RULE. T is a theorem if and only if there is a demonstration of which T is a subformula.

CHAINS We now take the trouble to make a number of earlier notions quite explicit. It is to be noted that 0.79,0.81, 0.83, and 0.85, have, in reverse order, the force of a sequence of agreements. 0.76 AGREEMENTS. .O Cis a chain if and only if C is an expression whose initial symbol is ‘ ’. .1 C’ is a subchain ofC if and only if C is a chain, C’ is a chain, and either C‘ is C or there is such a chain C “ that C is (C’C”). .2 C ends with A if and only if A is framed and C is of the kind (C’A) where C‘ is a chain whose terminal symbol is ‘ 1’. . 3 A is a link of C if and only if some subchain of C ends with A .

0.77 AGREEMENTS. .O ( A : :B ) is the expression obtained from ‘ixy’ by replacing ‘2by A and ‘y’ by B. ( A :B ) is the expression obtained from ‘my’ by replacing ‘ x ’ by A ,1 and ‘y’ by B. We shall use 0.77 in 0.80 and 0.81.

30

0. Language and Inference

0.78 AGREEMENTS. .O A is a string-link of C if and only if A is a link of C and there is such a subchain C‘ of C that A is not a link of C‘ and A is of the kind (FB) where F is a formula and B is a link of C’. . I C is a string-chain if and only if each link of C is either a formula or a string-link ofC. 0.79 RULE. S is a string if and only if there is a string-chain ofwhich S is a link. 0.80 AGREEMENTS. .O A is an indicial-schematic-linkof C if and only if A is a link of C and A is of the kind ( a ::B ) where a is such a variable and B is such a formula that there are a subchain C‘ of C, a variable a, a schematic expression S, and a formula B for which:

A is not a link of C‘; a appears in S; ( a : : B )is a link ofC’; ( a ::B ) is a link of C’ ; B can be obtained from B by schematically replacing S by a formula.

.1 A is an accepted-schematic-linkof C if and only if A is a link of C and A is of the kind ( a :B ) where a is such a variable and B is such a formula that there are a subchain C‘ of C, a variable a, a schematic expression S, and a formula B for which: A is not a link of C’; a appears in S; ( a : :B ) is a link of C’ ; ( a :B ) is a link of C‘; B can be obtained from B by schematically replacing S by a formula in which a does not appear. .2 A is an indicial-free-link of C if and only if A is a link of C and A is of the kind ( a ::B ) where a is such a variable and B is such a formula that there are a subchain C‘ of C, a variable /3, and a formula B for which:

A is not a link of C’ ; ( a : : B )is a 1inkofC’;

31

Chains

fi is free in B ; (fi:B ) is a link of C‘; B can be obtained from B by replacing fi by a formula in which a does

not appear. .3 A is an accepted-free-link of C if and only if A is a link ofCand A is of the kind ( a:B ) where a is such a variable and B is such a formula that there are a subchain C‘ of C, a variable fi, and a strict formula B for which

A is not a link of C’; ( a :B ) is a link of C’; fi is free in B ; (/?: B ) is a link of C’;

B can be obtained from B by replacing

fi by a formula.

.4 A is an indicial-start if and only if A is of the kind ( a :: F ) where F is a form and a is a variable which occurs in F more than once.

.5 A is an accepted-start if and only if A is of the kind ( a : F )where F is a form and a is a variable which occurs in F less than twice. .6 C is a double-chain if and only if C is a chain and each link of C is either an indicial-start, or an accepted-start, or an indicial-schematiclink of C, or an accepted-schematic-link of C, or an indicial-free-link of C, or an accepted-free-link of C. 0.81

RULES.

.O a is indicia1 in A if and only if a is a variable, A is a formula, and ( a : : A ) is a link of some double-chain.

.1

a is accepted in A if and only if a is a variable, A is a formula, and

( a :A ) is a link of some double-chain.

0.82 AGREEMENTS. .O A is a free-link of C if and only if A is a link of C and A is of the kind ( a B ) where a is such a variable and B is such a n expression that there are a subchain C’ of C, a variable 6, an expression B , and an expression B for which : A is not a link of C‘; (fiB ) is a link of C’; (aB ) is a link of C’ ; (aB ) is a link of C’;

32

0. Language and Inference

B is obtained from B’ either by replacing /3 by B" or by schematically replacing some schematic expression by B".

.

1 A is a free-start if and only if A is of the kind (&) where F is a form and a is a variable which occurs in F less than twice. Thus an accepted-start is the same as a free-start. We repeat ourselves here in order to make 0.82.1 independent of 0.80.5. .2 C is a free-chain if and only if C is a chain and each link of C is either a free-start or a free-link of C. 0.83 RULE. a is free in A if and only-if a is a variable, A is a n expression, and ( a A ) is a link of some free-chain. 0.84 AGREEMENTS. .O A is a parenthetical-link of C if and only if A is a link of C and there are such a subchain C' of C and such a link B of C' that:

A is not a link of C'; and A can be obtained from B by replacing a symbol which is not a parenthesis by a parenthetic expression.

.1 C is a parenthetical-chain if and only if C is a chain and each link of C either is an expression devoid of parenthesis, or is a parenthetical-link of c. 0.85 RULE. Sis parenthetical if and only if there is a parentheticalchain of which S is a link.

CHAPTER 1

LOGIC 1.0 DEFINITIONS. .O (Ifp then q = (p --f q ) ) .1 ( ( x impliesy) = ( x +y)) ux = Ax ux) .2 (For each x , .3 ( 0 ~ A x x ) .4 (-p = (p + 0)) .5 (Notp=+) .6 (U = N O )

d =+ v)) ((Pand 4) = ( P A 4 ) ) ((P* 4) = ( P A " 4 ) ) * l o ((Pv 4) =-(+ A "Q)) .11 ((Porq) = ( P V d ) *12 ((P" q) = ((P q) A (Q -.P))) .13 ((pif and only if q) = (p q ) ) .14 ( ( x is equivalent toy) = ( x +--t y))

-7 *8 -9

((PA

+

-+

t)

.15 (Vx ux =-AX N_W) .16 (For some x , ux = V x ux)

-

Although it will turn out that (A

B

=A

"B)

there are certain technical advantages arising from 1.0.9 and the Theory of Notation. With Remark A.28 in mind we make: 1.1

DEFINITIONAL AXIOMS FOR LOGIC. .O (0 r A x x ) .1 (-p = (p --f 0 ) ) 33

1. Logic

34

1.2 AXIOMS OF DEFINITION FOR LOGIC. -0 ( ( x E Y ) ( x -+!I)) +

- 1 ( ( x =Y)

+

(Y

+

4)

1.3 AXIOMS FOR LOGIC. .O (Axux +ux) .1 (y S A x y ) vx) + (Ax ux -+ Ax vx)) .2 (Ax(ux - +-

-(P-+4)

-3 ( ( P - + q ) - + ( ( q - + r ) -4 ((P-+ ( 4 r ) ) ( 4 + (P

((-P -+PI -.PI +

-5

+

-+

4))

1.4 THEOREMS. -0

(0 -+PI

Proof. Because of 1.0.3 and initiation (0 = A m ) .

Initiating 1.2.0 we learn by substitution that ( ( 0 =!I) -+ (0 -+d)

and from this in turn we learn by substitution that ((0=Axx)

--f

(0 -+ Axx)).

By detachment (0 -+ Axx).

By schematic substitution in 1.3.0 ( A x x -+ x ) .

Starting with 1.3.3 we learn successively by substitution that ((0

+

4)

( ( 0 -+ 4)

+

+

((4

((4

+

+

and

r)

4

+

(0 -. r ) ) ) ,

+

(0 + x ) ) ) ,

( ( 0 -+ A x x ) -+ ( ( A x x -+ x ) -+ (0 -+ x ) ) ) .

By detachment ( ( A x x +x )

-+

(0

-+ x ) ) ,

35

Logic and again by detachment ( 0 -+ x ) .

By substitution we conclude

(0 +P)We shall never again be so detailed in our proofs.

-1

(-P

Proof.

+

(P

+

4))

Because of 1.0.4, 1.2.0, and 1.3.3

(-P

(P

-+

+

0))

and

((P

0)

-+

-+

((0

+

4)

-+

(P

-+

4))).

Substituting in 1.3.3 and detaching twice we see

(-P

-+

((0

+

4)

-+

Consequently, because of 1.3.4,

((0

+

4)

-+

(-P

+

(P d)). +

(P

+

4))).

Now employ .O and detach the desired result.

2

(P (-P

Proof.

+

-+

4))

Use. 1 and 1.3.4.

A remarkable discovery by Lukasiewicz is that all ordinary sentential theorems which can be written down in terms of parentheses, variables, '-', and ' +' can be inferred from 1.3.3, 1.4.2, and 1.3.5 by using only substitution and detachment.

36

1. Logic

*8 (- -P (-P -9 (- -P (-P .10 ( - - p -+p)

*4))

-+

*P))

-+

(@*-PI

*-PI ((- -P -.PI * ((P *-PI * (- -P (cp +-PI (- -P -.PI)

Proof.

-+

-9)))

+

-P -P) -P) ((fi * -P) + -P) ((-

+

+

.12 ( p * - - p ) -13

((P-+Q)

*(-4*-P))

((P 4 ) * ( ( 4 0) * I 4 ((-P -4) ( q *P)) -15 (P * ( 4 * P I ) Hint.

-+

-+

(P Proof.

(P * 0 ) ) )

+

+

Hint.

+

Use 1.4.2. -+

( 4 -+

Q)))

(PA

(P * ((P* "Q) -4)) (P * (,- -4 * -(P * -54)) (P ( q -(P * " 4 ) ) ) +

+

+

-17 ( P A Q * P ) Hint. Manipulate 1.4.1 ; use 1.2.0, 0.48, and 1.2.1. -18 ( P A Q + Q ) Hint. Manipulate 1.4.15. I n trying to prove Theorem 1.5.0 below we write down a single formula which, when properly understood, should make us believe 1.5.0 is a theorem. That the formula written in proof is a theorem follows by intuitive induction from 1.3.3 and 1.4.16. That this formula yields 1.5.0 is a consequence of 1.4.18. In checking the next to the last step we use 1.4.1 1. I t will become increasingly important to correctly understand 0.37. I n particular, note that

((P

+

4

+

r

+

J)

= ((P* 4 ) A (P-.r ) A (P 4)). -+

Logic

37

38

1. Logic

39

Logic .1

(EX -+ v x UX) -

2

(VXY +Y) (AXY H Y )

.3

-4 ( V X Y H Y )

.5 .6

(Ax ux -+ Vx UX) (Ax(ux - -+ VX) -+ (Vx ux + VX VX))

.7

(AxAy u’xy -+ AyAx u’xy)

Proof.

(As u‘xs

u’xs)

--f

(AxAs u‘xs + Ax u’xs) (AsAxAs u’xs

-

(AsAxAy u’xy

-+ AsAx U‘XS) + AyAx u’xy)

-

(AxAy u’xy -+ AsAxAy u‘xy)

Now combine the last two formulas. u‘xy .8 (AxAy -

.9

e,AyAx

u’xy (VxVy -

. l o (vX(y A UX) + y Proof.

u’xy)

u’xy) VX UX)

e, v y v x A

(ux - + Vx ux)

(Y +Y) ( Y A ~ X + Y A

(vX(y A UX)

.I1 (y A VX UX Proof.

--f

Vxyx)

+ vX(y A VX UX) -fy

VX(y

-

A UX))

(y --+ (yx + (y A yx))) (Axy + Ax(yx --f y A UX) + (VX U X -+ v X ( y A UX))) -

(y + (VX U X -+ vX(y (y A VX y X .12 (vX(y A UX) t ) y

A VX

.13 (Ax(y v gx)

v Ax yx)

e,y

.14 (Ax(ux - Avx) .15 (VX(? v vx)

A 2X)))

+ vX(y A UX))

e,Ax e, v x

_wC)

u x A Ax vx) -

ux v v x VX)

A VX UX)

1. Logic

40 .16 (VxAy u'xy

+ AyVx u'xy)

.17 (Ax(y + ux) c-) (y + A x ux))

.18 .19 .20 .21

(Ax(yx -+y)

c-)

(Vx(y + UX)

4-9

-

(Vx ux +y))

(y -+ Vxyx)) (Vx(ux - +y) t--) (Ax ux +y))

+ Ax u x t)Ax yx) .22 (Ax(ux - t)vx) - + Vx gx t--) Vx vx) (Ax(?

e+ VX) -

CHAPTER 2

SET THEORY Any set theory formalized in the spirit of Chapter 0 naturally suggests certain simple provocative questions. When is x ? What is ( x E y) ? What is ( p + q) ? What is Ax ux? We shall commit ourselves to a set theory unorthodox in the sense that these questions are answered. In fact, our Axioms 2.5.0-2.5.3 were conceived for this express purpose. We were led to these four axioms somewhat as follows. We believe every (mathematical) thing is a set. We believe there is no difference between the conjunction of two or more things and their intersection. We believe there is no difference between the disjunction of two things and their union. We believe there is no difference between the negation of a thing and its complement. We have come to believe a thing if and only if the empty set is a member of the thing. We believe ( x E y) if and only if x is a member ofy. We believe ( x E y) if and only if ( x E Y ) is the universe. We disbelieve ( x E Y ) if and only if ( x E y) is the empty set.

PRELIMINARIES 2.0 ORIENTING DEFINITIONS. .O (me1 E X = x ) .I ( ( x EX’) = ( x E X ’ ) ) .2 (me1 x = me1 x )

2.1 .O .I .2 .3 .4 .5

DEFINITIONS. ((xis a set) = (x + x ) ) (The empty set = 0) (The universe = U) (complement x = - x ) ( ( x is a member ofy) = ( x E y)) ((xisiny) ~ ( x ~ y ) ) 41

42

2. Set Theory

= Vy(x ~ y ) ) (0 E x ) ) ( ( x is false) = ~ ( E x0) )

.6

( ( x is a point)

.7

( ( x is true)

.8

-9 .10 .I1 .12 .I3

((X3Y)

E

= (9€ 4 )

((xholdsy) = ( x 3 y ) ) ((xcy) = A t ( ( t ~ x + ) (t~y))) ( ( x is included in y) = ( x c y)) ((xis a subset ofy) = ( x c y ) )

.14 ((x'y)

= (ycx))

.15 ( ( x includes y) 3 ( x 3 y)) .I6 ( ( x is a superset ofy) = ( x Iy)) .I7 ((.=Y) = ((x=y) A (y=x))) ( ( x equalsy) = ( x =y))

.18 .19 .20 .21 .22 .23 .24 .25 .26

.27 .28 .29 .30 .31 .32 .33 .34 ,35 .36

( ( x #y)

= -(x

=y))

((x=.y)=(xCy#x)) ( ( x is a proper subset ofy)

((x

-=y) = (y =. x ) )

= (x c-y))

( ( x is a proper superset ofy) =- (x

y))

(The intersection as x runs ,of yx = Ax UX) (The union as x runs , of ux 5 V X UX) ('IlA 3 Ay(y E A -.y)) (The intersection of A = l l A ) ( V A vy(y E A A y)) (The union of A = VA) ( ( x n y) = ( x A y ) ) ((xintersecty) = ( x ny)) ( ( x u y) = ( x vy)) ( ( x uniony) = ( x u y)) (sng x E Ay(y +. (x ~ y ) ) ) (singleton x = sng x ) (The set whose sole member is x = sng x )

I n formulating 2.2 and 2.3 we have Remark A.28 in mind.

43

Preliminaries 2.2

.o

.1

LOGICAL DEFINITIONAL A X I O M S FOR SET THEORY.

(U = -0) ((PA

4 = -(P

+." 9 ) )

2 ((Pf-td=((P+.dA ux = -AX-UX).3 (VX -

(4+.P)))

2.3 SET-THEORETIC DEFINITIONAL A X I O M S FOR SET THEORY. .O ( ( x c y ) = A t ( ( t ~ x )-+ ( t ~ y ) ) ) .1 ((.= =!( I( ).'!AI) (YCX))) .2 (sng x = Ay(y + ( x E y)))

2.4 A X I O M O F D E F I N I T I O N FOR SET THEORY. ( ( x =!= I) ( x =!I))

2.5

.o

-

A X I O M S FOR SET THEORY. (xf-t (0 E X ) )

-1 ( ( t E U) -+ ( ( t E .( ELI)) (x E d ) ) 2 ( ( t E a) + ( ( t E (P 9 ) ) * ( ( t E P ) ( t E PI))) .3 ( ( t E Ax UX) t)Ax(t E U.)) .4 ( ( x E U) -+ ( ( x =tj) f-t A t ( ( x E t ) + (y E t ) ) ) ) .5 ( ( x = y ) -+ (u.=uy)) - .6 (U = VcAx((c A ( c E U)) A ( ( x E c) + (sng x E c)))) .7 (VX(((AE u) A ( X c A ) ) A ((s E u) A UX)) E u) .8 ( ( z ~ A ) - + ( r n e l A ~ A ) ) -9 ((2 E A ) VY((Y E 4 A (Y = -4)) -+

-+

L

+

Remark. Axiom 2.5.9. is our axiom of regularity. Its purpose is to preclude the sequential possibility that

.so 3 .s1 3 .s2 3 ....

The only use we shall make of it is in proving 2.105. If we wished to avoid all use of 2.5.9 we would use 2.108 as a basis for a more complicated version of 2.5.8, free 2.1 17 and 2.126 of their present dependence on 2.105, and delete 2.103-2.108. Axiom 2.5.8 is our version of the

44

2. Set Theory

Zermelo principle of choice. I t can without the loss of 2.108 be replaced by the longer but less demanding formula ‘ ( ( ( z E A ) A( A E U ) ) - - + ( m e l A E A ) ) ’ .

Axiom 2.5.7 is our axiom of replacement. From it we learn that quite a few sets are points. It can, at some cost, be replaced by axioms in which no schemator appears. Axiom 2.5.6 is our axiom of infinity. Its purpose is to assure that VcAx( (C A

(C

E U)) A ( ( x E c) -+ (sng x E 6 ) ) )

and that (sng x E U). Thus at small cost we could replace 2.5.6 by two simpler axioms. Axiom 2.5.5 is our axiom of equality. I t is principally ofvalue in establishing certain intuitively reasonable general formulas. I n order to stress its relative unimportance we do not use it prior to the proof of 2.31. Axiom 2.5.4 is our version of the law of Leibniz. Axiom 2.5.3 is our axiom of intersection; Axiom 2.5.2 is our axiom of distribution; Axiom 2.5.1 is our axiom of value; and Axiom 2.5.0 is our axiom of truth. Let us agree here that our revised system is the one obtained from the present one by replacing Axiom 2.5.5 by

‘ ( ( x =y) -+ (me1 x

= me1 y)) ’.

Helped by suggestions made by Dana Scott we have convinced ourselves that our present system is consistent with our revised system. With this is mind we find it relatively easy to see that Axiom 2.5.9 is consistent with the rest. Nevertheless, we are not at all sure that Godel’s approach, exploited so successfully e l ~ e w h e r ecan , ~ be used here to show Axiom 2.5.8 is consistent with the rest. 2.6

THEOREM.

(xis a set)

2.7

THEOREM.

(OEU)

Proof.

Use 1.4.5 and 2.5.0.

3 Godel, K., The Consistency of the Continuum Hypothesis (Ann. of Math. Studies No. 3), Princeton Univ. Press, Princeton, New Jersey, 1940.

45

Preliminaries ( x cy -+ (.x +y))

2.8 T H E O R E M . Proof.

Helped by 2.5.0 we infer ( x cy + ( t E x

--f t E y) (0 E x -+ 0 €Y) + ( x -+!I)).

3

2.9 T H E O R E M .

(x

=ZJ +x

( ( x -y)

tty)

x =y)

2.10

THEOREM.

2.11

T H E THEOREM OF EXTENT. ( a = b tt AX(X E u t,x

2.12

LEMMA.

Proof.

(x E a

-+

t-f

E

b))

x E U)

Because of 2.5.2, 1.0.4, and 1.0.6 we know (2 € a -+ ( ( x € 0 --f x E 0) -+ x E (0 -+ O ) ) ) , ( ( x € 0 + x € 0 ) 3 ( x E U + x E ( 0 -+O))),

and

+x

(x E a

E

(0 -+ 0)

-+ x E

-0

2.13

THEOREM.

( x E Y + (xis a point))

2.14

THEOREM.

((xis a point) H x E U)

2.15

LEMMA.

Proof.

(x E

( t E 0 -+ t

0 -+ x

E a)

E Axx -+ A x ( t E X )

2.16 T H E O R E M .

3x E

-+ t E a)

(0 c a c U )

Taking advantage of 2.12 we infer: 2.17

LEMMAS.

u) H ( t E u -+ t E U H Y ) )

.o

((tE a t t y A t E

.1

((tEatttEb)tt(tEU +tEaHtEb))

From 2.5.1, 2.5.2 and 2.17.0 we deduce: 2.18 T H E O R E M S .

.o .1

(t E

( X E y) t--f X

( t E (p -+ q)

H

Ey A

t

E

u)

( t E! + t

E 4) A t E

u)

U).

2. Set Theory

46 2.19

.o

(x

LEMMAS. € 0 -+O)

Proof.

Using 2.15, 2.18.0, and 2.5.0 we infer ( x € 0 -+x

.I .2

E

( x €0-0) -(x

(0 € 0 ) -+o

E0

-to).

€0)

2.20 T H E O R E M S . .O ( t ~ U - + t ~ - a t t t - ~ a )

Recalling 0.49 and using 2.19.1 we deduce

Proof.

( t E U -+t

t -€

ts

u)

.1

( t E -Q

.2

(tE(QAb)HtEQAtEb)

Proof.

4 4

( t E U -+ t

Q A

E

t

(Q A

E

t E (Q + O ) ( t E Q -+ t E 0) e, ( t E a + 0) t-)t M E a).

E-at)

6 ) t)t

E -(Q -+ -b) -(t E (Q -+ - 6 ) ) t)" ( t E Q -+t E N b ) * " ( t E a 3 t M E b) ++ t E Q A t E b ) t)

( t E (Q v 6 ) t)t E Q v t E b ) .4 ( t E U - - t t E ( p t , q ) * ( t E p t , t E q ) ) .5 ( t E ( p t+ 4) t)( t E @f-f t E q) A t E u) u x t)V x ( t E ux)) .6 ( t E Vx .7 ( t E u --t t E ( x c y) t+ x c y) .8 ( t E ( ~ c y t))x c y A t E U) .9 ( t E U - + t E ( x = y ) * x = y ) .lo ( t E ( x = y ) t + x = y A t E U ) .3

2.21

THEOREM.

2.22

LEMMAS.

(-p

A

At(t

= 0 t)Ax - ( x

E

t)t E u A p ) + p = u) ~ p e t E, U ~ p +$) = 0)

.o ( p A At(t E P .1

(Q

Q) t+

-VX(X

E a))

Preliminaries

2.23 LEMMA. 2.24

.o

(a = 0 v a = U A

47

b = 0 v b = U -+ ( a t , b ) t)a = b )

EXERCISES. (U'U)

.1 ( a c b ~ c - t a c c ) .2 ( x = x ) . 3 ( x = y -+y=x) .4 ( x = y = z + x = z ) -5 ((P -+ 4 ) = (-P v 4) = -p u 4 ) .6 ( U n U = a ) .7 ( u u o = a > .8 (u n O = O ) .9 ( a u U = U ) .10 ( a n a = a ) .ll( a u a = a ) .12 ( a n b = b n a ) .13 ( U u b = b U U ) .14 ( a n ( b n c ) = ( a n b ) n c = u n b n c ) .15 (a u (6 u c ) = ( a u b ) U C = U U b U C) .16 ( a u b n c = a n c u b n c ) .17 ( a n b u c = a u c n b u c ) .18 ( - - u = u ) .I9 (-(a n 6) =-a u -b) .20 (-(a u b) = -a n 4) .21 ( U n -u = 0) .22 ( a u -a = U) .23 (-AX ux = Vx -2.) .24 ( -VX zx = AX N UX) .25 (u c b h c c d +-a n c c b n d ) .26 ( a c b h c c d - a U c c b U d ) .27 ( a n b c a)

48

2. Set Theory

-28 ( a c a u b) .29 ( a c b t t a = u n b ) .30 ( a ~ b t t b = a U b ) .31 ( y E a - + T l a c y ) .32 (y E a +y c V u ) .33 (y E a --f n u c y c V u ) .34 (u # 0 + n u c Va) .35 (U(Uu b ) = TTu n T l b ) .36 ( V ( a U b ) = V a U V b ) .37 (TTVx ux - = A x l l u-x ) .38 (VVx ux = VX VUX) .39 (u c 6: T l b c n u ) .40 ( a c b + V a c V b ) .41 (TlU = 0) .42 (TlO=U) .43 (VO = 0) .44 ( a c b - + a c * b v a = b ) .45 ( a c * b c c + a c - c ) .46 ( a c b c.c + a c.C) .47 (Axy=y) .48 (VXY =y) .49 ( ( u - + b ) = U t , a c b ) .50 ( X E Y -+ ( X EY) = U) .51 ( x V'EY -+ ( x EY) = 0) .52 ( X c y -+ ( X c y ) = U) .53 ( x -c y --f ( x c y ) = 0) .54 ( x = y + ( x = y ) = U ) .55 ( x # y + ( x =y) = 0) .56 (AxAy u'xy = AyAx u'x~) .57 (VxVy u'xy = vyvx u'xy) .58 (Ax(ux ux n Ax yx) - n -vx) = Ax .59 (Vx(ux u vx) = v x ux u vx vx) .60 (Ax(ux ux c Ax vx A Vx ux c Vx vx) - c -vx) -+ Ax -

Some Aspects of Equality

49

.61 (Ax(y u UX) - = y u Ax UX) .62 (Vx(y n UX) - = y n VX UX) .63 (Ax ux c u x c Vx ux) .64 (Ay(y E a -+ b cy)t)b c l l a ) .65 (Ay(y E a -+ y c b ) t)V a c b ) .66 (VxAy u'xy c AyVx u'xy)

SOME ASPECTS OF EQUALITY 2.25

THEOREM.

Proof.

(q = r

-+(p

(q=r

U

t

-+q) = (P + r ) )

E q t)t E r ( t E p - + t E q ) t)( t E p -+t EY) t E (P 4) t,t E (P -+ r ) ) ) ( t E U -+ t E (p -+ q) t)t E (p -+I)))

(t

-+

E

-+

-+

+

+

(q=r

-+

Now use 2.17.1 to infer

( q = r -+ t

conclude

( q = r -+ At(t

and

(4 = r

2.26 T H E O R E M . 2.27

(p -+ q )

E

THEOREM.

2.28 T H E O R E M .

+

(P

E

+

f-f

t E ( p +r ) ) ;

(p -+ q) tt t E (p -+ r ) ) )

q ) = (P

+

r)).

(p = q -+ (p -+ r ) = ( q + I ) ) (AX(UX ux = A X VX) - = VX) - -+ AX (y = z

-+

(X

~ y =) ( X

E 2))

So far we have used Axioms 2.5.0 through 2.5.3. We now use 2.5.4. 2.29

.o

LEMMAS. (x=y+(xEt+yEt))

Proof.

( x E t -+ x E U) ( X E U -+

(x E t

-+

(x=y+

(x=y

( x =y -+ ( x E t

.1

(x

E t -+y E t ) ) )

-+

( x E t -+y E t ) ) )

-+

( x E t +y E t ) ) )

( x = y -+ ( x E t -+ y E t ) ) ( x =y -+ ( x E t t)y E t ))

2. Set Theory

50 2.30 T H E O R E M .

(X=Y

-+

(x ~

t =(y ) ~ t ) )

We now use 2.5.5 for the first time. 2.31

THEOREM.

Proof.

(X

= y -+ V-X = VY)

( x = y -+ gx = y) (Ax(ux - = VX) - -+ (UX - =-VX)) ( A X ( ! ~= YX) -+ ( ~ I J= ~ y ) ( x = y A Ax(yx = VX) ux =-uy A -ux =-vx A gy = vy - -+ --f vx = y) (AX(UX - = VX) - -+ ( X = y -+ X X =~zJ))

I n this last formula schematically replace ‘ux’ - by ‘vx’ - and detach. The next four theorems, as well as many earlier ones, can be proved by similar devices.

2.32 THEOREMS. .O (x = y + me1 x = mely) U‘XZ = u‘yz) .1 ( x = y --f .2 ( x = y -+u’zx = u’zy) U’XY = ?’St) .3 ( X = 5 A y = t 3 Remark. Becauseof2.3.1, 2.4,2.5.4,2.5.5,2.10,2.11,2.24.2,2.24.3, 2.24.4,2.25, 2.26’2.27’2.28, 2.30,2.31, and 2.32, itseems that equality might well possess those intuitive attributes usually ascribed to it. Hereafter we shall accept formulas like those in 2.32 without question. Remark. Logic helps us investigate set theory. Conversely set theory can be used to establish theorems in logic. We agree that a formula A is universal if and only if a theorem is obtained from ‘ ( x = U) ’ by replacing ‘x’ by A . Now all theorems which can be inferred from universal axioms are themselves universal. An examination reveals that all our axioms for logic are universal and that all but Axiom 2.5.0 of our axioms for set theory are universal. Since every universal formula is obviously a theorem we now have a t hand a systematic set-theoretic method for exploring logic.

51

ClassiJication

CLASSIFICATION 2.33 DEFl NIT10 NS. ux 3 Vx(0 E yx A sng x ) ) .O (Ex UX) .l (The set of points x such that c x e Ex -

.2

({x :UX}

= Ex -UX)

.3 (sb A = Ex(x c 4)) .4 (psb A = Ex(x C . A ) ) .5 (sp A = Ex(x 3 A ) ) .6 ( p ~ Ap 3 Ex(x * =A ) ) Unused in the present section but used in the next is 2.34.4 below. 2.34 LEMMAS. .O (y E U +y E sng x e t y = x )

Recalling 2.5.4 we see

Proof.

(y E U +y

E sng

x

t)y

E At(t

t)y

=x).

+-x

E t)

At(y E t -+ x

Et)

t)

.1

.2 .3 .4

sng x ++y = x A y E U) ( x E U + x E sng x ) (x~U+x~A++sngxcA) ( x E U A a = sng x -+ x = TTa = V u )

(y

Proof.

E

From .O we infer (y E a - + y c

XA

Xcy).

Because of this, 2.24.65, and 2.24.64, we have on the one hand

(Va c x c n u ) . Because of .2 and 2.24.33 we have on the other hand

(nu c x c Va). The only use of 2.5.6 until 2.139 is in proving

52

2. Set Theory (x~U+sngx~U)

.5

We use 2.5.5 in proving the following very useful theorem. 2.35

T H E T H E O R E M O F CLASSIFICATION. ( x E E xuxt, UXA x E U)

Proof. Using 2.5.0, 2.34.1, 2.5.5, and 2.9 for the fifth, sixth, and seventh equivalences we see ( x E Ex ux ++ x E Vx(0 E ux A sng x )

++~ t ( Ex (0 E V t A sng t ) ) t)Vt(x E (0E i t ) A x E sng t)

V ~ ( OE ut A FE sng t ) t)Vt(ut AXE sng t) t)

vt(it A X E u A X = 1) f-) V t ( u X A X E u A X = t) t)U X i X E u A V t ( x = t)

et

-X

t ,U

2.36 2.37

.O .1 .2 .3

.4

.5 .6 .7 .8

.9 .10 .ll .12 .13 .14

THEOREM.

(x

EU

A X E

-+ x

E

u).

Ex ux t)ux) -

THEOREMS. ( A x ( u x + V X-) + E x-u x c Exvx) ( A x ( ~t x)X X ) + EX ux = EX VX) (y = Ex(x E Y ) = Vx(x € 9 A sng x ) ) ( EX(EX + X X ) = (EX ux -+ EX VX)) (Ex NUX UX) - =-EX (Ex(ux A y x ) = Ex _wc n Ex vx) (Ex(x E U A u x ) = Ex ux) ( E x ( ~ x v X X ) = EX ux U EX VX) (EX& ++VX) = (EXEX t)EX Y X ) )

~ E x1 1 ’ ~ ~ ) ( ExVy U ’ X ~= Vy EX L-I‘x~) ( E x-u x = U + + A x ( x ~ U- t u-x ) ) (p=O~p=U+p=Etp) ( x c y + sb x c sb y A psb x c psb y c sb y) (sb A sb B = sb ( A B ) ) (ExAy

U ’ X ~= A

53

The Role of Replacement Hint.

.15 .16 .17 .18 .19 .20

For the notation recall 0.36.

(sbA U s b B c s b ( A U B ) ) ( V sb A = A c sb VA) (sbU=U) (VU=U) (sng x = Ey(y = x ) ) (0 E sb 0 = sng 0 c sb A )

In establishing implications we shall frequently, as in the proof of 2.38 below, write down formulas some of which may not be theorems but each of which is implied by the premise of the implication to be established.

2.38 T H E O R E M . Proof.

(a= EX - ( x

E X ) -+ a -E

U)

From 2.36 we learn ( t E U +t

Hence (t E

E

Et ut - t)ut). -

u + t E a*

t

-E

t),

( aE U -+ a E a f-t a -E a),

and the desired conclusion is at hand. Remark. Our proof of 2.38 is closely patterned after the reasoning used by Bertrand Russell in reaching his famous paradox. Of course if by misfortune ' ( x E Ex - ( x E x ) t)x -E X ) '

is a theorem then the Russell paradox is at hand.

THE ROLE OF REPLACEMENT Usually of only local interest are definitions introduced in the spirit Of

2.39 D E F I N I T I O N . (2A A = V x ( A E U A x 2.40 LEMMAS. .O

(~AAEU)

cA

A

V xEU

A

Vx))

54

2. Set Theory

Proof.

.1

See 2.5.7.

(XEAEU-+X~~AA)

Proof.

( ( AE U

A

t cA

A

Vt E U

A

Vt)c 2AA)

because of 2.24.63. Substituting, we see that ( ( AE

u A s n g x c A A v sng x E u A Vsngx) C 2AA).

From this, 2.34.3, and 2.34.4 we infer ( X E AE U + X = ( U AU AU A X ) = (A EU A x EA A x EU A x) = ( A E U A s n g x c A A V sng x c 2A A ) .

.2

( ( x c 2A

Proof.

A

A

A

E

A

Use 2.34.5.

.4

Ey

2.41

V sngx)

u A x € A ) = ( A EU A X € A ) )

sng x E U) = ( x E A ) )

Proof.

Proof.

v

Use . l .

.3 ( ( x E A

(((X

EU

A

t ) EU

A X

Ey) = ( X Ey A t EU))

( ( x E y) = 0 v ( x E y) = U)

THE THEOREM OF REPLACEMENT. (VX(A E

Proof.

uA

X E

A

-

A UX E

u A -UX) E u)

From 2.5.7 we learn (Vx(2A A

E

uA x

c

2A A

A

ux E u A ux)

E

u).

In the light of 2.40.0 we see ( v x ( x C 2AA

A

ux E u A ux)

E

u).

Schematic substitution reveals that ( V x ( x c 2A A

A

(AE U

A

ux) E U A A

EU

E

u A -ux E u A -w)E u).

-

A UX) E U ) .

Employing 2.40.4 we find ( v x ( x c 2A A

A

A

The Role of Replacement

55

Another schematic substitution now reveals that ( ~ ~ ( X C ~ A A A A (EX EUAAA U - X )E U A X E A A U -XE ) U).

Employing 2.40.4 again we find (vx(xC 2 A A

A

A

u A x € A A -ux E U A yx) E U ) .

E

From 2.40.2 we consequently conclude (VX(A

2.42

uA X

E A A UX -

E

u A -UX) E u).

( A E U -+ B n A E U )

THEOREM.

Proof.

E

According to 2.41 (VX(XE A

ux E U

A

A

ux) E U).

Schematic substitution yields ( V X ( ~ E A (AX E B A-U X E )U A X E B A U - X )E U ) .

According to 2.40.4 (vx(x E A

A

x E

BAux E u A ux) E u).

Hence (Vx(x

EA

nBA ux E U

A

ux) E U )

and (Vx(x

E

A nB

A

sngx E U A sngx)

E U).

Helped by 2.37.2 and 2.40.3 we conclude

(A n B

= Vx(x E A n B A = Vx(x E A n B A

sngx) sng x E U A sng x)

2.43

T H E T H E O R E M OF HEREDITY. ( B c A E u + B E U)

2.44

T H E T H E O R E M OF SUBSETS. (AEUt+sbAEU)

Proof.

E U).

Schematic substitution in 2.5.7 assures us

( A E U -+ Vx(x c A

A

sng x

E UA

sng x ) E U).

2. Set Theory

56

Helped by 2.37.2, the Theorem of Classification, 2.40.3, and the Theorem of Heredity we infer

(AE U

-+ sb

A

= V x ( x E sb A A sng x ) =vX(X cA A X E A Sng X ) = V x ( x c A A x E U A sngx E U A sngx) = V x ( x c A A sng x E U A sng x ) E U).

u

Thus

(AEU

.O

-+ sb A E U).

Because of the Theorem of Replacement

( A E U -+ VA

= vx(x E =vX(X E

A A

A X) A X

E

uA

X)

E

u)

and hence

(AEU

.1

-+

VA

E U).

Because of .1 and 2.37.16 .2

( s b A E U - t A = V s b A EU).

The desired conclusion now follows from .O and .2. From 2.44.1 on the one hand, and from 2.44.0, 2.37.16, and the Theorem of Heredity on the other, we infer: 2.45

THE THEOREM OF AMALGAMATION. ( A E u c-) VA E U)

2.46

DEFINITION.

(2B abx = ( a A x

2.47 LEMMAS. .O (0 E U A sng 0 E U A sb sngO E U .1 (2BabO = a ) .2 (2B ab sng 0 = b) .3 (2B abx # 0 -+ x = 0 v x = sng 0) .4 (0 E sb sng 0 A sng 0 E sb sng 0) .5 (2B abx = ( x E sb sng 0 A 2B abx)) .6 ( a E U A b E U --f 2B abx E U)

A

=0

vbAx

= sng 0))

0 Esng 0 A 0 #sngO)

57

Singletom 2.48

T H E T H E O R E M O F UNIONS. ( a E U A b E U tt a U b E U )

This follows from the Theorem of Heredity and : Lemma.

Proof.

u

(a E U A b E U + a

b

E U)

Using 2.47.5 we see (Vx 2B abx = V x ( x E sb sng 0 A 2B abx) = Vx(sb sng 0 E U A x E sb sng 0 A 2B abx E U A 2B abx) E U).

But 2.47.1 and 2.47.2 tell us ( a u b = 2B abO u 2B ab sng 0 c Vx 2B abx

2.49

THEOREM.

Proof.

-(U

E

E U).

U)

From the Theorem of Heredity we have (U E u + x c

u EU + x

E

U).

Hence (x-EU

-tU4U).

Accordingly, because of 2.38, ( a = Ex - ( x

E x ) -+

a -E

U

-+ U ME

U),

and the desired conclusion is at hand.

SINGLETONS For the sake of completeness we restate in 2.51 and 2.54.10 results known earlier in 2.34 and 2.37.19. We shall use 2.34 without further reference. The inverted word order in 2.50.1, for example, obviates parentheses. 2.50

.O .1

DEFINITIONS.

(snglx = Ay(x E Y +y)) (singleton is a = (Va = l l a ) )

58

2. Set Theory

2.51 T H E O R E M S . .O ( ~ E +Uy E s n g x * y = x ) .1 ( X E U+ y E s n g l x t t y = x ) .2 (y E sng x-y = x ~y E U) 2.52 LEMMAS. .O (singleton is a + a # 0 ) .1 (singleton is a ~y E a +y = mu = V a )

Proof. 2.53

See 2.24.33.

LEMMA.

(x E U + singleton is sng x)

Theorem 2.54.8 is included for the sake of completeness, not utility. In checking 2.54.6 we use 2.52 and the Theorem of Amalgamation. I n connection with 2.54.7 we can infer, for example, that ( a = sngl n u

--f

Tla

E

U)

by noticing that ( u = sngl

nu + TTa = Tl sngl Tla)

and then using 2.54.3.

2.54 T H E O R E M S . .O ( x -E U + sng x = 0 A sngl x = U ) .1 (x E U e,sngl x E U t,sng x = sngl x) .2 (x E U t)x E sng x t)x E sngl x ) .3 (x E U tt x = V sng x tt x = TT sngl x)

.4 .5 .6 .7

(sngx E U) (sngl x # 0) (singleton is a tt V a = m a E a E U) (singleton is a t)a = sng V a tt a = sngl l l a ) .8 (singleton is a ++VyAx(x E a t)x =y) t)a # 0 A AxAy(x E a ~y E a + x =y)) (x E U tt singleton is sng x e , singleton is sngl x ) .9 .1O (sng x = Ey(y = x ) )

59

Ordered Pairs

ORDERED PAIRS In connection with 2.57.1 recall 0.58, 0.60, 0.62, and the relevant examples. In connection with 2.57.3 glance back at 0.30.19. The preliminary ordered pair, is described by 2.56.0 and is due to N. Wiener. It naturally gives rise to a preliminary Cartesian product, which behaves beautifully under nonvacuous intersection and nesting union, and falters as an ordered pair only when one of the coordinates is 0. This defect can be remedied by one-to-one correlating with each set a nonvacuous set. Depending on the correlation chosen the new ordered pair may have much or little in common with the preliminary Cartesian product from which it is fashioned. I n 1949J. W. Weihe hit upon the splendid idea of correlating with each set a the nonvacuous set sb a . The ordered pair of Weihe, (sb a

sb b ) ,

behaves smoothly under nonvacuous intersection but erratically under nonvacuous nesting union. Recently D. C. Peterson and I hit upon the idea of correlating with each set a the nonvacuous set ss a ,described by 2.57.0, and of reaching ( a , b ) by way of 2.57.1. Because of 2.60 and especially 2.60.2 the correlation we use is somewhat more commutative than that of Weihe, and our ordered pair behaves smoothly under both nonvacuous intersection and nonvacuous union. We are trying here to fashion an ordered pair which will stand up under strain. As an ordered pair, ((sng 0 ,,a ) u (sng sng 0

b))

qualifies under 2.61 and 2.62 but fails under 2.63. As a rather attractive ordered pair, ((ss a ss 0 ) u (ss 0 ss b ) ) qualifies under 2.61,2.62, and 2.63 but fails in some respects as a 2-tuple.

2. Set Theory

60

We have so arranged things that ( a , b) qualifies as a 2-tuple and we shall later so arrange things that ( a ,b ,c ) qualifies as a 3-tuple. Theorems 2.63 facilitate constructions. The reader uninterested in 2.62 is advised to ignore 2.59.10-2.59.15 and 2.60.2-2.60.4.

2.55 DEFl NIT10 NS. .O ( { x } = sngl x ) .1 ({xx'} = (sngl x u sngl x ' ) ) .2 ({xx'x"} 3 (sngl x u sngl x' u sngl x")) etc. 2.56

DEFINITIONS.

( ( x 1 Y) = { { X I {XY>>) (basicorderedpair xy = ( x I y)) .2 (basicorderedpair is p = V x V y ( p = x I y E U ) ) .3 (basicrelation is R = Ap(p E R -+ basicorderedpair isp)) .4 (bsvs R x = Ey(x ,y E R ) ) .5 (The basic vertical section of R a t x = bsvs R x )

-0

.1

2.57

.o .1

.2 .3 .4 .5 .6 .7 .8 .9

DEFINITIONS. (ss a = (sng 0 u V x ( x E a A sng sng x ) ) ) ( ( a , b ) = ( (sng 0 ss a ) U ((sng sng 0 ,/ ss b) ) ) (orderedpair ab = (a , b) ) ,/

( (a # b ) = ( a b )1 ( ( u criss b) = ( u # b ) ) (orderedpair is p = V a V b ( p = a , b) ) (crd' p -= V bsvs p 0) (The first coordinate o f t = crd'p) (crd" p = V bsvs p sng 0) (The second coordinate ofp = crd"p) 9

LEMMAS. .o ( X / y E U t , X E U A y E U ) .1 (p = x ,y E U -+ Vp = { ~ y A} l l p = { x } A VVp = x u y A Vmp = x A l l V p = x n y A l l l l p = x )

2.58

61

Ordered Pairs

.2 (p = X ,y E u + X = mmp A y = vvp -Vnp u . 3 (X ,y = U , V E u H X = U E u Ay = U E u) .4

(x / y # 0 )

LEMMAS.

2.59 .O

mvp)

(x I y E E x / y u‘xy - f-$_u’xy A x ,y

Proof.

E

U)

Again recall 0.58, 0.60, and t h e relevant examples. (z

E

Es

I

t u’st

z EEzVsVt(z = s I t A u’st) H VsVt(Z = S ,t A U’st) A Z E t)VSVt(U’St A Z = S I t E t)

u)

( x / ~ E Es , t u ‘ s t

u

u)

VsVt(u’stA X / y = 5 I t E vsvt(i’St A X = S E A y =t E t)V.JVt(u‘XlJ A X E Ay E A X =S A y = t ) t)u ’ x y ~x E U A Y E U A VsVt(x = s A Y = t) HU’XY A X / y E t) t ,

u

u

u

u)

u)

(x y E E s ,t u’st - t)y‘xy A x .y E U) (x y E E x .y U’XYH y’xy A x y E U)

.1

(A B

Proof.

= VxVy(x E A A Y E B A sng (x {y)))

( A B = E X .y

(X

E A A Y E B)

= EzVxVy(z = x / y A x E A A Y E B )

= VxVyEt(z = x .y A x E A ~ tE B j ) = V X ~ ~E(AXA y E B A EZ (Z = x .y)) = VxVy(x E A A y E B A sng (x y)))

.2 (x y E A B t)x E A A y E B ) .3 (bsvs (p u q)x = bsvspx U bsvs qx) .4 (X E A +bsvs ( A B)x= B ) .5 (X m~A + bsvs ( A ,/ B)x = 0 ) u‘xy + basicrelation i s R ) .6 ( R c E x y I

Hint.

Glance at the first formula in the proof o f .O.

.7

-(O

.8 .9

(p = 0 v p = U -+ V(p A c)

€ A I IB ) =p A

Vc)

(A#O#B-tVVV(A,,B)=VAuVB)

2. Set Theory

62

Hint. Use .1, 2.24.38, 2.58.1 and the fact that (Vx(x E A ) =

.10

u =Vy(y

EB)).

(basicrelation is R -+

RcSe,AxAy(x,y~R~x,y~S)

.1 1

(basicrelation is R A basicrelation is S -+ R = Stt AxAy(x I y E R t)x I y E S ) .12 ( A U B , , C = ( A , , C ) U ( B , , C ) ) .13 ( A , , B U C = ( A , , C ) u ( A , / B ) ) .14 ( ( A , , B ) ( C , , D )= A C , , B D ) .15 ( A B = 0- A = o v B = O ) //

LEMMAS.

2.60

.o

(0 E S S a)

( V ss a =a) .2 (ss ( a u b ) = ss a u ss b ) .3 ( a ~ b t t s s a ~ s s b ) .4 (ss ( a n b ) =ss a n ss b ) .1

Hint.

First check that (sng 0 n (x E a A sng sng x) = 0)

and that (Vy(x E a A sng sng x A y E b A sng sng y) = ( x E a A x E 6 A sngsngx) = (x E a n b A sng sng x) ).

(VVV(a , b ) = sng 0 u a u b ) (bsvs ( u , 6 ) 0 = ss a A bsvs ( a , b ) sng 0 = ss b ) .7 q o € a , b ) .8 (sng sng 0 E a , 6 ) .5 .6

Proof.

Using .O and 2.59.2 we see (sng sng 0 = 0 I 0 E sng 0 /, ss a c a , b ) .

Substitution 2.61

63

T H E O R D E R E D PAIR T H E O R E M S .

.O ( u , ~ E U + + ~ E U A ~ E U ) (crd' ( a , b) = a A crd" (a , 6) = 6 ) (a, b = c , d t , a = c ~ b=d)

.1

.2

As developed by Kelley4 the ordered pair introduced by 2.56.0 has many pleasant features. However, it is a defect in 2.56.0 that from Theorem 2.61.2, which enhances our theory of notation, a theorem is not obtained by replacing ' ,' by ','. Of interest to us but unused in the sequel are : 2.62

THEOREMS. .O ( a # 6 u G # d = a U G , b U d ) .1 ( a # b n c # d = a n c , b n d ) .2 ( a , b c c , d t , a c c ~ b c d ) .3 (crd' ( p u q) = crd'p u crd' q A crd" ( p u q ) = crd"p u crd" q ) ) .4 ( p c q -+ crd'p c crd' q A crd"p c crd" q) 2.63

.O

.l .2

THEOREMS. (orderedpair is p -+ 0 - E p ) (orderedpair is@--f sng sng 0 ~ orderedpair is 0

-

p )

SUBSTITUTION 2.64

.o

THEOREMS.

(st yx Y X = y)

Proof.

After glancing back at 0.57 we check

-

( S t y X u3c

= vX(y = X A Y X ) = VX(y = X A LJy) = y Vx(y = x )

=LyU = Ly). 4 J.

L. Kelley, General Topology,p. 259, Van Nostrand, Princeton, New Jersey, 1955.

64

2. Set Theory

.l .2 .3

u’xy (st ty -

= u’xt) -

(st (s , t ) x ,y y’xy = y‘st) (- orderedpair is z + st z x ,y y’xy

2.65

= 0)

LEMMAS.

.O ( N A Z ;u z y z = Vz ;uz -!Z) (Az ; st z x , y y’xy st z x ,y V’XY = .l A t ;s t z x ,y y’xy st z x ,y -1’xy) N

(orderedpair is z v

Hint.

N

orderedpair is z)

Theorem 2.61.2 gives rise to 2.64.2 which fortunately gives rise in turn to : 2.66 T H E O R E M .

(A x ,y ; ~ ‘ X Y~ ‘ X Y= AXAY ; LJ’XY

I’XY)

This follows from our theory of notation and : (AxAyAz(w’xy - = (0 E u‘xy -+ v’xy) A uz = (0 E st 2 x ,y y’xy -+ st z x ,y y’xy)) + AXAYW’XY = A t U Z )

Lemma.

Proof.

,

--f A t uz c yc = E’ab) b +A Z uz c !lab) (Az uz c w’ab) (c = a ,b -+ AxAy w‘xy c y’ab = UC) (c = a , b -+ AxAy w’xy c UC) (orderedpair is c -+ AxAy w‘xy - c uc) (- orderedpair is c -+ Axhy w‘xy U (AxAy w’xy c yc)

(c = a b

(C

.o

.1

=a ,

= uc) -

Using .O and .I we conclude

(Az uz c AaAb w’ab = AxAy w’xy - c AGuc - = Az uz).

Because of 2.65 we can now easily check: 2.67 T H E O R E M .

( V x ,y ; U’XY V’XY = VxVy ; U’XY V’XY)

Illustrative of our theory of notation are: 2.68

THEOREMS.

.O (A x n y ;u‘xy fxy

= AxAy ;u’xy v’xy)

Substitution .1 .2 .3

( A X nyu’xy=Ax,yu’xy=AxAyu’xy) (A x n y E A u‘xy = AxAy(x n y E A + l ‘ x y ) ) (V x n y E A u‘xy = VxVy(x n y E A A u’xy))

A different flavor is found in : 2.69 T H E O R E M S . U ‘ X ~= E z V X V ~ ( = Z x Uy A Y’x~)) .O (E x U y .1 ( E x U y E A Y ’ X ~= E z V X V(~z = x U y E A A -u ’ x ~))

2.70 T H E O R E M S . - -u ’ x ~ ) .O (AX ; X X Ey Y ’ X ~= EyAx ; vx .1 ( VX ;! X Ey -U ’ X ~= EyVx ;vx - -u’x~) .2 (y E U +y E Ax ; vx ux t)Ax ; vx (y E UX)) .3 (y E v x ; y x y x t ) vx; vx (y E ux)) .4 ( l l A = A x ~ A x ) .5 ( V A = vx E A x ) .6 (TlVx ;vx ux = A X ;vx TTux) .7 ( V V X ;vx Lix = v x ; vx V U-X ) - .8 (VX vx + vx u = u = VX ; vx U ) - A X ;X + AX ; !X 2 = u A VX ; vx ux = 0 ) .9 ( ~ V vx .10 (-AX ; X X ~l.y= VX ; !X - Y X ) .11 (-VX ; vx vx ~ U- X ) - _ux = AX ;.12 ( A x ; E x ( y n y x ) = A x ; W x y x n A ~ ; y-x ~ ~ ) .13 ( V x ; EX ( E X u y x ) = v x ; E X U-X u v x ; w x y x ) .14 (Ax ; wx (ux - c vx) - + AX; wx -uxc A X ; w - -uxc V x ; w x v-x ) - x-v x A V x ; wx .15 (vx + A x ; vx uxc uxc V x ; vx UX) - .16 (AX ; ( X =y) x = y = VX ; ( X =y) X ) . I 7 (Ax(ux - t)vx) + /“ c ; ux wx = A X ; vx ux wx = Vx ; y x WX) - EX A Vx ; .18 (Ax ux (y U VX) - =y u AX; ~ X X X ) .19 (Vx ux (y n vx) - = y n Vx ; yx y x ) .20 (Ax ux Ay ; vy 1 1 ‘ = ~ ~Ay ; vy AX ;ux u’x~)

.21 (VX ux vy ; y y‘xy = Vy ; yy vx ; _ ux -u‘xy)

65

2. Set Theory

66

.22 (Vx ;u x Ay ;vy - VX ; ux U’XY) - -u’xy c Ay ;vy .23 ( V A x ; vx u vx VUX) -x c AX ;.24 ( ~ A ;Xvx u x 3 Vx ; vx mu~) -

UNICITY 2.71 .O

.1 .2

DEFINITIONS. (One x u x = VyAx(yx t)x =y)) (There is j u s t one x such that y x = One x yx) (The x u x = A x ; (One x ux A yx) x)

2.72 LEMMAS. .O (One x y x A y x Proof.

-+ y z t ,

z =x)

(Ax(ux - f--) x = y) -+ (gx -+ x = y) A (yz -+ z =y) -+ (UX uz -+ x = y A z = y) - A-+ (UX A - -UZ -+ Z = X)) (Ax(ux -

tt

x =y) -+ (UX A

yz -+ z = X))

(VyAx(ux - tt x =y) -+ ( y A~y z -+ Z =X))

(One x ux -+ (yx A uz -+ z = x)) (One x g x A y x -+ (yz -+z = x)) L

Also

(One x y x A y x

-+

(z

=x

-+ UZ))

and the desired conclusion is at hand. .l

(One x x;

Proof.

A

u x -+ x = The x ux)

From .O we learn

(22 t)z

=x).

Consequently, with the help of2.70.17 and 2.70.16 we infer .2

uz z = A z ; ( z = x) z (The x ux -x x = A z ;- = Ax ; u (One x ux A u x -+ ( u z H z = The x ux))

Proof.

.3

(22 H z = x

z = The x UX)

t)

(One x u-x --f Vx ux)

= x).

67

Relations For the sake of completeness, not utility, we state:

2.73

THEOREM.

(One x ux tt Vx u x A AxAy(ux - A uy - -+ x =y))

2.74 T H E T H E O R E M O F U N I C I T Y . (One x yx -+ yx H x = T h e x ux) Proof. Because of 2.72.2

(One x u x A Vx ux uz tt z = T h e x ux). - -+Because of this and 2.72.3 (uz H

t = The

x ux).

The desired conclusion is at hand.

2.75 T H E O R E M .

(- One x ux -+ The x ux = U)

RELATIONS In connection with 2.76.19, again recall 0.62.

2.76 D E F I N I T I O N S . .O (relation is R = A x E R orderedpair is x ) .1 (relation RS = (relation is R A relation is S)) .2 (dmn R = ExVy(x ,y E R ) ) .3 (The domain of R r d m n R ) .4 (rng R = EyVx(x ,y E R ) ) .5 (The range of R = rng R ) .6 (fld R = (dmn R u rng R ) ) .7 (The field of R = fld R ) .8 (vs Rx = Ey(x ,y E R)) .9 (The vertical section of R a t x = vs Rx) .10 (The set of points which come after x under R = vs Rx) . l l (hsRy= E x ( x , y ~ R ) ) .12 (The horizontal section of R at y = hs Ry) .13 (The set of points which come before y under R = hs Ry) .14 (inv R = E x ,y (y , x E R ) )

2. Set Theory

68 .15 .16 .17 .18 .19 .20 .21 .22 .23 .24 .25 .26 .27 .28 .29 .30 .31 .32

(The inverse of R Einv R ) ( ( R: S) = E x ,y Vz(x , z E S A z ,y E R ) ) ( ( Rcomposed with S ) = ( R : S ) ) ( ( R i S) = ( S : R ) ) (rct AB E ( A ,, B ) ) (rectangle AB = rct AB) (sqr A E rct AA) (square A E sqr A ) (strc RA = ( R rct A U ) ) (strict RA = strc RA) (The restriction of R to A = strc RA) (strn RB = ( R rct U B ) ) (strun RB = strn RB) (The restriction in range of R to B = strn RB) (,RA = Vx E A vs Rx) (The image of A under R = *RA) (*RB = Vy E B hs Ry) (The inverse image of B under R = *RB)

By replacing ',' by ' ,' in the proof of 2.59.0 we obtain a proof o f 2.77

THEOREM.

(x ,y E

E x ,y u'xy et u'xy A

x ,y E U

2.78 T H E O R E M S . .O relation is E x ,y u'xy .1 relation is 0 .2 (relation is R -+ R = E x ,y (x ,y E R ) ) 2.79 T H E O R E M S . .O (relation is S A R c S -+ relation is R ) .1 (relation is R + R c S t , A x , y E R (x , y ES)) .2 (relation RS + R = S t)A x ,y (x ,y E R t)x ,y E S)) .3 (relation RS A dmn R u dmn S c A -+ R c S et Ax E A (vs Rx c vs Sx)) .4 (relation RS A rng R u rng S c B -+ R c S e t Ay E B (hs Ry c hs Sy))

)

Relations

69

2.80

THEOREMS. .O (dmn R = Ex(vs Rx # 0) A rng R = Ey(hs Ry # 0 ) ) .1 (relation is R -+ dmn R = Vp E R sng crd' p A rng R = V p E R sng crd"p) .2 (dmn R = dmn ( R sqr U) A rng R = rng ( R sqr U)) .3 ( R EU -+ dmn R E U A rng R E U) .4 (0 # A ,, B =S'+ dmn S = A A m g S = B ) .5 (relation is R -+ dmn R = 0 v rng R = 0 t+R = 0 ) .6 (sqr A = sqr B t+A = B )

2.81 .O

.1 .2 .3

THEOREMS. (dmn inv R = rng R A rng inv R = dmn R) (relation is R -+ inv inv R = R ) (R:(S:T)=(R:S):T=R:S:T) (inv ( R : S) = inv S : inv R )

( A u B ,, C = ( A ,, C ) u ( B ,,C ) = A # # C u B # # C ) .5 ( A , , B u C = ( A , , B ) u ( A , , C ) = A # # B UA # # C ) .6 ( ( A,, B ) ( C , , D )= A # # B n C # # D = A C , , BD) .4

2.82 .O

.1 .2 .3 .4

.5 .6 .7 .8 .9 .10 .ll

.I2 .13

--

THEOREMS. (strc R -A = R strc RA) (strn R -B = R strn RB) (strc R (AC)= strc RA strc RC) (strn R (BC) = strn RB strn RC) ( x E A + vs strc RA x = vs Rx) ( y E B -+ hs strn RB y = hs Ry) (relation is R A dmn R c A + strc RA = R ) (relation is R A rng R c B + strn RB = R ) (relation is R A A c C += ,. strc RC A = * R A ) (relation is R A B c C + * strn RC B = *RB) (*RA = EyVx E A ( x , y E R ) A *RB = ExVy E B (vs Rx = * R sng x A hs Ry = * R sng y ) (*RA = * inv R A A *RB = * inv R B ) (*RU = rng R A *RU = dmn R )

(X

,y

E

R))

2. Set Theory

70

.14 (*RO = *RO = 0) .I5 (,R(A uC)=,RAU*RC) .16 (*R(B u C) = *RB U *RC) .17 (*R Vx ;vx UX) _ ux _ = VX ;Y X * R .18 (*R VX ;vx ux = V X ; Y X * R :x) _ _ .I9 ( A c B + ,RA C * RB A *RA c *RB) .20 ( , R ( A n C ) c , R A n , R C ) .21 (*R(B n C) c *RB n *RC) .22 (*R Ax ;_vx -ux c Ax ; y x * R yx) .23 (*R Ax ;_vx ux UX) _ c AX ;_vx * R .24 (,R(A -C) 3 ,RA -*RC) .25 (*R(B-C) 3 *RB -*RC) .26 ( B n ,RA = * R(*RB n A ) ) .27 ( A n *RB c *R(,RA n B ) ) -28 ( A dmn R c *R,RA) .29 ( B rng R c *R*RB) .30 ( , ( R : S)A =*R,SA) .31 ( * ( R :S ) B =*S*RB) .32 (VS ( R : S ) X= * R vs SX) .33 (hs ( R : S)y = *Shs R~ J)

THEOREMS. .O (relation is R --f 0 ME R) Proof. Because of 2.63.2 (0 E R + orderedpair is 0

2.83

.1

(relation is R -+

Proof.

,-

--f

0).

orderedpair is R)

Helped by 2.63.1 and 2.24.32 we infer (orderedpair is R

0ER orderedpair is sng sng 0 --f sng sng 0 E sng sng 0 -+ sng sng 0 c sng 0 --fsngOcO -+ sng sng

3

-+O€O --f

0).

Functions

71

FUNCTIONS The notation of 2.84.7 is adapted from the lambda-notation of Alonzo Church. 2.84 DEFINITIONS. .O (function isf = (relation isf A Ax E dmn f singleton is vs fx)) .1 (functionfg = (function isf A function is g)) .2 (univalent i s f r function f invf) .3 (. fx = l l vsfx) .4 (The value off at x = .fx) .5 (-xf =.fx) .6 (Ax yx E x ,tj (tj = UX)) .7 (lonzo x ux = Ax yx) .8 (upon A isf = (function isf A dmnf c A)) .9 (on A isf = (function isf A dmn f = A ) ) .10 (upon A to B isf = (upon A is f A rng f c B ) ) .11 (on A to B isf (on A isf v m g f c B ) ) .13 (upon A onto B isf = (upon A isf A m g f = B ) ) .14 (on A onto B isf = (on A is f A rng f = B ) ) .15 ( U p o n A E E f u p o n A i s f ) .I6 (On A = E f on A isf ) .17 (To B = Efupon U to B isf ) .18 (Onto B = E f upon U onto B isf) .19 (Uto B = Ef(univa1ent isf A r n g f c B ) ) 2 0 (Uonto B = E f(univa1ent is f A m g f = B ) ) 2.85

THEOREM.

Proof.

(functionisf-tx,y€fHy=.fXAX,yEU)

From 2.6 1.O, 2.84.0, and 2.84.3 we deduce (X

u A Y E V SfX u A t j = .fX E u y =.fX A X ,?j E u).

, y Ef + + X

E

HX E

H

2. Set Theory

72

2.86 T H E O R E M S . ux A function is Ax ; yx ux) .O (function is Ax .1 (function is f --f f = Ax.fx) Proof.

(function isf + relation is f -+f = E x ,y ( x ,y ~ f ) = E x ,y (y = .fx) = Ax. fx)

.2 (function is 0 v dmn 0 = rng 0 = 0) .3 (function is g A f~ g -+ function is f) 2.87 .O

.l

.2

THEOREMS. (functionfg -+ Ax E dmn f (.fx = .gx) t--)f c g) (functionfg --+ A x E dmn f U dmn g (. fx = .gx) t ) f =g) (functionfg + Ax(.fx = .gx) ttf = g)

2.88 T H E O R E M S . .O (function is f + x E dmn f t).fx E U) .1 (function i s f + x -E drnn f t).fx = U) .2 (function i s f - t y E rng f f-) Vx E dmnf(y = .fx)) .3 (function isf -+f = Vx E dmn f sng (x , .fx)) .4 (function isf A dmn f E U +f E U A rngfE U) u x + d m n f = Ex(3x E U) A (x E d m n f - t .fx = ux)) .5 (f=Ax .6 (f=A x ; vx ux + dmnf: EX(vx - A ux - E U) A (x E dmn f + fx = ux))

.

.7

(f=AxEAux+ E A (ux - E U) A (x E dmnf + .fx = ux)) dmnf=

ux = XX .8 (AX -

EU UX)

If to each point x in A there is intuitively correlated a point yx then according to .7 there is a function which carries out this correlation. 2.89 T H E O R E M S . .O (univalent isf + univalent is inv f ) .1 (univalent isf A x E dmnf -+ invf.fx = x) .2 (univalent is f A y E rngf --f f.inv fy = y) .3 (function i s f j univalent i s f t ) AxAy(.fx = .fy E U + x =y)) .4 (univalent isf A rngfE U +f E U A d m n f e U)

. .

Ordinals

73

2.90 T H E O R E M S . .O (functionfg +f : g = Ax. f.gx) .l (functionfg A Ax E A (.fx = .gx) -+ strcfA = strc g A ) .2 (function isf A x E A -+ strcfA x = fx) .3 (function isf -+ x E *fB ++ fx E B) .4 (function isf + *f(B n C) = *fB n *fC) .5 (function isf -+ *fAx ; vx - -ux = Ax ; vx - *f-ux) .6 (function isf + *f(B -C) = *fB -*fC) . 7 (function isf -+ A n *fB = *f( *fA n B)) .8 (function is f + * f *fA = A rng f) .9 (function is f A A n *fB # 0 -+ *fA n B # 0) .10 (function isf A A c.B c rng f -+ *fA C.*fB)

.

.

.

2.91 T H E O R E M S . .O (upon sqr U is X x ,y u’xy A upon sqr U is X x ,y ; fxy u’xy) 1 (uponsqr U isf +f = A x , y . f(x , y ) ) .2 (upon sqr U isf A function is g + A x 9 Y E dmnf (.f@9 Y) = .g(x 9 Y)) -f = 9) .3 (upon sqr U isf A upon sqr U is g + A x , y E dmnfu d m n g , Y ) =.g(. ,y)) ++f=g) .4 (upon sqr U isf A upon sqr U is g -+ A W . f ( x 9 Y) = *g(x3 Y)) - f = g) .5 (f = X x , y ;v’xy u’xy -+ d m n f = E - x , ~ ( ~ ‘ x-~ A u ’ x ~ E (x,yEdmnf+.f(x,y) U)A = y’xy)) (f = X x , y E A U’XY + .6 dmn f = E X , G E A (-u ’ x ~ E UA) ( x , y E dmn f -+ .f(x ,y) = u_’xy)) .7 ( A x ,y u‘xy = X x ,y E sqr U u’xy) (sf(.

ORDINALS 2.92 D E FI NI l l 0 NS. .O (nest is N = A x E NAy E N ( x c y v y c x ) ) .1 (wellordered is N = AA ; (0 # A c N ) ( l l A E A)) .2 (strung is N = (wellordered is N A Ax E N Ay E N (x C *y t--) x E y)))

74 .3 .4

.5 .6 .7

2. Set Theory (ordinal is N = ( V N c N A strung is N ) ) (ordinal ab = (ordinal is a A ordinal is 6 ) ) ( Q =Ex ordinal is x ) (scsr x = ( x u sng x ) ) (successor x = scsr x )

2.93 THEOREM.

2.94

(wellordered is N

-+ nest

is N )

LEMMAS.

( M c N A wellordered is N + wellordered is M ) ( M e N A strung is N --t strung is M) ( A / ~ E F ( V ~ C+ BV )V F C V F A V ~ F C ~ F ) ( O # F ~ Q - + ~ ~ F E Q ) .4 (strung is N + N WE N )

.O .1 .2 .3

Proof.

( x =y = N E N + x E N A Y E N Ax EY + x c'y -+

.5

(ordinal is N

Proof.

.6 .7 .8 .9

A

x

EN

N c . N)

--f

x c.N )

Because of 2.92.3 and .4 ( x ~ N + xc V N c N + x c * N v N = x ~ N - + x c * N).

(ordinal is N A t E X E N + t C * x ) (ordinal is N A x E N + Vx c x ) (ordinal is N A x E N + x E Q ) (strung is 6 A t E b A y E b -+ t E y V t = y V y E t )

Proof.

Use 2.93 and 2.92.2.

. l o (ordinal ab A a C b A y Proof.

E

b -a

+ a c y)

From .9 and .5 we infer (t

Ea

+t E b h y E b + t Ey v y = t € a v y E t c a -+ t € y v y € a + t E y v y € a -a -+ t E y).

75

Ordinals . l l (ordinalisNhAcN-+AIlA=O)

Proof.

-

Because of .6 we learn ( t ~ A l l A - t t ~ T l A~ c E -+tEtEN -+ t c.t ) .

A

~

N

.12 (ordinal ab A a c b + a c l l ( b - a ) ) Proof.

Use .10 and 2.24.64.

.13 (ordinal a6

Proof.

A

a c.b + a 2 l l ( b -a)

E

b)

From .5 and .1 1 we infer ( A = b -a + I l A E A c b A l l A E b A llAcbcaUAA TTA=(a~A)llA=allAca~ a 2 l l A E b).

An immediate consequence of .12 and .13 is our pivotal Theorem 2.95.1 below. 2.95

.O

THEOREMS. (ordinal is N -+ N c Q) (ordinal ab A a c.b + a = l l ( b -a) E 6 )

.1 .2 Ax E QAy E Q(xC * y * x E Y ) .3 wellordered is Q Hint.

(0 # F c Q Al l F ~

-4 ( V Q c Q ) .5 ordinal is Q .6 - ( Q E U ) .7 (F c Q -+ordinal is VF)

Hint. .8

.9

( V F c VQ'Q)

( x E Q+

V scsr x = x ) (x E Q + x E scsr x E Q)

Hint.

( x c scsr x c Q)

E +FAy E F ( l l F c.y))

76

2. Set Theory

.I0 .ll .12 .I3 .I4 .I5

(VQ=Q) (OEQ) (x ~y E Q+scsr x Escsry) (X E Q A y E Q A x c y -+ scsr x c scsr y) (x c y c scsr x +y = x v y = scsr x) (sng 1 E -Q# 0)

It is a fact that (ordinal is N e , Ax ; (VXCx

C -N)(x E

N)).

Thus a more concise definition of ordinal is certainly possible. See J. R. Isbell, A DeJinition of Ordinal .Numbers, Amer. Math. Monthly, January, 1960.

DEFINITION BY INDUCTION 2.96 DEFlNITIONS. .O (Induced Rxy u’xy = (relation is RAdmn R c Q A Ax E Q (vs Rx = s t strc Rx y u’xy))) 1 ((R is induced by u’xy in x and y) E Induced Rxy u’xy) .2 (Ndc xy u’xy = The R Induced Rxy u‘xy) .3 (upon a ,f is induced by H 3 (function is HAordinal is a A upon a isf A Ax E a (.fx = .H strcfx))) .4 (ndc H a E Ndc xy (x E a A sng .Hy))

.

2.97

THEOREM. (Induced Rxy u‘xy e, relation is R A dmn R c Q A A x E Q (vs Rx = u‘x - strc Rx))

2.98

LEMMA. (Induced Rxy u’xy A Induced Sxy u’xy + R = S)

Proof. Suppose on the contrary that (0 # A Let

= EX E Q ( V SRX# V S

(4 = l-rA).

SX)).

77

Dejinition by Induction Clearly then

.O

(vs R5 # vs S5)

but

At E

Hence (t E

5 -+

5 (VS R t = vs St).

vs strc R t t = vs Rt = vs St = vs strc S t 1 ) .

Accordingly

- strc Sg'= vs Sg') - strc Rg’ = u'g' (strc R5 = strc Sg' A vs Rg’ = u'4

in contradiction to .O.

From 2.98 we see at once: 2.99

THEOREM.

2.100

u'xy + R (Induced Rxy -

= Ndc

xy u'y)

( R = Ndc xy u'xy -+ Induced R x y u'xy)

THEOREM.

Proof. Suppose

( A a (-u a = Ndc xy ( x E a A u'xy)) A S = E x ,y

( X E QA

y

- -

E U'X U X ) ) .

We divide the remainder ofthe proof into four parts, the first of which is evident. Part 0.

(relation is S A dmn S c Q A A x

Part I .

(a E Q A

Proof.

Ax

E

Let

- -

E Q (vs Sx = u'x U X ) )

a (vs Sx = y'x strc 9)-+ strc Sa = !a)

(T=strcSa).

Now on the one hand,

( x E a + strc T x = strc strc Sa x = strc S( a x ) = strc Sx + vs TX= vs SX = u'x - strc Sx = U'X - strc T x = (x E a A u'x strc T x ) ) . On the other hand,

( x E Q-a

--+ vs Tx = 0 = ( x E a A y'x strc Tx)).

78

2. Set Theory

Hence u'xy). Induced Txy (x E a A -

From 2.99 we learn

( T =!a). P a r t 2. Proof.

Induced Sxy u'xy Suppose on the contrary that

(0# A

and let

= Ex E Q (vs Sx #

u'x - strc Sx))

(5 = l-r.4).

Clearly then

(vs S.$# u't strc Sf) ;

.O

but Ax E $. (vs Sx = u'x - strc Sx).

Because of this, and Parts 0 and 1, (vs Sg = u'g - -ug = u'g - strc Sg) in contradiction to .O. Part 3. Proof.

Induced Rxy u'xy Because of Part 2 and 2.99 we conclude

(S = Ndc xy u'xy

=R A

Induced Rxy u'xy).

The general principle of definition by induction is summed up in: 2.101 THE GENERAL INDUCTION THEOREM. (Induced Rxy y'xy t,R = Ndc xy y'xy)

An easy application of the General Induction Theorem is 2.102.0 below. Since the vertical sections may not be points, the General Induction Theorem is not a special case of Theorem 2.102.0. More .demanding applications in which the Ordinary Induction Theorems are of little use can arise. See, for example, 2.182 and 2.183 wherein many vertical sections are not points.

79

Choice 2.102 T H E O R D I N A R Y INDUCTION THEOREMS. .O (function is H A ordinal is a -+ upon a ,f is induced by H t)f = ndc H a ) . l (function is H A ordinal is a A f = ndc Ha -+ dmn f = a Tl(a dmnf))

-

CHOICE 2.103 D E F I N I T I O N S . .O (2C = Xg(V rng g u sb V rng g)) . l (sbb = ndc 2C Q) .2 (subsetnest = rng sbb) .3 (nub A E sbb TTEx E Q ( A sbb x # 0)) .4 (Me1 A = ( A # 0 +-me1 ( A nub A ) ) )

.

.

2.104 T H E O R E M S . .O (dmn sbb = Q) .1 (f= sbb A x E Q A y E QA x c y -+ fx C fy)

.

Proof.

.

Let ( H = 2C) and assume ( x E y). We have (. f x E rng strcfy

.fx c V rng strcfy c .H strcfy A

=

.h).

The only use made of 2.5.9 is in verifying Part 1 in the proof of: 2.105

THEOREM.

(nest is subsetnest A V subsetnest = U)

.

Proof. Let ( N = subsetnest). From 2.104.1 it is clear that nest is N Letting (f= sbb) and ( H = 2C) we divide the remainder of the proof into three parts. Part 0.

Proof.

(y E sb V N +y

E

VN)

Let

(4 = XS E y 7 7EX E Q ( S E .f~))

80

2. Set Theory

and use 2.95.3 in checking

(6 E Ony To Q A (SEY

+SE.f.(S)

(s E y

+ sng s c .f.(s)).

Let

A

( A = rng t)

and note that

(A E U

A

V AE

QA

scsr V A E Q).

Helped in the last step by 2.104.1, check that

( y = Vs Eysngs C v s E y f.& = Vs E y Vt E sng .& ft = Vt E Vs E y sng &.ft = Vt E A . f t c.f V A ) .

.

.

Accordingly

( y ~ s b . Vf A ) . Now

(. f V A E rng strcf scsr V A A

.f V A c V rng strcf scsr V A y sb .f V A c sb V rng strcf s a r V A A

E

c .H strcf scsr V A f scsr V A c Vx E Q.f x = V rngf

=.

=VNA yE VN).

Part 1 . ( - V N #

0 -+ 0 )

Proof. Use 2.5.9 to so secure y that (yE -VNAy

CN

- V N = V N A ~ E sb V N ) .

Next employ Part 0 to conclude

( y E V N AE ~- V N A Y E O A 0 ) .

81

Maximulity Port2.

(VN=U)

Proof.

Use Part 1.

With the help of 2.105, 2.95.3, and 2.104.0 we check : 2106 LEMMAS. .O ( A # 0 +-Ex E Q ( A sbbx # 0) # 0) .1 (A=O+ExEQ(A.Sbbx#O) = 0 ) .2 (A # 0 +nub A E U A A nub A # 0) .3 (A = O +nubA = U )

.

In checking 2.107.0 we use 2.5.8 for the first time. 2.107 THEOREMS. .O (A#O+melAEA) .1 ( A # 0 --t Me1 A E A nub A .2 ( A = O - t M e l A = U ) -3 ( B c A +nub A c nub B)

A

nub A

E

U)

Hint. Use 2.104.1.

21W T H E T H E O R E M OF C H O I C E . VP E U AA ; ( z E A) (Me1A

E

AP)

Proof. From 2.107 we infer

(P = nub sng z + P E U A AA ; ( z EA)(sng z c A A Me1 A E A nub A + P E U A A A ; (zEA)(MelAEAP)).

2109 D E F I N I T I O N S . .O (hereditary is F = AuAB ; (ac B E F ) (aE F)) .1 (nestling is F = (hereditary is F A AN E sb F ; nest is N ( V N E F ) ) ) 2.110 D E F I N I T I O N S . .O (adjoinable Fg = Et E -rng g (mg g

u sng t E F))

AP)

a2

.1 .2 .3

2. Set Theory (adjoiner F = Xg Me1 adjoinable Fg) (nestbuilder F E ndc adjoiner F Q) (nesterFE Vx E dmn nestbuilder F sng * nestbuilder F scsr x )

2.111

D E F I N I T I O N . (capped is F E AN; (nestis N A N c F ) V Z ( V N ~ Z E F ) )

2.112 D E F I N I T I O N S . .O (nested R is ,9 = (sqr ,9 c Ax E fld R x u R u inv R ) ) .1 (cap RA = Ex E fld R ( A c hs Rx Ay E vs Rx hs R y ) ) .2 (capped R = A/3 ; nested R is ,9 (cap R,9 # 0)) .3 (maximal R = Ex E fld R (vs Rx c hs Rx))

Weshallnotuse2.111 and 2.112 unti12.116. It is easy to check: 2.113 .O

.l

.2 .3 .4 2.114

LEMMA. (K = nestbuilder F -+ ordinal is dmn K A ( x E Q -+ .Kx = Me1 adjoinable F strc Kx) A ( x E dmn K -+ .Kx E adjoinable F strc Kx A .Kx -E rng strc Kx A m g strc Kx u sng .Kx E F ) ) LEMMA. ( N = nester F A K = nestbuilder F -+ univalent is K A nest is N A N c F A V N = rng K )

Proof. Using 2.1 13.3,

( y E x E dmn K -+.Ky E rng strc Kx

-+ .Ky

# .Kx).

Consequently univalent is K Since ( N = Vx E dmn K sng *K scsr x ) , it is evident that nest is N

Also

( N = Vx E dmn K sng * K ( x u sngx) = Vx E dmn K sng (,Kx u sng .Kx) = Vx E dmn K sng (rng strc Kx u sng X x ) ) .

Maximality

83

Because of 2.1 13.4 we now know ( Nc F ) . Also (rng K

3

Vx E dmn K (rng strc Kx u sng .Kx)

=VN

Vx E dmn K sng .Kx =rngKA rng K = VN). 3

We shall now establish the very powerful5: 2.115

M A X I M A L PRINCIPLE. (nestling isFA N = nester F + n e s t i s N ~N c F A - V T c F ( n e s t i s 7 A V N c . Vv))

Proof. The first two conclusions follow from 2.1 14. Let

( K = nestbuilder F). I n order to complete the proof by showing

-Vq c F (nest is 7 A V N c.V7) we assume the contrary, so choose 7 that

(7c F A nest is 7 A V N c.Vq), and so determine z that (2 E

Vq -VN).

In accordance with the Theorem of Choice we so choose P that

.o

( P E U A AA ; ( z E A)(Mel A E A P ) )

and in a four step argument infer in contradiction to 2.95.6 that (QE U). Step 0. Proof.

( x E Q + rng strc Kx

u sng z E F)

Let ( B = rng strc Kx u sng z A 7' = V P

E

77 sng (BP)).

Since (rngstrc K x c rng K = V N c V7

A

zE

V7)

5 Note that N is maximal in the strong sense that F includes no other nest which covers more. Because of 2.120 we feel that the existence ofsuch a maximal N is not an easy consequence of Hausdorff'sMaximal Principle.

2. Set Theory

a4

we are sure

(B

VT).

Evidently (nestisq’h ~ c F A Vg‘ = Vg E q (BB) = B V g E q

Consequently

(q’ E U Step I . Proof.

A

B = B Vq = B E U).

9’E sb F A B = vq

E F).

( x E Q --f z E adjoinable F strc Kx)

Since ( z E -VN =

-

mg K c

we infer from Step 0 and 2.1 10.0 that

-

rng strc Kx)

.

( z E adjoinable F strc Fx)

Step 2. Proof.

(x

E Q + .Kx E

P)

From .O, Step 1, and 2113.1, we infer (.Kx = Me1 adjoinable F strc Kx E P).

Step 3. Proof.

(QEU)

From Step 2 we infer (dmn K

= Q Arng K c

P

E

u A m g K E u).

Since according to 2.1 14 univalent is K ,we now conclude from 2.89.4

(Q=dmn K E U). Obviously we have: 2.116

THEOREM. (AN; (nestis N A N c F ) ( V N F ) +cappedisF)

It should be fairly clear that (nested R is t, B c fld R A Ax E B Ay

E

( x =y v x ,y

ER

v y ,x

E R)).

We now establish a modification of Hausdorff’s maximal principle.

85

Maximality 2.117

THEOREM. (F = Ea nested R is a A B = V nester F --f nested R is B A -VB(nested R is A B c./I))

Let

Proof.

( N = nester F )

and note

.O

(nest is r ]

A r]

c F +-nested R is Vr])

and also

.1

b A nested R is b + nested R is a).

(a c

Thus nestling is F and our Maximal Principle assures us

.2

(nest is N

A

N c F A -Vr] c F (nest is r ]

From .2 and .O we infer nested R is B

.

A

V N c -vr])).

In order to show

-V/I(nested R is /I A B

p)

C.

we assume the contrary, so choose /3 that (nested R is /3

A

B c -B),

let (7’ = V a E subsetnest sng (pa)),

and in contradiction to .2 infer from .1 and 2.105 that (nest is 9’A T ’ C F AV N = B

B =Vq’).

C.

An immediate consequence of2.117 is the following modification of a lemma due to Kuratowski.

2.118

THEOREM.

VB(nested R is B A -Vp(nested R is /3

A

B c -B))

By letting ( R = s q r F E x , y (xcy)) we see that a special case of 2.1 18 is: 2119

HAUSDORFF‘S M A X I M A L PRINCIPLE. V N ( n e s t i s N ~ N C F ~ - V r l ( n e s t i s r l A q c F AN c - 7 ) )

2. Set Theory

86

‘That 2.1 18 is not a simple consequence of Hausdorff’s Maximal Principle is, we think, brought out by the easily checked: 2.120

(R =sqr U A F = U A B = N = Q A F = EU nested R is u A nest is N A N c F A -Vq(nest is 77 A 77 c F A N C -77) A B = V N Anested Ris p A B C -p)

THEOREM.

p=U+

Often it is existence, rather than maximality, which is of prime importance; therefore interesting and efficient is the following inductive6 modification of Zorn’s lemma. 2.121 T H E O R E M . ( A = fld R A capped R A Ax E A m CVy(x ,y E R-invR) Proof.

.O

+ A C # 0)

With the help of 2.1 17 we so choose B that (nested R is B A -Vp(nested R is p A B

8)).

C.

Since capped R ,we choose ( x E cap RB)

.1

and complete the proof by verifying that ( x E AC).

Suppose on the contrary -(x

E AC).

Since .1 and 2.1 12.1 guarantee that ( x E A ) we now know that (x E A

-C).

-

In accordance with our premise we so choosey that .2 Because of .1 and 2.112.1, .3

( x ,y E R

inv R).

( B c hs Rx).

6 In 2.12 1 the last part of the premise assurea us that if we have not yet found what we are looking for, then at least we can advance a step and look again.

87

Maximal$ Because of .2, . I , and 2.1 12.1,

( Bc hs Ry). Hence nested R is ( B u sng y)

.

According to this and .O, .4

EB).

(Y

Using .4, .3, and .2 we conclude (y , x E R Ax ,y E inv R

-

inv R = 0).

Next we have a noninductive modification of Zorn’s lemma.

2.122 THEOREM. Proof.

(capped R + maximal R # 0)

Let

( A = fld R A C = maximal R ) and check

Ax E A

rn

C Vy(x, y

ER

-

inv R ) .

Now apply 2.121 to learn

(0 # AC = C ) .

Very useful is: 2.123

T H E I N D U C T I V E PRINCIPLE OF I N C L U S I O N .

(capped is F A Ax Proof.

K Vy(x

EF

C.y E F )

+FK # 0)

Let

( R =sqr F A=FA C = K).

E x ,y ( x c y)

Notice ( A = fld R

A

capped R

A

Ax

EA

-

A

C Vy(x ,y

ER

-

inv R ) )

2. Set Theory

8a

and then apply 2.12 1 to learn

(0# AC = F K ) . The Inductive Principle of Inclusion can be proved in many ways. It follows easily, for example, from Hausdorff's Maximal Principle.

WELL ORDERING 2.124 DEFl NlTlO NS. .O (The Q inception of B = EE E /3 (/?c vs .I ((Q wellorders A) = (relation is Q A A/? ; (0 # /3 c A) singleton is The Q inception of p ) ) l The 52 inception of /?)) .2 (The Q start of ,k? = l . 3 ((Q orders A) = Ax E A Ay E A A z E A (Q wellorders {xyz})) .4 (Mel' = nestbuilder U) .5 (Melorder E E x ,y (. inv Mel' x c inv Mel' y))

at))

.

2.125

THEOREMS.

.O (A c B A Q wellorders B + Q wellorders A)

( x ~ / ? ~ A ~ Q w e l l o r d e tr=sTAh ~ eQstartof/?-+ ,k? c vs Qx t)x = 5) .2 (0 # /? c A A Q wellorders A A = The Q start of -+ E E B = vs QE) .3 (Q = E x ,y (x c y) --i,wellordered is A t)Q wellorders A) .4 (0wellorders A + 52 orders A) .5 (Q orders A + ( x E A A y E A +-x , y €52 v y ,x E Q)) .6 ( Q o r d e r s A + ( x E A + x , x E S Z ) ) .7 (Qorders A -+ (x E A A y E A A x , y E Q A y ,x E G + x = y ) .8 (Q orders A + ( X E A A YE A A z E A A x ,y E Q A Y , Z E Q + x , ZED) .1

2.126

THEOREM. (univalent is Mel'

A

dmn Mel'

= QA

rng Mel'

= U)

89

Well Ordering Proof.

Let (F=UA K = nestbuilder F A N = nester F).

From 2.124.4 we learn (K = Mel’). From 2.1 13.0 we learn

.O

.

ordinal is dmn K

From 2.1 14 we learn (univalent is K A rng K = VN). Now let

(r]=

subsetnest). According to 2.105 (nest is 7 A

V7 = U).

Since (nestling is F A 77 c F ) it follows from our Maximal Principle that

( V N-c* V T A V N -c* U A rng K

= V N = U).

Since 2.88.4 assures us (dmn K

we conclude from .O that

E Q+

U = rng K E U)

(dmn K = Q).

2.127 T H E W E L L O R D E R I N G T H E O R E M S .

.O .1

(Melorder wellorders U) (y E U + hs Melordery E U)

2.128 T H E O R E M . (Q wellorders A A Ay E A (hsQy E U) -+ One f (univalent isf A ordinal is dmn f A A = rng f A A a E dmnJ’A/3 E dmn f (a c /3 -+.fa,.ft?

a)))

2.129 T H E O R E M . (ordinal ab A on a to b isf A Aa E a A P .O Aa E a (aC.fa) A .1 a c 6)

Ea

(.fp

E .fa)+

2. Set Theory

90

NATURAL NUMBERS 2.130 DEFl N I T I O N S . .O (naturalnumberclassis A = (0 E A A Ax .1 (w = AA ; naturalnumberclassis A A ) .2 (naturalnumber is n = (n E w))

EA

(scsr x E A ) ) )

2.131 DEFl NlTlONS. .O ( 1 ~ s c s 0) r .1 (2 Escsr 1) .2 (3 = scsr 2) .3 (4 ~ s c s 3) r .4 (5 ~ s c s 4) r .5 (6 zscsr 5) .6 (7 = scsr 6) .7 (8 ~ s c s 7) r .8 (9 s s c s r 8) 2.132 THEOREMS. .O naturalnumberclass is w -1 ( w c Q )

Theorems 2.133 are the Peano axioms for natural numbers.

2.133

.o

.1 .2 .3 .4

THEOREMS.

(OE

0)

(x E w -+ scsr x E w) (x E w --f scsr x # 0) (x E w A Y E w A scsr x = scsry - f x = y ) (0 E SC w A A x E S (scsr x E S) + S = w )

2.134 T H E O R E M .

( w = Vw)

Proof. Let (S=wsbw).

91

Sequences We have (X

E S 4X EW A X c W -+ sng x C w A x C w

+ scsr x

=x U

sng x C w

-+ scsr x E w A scsr x C w -+ scsr x E S).

Since (0 E S) we are assured by 2.133.4 that (S = w ) . Thus (x

E w -+ X

Consequently

c w) .

(Vw = w ) .

On the other hand

( x E w - + x E scsr x E w + x

E Vw).

Accordingly ( w = Vw).

2.135

THEOREM.

Use 2.95.7, 2.132.1, and 2.134.

Proof.

2.136

ordinal is w

THEOREM.

Hint.

(0 # x

E w -+ scsr

Vx =x)

Let (S = w Ex(0 # x

-+ scsr

V x = x))

and show that (S= w ) by virtue of 2.133.4.

SEQUENCES 2.137 DEFl N I T I O N S . .O (sequence is S = on w is S) .1 ( s q n c A Z E S o n w t o A i s S ) .2 (sequence A = sqnc A ) .3 (ndc’ ha 3 ndc Xg(g = 0 A a v p # 0 A .h.g V dmn g) w) .4 (ndc”Su = ndc Xg(g = 0 A a v g # 0 A ..S V dmng .g V dmny) Since (h

U + X n h = 0),

2.137.3 is not a simple special case of 2.137.4.

w)

2. Set Theory

92

2.138 THEOREMS. .O (u E U +f= ndc' hut--) function isf A (dmnfE w v dmnf= .fO = u A An E w (. f scsr n = .h.fn))

w) A

Proof. Recall the Ordinary Induction Theorems.

.1

.2 .3

( a E U -+f = ndc" Su t)function isf A (dmnfE w v f0 = u A An E w (.Jscsr n = ..Sn.fn)) (a E G A

(u E G A

.

on G to G is h -+ on w to G is ndc' ha) S E sqnc (On G To G) + on w to G is ndc" Su)

2139 T H E O R E M . Proof.

dmnf= w ) A

(wEQ)

Use 2.5.6 to so secure (C E U) that

(0E C AAx € c (sng x E c)).

Let

(6 = X

x E C sng x

f = ndc'

to)

A

and divide the remainder of the proof into six parts. PartO.

Proof.

(S=wEn(.fn=.fO+n=O) - t S = w ) Clearly (0 E S ) . Also

(n E S +.f scsr n = sng. fn # 0 =. f 0 f scsr n #. f 0 + (.f scsr n f 0 + s a r n = 0) A scsr R E o

+.

=.

+ scsr n E S).

Consequently because of 2.133.4 (S = w ) . Port 1.

An E w (. fn

Proof.

USePartO.

Part2. Proof.

=.f0 - + n = 0 )

( S = w EmAn E w (. f n

=.fm + n =

From Part 1 we infer (0 E S). Now

m) + S = w )

(m E w~ 0 E n E o + f scsr m =sng. fm A fn f scsr Vn = sng. f Vn)

. . =.

93

Reiteration and hence

( m e s hO#nEw + (. f V n = . f m -+ V n = m) + (sng f V n = sng f m -+ n = scsr Vn = scsr m) + (. f n =.fscsr m -+ n = scsr m)).

.

.

Using Part 1 again

=.f scsr m -+ n = scsr m)).

( m E S A 0 = n E w -+ (. f n

Consequently (m E S

A

n E w -+ (. fn

Thus (S= wj.

Part3. Proof.

Part4. Proof.

( m E w A n E w -+ (. f n

=

.f scsr m -+n = scsr m ) ).

=.f m -+ n = m))

Use Part 2. (W

EU)

We see univalent isf by Part 3. Since according to 2.138.2 on w t o c i sf

we conclude from 2.89.4 (rngf

Part5 Proof.

C

C E U A rng f

EU

A

w = dmn f E U).

(wEQ)

Use Part 4 and 2.135.

REITERATION 2.140

DEFINITION.

2.141

THEOREMS.

.O

(reit Tn =Ax. ndc' Tx n)

(function is T +

/ \ x E U / \ n E w (.reit TOx=xh.reit T1 x = . T x ~

.reit T ~ x = . T . T x A .reit Tscsrnx=.T.reit Tnx))

94 .l

.2

2. Set Theory (function is T A n E w + reit TO =Xxx A reit TI = T A reit T scsr n = T : reit Tn) (function is T --+ Vn E w reit Tn 0 = V n E w reit T scsr n 0 )

.

Hint.

.

(. reit TO 0 = 0 )

SET FUNCTIONS AND FIXED POINTS Herein we follow the lead of Tarski and Knaster.

2.142 DEFI NITIONS. .O (includive is T = (function is T A Ay E dmn T Ax E dmn T n sb y (. T x c Ty))) .1 (inclusive = E T includive is T ) .2 (expansive N = ET E T o U (ordinal is N A 2 c N A Af; (on N to dmn Tisf A includive isf) (.TVXEN.~~=VXEN.T.~~))) .3 (unitive N = E T E T o U (ordinal is N A 2 c N A A f ; on N t o dmn T i s f ( . T V x E N . f x = V x E N.T. f x ) ) ) .4 (complementative A EE E T E T o U ( A E dmn T AAx E dmn T (.T(A -x) = .TA -.Tx)))

.

2.143

THEOREMS.

N + expansive N c expansive M A unitive N c unitive M ) .1 (2 c N E scsr w A f E O n N --f includive isf t)An E V N (.fn C.f scsr n)) .2 ( 2 c n E w -+ expansive 2 = expansive n A unitive 2 = unitive n) .3 (unitive N c expansive N c expansive 2 = inclusive) .4 ( V = S : T + (S E inclusive A T E inclusive -+ V E inclusive) A (S E expansive N A T E expansive N --f V E expansive N ) A (S E unitive N A T E unitive N + V E unitive N ) ) .O

(2 c M

E

Set Functions and Fixed Points

.5 ( V E T O U A E E U A W=Xa(EU.Va) -+ (WEOndmn V)A ( V E inclusive --+ W E inclusive) A ( V E expansive N --f W E expansive N ) A ( V E unitive N + W E unitive N ) ) 2.144 T H E O R E M . ( A u B E U A T = X x c A ( B *Rx) -+ .O ( TE unitive Q O n sb A To sb B ) A .1 (function is inv R A a c A --+ T E complementative a)) T H E O R E M . (TEinclusiveTodmn T A F = Ea(. Tu c u) A P = V n E w reit Tn 0 A P' = l-TF 3 .O (P' E dmn T -+ .TP' = P') A .1 (0 E dmn T --+ P E sb P') A .2 ( T ~ e x p a n s i v e w ~ O ~ dTm+n. T p = P = P ' ~ d r n n T))

2.145

Proof.

.

Note at the outset that

(Fc dmn T). We verify .O by checking that

(P' E dmn T + A a E F (P' c u) --+AuEF(.TP'c.Tuca) + Au E F (. TP' c a) +.TP'c TTF + .TP' c P' +.T. TP'c.TP' +.TP' E F +P'=TTFc.TP' +.TP'=P'). With the help of2.141.0 and 2.133.4 we verify .3 (0 E dmn T --f A n E w (. reit T scsr n 0 3 . reit Tn 0 E dmn T))

and .4

(0 E dmn T A a E F -+ An

Ew

(. reit Tn 0 c u)).

95

2. Set Theory

96

We verify .1 by checking, with the help of .3 and .4,

(0 Edmn T - t P E U A ha E F( P c a) -+ P E u h P C n F = P' A PE sb P'). Next we notice with the help of .3, 2.143.1, 2.141.0, 2.141.2, and .l, that .5

( T E expansive w

A

0 E dmn T -+ .TP =.T Vn E w .reit Tn 0 = Vn E w .T.reit T n 0 = Vn E w .reit Tsar n 0 =PEU).

We now verify .2 by checking, with the help of .5 and .l, that

( T Eexpansive w A 0 E dmn T

2.146

+.TP

= P E dmn T +PEF +P'cP -+p’=P).

T H E O R E M . ( T E expansive w To dmn T A 0 E dmn T A F = Ea(. Ta c a) A P = Vn E w .reit Tn 0 A P' = nF -+ .TP = P = P' E dmn T)

Proof. Use 2.145.2 and 2.143.3.

2.147 T H E O R E M . (TEinclusive O n Sb A To s b A A F = Ea(.Tac a ) A B = TTF + .TB = B E sb A ) Proof. Since

(.TA

E

sb A )

it is clear that

( A E F AB E s b A ) . The desired conclusion now follows from 2.145.0. 2.148 T H E O R E M . (S E O n sb A To s b A'

D =.S'A'

A

S' E O n s b A' T o sb A A

A

T = X a c A (A -.S'(A'

-.Sa))

A

Set Functions and Fixed Points

97

V=S':SA W=X~(A-DU.V~)A

F = Ea(.Tuc a) A B = TTF A B' = .SB A C' = A ' -B' A C =.S’C’ -+ .O ( T ~ O n s b A T o s b A A) .1 (W~onsbATosbA)~ (S E inclusive A S' E inclusive + T E inclusive) A .2 .3 (S E inclusive A S' E inclusive + W E inclusive) A .4 (S E expansive N A S' E expansive N --+ W E expansive N) A .5 (S E unitive N A S' E unitive N + W E unitive N) A (S'E complementative A' -+ T = W) A .6 .7 (B'C' = 0 A A' = B' U @) A .8 (S E inclusive A S' E inclusive + BC = 0 A A = B u C ) A .9 ( S E expansive o A S' E expansive w complementative A' + B = V n E w .reit Tn 0)) Proof.

Notice first that ( V E On sb A T o sb A)

and use 2.143.5 in checking . l . After checking .O and .2 directly we easily infer .3, .4, and .5 from 2.143.4 and 2.143.5. Now

(S' E complementative A' A a E sb A . Ta = A -.S’(A’ -.Sa) =A (.S'A -.S'.Sa) = A - ( D -.Va) = A --D u A .Va = A - D u.Va = Wa)

-

4

.

and .6 is at hand. Clearly

(B'C'=O

A

B' u C’ =A'B' u A' - B ' = A ' )

and .7 is at hand. Because of .2, .O, and 2.147

(S E inclusive A S' E inclusive --+ T E inclusive On sb A To sb A

2. Set Theory

98

+ .TB = B E sb A + B =.TB = A -.S’(A’ - S B )

= A -.S(A’ -B’) = A -.S'C' =A-C -+ B = A -CA BC= 0 A B u C = A -C u AC= A )

and .8 is a t hand. Because of .6, .4, .1, and 2.146,

(S E expansive w A S' E expansive w complementative A’ -+ T = W E expansive w On sb A To sb A --f B = Vn E w .reit Tn 0)

and .9 is a t hand.

2.149 T H E T H E O R E M OF B I P A R T I T I O N . (rng R c A’ E U A rng R ' c A E U A S = X u c A ,Ra A S' = L a c A’ ,R’a A T = A u c A ( A -.S(A’ -.Sa)) A F = Ea(.Ta c a ) A B=TTFAB’=.SBA C’=A’NB’AC=.SC’ + (BC = 0 = B’C’ A .O A = B u C AA’= B’ u C’ A ,RB = B’ A ,R’C’ = C ) A (function is inv R’ + B = Vn E w reit Tn 0)) .1

.

Proof.

According to 2.144.0

(S E unitive Q O n sb A T o sb A’ A S' E unitive Q o n sb A’ To sb A). Also, because of 2.143.3 and 2.143.0, (unitive Qc expansive Qc expansive w c inclusive). Hence we can infer .O from 2.148.7 and 2.148.8, and we can infer .1 from 2.144.1 and 2.148.9.

EQUINUMEROSITY 2.150 D E F I N I T I O N S . .O ( ( Aeq B ) = V f ; univalent isf (dmnf= A . l ( ( Ais equinumerous with B ) = ( A eq B ) )

A

rng f = B ) )

Equinumerosity

99

2.151 T H E O R E M S . .O (Aeq A ) .1 (A eq B + B eq A) .2 (A eq B eq C --f A eq C) .3 (A eq 0 t)A = 0) 2.152 T H E O R E M S . .O ( B eq B' A C e q C' A BC=O = B’C’ -+B U C e q B’ .1 ( B e q B ' A C e q C ' - t r c t B C e q r c t B ' C ' ) .2 (univalent isfA A c dmnf + A eq ,fA) .3 (function i s f - t d m n f e q f )

( A eq B

EU

+A

U

E U)

2.153

THEOREM.

2.154

T H E CANTOR-BERNSTEIN THEOREM.

(Dc A

EU A

D ’ c A'

A

C’)

A eq D'A A'eq D + A eq A')

Proof. Note that 2.153 assures (A' E U). The desired conclusion now follows from 2.152 and the Theorem of Bipartition.

Remark. The Cantor-Bernstein Theorem is, of course, simpler in statement than the Theorem of Bipartition. However, the latter reveals a simple explicit mechanism which is useful in other contexts. By using the General Induction Theorem it is possible to salvage the effective content of the Theorem of Bipartition under the altered assumptions that

(rngRcA'~rngR'cA). Thus an effective proof is indeed possible of the statement

( Dc A

A

D'c A' A A eq D’ A A' eq D

--f

A eq A ' ) .

Except for the above statement and the altered Theorem of Bipartition which we have in mind, we know of no interesting reward for the extra effort.

2.155

LEMMA.

(s E

A

A t EB A

A eq B - + A

-

sng s eq B

N

sng t )

2. Set Theory

100

CARDINALS 2.156 DEFINITIONS. .O (cardinal is a = (ordinal is a A A/3 E a - ( a eq B ) ) ) 1 (cardinal aB = (cardinal is a A cardinal is 8)) .2 (C = Ea cardinal is a)

.

2.157 LEMMAS. .O (cardinal aB A CL eq B + a = 8) .1 (cardinal a/3 A a c y eq fl -+ a c /3) Proof. Recalling the Cantor-Bernstein Theorem we see

(fl

E

a + Va' c a +-aeqB

(B eq E ' ) A V/3' c /?( a eq B')

+a=/3AacP).

But ordinal aB and therefore (acfivPEa).

.2

B E a A cardinal a/3 A ordinal is y According to 2.156.0 and .1 ,

( y eq

Proof.

(ordinal ay

hence ( y E a).

A

a

-+

y E a)

y);

2.158 THEOREMS.

.o

(0c

C)

Hint. 2.155.

.1

(w

EC)

Proof. Using 2.157.2 we see

cardinal is w -+ V n ( w eq n E w A w eq n E scsr n A cardinal n scsr n A ordinal is w w Escsr n c w A w E W A 0 ) ) .

(-

.2

(w c

/3

E Q+

scsr /3

E

-

A

C)

Proof. ( f = X x ~ / ( 3x = O A j3 v 0 E X E w A V X Vw c x A x ) + univalent isf A dmn f = /3 A rng f = scsr 8) . 3 cardinal is Q

Cardinality

CARDINALITY 2.159 .O

.1 .2 .3 .4 .5 .6 .7 .8

DEFINITIONS.

(pwr A = ( Q l l E a ( A eq a E Q))) (power A = pwr A ) (The cardinality of A = pwr A ) (finite is A = (pwr A E w ) ) (fnt = EA finite is A ) (infinite is A = (pwr A 2 w ) ) (countable is A = (pwr A c w ) ) (cbl = EA countable is A) (denumerable is A = (pwr A = w ) )

2.160 DEFl N I T I O N S . .O (2D A = (TT dmn A , .A T l dmn A)) .1 (2E A = 2D (A sqr T r E t E Q ( A sqr t # 0 ) ) ) .2 (2F =Xf2E (sqr Q- rngf)) .3 (Sq = ndc 2F Q)

We shall not use 2.160 until 2.167. 2.161 T H E O R E M S . .O cardinal is pwr A .1 (A eq B -+ pwr A = pwr B) .2 (ordinal is a + a eq pwr a c a) .3 (cardinal is a + pwr a = a) .4 (A eq a A cardinal is a + pwr A = a) .5 (pwr A E Q + A eq pwr A ) .6 ( A c 6 A ordinal is b + A eq pwr A c 6)

Hint. .7 .8

Use 2.125.3, 2.128, 2.129.1.

( A eq C c Q+ A eq pwr A ) (AcB+pwrAcpwrB)

Hint.

(pwr B

=Qv

pwr B E Q)

101

102

2. Set Theory

.9 (A c Ceq B --+ pwr A c pwr B) .1O (A eq C C B -+ pwr A c pwr B) .1 1 (upon Q i sf -+ pwr r n g f c pwr dmnf )

Hint.

Let

,12 (function isf

(g = Xy -+

IT hsfi).

pwr r n g f c pwr dmnf = pwr f )

Among the above .6 and .l 1 are incidental. The principle of choice is involved in 2.162-2.165.

2.162 T H E O R E M . Proof.

VCC Q ( A eq C)

Use 2.126.

2.163 T H E T H E O R E M S OF C A R D I N A L I T Y . .O ( A e q p w r A ) .1 (A eq B t,pwr A = pwr B) 2.164 THEOREMS. .O (0 $- A A ordinal is a -+ pwr A c a t,Vf on a onto A isf) .l (ordinal is a -+ pwr A c a t)Vf(on a isfA A c rngf)) 2.165

T H E O R E M . (Ax E A (pwr A c pwr UX) --+ Vg(univa1ent is g A Ax E A ( . ~ x - E UX)))

2.166 THEOREMS. .O (pwr A = n E w A x E -A -+ pwr (A u sng x ) = scsr n) sng x ) =Vn) .1 (pwr A = n E w A x E A +pwr (A .2 (A E fnt A B E fnt -+ A u B E fnt) .3 (FE fnt sb fnt -+ VF E fnt)

-

2.167 Hint.

LEMMA.

(0 # A c sqr Q-+ 2D A E A)

Recall 2.84.3.

2.168 THEOREMS. .O (univalent is Sq A dmn Sq = Q Arng Sq = sqr Q A Ax E Q ( * S q sqr x E Q)) . l (ordinal is a -+ a C *Sq sqr a) Hint. Use 2.90.10, 2.129.0, and .O.

103

Cardinality 2.169

(pwr sqr w

THEOREM.

= w)

Let

Proof.

( y = *Sq sqr w).

Notice that (sqr w = V n E w sqr n A y

=Vn E w

*Sq sqr n).

We know from 2.166.3 that ( n E w -+ sqr n

E

fnt).

Hence because of 2.168.0 (n E w

-+ *Sq

sqr n E w).

Consequently ( y c w) and, because of 2.168.1, (y=w Remark.

A

sqr w =*Sq w

A

pwr sqr w

= w).

It can be seen without much trouble that

(cardinalisah w ~ a - + s q r a = * S q U A p w r s q r a = a ) . We again use the principle of choice in : 2.170 Proof.

(F E cbl sb cbl -+ V F E cbl)

THEOREM.

Let

(H = F - l )

and recall that

(1 =sngO).

Clearly

.o

(VF = V H U V ( F " H )

=V H U

0 = VH) .

Since the desired conclusion is evident in the event ( H = 0), assume ( H # 0). Use 2.164.0 to choose (h E On

w

Onto H ) .

Aided by 2.164.0 and the principle of choice select such a function g that Let

(g E On w

A

An

Ew

(.gn

E On

w

Onto .hn)).

(f= A m ,n E sqr w ..gmn).

104

2. Set Theory

Evidently

(fE On sqr w Onto V H ).

According to .O, 2.161.12, and 2.169 (pwr V H c pwr sqr w = w ) . The next three theorems, which are of interest in themselves, lead up to 2.174. 2.171

(y E U -+ O n y To 2 eq sby)

THEOREM.

Taking

(f

=xXX

A

y=

u)

we see that 2.172 generalizes 2.38. 2.172 T H E O R E M . (ony isf A a = E x ( x E - . f x ) Proof.

( t E a f--f t

E

-.It

Hence (ac y) and ( t ~y

A

.ft=

t ~y

t)

A

t

+y

-E

2

a -E rngf)

.ft)

a + t E at) t - E

a

Accordingly (a E rngf-t

V t ( t E Y A .ft

+O).

= a) + VtO

+ 0)

and the desired conclusion is at hand. According to 2.172, a is such a subset of the domain off that a does not belong to the range off. 2.173

THEOREM.

-Vf

E Ony

(sby c rngf)

The principle of choice is involved in proving: 2.174 Proof.

CANTOR’S POWER T H E O R E M .

(Y E Q + y

E pwrsby)

Use 2.164.1 and 2.173.

I n 2.175 we formulate two special cases of the principle of choice. 2.175.0 is the finite principle of choice and 2.175.1 is the countable principle of choice. 2.175.0 is to be proved without the principle of

105

Cardinal Arithmetic

choice; however 2.175.1 cannot be proved without the principle of choice.

-

2.175 THEOREMS. ' .O ( F E fnt sb 1 --f V E' . l (F E cbl sb -1 + V

E

B)

O n F A 8 E F (.fp E ) O n F A P E F (.fp E p ) )

CARDINAL ARITHMETIC 2.176 DEFl NITIONS. .O ( ( a @ p ) = p w r E x , y ( x E a ~ .1 ( ( a 0/I)= pwr rct aB) .2 ( O a B = pwr (On /I To a ) ) .3 (exponential CL to the /3 = " a p ) 2.177 T H E O R E M S . .o ( a @ / 3 = / 3 @ a ) .1 ( ( a 0 8 )O r = a

= yo V x E p h y = 1))

0 (B BY)= a OB 0Y)

.2 ( a O B = / I O a ) .3 ( ( a 0B) 0 y = = 0 0Y)= 0 .4 ( ( a @ / % O y = a O y O B O y )

(B

2.178 T H E O R E M . ( a E C A /3 E C A y .O 0.B 0Oay = O a @ y ) A .1 Oay O o B y = O ( a OF)Y A .2 ooapy = O a 0y ) )

(B

B 0Y) EC

+

(B

2.179 T H E O R E M .

(w c a E C + a @ a = a

-

0 a = a E O2a = Oaa)

The famous hypothesis of the continuum asserts (020 = l l ( C

scsr w ) ) ,

that is, 02w is the smallest cardinal larger than w . We are not at all sure that Godel's approach7 can be used here to show the consistency of the hypothesis of the continuum. 7

See the sentence preceding 2.6 on p. 44.

106

2. Set Theory

2.180 T H E O R E M S .O ( A B = O + p w r ( A u B ) = p w r A @ p w r B ) .1 (pwr ( A u B ) c pwr A @ pwr B ) .2 (n E w + n @ 1 = scsr n)

DIRECT EXTENSIONS Suppose (on A isf A B = To A -A -1). If we wish to extend the domain off so that it becomes ( A u B ) then it is natural to so determine F that (on ( A U B ) is F A f c F

A

A z E B (.Fz

.

=f : z))

And there is no need to stop here! Our interest in direct extensions of this sort motivated 2.181-2.183. Definition 2.181.5 is of value, for example, in extending addition and multiplication functions. Theorems 2.182 and 2.183 help us evaluate the result. In checking 2.182 and 2.183 the Ordinary Induction Theorems fail us but the General Induction Theorem does not.

2.181 D E F I N I T I O N S . .O (noz R = (R= 0 v R ) ) .1 (domonde AO = Ndc xy ( A u Ez E dmn O ( x # 0 A rng .8z c Vt E x vsyt))) .2 (domo ABx = vs domonde AOx) . 3 (dom A0 = V x E Q d o m o AOx) .4 (drexndcfAO = Ndc xy (f u Vt E x vs yt u X Z E domo AOx V t E x domo ABt noz ( x # 0 A V t E x vsyt : .Oz))) .5 (drexfAO = Vx E Q v s drexndc f A 8 x ) .6 (The direct extension off beyond A via 8 = drex fAO)

-

2.182 T H E O R E M . (D= dom A8 + A c D = A u EtEdmnO(rng.OzcD))

107

Families of Sets 2.183 T H E O R E M . (function isf A dmn f c A A D = dom A0 A F = drexfA0 -+ function is F A f C F A dmn F C D A A z E A (. f z =.Fz) A A z E D A (.Fz =noz ( F : .&)))

-

FAMILIES OF SETS 2.184

DEFl NIT10 NS.

(disjointed is F = Aa E F A p E F ( a = p v ap = 0)) (dsjn = EF disjointed is F ) .2 (dsn' F E VG E fnt n dsjn n sb F sng V G ) .3 (V’F = V G E fnt n sb F sng V G ) F = V G E fnt n sb F sng ( V F TTG)) .4 (ll' .5 ( - ’ F = V f l E F s n g ( V F - p ) ) .6 (dsn" F = VG E cbl n dsjn n sb F sng V G ) .7 (V"F = VG E cbl n sb F sng V G ) 8 (TT" F = VG E cbl n sb F sng ( V F TTG)) .9 (V- F = VG E sb F sng V G ) .10 ( l T F = V G E sb F sng ( V F TTG)) .11 (bore1F = (sb V F TTEG 2 F (V"G = T l " G = G ) ) ) .12 (Bore1F = (sb V F TT EG 2 F (V"G = -' G = G ) ) ) .13 (topology= ET(T=V- T = TT' T ) ) .14 (( T topologizes A ) = ( T E topology A v T = A ) ) .15 (diskompact = EFAH E fnt n sb F ( V H # V F ) ) ,16 (kompact = EFAH c F ; ( V H = V F )( H E diskompact)) .17 ((G c~ F ) = A a E G V p E F ( a c p)) .18 ((Gis a refinement ofF) = (G cc F ) ) .19 (refined is F = A H E cbl n s b F V G Ecbl n dsjn n s b F ( G c c H A V G = V H ) )

.O .l

-

2.185

THEOREMS.

.O ( F c V’ F c V"F c V - F ) .1 ( F c T T ’ F c T T " F c T F )

108

2. Set Theory

.2 .3 .4 .5

(OEV’F) (FEU-+VFETT’F) ( F c G + V’F c V’ G A V "F c V " G A V - F c V - G ) (FcGhVF=VG+ T T ’ F c l l ' G ~l l " F c TT"GA T T F c n - G ) .6 ( F ~ G A V F = V G + - ’ F C - ’ G ) .7 ( V ’ F = s n g O u V G E n t n s b F - 1 s n g V G A V"F=sngOuVGEcblnsbF- 1sngVGA V - F = s n g O u V G E s b F - 1 sngVG) .8 (TT’F=sng V F u VG E nt n s b F - 1 sng ~ G A TT" F = sng V F u V G E cbl n sb F - 1 sng TTG A ll-F=sngVFuVGEsbF1 sngllG) .9 ( V - F U T T - F u - ’ F c s b V F ) .10 ( V V ’ F = V V " F = V V - F = V F ) .11 (Vll’F = V l l " F = V T F = V F ) .12 (V-IF c V F ) .13 ( V ’ V ’ F = V ’ F AV " V " F = V " F A V - V - F = V - F ) .14 (TT' TT' F = TT' F A ll"11"F = TT" F A ll-TT- F = ll- F ) .15 ( A a E F ( V F - a E G ) + - ’ F c G ) .16 ( a E F E U + V F - a - ’ F ) .17 ( a E - ’ F + V F -a E F E U ) .18 (-’F c F E U t,- ' F =F ) .19 ( F E U +-' ( F U s n g 0 ) =-IF u sng V F A -' ( F u sng V F ) =-’F u sng 0 ) .20 ( F E U + V--’ F = V F -TTF) .21 ( O # F E U - + T T - ’ F = O ) .22 ( - ’ - ’ F = F t ) V - ’ F = V F ) .23 ( - ’ - ’ F = F + + F E U A VFllF=O) .24 (0 E F E U -+ -' -IF = F ) .25 ( F E U - + - ’ ( F U - ’ F ) - F u - ’ F ) -26 (-' -' - ’ F = - ’ F ) .27 (0 # G C F A V G E F U sngO -+ V G E F ) .28 (0 # G c F A l l G E F u sng V F +-l l G E F )

109

Families of Sets .29 .30 .31 .32 .33 .34 .35 .36 .37 .38 .39 .40 .41 .42 .43 .44 .45 .46 .47 .48 .49 .50

(V’F=FusngOttAaEFABEF(aUBEF)) ( l l ’ F = F u sng V F e t A a E F A B E F ( a n B E F ) ) ( V " F = F u sng 0 tt AG E cbl n sb F 1 (VGEF)) ( l l " F = F u sng V F t t AG E cbl n s b F - 1 (TlG E F ) )

-

(N’-’F=F+N’V’F= TT’N’FAN’V"F= TT"N’FA N' V - F = n- N ’ F ) (N' N' F = F + N' n ’ F = V ' - ’ F A -' ll"F = V" N ’ F A N' n-F = V - N' F ) ( F -E U + borel F = Borel F = sb V F ) ( F c borel F C Borel F ) (V borel F = V Borel F = V F ) (V"borel F = TT" borel F = borel F ) (-' Borel F c V" Borel F = 11"Borel F = Borel F ) (F c G A V F = V G --+ borel F c borel G) ( F c G A V F = V G --+ Borel F c Borel G) (borel borel F = borel F ) (Borel Borel F = Borel F ) (-' -' F = F --+ -' Borel F = Borel -' F ) (N' -' F = F -+ N' borel F = borel N' F ) (N' F c borel F t)borel F = Borel F ) (FE U --+ Borel F = VG E cbl n sb F Borel (G u sng V F ) ) ( F E U --+ borel F = VG E cbl n sb F borel (G u sng V F ) ) ( V G c A + borel (G u sng A) c sb V G u sng A ) ) (-' F c borel F E U -+ V F E V " F )

2.186

THEOREMS.

2.187

THEOREM. (F E topology t)AG c F ha E F Ap E F ( V G E F

V - ll'F = V - l l'F ) .O (ll' l'F topologizes V F ) .1 ( F E U --+ V - l

2.188 THEOREMS. .O (diskompact c kompact) 1 ('7-F E kompact t)F E kompact)

.

N

A

aB E F ) )

2. Set Theory

110 Hint.

Use 2.175.0

A certain amount of effort may be required to check the beautiful: 2.189 T H E O R E M .

(V- TT'F E kompact t)F E kompact)

--

I n connection with 2.190 recall 0.62. 2.190

.O

.I

.2 .3

Hint.

T H E O R E M . (F K - mK c K A KnnKcKh K U U K ~ K A refined is F)

F c dsn'F = K +-

Notice first that (dsn' K

u

-

F c dsn' F).

TUPLES We shall use 2.56 and 2.57. 2.191 DEFl NIT10NS. .O (bsdmn x = Et (bsvs xt # 0) ) .1 (tuple is x = (basicrelation is x A At E bdsmn x (bsvs xt = ss V bsvs x t ) ) ) .2 (tuple u is x = (tuple is x A bsdmn x = u ) ) .3 (crd tx E V bsvs x t ) .4 (The t coordinate of x = crd t x ) 2. I92 DEFl NlTlO NAL SCHEMAS. .O We accept as a definition each expression obtained from

'( (x , ~ y = ) (tuple is x

A

A t E bsdmn x

(crd t x ~ y) )) '

by replacing ' E' by a nexus which is not a comma.

.1

We accept as a definition each expression obtained from

' (Each coordinate of x ~y

= ( x , ~ y ) ')

by replacing ' E' by a nexus which is not a comma.

Tuples

111

2.193 DEFl NlTlO NS. .O ( ( x , x' , x") = ( (x , x') u (sng 2 ss x") ) ) . 1 ( ( x , x' , x" , x"') = ( ( x , x' , x") u (sng 3 ,I ss x " ' ) ) ) .2 ( (x ,x' ,x" ,x"' ,x"") = ( ( x ,x' ,x" , x") u (sng 4 ,,ss x"") ) ) etc. 2.194 THEOREMS. .O (tuple a is x A tuple a is y + x = y tt At E a (crd tx = crd ty) ) . 1 ( x = V t E a (sng t ,/ ss ut) -+ tuple a is x A At E a (crd tx = ut) ) .2 (tuple a is x +- V V V x = V a u V t E a crd t x ) .3 (crd t ( x u y ) = crd tx u crd ty) .4 (tuple is x A tuple is y +tuple is ( x u y ) A tuple is ( x n y ) A crd t ( x n y ) = crd tx n crd ty) .5 (crd' x = crd Ox A crd" x = crd I x ) .6 (p = 0 + tuple 0 isp A crd tp = 0) .7 (p = sng 0 ss x + tuple 1 isp A crd Op = x ) .8 (p = x ,x' --f tuple 2 isp A crd Op = x A crd Ip = x') .9 (p = x , x' , x" -+ tuple 3 isp A crd Op = x A crd Ip = x' A crd 2p = x") .10 (p = x , x' , X" , x'" +- tuple 4 isp A crd Op = x A crd lp = x' A crd 2p = x" A crd 3p = x"') etc. The usefulness of 2.192 is illustrated by :

2.195 THEOREMS. .O ( x , y ,E A t t x E A A Y E A ) .1 ( X , y + Z , t , < U t t X < U A y + Z < U A t < a ) u " x y z t t A x E A Ay E A A t E A u"xyz) .2 ( A x , y , z ,E A -

This Page Intentionally Left Blank

APPENDIX

THE CONSTRUCTI0N OF DEFINITIONS Definitions are, as we have said before, more than mere shorthand devices. Since we accept8 formulas of this sort as theorems we should use care in making them. For example if to our present definienda we were in some way to add ‘ f ( x )’ then many resulting formulas would be unreadable. I n particular if,

‘( f ( x )= .fx) ’ were added to our list of definitions then it should be easy for anyone familiar with Chapter 2 to show that ‘ (0 = 1) ’ is a theorem. O u r definitions are constructed in accordance with the agreements and rules below ; we suggest that the reader bear these in mind when he formulates new definitions of his own.

THE STRUCTURE OF BASIC FORMS I n this section we presuppose terminological familiarity with only the Introduction which begins Chapter 0. A.0 AGREEMENT. definiendum.

AisbmicifandonlyifAiseither‘(x=y)’ora

As in 0.7 we make: A.l AGREEMENT. a is a n introductor if and only if a is a constant which is the initial symbol of some definiendum. A.2 AGREEMENT. a is a connector if and only if a is a constant which is not a schemator and some definiendum can be obtained from 8 If, however, a definition, or even an axiom, is not a formula, then it is not accepted as a theorem. 113

114

A. The Construction of Definitionr

‘xy’ by replacing ‘x’ by a symbol and ‘y’ by an expression in which a appears. A.3 AGREEMENT. tor and a connector.

a is afianker if and only if a is both an introduc-

A.4 AGREEMENT. S is a signature of A if and only if there is such an expression Q, devoid of schemators, that A can be obtained from Q by replacing variables by schematic expressions, and S can be obtained from Q by replacing each variable of Q by ‘ x ’ .

Thus ‘ (x + x)’ is a signature of both ‘ (x + A ) ’ and of ‘ ( z +y) ’, ‘x’ is a signature of both ‘ uy ’ and ‘_~“xyz’, ‘Axx’ is a signature of ‘Ax v’yy’ and the expression ‘ uvx’ has no signature. I t should be fairlyclear that an expression can have at most one signature. A.5 RULE. A is a basic form if and only if A either is a primal expression or is a definiendum corresponding to which there is such a simple expression F that: no schemator appears in F ; every variable which appears in A also appears in F ; and A can be obtained from F by replacing variables which do not appear in A by schematic expressions. A.6 RULE. If A is a basic form then in A no schemator appears more than once. A.7 RULE. If a is a flanker and A is a basic form in which a appears then A can be obtained from ‘xyx’ by replacing ‘x’ by ci and ‘y ’ by some expression B for which: ci does not appear in B ; the terminal symbol of B is a variable; and in some signature of B, ‘x’ is not adjacent to ‘x’. A.8 RULE. If A and A‘ are diverse basic forms which are not schematic, then there are such expressions S and S‘ that S is a signature of A , S’is a signature of A‘, and S is not an initial segment of S’. A.9 RULE. If A is a basic form, B and C are schematic expressions which are segments of A , and a is a variable, then a appears in B if and only if a appears in C.

Conformity of our definitions to A.0-A.8 assures the variability of primal symbols, the constancy of the opening parenthesis, the unique readability of formulas, the mechanical soundness of our language, the

The Structure of Dejinitions

115

harmony of all our rules and agreements, and the precision of our descriptions of formulas and theorems. If, in nonconformity with A.5, our whole set of definitions were to consist of the expressions enumerated in 0.0 together with the seemingly innocent expression ‘ (A* u‘xx = Ax u’xx) ’ then, as the reader may easily check, ‘x’ would be both free and not free in ‘A* u‘xx’. We shallcomment later on the rather interesting role played by A.9.

THE STRUCTURE OF DEFINITIONS In this section we shall give rules of definition which though sometimes complicated in formulation are for the most part followed instinctively by any cautious constructor of definitions. Throughout the remainder of this appendix we presuppose termino1ogicalCamiliaritywith the material preceding and following the Theory of Notation, and with 0.31.0 and 0.51. Here we are primarily interested in mathematical, rather than mechanical, soundness of our language. We want to make sure, for example, that unwanted theorems must arise from axiomatic rather than linguistic .defects. A.10 RULE. Parentheses, the semicolon, binarians, and notarians are constants; in particular, ‘ +’ and ‘A’ are constants. A.11 RULE. The lightface italic Latin letters together with the superscripted and subscripted symbols derived therefrom are variables. A.12

RULE.

Every primal expression is a primitive form.

A.13

RULE.

Among the forms are ‘ (x + x ’ ) ’ and ‘Ax ux’.

At this stage it seems pleasanter to endow A.14 with a symmetry which not only smooths our present path but also makes each formula parenthetical. A.14

‘(X ~

RULE.

If D is a definition then D can be obtained from

y’ by ) replacing ‘x’ and ‘y’by formative parenthetical formulas.

116

A. The Construction of Definitions

A.15 RULE. If D is a definition and a is a schemator then some formula in which a does not appear can be obtained from D by schematically replacing some schematic expression by ‘x ’. A.16 AGREEMENT. S is a child of D if and only if D raises a n expression of which S is a signature. A.17

RULE.

If S is a child of D and of D ’ , then D is the same as D’.

I n other words, a n expression is the child of at most one expression. A.18 AGREEMENT. a is bound in A if and only if a is a variable and A can be obtained from some formula in which a does not occur by replacing free variables by formulas in which a is indicial. Thus in each of the expressions

‘ Vxx’, ‘ (y -+ Ayy) ’, ‘ (y -+ Vx ux) ’, ux -+ Axy)’, ‘ V x E y x’, ‘Vy E Y y’, ‘(Ax ‘ x ’ is bound and, except in the first, ‘y’is not. A.19

RULE.

If a definition is obtained from ‘ (x ~ y’ by ) replacing

‘x’ by A and ‘y’ by B then: every variable is either free in B or bound in B; a schemator appears in A if and only if it appears in B; a variable appears precisely once in A if and only if it appears in B and is free therein; and if a variable is indicial in A then it is bound in B. A.20 AGREEMENT. B is a constituent of A if and only if B is a strict formula and there are such a formula Q and such a variable a that u appears precisely once in Q, and A is obtained from Q by replacing a by B. A.21 AGREEMENT. T is a progenitor of A if and only if there are such formulas B and F that: B is a constituent of A; F is a fundamental formula from which B can be obtained by replacing free variables of F by formulas; and T is a signature ofF. A.22 AGREEMENT. T is a forebear of D if and only if D is a definition and there is such an expression B that D can be obtained from ‘(x =y)’ by replacing ‘ x ’ by an expression and ‘y’ by B, and T is a progenitor of B.

Adherence and Translatability

117

A.23 AGREEMENT. T is an ancestor of S if and only if there is a definition of which S is a child and T is a forebear.

A.24 AGREEMENT. D is an antecedent of A if and only if D has a child which is a progenitor of A. We now use 0.76 and 0.9.

A.25 AGREEMENT. R is a tree if and only if R is a chain and corresponding to each link A of R, each ancestor T of A, and each such subchain P of T that P ends with A, there is such a chain Q that R is (PQ)and T is a link of Q. If D is the definition

‘ (-p = (p -+ 0 ) ) ’ then: D is the only definition of which ‘ N X ’ is a child; the ancestors of ‘NX’ are the forebears of D,which in turn are the progenitors of ‘ (p --f 0)’; the constituents of ‘(p --+ 0 ) ’ are ‘(p --f 0 ) ’ and ‘ 0 ’ ; the progenitors of ‘ (p --+ 0) ’ are ‘ ( x -+ x ) ’ and ‘0’; the ancestors of ‘ N X ’ are ‘ ( x --f x ) ’ and ‘0’; of these, the first has no ancestor and the second has the one ancestor ‘ A x x ’ ; ‘ A x x ’ has no ancestor; finally ‘ N X ’ is a link of the tree

‘1- X 1 ( x + x ) I0 4 A x x ’ . A.26 link.

RULE. If S is a child of D then there is a tree of which S is a

A.27

RULE.

Every antecedent of an axiom is also a n axiom.

A.28 REMARK. Systems which fail to comply with A.27 have a spurious simplicity. If two systems are to be compared, it is highly desirable that they both comply with A.27. Noncompliance has been the fundamental cause underlying certain anomalies.

ADHERENCE AND TRANSLATABILITY A.29 AGREEMENT. F is a formulaclass if and only if F is a class of formulas, each variable belongs to F, each schematic form belongs to F, and C is in F whenever A and B are such members of F and C is such a

118

A. The Construction of Dejinitionr

formula that either C is a variant of A, or C is a constituent of A, or C is obtained from A by replacing some free variable of A by B, or C is obtained from A by schematically replacing some schematic expression by B. A.30 AGREEMENT. (formulas G) consists of those formulas A such that A belongs to each formulaclass of which G is a subfamily. A.31 AGREEMENT. F is a consequenceclass if and only if F is such a class of formulas that C is in F whenever A and B are such members of Fand Cis such a member of (formulas F) that Cis entailed by A and by B. A.32 AG REEMENT. (consequences G) consists of those formulas A such that A belongs to each consequenceclass of which G is a subfamily. If G is any family of formulas then (formulas G) is a formulaclass, (consequences G) is a consequenceclass, G is a subfamily of (consequences G), and (consequences G) is a subfamily of (formulas G). A.33 AGREEMENT. We agree that F adheres to G if and only if each member of (consequences F) which is a member of (formulas G) is also a member of (consequences G) . Thus F adheres to G if and only if ((formulas G) n (consequencesF) c (consequences G)). A.34 AGREEMENT. A is proper if and only if A is a form with a signature different from ‘ x ’ . A.35 AGREEMENTS. .O A is salient if and only if A is such a proper primitive form that some progenitor of an axiom is a signature of A. .1 A is pristine if and only if A is a proper primitive form which is not salient. A pristine form awaits, so to speak, either definitional clarification or axiomatic elucidation. A.36 AGREEMENT. can be obtained from

We agree that A is annexed if and only if A

‘ (y = Axx) ’ by replacing ‘y’ by a pristine form.

119

Adherence and Translatability

Although annexed formulas are not to be thought of as definitions we nevertheless could easily, in conformity with our rules, so additionally designate as definitions certain of our present formulas that no form would be pristine and each presently annexed formula would become a theorem. Our salient forms actually are :

‘ (x E x’) ’, ‘me1 x’. ‘ (x =y) ’, ‘ (x + x’) ’, ‘A x ux’, Of these the second is lifted by 0.0.3, the third by 0.0.4, and the fourth by 2.0.1. It might be noticed in this connection that 0.0.3,0.0.4, and 2.0.1 are also made into definitions by the Theory of Notation. A.37 AGREEMENTS. 0 A is our set of axioms. 1 X consists of those formulas which are either axioms or definitions. .2 W consists of those formulas which are either axioms or definitions or annexed formulas. .3 S is our set of salient forms.

.

A.38 AGREEMENT. We agree that A translates into G if and only if a member of (consequences W) can be obtained from ‘ (x 3y) ’ by replacing ‘x’ by A and ‘y’ by a member of (formulas G). Remark. We have tried to so formulate the above rules that conformity of our definitions thereto will ensure, among other things, that X adheres to A and each formula translates into S.

If, in defiance of A.9, we were to include

‘ (A* xy ux y = AxAy(_wc+ xy)) ’

among our definitions, then

‘A* xy u’xy v’xy’ would become a formula which would not translate into S. If on the other hand, in conformity with our rules, we were to include ( (A* xy u’xy v‘xy -

E

AxAy(u‘xy - + v’xy)) -

among our definitions, then

‘ (A* xy ux - y = AxAy(ux - -+y)) ’,

would clearly become a theorem.

’

This Page Intentionally Left Blank

INDEX OF CONSTANTS An unindexed usage found in a section and unexplained earlier therein is probably explained by the Theory of Notation. 3-5 6 0.0.0 17 0.36 6 0.0.0 17 0.36 6 0.0.0 6 0.0.2

6 0.0.1 6 0.0.3 33 1.0.15 6 0.0.1 23 0.56 33 1.0.4 107 2.184.5 33 1.0.9 22 0.49 33

1.0.7

33 1.0.10

#

42 2.1.20 42 2.1.22

l-r

ll' ll"

TT-

42 2.1.14 42 2.1.22 42 2.1.17

107 2.184.8 107 2.184.10

n U

42 2.1.30 42 2.1.32

E

51 2.33.0

{

51 2.33.2

1

51 2.33.2

107 2.184.7 107 2.184.9

60 2.55 60 2.55 51 2.33.2 68 2.76.16

1

Y

42 2.1.11 42 2.1.20 107 2.184.17

107 2.184.4

42 2.1.28 107 2.184.3

41 2.0.0 42 2.1.9

42 2.1.26

V V' V V-

33 1.0.12 41 2.0.1

42 2.1.19

#

*

*

60 60 110 111

2.56.0 2.57.1 2.192 2.193

60 2.57.3 68 2.76.29 68 2.76.31 71 2.84.3

121

122

Index of Constants 71 2.84.6

@

0

105 2.176.0

2.142.2

105 2.176.1 105 2.176.2

o

eq 98 2.150.0 expansive 94

90 2.130.1

Ad 67 2.76.6 fnt 101 2.159.4 function 71 2.84.0 71 2.84.1

adjoinable 81 2.1 10.0 adjoiner 82 2.110.1

hereditary 81 2.109.0

basicorderedpair 60 2.56.2 basicrelation 60 2.56.3 bore1 107 2.184.11 Bore1 107 2.184.12 bsdmn 110 2.191.0 bsvs 60 2.56.4

inception includive inclusive induced

c

100 2.156.2

cap 82 2.112.1 capped 82 2.111 2.112.2 cardinal 100 2.156.0 100 2.156.1 cbl 101 2.159.7 complementative 94 2.142.4 crd 110 2.191.3 crd' 60 2.57.6 crd" 60 2.57.8

hs

67 2.76.11

Induced inv 67

88 94 94 76

2.124.0 2.142.0 2.142.1 2.96.1 76 2.96.3 76 2.96.0 2.76.14

kompact 107 2.184.16

82

disjointed 107 2.184.0 diskompact 107 2.184.15 dmn 67 2.76.2 dom 106 2.181.3 domo 106 2.181.2 domonde 106 2.181.1 drex 106 2.181.5 drexndc 106 2.181.4 dsjn 107 2.184.1 dsn' 107 2.184.2 dsn" 107 2.184.6

maximal 82 2.112.3 me1 41 2.0.0 41 2.0.2

Me1 79 2.103.4 Mel' 88 2.124.4 Melorder 88 2.124.5 naturalnumberclass 90 2.130.0 ndc 76 2.96.4 ndc' 91 2.137.3 ndc" 91 2.137.4 Ndc 76 2.96.2 nest 73 2.92.0 nestbuilder 82 2.1 10.2 nested a2 2.112.0 nester 82 2.110.3 nestling 81 2.109.1 noz 106 2.181.0 nub 79 2.103.3

Index of Constanb on 71 2.84.9

71 2.84.11 71 2.84.14 On 71 2.84.16 One 66 2.71.0 onto 71 2.84.13 71 2.84.14 Onto 71 2.84.18 orderedpair 60 2.57.5 orders 88 2.124.3 ordinal 74 2.92.3 74 2.92.4

point 42 2.1.6 psb 51 2.33.4 psp 51 2.33.6 pwr 101 2.159.0 Q 74 2.92.5 rct 68 refined reit 93 relation rng

2.76.19 107 2.184.19 2.140 67 2.76.0 67 2.76.1 67 2.76.4

sb 51 2.33.3 sbb 79 2.103.1 scsr 74 2.92.6 set 41 2.1.0 singleton 57 2.50.1 sng 42 2.1.34 sngl 57 2.50.0 sp 51 2.33.5 s q 101 2.160.3 sqnc 91 2.137.1 sqr 68 2.76.21 ss 60 2.57.0

st 23 0.57.0 23 0.58

start 88 2.124.2 strc 68 2.76.23 strn 68 2.76.26 strung 73 2.92.2 subsetnest 79 2.103.2

The

66 2.71.2 to 71 2.84.10 71 2.84.11 To 71 2.84.17 topologizes 107 2.184.14 topology 107 2.184.13 tuple 110 2.191.1 110 2.191.2

u

33

1.0.6

unitive 94 2.142.3 univalent 71 2.84.2 Uonto 71 2.84.20 upon 71 2.84.8 71 2.84.10 71 2.84.13 76 2.96.3 Upon 71 2.84.15 Uto 71 2.84.19

vs 67 2.76.8 wellordered 73 2.92.1 wellorders 88 2.124.1

0

33

1.0.3

1 90 2.131.0

2 90 2.131.1 3 90 2.131.2

4 90 2.131.3

123

This Page Intentionally Left Blank

GENERAL INDEX Note that many ordinary words are listed in the Index of Constants.

A

119 A.37.0 accepted 7 10 31 0.81.1 accepted-free-link 31 0.80.3 accepted-schematic-link 30 0.80.1 accepted-start 31 0.80.5 Accepted Variables 10 Adherence and Translatability 117 adheres 118 A.33 agreements 7 Amalgamation, Theorem of 56 2.45 ancestor 117 A.23 and 33 1.0.8 annexed 118 A.36 antecedent 117 A.24 associative laws 38 1.5.2 1 38 1.5.27 47 2.24.14 47 2.24.15 69 2.81.2 105 2.177.1 105 2.177.3 axiom 3 12 0.24 117 A.27 Axioms Definitional 33 1.1 43 2.2 43 2.3 for Logic 34 1.3 for SetTheory 43 2.5 ofDefinition 34 1.2 43 2.4 basic 113 A.0 Basic Forms, Structure of

113

basic ordered pair

60 2.56 60 2.58 basic relation 60 2.56 61 2.59 Bernstein, F. xxvii 99 2.154 betwixt 18 0.41 binarian 16 0.31.0 binariate 16 0.31.1 Bipartition, Theorem of 98 2.149 bisegment 19 0.42 Boole, G. Boolean Algebra 47 2.24.18 47 2.24.7 47 2.24.22 47 2.24.11 47 2.24.13 47 2.24.15 47 2.24.20 47 2.24.17 47 2.24.16 47 2.24.19 47 2.24.14 47 2.24.12 47 2.24.21 47 2.24.8 47 2.24.18 bound 116 A.18 Cantor, G. xxvii 99 2.154 104 2.174 Cantor’s Power Theorem 104 2.174 Cantor-Bernstein Theorem 99 2.154 Cardinal Arithmetic 105 Cardinality 101 Theorems of- 102 2.163 125

126 Cardinals 100 Cartesian product

General Index 59 68 2.76.19

chain 29 0.76.0 Chains 29 child 116 A.16 choice, principle of 43 2.5.8 Choice 79 Theorem of - 81 2.108 Church,A. 71 71 2.84.7 class xxvi class 22 0.50 Classification 5 1 Theorem of - 52 2.35 combinatorial 25 0.62 commutative laws 37 1.5.12 38 1.5.26 39 1.6.8 39 1.6.9 47 2.24.12 47 2.24.13 48 2.24.56 48 2.24.57 65 2.70.20 65 2.70.21 105 2.177.0 105 2.177.2 complementation 33 1.0.4 41 2.1.3 46 2.20.0 complicate 20 0.47 composition 68 2.76.16 68 2.76.18 concatenation 8 0.9 conjunction 33 1.0.7 connector 113 A.2 consequenceclass 118 A.31 consequences 118 A.32 constant 4 constituent 116 A.20 construction of definitions 113-1 17 coordinate 60 2.57.7 60 2.57.9 110 2.191.4 110 2.192.1

countable

101 2.159.6 103 2.169 103 2.170

definiendum 4 definition 3 12 0.24 113-1 19 Definition, Axioms of 34 1.2 43 2.4 Definition by Induction 76 Definitions, Structure of 115 definor 3 demonstration 29 0.74 Demonstrations 27 De Morgan, A., laws of 38 1.5.23 38 1.5.24 47 2.24.19 47 2.24.20 47 2.24.23 47 2.24.24 65 2.70.10 65 2.70.11 denumerable 101 2.159.8 detachment 13 0.25 Direct Extensions 106 disjunction 33 1.O. 10 distribution, axiom of 43 2.5.2 distributive laws 38 1.5.30 38 1.5.31 39 1.6.12 39 1.6.13 47 2.24.16 47 2.24.17 49 2.24.61 49 2.24.62 65 2.70.18 65 2.70.19 105 2.177.4 diverse 5 domain 67 2.76.3 double-chain 31 0.80.6 doubleton 60 2.55.1

General Index each 33 1.0.2 emptyset 41 2.1.1 33 1.0.3 ends 29 0.76.2 enlisted 29 0.73 entailed 27 0.70 equality, axiom of 43 2.5.5 definition of - 42 2.1.17 Equality, Some Aspects of 49 Equinumerosity 98 equivalence 33 1.O. 12 evolves 3 existential quantification 33 1.0.15 expression 1 Expressions 2 extension 18 0.40 Extensions, Direct 106 Extent, Theorem of 45 2.11 false 42 2.1.8 Families of Sets 107 field 67 2.76.7 finite 101 2.159.3 102 2.166 fixed 4 Fixed Points 94 flanker 114 A.3 forebear 116 A.22 form 5 formalization 7 formative 3 formula 7-10 7 0.3 formulaclass 117 A.29 formulas 118 A.30 Formulas 7 framed 3 free 7-10 32 0.83 free-chain 32 0.82.2 free-link 31 0.82.0 free-start 31 0.82.1 Free Variables and Formulas Frege, G. xxvii Functions 71 fundamental 8 0.6

7

G a e l , K.

127 44

105

Hausdorff, F. xxvi-xxvii 84 85 2.117 85 2.119 Hausdorff’s Maximal Principle 85 2.119 Heredity, Theorem of 55 2.43 hypothesis of the continuum 105 if and only if 33 1.O. 13 If. . .then 33 1.0.0 6 0.0.2 image 68 2.76.30 inverse68 2.76.32 implication 6 0.0.2 33 1.0.1 implicator 4 inclusion 42 2.1.11 42 2.1.14 proper42 2.1.20 42 2.1.22 Inclusion, Inductive Principle of 87 2.123 indicia1 7 10 31 0.81.0 Indicia1 and Accepted Variables 10 indicial-free-link 30 0.80.2 indicial-schematic-link 30 0.80.0 indicial-start 31 0.80.4 induction 76-79 90 2.133.4 92 2.138 Induction, Definition by 76 General - Theorem 78 2.101 Ordinary - Theorems 79 2.102 inductive 86 2.121 Inductive Principle of Inclusion 87 2.123 inference 3 7 12-15 27-29

I28 Inference, Rules of 12 infinite 101 2.159.5 infinity, axiom of 43 2.5.6 initiation 12 0.24 intersection 42 2.1.24 6 0.0.3 42 2.1.27 42 2.1.31 46 2.20.2 43 2.5.3 axiomof43 2.5.3 introductor 8 0.7 113 A.l inverse 68 2.76.15 - image 68 2.76.32 Isbell, J. R. 76 Kelley, J. L. xxvii 63 Knaster, B. xxvii 94 Kuratowski, C. xxvii 52 2.37.9 52 2.37.10 65 2.70.0 65 2.70.1 85 85 2.118 language

1-32 113-1 19 law of Leibniz 43 2.5.4 laws associative commutative De Morgan distributive left 19 0.45.0 - enlargement 19 0.46.0 Leibniz, G. W. 44 law of - 43 2.5.4 Leiniewski, S. xxvi lifts 4 logic 33-40 50 tukasiewicz, J. 35

General Index march 2 3 0.52 mark 1 mathematics 7 Maximal Principle 8 3 2.1 15 maximal principle of Hausdorff 85 2.119 Kuratowski 85 2.118 Morse 83 2.115 Zorn 87 2.122 Maximality 81 membership 41 2.0.1 41 2.1.4 42 2.1.9 - sign 4 metamathematics 7 minimal 19 name 1 Natural Numbers 90 negation 22 0.49 33 1.0.4 33 1.0.5 33 1.O.Y nest 73 2.92.0 subsetnest 79 2.103.2 nexus 16 0.32 Not 33 1.0.5 notarian 22 0.51 Notation, Theory of 15 noun 8 0.8 Numbers, Natural 90 or 33 1.0.11 order 23 0.55 Ordered Pair Theorems 63 2.61 Ordered Pairs 59 ordering 88 2.124.3 88 2.125 8 2.124.1 wellOrdinals 73

parade 17 0.33 parenthetic 3

General Index parenthetical 3 parenthetical-chain 32 0.84.1 parenthetical-link 32 0.84.0 Peano,G. 90 -axioms 90 2.133 Peterson, D. C. xxvii 59 point 42 2.1.6 xxvi power 17 0.34 power 101-1 06 101 2.159.1 prefix 8 0.10 primal 5 prime importance 19 0.44 primitive 5 118-1 19 118 A.35.0 principle of choice 43 2.5.8 pristine 118 A.35.1 progenitor 116 A.21 proper 118 A.34 punctuator 3 quantification, existential 33 universal - 6 0.0.3 33 1.0.2 quotation marks 1-2

I .O. 15

raises 4 range 67 2.76.5 rectangle 68 2.76.20 reducible 9 0.12 refinement 107 2.184.18 regularity, axiom of 43 2.5.9 Reiteration 93 relation, basic 60 2.56 61 2.59 Relations 12 Replacement 1 Schematic6 replacement, axiom of 43 2.5.7 Replacement, Role of 53 Theoremof54 2.41

restriction

68 2.76.25 68 2.76.28 revised system 44 right 19 0.45.1 - enlargement 20 0.46.1 Rudiments 3 rules 7 rules of definition 113-1 17 Rules of Inference ; Theorems 12 Russell, B. A. W. 53

S 119 A.37.3 salient 118 A.35.0 schematic 6 Schematic Replacement 6 schematically replacing 6 schemator 3 Scott, D. S. 44 section 67 2.76.9 67 2.76.12 Selector 4 Sequences 91 set xxvi 41-1 11 41 2.1.0 - builder 51 2.33.0 52 2.35 Set Functions and Fixed Points 94 signature 114 A.4 simple 6 singleton 42 2.1.35 57 2.50 60 2.55.0 Singletons 57 some 33 1.0.16 square 68 2.76.22 stencil 24 0.59 strict 8 0.5 string 27 0.71 string-chain 30 0.78.1 string-link 30 0.78.0 Structure of Basic Forms I 13 Definitions 115 subchain 29 0.76.1

129

130 subformula 28 0.72.2 subject 23 0.54 subset 42 2.1.13 proper - 42 2.1.21 subsets, set of 51 2.33.3 set of proper - 51 2.33.4 Subsets, Theorem of 55 2.44 substitution 13 0.26 indicial13 0.28 schematic13 0.27 substitution 23 0.57 24 0.58 63-66 Substitution 63 substring 28 0.72.0 successor 74 2.92.7 suffix 8 0.11 superset 42 2.1.16 proper - 42 2.1.23 supersets, set of 51 2.33.5 set of proper - 51 2.33.6 symbol 1

Tarski, A. xxvii 94 terminates 28 0.72.1 theorem 7 12-15 29 0.75 Theorems 12 Theory of Notation 15 Translatability 117 translates 119 A.38 tree 117 A.25 true 42 2.1.7 truth, axiom of 43 2.5.0 Tuples 110 .type 15 0.30

Unicity 66 Theorem of67 2.74 union 42 2.1.25 33 1.0.15

General Index 42 2.1.29 42 2.1.33 46 2.20.3 46 2.20.6 Unions, Theorem of 57 2.48 universal 50 universal quantification 6 0.0.3 33 1.0.2 universal quantifier 4 universalization 13 0.29 universe 41 2.1.2 33 1.0.6

value, axiom of 43 2.5.1 value o f a function 71 2.84.4 variable 4 variant 5 verb 23 0.53.0 verbal 23 0.53.1 verbless 23 0.53.2 von Neumann, J. xxvi

W

119 A.37.2 Weihe, J. W. 59 Well Ordering 88 --Theorems 89 2.127 Wiener, N. 59 60 2.56.0

X 119 A.37.1 Zermelo, E. 4

44

43 2.5.8 Zermelo Selector 4 Zorn, M. A. xxvii 86 86 2.121 87 87 2.122