Alfred Tarski - Logic, Semantics, Metamathematics. Papers From 1923 To 1938 (1956, Clarendon Press) PDF [PDF]

Zitiervorschau

LOGIC, SEMANTICS, METAMATHEMATICS PAPE RS FROM 1923 TO 1938 BY

ALFRED

TARSKI

T B A N SL A T K B BY

J. H. W O G D G E R

OXFORD AT TH E CLAREN D O N PRESS 1956

PRINTED IN GREAT BRITAIN

T R A N SL A T O R ’S PREFACE

T he setting free o f Poland after the First W orld W ar wa s fol­ lowed b y intensive activity in her Universities. In the depart­ ments o f philosophy and mathematics this took the form, in a number o f places, o f new and powerful investigations in the fields o f mathematical logic, the foundations o f mathematics, and the m ethodology o f the sciences. Prominent in this m ove­ ment was the W arsaw school led b y Lukasiewicz, Kotarbinski, and Lesniewski. Under their skilled guidance a younger genera­ tion grew up and among these Alfred Tarski quickly dis­ tinguished himself. Ever since I first enjoyed the hospitality o f Professor Tarski in Warsaw in 1936, it has seemed to me that the importance and scope o f the Polish school o f logicians were insufficiently known and appreciated in the English-speaking world. Then came the Second W orld W ar, bringing ruin once more to Poland, killing men, destroying laboratories, and burning manuscripts and libraries. After this war it occurred to me that I should be performing a public service, as well as acknowledging in some small measure m y debt to m y Polish friends, i f I prepared a collected edition o f some o f Professor Tarski’s publications in English translation. W hen he visited England in 1950 to deliver the Sherman Lectures at University College, London, I men­ tioned m y plan to him and received his approval. This volume contains Tarski’s m ajor contributions to logic, semantics, and metamathematics published before the Second W orld W a r ; their arrangement here corresponds to the chrono­ logical order in which they first appeared in print. W ith the exception o f articles I I and X I (which are too closely connected with, and too often referred to in, the other articles to be omitted), the volume does not include Tarski’s studies in the foundations o f special mathematical disciplines— set theory, group theory, etc. Neither does it contain his papers o f a pronouncedly mathematical character, dealing with special topics from the domain o f set theory, measure theory, abstract

viii

T R A N S L A T O R ’ S PREFACE

algebra, elementary geometry, etc. Also excluded are short notes, abstracts, and preliminary reports whioh are closely related to some o f the articles included in the volume and the contents o f which are more fully presented in these articles. A longer paper from the domain o f logic and m ethodology which has been omitted is cSur la method© deductive 5in Travaiuc du IX e Congrls International de Philosophic (Paris 1937); this paper is a purely expository one, and its ideas have been fully developed in Chapter V I o f Tarski’s book Introduction, to logic (New Y ork, 1941). In a sense the present work is more than a volume o f transla­ tions. Naturally an attempt has been made to remove the misprints and errors whioh occur in the originals. Moreover, the articles have been provided b y the author with cross-references to other articles in the volume and with notes referring to later developments and recent literature. Occasionally some new remarks have been added for the purpose o f clarifying certain passages in the original text. Articles I I and V I contain more serious changes, Tarski having inserted in them several passages which, he hopes, will help to clarify and amplify their contents. W hile the work o f translation was in progress, the passages whioh seemed to me doubtful and difficult wer6 noted down and sent to Professor Tarski in Berkeley, California. In this way it was possible to adjust the text o f the translations in many points, so as to meet the author’s wishes. However, in view o f the time limit and the geographical distance between the resi­ dences o f the author and the translator, it was impracticable to send the whole manuscript to Professor Tarski before it was set in print. Instead he received galley proofs, on which for obvious reasons he could not suggest too extensive changes. It also proved impossible to discuss the suggested changes in detail, and it was left to m y decision which changes were actually to be carried through. Thus Professor Tarski is not responsible for the final text or the technical aspect o f the book. Three articles in this volume are joint publications o f Tarski and other authors: Professor C. Kuratowski (article V II), Dr. A. Lindenbaum (article X H I), and Professor J. Lukasiewicz

T R A N S L A T O R ’ S PREFACE

ix

(article IV ). W e are greatly obliged to Professors Kuratowski and Lukasiewicz for their permission to include the translations o f the jointly published articles in the volume, Dr. Lindenbaum fell a victim to the Gestapo during the war. The papers included in the volume originally appeared in the following periodicals and collective works: Actes du Congres International de Philosophic Scientifique (articles X V and X V I),

