Sir P.6 POSTULATIONAL METHODS by Samuel Ernest S t a l l a r d A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTERS OF ARTS i n the Department of MATHEMAT ICS we accept t h i s t h e s i s as conforming to the standard required from candidates for the degree of MASTER OF ARTS. Member of the Department of Philosophy and Psychology Member of the Department of Ms&hematics THE UNIVERSITY OF BRITISH COLUMBIA October, 1951 Abstract Since the middle o f t h e 19th century t h e r e has been a r a p i d growth i n t h e use o f t h e p o s t u l a t i o n a l method i n mathematics. C o n c u r r e n t l y w i t h t h i s growth such concepts have a r i s e n as t h e c o n s i s t e n c y , independence o r completeness o f a b s t r a c t s e t s o f p o s t u l a t e s . The d e f i n i t i o n s o f these c o n c e p t s , as w e l l a s t h e methods used to t e s t l a t e s f o r these p r o p e r t i e s , are w i d e l y s c a t t e r e d out mathematical and l o g i c a l , l i t e r a t u r e . postu- through- The o b j e c t o f t h i s t h e s i s has been to make a survey of t h i s new f i e l d (which we might c a l l Axiomatics) and to i n d i c a t e some o f the t e c h n i q u e s used i n i t . The method has been t o t a k e a simple s e t of p o s t u l a t e s (those £.G-r.the r e l a t i o n of s e r i a l o r d e r ) and then d e v i s e p r o o f s f o r the c o n s i s t e n c y , completeness, postulates. e t c . o f these Each proof i l l u s t r a t i n g one of t h e methods c u r r e n t l y i n use f o r t e s t i n g p o s t u l a t e s . Historical Introduction Our modern concern with postulational nethods had i t s historical beginning in Greek mathematics, a mathematics, which, although chiefly remembered for i t s work on the real numbers and geometry, really made i t s greatest contribution <in the form of the above mentioned methodology. This contribution was l e f t in the form of a synthetic geometry, which had developed from a practical, workable empiricism to a strict deductive science in an extraordinary short time. The earliest "proof" in geometry is traditionally ascribed to Thales, about 600 B.C. In solid geometry, the Pythagoreans knew at least three of the five regular solids and probably a l l . However, the proof that i t i s possible to construct five, and only five, regular solids i s ascribed to Theaetetus about the middle of the fourth century B.C. Euclid later i n the same century completed the elementary theory of these solids in his Book XIII, as the climax of his geometry. With this completion of Euclid's Elements, Greek elementary geometry attained i t s rigid perfection. Its lastiriaj contri- bution - and Euclid's - to mathematics, was not so much the store of 465 propositions which i t offered, but rather the new methodology which, as we shall see, was far ahead of i t s times. For the f i r s t time i n history masses of isolated discoveries were unified and correlated by a single guiding p r i n c i p l e , that of rigorous deduction from e x p l i c i t l y stated assumptions. goreans had Before E u c l i d , Eudoxus and some of the Pytha- executed important d e t a i l s of the grand design, but i t remained for Euclid to see i t a l l and see i t whole. He i s therefore the perfector, i f not the sole creator, of what i s today called the postulational method, the central nervous system of l i v i n g mathematics. It seems strange to us today that a f t e r t h i s clear exposi- t i o n of the postulational method, it. had to wait u n t i l the nineteenth century to be f u l l y appreciated. not u n t i l then that the method, was At least i t was sufficiently abstracted from geometry to enable mathematicians to consider to other f i e l d s . Euclid's geometry of course continued i n the postulational t r a d i t i o n . for i t was applying i t But t h i s , apparently, was only inertia, decades after the outburst of projective geometry i n the nineteenth century, before anyone attempted to put i t on a sound postulational basis. that any serious attempt was (And i t was not until the l#30's made to handle elementary i n t h i s postulational manner.) Not u n t i l 1399 algebra i n the work of D. H i l b e r t (l£62 - 1943, German) on the foundations of geometry, was the f u l l impact of Euclid's methodology f e l t i n a l l mathematics. Concurrently with the pragmatic demonstration of the creative power of the postulational method i n arithematic, geometry, algebra, topology, the theory of point sets, and analysis, which distinguished the f i r s t part of the twentieth century, the method became increasingly popular i n t h e o r e t i c a l physics i n the 1930's. by E. Mach (l$7c> - Earlier writings in the method, notably - 1916, Austrian^ in mechanics and A. Einstein ) io r e l a t i v i t y , had shown that the postulational approach is not only clarifying but creative. The more con- servative mathematicians and scientists may feel that a science constrained by an explicitly formulated set of assumptions has lost some of its freedom and i s almost sterile. However, the only loss, as experience has shown, is that of making systematic mistakes in reasoning, and objection to the method is really objection to the whole pattern of mathematics i t s e l f . The abstract approach made to algebra in the middle of the nineteenth century p a r a l l e l e d the epochal advance of geometry made simultaneously with the publication in 1#29 of N.I. Lobachewsky's C1793 - 1$56, Russian^ non-Euclidean geometry. It is of interest that algebraists and geometers percieved a l most simulataneously that mathematical systems are not supernaturally imposed on human beings from without, but are free creations of imaginative mathematicians. Lobachewsky's new geometry was the earliest such mathematical system to be recognized as this type of free creation. Hamilton's rejection (1043) of the postulate that multiplication is commutative, in his invention of quaternions paved the way to a host of "new algebras", in which one after another of the supposedly immutable "laws" of natural arithmetic and common algebra was modified or discarded as unnecessarily restrictive. By I85O it was becoming clear to many mathematicians that none of the postulates of common algebra, which up to 1$43 had been thought e s s e n t i a l f o r the s e l f c o n s i s t e n c y reasoning, algebra, was any more a n e c e s s i t y f o r a than i s E u c l i d ' s p a r a l l e l t e n t geometry. o f symbolic non-contradictory postulate f o r a s e l f consis- Moreover, t o t h e astonishment o f many i t was found that the modified algebras, as f o r example Hamilton's, were adaptable t o mechanics, geometry and mathematical Thus mathematics achieved the a t t e n t i o n being turned physics. the freedom i t has today because o f again t o the p o s t u l a t i o n a l method. An experiment of Veblen Before proceeding f u r t h e r to a d i s c u s s i o n of t h e p o s t u l a t i o n a l method I f e e l i t would be to the p o i n t t o look a t an i n t e r e s t i n g experiment (1) performed at P r i n c e t o n U n i v e r s i t y by a c l a s s of graduate s t u d e n t s i n P r o j e c t i v e Geometry under the / d i r e c t i o n of P r o f e s s o r 0. Veblen. T h i s experiment o r i g i n a t e d i n the d e s i r e t o emphasize the point that our l o g i c a l p r o c e s s e s may. be independent o f any p a r t i c u l a r set of mental images assoc i a t e d w i t h the o b j e c t s of thought and t h a t they may i n f a c t be performed without any knowledge o f the concrete the p r i m i t i v e p r o p o s i t i o n s or p o s t u l a t e s r e f e r . o b j e c t s t o which As we c a n r e a d i l y see, the success o f t h e a b s t r a c t p o s t u l a t i o n a l method i n mathematics and l o g i c depends l a r g e l y upon our a b i l i t y t o t h i n k i n t h i s formal the manner. The experiment was as f o l l o w s : i n s t r u c t o r proposed t o t h e c l a s s that c e r t a i n members make up a s e t o f p o s t u l a t e s g i v i n g p r o p e r t i e s s u f f i c i e n t t o charact e r i z e some s e t of o b j e c t s chosen by them and t h a t these post u l a t e s should be submitted to the remainder of the. c l a s s , the l a t t e r were then to attempt t o determine the p r e c i s e nature of c The o b j e c t s without any f u r t h e r i n f o r m a t i o n concerning t h a n what was c o n t a i n e d tulates. them i n the p r o p o s i t i o n s of the s e t o f pos- The way i n which t h e students were to proceed was t o make deductions f r o m t h e given p o s t u l a t e s and t o d e r i v e theorems concerning the o b j e c t s r e f e r r e d t o i n them u n t i l they had learned enough about these o b j e c t s to know what the p o s t u l a t e makers had i n mind when they formed the p o s t u l a t e s . Of t h i s experiment Professor Veblen has w r i t t e n as f o l l o w s : "The e x e r c i s e was a success t i o n s can be made without about. i n showing how mathematical deduc- knowledge as t o what one i s r e a s o n i n g I t also brought out v i v i d l y t h e problem of the s i g n i f i - cance of the l o g i c a l processes as a method o f d i s c o v e r y . While t h e r e i s a sense i n which i t i s t r u e t h a t you cannot g e t anything out of a set o f p o s t u l a t e s except w h t has been put i n them, you a can a t l e a s t f i n d out what has been put i n them. This the s o l v e r of t h i s problem has to do i n a simple case. more complicated cases, the student i s what I n the i s apt t o t h i n k that he understands what i s i n t h e axioms, but every time t h a t he w i t nesses t h e d e r i v a t i o n o f a new theorem i t t u r n s out t h a t there was something i n them t h a t he had not seen b e f o r e " . 6 I Chapter I Hawing d i s c u s s e d the h i s t o r y of the p o s t u l a t i o n a l method and having g i v e n a b r i e f example to i l l u s t r a t e the of r e a s o n i n g possibility a b s t r a c t e d from a l l i n t e r p r e t a t i o n s , l e t us ceed t o examine i n g r e a t e r d e t a i l the nature of t h i s pro- method. To a r r i v e a t the u n d e r l y i n g m o t i v a t i o n of the p o s t u l a t i o n a l school i t i s only necessary a r i s e when one t o c o n s i d e r the d i f f i c u l t i e s which attempts to g i v e a c a r e f u l p r e s e n t a t i o n o f precise subject. We are l e d immediately to a d i s c u s s i o n of language, f o r the degree of c l e a r n e s s which we depend d i r e c t l y on what a t t i t u d e we Here we adopt toward t h e same. have a usage which, although to enable us t o d e a l with day by day An attempt at g r e a t e r p r e c i s i o n i n the ment forms, e t c . tionally difficult Here the of c l e a r enough mathematics. use of language p l i c i e s , l e g a l documents, governideas to be conveyed are not excep- but the importance o f a v o i d i n g ambiguity i s g r e a t e r than i n everyday d i s c o u r s e . phraseology To natters, s t i l l f a l l s f a r short of the p r e c i s i o n demanded by science and i s i l l u s t r a t e d by insurance j obtain w i l l b r i n g the problem into f o c u s c o n s i d e r our everyday use language. any Therefore, elaborate i s i n t r o d u c e d t o guard a g a i n s t the m i s i n t e r p r e t a t i o n s that might otherwise be p o s s i b l e . One c a n e a s i l y t h i n k of f u r - t h e r examples of more or l e s s s p e c i a l i z e d forms of communications. I t becomes apparent t h a t the more s p e c i f i c the subject matter under d i s c u s s i o n , the more s e r i o u s i s t h e c o n f u s i o n a r i s i n g from the u n q u a l i f i e d use of everyday language. I t i s not s u r p r i s i n g , 1 then, that i n mathematics we f i n d language t r o u b l e s as perp l e x i n g as they can be anywhere. It might n a t u r a l l y occur t o one now, that i n any use of language, misunderstandings might be reduced bjj coming to an agreement on d e f i n i t i o n s of dubious terms. The need f o r agree- ment i s g e n e r a l l y admitted as i s shown by the o f t e n heard demand, " d e f i n e your terms", d u r i n g a d i s c u s s i o n . It i s easy enough to d e c i d e that we must d e f i n e doubtful terms, but what are we going t o agree on as c o n s t i t u t i n g a definition? Let us examine, t h e n , t h e everyday source of d e f i n i - t i o n s , the d i c t i o n a r y . Here we f i n d , on l o o k i n g up the meaning of the word, a v a r i e t y of p o s s i b l e meanings f o r the same word; e.g., f o r the a d j e c t i v e " f a i r " , we f i n d nine d i f f e r e n t meanings. In a d i s c u s s i o n i n which i t i s important to understand, indepen- d e n t l y of c o n t e x t , such a m u l t i p l i c i t y of meanings i s i n t o l e r a b l e . Thus, i f a d e f i n i t i o n i s to be h e l p f u l i n an exact d i s c u s s i o n , i t must be unambiguous. Also a d e f i n i t i o n , i f i t i s t o be o f any use at a l l , give the meaning of a new word i n terms o f words which ready known. Otherwise, we There i s s t i l l hope, however, that t h i s process w i l l come t o an end by e v e n t u a l l y We re ching a terms. cannot always be sure of s u c c e s s i n t h e p r o c e s s , however, as t h e f o l l o w i n g example w i l l show. Suppose t h a t we wish t o l e a r n the value of the A u s t r i a n c o i n , t h e Krone. gives: are a l - might be f o r c e d t o look up unknown words i n the d e f i n i t i o f i i t s e l f . recognizable must A dictionary , Krone: The former monetary u n i t of Austria-Hungary, lc>92-1925; also the But corresponding c o i n , e q u i v a l e n t t o 100 H e l l e r . then, Heller: In A u s t r i a , up t o 1925, e q u i v a l e n t to 1/100 Here we Krone. come t o a dead end. v i c i o u s c i r c l e with no the heart a small copper c o i n Rather, we side turnings. of the t r o u b l e . The Now inescapable we are caught i n a have a r r i v e d a t f a c t i s that the d i s t i o n a r y must i n e v i t a b l y lead us i n an unending c i r c l e : A Krone i s 100 H e l l e r s ; a H e l l e r i s 1/100 Krone. T h i s c y c l i c d e f i n i t i o n must a r i s e ; s i m p l y because the t i o n a r y i s t r y i n g to do the a l l words. impossible. That t h i s i s impossible may dic- I t i s t r y i n g to d e f i n e be e a s i l y seen. For c o n s i d e r t h a t a d e f i n i t i o n r e p l a c e s an unknown word by a c o l l e c t i o n o f known words. From t h i s i t f o l l o w s that a d e f i n e d word i s an unnecessary word, f o r i t may d e f i n i n g phrase. be r e p l a c e d by i t s So i f a l l words were d e f i n e d , no words would be neededT ,This i m p o s s i b i l i t y shows t h a t some w r d s must be ever undefined. Before problem, l e t us see how r e a l l y can t r y i n g to a r r i v e a t any dangerous t h i s process- of eydic the wellknown paradox, i n which the S e v i l l e i s d e f i n e d by t h i s We do not ask now, We f i n d Barber of statement: shaves a l l t h o s e men S e v i l l e who definition be. Cohsider "He s o l u t i o n to t h i s of S e v i l l e and only those men shave themselves." "Who shaves the Barber o f Seville?" as a consequence of our d e f i n i t i o n t h a t i f the Barber shaves h i m s e l f , then he does not does not, t h e n he does. shave h i m s e l f ; i f he of 9c When t h i s paradox f i r s t appeared i t caused q u i t e understandable concern, f o r the d e f i n i t i o n of the Barber seemed q u i t e p a r a l l e l t o the s o r t of d e f i n i t i o n s used i n mathematics. A c t u a l l y , the of the d i f f i c u l t y source i s easy-to The d e f i n i t i o n of the Barber i n v o l v e s the men the Barber i s t o be considered as one then the d e f i n i t i o n i s cyclic, t h a t i n p a r t , i n terms of h i m s e l f . of S e v i l l e . o f the men i s , the Although we locate. of Seville, Barber i s d e f i n e d , will not go the matter here, c y c l i c d e f i n i t i o n s are d e a l t w i t h by z i n g them; hence, the d e f i n i t i o n of the as i n a d m i s s i b l e . man If into ostraci- Barber i s t o be regarded Note t h a t i f the Barber i s r e g a r d e d , not as a o f S e v i l l e , but as a new e n t i t y introduced the paradox d i s a p p e a r s f o r he may by h i s d e f i n i t i o n , shave h i m s e l f or not as he chooses,since the d e f i n i t i o n s p e c i f i e s h i s a c t i o n s only w i t h r e s p e c t to the men Now t h a t we of S e v i l l e , of whom he i s then not have shown the need o f e l i m i n a t i n g c y c l i c d e f i n i t i o n s l e t us see how t h i s e l i m i n a t i o n can be A h i n t that a s o l u t i o n e x i s t s l i e s i n the dictionary and i s o f t e n of value t o us. achieved. f a c t that True, i f we the l o o k up a,word, are l e a d through a c h a i n of u n f a m i l i a r synonyms back to o r i g i n a l word, the d i c t i o n a r y has the one. not helped. But the i f j u s t one of synonyms i s known, then a u t o m a t i c a l l y they a l l become known. D e f i n i t i o n s can be h e l p f u l , t h e n , i f they always give meanings u l t i m a t e l y i n terms.of a l i s f c r o f knd.wn words. • We have already There should i n d i c a t e d t h a t not a l l ^ o r d s can be be then a b a s i c l i s t of words t h a t x^e forego f i n i n g ; these words are learned p r a g m a t i c a l l y by the defined. de- elaborate means by which one learns to speak i n childhood. Once the basic l i s t has been decided upon and agreement on the meanings of these words has been reached a l l remaining words; i . e . , the defined words become meaningful by v i r t u e of the elaborate network of paths connecting them with the basic words. It is now seen that i f we were to construct a language systematically, we should introduce f i r s t a 1 anguage basis, con- s i s t i n g of words and phrases, upon which a l l agree, and about which there i s no argument. The remainder of the language would then be b u i l t up by following some agreed on r u l e s of grammar and by.a systematic use of d e f i n i t i o n s having the property that new words would be defined always i n terms of words from the basic l i s t or previously defined words. Now i n mathematics the underlying language i s Logic, which i s taken i n i t s entirety by the postulational school as basic. It is not r e a l l y necessary to assume the whole of l o g i c , since the l o g i c a l c a l c u l i may be b u i l t up systematically upon a very few primitive, or basic ideas. On the other hand for the purpose of serving mathematics i t i s only, an aesthetic issue whether we take a part or a l l of logic as basic. As a matter of fact with any of the c a l c u l i which are applied i n science a" l o g i c a l c a l culus serves as i t s basis. mathematics and the consist of two Each of the non-logical c a l c u l i , c a l c u l i applied i n science, s t r i c t l y speaking parts: calculus added to i t . a l o g i c a l basic calculus and a s p e c i f i c The basic calculus could be approximately the same for a l l those c a l c u l i ; i t could consist of the sentential calculus and a smaller or greater part of the functional calculus. The s p e c i f i c p a r t i a l calculus; e.g., a branch of mathematics, does not usually contain additional rules of inference but only a d d i t i o n a l p r i m i t i v e sentences, c a l l e d axioms or p o s t u l a t e s , and u s u a l l y some a d d i t i o n a l p r i m i t i v e terms. As the b a s i c c a l c u l u s i s e s s e n t i a l l y t h e same f o r a l l the d i f f e r e n t s p e c i f i c c a l c u l i , i t i s not customary to mention i t a t a l l but to desc r i b e only the s p e c i f i c part of the c a l c u l u s . What u s u a l l y i s c a l l e d an axiom system i s t h u s the second part o f a c a l c u l u s whose c h a r a c t e r as a part i s u s u a l l y not n o t i c e d . For any o f the mathematical and p h y s i c a l axiom systems i n t h e i r form i t i s necessary to add a l o g i c a l b a s i c c a l c u l u s . ordinary Without i t s h e l p i t would not be p o s s i b l e t o prove any theorem of the system or t o c a r r y out any d e d u c t i o n by use of t h e system. axiom system, c o n t a i n s , An b e s i d e s the l o g i c a l c o n s t a n t s , other constants which we may c a l l i t s s p e c i f i c or axiomatic c o n s t a n t s . Some of these a r e taken as p r i m i t i v e ; o t h e r s may be d e f i n e d . The d e f i n i t i o n s l e a d back t o the p r i m i t i v e s p e c i f i c signs and logical signs. An i n t e r p r e t a t i o n o f an axiom system i s g i v e n by semantic a l r u l e s f o r some o f the s p e c i f i c s i g n s , s i n c e f o r the l o g i c a l s i g n s the normal; i . e . , l o g i c a l , i n t e r p r e t a t i o n i s presupposed. / Chapter I I The S p e c i f i c Concepts o f Mathematics Having noted i n the p r e v i o u s d i s c u s s i o n t h a t any mathemat i c a l theory w i l l c o n s i s t o f two p a r t s , a b a s i c u n d e r l y i n g l o g i c and a s p e c i f i c mathematical s u p e r s t r u c t u r e , we wish cuss some o f t h e concepts which are fundamental now to d i s - to the l a t t e r . F i r s t l e t us s e t f o r t h the terms which are p r i m i t i v e f o r mathema tics. Admittedly, any p r i m i t i v e term i s to he undefined and t o achieve an understanding of such terms one must observe them i n use. Yet a c t u a l l y "behind t h e scenes" one possesses an i n t u i - t i v e grasp of t h e meanings of t h e s e b a s i c concepts. A l s o these meanings may be communicated by means of broad p r e l i m i n a r y d i s cussions. Elements: Perhaps t h e most elemental of the s p e c i f i c mathematical concepts i s t h a t of a completely a b s t r a c t and f o r m l e s s e n t i t y . It i s completely u n e s s e n t i a l to have any d e f i n i t e p i c t u r e o f these e n t i t i e s or o b j e c t s or to have any knowledge of t h e i r p r e c i s e nature. I t i s necessary t h a t the e n t i t i e s of our d i s - course possess such g e n e r a l i t y that terms whether concrete or a b s t r a c t , s i n g u l a r or p l u r a l , w i l l be i n c l u d e d . the word, "element" or Accordingly, i s i n t r o d u c e d to r e p l a c e , " o b j e c t " , "entity" s i m i l a r words, with t h e i n t e n t i o n t h a t "element" should be understood i n the broadest p o s s i b l e sense. The high degree of 13 a b s t r a c t n e s s a s s o c i a t e d with t h e term "element" should not be allowed to cause any d i s c o n t e n t , f o r we have t h e compensating f a c t o r that there i s no need to f i x c o n c r e t e meanings e a r l y i n t h e development of a t h e o r y . An element i s t h u s a blank into which may be r e a d or i n s e r t e d any s p e c i f i c meaning. i Sets o f Elements: In o r d e r t o prevent l o g i c a l chaos i t i s found necessary t o limit our d i s c o u r s e i n any given d i s c u s s i o n or theory t o c e r t a i n p a r t i c u l a r elements, which we imagine t o be before us throughout the theory. That i s , any elements which enter our d i s c o u r s e must belong to a f a m i l y o f elements which i s f i x e d and i n v a r i a n t throughout t h e t h e o r y . Such a f a m i l y i s c a l l e d - a s e t , and the elements comprising i t a r e s a i d t o belong t o , or be .members o f , the set. Note a l s o t h a t t h e r e can be no o b j e c t i o n to a l l o w i n g two or more f i x e d s e t s t o be before us i n a s i n g l e t h e o r y . F o r since t h e elements of a set a r e a r b i t r a r y they may themselves be s e t s o f elements. Equality: Whereas the statement "a e A" says something about an element a and a set A , aamely^, a type of statement which "a belongs t o A", there i s i n v o l v e s two elements or two sets and which occurs so o f t e n that one takes i t f o r g r a n t e d . be elements of any k i n d . say b that "a They may, i n p a r t i c u l a r be s e t s . i s equal to are the same element. a = b means "a If i t i s f a l s e that Let a , b b" , and w r i t e "a = b", i f a We and Thus and b a = b are two l a b l e s f o r t h e same object' then we w r i t e a ^ b . Thus 7 from t h i s p o i n t o f view i t appears t h a t the statement "equals may be s u b s t i t u t e d f o r e q u a l s " means only t h a t c h a r i n g t h e name o f an object does not change the o b j e c t . To i l l u s t r a t e t h a t statements of e q u a l i t y may have content c o n s i d e r t h e f o l l o w i n g example. dents of the United Let A States d u r i n g World War I , and l e t the s e t c o n s i s t i n g of Woodrow Wilson. statement. be the s e t o f a l l p r e s i - Then A = B B be i s a true Moreover, t h i s statement conveys t h e i n f o r m a t i o n t h a t Woodrow Wilson, and only Woodrow Wilson, served as p r e s i - dent, d u r i n g World War I . Subsets: Suppose t h a t we have the set A before us, where A = [ a , b, c ] A little r e f l e c t i o n shows us t h a t once t o our c o n s i d e r a t i o n , we a u t o m a t i c a l l y A has been admitted admitted s i x other sets, namely, 0, bj, [ b , c ] , [ a , c ] , £a] , [ b ] , \c] T h i s process of s e l e c t i n g s e t s , each one of which i s a " p a r t " of t h e g i v e n set, may be s t a t e d g e n e r a l l y . Any s e t r e s u l t i n g from the p r o c e s s being c a l l e d a subset o f the o r i g i n a l s e t . Thus we f o r m u l a t e a d e f i n i t i o n of subset as f o l l o w s : A set B of B i s a subset o f a s e t A are elements of A and we w r i t e whenever a l l the elements BC A or A 3) B , It would be now p o s s i b l e by u s i n g t h e above concepts to b u i l d up a s u b s t a n t i a l a l g e b r a of s e t s i n t r o d u c i n g by d e f i n i t i o n s the concepts o f set-sum, set-product, e t c . Ordered P a i r s Although i t i s a e s t h e t i c a l l y d e s i r a b l e t h a t the l i s t o f -15. p r i m i t i v e conc-epts f>or a t h e o r y be as small as p o s s i b l e , i t o f t e n happens t h a t when c e r t a i n concepts a r e d e f i n e d i n s t e a d of being p l a c e d on the language b a s i s , t h e i r d e f i n i t i o n s be- come awkward, a r t i f i c i a l and c o n c e p t u a l l y d i f f i c u l t . In f a c t the d e f i n i t i o n s may be l e s s s a t i s f a c t o r y than the o r i g i n a l i n t u i t i o n s connected with the terms. We f i n d o u r s e l v e s i n t h i s s i t u a t i o n now; i t s being p o s s i b l e at t h i s p o i n t to d e s c r i b e a l l f u r t h e r mathematical concepts i n terms of s e t s of elements o n l y . However, f o r the above reasons i t i s convenient to l i s t one f u r t h e r concept as p r i m i t i v e . The term set to be i n t r o d u c e d i s "ordered p a i r " . This i s a c o n s i s t i n g o f two elements t o g e t h e r with a c e r t a i n specifi- c a t i o n as t o which element "comes f i r s t " and which "comes T h i s order i s i n d i c a t e d by w r i t i n g a, b i n which a preceeds b . (a, b) f o r t h e ordered Note t h a t the s e t nothing t o do with t h e order of the elements, If ( a , b) and from our concept (a, (c, d) [ a , b] since of e q u a l i t y t h a t b) = (c, d) only when a = c and b = d: . o f ordered p a i r w i l l T h i s s e t i s the s e t of a l l ordered p a i r s whose " f i r s t and whose "second" Df. element i s from A x B = the C a r t e s i a n Product & Let The has |[a, b] = [ b , a be put i s t o d e f i n e t h e C a r t e s i a n Product; of two s e t s A pair a r e ordered p a i r s , t h e n i t i s c l e a r The immediate use to which the concept from second". [(a, b) ; of A and B . element i s B . Thus A and B a e A, b e B ] us l o o k back f o r a moment at t h e terms j u s t i n t r o d u c e d . b a s i c terms which have appeared a r e element, s e t and ordered I 16 k pair. But a l s o t h e r e have been i n t r o d u c e d other concepts, subset, c a r t e s i a n product, e t c I t i s evident that these l a t t e r terms were d e f i n e d and a l s o t h a t c o n s i d e r a b l e o r d i n a r y language was used i n e f f e c t i n g t h e d e f i n i t i o n s . However, i f one were t o s t r i p away the u n e s s e n t i a l s , one would f i n d t h a t t h e a u x i l i a r y mathematical concepts are d e f i n e d i n terms of the b a s i c ones w i t h t h e h e l p of a few a d d i t i o n a l terms, the b a s i c l o g i c a l The l o g i c a l terms met thus so f a r a r e : " i s a member o<5f " or "e" "nnt" " a l l " or "every" as i n "the s e t of a l l ..." "such t h a t " as symbolized by ft . ?! in [ ( a , b) ; a e A, b e B ] "there "if exists" ... , t h e n ..." "or" "and" These terms are a l l a c c e p t e d without q u e s t i o n , w i t h meanings as commonly understood i n l o g i c . terms. 3-' Chapter I I I Further S p e c i f i c Terms of Mathematics. I t w i l l be r e c a l l e d t h a t o b j e c t i o n s t o d i c t i o n a r y d e f i n i t i o n s were r a i s e d on the grounds t h a t words are d e f i n e d of themselves. a list In order to a v o i d t h i s d i f f i c u l t y the need f o r o f p r i m i t i v e terms was p r i m i t i v e terms a v a i l a b l e , we stressed. may Now construct with the " ordered p a i r " . foregoing a legitimate dic- t i o n a r y , i n which f u r t h e r mathematical concepts may s t r i c t l y i n terms of the i n terms be defined b a s i c ones, namely, "element" " s e t " , Let us i n d i c a t e t h e n , q u i t e b r i e f l y , how n e a r l y b a s i c mathematical terms, " r e l a t i o n " , " f u n c t i o n " , and "one-to-one correspondence" may be now ,T the operatic defined. Relations: Given a set that R M with elements is a relation i n M i f t h e statement t r u e or f a l s e f o r a l l elements e.g. a, b, c ... a, b, c ... of we aRb usually say is either M . M = set of a l l people. R = " i s the f a t h e r Notice uniquely now, however, that any of" such r e l a t i o n determines a s e t o f ordered p a i r s of elements f r o m the s e t of a l l (a, b) such that a e M, b e M, M , namely, and aRb . The . r e l a t i o n i s t h u s f u l l y known i f t h i s s e t i s known and v i c e Hence, i t w i l l be found v e r y convenient and f r u i t f u l to versa. regard the r e l a t i o n as i d e n t i c a l w i t h t h i s set of ordered p a i r s . Note IB. that t h e r e i s no need t o r e s t r i c t t h e r e l a t i o n t o b e i n g on one s e t . e.g. A i s the s e t of a l l men B i s t h e s e t of a l l women R = " i s t h e husband o f " • T h i s r e l a t i o n determines a subset of the c a r t e s i a n product A x B which i s t h e set of a l l p o s s i b l e 'a man and (second) a woman. ordered p a i r s o f ( f i r s t ) We thus give as t h e mathematical d e f i n i t i o n o f r e l a t i o n the f o l l o w i n g : (3.1) Let A subset of and B be s e t s . A r e l a t i o n on A x B i sa A x B . Thus i f R i s a r e l a t i o n on A x B *ie, if a e A, b e B, the statement that to b" or "aRb" means t h a t When.the s e t s A and "a Rc A x B then, i s i n the r e l a t i o n R (a, b) £ R . B possible t o specify a r e l a t i o n have only R a few elements i t i s by means o f t h e f o l l o w i n g con- venient t a b l e : e.g. V Where an a s t e r i s k i n a p a r t i c u l a r row and column i n d i c a t e s t h a t t h e ordered p a i r c o n s i s t i n g o f the element at the l e f t of the row and t o p of the column a r e i n the r e q u i r e d r e l a t i o n . Thus i n the above example ( a , b^) , (a^, b ) belong to 2 Notice t h a t we could a l s o g i v e a t r u t h t a b l e 2 R . i n order t o s p e c i f y 19. B this relation R eg. A a f F T T F F F In t h i s case i t i s convenient t o r e c a l l the more c o n v e n t i o n a l concept of a r e l a t i o n as being a p r o p o s i t i o n a l f u n c t i o n i n two v a r i a b l e s and which we might c o n v e n i e n t l y w r i t e as Suppose now t h a t of B x A R i s a r e l a t i o n on c o n s i s t i n g of those a r e l a t i o n on B x A . denoted by . R R(x, y) . A x B . p a i r s (b, a) The subset f o r which I t i s c a l l e d the converse o f Thus bRa means the same as aRb aRb, i s R and i s and we make the f o l l o w i n g d e f i n i t i o n : (3.2) R* [(b, a) e B x A ; aRb ] I t i s p o s s i b l e now t o b u i l d up an i n t e r e s t i n g a l g e b r a of r e l a t i o n s u s i n g the above d e f i n i t i o n o f a r e l a t i o n and t h e a l g e b r a of s e t s . However, to b u i l d such an a l g e b r a would not d i r e c t l y bear on our p r o j e c t o f t r a c i n g through t h e program o f t h e p o s t u l a t i o n a l s c h o o l and so i t w i l l be p e r t i n e n t only to mention t h e following reference i n t h i s connection. " R e l a t i o n s b i n a i r e s , ferme^ t u r e s , correspondences de G a l o i s " by Jacques Riguet, B u l l , de l a S o c i e t e Mathematique de France. V o l . 76 (194S) pp. 115 - 155* Functions: Before d e f i n i n g a f u n c t i o n we need f i r s t one more d e f i n i t i o n relating to relations. (3.3) Let A and B be s e t s and R a r e l a t i o n on A x B . 2C Then the domain of R ^ (_a e A , there e x i s t s -jjC the converse domain of Now there R b e B and a R b ] -l r =' [b e B, there e x i s t s a e A and a fi bj i s a f e a t u r e which some, but by no means a l l , tions e x h i b i t , a feature according rela- to which r e l a t i o n s might be classified. (3.4) Let A and B be s e t s and R a r e l a t i o n on A x B . Then R i s a function =' f o r every a e domain of e x a c t l y one I f t h e domain of be A to B . of R may be b e B R there such t h a t R = A , t h e n the f u n c t i o n R exists a R b i s s a i d to N t e i n t h i s c o n n e c t i o n t h a t t h e converse domain 0 B o r a subset of B . One-torone Correspondences: Let F be a f u n c t i o n on as u s u a l , given converse F sets. of ask whether F F Since set [P]_, P , P3] F Pi ?2 P and and; G F 3 B , where A F i s a r e l a t i o n on B x A . and B are, A x B , the I t i s n a t u r a l to i s n e c e s s a r i l y , or may be, a f u n c t i o n t o o . s u f f i c e to c o n s i d e r relations to i s a r e l a t i o n on will 2 A a p a i r of simple examples. B the s e t [ q ^ , q 2 , q3) Let ^3 G P l P P <>1 2 3 #• ^2 q be the and d e f i n e two by means o f t h e f o l l o w i n g t a b l e s : ^2 A It 3 21. I t i s evident that not f u l f i l d e f i n i t i o n clear that G F i s not a f u n c t i o n , s i n c e i t does ( 3 . 4 ) above. is a function. Moreover, i t i s e q u a l l y These examples serve t o show t h a t the converse of a f u n c t i o n can be a f u n c t i o n but need not be. This leads to the d e f i n i t i o n (3.5) Let Then F A and B be s e t s and a f u n c t i o n on i s a one-to-one correspondence 1) The domain of 2) A; F = between A A x B . and B if A F = B i s a function. Clearly, i f F B , then F The converse domain of 3) F and F F i s a one-to-one correspondence i s a one-to-one correspondence i s then c a l l e d the i n v e r s e of between between A B and F. Binary Operations: In the g e n e r a l to B , A d i s c u s s i o n of f u n c t i o n s on i s an a r b i t r a r y s e t . A x B or on A A s p e c i a l case a r i s e s so o f t e n t h a t a s p e c i a l terminology and n o t a t i o n f o r i t i s d e s i r a b l e . case i s when A (3.6) i s a f u n c t i o n on If F i s t h e c a r t e s i a n product of two s e t s A]_ x A 2 to B , t h en A^ The and F is c a l l e d a binary o p e r a t i o n , or simply an o p e r a t i o n . The element's o f t h e domain o f (a 1 ? a ) 2 (a-p a ) 2 with a 1 e A^ i s an element and a 2 F are of course the p a i r s e A . 2 The F-correspondent of b e B, which we might w r i t e as b = F(a , a ) 1 2 or i n another n o t a t i o n suggested by mathematical b = a F a x 2 custom A2. 22 -The p e c u l i a r nature of a binary o p e r a t i o n makes p o s s i b l e a very ^compact t a b u l a r r e p r e s e n t a t i o n . eg. if A A = [p-p x 2 we 2 Ul» = B p ] =[s l r s , s ], 2 3 might d e f i n e a b i n a r y o p e r a t i o n F Pi P Baturally A, , A , and B 2 f a c t a common type find 2 q i q 2 S 3 S 2 S l S 2 F as f o l l o w s : need not be d i s t i n c t , as a matter of of o p e r a t i o n i s one on A x A present chapter has d e f i n e d c e r t a i n non-basic, b a s i c , terms w i t h the h e l p of the b a s i c concepts, " c a r t e s i a n product". these a e A , i s an a R b has b e B , and R is a proposition R a s we about o p e r a t i o n on An I l l u s t r a t i o n of the Having now a S but nearly " s e t " , "element" Also c e r t a i n standard n o t a t i o n s f o r concepts have been introduced. that the n o t a t i o n If A i n group t h e o r y . The and to to two F i n a l l y we should p o i n t out important i n t e r p r e t a t i o n s . is a relation on and (a,b)eSCAxB b. C , then If aRb A x B , then a R b and i s an element of C . P o s t u l a t i o n a l Method d i s c u s s e d the m o t i v a t i o n behind the p o s t u l a t i o n a l method as w e l l as t h e s p e c i f i c m a t e r i a l s which are the b u i l d i n g b l o c k s of a mathematical theory, l e t us examine the i s s u e s i n volved i n p u t t i n g a g i v e n s u b j e c t matter on a p o s t u l a t i o n a l b a s i s . We w i l l choose as simple anT example as p o s s i b l e so as not to cloud -2' the i s s u e s by t e c h n i c a l d e t a i l s . I Suppose then t h a t we have a c o l l e c t i o n two M o f o b j e c t s , no o f which have the same weight and which we widi t o compare, with r e s p e c t to t h e r e l a t i o n "heav er than". We begin by l i s t i n g L c e r t a i n fundamental r e l a t i o n s h i p s which we can "see" to be t r u e f o r t h i s subject, t h u s we might have: x a) I f x belongs to b) I f x and y are d i s t i n c t i s h e a v i e r than y or I are d i s t i n c t members of c) I f x f a l s e that and x y y and x i s not h e a v i e r t h a n members of i s h e a v i e r than i s heavier than d) I f x , y , z heavier t h a n M , then y and y y i s h e a v i e r than T h i s i s an i n s t a n c e of s e r i a l M , then either x . M , then i t i s i s heavier t h a n are d i s t i n c t members of z itself. M ,+.hen and x is x x • is h e a v i e r U^n z o r d e r , a concept o f c o n s i d e r a b l e importance i n mathematics. Now, as a step towards making these p r o p o s i t i o n s e n t i r e l y formal l e t us borrow the n o t a t i o n o f the p r e d i c a t e c a l c u l u s of l o g i c and d e f i n e as " x f ( x ) as " x i s heavier than belongs t o M " g(x, y) y " , thus we o b t a i n a) (x) , f (x) -> ~ g(x, x) b) (x, y) :f ( x ) . f ( y ) . — c) (x, y ) : f ( x ) . f ( y ) . ~ (x = y ) . -* . ~ [ g ( x , (x = y ) . -> . g(x, y) v g ( y , x) — d) and y).g(y, x)] g(x, y) v ~- g(y, x) ( x , y , z ) : f ( x ) . f ( y ) . f ( z ) . d ( x , y , z ) . g ( x , y ) . g ( y , z ) . -* . g(x,z) To make our p o s t u l a t e s completely card the i n t e r p r e t a t i o n o f M (1) we make t h e d e f i n i t i o n t h a t a b s t r a c t we must now d i s - as being a p a r t i c u l a r s e t of o b j e c t s d ( x , y , z ) . = ,(x / y ) ( y / z ) ( x / z) 24. ( t h i s c o u l d be done a l s o , by c o n s i d e r i n g M f; i . e . , M i s t h e s e t of a l l x such t h a t allowing f to be undefined) consider f o r some undefined and b i n a r y r e l a t i o n between stage, the undefined to be d e f i n e d f ( x ) , and then g(x, y) as x and by standing y . At t h i s terms and the p o s t u l a t e s s t i l l have some con- c r e t e or p s y c h o l o g i c a l s i g n i f i c a n c e t o the mind. But i f the un- d e f i n e d terms are r e a l l y r e c o g n i z e d i t must be pos- s i b l e to a b s t r a c t a l l p r e v i o u s them as mere symbols devoid other t h a n what may as undefined, connotations of any from them, and t o t r e a t s p e c i a l s i g n i f i c a n c e to the mind be i m p l i e d about them i n broad p r e l i m i n a r y des- c r i p t i o n s or i n the statement of the p o s t u l a t e s . For example, the f o l l o w i n g p r o p o s i t i o n i s e a s i l y seen to be t r u e o f the subject matter, not h e a v i e r t h a n and y "if x y and are i d e n t i c a l " . (3.7) and y y are members of i s not h e a v i e r t h a n t o be t r u e i n the a b s t r a c t t h e o r y , from the p o s t u l a t e s l o g i c alone. x x , then (b). is x theorem x ) . •* .(x = y) i t must f o l l o w ; i . e . , be ( a ) , ... , (d) by the r u l e s o f Using the r e s t r i c t e d p r e d i c a t e c a l c u l u s we i t f o l l o w s from p o s t u l a t e see t h a t For (x, y ) : f ( x ) . f ( y ) . ~ ( x « y) six, M , and However, f o r the corresponding (x, y) : f ( x ) . f l y ) . ~ g ( x , y ) . ^ g ( y , deducible, original . -*• . g(x, y) v g(y, y ) : ~ [f ( x ) . f (y) .~-(x = y)] = (x, y ) : ~ ^ f ( x ) v ~ f ( y ) v ^ ^ ( x x) . v . g(x, y) v g(y, « y) v g(x, sr(x, y ) : ~ [ f ( x ) . f ( y ) . ~ g ( x , y ) . ^ g ( y , = (x, y ) : f ( x ) . f ( y ) . - g ( x , y ) . ^ g ( y , x)] y) v g(y, v(x = y) x ) . -> . (x = y) I t i s worthy of note at t h i s p o i n t t h a t , although we x) x) speak of the consequences of a s e t o f p r o p o s i t i o n s , i n a c t u a l i t y the consequences fellow from one p r o p o s i t i o n which i s the c o n j u n c t i o n the v a r i o u s members of the s e t . of 25 Now i f we consider t h e compound p o s t u l a t e ( a ) . (b). (c ). (d ), from which a l l t h e i m p l i c a t i o n s must f o l l o w which a r e theorems of the p o s t u l a t e and g s e t ( a ) , ( b ) , ( c ) , ( d ) , we see t h a t i t has only o c c u r i n g as f r e e v a r i a b l e s . premise as a f u n c t i o n f Thus we may write our compound ( p r o p o s i t i o n a l ) of f and I t should now be e q u a l l y p o s s i b l e t o r e i n t e r p r e t g , say f and F(f, g). g in new ways, which have concrete s i g n i f i c a n c e d i f f e r e n t from t h e preconceived s i g n i f i c a n c e of the o r i g i n a l terms. an i n t e r p r e t a t i o n i s a s s i g n e d t o the s e t , F ( f , g) formed i n t o a compound p r o p o s i t i o n , l e t s say t i o n of the p o s t u l a t e s t o a theorem Q Whenever such i s trans- P , and t h e r e l a - w i l l he P -*• Q . each new i n t e r p r e t a t i o n o f the symbols each postulate will With of t h e s e t again make a c o n c r e t e statement, and, i f the i n t e r p r e t a t i o n i s s u i t a b l e , t h i s can be judged to be true or f a l s e . postulate t h i s point i s s a i d to be s a t i s f i e d i n such an i n t e r p r e t a t i o n . i t seems t h a t and a theorem At quite a d i s t i n c t i o n might be drawn betweer a b s t r a c t and i n t e r p r e t e d systems. been g i v e n Each G ( f , g) f o l l o w s f o r m a l l y , as d i d For i f no i n t e r p r e t a t i o n has ( r e f e r i n g t o above system) ( 3 . 7 ) above, t h e n we a r e a s s e r t i n g that ( f , g ) . F ( f , g) -> G(f, g) . statements of i m p l i c a t i o n s . So t h a t the theorems are a c t u a l l y On the other hand i n an i n t e r p r e t a - t i o n s a t i s f y i n g the p o s t u l a t e s we a s s e r t that the p o s t u l a t e s are t u r e ; i . e . , using t h e example above we a s s e r t P -*• Q ference i s true P . Then i f i n t h e system we may make use of the r u l e o f i n - from our u n d e r l y i n g b a s i s of l o g i c and a s s e r t Q , CHAPTER IV Consi stency. We come now to t h e most important concept i n axiomatics, namely, the concept of the c o n s i s t e n c y f o r m a l d e f i n i t i o n of c o n s i s t e n c y axiom system w i l l be c a l l e d o f an axiom system. runs u s u a l l y as f o l l o w s : consistent The an i f i t i s impossible to prove from the p o s t u l a t e s , by means o f the l o g i c a l operations, two p r o p o s i t i o n s which are mutually c o n t r a d i c t o r y . This t i o n requires some j u s t i f i c a t i o n , f o r at f i r s t defini- s i g h t i t seems merely that precedence has been given to one p a r t i c u l a r l o g i c a l p r i n c i p l e , namely, the p r i n c i p l e of c o n t r a d i c t i o n ^ i . e . , i t i s not p o s s i b l e t o have t r u e both the propositions A (not-A). In f a c t , however, the p r o v a b i l i t y of two A 'A and We may — A theorems would condemn the e n t i r e system as meaningless. show t h i s q u i t e e a s i l y as f o l l o w s : Hilbert's and l e t us assume (2) p o s t u l a t e s f o r the l o g i c o f p r o p o s i t i o n s as w e l l as t h e usual r u l e s of s u b s t i t u t i o n and t h e r u l e of i n f e r e n c e ; i . e . , from the two theorems B . A and A -*• B we obtain the theore As a consequence o f the second axiom and the r u l e of sub- s t i t u t i o n we Theorem: then A v B Proof: obtain, If A i s any theorem and A any p r o p o s i t i o n , i s a theorem. p p v q A ->'A v B Since B i s a theorem, t h e r e f o r e Axiom 2 Substitution A v B i s a theorem. Inferenc 27 Now consider t h e s i t u a t i o n when both theorems. First**'A being a theorem theorem f o r any p r o p o s i t i o n consideration. A B But t h e n , s i n c e i s a theorem. and i m p l i e s ~A ~- A are v B is a i n t h e mathematical system under A v B . =". A -»• B i s a theorem we may a s s e r t B . B A and s i n c e S i m i l a r i l y we may prove t h a t Thus we could prove any p r o p o s i t i o n i n the system as w e l l as i t s c o n t r a d i c t o r y ! To t e s t a s e t of p o s t u l a t e s f o r consistency i s therefore one of the c e n t r a l problems of the p o s t u l a t i o n a l s c h o o l . The usual method o f t e s t i n g i s to f i n d a c o n c r e t e i n t e r p r e t a t i o n which s t a i s f i e s the a b s t r a c t p o s t u l a t e s . c o n s i s t e n t two p r o p o s i t i o n s A and —* A I f t h e system i s i n w i l l be implied by t h e axioms, but now t h a t the axioms a r e a s s e r t e d by the r u l e o f i n f e r e n c e " A and '* . A " w p r o p o s i t i o n about the "outside w o r l d " . to be impossible. as t r u t h s we have a s s e r t e d as a t r u e This i s generally felt From t h i s s i t u a t i o n , namely, t h a t an incon- s i s t e n t s e t o f p o s t u l a t e s cannot p o s s i b l e have a t r u e i n t e r p r e t a t i o n , we o b t a i n t h a t a s u f f i c i e n t the existence c o n d i t i o n f o r consistency i s of a true i n t e r p r e t a t i o n o f the p o s t u l a t e s . t h a t we do not know i f the c o n d i t i o n i s a necessary one. cannot i n f e r from the f a c t t h a t a :set does not have a t r u e p r e t a t i o n t h a t i t i s not c o n s i s t e n t . Note We inter- I t seems t h a t t h e i n t e r - p r e t a t i o n a l t e s t i m p l i e s a t a c i t assumption that any accurate d e s c r i p t i o n of an e x i s t i n g s t a t e of a f f a i r s i s c o n s i s t e n t . This seems r a t h e r u n s a t i s f y i n g f o r i t appears t h a t i n t h i s view cons i s t e n c y depends upon a c e r t a i n metaphysical b i a s , (eg. Parmenides or Hegel) t h a t r e a l i t y i t s e l f fore consistent. i s fundamentally r a t i o n a l and t h e r e - A r i s t o t l e has an i n t e r e s t i n g d i s c u s s i o n i n 2d. r Book of Metaphysics on the r e a l t i o n of l o g i c and e s p e c i a l l y chapter I I I . laws of l o g i c , A r i s t o t l e holds t h a t the a i c h as the Law t h i n g t h a t i s " ; i . e . , that existence, fundamental of C o n t r a d i t i o n , h o l d of "every- nothing t h a t a c t u a l l y e x i s t s can possess s e l f - c o n t r a d i c t o r y p r o p e r t i e s . I t i s easy to f i n d i n t e r p r e t a t i o n s which s a t i s f y our lates (a) to (d) . For example we f ( x ) . = . "x might t a k e i s a member of the s o l a r system" g(x, y ) . = . "x The postu- statements which we i s nearer the sun than y" . now o b t a i n from (a) t h i s i n t e r p r e t a t i o n are e a s i l y seen to be t r u e to (d) under i n the l i g h t of our p r e v i o u s knowledge. Let us now i n v e s t i g a t e other methods f o r p r o v i n g tency of a set of p o s t u l a t e s . the F i r s t we tained of any might mention t h a t i f a g a i n our versal functions special entities. ( x ) . f ( x ) -> ~ thus not f o l l o w f r o m them. postulates and (a) thus do not to Example, i n the case of g(x, x) 5= ~ ( a only f u n c t i o n s t h a t x can be are those with e x i s t e n t i a l import. consistency, has i n an i n c o n s i s t e n t system any . As an example They are a l l u n i - existence (a) we ).f(x).g(x, of any have x) of a t h i n g of a c e r t a i n kind, inconsistent with t h i s Secondly, the e n t i r e l y formal ( i . e . without appealing method of proving (d) a s s e r t the which merely d e n i e s the e x i s t e n c e the the theorem would possess a concept not con- i n the axioms and consider that consis- set i s q u i t e simple i t i s sometimes p o s s i b l e to see t h a t contradictory and the to already one basis for an interpretations) been given statement i n the i n the proof system would 2-9. ,be p r o v a b l e . property In t h i s method one P , f o r which one can 1) Every axiom has 2) The has t o f i n d a s u i t a b l e f o r m a l show: P . a p p l i c a t i o n of any r u l e of s u b s t i t u t i o n , e t c . , to one t o a formula with mula has inference, formulas w i t h P leads Then i t i s c l e a r that every provable f o r - shows now t h a t a c e r t a i n formula does not Therefore t h i s formula i s non-provable and i s consistent, s i n c e t h e r e would be an i n c o n s i s t e n t calculus. The otherwise no j u s t i f i c a t i o n ; out or two r u l e of P . 3 ) One P . P . r u l e ; e.g., a p l a u s i b l e r e l a t i o n to the calculus no noh-provable formulas i n c h o i c e of the i t may hence the have be property P quite a r t i f i c i a l ordinary needs and with- i n t e r p r e t a t i o n of the postulates. For an example of t h i s method l e t us t u r n to axiomatization of the s e n t e n t i a l c a l c u l u s i t s e l f . s i d e r the c a l c u l u s to be e n t i r e l y formal and basis (K, v, —* ) , where p, q , r , ... ;v on K operation to K . The on have the con- b u i l t upon the K x K to p v p. K by and 2) p •* .p v q 3) p v q. 4) (p -> q) -> (r v p. -> .r v q) . •* p .q v p p v q . For p r o v i n g new formulas from the p r i m i t i v e formulas, as w e l l as from formulas a l r e a d y we shall p r i m i t i v e formulas are 1) p -> q.='. We i s a s e t of elements symbolized i s a binary i s a unary o p e r a t i o n Note that K Hilbert's f o l l o w i n g two rules: so proved, 3--0. (, a) Rule of S u b s t i t u t i o n : we v a r i a b l e ; i . e . , a lower case l e t t e r t i o n of v a r i a b l e s , provided p) A -> B the o b t a i n the new p, q, e t c . , any From the two formula combina- formulas A and B . In order to prove the c o n s i s t e n c y as substitute f o r a s u b s t i t u t i o n i s complete. Rule of Inference: we may of the c a l c u l u s we proceed follows: We i n t e r p r e t the v a r i a b l e s p, r , ... as being t i o n s ; i . e . , statements which are e i t h e r t u r e (F) . We now d e f i n e the operations v (T) and '—by proposi- or f a l s e the tables q We now V T F —- T T T F F T F T s t a t e our property axioms and a) and ^) f a c t t h a t , on t h e b a s i s of the axioms yield the t r u t h value variables. T , T h i s con- i n t e r p r e t a t i o n , the f o r every p o s s i b l e set of v a l u e s That the axioms 1) through 4) possess t h i s property i s shown thus. 1) —(p v p) V T F F T p t h a t i s possessed by a l l the propagated by the r u l e s s i s t s i n the o f the "P" 2) P V (p v T F T T T F F T T 'F T T T T F F T T F p q T T T P ~ p) 31. -*(p v p) V (q v p q T T F T T T F F T T F T F T T F F T T F v{—<(r v p) V (r v q)} P q r T T T F T F T T T T F F T F T T T F T T T F T T T F F T T F F F F T T F T F T T F T F F T T T T F F T F T F T T F F F T T T F F v ~(~-p v q) Therefore t h e fomulas o f t h e f o u r axioms have the above mentioned property. Now under a p p l i c a t i o n o f the two r u l e s used f o r i n - f e r r i n g new formulas; namely, a) and ) the p r o p e r t y p e r s i s t s . For, with r e g a r d to the f i r s t r u l e , i t i s evident t h a t t h e range of v a l u e s f o r the v a r i a b l e s can c e r t a i n l y not be extended by sub- s t i t u t i n g an e x p r e s s i o n f o r any of them. B f r o m t h e two formulas A and ^ A v B And when we i n f e r formula by means of t h e second r u l e , t h e property o f always y i e l d i n g the value T from the l a s t two formulas t o t h e one i n f e r r e d . For s i n c e t h e formula value A always y i e l d s the value F ; hence —"A v B T , ~ A i s carried always has t h e always has the same v a l u e as B , so over that we B as w e l l as *- A v B always has the value T . Thus see t h a t every provable f o r m u l a i n our c a l c u l u s w i l l have the value T . Now t h e formula on the b a s i s value F and (K, v, q ) p v, q.-> p which can,be. c o n s t r u c t e d has the value the value F when p has the T . ~ ( p v q) V P p q T T F T T T F F T T F T F F F F F T T F Hence t h e r e e x i s t s a formula w r i t a b l e i n our system which does not have the value and F T f o r a l l assignment of the value t o the i n d i v i d u a l v a r i a b l e s i n v o l v e d . formula i s not provable and thus the Note t h a t i f we had T Therefore t h i s system i s c o n s i s t e n t . not i n s i s t e d t h a t the symbols o f our c a l c u l u s have no meaning and had worked i n the normal interpreta- t i o n of the system; i . e . , as g i v e n , namely, the c a l c u l u s o f prop o s i t i o n s , then our proof could have been shortened somewhat. For i f a formula —A A i n the system was would be f a l s e and thus not provable s i n c e every formula had the t r u t h v a l u e t r u t h . system, however, unary o p e r a t i o n on Although still t r u e then i t s c o n t r a d i c t o r y ~-A A provable In the completely a b s t r a c t was merely the r e s u l t of an undefined and not n e c e s s a r i l y not-A . not r e a l l y another method of p r o v i n g c o n s i s t e n c y , one more device i s worthy of mention here. It i s often p o s s i b l e t o reduce the q u e s t i o n o f the c o n s i s t e n c y of one system _S to t h a t of another R . T h i s i s achieved to d e f i n e t h e basic concepts o f R S i n terms i n such a manner t h a t the axioms of sequences of the axioms of R . S i f i t i s possible of the concepts of become l o g i c a l No a t t e n t i o n has t o be paid, f o r t h i s purpose, t o the i n t u i t i v e meaning of the b a s i c in S and i n R ; b a s i c concept of con- the assignment concepts of the names g i v e n t o t h e S \ as c e r t a i n concepts d e r i v e d from R , is purely a r b i t r a r y . As an example of t h i s method l e t us r e t u r n to our axiom system f o r t h e r e l a t i o n of s e r i a l order. elements f o r which the binary r e l a t i o n Let g M be a s e t o f i s defined. This time l e t us use the i n f o r m a l statement that the u n i v e r s a l q u a n t i f i e r (x) r e v e r s o n l y t o t h e elements o f dicate f f o r "belongs t o M" . M , r a t h e r than use t h e pre- Our p o s t u l a t e s then become: a) ( x ) . ~ g ( x , x) b) (x, y ) . ( x = y) v g(x, y) v g(y, x) c) (x, y ) . ( x = y) v ~ g ( x , y) v ~ g(y, x) d) (x, y, z ) . ( x = y) v (y = z) v ( x = z) v ~ g ( x , y) v — g ( y , z) v g(x, z) . Now make t h e i n t e r p r e t a t i o n t h a t elementary p r o p o s i t i o n s for the r e l a t i o n value M r e p r e s e n t s t h e s e t of (p, q, r , ... ) , t h a t ~ ( q •* p) . Now (p) p and our d e f i n i t i o n of q p = q means t h a t the have the same t r u t h value. g(p, q) stands means " f o r any t r u t h of p" or " f o r any . p r o p o s i t i o n p" and propositions g(p, q) may be represented Note t h a t by the t r u t h t a b l e q) g(p, / F f F T F F F I T ' We now show t h a t our axioms by t h i s (a) to (d) are s a t i s f i e d interpretation: a) ~g(p> (p) F T T T P) f q) V g(p, q) T T T F F T F F T F T F •' T F T T F F F T T F F P q (P = q) T T T T T T T F F T T F F T F T F T F F T T T p q T (p v-~ g ( p , q) v g ( q , p) v~g(q, p) T - g(p,q) v--g(q,r) v g ( p , r ) (p=q) v (q=r ) v (p=r) P q r T T T T T T T T T T T T F T F F T T T F T F T F F T T T F F T F F T T F T T T F F T T F T F T F T T F T F F F T T F T F F F T T F F T T F T F F f T T T T T T F • 35- i Thus the postulates for s e r i a l order are transformed upon t h i s i n t e r p r e t a t i o n into t a u t o l o g i e s c a l c u l u s ; and consequently w i l l ' now propositional calculus. the Now, of the propositional be provable formulas of the (This f o l l o w s from the completeness o f p r o p o s i t i o n a l c a l c u l u s , which w i l l be proved i n Chapter VI. ) since the r u l e s f o r d e r i v i n g new serial statements i n the system of order are drawn from tho-se o f the l o g i c a l thus w i l l be the u s u a l r u l e s of s u b s t i t u t i o n and see that a l l the theorems of our calculi, inference, i n t e r p r e t e d system w i l l subset of the theorems of the p r o p o s i t i o n a l c a l c u l u s . system has been shown to be cussed formal method; and s i s t e n c y of the postulates consistent so we by our for s e r i a l order. we form a But previously have e s t a b l i s h e d and this dis- the formal con- CHAPTER V Independence When a t e n t a t i v e l i s t of p o s t u l a t e s has been proposed f o r some branch of mathematics and has been shown to be a c o n s i s tent set, i t i s p e r f e c t l y conceivable o f t h e s e t a r e l o g i c a l l y deducible Such p o s t u l a t e s are s u p e r f l u o u s that c e r t a i n p o s t u l a t e s from o t h e r s of t h e s e t . or redundant. There i s no inherent l o g i c a l f a l l a c y i n u s i n g a redundant c o n s i s t e n t s e t of p o s t u l a t e s , but f o r at l e a s t two reasons i t i s o f t e n d e s i r able that t h e p o s t u l a t e s be f r e e from redundancies; i . e . , be independent. First, an independent s e t of p o s t u l a t e s r e n d e r s , the s t r u c t u r e of the subject a e s t h e t i c a l l y more p l e a s i n g . For no statement i s i n c l u d e d among the p o s t u l a t e s which might be d e r i v e d as a theorem. Second, i f the redundant p o s t u l a t e s are removed, t h e n when i n t e r p r e t i n g t h e system i t i s not necessary t o make as many judgments as t o whether the p o s t u l a t e s are t r u e or f a l s e f o r the given s u b j e c t matter. Hence a c o n s i s t e n c y proof would depend l e s s upon i n t e r p r e t i v e judgments and thus be l e s s l i a b l e to e r r o r . I t i s not always d e s i r a b l e , however, i n a c t u a l p r a c t i c e t o have an independent set o f p o s t u l a t e s , s i n c e the r e - d u c t i o n of t h e number of p o s t u l a t e s can often i n c r e a s e the comp l e x i t y of the d e r i v a t i o n o f theorems to t h e point where great i n g e n u i t y i s r e q u i r e d to e s t a b l i s h even the simplest For example the system o f p o s t u l a t e s : results. (1) p v p. •* p (2) q. -> .p v q (3) ..p v £. -> .q v p (4) p.v.q v r : -> :q.v.p v r (5) q -»• r . -> : p v q . -> . p v r f o r the s e n t e n t i a l c a l c u l u s of t h e " P r i n c i p i a Mathematica" cont a i n s a redundancy i n postulate (4), since P . Bernays has shown t h a t i t can be deduced from the o t h e r f o u r . (4) postulates i t may (1), Discarding i n t h i s case does not cause any inconvenience s i n c e be d e r i v e d i n a few l i n e s as a theorem. postulates (3) (2), (3), (5) are now Although the independent, the p r i m i t i v e ideas of d i s j u n c t i o n and n e g a t i o n u n d e r l y i n g them are not independent and may i n t u r n be d e f i n e d i n terms of the s i n g l e p r i - m i t i v e i d e a of i n c o m p a t i b i l i t y p/q f a l s e or q (4) (read, " e i t h e r p is i s f a l s e " ) as f o l l o w s : ~P"-=-P/P -2$. / p v q .=. ~p/~q By use of t h i s p r i m i t i v e i d e a , t h e s i n g l e p o s t u l a t e [p/ ( q/r )] will /{[V (u/u)] / f(v/q)/ ( ( p / v ) / (p/v))]} s u f f i c e as the b a s i s f o r the s e n t e n t i a l c a l c u l u s . Now, however, great d i f f i c u l t y I s e x p e r i e n c e d i n drawing out the consequences of t h i s p o s t u l a t e . I t i s o f i n t e r e s t to note t h a t H i l b e r t and Bernays i n t h e i r "Grundlagen der Mathematik'? do not attempt to use an independent set of p o s t u l a t e s i n b u i l d i n g up the l o g i c a l c a l c u l i but r a t h e r g i v e l o n g l i s t s o f "Ausgangsformeln". ( c f . p. 6 6 , V o l . I) The method used to prove the independence of a s e t o f postulates ... i s as follows: , (n) . suppose the postulates (1),(2), If we can f i n d a concrete interpretation of the ( 2 ) , ( 3 ) , ... undefined terms such that but are (1) i s not , (n) are s a t i s f i e d , s a t i s f i e d , then (1) i s held to be independent of the others. For i f (1) were a l o g i c a l consequence of some or a l l of the others i t would have to be true i n any t a t i o n for which the others were a l l true. interpre- Thus i n order to establish the independence of the entire set i t i s s u f f i c i e n t to exhibit n suitable concrete interpretations, using each example to establish the independence of one corresponding postulate . That t h i s method i s useful, follows from the fact that i t i s often easier to see that under c e r t a i n circumstances c e r t a i n statements are true or f a l s e , th"a» i t i s to see that one formal statement does or does not imply another. Notice that t h i s method does not f u r n i s h a necessary condition for the of a postulate independence set, for i f an independent interpretation exists then the postulates are independent. If no interpretations can be found, however, i t i s not a proof of dependence. In our postulate set for s e r i a l order we may show the i n - dependence of (a) from (b), (c), (d) by interpreting the free variables f and g as follows: f ( x ) . = . "x i s one of the natural numbers" ,g(x, y ) . = . "x < y" . Then (a) becomes, " I f anything is a'natural number then i t i s greater than i t s e l f " , which i s , of course, f a l s e ; whereas, (b) becomes " I f x and y are d i s t i n c t natural numbers, then either x < y or y < x" , (c) becomes " I f d i s t i n c t n a t u r a l numbers, then not both (d) becomes " I f x, y, z bers and x < y and are any Thus, and (d) . S i m i l a r i l y we and (d) . We postulates should and y are x < y and y < x" , t h r e e d i s t i n c t n a t u r a l num- y < z , then to be t r u e p r o p o s i t i o n s . x x < z", which are a l l judged (a) i s independent of (b), ( c ) , can show the independence of (b), ( c ) , note a l s o t h a t the independence of the i n t h e i r a b s t r a c t form does not guarantee the i n - dependence of the p r o p o s i t i o n s a r i s i n g when an i n t e r p r e t a t i o n i s assigned t o the p r i m i t i v e elements. p a r t i c u l a r values For i n general of the p r i m i t i v e p r o p o s i t i o n s w i l l be more determinate than the a b s t r a c t postulates. Thus t h e r e may i m p l i c a t i o n s h o l d i n g which were not present We the these might consider now, i n the a b s t r a c t form. i n order to make t h i s idea c l e a r e r , simple example a f f o r d e d by . f ( x ) and be ( "3x, a system c o n s i s t i n g of two tulates Ox) are two undefined p r e d i c a t e s whose arguments range over some undefined set. of elements. f o r under the y).g(x, These p o s t u l a t e s are interpretations interpretations the f a t h e r and (3x, y)g(x, y" we a t r u e p r o p o s i t i o n , whereas Thus n e i t h e r of the two I f we now y) we formal and g independent, see that see that (3x, g(x, y ) . = . "x i s the f a t h e r of y" the g(x, y ) . = . "x (3x).f(x) y).g(x, postulates use the i n t e r p r e t a t i o n s Ox).f(x) i s t r u e ; by u s i n g f ( x ) . = . "x i s a man", sono of f f ( x ) . = . "x i s a centaur", g(x, y ) . = . "x i s the f a t h e r of y" i s f a l s e , whereas y ) , where pos- y) is becomes becomes f a l s e . impliesjthg(other. f (x). = . "x i s a man", , then, although the two a b s t r a c t statements are independent, the propositions, r e s u l t i n g /from t h i s i n t e r p r e t a t i o n are Consider now not. an a b s t r a c t p o s t u l a t e system; i t has b a s i s a system of undefined elements, and We undefined as i t s operations. then have a set of formulas (postulates), i n v o l v i n g the defined operations So the elements. notions and r e l a t i o n s which p l a c e r e s t r i c t i o n s that i n any i n t e r p r e t a t i o n of the unon undefined the p o s t u l a t e s become p r o p o s i t i o n s e i t h e r t r u e or f a l s e concerning Now the subject matter of t h i s i n t e r p r e t a t i o n . suppose we postulates. I f we have an a b s t r a c t system with, say, three conceive of a l l p o s s i b l e systems which as i n t e r p r e t a t i o n s of t h i s a b s t r a c t system, we stand s h a l l have d i f f e r e n t v a r i e t i e s d e f i n e d by the a b i l i t i e s of each system t o s a t i s f y , or f a i l t o s a t i s f y , each of the t h r e e p o s t u l a t e s . example, a system may (3) , o r i t may s a t i s f y a l l of the p o s t u l a t e s CD s a t i s f y (T) s a t i s f i e s the system ( T ) , QT) postulate (3) ) . from (J) and and f a i l , ^(J) i n s u r e the , (2) , on ( 3 ) , i . e . , i t (the c o n t r a d i c t o r y Recall t h a t the existence t e r p r e t a t i o n as t h i s would Q) (2) and For of of such an i n - independence of postulate (J). Before proceeding f u r t h e r l e t us diagram t o i l l u s t r a t e these 2 3 make use o f a type of Venn differentrs/stems. ^ Here the c i r c l e marked which s a t i s f y p o s t u l a t e (T) i n t e r s e c t i o n of the fying a l l three presnted c l a s s of systems , S i m i l a r i l y with 2 and postulates. , (2) r e p r e s e n t s the The shaded areas represent guarantees the and (3) i e.g., by t h e cross-hatched (where (T) (l) ) . stands now of p o s t u l a t e the new marked (2) from (T) ~Q) and this (2) shows the i n the independence abstract set. by these Now. considerations, consider the s i g n i f i c a n c e of some of the Suppose now was become becomes a f a l s e p r o p o s i t i o n . before f e a t u r e which i s introduced a r i s e s when we areas. and that f o r the p r o p o s i t i o n a r i s i n g from p o s t u l a t e have d i s c u s s e d C]D the area i s not n u l l would t e l l us a s s e r t as t r u e ® j C D ? ~ ( 3 ) ; i . e . , © . © . As we the the f a c t t h a t the c l a s s r e - t r u e p r o p o s i t i o n s and p o s t u l a t e ^3} may Now independence of the pos- i n t e r p r e t a t i o n s e x i s t f o r which p o s t u l a t e s (T) Thus we 3 . three c i r c l e s r e p r e s e n t s the systems s a t i s - systems whose e x i s t e n c e t u l a t e s (T) 1 other i n t e r p r e t a t i o n s e x i s t e d so that the c l a s s not n u l l . that ~" ( l ) . ~ ( 2 ) . (3) ,but This would show t h a t i t i s p o s s i b l e t h i s compound p r o p o s i t i o n i s equivalent to ~ ( ~ ® •© © ) (z) which shows us that p o s t u l a t e the c o n t r a d i c t o r y of (3) <2) , and t h e c o n t r a d i c t o r y or~(r© i s independent of also that of (2) . CD.— CT) CD) (^) and i s independent of . Or again, suppose the area marked A was not empty, t h e n t h e r e would e x i s t i n t e r p r e t a t i o n s such t h a t which i s e q u i v a l e n t to the f o l l o w i n g t h r e e -(-CD ®) — (~© .~®.-* CD) ~( -CD .-CD.- CD ) ~G) .-Q) implications: . ~(D 42 Thus, i f none of the 2 3 different areas were empty, t h e r e would e x i s t no i m p l i c a t i o n s whatsoever among the t h r e e p o s t u l a t e s . Or to put i t d i f f e r e n t l y , none of the p o s t u l a t e s w i l l follow e i t h e r from t h e remainder or t h e i r c o n t r a d i c t o r i e s or any combination thereof. If this s i t u a t i o n i s r e a l i z e d t h e n the pos- t u l a t e s are s a i d to be completely (5) . independent Note t h a t even i f the p o s t u l a t e s possess o r d i n a r y independence t h e r e i s a v e r y r e a l sense i n which they a r e not "completely" if one f o l l o w e d from the c o n t r a d i c t o r y of another. surmised complete independence i s a very As might be s t r o n g c o n d i t i o n and i s not possessed by many s e t s o f p o s t u l a t e s . (6) independent I t has been shown t h a t the p o s t u l a t e s f o r A b e l i a n groups and f i e l d s are com- p l e t e l y independent. We s h a l l now show that the p o s t u l a t e s we have been using f o r the r e l a t i o n of s e r i a l order are also com- p l e t e l y independent. We have as before a) the four postulates: ( x ) . *~g(x, x) b) '.(x, y ) . ( x ^y) g(x, y) v g(y, x) c) (x, y ) . ( x ^ y) -> ~ g ( x , d) (x, y) v ~ g ( y , x ) . y, z ) . d ( x , y, z).g(x, y ) . g ( y , z) -> g ( x , where the u n i v e r s a l q u a n t i f i e r s range over a s e t mits t h e binary r e l a t i o n g . K which ad- Now l e t us c o n s i d e r an i n t e r - p r e t a t i o n o f t h e a b s t r a c t system (K, g ) , o b t a i n e d elements of K z) and d e f i n i n g t h e r e l a t i o n i n d i c a t i n g f o r each p a i r of elements o f g K by l i s t i n g the e x t e n s i v e l y by whether g hold or n o t . The relation elements of K g d e f i n e d by w i l l be symbolized by 0, 1, 2 and t h e •43 f° x<( 1 1 2 0 1 2 F T T "F "F T F F F This interpretation of (K, g) s a t i s f i e s the postulates (a) to (d); i . e . , i t causes each of the abstract formulas (a) to (d) to become a true proposition. ~ g ( x , x) That i s , (x f y) -> g(x, y) v g(y, x ) , (x £'y) ->~g(x, y) • v ~ g ( y , x ) , etc. , S become tautologies i n K . i e.g. v (x) ~g(x, x) a) 'i • 3r 0 T 1 T T 2 y' (x = y) V g(x, y) v g(y, x) 0 0 T T F F 0 l F T T F 0 2 F T T F 1 0 F T F T 1 1 T T F F 1 2 F T T F 2 0 F T F T 2 1 F T F T 2 2 T T F F I 1 y) v ~ g ( y , x) X y (x = y) 0 0 T T T T 0 1 F T F T 0 2 F T F T 1 0 F • T T F 1 1 T T T T 1 2 F T F T 2 0 F T T F 2 1 F T T F 2 2 T T T T V'~ g ( x , 45 (x = y ) v ( y » z)v(x = z)v ~ g ( x , y ) v ~ g ( y , z) y g(x, z) X y z 0 0 0 T T T T T T F 0 0 1 T F F T. F T T 0 0 2 T F F T T T T 0 l 0 F F T F T T F 0 l 1 F T F F T T T 0 i 2 F F F F F T T • 0 2 0 F F T F T T F 0 2 1 F F F F T T T 0 2 2 F T F F T T T 1 0 0 F T F T T T F 1- 0 1 F F T T F T F 1 0 2 F F F T F T T 1 1 0 T F F T T T T 1 1 1 T T T T T T F 1 1 2 T F F T ¥ T T 1 2 0 F .F F F T T F 1 2 1 F F T F T . T F 1 2 2 F T F F T T T 2 0 0 F T F T T T F 2 0 1 F F F T F T F 2 0 2 F F T T F T F 2 1 0 F F F T T T F 2 1 1 F T F T T T F 2 1 2 F F T T F T F 2 2 0 T F F T T T F 2 2 1 T F F T T T F 2 2 2 T •T T T T T F K ( 0 , 1, Hence the system 2) with g(x, y) f i e s a l l the postulates (a) to (d) . so defined s a t i s - We w i l l indicate the character of t h i s interpretation of our postulates by writing ( + , +, +, +, ), which indicates that a l l four postulates become true propositions. Now to effect a proof that the s e r i a l order postulates are completely (K, g) (-> , + 2^-1 exhibit interpretations of such that each of the following characters i s r e a l i z e d . + ( , -, , + ( , -, ~, , ~, + + independent we + ), (-,.-•, (-, - ) , , + + , + + )> (+ , +),(-, + , + , , + + , ), -)» ~, + K (+ , + , + ), + , ~, , "),( + , -) In each of the following examples the basic set w i l l be K(0, 1, 2) and g(x, y) w i l l be redefined to obtain the 2^ - varieties. Define g(x, y) now by the following table: y) ^ 0 1 2 0 T T T l F F T 2 F F F g(x, g(0, (a) Since 0) holds, we have that ( 3 x ) . g ( x , x), i . e . ~ ( x ) . ~'g(x, x) and hence (a) i s not satisfied. (b) Holds, since g i s true f o r every pa i r of " d i f f e r e n t " elements, i . e . g(0, 1), g(l, 2), g(0, 2) a l l hold. (c) not Holds, since g ( l , 0 ) , g(2, 1), g(0, g(2, 1), 0 g(l, 2), g(6, 2) holds, but 4? (d) The only instance s a t i s f y i n g the c o n d i t i o n s of g(0, l).g£L, 2) is and we see t h a t holds, thus (d) satisfied. 0 1 2 0 F F T l F F F 2 F F F g(x, It g(0, 2) (d) i s y) i s easy to checJk t h a t p o s t u l a t e s f i e d , whereas (b) f a i l s . ( a ) , ( c ) , (d) Note that p o s t u l a t e are (d) holds because the c o n d i t i o n s of i t s i m p l i c a t i o n are not f u l f i l l e d ; no t h r e e elements do g(x, y) and g ( y , z) i . e . , for both hold. In the f o l l o w i n g examples we w i l l g i v e o n l y the of the r e l a t i o n g(x, y) satis- definition together with the c h a r a c t e r of the system i t generates. g(x, +) + (+, y) , 2 1 0 0 0 l l 2 2 (The a s t e r i s k i n d i c a t e s when (+, + g(x, g(x, g(x, y) , 0 0 + 1 2 g(x, 0 1 l 7 ^ 1 2 -¥ -) y) -) holds.) 0 2 y) + 2 y) 0 ) 1 2 (-, -> + g(x, y) (-, + , 1 0 2 g(x, y) ) l 0 2 0 0 >£- l 1 *c 2 2 (-, + g(x, y) 0 1 (+, -) . 1 0 2 1 +, •\ g U , y) - (-, - ) 1 0 2 1 1 2 2 -) (-, " g(x, y) 0 (-, 1 2 0 1 l 2 2 -) g(x, y) 0 1 2 "* > 0 l 2 l 2 -) +) - g(x, y) 0 (-, *« g(x, y) 0 2 0 l 0 1 -) 2 g(x, y) 0 - 0 2 ( + 0 l 2 CHAPTER VI Completeness: Another c h a r a c t e r i s t i c which a c o n s i s t e n t s e t of p o s t u l a t e s may or may ness. not possess i s t h a t of completeness or c a t e g o r i c a l - B r i e f l y , a set of p o s t u l a t e s i s c a t e g o r i c a l i f i t forms foundations f o r e s s e n t i a l l y o n l y one branch of mathematics, and i s n o n c a t e g o r i c a l i f i t can serve as a f o u n d a t i o n f o r two or more e s s e n t i a l l y d i f f e r e n t branches o f mathematics. To be more p r e c i s e , l e t us suppose t h a t we have a given set of abstract postulates. concrete i.e., The s e t w i l l be c a t e g o r i c a l i f any two i n t e r p r e t a t i o n s of the p o s t u l a t e s are i f a complete one-to-one isomorphic; correspondence can be s e t up between the elements and r e l a t i o n s o f any two i n t e r p r e t a t i o n s . Thus i n t h i s case any formal property which was t r u e of one system must have i t s analogue i n the other system. words the p o s t u l a t e s s u f f i c e t o determine the formal any concrete systems which s a t i s f y them. In other nature of I f the undefined are i n t e r p r e t e d i n v a r i o u s ways so as to o b t a i n concrete terms systems s a t i s f y i n g a l l the p o s t u l a t e s , the a b s t r a c t s c i e n c e i s r e p l a c e d by a number of concrete systems a l l o f which a r e f o r m a l l y e q u i - v a l e n t t o each other, and each o f which i s r e p r e s e n t a t i v e of the underlying s c i e n c e . Further c l a r i f i c a t i o n of t h i s concept r e q u i r e s the development of the i d e a of isomorphism between two mathematical systems. Isomorphism may be approached as a g e n e r a l i z a t i o n o f the .50. concept of equivalence of sets. Two sets are called equivalent i f t h e i r elements may be placed i n a one-to-one correspondence; i . e . , i f the two sets have the same number of elements. Thus equivalence, at least f o r abstract s e t s , i s a mathematical counterpart of the i n t u i t i v e idea of "resemblance". The question to be discussed now i s the existence of a similar concept of "resemblance" applicable to systems more general than a single abstract set. As we have discussed before, a mathematical theory i s a d i s course, not as a rule on one set, but rather on a system consist i n g of several sets, relations, functions, operations, etc. We desire then to seek an extension of the mathematical concept of equivalence, or the i n t u i t i v e concept of "resemblance", which is applicable to such more general systems. In order to indicate the procedure to be adopted, we consider f i r s t an example of the type of system involved i n group theory. three d i s t i n c t elements p, q, r , and l e t G of three d i s t i n c t elements 1, 2,3 ) . Let G-^ be a set of be another set 2 1 , 2 , 3 , (not the positive integers 0j, Define t h e group operations 0 by the following 2 tables: Thus 0]_ Moreover, °1 P q r p P q r q. q r r r P i s on G]_ x G^ 1 2 3 1 1 2 3 P 2 2 3 1 q 3 3 1 2 to G]_ and 0 2 i s on G 2 x G 2 to G. 2 i t w i l l be seen that these groups bear to each other a close resemblance, even though the sets G;-^, G p may be d i f f e r e n t , 'First i t i s noted that for the f u n c t i o n cp Gj and G represented by <P P 2 are equivalent sets, q 1 2 3 i s evidently a one-to-one correspondence between But here the system (G^, 0^) p sets involved. 2 9(p) <p(q) 9(r) 9(p) <p(p) <p(q) cp(r) <p(q) <p(q) cp(r) 9(p) cp(r) cp(r) 9(p) <p(q) which i s obtained from the table for G 2 x G its to 2 G ; cp-correspondent, one sees that 2 and also that (G , 2 If one 0) 2 defines P 2 = 0. 2 p i s on 2 It i s usual i n mathe(G-^, O^) and (G , 2 0) 2 "abstractly ; i d e n t i c a l " . Mathematical formulation of the connection just described between two a r b i t r a r y groups may (Gg, 0 ) 2 be two groups. morphic i f there the sets (6.1) 2 0j_ by replacing every matics to say that therefore the systems are G. by the t a b l e : 2 P entry by and has more resemblance to than just the equivalence of the an operation G-j_ G-^ and for every be given thus: let We s h a l l say that these groups are i s o - exists a one-to-one correspondence G 2 (G-^, 0-^) , such that, a, b e G, , cp(a)CL 9(b) = <p(aO.,b) cp between 52 1 (6.1) by s a y i n g that I t i s convenient t o a b b r e v i a t e carries Oi O2 . into Hence isomorphism, between groups, means the e x i s t e n c e of a one-to-6ne G]_ and G 2 cp which c a r r i e s Oi correpsondence between O2 . into An important o b s e r v a t i o n i s t h a t the c r i t e r i o n f o r ismorphism (G]_, O J L ) , i s meaningful even i f the systems (G , 0 ) are not 2 2 n e c e s s a r i l y groups, indeed even: if they s a t i s f y no axioms what: ever. With t h i s i n mind, we make the formal (6.2) Let -fehe systems 0]_ being s e t s , 0 (Gj, 0^) x G 2 G. to Then 2 G]_ 2 and (G^, 0]_) i s (G]_, 0 ] _ ) ^ = ( G , 0 ) ] | i f there 2 2 correspondence holds. G^ x G^ to 2 2 2 e x i s t s a one-to-one (6.1) G G]_, G 2 2 ( G , 0 ) [we w r i t e isomorphic to that , ( G , 0 ) be g i v e n , a b i n a r y o p e r a t i o n on a b i n a r y o p e r a t i o n on 2 definition: cp between G-j_ and G such 2 Such a correspondence i s c a l l e d an isomor- phism between (G]_, 0]_) and (G , 0 ) . 2 2 I t i s e a s i l y shown that isomorphism as so d e f i n e d i s an equivalence r e l a t i o n ; i . e . , i t has the f o l l o w i n g three p r o p e r t i e s : 1) ( G - L , 0 ) s ^ ( G - , Oj.) 1 t 2) (G , 0 ) ^ ( G , 0 )-^-(G , 0 ) ^ ( G 3) (G , 0 ) ^ ( G , 0 ) and x x t 1 2 2 2 2 2 2 1 0 ) X } (G , 0 ) ^ ( G , 2 2 3 O3 ).-*-( Gj^, 0]_) «(G , 3 Now t h a t we have d e f i n e d isomorphism f o r systems (G , 0 ) 2 2 O3) (G]_, 0]_) , i t would be d e s i r a b l e t o have a s i m i l a r n o t i o n of i s o - morphism f o r any mathematical systems t h a t are t o be d e a l t w i t h . It i s c l e a r that a mathematical system may a g i v e n set and o p e r a t i o n . i n v o l v e much more than For example, the b a s i c set f o r the p o s i t i v e i n t e g e r s (using Peano's axioms) r e q u i r e s a s e t , a s p e c i a l (element, " 0 " , and may a r e l a t i o n "the successor of" . be many b a s i c s e t s , r a t h e r than j u s t one. Also The problem of i n c l u d i n g " a l l p o s s i b l e " mathematical systems i n a d e f i n i t i o n of isomorphism is. one which does not at present to d e a l w i t h . the general seem p o s s i b l e Perhaps when the growing movement towards working i n meta-mathematical systems has f u l l y , t h i s w i l l be there achieved. developed more However, at present i t seems that only course i s to d e f i n e s e p a r a t e l y the concept of isomor- phism f o r each d i f f e r e n t type of .system. The motivation, of course, i s always the same f o r each d e f i n i t i o n ; namely, the n e c e s s i t y that the s e t s be e q u i v a l e n t the r e l a t i o n s and operations i n v o l v e d be r e l a t e d , as they i n t h e example g i v e n f o r groups. (6.3) on K If R) 2 2 if 2 and K-j_ and and K K 2 2 are s e t s and x K K 2 cp(a) R 2 2 such t h a t i f cp (b) ; ( i . e . , show t h a t our , then and (K-^, R^) a, b e K-j_ cp carries then R-j_ are r e l a t i o n s 2 i s isomorphic to a R-j_b into R) 2 cp between i f and only . d i f f i c u l t to g i v e r i s e to a non- To show t h i s i t i s only necessary to e x h i b i t i n t e r p r e t a t i o n s s a t i s f y i n g the p o s t u l a t e s , other R l a s t d e f i n i t i o n i t i s not p o s t u l a t e s f o r s e r i a l order c a t e g o r i c a l system. volves As an example, i f there e x i s t s a one-to-one correspondence On the b a s i s of t h i s two relation. the d e f i n i t i o n : Kp x (K , are Also the r e s u l t i n g r e l a t i o n of isomorphism must be an equivalence consider and t h a t the t a b l e s f o r one of which i n - a f i n i t e number o f elements i n i t s b a s i c s e t and i n v o l v i n g an i n f i n i t e set of elements. the I t would be impos- s i b l e then to e s t a b l i s h the one-to-one correspondence between the b a s i c s e t s as i s require_d i n the ness. above d e f i n i t i o n of categorica Two such interpretations are the following: 1) f ( x ) . = . "x i s one of the numbers ' g(x, y ) . = . »x < y" 1, 2, 3, ••• ,9" 1 2) f ( x ) . = . "x i s one of the numbers 1, 2, 3, ... , g(x, y ) . = . "x < y" . It i s e a s i l y checked that both interpretations l ) and s a t i s f y the postulates (a) and (d) . It would be natural now to ask whether for systems (% S2) s a t i s f y i n g (a) and K 1^ 2 (% gi) , (d) i t i s true that implies K 2) (K lf g l ) (K , 2 g) 2 It w i l l be seen that the answer i s affirmative. i f we add the condition that the basic sets, That i s , K , underlying the systems for s e r i a l order must possess always just n elements then the systems w i l l be categorical. In order t o show this property l e t us f i r s t make the defin- tion: (6.4) An element a Q of K w i l l be c a l l e d a "first"element i f (x). (x / a ) -* g ( a , 0 Lemma: For any f i n i t e set 0 K x) admitting the r e l a t i o n g and s a t i s f y i n g the axioms (a) to (d) there e x i s t s a unique f i r s t element Proof: a 0 Let CD or © . y Q be any element of K . ~ ( 3 x ) . ( x fi y ) . g ( x , y ) Q (3x).(x / y ).g(x, Suppose (l) i s true, then 0 Q y) Q fhen, either , _55.. - M3x).(x £ y ).g(x, y .) = 0 y ).g(x, (x).~{(x ^ Q 0 (x).(x ^ y ) -> Q y )^ Q g(x, (a) y ) Q But from axiom c) (x).(x £ y ) Q «(x),(x ^ y ) 0 -*--g(x, y ) v g ( y , x) V Grg(x, y ) -> g ( y , x ) ] Q 0 Using the theorem we a d j o i n (a) Q ( x ) . A ( x ) . ( x ) B ( x ) = (x).A(x).B(x) and (@) t o get ( x ) . [ ( x ^ y ) •> ~ g ( x , y H .Ox ^ y) 0 0 0 -* - ~ g U , y ) •* g(yo> 0 s ( ) . ( x ^ y ) - G ~ g ( x , y ) - g(y » x ((3) 0 0 0 x x 0 ) 0 « C^g(x, y Q 0 From which we o b t a i n by i n f e r e n c e (x). (x £ y ) -> g ( y , x ) 0 and thus case y 0 0 i s our d e s i r e d f i r s t element. Otherwise we have C2) ( I x ) . (x ^ y ) .g(x, y ) 0 Let y^ be such an 0 "x" . Then we have the same two cases a g a i n : either CD , ^ ( 3 x ) . ( x / y]_).g( , y^) or (D ( 3 x ) . ( x / yi).g(x, y^) x i f case ( l ) h o l d s we are f i n i s h e d element). Otherwise case CD ( i . e . , have e x h i b i t e d a f i r s t holds. Thus i n a f i n i t e number ( l e s s than must f i n a l l y a r r i v e a t case CD n ) o f such s t e p s we , f o r otherwise i f case always h e l d we whould be a s s e r t i n g the e x i s t e n c e of an CD infinite number of elements. We have shown the e x i s t e n c e now of an element, say which (x). (x ^ a ) •* g ( a , x) Q Suppose t h a t Q a' (r) i s another such element; i . e . , a , for Q 56 ( x ) . (x -f a ) •* g ( a , x) Q Thus i f a '(r) 0 ^ a we may a s s e r t Q we o b t a i n Q g(a ,a ) . 0 Q g ( a , a ) , but s i m i l a r i l y from 0 0 Combining these two a s s e r t s i o n we obtain ( 3 x ) : O y ) . ( x . y y).g(x, y ) . g ( y , x) = *-(x, y ) . ( x ^ y ) - * - . ~ g ( x , y) v <^g(Y, x) R e c a l l axiom c) (x, y ) . ( x ^ y ) - > - . ~ » g ( x , y) v ~ g(y, x) T h i s c o n t r a d i c t i o n proves that such an i.e., a Q hold n - 1 a from Q K . elements f o r which the axiom exist; We then have a (a) and (d) s t i l l ( r e c a l l t h a t they were a l l u n i v e r s a l s t a t e m e n t s ) . set w i l l a l s o have a f i r s t element, ( x ) . (x £ aj) -* g ( a where (x) now ranges over say a such t h a t o» a K —• £a ^ . 0 l > 2> a T h i s new a^, such that x) 1 } f a s h i o n we may order t h e elements of . K all cannot 0 i s unique, and the lemma i s proved. Now suppose t h a t we exclude set w i t h a Continuing i n t h i s as f o l l o w s : * * * » n a g ( a , a-jj, g(a-j_, a ) , ... , g ( a _ Q 2 n a ) 1 } n hold. Suppose now t h a t fying postulates K i s any other set of (a) to (d) . n elements We may order i t s elements t h e same as above; i . e . , i n t h e sequence b where hold. o> l > 2 > b b g ( b , b ), Q ± satis- ••• » n b g ( b , b ) , ... , g ( b _ i , 1 2 n b ) n Our required isomorphism is given by the function cp de- fined by f a l a 2 l b b 2 0 • • b t • • • • « a For and n • • . . . n g ( a , aj) i implies g Ijpia.^), 9 (a j )] implies g I j f a ^ , cp(aj)J g(a i } a j ) and hence d e f i n i t i o n (6.3) i s s a t i s f i e d . We have shown that, although the systems fying postulates (E, g) satis- (a) to (d) are not c a t e g o r i c a l , the addition of the axiom, (e) the set K contains p r e c i s i y n elements, causes the set to become c a t e g o r i c a l . Although the above d e f i n i t i o n of categoricalness is used c h i e f l y by workers i n mathematics, one finds the concept of completeness i n l o g i c a l works. corresponding One of the usual de- f i n i t i o n s i s e s s e n t i a l l y that a l l u n i v e r s a l l y v a l i d formulas of the system must be formally provable from the postulates i n a complete system. B y a universally v a l i d formula we that i s true by context mean one i n any i n t e r p r e t a t i o n of the postulates. In a general sense i t seems that the two concepts are rough-rly equivalent, for i f we have categoricalness, then every formula true by context must be provable. an i n t e r p r e t a t i o n which contained Otherwise there would exist a formula which was true for 5S. " that particular subject matter, but yet was not formally prova b l e from the abstract postulates. But since t h i s formula would be true i n virtue of the special features of that p a r t i c u l a r i n terpretation, i t would not hold f o r a l l interpretations and thus not a l l interpretations would be isomorphic, t h i s , however, cont r a d i c t s the assumption that the set was c a t e g o r i c a l . On the other hand i f every formula true by context is provable then every interpretation i s isomorphic to tthe abstract system and consequently to each other. To prove the system of s e r i a l order incomplete i n t h i s sense i t i s only necessary to e x h i b i t a formula which i s true i n some interpretation but does not follow formally from the axioms. Such a formual i s ( 3 x ) . f (x) which is true for any interpreta- t i o n which s a t i s f i e s the postulates (a) to (d) non-vacuously, ( i . e . , the basic set of elements is not n u l l ) , but which obviously cannot follow from the axioms since they are a l l universal statements and have no existential import. Let us show that the axiom system for the prepositional' calculus i s complete i n t h i s sense. We s h a l l alter s l i g h t l y the d e f i n i t i o n of completeness i n order t o e f f e c t t h i s proof. F i r s t note that f o r any given calculus there are, i n general, many d i f f e r e n t p o s s i b i l i t i e s of a true interpretation. The pract i c a l s i t u a t i o n , however, i s such that f o r almost every calculus which a c t u a l l y i s interpreted and applied, there is a c e r t a i n interpretation or a c e r t a i n kind of i n t e r p r e t a t i o n used i n the great majority of cases of i t s p r a c t i c a l application. might c a l l the normal interpretation of the calculus., This we 59 , The' normal interpretation of the axiom system f o r the sen- t e n t i a l calculus i s of course the usual l o g i c a l interpretation. We s h a l l c a l l t h i s calculus complete, then, i f every formula true by context i n t h i s interpretation is formally provable i n the abstract axiom system. The f i r s t step i n proving completeness, i n this sense, i s to lay down (semantical) r u l e s so that we may c l a r i f y the concept of "the set of a l l formulas ture by context". Since the normal interpretation of the sentential calculus i s a system of assertions, or declarative sentences, we w i l l turn to i t for our intuitive rules. By a declarative sentence, or simply sentence, we mean a l i n g u i s t i c expression concerning which i t i s meaningful to say that i t s content i s true or f a l s e . of the form "A i s P", where A Example, an expression i s the name for some thing and P stands for some property. Now from our empirical observation of language we f i n d that sentences can be combined i n a d e f i n i t e manner to form new sentences, and we lay down the following r u l e s of formations An expression of our system i s c a l l e d a sentence (or propo- s i t i o n ) i f i t has one of the following forms: F 1 "A i s P" (where A i s an individual and P i s a property "not p" 5where F 4 p applicable to A ) i s a proposition. "p and q",where p and q are propositions. Hp or q" , where p and q are propositions, "if Tt p, then q",, where p p i f and only i f q" where > propositions. and q p are propositions, and q are 60 We now lay down the following truth conditions and introduce a more compact notation f o r the above sentences T]_ : "A i s P" T 2 4 " —p" (read not p) i s true i f f p : p.q '• P (read p and q) i s true i f f p P . i s false. i s true and i s true. v q q. (read p or q) or i s true if-f p i s tujre or i s true . T.5 : p -> q T5 has the property : q T i s true i f f A F-[_ - Fg. q : p= q (read i f p then q) i s true i f f p i s false i s true. (p i f and only q) i s true i f f p and q are both true or both f a l s e . We see that according to the d e f i n i t i o n of our fundamental l o g i c a l connections, the truth or falsehood of a sentential combination depends solely upon the truth or falsehood of the sentences entering into the combination, and not up8n their content. This i s of course a f t e r we have determined the propositions to be true or f a l s e by use of T]_ . It should be noted now, that some of the fundamental connect i v e s may have the same meaning; i . e . , express the same t r u t h function. Thus '-"(-—p) has the same meaning as p ; i . e . , the double negative i s the same as the affirmative. Combinations ^such as these w i l l be c a l l e d equivalent, and w i l l have the property that i f we take a l l possible combinations of truth values of the original sentences both sides of the. equivalence w i l l have the same truth value. We s h a l l now show that any combination of sentences can be brought Into a certain Normal Form transformations. This conjunctive by means of equivalence normal form consists of a conjunction, of disjunctions i n which each member of a disjunction i s either a sentence or the negation of one. Demonstration: On the basis of the nation of equivalence we may set forth the following rules for the transformation of sentential ex^ pressions. al) Calculatio ns with the symbols and "v" follow the associative, commutative and d i s t r i b u t i v e laws. a2) For ~ ( ~ p ) we may substitute a3 ) We may write ~ - p v — q p . f o r M p . q ) and-^p.^q for -^(p v q). a4) for We may subtitute ^ p v q f o r p -*• q and ~p v q. ^ q v p p == q . The trmsqfrmation i s effected thus: f i r s t , by employing Rule a4) we can substitute f o r any expression an equivalent one that no longer involves the symbols and " ing expression i s then e n t i r e l y i n terms of Now by successive . The r e s u l t - "v", applications of Rule a3), the negation signs can be brought farther and farther inside u n t i l f i n a l l y they stand only over the elementary sentences. For example from ~ j ] p v q . ~ q ) v (r.qjl we have f i r s t Mp v q\. ~ q ) . ^ ( r .q) then by another a p p l i c a t i o n of *Mp v and f i n a l l y . a3 ) q) v ~ ( ~-q). r v^q (^p.—q) v q. ~ r v ~ q . 1 Thus we may transform any expression to a form composed of negated and unnegated elementary sentences connected by "." and "v" . Now by applying the distributive law of "v" over "." to (~'p.~'q) v q one obtains, i n our example (~p v q). (~q v q). ( ~ r v~q) and this is the desired conjunctive normal form. It i s now our task to find those combinations of sentences which are logically true; i.e., true independently of the truth values of the elementary sentences. Since for any given logical expression we can find an equivalent one in normal form,the solution of t h i s problem is only a matter of determining when an expression i n normal form represents a logically true . (L-treu) combination of sentences. This deter- mination i s easily arrived at by means of the following rules which are direct consequences of T-j_ - T^ : bl) p v—p i s L-true. b2) if p i s true, b3) if p i s true and p v q i s L-true for a l l q i s true, then q. p.q i s L=true. It is to be understood that for the p and q's above we may substitute any sentence or combination of sentences. So i n accordance with Rules bl), b 2 ) , b3), al) i t may be seen that a l l expression i n normal form (i.e., i n the form (p]_ v p 2 v ... ).(p " v 2 v , . . ) . ... ) are true,which have the characteristic that i n each disjunction there occurs at least one of the elementary sentences together with i t s negation. Moreover, these are the only expressions which are logically true. For i f every elementary sentence—in some conjunct — which is i t s e l f a 'disjunction o f a normal form occurs as a f a c t o r e i t h e r negated or only unnegated, t h e n t h i s d i s j u n c t i o n c a n be made i n t o a false sentence by r e p l a c i n g each unnegated symbol by a f a l s e sentence and each negated symbol by a t r u e sentence. Then a conjunct of the normal form i s a f a l s e sentence and c o n s e q u e n t l y the e n t i r e e x p r e s s i o n y i e l d s a f a l s e sentence. Thus i t i s not the case t h a t the normal form y i e l d s a t r u e sentence independently of t h e t r u t h values of i t s elementary component sentences, and thus i s not L-true. As we have d i s c u s s e d b e f o r e the formal c a l c u l u s may be b u i l t up on the undefined s e t of elements defined operations 1) "v" and p, q, r , ... and the un- " ~ » , by t h e use of the axioms p v p.->- p 2) p -*.p v q . 3 ) p v q-->. q v p 4) (p -»• q) (r v p. -*• . r v q) and the r u l e s of s u b s t i t u t i o n and i n f e r e n c e . In t h i s system i t may be shown q u i t e e a s i l y , although we s h a l l not take the space here, t h a t Rule a l ) - a4) and b l ) - b3) may be obtained from t h e axioms we must read the r u l e s bl) p v ^ p b2) i f p as d e r i v e d r u l e s . Now, however, b l ) - b3) as f o l l o w s : i s a theorem i s a theorem, (i.e. , provable) p v q i s a theorem for a l l q , etc. For t h e n o t i o n o f trutii i s r e p l a c e d by t h a t o f p r o v a b i l i t y i n a formal calculus. Hence, i t f o l l o w s t h a t a l l the o b s e r v a t i o n s made e a r l i e r i n 64. eonncection with these rules; e.g., those concerning normal forms and the class of l o g i c a l l y true sentences, may also be derived from the axioms. Thus a formula from our axiom system i s prov- able, i f and only i f each d i s j u n c t i o n of i t s conjunctive normal form contains two components of which one i s the r e s u l t of operat i n g on the other by T W f . We see then that the class of l o g i - c a l l y true sentences coincides exactly with the class of provable formulas, and thus the axiom system i s complete. There i s s t i l l another d e f i n i t i o n of completeness which i s stronger; i . e . , moie l i m i t i n g , than the previous one. To arrive at t h i s d e f i n i t i o n , l e t us consider f i r s t a set of axioms which are written i n terms of a set B operations, r e l a t i o n s , etc. of primitive A elements, I f we consider a class of a l l formulas which can be written (following specified syntactical rules of formation) i n terms of the base B , we f i n d that, i n general, these formulas f a l l i n three classes: , those which follow from - A ; a , those whose contradictor i e s f o l l o w from 2 A ; and CX3 , those such that neither they nor their contradictories follow. Here, i t i s to be noted that the members of a considered independent of the set A i f an interpretation s a t i s f i e s 2 can no more be than the members of a]_ ; A , then a l l the members of ct]_ w i l l be transformed into true propositions, and a l l those of a into f a l s e ones; so that we may combine c l a s s , 2_2> a a n d s a y t h a t member of t h i s class. A et-^ and 2 into one determines the truth value of every I f we add to A a member of the class a 12 we s h a l l get either a contradiction or redundancy, whereas i f - we add a member of the new set w i l l be s e l f consistent — although i t may not be an independent"set, owing to the fact that the new ,65 condition either alone or i n conjunction with some of the o r i g i n a l members of A , may imply other members of A . Now, t h i s new set w i l l have a wider range of implications; creased, and 0:3 correspondingly diminished. to add formulas from a ^ to A until a 12 w i l l be i n - So, we may continue 0:3 vanishes altogether. • When this occurs the set obtained i s said to be complete. Sometimes t h i s new set of axioms is c a l l e d the completion of a set i s complete A . Thus i f and only i f i t determines the truth value ( i . e . , provability) of every formula that can be constructed on i t s base. This d e f i n i t i o n i s often worded as follows: a system i s complete i f and only i f the addition of a previously unprovable formula to the axiom system always yields a contradiction. The two different statements of this d e f i n i t i o n of completeness, while c e r t a i n l y equivalent, give r i s e to d i f f e r e n t techniques i n constructing proofs of completeness. Using the f i r s t emphasis, l e t us show that the postulates (#) to (d) for s e r i a l order are not complete. Here we must show that there exists a pair of mutually contradictory formulas which can be written i n terms of the basis of the set (a) to (d), and such that neither i s provable from the set. (3x).f(x) and Two such formulas are (J.f(x) [ > ~ > ( B x ) . f ( x ) ] . The proofs that these formulas do not follow from the set i s , of course, l i k e the proofs of independence given before: we f i n d an interpretation satisfying (a) to (d) and f a i l i n g to s a t i s fy the formula that i s to be shown not to follow. Let f (x) mean "x i s a satellite of the moon" and g(x, y) mean about "x revolves y" . Then (a) to (d) are s a t i s f i e d vacuously, while (3x).f(x) f a i l s . Let f(x) mean "x i s a s a t e l l i t e of the earth" 66 (and g(x, y) mean "x i s not i d e n t i c a l with y" . Then (a) to (d) are s a t i s f i e d , the l a s t three vacuously, while (3x).f(x) fails. since the formula Thus our set of postulates i s not complete ( 3 x ) . f ( x ) , which i s written properly i n terms of the primitive ideas of our set, can be neither proved nor d i s proved (the contradictory proved) i n the system. Turning to the second way of s t a t i n g this s t r i c t e r defini- t i o n of completeness; namely, that the addition of an unprovable formula to the system always yields a contradiction, we find that i t s use may be i l l u s t r a t e d quite simply i n the sentential calculus. Suppose, then, that A t e n t i a l calculus. Let Thus of course i s not provable since i t is equivalent to N N is an unprovable formula of the senbe the normal form corresponding to A. A . Now r e c a l l that the t o t a l i t y of provable formulas i n the sentential calculus corresponded to the t o t a l i t y of formulas whose normal forms contained, i n every conjunct, and i t s contradictory. both an elementary proposition So the non-provability of there e x i s t s a conjunct C tory elements; i.e. , must be of the form C PjL where (for a l l In and ~ q C i ) p p.^ substitute 2 q if A implies that which contains no mutually contradic- V ""P-^ v . .. and — p ^ for each negated C st.q Now V A do not both occur. f o r each pj_ . p^ that occurs unnegated After t h i s subsitution we obtain v q v q v . . . v q . s 3 q i s added to the system as an axiom, we should have as theorems i n this new system, f i r s t the formula C , and f i n a l l y But now we could substitute -"q q itself. N , then for 67 jq and have the c o n t r a d i c t i o n t h a t We mentioned ness was q and ^q are both p r o v a b l e . e a r l i e r that t h i s l a s t d e f i n i t i o n of complete- more r e s t r i c t i v e t h a n the p r e v i o u s d e f i n i t i o n . To prove t h i s statement i t i s o n l y necessary t o f i n d an axiom system which i s complete a c c o r d i n g t o t h e f i r s t d e f i n i t i o n but does not the requirements of the second d e f i n i t i o n . the r e s t r i c t e d p r e d i c a t e c a l c u l u s . fulfil Such a system i s t h a t o The completeness of t h i s sys- tem i n the broader sense; i . e . , that a l l u n i v e r s a l l y v a l i d formulas are p r o v a b l e , has been proved by K. Goedel hand H i l b e r t On the o t h e r (2) has shown that the s t r i c t e r form of i s lacking i n this calculus. essentially (7) • as f o l l o w s : completeness H i s method i s q u i t e simple and i s first he g i v e s an a r i t h m e t i c a l p r e t a t i o n to the c a l c u l u s so that every inter- axiom as w e l l as a l l provable formulas assume the value 0 , and moreover, the con- t r a d i c t o r y of a formula with v a l u e 0 w i l l have a value then e x h i b i t s a f o r m u l a which has t h e v a l u e proves i s nonprovable. i t s contradictory. Now 0 1 . and which he t o d i s p r o v e t h i s formula we must prove But i t s c o n t r a d i c t o r y w i l l have the value and thus be non-provable. He 1 Thus the v a l i d i t y of t h i s f o r m u l a i s 1 undecidable and t h e axiom system i s not compile. C l o s e l y connected w i t h the problem of completeness i s another, more g e n e r a l problem which concerns incomplete, as w e l l as theories. I t i s the problem of f i n d i n g , complete f o r a given deductive t h e o r y , a general method which would enable us t o decide whether or not any p a r t i c u l a r formula c o n s t r u c t e d i n t h e terms of t h i s t h e o r y can be proved w i t h i n t h i s t h e o r y . T h i s important and c u l t problem i s known as the D e c i s i o n Problem. One diffi- can e a s i l y v i s u a l i z e the value of a d e c i s i o n procedure i n mathematics; i t c o u l d t h e n be decided whether such formulas as Fermat's e.g., "last 6.6^ theorem" j (n) (n > (where the y, z) .x 31 + y n q u a n t i f i e r s range over the were v a l i d or The M3x, 2) = z 11 ^ set of r a t i o n a l i n t e g e r s ) not. f i r s t d e d u c t i v e system f o r which a mechanical d e c i s i o n procedure was e x h i b i t e d was the p r o p o s i t i o n a l c a l c u l u s . procedure i s , of course, the g i c a l formulas. f a m i l i a r matrix t e s t f o r t a u t o l o - Immediately a f t e r t h i s c a l c u l u s , proceeding i n the d i r e c t i o n of more complex s t r u c t u r e , one r u n s i n t o ties. The The r e s t r i c t e d p r e d i c a t e t h e o r y ) , despite calculus difficul- (general q u a n t i f i c a t i o n i t s completeness, d i f f e r s from the simpler l o g i c i n t h a t i t possesses no mechanical t e s t of v a l i d i t y . Here we must, i n g e n e r a l , grope f o r the d e d u c t i o n which w i l l e s t a b l i s h the v a l i d i t y of a given formula. l a c k of i n g e n u i t y Church (£) has i n discovering be generally i n q u a n t i f i c a t i o n theory. However, quest f o r d e c i s i o n methods does not t h i s p o i n t , f o r i t can be shown t h a t predicate calculus a successful has been reached. for come to a dead end s o l u t i o n to the and Simpler p r o o f s H. Behmann (11) . the d e c i s i o n problem been solved only monadic predic-srtevariables. p o s s i b i l i t y of d e c i s i o n i n t h i s case was Loewenheim (9) . at i n c e r t a i n s e c t i o n s of In f a c t the d e c i s i o n problem has a l l formulas c o n t a i n i n g simply a such a procedure, f o r Alonzo proved that no mechanical r o u t i n e can adsniate f o r d e c i d i n g v a l i d i t y the Moreover, t h i s i s not f i r s t recognized have been given by T. by The L. Skolem (10) These methods of p r o o f extend beyond the r e s t r i c t e d p r e d i c a t e c a l c u l u s , since they s o l v e t h e d e c i s i o n pro- blem i n the case o f monadic p r e d i c a t e s predicate c a l c u l u s of the second order a l s o f o r the (where q u a n t i f i e a t i o n extends to 69. predicate The with variables). q u e s t i o n now r e s p e c t to pleteness. such a r i s e s as to the concepts I t can be as the situation d e c i s i o n p r o b l e m and shown t h a t t h e g e n e r a l l o g i c i s a d e q u a t e as a f o u n d a t i o n f o r c l a s s i c i a l the higher predicate c a l c u l i p r e s s the t h e o r y unreasonable of c l a s s e s . tics begin with, called are numbers. of the and type; construed The n o t a t i o n o f elementary as r e f e r r i n g "x + y" and "x.y" notation (3x)(y){ x + y = y | , ideal test treatment of truth described. of t h i s deduction, had or p r o o f . sense t h a t e v e r y technique to s e t t l e o f sum was half once p r e s e n t e d , mechanical, admitted and y, z etc., natural sign product. " = " Typical are: consist (y. ideal had was admitted is mechanical notation unobtainable. a similar situation a technique complete i n the of a proof. i n t h a t every ofLa m e c h a n i c a l x)} in a expressible i n the f o r a second b e s t : v a l i d formula x, number t h e o r y i s m e r e l y t h a t t h e o r y would This technique o f mathema- e x c l u s i v e l y to t h e I t happens, however, t h a t t h i s one turn . i . e . the u s u a l ( x ) ( y ) { (x.y) - f o r a l l statements may Here the v a r i a b l e s of I n t h e r e s t r i c t e d p r e d i c a t e c a l c u l u s we and t h e r e (12) Goedel of q u a n t i f i c a t i o n p l u s t h e a d d i t i o n a l notation ex- s e c t i o n s of c o m p l e t e n e s s we K. number t h e o r y . truths expressible i n this An by row logic the i n which t o consider only t h a t branch are a l l o f one Moreover, T h u s i t w o u l d seem t h a t i t i s not obtained l e t us elementary quantification which as a l a n g u a g e For a d i s c u s s i o n of t h i s a f a r reaching r e s u l t To serve com- of c l a s s e s mathematics. t o look f o r completeness i n c e r t a i n mathematics. to i n mathematics test Also of weaker the alleged proof, of correctness. 70. But the discovery of such proofs i s e n t i r e l y unmechanical. Such would seem to be a reasonable objective also i n elementary number theory. What i s wanted i s a proof procedure just broad enough so that a l l truths expressible i n the notation of elementary number theory, and no falsehoods, come to admit of a proof. Although one would expect the discovery of these proofs to be unmechanical, the rules of proof, however, must be h a l f mechanical i n the sense explained above. Proofs would have no claim on conviction i f they could not i n p r i n c i p l e be checked for conformity to r u l e s . Now the remarkable f a c t which Goedel has established is that even t h i s objective, f o r a l l i t s apparent reasonableness, attainable. Elementary i s un- number theory, unlike the predicate c a l - culus, r e s i s t s complete systematization. Given any proof procedure P f o r elementary number theory, even of the "half-mechanical" kind, Goedel shows how a statement Sp of elementary number theory can be constructed which w i l l be true i f , and only i f , i t is not provable by the procedure Either Sp P . i s provable, i n which case i t i s f a l s e and so the general proof procedure P i s discredited, or else and not provable, i n which case the proof procedure Sp P i s true is incomplete. The following summary of Goedels method i s due to Quine: Since "v", "->•" and are translatable into conjunction and negation, and existential quantifiers are translatable i n the fashion " ~*(x).*-'..." , and variables may j -A. j ./V j -A. y • 9 • be l i m i t e d to 9f we may think of the notation of elementary number theory as com- posed of just t h i s nine-sign alphabet; . ( ) = + Now l e t us assign the numbers . 1,2, the nine signs of t h i s alphabet. x ' ... ,9 a r b i t r a r i l y to To complex expressions b u i l t up of that alphabet l e t us assign the number which i s expressed by the corresponding string of d i g i t s ; to the statement = x); e.g., the number 3$,43^,584 i s assigned. (x)(x Thus every statement of elementary number theory, true or not, receives a number. Now i t turns out that as long as the proof procedure P i s h a l f mechanical, at least, i t i s possible within the notation of elementary number theory to formulate an open sentence, "... x ..." l e t usyf^which i s true of any number if x x i s the number of a statement which can be proved by Next Goedel shows, i n effect, how to find a number sentence " — conditions: x __" of elementary " _ ~ x «—." number assigned to (3x)y i s true of " (3x) ^ F i n a l l y the sought x S p P . and an open n exclusively; n i s the x .—. ."-'(... x ... ) ~t " . i s taken as the quantification . ~ ( . . . x ... )\ n , and hence i f and only i f ment provable by n P . number theory f u l f i l i n g these It w i l l be true, c l e a r l y , i f and only i f of i f and only n "... x ..." i s false is not the number of a state- But the statement numbered n i s Sp i t - s e l f , which, therefore, i s true i f and only i f not provable. From t h i s result we obtain a corresponding conclusion r e garding the theory of classes. Elementary number theory i s trans- latable into the notation of the theory of classes and therefore the incompletability of elementary number theory e n t i a l s the i n - co-mpletability of the theory of classes. Also since the concepts of the general theory of classes are adequate as a foundation for c l a s s i c a l mathematics, any effort toward a complete deductive theory for c l a s s i c a l mathematics must necessarily f a i l . It i s doomed to f a i l u r e as soon as i t attempts to encompass even that well-behaved i n f i n i t y of objects c a l l e d natural numbers. One can do no better, from that point forward, than add special axioms now and again to strengthen the system f o r s p e c i f i c purposes. But i f i n view of Goedel's r e s u l t our knowledge about class and number is subject to unexpected l i m i t a t i o n s , the very oppo- s i t e i s true of our knowledge about such knowledge. Goedel's result brings a new branch of mathematical theory to maturity, a branch known as "Metamathematics" or proof theory, whose subject matter i s mathematical theory i t s e l f . F r u i t f u l further research i n proof theory i s now going f o r ward. M, Pressburger (Warsaw) and T, Skolem (Oslo) have shown that when elementary number theory i s further limited to the extent of dropping m u l t i p l i c a t i o n and keeping just addition, or vice versa, the r e s u l t i n g theory does admit of a complete proof procedure and even of a decision procedure, truth. What i s more surprising, Tarski (13) or mechanical tested has shown that the ele mentary algebra of r e a l numbers likewise admits of a decision procedure. The notation of this elementary algebra i s precisely the same as that descirbed above for elementary number theory, includ- ing both addition and multiplication, the only difference being that the variables are construed now as r e f e r r i n g to r e a l numbers generally rather than to natural numbers. Despite the seemingly (greater complexity i s completable of i t s s u b j e c t matter, elementary algebra and m e c h a n i c a l l y decidable w h i l e elementary ber t h e o r y i s not. num- References 1) Amer. Math. Monthly, V o l . 29 (Oct. 1922), p. 357-35S. 2) Hilbert and Ackermann, Grundztlge der Theoretischen Logik. 2nd ed. p. 2 J . 3) P. Bernays, Axiomatische Untersuchung des Aussagenkalkuls der P r i n c i p i a Mathematica. Math. Zeitschr. V o l . 25, (1926). . 4) J . G . P . Nicod, A reduction^ i n the number of the primitive propositions of l o g i c , P r o c . Camb. P h i l . Soc. V o l . 19 (1V17). cf? Quine, Mind 41. 5) E . H . Moore, Introduction to a form of General ^Analysis. New Haven Mathematical Colloquium (190o). 6) The Complete Independence of Hurwitz's Postulates for Abelian uroups ana J i e i a s . Annais or Mam. V o l . 2 3 , p. 313. For an interesting set of postulates possessing complete independence see also, Per Satz von arithemischen Mitt e l i n axiomatischer Begriandung. Math. Ann. 68, and the complete independence of these post u l a t e s , Math. Ann. 7 6 . 7) K. G6del, Die Vollstandigkeit der Axiome des logischen 'Funktionen-Kalkuls. J l h . M a t h . P h y s i k . V o l . 37, (1930J. 8) A. Church, A note on the Entscheidungsproblem. Symbolic Logic, V o l . 1, (1936). Journ. of 9) L . Lewenheim, Ueber Mflglichkeiten-in R e l a t i v k a l k u l . Math. Ann. Vol. 76, 11915). 10) T . Skolem, Untersuchungen fiber die Axiome des KlassenKalkuls. V i d . Skrifter I , i Jath.-nat. Klasse 1919, No. 3. 11) H. Behmann, Beitrage zur Algebra der l o g i k und zum Entscheidungsproblem. Math. Ann. V o l . 89 (1922). 12) G. GBdel, Ueber formal unentscheidbare Sfltze .der P r i n c i p i a Mathematica und verwandter Systeme. Mb., far Math, u. Physik, V o l . 3& (1931), c f . On undecidable propositions of Formal Mathematical systems, mimeographe Princeton (1934). 13) A. T a r s k i , A Decision Method for Elementary Algebra and Geometry, Santa Monica, 19U>. v
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Postulational methods
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Postulational methods Stallard, Samuel Ernest 1951
pdf
Page Metadata
Item Metadata
Title | Postulational methods |
Creator |
Stallard, Samuel Ernest |
Publisher | University of British Columbia |
Date Issued | 1951 |
Description | Since the middle of the 19th century there has been a rapid growth in the use of the postulational method in mathematics. Concurrently with this growth such concepts have arisen as the consistency, independence or completeness of abstract sets of postulates. The definitions of these concepts, as well as the methods used to test postulates for these properties, are widely scattered throughout mathematical and logical, literature. The object of this thesis has been to make a survey of this new field (which we might call Axiomatics) and to indicate some of the techniques used in it. The method has been to take a simple set of postulates (those for the relation of serial order) and then devise proofs for the consistency, completeness, etc. of these postulates. Each proof illustrating one of the methods currently in use for testing postulates. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2012-03-01 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080626 |
URI | http://hdl.handle.net/2429/41042 |
Degree |
Master of Arts - MA |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1951_A8 S8 P6.pdf [ 4.1MB ]
- Metadata
- JSON: 831-1.0080626.json
- JSON-LD: 831-1.0080626-ld.json
- RDF/XML (Pretty): 831-1.0080626-rdf.xml
- RDF/JSON: 831-1.0080626-rdf.json
- Turtle: 831-1.0080626-turtle.txt
- N-Triples: 831-1.0080626-rdf-ntriples.txt
- Original Record: 831-1.0080626-source.json
- Full Text
- 831-1.0080626-fulltext.txt
- Citation
- 831-1.0080626.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080626/manifest