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

POSTULATIONAL METHODS by Samuel Ernest Stallard S i r P.6 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTERS OF ARTS in the Department of MATHEMAT ICS we accept this thesis 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 of the 19th century there has been a r a p i d growth i n the use of the postulational method i n mathematics. Concurrently with t h i s growth such concepts have arisen as the consistency, independence or complete-ness of abstract sets of postulates. The d e f i n i t i o n s of these concepts, as well as the methods used to t e s t postu-l a t e s for these properties, are widely scattered through-out mathematical and l o g i c a l , l i t e r a t u r e . The object of 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 indicate some of the techniques used i n i t . The method has been to take a simple set of postulates (those £.G-r.the r e l a t i o n of s e r i a l order) and then devise proofs f o r the consistency, completeness, etc. of these postulates. Each proof i l l u s t r a t i n g one of the methods currently i n use f o r t e s t i n g postulates. Historical Introduction Our modern concern with postulational nethods had its historical beginning in Greek mathematics, a mathematics, which, although chiefly remembered for its work on the real numbers and geometry, really made its greatest contribution <in the form of the above mentioned methodology. This contribution was left 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 is possible to construct five, and only five, regular solids is ascribed to Theaetetus about the middle of the fourth century B.C. Euclid later in 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 its rigid perfection. Its lastiriaj contri-bution - and Euclid's - to mathematics, was not so much the store of 465 propositions which it offered, but rather the new methodology which, as we shall see, was far ahead of its times. For the first time in history masses of isolated dis-coveries were unified and correlated by a single guiding principle, that of rigorous deduction from e x p l i c i t l y stated assumptions. Before Euclid, Eudoxus and some of the Pytha-goreans had executed important details of the grand design, but i t remained for Euclid to see i t a l l and see i t whole. He is therefore the perfector, i f not the sole creator, of what is today called the postulational method, the central nervous system of livi n g mathematics. It seems strange to us today that after this clear exposi-tion of the postulational method, it. had to wait u n t i l the nineteenth century to be f u l l y appreciated. At least i t was not u n t i l then that the method, was sufficiently abstracted from geometry to enable mathematicians to consider applying i t to other field s . Euclid's geometry of course continued in the postulational tradition. But this, apparently, was only inertia, for i t was decades after the outburst of projective geometry in the nineteenth century, before anyone attempted to put i t on a sound postulational basis. (And i t was not until the l#30's that any serious attempt was made to handle elementary algebra in this postulational manner.) Not u n t i l 1399 in the work of D. Hilbert (l£62 - 1943, German) on the foundations of geometry, was the f u l l impact of Euclid's methodology f e l t in a l l mathema-t i c s . Concurrently with the pragmatic demonstration of the creative power of the postulational method in 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 in theoretical physics in the 1930's. Earlier writings in the method, notably by E. Mach - 1916, Austrian^ in mechanics and A. Einstein (l$7c> - ) io relativity, 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 is 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 itself. 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 al-most simulataneously that mathematical systems are not super-naturally 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 re-cognized as this type of free creation. Hamilton's rejection (1043) of the postulate that multi-plication 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 res-trictive. 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 essential for the s e l f consistency of symbolic reasoning, was any more a necessity f o r a non-contradictory algebra, than i s Euclid's p a r a l l e l postulate for a s e l f consis-tent geometry. Moreover, to the astonishment of many i t was found that the modified algebras, as f o r example Hamilton's, were adaptable to mechanics, geometry and mathematical physics. Thus mathematics achieved the freedom i t has today because of the a t t e n t i o n being turned again to the postulational method. An experiment of Veblen Before proceeding further to a discussion of the postula-t i o n a l method I f e e l i t would be to the point to look at an int e r e s t i n g experiment (1) performed at Princeton University by a class of graduate students i n Projective Geometry under the / d i r e c t i o n of Professor 0. Veblen. This experiment originated i n the desire to emphasize the point that our l o g i c a l processes may. be independent of any p a r t i c u l a r set of mental images asso-ciated with the objects of thought and that they may i n fact be performed without any knowledge of the concrete objects to which the primitive propositions or postulates r e f e r . As we can re a d i l y see, the success of the abstract postulational 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 to think i n t h i s formal manner. The experiment was as follows: the instructor proposed to the class that c e r t a i n members make up a set of postulates giving properties s u f f i c i e n t to charac-t e r i z e some set of objects chosen by them and that these pos-tulates should be submitted to the remainder of the. class, the l a t t e r were then to attempt to determine the precise nature of c The objects without any further information concerning them than what was contained i n the propositions of the set of pos-tu l a t e s . The way i n which the students were to proceed was to make deductions from the given postulates and to derive theorems concerning the objects referred to i n them u n t i l they had learned enough about these objects to know what the postulate makers had i n mind when they formed the postulates. Of t h i s experiment Professor Veblen has written as follows: "The exercise was a success i n showing how mathematical deduc-tions can be made without knowledge as to what one i s reasoning about. It also brought out v i v i d l y the problem of the s i g n i f i -cance of the l o g i c a l processes as a method of discovery. While there i s a sense i n which i t i s true that you cannot get anything out of a set of postulates except wh at has been put i n them, you can at least f i n d out what has been put i n them. This i s what the solver of t h i s problem has to do i n a simple case. In the more complicated cases, the student i s apt to think that he understands what is i n the axioms, but every time that he wit-nesses the der i v a t i o n of a new theorem i t turns out that there was something i n them that he had not seen before". 6 I Chapter I Hawing discussed the history of the postulational method and having given a b r i e f example to i l l u s t r a t e the p o s s i b i l i t y of reasoning abstracted from a l l interpretations, l e t us pro-ceed to examine i n greater d e t a i l the nature of this method. To arrive at the underlying motivation of the postulational school i t i s only necessary to consider the d i f f i c u l t i e s which arise when one attempts to give a careful presentation of any precise subject. We are led immediately to a discussion of language, for the degree of clearness which we obtain w i l l j depend d i r e c t l y on what attitude we adopt toward the same. To bring the problem into focus consider our everyday use of language. Here we have a usage which, although clear enough to enable us to deal with day by day natters, s t i l l f a l l s f a r short of the precision demanded by science and mathematics. An attempt at greater precision i n the use of language i s i l l u s t r a t e d by insurance p l i c i e s , l e g a l documents, govern-ment forms, etc. Here the ideas to be conveyed are not excep-t i o n a l l y d i f f i c u l t but the importance of avoiding ambiguity i s greater than i n everyday discourse. Therefore, elaborate phraseology i s introduced to guard against the misinterpretations that might otherwise be possible. One can easily think of fur-ther examples of more or l e s s s p e c i a l i z e d forms of communications. It becomes apparent that the more s p e c i f i c the subject matter under discussion, the more serious i s the confusion a r i s i n g from the unqualified use of everyday language. It i s not surprising, 1 then, that i n mathematics we f i n d language troubles as per-plexing as they can be anywhere. It might naturally occur to 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 for agree-ment i s generally admitted as i s shown by the often heard demand, "define your terms", during a discussion. It i s easy enough to decide that we must define doubtful terms, but what are we going to agree on as constituting a de-f i n i t i o n ? Let us examine, then, the everyday source of d e f i n i -t i o n s , the dictionary. Here we find , on looking up the meaning of the word, a variety of possible meanings for the same word; e.g., for the adjective " f a i r " , we f i n d nine different meanings. In a discussion i n which i t i s important to understand, indepen-dently of context, such a m u l t i p l i c i t y of meanings i s intolerable. Thus, i f a d e f i n i t i o n i s to be helpful i n an exact discussion, i t must be unambiguous. Also a d e f i n i t i o n , i f i t i s to be of any use at a l l , must give the meaning of a new word i n terms of words which are a l -ready known. Otherwise, we might be forced to look up unknown words i n the d e f i n i t i o f i i t s e l f . There i s s t i l l hope, however, that t h i s process w i l l come to an end by eventually r e a c h i n g recognizable terms. We cannot always be sure of success i n the process, however, as the following example w i l l show. Suppose that we wish to lea r n the value of the Austrian coin, the Krone. A dictionary gives: , Krone: The former monetary unit of Austria-Hungary, lc>92-1925; also the corresponding coin, equivalent to 100 Heller. But then, Heller: In Austria, up to 1925, a small copper coin equivalent to 1/100 Krone. Here we come to a dead end. Rather, we are caught i n a vicious c i r c l e with no side turnings. Now we have arrived at the heart of the trouble. The inescapable f a c t i s that the distionary must inevitably lead us i n an unending c i r c l e : A Krone i s 100 Hellers; a Heller i s 1/100 Krone. This c y c l i c d e f i n i t i o n must arise;simply because the d i c -tionary is trying to do the impossible. It i s t r y i n g to define a l l words. That t h i s i s impossible may be e a s i l y seen. For consider that a d e f i n i t i o n replaces an unknown word by a c o l -l e c t i o n of known words. From th i s i t follows that a defined word i s an unnecessary word, f o r i t may be replaced by i t s defining phrase. So i f a l l words were defined, no words would be neededT ,This impossibility shows that some wrds must be ever undefined. Before t r y i n g to a r r i v e at any solution to t h i s problem, l e t us see how dangerous t h i s process- of eydic d e f i n i t i o n r e a l l y can be. Cohsider the wellknown paradox, i n which the Barber of S e v i l l e is defined by t h i s statement: "He shaves a l l those men of S e v i l l e and only those men of S e v i l l e who do not shave themselves." We ask now, "Who shaves the Barber of S e v i l l e ? " We f i n d as a consequence of our d e f i n i t i o n that i f the Barber shaves himself, then he does not shave himself; i f he does not, then he does. 9c When t h i s paradox f i r s t appeared i t caused quite under-standable concern, for the d e f i n i t i o n of the Barber seemed quite p a r a l l e l to the sort of d e f i n i t i o n s used i n mathematics. Actually, the source of the d i f f i c u l t y i s easy-to locate. The d e f i n i t i o n of the Barber involves the men of S e v i l l e . If the Barber i s to be considered as one of the men of S e v i l l e , then the d e f i n i t i o n i s cyclic, that i s , the Barber i s defined, i n part, i n terms of himself. Although we w i l l not go into the matter here, c y c l i c d e f i n i t i o n s are dealt with by o s t r a c i -zing them; hence, the d e f i n i t i o n of the Barber i s to be regarded as inadmissible. Note that i f the Barber i s regarded, not as a man of S e v i l l e , but as a new entity introduced by h i s d e f i n i t i o n , the paradox disappears for he may shave himself 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 his actions only with respect to the men of S e v i l l e , of whom he i s then not one. Now that we have shown the need of eliminating 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 elimination can be achieved. A hint that a s o l u t i o n exists l i e s i n the f a c t that the dictionary i s often of value to us. True, i f we look up a,word, and are lead through a chain of unfamiliar synonyms back to the o r i g i n a l word, the dictionary has not helped. But i f just one of the synonyms i s known, then automatically they a l l become known. Definitions can be h e l p f u l , then, i f they always give meanings ultimately i n terms.of a lisfcrof knd.wn words. • We have already indicated that not a l l ^ o r d s can be defined. There should be then a basic l i s t of words that x^ e forego de-f i n i n g ; these words are learned pragmatically by the elaborate means by which one learns to speak in 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 virtue of the elaborate network of paths con-necting 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-sisting of words and phrases, upon which a l l agree, and about which there is no argument. The remainder of the language would then be built up by following some agreed on rules of grammar and by.a systematic use of definitions 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 in mathematics the underlying language is Logic, which is taken in i t s entirety by the postulational school as basic. It is not really necessary to assume the whole of logic, since the logical calculi may be built 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 calculi which are applied in science a" logical cal-culus serves as i t s basis. Each of the non-logical c a l c u l i , mathematics and the calculi applied i n science, s t r i c t l y speaking consist of two parts: a logical basic calculus and a specific calculus added to i t . The basic calculus could be approximately the same for a l l those calculi; i t could consist of the sentential calculus and a smaller or greater part of the functional calculus. The specific partial calculus; e.g., a branch of mathematics, does not usually contain additional rules of inference but only additional primitive sentences, c a l l e d axioms or postulates, and usually some additional primitive terms. As the basic calculus i s e s s e n t i a l l y the same for a l l the diff 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 at a l l but to des-cribe only the s p e c i f i c part of the calculus. What usually i s ca l l e d an axiom system i s thus the second part of a calculus whose character as a part i s usually not noticed. For any of the mathematical and physical axiom systems i n t h e i r ordinary form i t i s necessary to add a l o g i c a l basic calculus. Without i t s help i t would not be possible to prove any theorem of the system or to carry out any deduction by use of the system. An axiom system, contains, besides the l o g i c a l constants, other constants which we may c a l l i t s s p e c i f i c or axiomatic constants. Some of these are taken as primitive; others may be defined. The d e f i n i t i o n s lead back to the primitive s p e c i f i c signs and l o g i c a l signs. An i n t e r p r e t a t i o n of an axiom system i s given by semanti-c a l rules for some of the s p e c i f i c signs, since for the l o g i c a l signs the normal; i . e . , l o g i c a l , i nterpretation i s presupposed. / Chapter II  The Specific Concepts of Mathematics Having noted i n the previous discussion that any mathema-t i c a l theory w i l l consist of two parts, a basic underlying l o g i c and a s p e c i f i c mathematical superstructure, we wish now to d i s -cuss some of the concepts which are fundamental to the l a t t e r . F i r s t l e t us set forth the terms which are primitive for mathema t i c s . Admittedly, any primitive term i s to he undefined and to achieve an understanding of such terms one must observe them i n use. Yet a c t u a l l y "behind the scenes" one possesses an i n t u i -t i v e grasp of the meanings of these basic concepts. Also these meanings may be communicated by means of broad preliminary d i s -cussions. Elements: Perhaps the most elemental of the s p e c i f i c mathematical concepts is that of a completely abstract and formless e n t i t y . It i s completely unessential to have any d e f i n i t e picture of these e n t i t i e s or objects or to have any knowledge of t h e i r precise nature. It is necessary that the e n t i t i e s of our d i s -course possess such generality that terms whether concrete or abstract, singular or p l u r a l , w i l l be included. Accordingly, the word, "element" i s introduced to replace, "object", "entity" or similar words, with the intention that "element" should be understood i n the broadest possible sense. The high degree of 13 abstractness associated with the term "element" should not be allowed to cause any discontent, for we have the compensating factor that there i s no need to f i x concrete meanings early i n the development of a theory. An element i s thus a blank into which may be read or inserted any s p e c i f i c meaning. i Sets of Elements: In order to prevent l o g i c a l chaos i t i s found necessary to l i m i t our discourse i n any given discussion or theory to c e r t a i n p a r t i c u l a r elements, which we imagine to be before us throughout the theory. That i s , any elements which enter our discourse must belong to a family of elements which i s fix e d and invariant throughout the theory. Such a family i s called-a set, and the elements comprising i t are said to belong to, or be .members of, the set. Note also that there can be no objection to allowing two or more fixed sets to be before us i n a single theory. For since the elements of a set are arbitrary they may themselves be sets of elements. Equality: Whereas the statement "a e A" says something about an element a and a set A , aamely^, "a belongs to A", there i s a type of statement which involves two elements or two sets and which occurs so often that one takes i t for granted. Let a , b be elements of any kind. They may, i n p a r t i c u l a r be sets. We say that "a i s equal to b" , and write "a = b", i f a and b are the same element. Thus a = b means "a and b are two lab l e s f o r the same object' If i t i s f a l s e that a = b then we write a ^ b . Thus 7from t h i s point of view i t appears that the statement "equals may be substituted for equals" means only that charing the name of an object does not change the object. To i l l u s t r a t e that statements of equality may have content consider the following example. Let A be the set of a l l p r e s i -dents of the United States during World War I , and l e t B be the set consisting of Woodrow Wilson. Then A = B i s a true statement. Moreover, t h i s statement conveys the information that Woodrow Wilson, and only Woodrow Wilson, served as presi-dent, during World War I . Subsets: Suppose that we have the set A before us, where A = [a, b, c] A l i t t l e r e f l e c t i o n shows us that once A has been admitted to our consideration, we automatically admitted s i x other sets, namely, 0 , bj, [b, c ] , [a, c ] , £a] , [b] , \c] This process of selecting sets, each one of which i s a "part" of the given set, may be stated generally. Any set r e s u l t i n g from the process being c a l l e d a subset of the o r i g i n a l set. Thus we formulate a d e f i n i t i o n of subset as follows: A set B i s a subset of a set A whenever a l l the elements of B are elements of A and we write B C A or A 3) B , It would be now possible by using the above concepts to buil d up a substantial algebra of sets introducing by d e f i n i t i o n s the concepts of set-sum, set-product, etc. Ordered Pairs Although i t i s a e s t h e t i c a l l y desirable that the l i s t of -15. p r i m i t i v e conc-epts f>or a theory be as small as possible, i t often happens that when c e r t a i n concepts are defined instead of being placed on the language basis, 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 conceptually 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 less 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 ourselves i n t h i s s i t u a t i o n now; i t s being possible at t h i s point to describe a l l further mathematical concepts i n terms of sets of elements only. However, for the above reasons i t is convenient to l i s t one further concept as primitive. The term to be introduced i s "ordered pair". This i s a set consisting of two elements together with a certa i n s p e c i f i -cation as t o which element "comes f i r s t " and which "comes second". This order i s indicated by writing (a, b) f o r the ordered pair a, b i n which a preceeds b . Note that the set [a, b] has nothing to do with the order of the elements, since |[a, b] = [b, a If (a, b) and (c, d) are ordered p a i r s , then i t i s clear from our concept of equality that (a, b) = (c, d) only when a = c and b = d: . The immediate use to which the concept of ordered pair w i l l be put i s to define the Cartesian Product; of two sets A and B . This set is the set of a l l ordered pairs whose " f i r s t element i s from A and whose "second" element i s from B . Thus Df. A x B = the Cartesian Product of A and B & [(a, b) ; a e A, b e B] I Let us look back f o r a moment at the terms just introduced. The basic terms which have appeared are element, set and ordered 16 k p a i r . But also there have been introduced other concepts, subset, cartesian product, etc It i s evident that these l a t t e r terms were defined and also that considerable ordinary language was used i n ef f e c t i n g the d e f i n i t i o n s . However, i f one were to s t r i p away the unessentials, one would f i n d that the a u x i l i a r y mathematical concepts are defined i n terms of the basic ones with the help of a few additional terms, the basic l o g i c a l terms. The l o g i c a l terms met thus so f a r are: " i s a member o<5f " or "e" "nnt" " a l l " or "every" as i n "the set of a l l ..." "such th a t " as symbolized by [(a, b) ; a e A, b e B ] "there e x i s t s " " i f ... , then ..." ft . ?! i n "or" "and" These terms are a l l accepted without question, with meanings as commonly understood i n l o g i c . 3-' Chapter III Further Specific Terms of Mathematics. It w i l l be r e c a l l e d that objections to dictionary d e f i n i -t i ons were ra i s e d on the grounds that words are defined i n terms of themselves. In order to avoid t h i s d i f f i c u l t y the need for a l i s t of primitive terms was stressed. Now with the foregoing primitive terms av a i l a b l e , we may construct a legitimate d i c -tionary, i n which further mathematical concepts may be defined s t r i c t l y i n terms of the basic ones, namely, "element" "set", " ordered p a i r " . Let us indicate then, quite b r i e f l y , how the nearly basic mathematical terms, " r e l a t i o n " , "function", , Toperatic and "one-to-one correspondence" may be now defined. Relations: Given a set M with elements a, b, c ... we usually say that R i s a r e l a t i o n i n M i f the statement aRb i s e i t h e r true or f a l s e for a l l elements a, b, c ... of M . e.g. M = set of a l l people. R = " i s the father of" Notice now, however, that any such r e l a t i o n determines uniquely a set of ordered p a i r s of elements from M , namely, the set of a l l (a, b) such that a e M, b e M, and aRb . The . r e l a t i o n i s thus f u l l y known i f t h i s set i s known and v i c e versa. Hence, i t w i l l be found very convenient and f r u i t f u l to regard the r e l a t i o n as i d e n t i c a l with t h i s set of ordered pairs. Note IB. that there i s no need to r e s t r i c t the r e l a t i o n to being on one set. e.g. A i s the set of a l l men B i s the set of a l l women R = " i s the husband of" • This r e l a t i o n determines a subset of the cartesian product A x B which is the set of a l l possible ordered pairs of ( f i r s t ) 'a man and (second) a woman. We thus give as the mathematical d e f i n i t i o n of r e l a t i o n the following: (3.1) Let A and B be sets. A r e l a t i o n on A x B i s a subset of A x B . Thus i f R i s a r e l a t i o n on A x B *i e , R c A x B then, i f a e A, b e B, the statement that "a i s i n the r e l a t i o n R to b" or "aRb" means that (a, b) £ R . When.the sets A and B have only a few elements i t i s possible to specify a r e l a t i o n R by means of the following con-venient t a b l e : Where an asterisk i n a p a r t i c u l a r row and column indicates that the ordered pair consisting of the element at the l e f t of the row and top of the column are i n the required r e l a t i o n . Thus i n the above example ( a 2 , b^) , (a^, b 2) belong to R . Notice that we could also give a truth table i n order to specify e.g. V 19. t h i s r e l a t i o n B eg. R F T A f a T F F F In t h i s case i t i s convenient to r e c a l l the more conventional concept of a r e l a t i o n as being a propositional function i n two variables and which we might conveniently write as R(x, y) . Suppose now that R i s a r e l a t i o n on A x B . The subset a r e l a t i o n on B x A . It i s c a l l e d the converse of R and i s denoted by R . Thus bRa means the same as aRb and we make the following d e f i n i t i o n : (3.2) R* [(b, a) e B x A ; aRb ] It i s possible now to build up an interesting algebra of rela t i o n s using the above d e f i n i t i o n of a r e l a t i o n and the algebra of sets. However, to bu i l d such an algebra would not d i r e c t l y bear on our project of t r a c i n g through the program of the postula-t i o n a l school and so i t w i l l be pertinent only to mention the following reference i n t h i s connection. "Relations binaires, ferme^ tures, correspondences de Galois" by Jacques Riguet, B u l l , de l a Societe Mathematique de France. Vol. 76 (194S) pp. 115 - 155* Functions: Before defining a function we need f i r s t one more d e f i n i t i o n r e l a t i n g to r e l a t i o n s . (3.3) Let A and B be sets and R a r e l a t i o n on A x B . of B x A consisting of those pairs (b, a) for which aRb, i s 2C Then the domain of R ^ (_a e A , there exists b e B and a R b] -jjC r -l the converse domain of R =' [b e B, there exists a e A and a fi bj Now there is a feature which some, but by no means a l l , r e l a -tions exhibit, a feature according to which r e l a t i o n s might be c l a s s i f i e d . ( 3 . 4 ) Let A and B be sets and R a r e l a t i o n on A x B . Then R i s a function =' for every a e domain of R there exists exactly one b e B such that a R b If the domain of R = A , then the function R is said to be A to B . N 0te i n t h i s connection that the converse domain of R may be B or a subset of B . One-torone Correspondences: Let F be a function on A to B , where A and B are, as usual, given sets. Since F i s a r e l a t i o n on A x B , the converse F of F i s a r e l a t i o n on B x A . It i s natural to ask whether F is necessarily, or may be, a function too. It w i l l s u f f i c e to consider a pair of simple examples. Let A be the set [P]_, P 2, P3] and B the set [q^, q2, q3) and define two rel a t i o n s F and; G by means of the following t a b l e s : F ^2 3^ G <>1 ^2 q 3 P i P l ?2 P 2 P 3 P 3 #• 21. It i s evident that F i s not a function, since i t does not f u l f i l d e f i n i t i o n (3 .4) above. Moreover, i t is equally clear that G is a function. These examples serve to show that the converse of a function can be a function but need not be. This leads to the d e f i n i t i o n (3.5) Let A and B be sets and F a function on A x B . Then F i s a one-to-one correspondence between A and B i f 1) The domain of F = A 2) The converse domain of F = B 3) F i s a function. Clearly, i f F i s a one-to-one correspondence between A and B , then F i s a one-to-one correspondence between B and A; F is then c a l l e d the inverse of F. Binary Operations: In the general discussion of functions on A x B or on A to B , A i s an arbitrary set. A special case arises so often that a special terminology and notation for i t i s desirable. The case i s when A i s the cartesian product of two sets A^ and A2. (3 .6) If F i s a function on A]_ x A 2 to B , th en F i s c a l l e d a binary operation, or simply an operation. The element's of the domain of F are of course the pairs ( a 1 ? a 2) with a 1 e A^ and a 2 e A 2. The F-correspondent of (a-p a 2) i s an element b e B, which we might write as b = F ( a 1 , a 2) or i n another notation suggested by mathematical custom b = a xF a 2 22 -The peculiar nature of a binary operation makes possible a very ^compact tabular representation. eg. i f A x = [p-p p 2 ] A 2 = U l » B = [ s l r s 2 , s 3 ] , we might define a binary operation F as follows: F q i q 2 P i S 3 S 2 P 2 S l S 2 Baturally A, , A 2 , and B need not be d i s t i n c t , as a matter of fact a common type of operation i s one on A x A to A a s we f i n d i n group theory. The present chapter has defined c e r t a i n non-basic, but nearly basic, terms with the help of the basic concepts, "set", "element" and "cartesian product". Also c e r t a i n standard notations for these concepts have been introduced. F i n a l l y we should point out that the notation a R b has two important interpretations. If a e A , b e B , and R i s a r e l a t i o n on A x B , then a R b i s a proposition about a and b . I f ( a , b ) e S C A x B and R is an operation on S to C , then aRb i s an element of C . An I l l u s t r a t i o n of the Postulational Method Having now discussed the motivation behind the postulational method as well as the s p e c i f i c materials which are the building blocks of a mathematical theory, l e t us examine the issues i n -volved i n putting a given subject matter on a postulational basis. We w i l l choose as simple anT example as possible so as not to cloud -2' the issues by technical d e t a i l s . I Suppose then that we have a c o l l e c t i o n M of objects, no two of which have the same weight and which we widi to compare, with respect to the r e l a t i o n "heavLer than". We begin by l i s t i n g 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 true for t h i s subject, thus we might have: a) If x belongs to M , then x i s not heavier than i t s e l f . b) If x and y are d i s t i n c t members of M , then either x i s heavier than y or y i s heavier than x . c) I f x and I are d i s t i n c t members of M , then i t is fal s e that x i s heavier than y and y i s heavier than x • d) If x , y , z are d i s t i n c t members of M and x i s heavier than y and y i s heavier than z ,+.hen x i s h e a v i e r U^n z This is an instance of s e r i a l order, a concept of considerable importance i n mathematics. Now, as a step towards making these propositions e n t i r e l y formal l e t us borrow the notation of the predicate calculus of lo g i c and define f(x) as " x belongs to M " and g(x, y) as " x i s heavier than y " , thus we obtain a) (x) ,f (x) -> ~ g(x, x) b) (x, y) :f (x).f (y). — (x = y ) . -> . g(x, y) v g(y, x) c) (x, y ) : f ( x ) . f ( y ) . ~ (x = y ) . -* . ~ [ g ( x , y).g(y, x)] — g(x, y) v ~- g(y, x) d) (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 postulates completely abstract we must now dis-card the interpretation of M as being a p a r t i c u l a r set of objects (1) we make the d e f i n i t i o n that d(x,y,z). = ,(x / y)(y / z)(x / z) 24. (this could be done also, by considering M to be defined by f; i . e . , M i s the set of a l l x such that f ( x ) , and then allowing f to be undefined) and consider g(x, y) as standing for some undefined binary r e l a t i o n between x and y . At t h i s stage, the undefined terms and the postulates s t i l l have some con-crete or psychological significance to the mind. But i f the un-defined terms are r e a l l y recognized as undefined, i t must be pos-s i b l e to abstract a l l previous connotations from them, and t o treat them as mere symbols devoid of any special significance to the mind other than what may be implied about them i n broad preliminary des-cr i p t i o n s or i n the statement of the postulates. For example, the following proposition is e a s i l y seen to be true of the o r i g i n a l subject matter, " i f x and y are members of M , and x i s not heavier than y and y i s not heavier than x , then x and y are i d e n t i c a l " . However, f o r the corresponding theorem (3.7) (x, y) :f (x).f l y ) . ~ g ( x , y ) . ^ g ( y , x ) . •* .(x = y) to be true i n the abstract theory, i t must follow; i . e . , be deducible, from the postulates (a), ... , (d) by the rules of l o g i c alone. Using the r e s t r i c t e d predicate calculus we see that i t follows from postulate (b). For (x, y ) : f ( x ) . f ( y ) . ~ ( x « y) . -*• . g(x, y) v g(y, x) six, y ) : ~ [f (x).f (y) .~-(x = y)] . v . g(x, y) v g(y, x) = (x, y):~^f(x) v ~ f ( y ) v ^ ^ ( x « y) v g(x, y) v g(y, x) sr(x, y ) : ~ [ f ( x ) . f ( y ) . ~ g ( x , y ) . ^ g ( y , x)] v(x = y) = (x, y): f ( x ) . f ( y ) . - g ( x , y ) . ^ g ( y , x). -> . (x = y) It i s worthy of note at t h i s point that, although we speak of the consequences of a set of propositions, i n a c t u a l i t y the con-sequences fellow from one proposition which is the conjunction of the various members of the set. 25 Now i f we consider the compound postulate (a). (b). (c ). (d ), from which a l l the implications must follow which are theorems of the postulate set (a),(b),(c),(d), we see that i t has only f and g occuring as free variables. Thus we may write our compound premise as a function (propositional) of f and g , say F(f, g). It should now be equally possible to reinterpret f and g i n new ways, which have concrete significance d i f f e r e n t from the preconceived significance of the o r i g i n a l terms. Whenever such an interpretation i s assigned to the set, F(f, g) i s trans-formed into a compound proposition, l e t s say P , and the r e l a -t i o n of the postulates to a theorem Q w i l l he P -*• Q . With each new interpretation of the symbols each postulate of the set w i l l again make a concrete statement, and, i f the in t e r p r e t a t i o n i s suitable, t h i s can be judged to be true or f a l s e . Each postulate is said to be s a t i s f i e d i n such an interpretation. At this point i t seems that quite a d i s t i n c t i o n might be drawn betweer abstract and interpreted systems. For i f no int e r p r e t a t i o n has been given and a theorem G(f, g) (refering to above system) follows formally, as did (3.7) above, then we are asserting that (f, g).F(f, g) -> G(f, g) . So that the theorems are a c t u a l l y statements of implications. On the other hand i n an interpreta-t i o n s a t i s f y i n g the postulates we assert that the postulates are ture; i . e . , using the example above we assert P . Then i f P -*• Q i s true i n the system we may make use of the rule of i n -ference from our underlying basis of l o g i c and assert Q , CHAPTER IV Consi stency. We come now to the most important concept i n axiomatics, namely, the concept of the consistency of an axiom system. The formal d e f i n i t i o n of consistency runs usually as follows: an axiom system w i l l be c a l l e d consistent i f i t is impossible to prove from the postulates, by means of the l o g i c a l operations, two propositions which are mutually contradictory. This d e f i n i -t i o n requires some j u s t i f i c a t i o n , for at f i r s t sight 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 contradiction^ i . e . , i t i s not possible to have true both the propositions A and — A (not-A). In f a c t , however, the p r o v a b i l i t y of two theorems A and ' A would condemn the entire system as meaningless. We may show t h i s quite e a s i l y as follows: l e t us assume Hilbert's (2) postulates f o r the l o g i c of propositions as well as the usual rules of s u b s t i t u t i o n and the ru l e of inference; i . e . , from the two theorems A and A -*• B we obtain the theore B . As a consequence of the second axiom and the rule of sub-s t i t u t i o n we obtain, Theorem: If A i s any theorem and B any proposition, then A v B i s a theorem. Proof: p p v q Axiom 2 A ->'A v B Substitution Since A i s a theorem, therefore A v B i s a theorem. Inferenc 27 Now consider the s i t u a t i o n when both A and ~- A are theorems. First**'A being a theorem implies ~A v B i s a theorem for any proposition B i n the mathematical system under consideration. But then, since A v B . =". A -»• B and since A i s a theorem we may assert B . S i m i l a r i l y we may prove that B i s a theorem. Thus we could prove any proposition i n the system as well as i t s contradictory! To test a set of postulates for consistency i s therefore one of the central problems of the postulational school. The usual method of tes t i n g i s to f i n d a concrete int e r p r e t a t i o n which s t a i s f i e s the abstract postulates. If the system i s i n -consistent two propositions A and —* A w i l l be implied by the axioms, but now that the axioms are asserted as truths we have by the rule of inference " A and '*w. A " asserted as a true proposition about the "outside world". This i s generally f e l t to be impossible. From t h i s s i t u a t i o n , namely, that an incon-sistent set of postulates cannot possible have a true interpre-ta t i o n , we obtain that a s u f f i c i e n t condition for consistency i s the existence of a true i n t e r p r e t a t i o n of the postulates. Note that we do not know i f the condition i s a necessary one. We cannot infer from the fact t h a t a :set does not have a true i n t e r -pretation that i t is not consistent. It seems that the in t e r -pretational test implies a t a c i t assumption that any accurate description of an existing state of a f f a i r s is consistent. This seems rather unsatisfying for i t appears that i n t h i s view con-sistency depends upon a certain metaphysical bias, (eg. Parmenides or Hegel) that r e a l i t y i t s e l f is fundamentally r a t i o n a l and there-fore consistent. A r i s t o t l e has an i n t e r e s t i n g discussion i n 2d. Book r of Metaphysics on the r e a l t i o n of l o g i c and existence, especially chapter I I I . A r i s t o t l e holds that the fundamental laws of l o g i c , aich as the Law of Contradition, hold of "every-thing that i s " ; i . e . , that nothing that actually exists can possess self-contradictory properties. It i s easy to f i n d interpretations which s a t i s f y our postu-la t e s (a) to (d) . For example we might take f ( x ) . = . "x i s a member of the solar system" g(x, y ) . = . "x i s nearer the sun than y" . The statements which we now obtain from (a) to (d) under t h i s interpretation are e a s i l y seen to be true i n the l i g h t of our previous knowledge. Let us now investigate other methods for proving the consis-tency of a set of postulates. F i r s t we might mention that i f the set i s quite simple i t i s sometimes possible to see that the contradictory of any theorem would possess a concept not con-tained i n the axioms and thus not follow from them. As an example consider again our postulates (a) to (d) . They are a l l uni-versal functions and thus do not assert the existence of any special e n t i t i e s . Example, i n the case of (a) we have (x).f(x) -> ~ g(x, x) 5= ~ ( a x ) . f ( x ) . g ( x , x) which merely denies the existence of a thing of a c e r t a i n kind, and the only functions that can be inconsistent with t h i s one are those with e x i s t e n t i a l import. Secondly, the basis for an e n t i r e l y formal ( i . e . without appealing to interpretations) method of proving consistency, has already been given i n the proof that i n an inconsistent system any statement i n the system would 2-9. ,be provable. In this method one has to f i n d a suitable formal property P , for which one can show: 1) Every axiom has P . 2) The application of any r u l e ; e.g., rule of inference, rule of substitution, etc. , to one or two formulas with P leads to a formula with P . Then i t i s clear that every provable for-mula has P . 3) One shows now that a c e r t a i n formula does not have P . Therefore this formula is non-provable and hence the calculus i s consistent, since there would be no noh-provable formulas i n an inconsistent calculus. The choice of the property P needs otherwise no j u s t i f i c a t i o n ; i t may be quite a r t i f i c i a l and with-out a plausible r e l a t i o n to the ordinary 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 turn to Hilbert's axiomatization of the sentential calculus i t s e l f . We s h a l l con-sider the calculus to be e n t i r e l y formal and b u i l t upon the basis (K, v, —* ) , where K i s a set of elements symbolized by p, q , r , ... ; v i s a binary operation on K x K to K and i s a unary operation on K to K . The primitive formulas are 1) 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) . Note that p -> q.='. p v q . For proving new formulas from the primitive formulas, as well as from formulas already so proved, we have the following two r u l e s : 3--0. (, a) Rule of Substitution: we may substitute f o r a variable; i . e . , a lower case l e t t e r p, q, etc., any combina-t i o n of variables, provided the substitution i s complete. p ) Rule of Inference: From the two formulas A and A -> B we obtain the new formula B . In order to prove the consistency of the calculus we proceed as follows: We interpret the variables p, r , ... as being proposi-tions; i . e . , statements which are either ture (T) or f a l s e (F) . We now define the operations v and '—by the tables q V T F — -T T T F F T F T We now state our property "P" that i s possessed by a l l the axioms and propagated by the rules a) and ^) , This con-s i s t s i n the fact that, on the basis of the interpretation, the axioms yield the truth value T f o r every possible set of values of the variables. That the axioms 1) through 4) possess t h i s property i s shown thus. 1) p — ( p v p) V P 2) p q ~ P V (p v p) T F T T T F T T F T T T F F T T ' F T T T T F F T T F 31. p q -*(p v p) V (q v T T F T T T F F T T F T F T T F F T T F P q r ~ (~-p v q) v{—<(r v p) V (r v q)} 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 v F F F T T T F Therefore the fomulas of the four axioms have the above mentioned property. Now under application of the two rules used for i n -f e r r i n g new formulas; namely, a) and ) the property p e r s i s t s . For, with regard to the f i r s t r u l e , i t i s evident that the range of values for the variables can cer t a i n l y not be extended by sub-s t i t u t i n g an expression for any of them. And when we inf e r formula B from the two formulas A and ^A v B by means of the second r u l e , the property of always y i e l d i n g the value T i s carried over from the l a s t two formulas t o the one inferr e d . For since the formula A always y i e l d s the value T , ~ A always has the value F ; hence —"A v B always has the same value as B , so that B as well as *- A v B always has the value T . Thus we see that every provable formula i n our calculus w i l l have the value T . Now the formula p v, q.-> p which can,be. constructed on the basis (K, v, ) has the value F when p has the value F and q the value T . p q ~ ( p v q) V P T T F T T T F F T T F T F F F F F T T F Hence there exists a formula writable i n our system which does not have the value T f o r a l l assignment of the value T and F to the individual variables involved. Therefore t h i s formula i s not provable and thus the system i s consistent. Note that i f we had not i n s i s t e d that the symbols of our calculus have no meaning and had worked i n the normal interpreta-t i o n of the system; i . e . , as given, namely, the calculus of pro-positions, then our proof could have been shortened somewhat. For i f a formula A i n the system was true then i t s contradictory —A would be f a l s e and thus not provable since every provable formula had the t r u t h value truth. In the completely abstract system, however, ~-A was merely the r e s u l t of an undefined unary operation on A and not necessarily not-A . Although not r e a l l y another method of proving consistency, s t i l l one more device i s worthy of mention here. It i s often possible to reduce the question of the consistency of one system _S to that of another R . This i s achieved i f i t i s possible to define the basic concepts of S i n terms of the concepts of R i n such a manner that the axioms of S become l o g i c a l con-sequences of the axioms of R . No attention has to be paid, for t h i s purpose, to the i n t u i t i v e meaning of the basic concepts i n S and i n R ; the assignment of the names given t o the basic concept of S \ as certa i n concepts derived from R , i s purely a r b i t r a r y . As an example of t h i s method l e t us return to our axiom system f o r the r e l a t i o n of s e r i a l order. Let M be a set of elements for which the binary r e l a t i o n g is defined. This time l e t us use the informal statement that the universal quantifier (x) revers only to the elements of M , rather than use the pre-dicate f for "belongs to M" . Our postulates 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 the interpretation that M represents the set of elementary propositions (p, q, r , ... ) , that g(p, q) stands for the r e l a t i o n ~ ( q •* p) . Now (p) means "for any truth value of p" or "for any .proposition p" and p = q means that the propositions p and q have the same truth value. Note that our d e f i n i t i o n of g(p, q) may be represented by the truth table g(p, q) F f / F F T I T F F ' We now show that our axioms (a) to (d) are s a t i s f i e d by t h i s i n t e r p r e t a t i o n : a) (p) ~g(p> P) F T T T p q (p f q) V g(p, q) v g(q, p) T 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) v-~g(p, q) v ~ g ( q , p) T T T T T T T F F T T F F T F T F T F F T T T - T P q r (p=q) v (q=r ) v (p=r) g(p,q) v--g(q,r) v g(p,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 tautologies of the propositional calculus; and consequently w i l l ' now be provable formulas of the propositional calculus. (This follows from the completeness of the propositional calculus, which w i l l be proved i n Chapter VI. ) Now, since the r u l e s for d e r i v i n g new statements i n the system of s e r i a l order are drawn from tho-se of the l o g i c a l c a l c u l i , and thus w i l l be the usual rules of substitution and inference, we see that a l l the theorems of our interpreted system w i l l form a subset of the theorems of the propositional calculus. But t h i s system has been shown to be consistent by our previously d i s -cussed formal method; and so we have established the formal con-sistency of the postulates for s e r i a l order. CHAPTER V Independence When a tentative l i s t of postulates has been proposed for some branch of mathematics and has been shown to be a consis-tent set, i t i s perfectly conceivable that c e r t a i n postulates of the set are l o g i c a l l y deducible from others of the set. Such postulates are superfluous or redundant. There i s no inherent l o g i c a l f a l l a c y i n using a redundant consistent set of postulates, but for at least two reasons i t i s often d e s i r -able that the postulates be free from redundancies; i.e . , be independent. F i r s t , an independent set of postulates renders, the structure of the subject a e s t h e t i c a l l y more pleasing. For no statement i s included among the postulates which might be derived as a theorem. Second, i f the redundant postulates are removed, then when interpreting the system i t i s not necessary to make as many judgments as to whether the postulates are true or fa l s e for the given subject matter. Hence a consistency proof would depend le s s upon interpretive judgments and thus be les s l i a b l e to error. It i s not always desirable, however, i n actual practice to have an independent set of postulates, since the re-duction of the number of postulates can often increase the com-p l e x i t y of the derivation of theorems to the point where great ingenuity i s required to e s t a b l i s h even the simplest r e s u l t s . For example the system of postulates: (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 for the sentential calculus of the " P r i n c i p i a Mathematica" con-tains a redundancy i n postulate ( 4 ) , since P . Bernays (3) has shown that i t can be deduced from the other four. Discarding postulates (4) i n t h i s case does not cause any inconvenience since i t may be derived i n a few l i n e s as a theorem. Although the postulates ( 1 ) , ( 2 ) , ( 3 ) , (5) are now independent, the primitive ideas of d i s j u n c t i o n and negation underlying them are not inde-pendent and may i n turn be defined i n terms of the single p r i -mitive idea of incompatibility p/q (4) (read, "either p i s f a l s e or q i s f a l s e " ) as follows: ~P"-=-P/P -2$. / p v q .=. ~p/~q By use of t h i s primitive idea, the sing l e postulate [p/ ( q/r )] /{[V (u/u)] / f(v/q)/ ((p/v)/ (p/v))]} w i l l s uffice as the basis for the sentential calculus. Now, however, great d i f f i c u l t y Is experienced i n drawing out the con-sequences of t h i s postulate. It i s of inter e s t to note that Hilbert and Bernays i n th e i r "Grundlagen der Mathematik'? do not attempt to use an independent set of postulates i n building up the l o g i c a l c a l c u l i but rather give long l i s t s of "Ausgangsformeln". (cf. p. 66, Vol. I) The method used to prove the independence of a set of postulates is as follows: suppose the postulates are ( 1 ) , ( 2 ) , ... , (n) . If we can find a concrete interpretation of the undefined terms such that ( 2 ) , ( 3 ) , ... , (n) are satisfied, but (1) is not satisfied, then (1) i s held to be independent of the others. For i f (1) were a logical consequence of some or a l l of the others i t would have to be true in any interpre-tation for which the others were a l l true. Thus in order to establish the independence of the entire set i t i s sufficient to exhibit n suitable concrete interpretations, using each example to establish the independence of one corresponding pos-tulate . That this method i s useful, follows from the fact that i t is often easier to see that under certain circumstances certain statements are true or false, th"a» it is to see that one formal statement does or does not imply another. Notice that this method does not furnish a necessary condition for the independence of a postulate set, for i f an independent interpretation exists then the postulates are independent. If no interpretations can be found, however, it is not a proof of dependence. In our postulate set for serial order we may show the in-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, "If anything is a'natural number then i t is greater than i t s e l f " , which i s , of course, false; whereas, (b) becomes "If x and y are distinct natural numbers, then either x < y or y < x" , (c) becomes " I f x and y are d i s t i n c t natural numbers, then not both x < y and y < x" , (d) becomes " I f x, y, z are any three d i s t i n c t natural num-bers and x < y and y < z , then x < z", which are a l l judged to be true propositions. T h u s , (a) i s independent of (b), (c), and (d) . S i m i l a r i l y we can show the independence of (b), (c), and (d) . We should note also that the independence of the postulates i n t h e i r abstract form does not guarantee the i n -dependence of the propositions a r i s i n g when an interpretation i s assigned to the primitive elements. For i n general these p a r t i c u l a r values of the primitive propositions w i l l be more determinate than the abstract postulates. Thus there may be implications holding which were not present i n the abstract form. We might consider now, i n order to make thi s idea clearer, the simple example afforded by a system consisting of two pos-tulates O x ) . f(x) and ( "3x, y).g(x, y ) , where f and g are two undefined predicates whose arguments range over some undefined set. of elements. These postulates are independent, for under the interpretations f ( x ) . = . "x i s a centaur", g(x, y ) . = . "x i s the father of y" we see that O x ) . f ( x ) i s f a l s e , whereas ( 3 x , y)g(x, y) i s true; by using the interpretations f ( x ) . = . "x i s a man", g(x, y). = . "x is the father and sono of y" we see that ( 3 x ) . f ( x ) becomes a true proposition, whereas (3x, y).g(x, y) becomes f a l s e . Thus neither of the two formal postulates impliesjthg(other. If we now use the interpretations f (x). = . "x i s a man", g(x, y ) . = . "x is the father of y" , then, although the two abstract 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 not. Consider now an abstract postulate system; i t has as i t s basis a system of undefined elements, and undefined operations. We then have a set of formulas (postulates), involving the un-defined operations and r e l a t i o n s which place r e s t r i c t i o n s on the elements. So that i n any i n t e r p r e t a t i o n of the undefined notions the postulates become propositions either true or f a l s e concerning the subject matter of t h i s interpretation. Now suppose we have an abstract system with, say, three postulates. I f we conceive of a l l possible systems which stand as interpretations of t h i s abstract system, we s h a l l have diff e r e n t v a r i e t i e s defined by the a b i l i t i e s of each system to s a t i s f y , or f a i l to s a t i s f y , each of the three postulates. For example, a system may s a t i s f y a l l of the postulates CD , (2) , (3) , or i t may s a t i s f y (T) and (2) and f a i l on (3) , i . e . , i t s a t i s f i e s the system ( T ) , QT) , ^(J) (the contradictory of postulate ( 3 ) ) . Recall that the existence of such an i n -te r p r e t a t i o n as t h i s would insure the independence of postulate Q) from (J) and (J). Before proceeding further l e t us make use of a type of Venn diagram to i l l u s t r a t e these 2 3 differentrs/stems. ^ Here the c i r c l e marked 1 represents the class of systems which s a t i s f y postulate (T) , S i m i l a r i l y with 2 and 3 . Now the intersection of the three c i r c l e s represents the systems s a t i s -fying a l l three postulates. The shaded areas represent the systems whose existence guarantees the independence of the pos-tulates (T) , (2) and (3) i e.g., the f a c t that the c l a s s re-presnted by the cross-hatched area i s not n u l l would t e l l us that interpretations exist for which postulates (T) and (2) become true propositions and postulate 3^} becomes a f a l s e proposition. Thus we may assert as true® j C D ?~(3) ; i . e . , © . © . ~Q) (where (T) stands now f o r the proposition a r i s i n g from postulate ( l ) ) . As we have discussed before this shows the independence of postulate C]D from (T) and (2) i n the abstract set. Now. the new feature which i s introduced by these considerations, arises when we consider the significance of some of the other areas. Suppose now interpretations existed so that the c l a s s marked was not n u l l . This would show that i t i s possible that ~" (l).~(2). (3) ,but t h i s compound proposition is equivalent to ~ ( ~ ® • © © ) or~(r© . CD.— CD) which shows us that postulate (z) is independent of (^) and the contradictory of <2) , also that CT) i s independent of (3) and the contradictory of (2) . Or again, suppose the area marked A was not empty, then there would exist interpretations such that ~G) . - Q ) . ~ ( D which i s equivalent to the following three implications: -(-CD ® ) — (~© .~®.-* CD) ~( -CD .-CD.- CD ) 42 Thus, i f none of the 2 3 d i f f e r e n t areas were empty, there would exist no implications whatsoever among the three postulates. Or to put i t d i f f e r e n t l y , none of the postulates w i l l follow either from the remainder or t h e i r contradictories or any com-bination thereof. If t h i s s i t u a t i o n is r e a l i z e d then the pos-tulates are said to be completely independent ( 5 ) . Note that even i f the postulates possess ordinary independence there is a very r e a l sense i n which they are not "completely" independent i f one followed from the contradictory of another. As might be surmised complete independence i s a very strong condition and i s not possessed by many sets of postulates. It has been shown ( 6 ) that the postulates for Abelian groups and f i e l d s are com-pl e t e l y independent. We s h a l l now show that the postulates we have been using for the r e l a t i o n of s e r i a l order are also com-pl e t e l y independent. We have as before the four postulates: a) (x). *~g(x, x) b) '.(x, y).(x ^y) g(x, y) v g(y, x) c) (x, y).(x ^ y) -> ~ g ( x , y) v ~ g ( y , x). d) (x, y, z).d (x , y, z).g(x, y).g(y, z) -> g (x , z) where the universal q u a n t i f i e r s range over a set K which ad-mits the binary r e l a t i o n g . Now l e t us consider an i n t e r -pretation of the abstract system (K, g),obtained by l i s t i n g the elements of K and defining the r e l a t i o n g extensively by indicating for each pair of elements of K whether g hold or not. The elements of K w i l l be symbolized by 0 , 1 , 2 and the r e l a t i o n g d efined by •43 0 1 2 f ° F T T x<( 1 "F "F T 1 2 F F F This interpretation of (K, g) satisfies the postulates (a) to (d); i.e., i t causes each of the abstract formulas (a) to (d) to become a true proposition. That i s , ~g(x, x) (x f y) -> g(x, y) v g(y, x), (x £'y) ->~g(x, y) S • v ~ g ( y , x), etc. , become tautologies in i K . e.g. v a) (x) ~g(x, x) ' i 0 T - 1 T 3r • 2 T 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 X y (x = y) V' ~ g ( x , y) v~g(y, x) 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 45 X y z (x = y)v(y » z)v(x = z)v ~g(x, y ) v ~ g ( y , z) y g(x, 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 Hence the system K (0 , 1, 2) with g(x, y) so defined satis-fies a l l the postulates (a) to (d) . We w i l l indicate the character of this interpretation of our postulates by writing ( + , +, +, +, ), which indicates that a l l four postulates become true propositions. Now to effect a proof that the serial order postulates are completely independent we exhibit 2 ^ - 1 interpretations of (K, g) such that each of the following characters i s realized. (-> + , + , ( + , - , + , + )> ( + , + , + ) , 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: g(x, y) ^ 0 1 2 0 T T T l F F T 2 F F F (a) Since g ( 0 , 0) holds, we have that (3x).g(x, x), i.e. ~ ( x ) . ~'g(x, x) and hence (a) i s not satisfied. (b) Holds, since g is true for every pa ir of "different" elements, i.e. g(0, 1 ) , g ( l , 2 ) , g (0 , 2) a l l hold. (c) Holds, since g ( 0 , 1 ) , g ( l , 2 ) , g (6 , 2) holds, but not g(l, 0 ) , g(2, 1 ) , g (2 , 0 4? (d) The only instance s a t i s f y i n g the conditions of (d) is g(0, l).g£L, 2) and we see that g(0, 2) holds, thus (d) i s s a t i s f i e d . g(x, y) 0 1 2 0 F F T l F F F 2 F F F It i s easy to checJk that postulates (a), (c), (d) are s a t i s -f i e d , whereas (b) f a i l s . Note that postulate (d) holds because the conditions of i t s implication are not f u l f i l l e d ; i . e . , for no three elements do g(x, y) and g(y, z) both hold. In the following examples we w i l l give only the d e f i n i t i o n of the r e l a t i o n g(x, y) together with the character of the system i t generates. ( + , + +) , + , - ) g(x, y) 0 1 2 g(x, y) 0 1 2 0 0 -¥ l l 2 2 (The asterisk i n d i c a t e s when g(x, y) holds.) (+, + -) + ) g(x, y) 0 1 2 g(x, y) 0 1 2 0 0 1 l 2 7 ^ 2 (-, - > + , (-, + + ) g(x, y) 0 1 2 g(x, y) 0 l 2 0 0 >£-l 1 *c 2 2 (-, + -) ( + , - -) g(x, y) . 0 1 2 g U , y) 0 l 2 0 1 0 1 • \ l 2 2 ( + , - - ) (-, * « "* > -) g(x, y) 0 1 2 g(x, y) 0 l 2 0 0 1 1 2 2 (-, " -) (-, - + ) g(x, y) 0 1 2 g(x, y) 0 l 2 0 0 1 l 2 2 (-, -) g(x, y) 0 1 2 0 1 2 CHAPTER VI Completeness: Another c h a r a c t e r i s t i c which a consistent set of postulates may or may not possess is that of completeness or categorical-ness. B r i e f l y , a set of postulates i s categorical i f i t forms foundations for e s s e n t i a l l y only one branch of mathematics, and i s noncategorical i f i t can serve as a foundation for two or more e s s e n t i a l l y d i f f e r e n t branches of mathematics. To be more precise, l e t us suppose that we have a given set of ab-stract postulates. The set w i l l be categorical i f any two concrete interpretations of the postulates are isomorphic; i . e . , i f a complete one-to-one correspondence can be set up between the elements and r e l a t i o n s of any two interpretations. Thus i n t h i s case any formal property which was true of one system must have i t s analogue i n the other system. In other words the postulates s u f f i c e to determine the formal nature of any concrete systems which s a t i s f y them. I f the undefined terms are interpreted i n various ways so as to obtain concrete systems s a t i s f y i n g a l l the postulates, the abstract science i s replaced by a number of concrete systems a l l of which are formally equi-valent to each other, and each of which i s representative of the underlying science. Further c l a r i f i c a t i o n of t h i s concept requires the develop-ment of the idea of isomorphism between two mathematical sys-tems. Isomorphism may be approached as a generalization of the .50. concept of equivalence of sets. Two sets are called equivalent i f their elements may be placed in a one-to-one correspondence; i.e., i f the two sets have the same number of elements. Thus equivalence, at least for abstract sets, is a mathematical counterpart of the intuitive idea of "resemblance". The question to be discussed now is 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 is a dis-course, not as a rule on one set, but rather on a system consis-ting of several sets, relations, functions, operations, etc. We desire then to seek an extension of the mathematical concept of equivalence, or the intuitive 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 in group theory. Let G-^ be a set of three distinct elements p, q, r, and let G 2 be another set of three distinct elements 1 , 2 , 3 , (not the positive integers 1 , 2 , 3 ) . Define the group operations 0j, 0 2 by the following tables: ° 1 P q r 1 2 3 p P q r 1 1 2 3 q. q r P 2 2 3 1 r r P q 3 3 1 2 Thus 0]_ i s on G]_ x G^  to G]_ and 02 i s on G 2 x G 2 to G2. Moreover, it w i l l be seen that these groups bear to each other a close resemblance, even though the sets G;-^, Gp may be different, 'First i t i s noted that Gj and G 2 are equivalent sets, for the function cp represented by <P P q 1 2 3 is evidently a one-to-one correspondence between G-j_ and G2. But here the system (G^, 0^) has more resemblance to (G 2, 0 2) than just the equivalence of the sets involved. If one defines an operation p 2 by the table: P2 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 0j_ by replacing every entry by i t s cp-correspondent, one sees that p 2 is on G 2 x G 2 to G 2 and also that P 2 = 0 2. It is usual in mathe-matics to say that therefore the systems (G-^ , O^ ) and (G2, 0 2) are ; "abstractly ; identical" . Mathematical formulation of the connection just described between two arbitrary groups may be given thus: let (G-^ , 0-^ ) , (Gg, 0 2) be two groups. We shall say that these groups are iso-morphic i f there exists a one-to-one correspondence cp between the sets G-^  and G 2 such that, (6.1) for every a, b e G, , cp(a)CL 9(b) = <p(aO.,b) 5 2 1 It i s convenient to abbreviate (6.1) by saying that cp carr i e s Oi into O2 . Hence isomorphism, between groups, means the existence of a one-to-6ne correpsondence between G]_ and G 2 which carries Oi into O2 . An important observation i s that the c r i t e r i o n for ismorphism i s meaningful even i f the systems (G]_, O J L ) , (G 2, 0 2 ) are not necessarily 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 d e f i n i t i o n : (6 .2) Let -fehe systems (Gj, 0^) , (G 2, 0 2 ) be given, G]_, G 2 being sets, 0]_ a binary operation on G^  x G^ to G]_ and 0 2 a binary operation on G 2 x G 2 to G 2. Then (G^, 0]_) is isomorphic to (G 2, 0 2 ) [we write (G]_, 0]_)^=(G 2, 0 2 ) ] | i f there exists a one-to-one correspondence cp between G-j_ and G 2 such that (6.1) holds. Such a correspondence i s c a l l e d an isomor-phism between (G]_, 0]_) and (G 2, 0 2 ) . It is e a s i l y shown that isomorphism as so defined i s an equivalence r e l a t i o n ; i . e . , i t has the following three properties: 1) ( G - L , 0 1 ) s ^ ( G - t , Oj.) 2) (G x, 0 t ) ^ ( G 2 , 0 2 ) - ^ - ( G 2 , 0 2 ) ^ ( G 1 } 0 X ) 3 ) (G x, 0 1 ) ^ ( G 2 , 0 2 ) and (G 2, 0 2 ) ^ ( G 3 , O3 ).-*-( Gj^, 0]_) « ( G 3 , O3) Now that we have defined isomorphism f o r systems (G]_, 0]_) , (G 2, 0 2 ) i t would be desirable to have a similar notion of i s o -morphism for any mathematical systems that are to be dealt with. It i s clear that a mathematical system may involve much more than a given set and operation. For example, the basic set for the positive integers (using Peano's axioms) requires a set, a special (element, " 0 " , and a r e l a t i o n "the successor of" . Also there may be many basic sets, rather than just one. The problem of including " a l l possible" mathematical systems i n a general d e f i n i t i o n of isomorphism is. one which does not seem possible at present to deal with. Perhaps when the growing movement towards working i n meta-mathematical systems has developed more f u l l y , t h i s w i l l be achieved. However, at present i t seems that the only course is to define separately the concept of isomor-phism for each d i f f e r e n t type of .system. The motivation, of course, i s always the same for each d e f i n i t i o n ; namely, the necessity that the sets be equivalent and that the tables for the r e l a t i o n s and operations involved be related, as they are i n the example given f o r groups. 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 r e l a t i o n . As an example, consider the d e f i n i t i o n : ( 6 . 3 ) I f K-j_ and K 2 are sets and and R 2 are relations on Kp x and K 2 x K 2 , then (K-^ , R^) i s isomorphic to (K 2, R 2) i f there e x i s t s a one-to-one correspondence cp between K 2 and K 2 such that i f a, b e K-j_ then a R-j_b i f and only i f cp(a) R 2 cp (b) ; ( i . e . , cp carries R-j_ into R 2) . On the basis of this l a s t d e f i n i t i o n i t i s not d i f f i c u l t to show that our postulates for s e r i a l order give r i s e to a non-categorical system. To show t h i s i t is only necessary to exhibit two interpretations s a t i s f y i n g the postulates, one of which i n -volves a f i n i t e number of elements i n i t s basic set and the other involving an i n f i n i t e set of elements. It would be impos-sib l e then to establish the one-to-one correspondence between the basic sets as i s require_d i n the above d e f i n i t i o n of categorica ness. Two such interpretations are the following: 1) f(x). = . "x i s one of the numbers 1, 2, 3, ••• ,9" ' g(x, y). = . »x < y" 1 2) f(x). = . "x i s one of the numbers 1, 2, 3, ... , g(x, y). = . "x < y" . It is easily checked that both interpretations l ) and 2) satisfy the postulates (a) and (d) . It would be natural now to ask whether for systems (% gi) , (% S2) satisfying (a) and (d) i t is true that K 1 ^ K 2 implies (K l f g l ) (K2, g 2) It w i l l be seen that the answer is affirmative. That i s , i f we add the condition that the basic sets, K , underlying the systems for serial order must possess always just n elements then the systems w i l l be categorical. In order to show this property let us f i r s t make the defin-tion: (6.4) An element a Q of K w i l l be called a "first"element i f (x). (x / a 0) -* g(a 0, x) Lemma: For any f i n i t e set K admitting the relation g and satisfying the axioms (a) to (d) there exists a unique f i r s t element a 0 . Proof: Let y Q be any element of K . fhen, either CD ~ ( 3 x ) . ( x fi y Q).g(x, y Q) , or © ( 3 x ) . ( x / y 0).g(x, y Q) Suppose (l) i s true, then _55.. - M 3 x ) . ( x £ y0 ).g(x, yQ.) = ( x ) . ~ { ( x ^  y 0).g(x, y Q ) ^ (x).(x ^ yQ) -> g(x, y Q) (a) But from axiom c) (x).(x £ y Q ) -*--g(x, y Q ) v g(y Q, x) «(x),(x ^ y 0 ) V Grg(x, y 0) -> g(y 0,x)] ((3) Using the theorem (x).A(x).(x)B(x) = (x).A(x).B(x) we adjoin (a) and (@) to get (x).[(x ^ y 0) •> ~ g ( x , y 0 H .Ox ^ y0) -* - ~ g U , y 0) •* g(yo> x ) s ( x ) . ( x ^ y 0) -G~g(x, y 0 ) - g(y 0» x0« C^ g(x, y 0 Q From which we obtain by inference (x). (x £ y 0) -> g(y 0,x) and thus y 0 i s our desired f i r s t element. Otherwise we have case C2) ( I x ) . (x ^  y 0) .g(x, y 0 ) Let y^ be such an "x" . Then we have the same two cases again: either CD , ^ ( 3 x ) . ( x / y]_).g( x, y^ ) or (D ( 3 x ) . ( x / yi).g(x, y^ ) i f case ( l ) holds we are f i n i s h e d ( i . e . , have exhibited a f i r s t element). Otherwise case CD holds. Thus i n a f i n i t e number (less than n ) of such steps we must f i n a l l y arrive at case CD , for otherwise i f case CD always held we whould be asserting the existence of an i n f i n i t e number of elements. We have shown the existence now of an element, say a Q , f o r which (x). (x ^  a Q) •* g ( a Q , x) (r) Suppose that a' i s another such element; i . e . , 56 (x). (x -f a Q) •* g ( a Q , x) Thus i f a 0 ^ a Q we may assert g ( a 0 , a 0 ) , but s i m i l a r i l y from '(r) we obtain g ( a 0 , a Q) . Combining these two assertsion 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) Recall axiom c) (x, y).(x^y)->-.~»g(x, y) v ~ g(y, x) This contradiction proves that such an a 0 cannot e x i s t ; i . e . , a Q i s unique, and the lemma i s proved. Now suppose that we exclude a Q from K . We then have a set with n - 1 elements for which the axiom (a) and (d) s t i l l hold ( r e c a l l that they were a l l universal statements). This new set w i l l also have a f i r s t element, say a^, such that (x). (x £ aj) -* g ( a 1 } x) where (x) now ranges over K —• £a 0^ . Continuing i n this fashion we may order the elements of . K as follows: ao» a l > a2> * * * » a n such that g ( a Q, a-jj, g(a-j_, a 2 ) , ... , g ( a n _ 1 } a n) a l l hold. Suppose now that K i s any other set of n elements s a t i s -f y i n g postulates (a) to (d) . We may order i t s elements the same as above; i . e . , i n the sequence bo> b l > b2> ••• » b n where g(b Q, b±), g(b 1, b 2 ) , ... , g ( b n _ i , b n) hold. Our required isomorphism is given by the function cp de-fined by f b l b 2 0 • • b n a l a 2 • • « • • t • • a n . . . For g(a i, aj) implies g I j f a ^ , cp(aj)J and g Ijpia.^), 9 (a j )] implies g ( a i } a j ) and hence definition (6.3) is satisfied. We have shown that, although the systems (E, g) satis-fying postulates (a) to (d) are not categorical, the addition of the axiom, (e) the set K contains precisiy n elements, causes the set to become categorical. Although the above definition of categoricalness is used chiefly by workers i n mathematics, one finds the corresponding concept of completeness in logical works. One of the usual de-finitions is essentially that a l l universally valid formulas of the system must be formally provable from the postulates in a complete system. B y a universally valid formula we mean one that is true by context in any interpretation 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. Otherwise there would exist an interpretation which contained a formula which was true for 5S. " that particular subject matter, but yet was not formally prov-able from the abstract postulates. But since t h i s formula would be true in virtue of the special features of that particular in-terpretation, i t would not hold for a l l interpretations and thus not a l l interpretations would be isomorphic, this, however, con-tradicts the assumption that the set was categorical. 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 serial order incomplete in this sense i t is only necessary to exhibit a formula which is true in some interpretation but does not follow formally from the axioms. Such a formual i s ( 3x).f (x) which is true for any interpreta-tion which satisfies the postulates (a) to (d) non-vacuously, (i.e., the basic set of elements is not null), but which obviously cannot follow from the axioms since they are a l l universal state-ments and have no existential import. Let us show that the axiom system for the prepositional' calculus is complete in this sense. We shall alter slightly the definition of completeness in order to effect this proof. First note that for any given calculus there are, in general, many different possibilities of a true interpretation. The prac-t i c a l situation, however, i s such that for almost every calculus which actually is interpreted and applied, there is a certain interpretation or a certain kind of interpretation used in the great majority of cases of i t s practical application. This we might c a l l the normal interpretation of the calculus., 59 , The' normal interpretation of the axiom system for the sen-tential calculus is of course the usual logical interpretation. We shall c a l l this calculus complete, then, i f every formula true by context in this interpretation is formally provable in the abstract axiom system. The f i r s t step in proving completeness, in this sense, i s to lay down (semantical) rules so that we may clarify 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 asser-tions, or declarative sentences, we wi l l turn to i t for our intuitive rules. By a declarative sentence, or simply sentence, we mean a linguistic expression concerning which i t is meaningful to say that i t s content is true or false. Example, an expression of the form "A is P", where A i s the name for some thing and P stands for some property. Now from our empirical observation of language we find that sentences can be combined in a definite manner to form new sen-tences, and we lay down the following rules of formations An expression of our system i s called a sentence (or propo-sition) i f i t has one of the following forms: F 1 "A i s P" (where A i s an individual and P is a property applicable to A ) "not p" 5where p is a proposition. F 4 "p and q",where p and q are propositions. Hp or q" , where p and q are propositions, " i f p, then q",, where p and q are propositions, Tt p i f and only i f q" > where p and q are propositions. 60 We now lay down the following truth conditions and introduce a more compact notation for the above sentences F-[_ - Fg. T]_ : "A is P" is true i f f A has the property P . T 2 : " —p" (read not p) is true i f f p i s false. : p.q (read p and q) i s true i f f p is true and q is true. T 4 '• P v q. (read p or q) i s true if-f p i s tujre or q i s true . T.5 : p -> q (read i f p then q) is true i f f p is false or q i s true. T5 : p = q (p i f and only q) i s true i f f p and q are both true or both false. We see that according to the definition of our fundamental logical connections, the truth or falsehood of a sentential com-bination depends solely upon the truth or falsehood of the sen-tences entering into the combination, and not up8n their content. This i s of course after we have determined the propositions to be true or false by use of T]_ . It should be noted now, that some of the fundamental connec-tives may have the same meaning; i.e., express the same truth 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 called equivalent, and w i l l have the pro-perty 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 shall now show that any combination of sentences can be brought Into a certain Normal Form by means of equivalence transformations. This conjunctive normal form consists of a conjunction, of disjunctions in which each member of a disjunction is 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 distributive laws. a2) For ~ ( ~ p ) we may substitute p . a3 ) We may write ~ - p v — q for M p.q) and-^p.^q for -^(p v q). a4) We may subtitute ^p v q for p -*• q and ~p v q. ^ q v p for p == q . The trmsqfrmation is effected thus: f i r s t , by employing Rule a4) we can substitute for any expression an equivalent one that no longer involves the symbols and " . The result-ing expression i s then entirely in terms of "v", . Now by successive applications of Rule a3), the negation signs can be brought farther and farther inside until 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 M p v q\. ~ q ) . ^ ( r .q) then by another application of a3 ) *Mp v q) v ~( ~-q). r v ^ q and f i n a l l y (^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, in our example (~p v q). (~q v q). ( ~ r v~q) and this is the desired conjunctive normal form. It is 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 equi-valent one in normal form,the solution of this problem is only a matter of determining when an expression in normal form represents a logically true . (L-treu) combination of sentences. This deter-mination is easily arrived at by means of the following rules which are direct consequences of T-j_ - T^  : bl) p v—p is L-true. b2) i f p is true, p v q is L-true for all q . b3) i f p is true and q i s true, then p.q is 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 in accordance with Rules bl), b 2 ) , b3), al) i t may be seen that a l l expression in normal form (i.e., in the form (p]_ v p 2 v ... ).(p2" v v , . . ) . ... ) are true,which have the characteristic that in each disjunction there occurs at least one of the elementary sentences together with its negation. Moreover, these are the only expressions which are logically true. For if every elementary sentence—in some conjunct — which is itself a 'disjunction of a normal form occurs as a fact o r either negated or only unnegated, then t h i s disjunction can be made into a f a l s e sentence by replacing each unnegated symbol by a f a l s e sentence and each negated symbol by a true sentence. Then a conjunct of the normal form i s a fa l s e sentence and consequently the entire expression yi e l d s a f a l s e sentence. Thus i t is not the case that the normal form yields a true sentence independently of the truth values of i t s elementary component sentences, and thus i s not L-true. As we have discussed before the formal calculus may be b u i l t up on the undefined set of elements p, q, r , ... and the un-defined operations "v" and " ~ » , by the use of the axioms 1 ) 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 rules of substitution and inference. In t h i s system i t may be shown quite e a s i l y , although we s h a l l not take the space here, that Rule al) - a4) and bl) - b3) may be obtained from the axioms as derived rules. Now, however, we must read the rules bl) - b3) as follows: bl) p v ^  p i s a theorem (i.e. , provable) b2) i f p i s a theorem, p v q is a theorem for a l l q , etc. For the notion of trutii i s replaced by that of p r o v a b i l i t y i n a formal calculus. Hence, i t follows that a l l the observations 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 logically true sentences, may also be derived from the axioms. Thus a formula from our axiom system is prov-able, i f and only i f each disjunction of i t s conjunctive normal form contains two components of which one is the result of opera-ting on the other by TW f . We see then that the class of logi-cally true sentences coincides exactly with the class of provable formulas, and thus the axiom system is complete. There is s t i l l another definition of completeness which is stronger; i.e., moie limiting, than the previous one. To arrive at this definition, let us consider f i r s t a set of axioms A which are written i n terms of a set B of primitive elements, operations, relations, etc. If we consider a class of a l l formulas which can be written (following specified syntactical rules of formation) in terms of the base B , we find that, in general, these formulas f a l l i n three classes: , those which follow from A ; a 2, those whose contradictor ies -follow from A ; and CX3 , those such that neither they nor their contradictories follow. Here, i t is to be noted that the members of a 2 can no more be considered independent of the set A than the members of a]_ ; i f an interpretation satisfies 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 2 into false ones; so that we may combine et-^  and into one class, a2_2> a n d s a y t h a t A determines the truth value of every member of this class. If we add to A a member of the class a 12 we shall get either a contradiction or redundancy, whereas i f - we add a member of the new set w i l l be self consistent — although i t may not be an independent"set, owing to the fact that the new ,65 condition either alone or in conjunction with some of the original members of A , may imply other members of A . Now, this new set w i l l have a wider range of implications; a 12 w i l l be in-creased, and 0:3 correspondingly diminished. So, we may continue to add formulas from a ^  to A until 0:3 vanishes altogether. • When this occurs the set obtained i s said to be complete. Some-times this new set of axioms is called the completion of A . Thus a set is complete 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 definition i s often worded as follows: a system is 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 definition of complete-ness, while certainly equivalent, give rise to different tech-niques in constructing proofs of completeness. Using the f i r s t emphasis, let us show that the postulates (#) to (d) for serial order are not complete. Here we must show that there exists a pair of mutually contradictory formulas which can be written in terms of the basis of the set (a) to (d), and such that neither i s provable from the set. Two such formulas are (3x).f(x) and (J.f(x) [> ~ > ( B x ) . f ( x ) ] . The proofs that these formulas do not follow from the set i s , of course, like the proofs of independence given before: we find an interpretation satisfying (a) to (d) and f a i l i n g to satis-fy the formula that i s to be shown not to follow. Let f (x) mean "x is a satellite of the moon" and g(x, y) mean "x revolves about y" . Then (a) to (d) are satisfied vacuously, while (3x).f(x) f a i l s . Let f(x) mean "x is a satel l i t e of the earth" 6 6 (and g(x, y) mean "x is not identical with y" . Then (a) to (d) are satisfied, the last three vacuously, while (3x).f(x) f a i l s . Thus our set of postulates i s not complete since the formula (3x).f(x) , which is written properly in terms of the primitive ideas of our set, can be neither proved nor dis-proved (the contradictory proved) in the system. Turning to the second way of stating this stricter defini-tion 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 illustrated quite simply in the sentential calculus. Suppose, then, that A is an unprovable formula of the sen-tential calculus. Let N be the normal form corresponding to A. Thus of course N is not provable since i t is equivalent to A . Now rec a l l that the t o t a l i t y of provable formulas in the sentential calculus corresponded to the totality of formulas whose normal forms contained, in every conjunct, both an elementary proposition and i t s contradictory. So the non-provability of A implies that there exists a conjunct C which contains no mutually contradic-tory elements; i.e. , C must be of the form PjL V p 2 V ""P-^  v . .. where (for a l l i ) p.^  and — p ^ do not both occur. In C substitute q for each p^ that occurs unnegated and ~ q for each negated pj_ . After this subsitution we obtain C s t.q v q v q v . . . v q . s 3 q Now i f A is added to the system as an axiom, we should have as theorems in this new system, f i r s t the formula N , then C , and f i n a l l y q i t s e l f . But now we could substitute -"q for 67 jq and have the contradiction that q and ^ q are both provable. We mentioned 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-ness was more r e s t r i c t i v e than the previous d e f i n i t i o n . To prove t h i s statement i t i s only necessary to f i n d an axiom system which i s complete according to the f i r s t d e f i n i t i o n but does not f u l f i l the requirements of the second d e f i n i t i o n . Such a system is that o the r e s t r i c t e d predicate calculus. The completeness of t h i s sys-tem i n the broader sense; i . e . , that a l l univ e r s a l l y v a l i d formulas are provable, has been proved by K. Goedel (7) • On the other hand Hilbert (2) has shown that the s t r i c t e r form of completeness i s lacking i n t h i s c a l c u l u s . His method i s quite simple and is e s s e n t i a l l y as follows: f i r s t he gives an arithmetical i n t e r -pretation to the calculus so that every axiom as well 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 value 0 w i l l have a value 1 . He then exhibits a formula which has the value 0 and which he proves i s nonprovable. Now to disprove t h i s formula we must prove i t s contradictory. But i t s contradictory w i l l have the value 1 and thus be non-provable. Thus1 the v a l i d i t y of this formula i s undecidable and the axiom system is not compile. Closely connected with the problem of completeness i s another, more general problem which concerns incomplete, as well as complete theories. It i s the problem of finding, f o r a given deductive theory, a general method which would enable us to decide whether or not any p a r t i c u l a r formula constructed i n the terms of t h i s theory can be proved within t h i s theory. This important and d i f f i -c u l t problem i s known as the Decision Problem. One can e a s i l y v i s u a l i z e the value of a decision procedure i n mathematics; e.g., i t could then be decided whether such formulas as Fermat's " l a s t 6.6-^ theorem" (n) j (n > 2) M3x, y, z) .x31 + yn = z 1 1 ^ (where the quantifiers range over the set of r a t i o n a l integers) were v a l i d or not. The f i r s t deductive system for which a mechanical decision procedure was exhibited was the propositional calculus. The procedure i s , of course, the f a m i l i a r matrix test for tautolo-g i c a l formulas. Immediately a f t e r t h i s calculus, proceeding i n the d i r e c t i o n of more complex structure, one runs into d i f f i c u l -t i e s . The r e s t r i c t e d predicate calculus (general q u a n t i f i c a t i o n theory), despite i t s completeness, d i f f e r s from the simpler l o g i c i n that i t possesses no mechanical t e s t of v a l i d i t y . Here we must, i n general, grope for the deduction which w i l l e stablish the v a l i d i t y of a given formula. Moreover, t h i s i s not simply a lack of ingenuity i n discovering such a procedure, f o r Alonzo Church (£) has proved that no mechanical routine can be generally adsniate for deciding v a l i d i t y i n q u a n t i f i c a t i o n theory. However, the quest for d e c i s i o n methods does not come to a dead end at t h i s point, f o r i t can be shown that i n certain sections of the predicate calculus a successful s o l u t i o n to the decision problem has been reached. In fact the d e c i s i o n problem has been solved for a l l formulas containing only monadic predic-srtevariables. The p o s s i b i l i t y of decision i n t h i s case was f i r s t recognized by L. Loewenheim (9) . Simpler proofs have been given by T. Skolem (10) and H. Behmann (11) . These methods of proof extend beyond the r e s t r i c t e d predicate calculus, since they solve the decision pro-blem i n the case of monadic predicates also for the predicate calculus of the second order (where quantifieatio n extends to 69. p r e d i c a t e v a r i a b l e s ) . The q u e s t i o n now a r i s e s as to the s i t u a t i o n i n mathematics w i t h respect to such concepts as the d e c i s i o n problem and com-pl e t e n e s s . I t can be shown t h a t the g e n e r a l l o g i c of c l a s s e s i s adequate 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 mathematics. Moreover, the higher p r e d i c a t e c a l c u l i s erve as a language i n which t o ex-press the theory of c l a s s e s . Thus i t would seem t h a t i t i s not unreasonable t o l o o k f o r completeness i n c e r t a i n s e c t i o n s of mathematics. For a d i s c u s s i o n of t h i s completeness we may t u r n to a f a r r e a c h i n g r e s u l t obtained by K. Goedel (12) . To b e g i n w i t h , l e t us c o n s i d e r o n l y t h a t branch o f mathema-t i c s c a l l e d elementary number theory. Here the v a r i a b l e s of q u a n t i f i c a t i o n are a l l o f one type; i . e . the u s u a l x, y, z e t c . , which are row construed as r e f e r r i n g e x c l u s i v e l y to t h e n a t u r a l numbers. The n o t a t i o n o f elementary number theory i s merely that o f t h e l o g i c of q u a n t i f i c a t i o n p l u s the a d d i t i o n a l s i g n " = " and t h e n o t a t i o n "x + y" and "x.y" of sum and product. T y p i c a l t r u t h s e x p r e s s i b l e i n t h i s n o t a t i o n are: ( 3 x ) ( y ) { x + y = y | , (x)(y) { (x.y) - (y. x)} An i d e a l treatment of t h i s theory would c o n s i s t i n a mechanical t e s t of t r u t h f o r a l l statements e x p r e s s i b l e i n t h e n o t a t i o n d e s c r i b e d . I t happens, however, t h a t t h i s i d e a l i s unobtainable. In 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 had a s i m i l a r s i t u a t i o n and t h e r e one had to s e t t l e f o r a second b e s t : a technique of d e d u c t i o n , or proof. This technique was complete i n the weaker sense t h a t every v a l i d formula admitted o f a proof. Also the technique was h a l f mechanical, i n t h a t every a l l e g e d p r o o f , once presented, admitted ofLa mechanical t e s t of c o r r e c t n e s s . 70. But the discovery of such proofs is entirely unmechanical. Such would seem to be a reasonable objective also in ele-mentary number theory. What is wanted is a proof procedure just broad enough so that a l l truths expressible in 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 half mechanical in the sense explained above. Proofs would have no claim on conviction i f they could not in principle be checked for conformity to rules. Now the remarkable fact which Goedel has established is that even this objective, for a l l i t s apparent reasonableness, is un-attainable. Elementary number theory, unlike the predicate cal-culus, resists complete systematization. Given any proof procedure P for 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 P . Either Sp is provable, in which case i t is false and so the general proof procedure P is discredited, or else Sp i s true and not provable, in which case the proof procedure P is incomplete. The following summary of Goedels method is 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 be limited to j -A. j ./V j -A. y • 9 • 9f we may think of the notation of elementary number theory as com-posed of just this nine-sign alphabet; . ( ) = + . x ' Now let us assign the numbers 1 , 2 , . . . , 9 arbitrarily to the nine signs of this alphabet. To complex expressions built up of that alphabet let us assign the number which is expressed by the corresponding string of digits; to the statement (x)(x = x); e.g., the number 3$,43^,584 is assigned. 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 is half mechanical, at least, i t i s possible within the notation of elementary number theory to formulate an open sentence, "... x ..." let usyf^which is true of any number x i f and only i f x is the number of a statement which can be proved by P . Next Goedel shows, in effect, how to find a number n and an open sentence " — x __" of elementary number theory f u l f i l i n g these conditions: "_~ x «—." is true of n exclusively; n is the number assigned to " (3x) ^  x .—. ."-'(... x ... ) ~t " . Finally the sought S p is taken as the quantification (3x)y x . ~ ( . . . x ... )\ It w i l l be true, clearly, i f and only i f "... x ..." is false of n , and hence i f and only i f n is not the number of a state-ment provable by P . But the statement numbered n i s Sp i t -self, which, therefore, is true i f and only i f not provable. From this result we obtain a corresponding conclusion re-garding the theory of classes. Elementary number theory is trans-latable into the notation of the theory of classes and therefore the incompletability of elementary number theory entials the in-co-mpletability of the theory of classes. Also since the concepts of the general theory of classes are adequate as a foundation for classical mathematics, any effort toward a complete deductive theory for classical mathematics must necessarily f a i l . It is doomed to failure as soon as i t attempts to encompass even that well-behaved infinity of objects called natural numbers. One can do no better, from that point forward, than add special axioms now and again to strengthen the system for specific purposes. But i f in view of Goedel's result our knowledge about class and number is subject to unexpected limitations, the very oppo-site is 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 sub-ject matter is mathematical theory i t s e l f . Fruitful further research in proof theory i s now going for-ward. M, Pressburger (Warsaw) and T, Skolem (Oslo) have shown that when elementary number theory is further limited to the ex-tent of dropping multiplication and keeping just addition, or vice versa, the resulting theory does admit of a complete proof -procedure and even of a decision procedure, or mechanical tested truth. What is more surprising, Tarski (13) has shown that the ele mentary algebra of real numbers likewise admits of a decision pro-cedure. The notation of this elementary algebra is 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 referring to real numbers generally rather than to natural numbers. Despite the seemingly (greater complexity of i t s subject matter, elementary algebra is completable and mechanically decidable while elementary num-ber theory i s not. References 1) Amer. Math. Monthly, Vo 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 Principia Mathematica. Math. Zeitschr. V o l . 25 , (1926) . . 4) J .G.P . Nicod, A reduction^ i n the number of the primitive propositions of log ic , Proc. Camb. P h i l . Soc. Vol . 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. Vol . 23, p. 313. For an interesting set of postulates possessing complete independence see also, Per Satz von arithemischen Mitt e l  in axiomatischer Begriandung. Math. Ann. 68, and the complete independence of these pos-tulates, Math. Ann. 76 . 7) K. G6del, Die Vollstandigkeit der Axiome des logischen 'Funktionen-Kalkuls. J l h . Math.Physik.Vol . 37, (1930J. 8) A. Church, A note on the Entscheidungsproblem. Journ. of Symbolic Logic, Vol . 1, (1936). 9) L . Lewenheim, Ueber Mflglichkeiten-in Relativkalkul. Math. Ann. Vol. 76, 11915). 10) T. Skolem, Untersuchungen fiber die Axiome des Klassen-Kalkuls. Vid. Skrifter I , ivJath.-nat. Klasse 1919, No. 3. 11) H. Behmann, Beitrage zur Algebra der logik und zum Entscheidungsproblem. Math. Ann. Vol . 89 (1922). 12) G. GBdel, Ueber formal unentscheidbare Sfltze .der Principia Mathematica und verwandter Systeme. Mb., far Math, u. Physik, Vo l . 3& (1931), cf . On undecidable pro-positions of Formal Mathematical systems, mimeographe Princeton (1934). 13) A. Tarski , A Decision Method for Elementary Algebra and Geometry, Santa Monica, 19U>. 

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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0080626/manifest

Comment

Related Items