Comptes Rendus de la SociiU des Sciences et des Lettres de Varsovie (articles H I and IV ), Ergebnisse tines mathematischen Kolloquiums (articles X I I I and X IV ), Erkenntnis (article X ), Fundamenta Mathematical (articles I, V I, V II, X I, X U , and X V II), Ksiyga Pamiqtkowa Pienvszego Polskiego Zjazdu Hatemaiycznego (article II), Monatshefte fUr Mathematik und Physik (articles V and I X ), Przeglqd Filozoficzny (articles I, X , X V , and X V I), and Travaux de la Sociiii des Sciences et des Lettres de Varsovie (article V III). Acknowledgements should be made to the pu b­ lishers and editors o f these periodicals for their generosity. I am obliged to Mr. S. W . P. Steen for kindly reading the proofs o f article VILl and throughout the work I have received much help from m y son, Michael W oodger. W e are also indebted to several colleagues and students o f Professor Tarski— Dr. C. C. Chang, Professor A. C. Davis, Professor J. Kalicki, Mr. R. Montague, Professor J. Myhill, Professor D. Rynin. and Mr. D . Scott— for their assistance in revising the original text o f the articles and in reading galley proofs. Finally it is a pleasure to acknowledge the courtesy and help which we have received from the staff o f the Clarendon Press at all stages in the production o f the book. J. H. W .

A U T H O R ’S ACKN O W LED G EM EN TS

I t is a rare privilege for an author to see a volume o f his collected papers published during his lifetime, and especially so if the papers be translated into a single language from originals in a number o f other languages. I cannot therefore but be deeply m oved b y the appearance o f this volume and b y the thought o f the m any and great sacrifices which its publication has laid upon m y friend, Professor Joseph H. W oodger. For five long years he has devoted to this work an immense amount o f effort and time, which otherwise could have been used for fruitful research in his chosen field, theoretical biology and its foundations. The task o f a translator is rarely a gratifying one. Circum­ stances have made it especially thankless in the present ca se; let me indicate some o f them. The papers whose translations constitute the volume were originally published over a period o f fifteen years and in several different languages. They vary considerably in subject-matter, style, and notation. Under these conditions, the task o f combining the papers in one book provided with a reasonable degree o f terminological consistency and conceptual uniform ity presents extreme difficulties. In a few cases (in particular, in the case o f the monograph on the concept o f truth, which occupies nearly one-third o f the volume) the translation had to be based not upon the original, which was published in Polish, but upon the French or German version. This made it even harder for the translator to give a fully adequate rendering o f the original intentions and ideas o f the author. In addition, due to the factors o f space and time, the translator was deprived o f the benefit o f extensively discussing with the author even the m ajor difficulties encountered in his work, and so achieving a meeting o f minds before the text was set up in type. T o illustrate this point I may mention that, for various reasons, I have been unable so far to read a considerable part o f the present text, and it seems more than likely that I shall not have read it before receiving a copy o f the published

Zll

AUTHOR’S ACKNOWLEDGEMENTS

book. The realization o f the difficulties involved makes me feel all the more indebted to him whose initiative, devotion, and labour have brought this volume into existence. I t is needless to say that I fully appreciate the assistance and consideration o f all the persons mentioned in the translator’s preface. But I should feel unhappy if at this place I did not make special mention o f the man who helped me more than anyone else in m y part o f the job — m y younger colleague, the late Jan Kalieki. He spent the last two years o f his short life in Berkeley; he generously offered his help on the day o f his arrival and continued it untiringly and patiently, with the greatest devotion and conscientiousness, until his last day. He studied the originals o f the articles, translated for Professor W oodger various passages from the Polish text, prepared refer­ ences to recent literature, discussed with me the remarks which I planned to insert in the translations, assumed most o f the burden o f the extensive correspondence connected with the publication o f the book, and read the first batch o f galley proofs. His tragic and untimely death (in November 1953) was a cause o f considerable delay in the publication o f this volume. A. T.

University of California Berkeley>August 1955

CONTENTS I. II. III.

IV.

V. V I. V II. V III.

IX .

X.

XL X II.

X III.

1

ON T H E P R I M I T I V E T E R M OF L O G IS T IC F O U N D A T I O N S OF T H E G E O M E T R Y OF SO L ID S

24

ON SO M E FUNDAMENTAL M ETA M A TH E M ATIC S

30

CONCEPTS

OF

IN V E ST IG A T IO N S IN T O THE SE N TEN TIA L CALCULUS (by Jan L U K A S I E W I C Z and Alfred T A R S K I ) F U N D A M E N T A L C O N CEP T S OF T H E M E T H O D O ­ L O G Y OF T H E D E D U C T I V E S C IE N C E S

38

