UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Postulational methods Stallard, Samuel Ernest 1951

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

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

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  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo 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

Comment

Related Items