60

ON D E F I N A B L E SE TS OF R E A L N U M B E R S

no

L O G I C A L O P E R A T I O N S A N D P R O J E C T I V E SETS (by Casimir K U R A T O W S K I and Alfred T A R S K I )

143

T H E C O N C E P T OF T R U T H I N F O R M A L I Z E D LANGUAGES Introduction § 1. The Concept of True Sentence in Everyday or Colloquial Language § 2. Formalized Languages, especially the Language of the Calculus of Classes § 3. The Concept of True Sentence in the Language of the Calculus of Classes § 4. The Concept of True Sentence in Languages of Finite Order $ 6. The Concept of True Sentence in Languages of Infinite Order § 6. Summary § 7. Poateoript

152 152 154 165 186 209 241 265 268

SOME O B S E R V A T I O N S ON T H E C O N C E P T S OF cu-CO N SIST E N CY A N D ^ -C O M P L E T E N E S S

278

SOM E M E T H O D O L O G I C A L I N V E S T I G A T I O N S ON T H E D E F I N A B I L I T Y OF CONCEPTS

296

O N T H E F O U N D A T I O N S OF B O O L E A N A L G E B R A

320

FO U N D ATIO N S SYSTEMS

342

OF

THE

CALCULUS

OF

ON T H E L I M I T A T I O N S OF T H E M E A N S OF E X P R E S S I O N OF D E D U C T I V E T H E O R I E S (by Adolf L J K D E N B A U M and Alfred T A R S K I )

384

xiv X IV .

XV.

X V I. X V II.

CONTENTS ON E X T E N S I O N S OF I N C O M P L E T E OF T H E S E N T E N T I A L C A L C U L U S THE E STAB LISH M E N T SEM AN TICS

OF

SYSTEMS 393

SCIE NTIFIC 401

O N T H E C O N C E P T OF L O G I C A L C O N S E Q U E N C E

409

SE N T E N T IA L CALCULUS AND TOPOLOGY

421

A B B R E V IA TIO N S

455

B IB L IO G R A P H Y

456

SUBJECT I N D E X

463

I N D E X OF N A M E S OF P E R S O N S

468

I N D E X OF S Y M B O L S

470

I

ON

THE

PR IM ITIVE

TERM

OF

LOGISTICf

I n- this article I propose to establish a theorem belonging to logistic concerning some connexions, not widely known, which exist between the terms o f this discipline. My reasonings are based on certain sentences which are generally accepted among logisticians. But they do not depend on this or that particular theory o f logical types. Among all the theories o f types which could be constructed1 there exist those according to which my arguments in their present form are perfectly legitimate.2 The problem o f which I here offer a solution is the following: is it possible to construct a system of logistic in which the sign of equivalence is the only primitive sign (in addition o f course to the quantifiers8) ? This problem seems to me to be interesting for the following reason. We know that it is possible to construct the system o f logistic by means o f a single primitive term, employing for this purpose either the sign o f implication, if we wish to follow the 1 The possibility of constructing different theories of logical types is also recognised by the inventor of the best known of them. Cf. Whitehead, A . N ., and Bussell, B . (90), vol. 1, p. vii. 1 Such a theory was developed in 1920 by S. Le6niewski in his course on the principles of arithmetic in the University of Warsaw; an exposition of the foundations of a system of logistic based upon this theory of types can be found in Le&niewski (46), (47), and (47 b). * In the sense of Peiroe (see Peirce, C. S. (58 a), p. 197) who gives this name to the symbols ‘ I T (universal quantifier) and ‘2* (particular or existential quantifier) representing abbreviations of the expressions: ‘ for every significa­ tion of the terms . . and ‘ for some signification of the terms . , t B ibliographical N ote . This article constitutes the essential part of the author’s doctoral dissertation submitted to the University of Warsaw in 1923. The paper appeared in print in Polish under the title *0 wyrazie pierwotnym logiBtyki’ in Przeglqd Filozoficzny, vol. 26 (1923), pp. 68-89. A somewhat modified version was published in French in two parts under separate titles: ‘Sur le terme primitif de la Logistique*, Fundamental Mathematicae, vol. 4 (1923), pp. 196-200, and ‘ Sur les truth-functions au sens de MM. Bussell et Whitehead’, ibid., vol. 6 (1924), pp. 69-74. The present English translation is based partly on the Polish and partly on the French original.

2

ON THE P R IM IT IV E TERM OF LOGISTIC

I

example o f Russell,1 or b y making use o f the idea o f Sheffer,2 who adopts as the primitive term the sign o f incompatibility, especially introduced for this purpose. Now, in order really to attain our goal, it is necessary to guard against the entry o f any constant special term into the wording o f the definitions involved, if this special term is at the same time distinct from the primitive term adopted, from terms previously defined, and from the term to be defined .8 The sign o f equivalence, if we em ploy it as our primitive term, presents from this standpoint the advantage that it permits us to observe the above rule quite strictly and at the same time to give to our definitions a form as natural as it is convenient, that is to say the form o f equivalences. The theorem which will be proved in § 1 o f this article,

[p,q]::p .q . == :.[/]:.*> s :[r].p s / ( r ) . ss .[r].q s / ( r ) « constitutes a positive answer to the question raised above. In fact it can serve as a definition o f the symbol o f logical product in terms o f the equivalence sym bol and the universal quantifier; and as soon as we are able to use the symbol o f logical product , the definitions o f other terms o f logistic do not present any difficulty, as appears, e.g. from the following sentences:

[?]:• ~ 0P) ss :p s .[q].q, [ p , q ] : . p o q . = :p ss .p.q, i

s s . (61 d)f pp. 16-18.

1 See Russell, B, * See Sheffer, H . M. (63 a). See also Russell, B. (61 s). 8 In this article we regard definitions as sentences belonging to the system of logistic. I f therefore we were to use some special symbol in formulating definitions we could hardly claim that only one symbol is accepted in our system as a primitive term. It may be mentioned that, in the work of Whitehead and Russell cited above all the definitions bave the form 4a =» b Df. * and thus actually contain a special symbol which occurs neither in axioms nor in theorems; it seems, however, that these authors do not treat definitions as sentences belonging to the system. 4 In this note I adopt the notation of Whitehead and Russell with some slight modifications; in particular, instead of expressions of the form *x9 I write *(x)9; also the use of dots differs in some details from that in Principia Mathematical b Some further developments related to this result are contained in the doctoral dissertation of Henry H it, ‘ An economic foundation for arithmetic*, Harvard University, 1948; see also H it, Henry (31 a).

I

ON TH E P R IM IT IV E TERM OF LOGISTIC

3

It will be seen from the discussion in § 2, that the results obtained can be considerably simplified within a system o f logistic which contains the following sentence among its axioms [ * , 5, / ] : f s , . f y ) . o , ( „ .

or theorems:

However, this sentence cannot be proved or disproved with­ in any o f the systems o f logistic which are known from the literature. This gave rise to a further study o f the sentence in question, and in particular to a. search for other sentences equivalent to it. The results obtained will be presented in §§ 3-6 o f this work. § 1. F u n d a m e n t a l T h e o r e m

I start b y introducing a few definitions, Def. 1-3, which will be used in this and the following sections. Then I give several lemmas, Th. 1- 10, and finally prove Th. 11 which is the main result o f this work. The proofs offered are strictly speaking incomplete; they must be regarded as commentaries indicating the course o f the reasoning. The structure o f these commentaries is in part bor­ rowed from Whitehead and Russell; they do not, I think, require more detailed explanation.

Dee. 1.

[p] :^r(p) = .p ~ p

Dee. 2.

[jp].&s(2>) s p

Dee. 3.

[p] :fl{p) == .p == ~ {p)

For symmetry, one could also introduce the following defini­ tion: D ee.

2'.

[p].ngr(p) s ~ (p ).

However, this definition would be quite useless, since the symbol ‘ ngr would have the same meaning as the negation symbol already occurring in logic. T h . 1.

0 1 .to{p)

T h . 2.

0 ] : [g]

(Def. 1) = tr(q) . o p

4

ON T H E P R IM IT I V E TER M OF LOGISTIC

1 .5 1

Proof.1 [p~\: . H p. 0 : p == .[g].fr(g):

(1)

(1, Th. 1)

Cn T h . 3.

\ p ,q\ :p ^ .p = tr(q)

Proof.

[p ]:H p .o.

T h . 4.

M ••[?]•.? = M a) •=

(Th. 2, Th. 3)

T h . 5.

Dp . a ] " [ / ]

:[d-3> =/(*■)•

u

fTV

£2j

r—l

Proof.

s

u

(Hp, 1) Hi is 2

Cn

2

(Th. 1)

III

tr{q)

(1)

\r\.p == /3

3

~ f ( r ) . =s .[r ].g s / ( r )

s

! > , 8 , / ] " - f f p 3 :.

i—

(4)

(1,2)

= ? HI

jP

II!

(3)

(Hp) III

(2)

P 1

( 1)

(5)

[ r ] :p s / ( r ) . = .q = f { r ) :

(6)

[r\.p = /(»• ). = .[r ].g = = / » : . On

T h . 11.

(3) (4) (5) ( 1, 6)

\jp,q\v.p.q== : . [ f ] : . p = :[r].j> = / ( r ) . = . [ r ] . q = f ( r ) (Th. 10, Th. 9)

§ 2. T r u t h - f u n c t io n s a n d t h e L a w o f S u b s t it u t io n

Whitehead and Russell, in their work mentioned above, refer to a function / as a truth-function1 if it takes sentences as argu­ ment values and satisfies the condition (a)

0 , 8]

3 /(g ).

The sentence (A)

[p,q,f] :p = q,f(p ) . 3 /(8 ),

which expresses the fact that every function / (taking sentences a$ argument values) is a truth-function, will be called the 'law of substitution\ 1 A. JST. Whitehead and B. Russell (90), vol, 1, p. 659 ff.

6

ON TH E P R IM IT I V E TERM OF LOGISTIC

I, § 2

In Def. 4 I introduce the sym bol ‘Bp’ ; by this definition, the expression will mean the same as ‘the function / is a truth-fiinction\ Def. 5 will enable us to replace the law o f substitution b y a single sym bol *Sb\ Am ong the theorems proved in this section, Th. 17 is the most important. I t shows that, in a system o f logistic which contains the law o f substitu­ tion among its axioms or theorems, the sentence formulated in Th. 11 can be replaced b y a simpler sentence,

[p ,q ]:.p.q. ss : [ / ] : p s ./(p ) s / ( j ) , which also can serve as a definition o f the symbol o f logical product in terms o f the equivalence symbol and the universal quantifier. From Th. 20 it follows that another closely related aari f/iri OP*

[ p , q ] : . p v q . = : [ 3 / ] :p ss .f(p ) s=f(q) can be used to define the sym bol o f logical sum. The remaining theorems o f this section are o f auxiliary character. D e f . 4.

[ / ] :. 8P{ f } = : [p, q] : p ~ q .f(p ) . of(q)

D e f . 5. T h . 12.

Sb = .[f ].6 p { f ) [ / ] : . 8p{f} = -[p,q]:p = g.D ./(p ) = /(g ) (Def. 4)

T h . 13.

8b == : [ p , q j ] :p = q-f(p).of{q)

T h . 14.

8b = :[p , q,f] :p

(Def. 5, D ef. 4)

q. o ,f(p) ==/(g) (Def. 5, Th. 12)

T h . 15.

8b = : . \ p , q , f ] : p . q . ? -f(p) s s fiq ) : . [p,q>f ] ■~ (?)• ~ (?)• 3 -f(p) = /( ? ) (Th. 14)

The theorem just stated shows that the law o f substitution is equivalent to the logical product o f two sentences, the first o f which could be called the law of substitution far true sentences, and the second one the law of substitution for false sentent&s. I am unable to solve the problem whether either o f these two sentences alone is equivalent to the general law o f substitution. T h . 16.

[ p , q , f ] : p . q . O .f(p) = /( g ) : D :.[p ,g ] :.p .g . e : [ / ] -P »

f(P)

I, §2

7

ON TH E P R IM IT IV E TER M OF LOGISTIC

Proof.

H p : o :.: 4

( 1)

:.

(a)

p.q:

(6'

[ / ] • /( ? ) = /(?)• '•

(e)

[ / ] : p = ./(p ) a / ( g ) : . :

( 2)

(Hp,a) (o, 6)

[P »ff]” [/]-* P s -/(P) * / t o ) =3 :•

(e)

P = -M p ) = tr{q) :

(/)

tr(p)s=tr(q).

to)

P:

(A)

p = .as(p) == a s(g ):

W

•«

• ••

III

III

**>

•• r—i

to)

( j)

p = p .s= q :

(i )

(*)

?•

0 ‘)

(*)

P -?:--*

to) (Th. 1)

(d) S'

••

III

*

III

(e ,/)

(?>*)

>?]:• ~ (p) •~ (?) • = : [ / ] : ~ (p) a ./(p ) a / ( g ) (Th. 1, Def. 2)

I am omitting the p roof o f Th. 18 which is entirely analogous to that o f Th. 16. T h . 19.

[ p . ? , / ] : ~ (p ). ~ to), o -f(P) ^ / ( ? ) ••3 •••[>.?]:• p v g . a : [ 3 / ] :p a ./(p ) a f(q)

T h . 20 .

(Th. 18)

Sbo :.[ p , g ] : . p V g . a : [ 3 / ] : p a ./(p ) a / ( g ) (Th. 15, Th. 19)

The converses o f Ths. 16 and 19 can easily be established. It is a direct conclusion that the sentence !>>