Handbook of the History of Logic Volume 8 The Many Valued and Nonmonotonic Turn in Logic
Handbook of the History of Logic Volume 8 The Many Valued and Nonmonotonic Turn in Logic
AMSTERDAM • BOSTON • HEIDELBERG • LONDON • NEW YORK • OXFORD
PARIS • SAN DIEGO • SAN FRANCISCO • SINGAPORE • SYDNEY • TOKYO
North-Holland is an imprint of Elsevier
Handbook of the History of Logic
Volume 8
The Many Valued and
Nonmonotonic Turn in Logic
Edited by Dov M. Gabbay Department of Computer Science
King’s College London
Strand, London, WC2R 2LS, UK
and
John Woods Philosophy Department
University of British Columbia
Vancouver, BC Canada, V6T 1Z1
and
Department of Computer Science
King’s College London
Strand, London, WC2R 2LS, UK
and
Department of Philosophy
University of Lethbridge
Lethbridge, Alberta, Canada, T1K 3M4
AMSTERDAM • BOSTON • HEIDELBERG • LONDON • NEW YORK • OXFORD
PARIS • SAN DIEGO • SAN FRANCISCO • SINGAPORE • SYDNEY • TOKYO
North-Holland is an imprint of Elsevier
North-Holland is an imprint of Elsevier Radarweg 29, PO Box 211, 1000 AE Amsterdam, The Netherlands Linacre House, Jordan Hill, Oxford OX2 8DP, UK
First edition 2007 Copyright © 2007 Elsevier B.V. All rights reserved No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means electronic, mechanical, photocopying, recording or otherwise without the prior written permission of the publisher Permissions may be sought directly from Elsevier’s Science & Technology Rights Department in Oxford, UK: phone (+44) (0) 1865 843830; fax (+44) (0) 1865 853333; email:
[email protected]. Alternatively you can submit your request online by visiting the Elsevier web site at http://elsevier.com/locate/permissions, and selecting Obtaining permission to use Elsevier material Notice No responsibility is assumed by the publisher for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions or ideas contained in the material herein. Because of rapid advances in the medical sciences, in particular, independent verification of diagnoses and drug dosages should be made Library of Congress Cataloging-in-Publication Data A catalog record for this book is available from the Library of Congress British Library Cataloguing in Publication Data A catalogue record for this book is available from the British Library ISBN:
978-0-444-51623-7
For information on all North-Holland publications visit our website at books.elsevier.com
Printed and bound in The Netherlands 07 08 09 10 11 10 9 8 7 6 5 4 3 2 1
CONTENTS Preface
vii
List of Authors
xi
Many-valued Logic and its Philosophy Grzegorz Malinowski
13
Preservationism: A Short History Bryson Brown
95
Paraconsistency and Dialetheism Graham Priest
129
The History of Quantum Logic Maria Luisa Dalla Chiara, Roberto Giuntini and Miklos R´ edei
205
Logics of Vagueness Dominic Hyde
285
Fuzzy-set Based Logics — An History-oriented Presentation of their Main Developments
Didier Dubois, Francesc Esteva, Llu´ıs Godo and Henri Prade
325
Nonmonotonic Logics: A Preferential Approach Karl Schlechta
451
Default Logic Grigoris Antoniou and Kewen Wang
517
Nonmonotonic Reasoning Alexander Bochman
557
Free Logics Carl J. Posy
633
Index
681
This page intentionally left blank
PREFACE
From its inception nearly 2500 years ago, logic has taken a dominant interest in the notion of logical consequence. It is widely agreed that there exists a basic con ception of deductive consequence, which Aristotle called “necessitation”, in which sentences or sets of sentences serve as inputs, generating output-sentences in a truth-preserving way. What is not widely agreed is that truth-preserving neces sitation is the sole relation of consequence, or the only form of it that merits the serious interest of logicians. Aristotle himself introduces a further — and, for his interests, the more important — idea of syllogistic consequence. Syllogistic conse quence is a restriction of necessitation, got by imposing further conditions which, among other things, require that syllogisms not have redundant premisses. This is clearly a constraint on inputs, and it is easy to see that it has the effect of making syllogistic consequence strongly non-monotonic. For if an argument is a syllogism, then the result of adding new sentences to its premisses cannot itself be a syllo gism. Aristotle also imposed constraints on the outputs of syllogistic consequence. Syllogisms are required to have only single propositions as conclusions. The question of the constraints it may be desirable or necessary to impose on a stripped down, merely truth-preserving deduction relation brings into conver gence the two main themes of the present volume of the Handbook of the History of Logic. Twentieth and twenty-first century logic is well-stocked with affirmative answers to this question. Many valued logicians gravitate to the idea that a re alistic characterization of consequence requires the admissibility of inputs which, owing to vagueness, temporal or quantum indeterminacy, or reference-failure, can not be considered classically bivalent. Consider the sentence “The present king of France”. On the many valued approach, the non-existence of the present king of France denies the sentence a referent, which in turn denies it a classical truth value. In classical logic, such sentences may not be admitted to the consequence relation. In many valued systems, the admissibility of such sentences is secured by the postulation of one of more additional truth values. Free logics offer an interesting alternative to many valued treatments of reference-failure. Instead of allowing many-valued sentences as inputs, free logicians retain the classical truth values while restricting output. In particular, the quantifier introduction rule F a ∃x(F x) fails when F a is guilty of reference failure. In a variation of free logic, the necessity to multiply truth values is also averted, provided we are pre pared to add to the logic’s standard domain of discourse a non-standard domain, in which singular terms such as “the present king of France” pick up a referent, notwithstanding that they lack a referent in the standard domain. Either way,
viii
Preface
whether the many valued way or the free logic way, something has to be added if sentences such as these are to be admitted to the consequence relation. Either an additional truth value must be introduced or an additional domain of discourse. Many valued logics are non-bivalent. This generates a problem for classical va lidity. An argument is valid classically if and only if there is no valuation making its premisses true and its conclusion false. So any argument containing at least one non-bivalent sentence — whether in basic systems such as K3 or in quantum logics or vagueness logics — is trivially valid classically. Accordingly, many valued consequence has to be contrived so as to avert these promiscuous validities. Many valued logics also impose constraints on outputs. In classical logic, the Law of Ex cluded Middle is a logical truth, hence is a consequence of any sentence whatever. But since in virtually all systems of many valued logic Excluded Middle is not a logical truth, it is not output for every input. Non-monotonic logicians, like Aristotle before them, are constrainers of inputs; and often they lay restrictions on outputs as well. The leading intuition of nonmonotonic logics is that there exist consequence relations in which reasonably drawn conclusions from a given set of premisses can be upset by the addition of new information, and that such consequence relations should be taken seriously by logicians. Default logics are a standard affirmative response to this intuition. When the conclusion drawn from some given premisses is a “default”, then it obtains provisionally and only in the absence of information to the contrary. Since indications to the contrary might subsequently present themselves in the form of new information, such consequences are non-monotonic. There are also many valued approaches in which it seems appropriate or nec essary directly to constrain the consequence relation itself. Dialetheic logics are a case in point. Dialetheic logics are systems in which selected sentences are allowed to be both true and false at once. Such sentences, while true, aren’t true only, since they are also false, hence not false only. Accordingly being both true and false is a third truth value, which makes dialetheic systems many valued. If conse quence were allowed to operate classically in these logics, then any input carrying the third truth value would have every sentence whatever as output. To avert this explosion, consequence has to be a paraconsistent relation, that is, one that does not generate this unfettered output. Accordingly, dialetheic logic is also a paraconsistent logic. The converse does not hold, however. There are paraconsistent logics that muffle the explosiveness of classical consequence without the necessity to posit true contradictions. A dominant move in paraconsistent circles is to con strain explosiveness by restricting the application of the output rule, Disjunctive Syllogism, when inputs contain inconsistencies, whether deemed true or not. A further development — also a many valued one — are fuzzy logics, which are purpose-built to accommodate vague sentences both as inputs to and outputs of the consequence relation. The founding insight of these logics is not that vague sentences require additional truth values, but that the classical truth and falsity will do provided that we allow the values of sentences to be degrees (or slices) of them. So seen, “Harry is bald” might be either true or false, or neither; and if
Preface
ix
neither, it might be somewhat true, or true to degree n, where n is fairly high; or more false than true, or false to degree m, where m is higher than any degree to which the sentence is true. The ten chapters of The Many Valued and Non-Monotonic Turn in Logic are designed to give readers a detailed, expert and up-to-date appreciation of the character and importance of the main expression of the volume’s twin themes. Once again the Editors are deeply and most gratefully in the debt of the vol ume’s very able authors. The Editors also warmly thank the following persons: Professor John Beatty, Acting Head of the Philosophy Department, and Pro fessor Nancy Gallini, Dean of the Faculty of Arts, at the University of British Columbia; Professor Michael Stingl, Chair of the Philosophy Department, and Professor Christopher Nicol, Dean of the Faculty of Arts and Science, at the Uni versity of Lethbridge; Professor Andrew Jones, Head of the Computer Science Department at King’s College London; Jane Spurr, Publications Administrator in London; Carol Woods, Production Associate in Vancouver and our valued col leagues at Elsevier, Senior Publisher, Arjen Sevenster, and his successor Donna Weerd-Wilson, and Production Associate, Andy Deelen. Dov M. Gabbay King’s College London John Woods University of British Columbia and King’s College London and University of Lethbridge
This page intentionally left blank
CONTRIBUTORS Grigoris Antoniou
Institute of Computer Science, FORTH, PO Box 1385, 71110 Heraklion, Crete,
Greece.
[email protected]
Bryson Brown
Department of Philosophy, University of Lethbridge, 4401 University Drive Leth
bridge, Alberta T1K 3M4, Canada.
[email protected]
Alexander Bochman
Department of Computer Science, Holon Institute of Technology, Holon, Israel.
[email protected]
Maria Luisa Dalla Chiara
Departimento di Filosofia, Universita’ de Firenze, Via Bolognese 52, I-50139 Firenze,
Italy.
dallachiara@unifi.it
Didier Dubois
Universit´e Paul Sabatier, IRIT, 118 Route de Narbonne, 31062 Toulouse Cedex
09, France.
[email protected]
Roberto Giuntini
Dipartimento di Scienze Pedagogiche e Filosofiche, Universita’ di Cagliari, Via Is
Mirrionis 1, I-09123 Cagliari, Italy.
[email protected]
Lluis Godo
o en Intellig`encia Artificial (IIIA), - Consejo Superior de In
Institut d’Investigaci´ vestigaciones Cient´ıficas (CSIC) - 08193 Bellaterra, Spain.
[email protected]
Dominic Hyde
School of History Philosophy Religion and Classics, University of Queensland,
Brisbane, Queensland, 4072, Australia.
[email protected]
Grzegorz Malinowski
Department of Logic, University of Lodz, Poland.
[email protected]
xii
Contributors
Carl J. Posy
Department of Philosophy, Hebrew University of Jerusalem, Mt. Scopus, Jerusalem
91905, Israel.
[email protected]
Henri Prade
Universit´e Paul Sabatier, IRIT, 118 Route de Narbonne, 31062 Toulouse Cedex
09, France.
[email protected]
Graham Priest
Philosophy Department, The University of Melbourne, Victoria 3010, Australia;
and Department of Philosophy, University of St Andrews, St Andrews,KY16 9AL,
Scotland.
[email protected]
Miklos R´edei
Department of History and Philosophy of Science, Faculty of Natural Sciences,
Lorand Eotvos University, Budapest, Hungary.
[email protected]
Karl Schlechta
Laboratoire d’Informatique de Marseille, UMR 6166, CNRS and Universit´e de
Provence, CMI, 39 rue Joliot-Curie, F-13453 Marseille Cedex 13, France.
[email protected], karl.schlechta:web.de
Kewen Wang
School of Information and Communication Technology, Griffith University, Bris
bane, QLD 4111 , Australia.
k.wang@griffith.edu.au
MANY-VALUED LOGIC AND ITS
PHILOSOPHY
Grzegorz Malinowski
INTRODUCTION The assumption stating that every propositions may be ascribed to exactly one of the two logical values, truth or falsity, called the principle of bivalence constitutes the basis for the classical logic.It determines both the subject matter and the scope of applicability of the classical logic. The principle is expressed together through the law of the excluded middle, p∨¬p and the principle of contradiction, ¬(p∧¬p). Given the classical understanding of the logical connectives, the above laws may be read, respectively, as stating that of the two propositions p and ¬p: at least one is true and at least one is false. The most natural and straightforward step beyond the two-valued logic is the introduction of more logical values, rejecting simultaneously the principle of biva lence. The indirect ways consist in revision of the “bunch” of sentence connectives, mostly after having questioned some classical laws concerning them. Then some non-truth-functional connectives are introduced into the language and the propo sitional logic is primal. The multiple-valued truth-tables constitute the basis of the first method, whereas in the other case they are procured as tools for the pro cedures of decidability of logical theorems. In either case, the extensional matrix semantics is based on revised “multiple-valued” truth-functionality. The chapter is devoted to the most important systems of many-valued logic and the vital philosophical and metalogical problems of many-valuedness. Its first aim is to give a historical account of the most important systems of many-valued logic and their development. In particular, to overview the original motivations and characteristic properties. The second aim of the proposal is to subscribe to a discussion on many-valuedness at all. Accordingly, some known, albeit the most justified, approaches to many-valuedness are recalled and, further to that, the author’s own approach to the problem of many-valuedness based on the inferential theory of (structural) propositional logics is presented.
Handbook of the History of Logic. Volume 8 Dov M. Gabbay and John Woods (Editors) © 2007 Elsevier B.V. All rights reserved.
14
Grzegorz Malinowski
The last two Sections, “Recent developments” and “Applications”, complement the general part of the text and introduce the Reader into more special topics. Monographs, expository papers on several issues concerning many-valuedness and suggested further readings are in Bibliography marked by an aterisk *. 1 WAYS OF MANY VALUES The question when a logic is many-valued is uneasy and non-trivial. To start with we outline an early history of the subject and recall some important justifica tions, interpretations and explanations of many logical values. We focus on future contingents, paradoxes and probability.
Early history The roots of many-valued logics can be traced back to Aristotle (4th century BC). In Chapter IX of De Interpretatione Aristotle considers the timely honoured sentence “There will be a sea-battle tomorrow”, which cannot be evaluated from the point of view of truth and falsity. The battle-sentence falls in a wide category of future contingents sentences, which refer to the future not necessary, or not actually determined, events. The Philosopher from Stagira suggests the existence of the “third” logical status of propositions. The prehistory of many-valued logic falls on the Middle Ages. However, an eval uation to what extent the approaches by Duns Scotus (c. 1266–1308), William Ockham (1285–1347) and Peter de Rivo (1420–1499) submitted to the topic is fairly uneasy. Mostly, since their studies were limited to the topics following Thomas Aquinas’ discussion of future contingents and divine foreknowledge. Ac cordingly, they were concerned with the modality and to the consequentia. More serious attempts to create non-classical logical constructions, three-valued mainly, appeared only on the turn of the XIXth century: they were due to Hugh MacColl, Charles S. Peirce, Nicolai A. Vasil’ev. In most cases the division of the totality of propositions into three categories was supported by some considera tions dealing with some modal or temporal concepts. Eventually, some criteria of the distinction were applied and the propositions mostly were grouped as either “affirmative”, “negative” or “indifferent”. Philosophical motivations for many-valuedness may roughly be classified as on tological and epistemic. First of them focus on the nature of objects and facts, while the others refer the knowledge status of actual propositions. The “Era of many-valuedness” was finally inaugurated in 1920 by L � ukasiewicz and Post, cf. L � ukasiewicz [1920], Post [1920]. The thoroughly successful formulations of manyvalued logical constructions were possible in the result of an adaptation of the truth-table method applied to the classical logic by Frege in 1879, Peirce in 1885 � ukasiewicz and Post method of and others. The impetus thus given bore the L logical algebras and matrices. Apparently different proposals of the two scholars had quite different supports.
Many-valued Logic and its Philosophy
15
The distinguishing feature of many-valued logics is that some of their connec tives are non-truth-functional with respect to truth and falsity, what means that their properties cannot be fully described by two logical values. On the other hand, all connectives of a many-valued logic proper display a kind of generalized “truth-functionality”, i.e. an extensionality with respect to actual values of the logic in question. The non-truth functionality, due to the traditional extension–intension oppo sition, has also been identified as intensionality. This distinction played some important role on extended justification for the construction of several systems of logic, which either did not have any direct explanation in terms of unorthodox logical values or did not accept anything but the truth-falsity universe. Then, using the axiomatic method, some non-classical constructions formalizing inten sional, and thus non-truth-functional, connectives appeared in the 1930s. First, the Lewis modal logics and the intuitionistic logic codifying the principles of a significant trend in the philosophy of mathematics initiated by Brouwer in 1907.
Future contingents The Aristotelian sea-battle sentence has been referred to and reproduced on sev � ukasiewicz eral occasions throughout the entire XXth century. The first was L analysing the sentence “I shall be in Warsaw at noon on 21 December of the next year.” The Polish philosopher argues that at the moment of the utterance this sen tence is neither true nor false, since otherwise would get fatalist conclusions about necessity or impossibility of the contingent future events. In the seminal paper � ukasiewicz considers the three values: 0, 1 and 2. ojwarto´sciowej”1 L “O logice tr´ While 0 and 1 are the classical values of the falsity and truth, the additional value 2 is a value of future contingent sentences and is interpreted as “possibility” or � ukasiewicz changed the notation, putting 1/2 instead of “indeterminacy”. Soon, L 2, and suggested that the natural “ordering” of the three values had reflected his philosophical intuitions concerning prepositional connectives better. And, slightly later, in 1938, when Gonseth urged to remark incompatibility of this way of inter � ukasiewicz preting the third value with other principles of the three-valued logic, L also quitted his “possibilistic” explanation of the intermediary logical value. Gon � ukasiewicz interpretation neglects the seth’s argument discovers that the original L mutual dependence of “possible” propositions and it runs as follows: consider two propositions α and ¬α. Whenever α is undetermined, so is ¬α and then, the con junction α ∧ ¬α is undetermined. This, however, contradicts the intuition since, independently of α’s content, α ∧ ¬α is false. The approach referring to future contingents has been discussed by further — we shall come back again to the problem, as soon as we have at hand all necessary knowledge concerning the propositional connectives. 1L � ukasiewicz
[1920].
16
Grzegorz Malinowski
Paradoxes The famous 1907 Russell’s re-discovery of the Liar paradox troubled the scientific community. The kernel of the semantic paradox, known already in antiquity, is the self-reference, which leads to absurd. Thus, e.g. when one says “I am now speaking falsely” yields that what she says is true if, and only if, she speaks falsely. The re-discovery version is set-theoretical. The Russell set “of all sets that are not their own elements”, Z = {x : x ∈ x}, put the Cantor’s set theory into question and inflicted a serious logical problem. Accepting Z in the set theory founded on the classical logic and substituting it for x in the formula we get an inconsistent equivalence Z∈Z≡Z∈ Z.
(∗)
So, is we insist on retaining Z, the sole possibility would be to change the underlying logic. Actually, this attitude was a strong argument in favour of manyvalued logics: the formula (*) ceases to be antinomy even in the simplest, threevalued L � ukasiewicz logic. Still, however, the original version of the Liar paradox inspired Bochvar [1938] and led him to the conception of three-valued logic based on the division of propositions into sensible and senseless, and then “mapping” it into a two-level formal language. A proposition is meaningful if it is either true or false, all other sentences are considered as meaningless or paradoxical. The propositional language of Bochvar logic has two levels, which correspond to the object language and to the metalanguage. The both levels have their own connectives being counterparts of standard connectives. The whole approach has been mainly directed towards solving paradoxes emerging with the classical logic and set theory based on it.
Many-valuedness and probability L � ukasiewicz, still before 1918, invented a theory of logical probability. The dif ferentiating feature of logical probability is that it refers to propositions and not � ukasiewicz [1913]. The conception was based on the assumption that to events, L there is a function P r ranging over the set of propositions of a given standard propositional language, with values from the real interval [0,1] satisfying the con ditions: P r(p ∨ ¬p) = 1, P r(p ∨ q) = P r(p) + P r(q) for p and q mutually exclusive (P r(p ∧ q) = 0) and such that P r(p) = P r(q) for any two logically equivalent p and q. If the logical value v(p) is then identified with the measure of probability P r(p) then for P r(p) = 1/2 we would get /2 ∨ 1/2 = P r(p ∨ ¬p) = 1 and 1/2 ∨ 1/2 = P r(p ∨ p) = P r(p) = 1/2 .
1
Many-valued Logic and its Philosophy
17
Consequently, logical probability must not be identified with logical values of many-valued logic. The reason is that probabilistic intensionality is incompati ble with logical extensionality. The logical probability has been later considered by several scholars. The con tinuators of the line exerted much effort to create unsuccessfully a many-valued logic within which logical probability could find a satisfactory interpretation, see e.g. Zawirski [1934a; 1934b], Reichenbach [1935]. Many years later, Giles [1975] got satisfactory results concerning relation probability — logical values.2 It may be interesting to learn that the early, somewhat naive, probabilistic approach bore the first intuition of non-classical logical values. L � ukasiewicz [1913] classified as undefinite the propositions with free nominal variables ranging over finite domains. He assigned to them fractions indicating the proportions between the number of actual variable values verifying a proposition and the number of all possible values of that variable. The “logical” values thus introduced are relative: they depend on the set of individuals actually evaluated. So, for example, the value of the proposition ‘x2 − 1 = 0’ amounts to 1/2 in the set {−1, 0} and to 2/3 in the set {−1, 0, 1}. Obviously enough, infinite sets of individuals are not admitted � ukasiewicz’s suggestion cannot be seriously taken within and this implies that L the theory of probability. 2
THE THREE-VALUED L � UKASIEWICZ LOGIC
The actual introduction of a third logical value next to truth and falsity, was � ukasiewicz, a co-originator of the preceded by thorough philosophical studies. L Lvov-Warsaw philosophical school,3 was concerned with the problems of induction � ukasiewicz and the theory of probability. Especially, while dealing with the latter L [1913] extricated himself from the “embarrassing” principle of contradiction. Still more direct influence on L � ukasiewicz’s thinking had the discourse in the Lvov-Warsaw school about freedom and creativity. Kotarbi´ nski [1913] suggested the need of revising the two-valued logic that seemed to interfere with the free � ukasiewicz, a fierce follower of indeterminism, finally dom of human thinking. L introduced the third logical value to be assigned to non-determined propositions; specifically, to propositions describing casual future events, i.e. future contingents. The entirely organized system, following the scheme of CP C, of propositional logic had as its aim to solve, among others, several questions concerning modality and paradoxes of set-theory.
The third logical value The first remarks about the three-valued propositional calculus can be found in the Farewell Lecture given in the Assembly Hall of Warsaw University on the 2 Giles considered subjective probability and translated its degrees into logical values of the � ukasiewicz logic in a fairly sophisticated way. infinite L 3 See Wole´ nski [1989].
18
Grzegorz Malinowski
7th March, 1918. Next came the paper “O logice tr´ ojwarto´sciowej” [�Lukasiewicz, 1920]. It brings an outline of the negation-implication version of the propositional calculus, whose semantics is based on three values: 0, 1 and, additionally 1/2 .4 At � ukasiewicz interpreted the third logical value 1/2 as “possibility” or the early stage L “indeterminacy”. Following intuitions of these concepts, he extended the classical interpretation of negation and implication in the following tables:5 α 0 1 /2 1
¬α 1 1 /2 0
→ 0 1 /2 1
0 1 1 /2 0
1
/2 1 1 1 /2
1 1 1 1
The other connectives of disjunction, conjunction and equivalence were (later) introduced through the sequence of the following definitions: α ∨ β =df (α → β) → β α ∧ β =df ¬(¬α ∨ ¬β) α ≡ β =df (α → β) ∧ (β → α). Their tables are as follows: ∨ 0 1 /2 1
0 0 1 /2 1
1
/2 /2 1 /2 1 1
≡ 0 1 /2 1
∧ 0 1 /2 1
1 1 1 1 0 1 1 /2 0
1
/2 /2 1 1 /2 1
0 0 0 0
1
/2 0 1 /2 1 /2
1 0 1 /2 1
1 0 1 /2 1
A valuation v in the three-valued logic is any function from the set of formu las F or to {0, 1/2 , 1}, v : F or → {0, 1/2 , 1}, compatible with the above tables. A tautology is a formula which under any v takes on the designated value 1. � ukasiewicz differs from TAUT. The set L � 3 of tautologies of three-valued logic of L So, for instance, neither the law of the excluded middle, nor the principle of con � 3 . To see this, it suffices to assign 1/2 for p: any such valuation also tradiction is in L 1 associates /2 with EM and CP . The thorough-going refutation of these two laws was intended, in L � ukasiewicz’s opinion, to codify the principles of indeterminism. 4 In
L � ukasiewicz [1920] the notation is different: 2 appears instead of 1/2 . truth-tables of binary connectives ∗ are viewed as follows: the value of α is placed in the first vertical line, the value of β in the first horizontal line and the value of α ∗ β at the intersection of the two lines. 5 The
Many-valued Logic and its Philosophy
19
Another property of new semantics is that some classically inconsistent formulas � 3 . One of such formulas: are no more contradictory in L p ≡ ¬p,
(∗)
is connected with the Russell paradox since the equivalence Z∈Z≡Z∈ Z, is a substitution of (*). Accordingly, Russell paradox ceases to be antinomy in L � 3: putting 1/2 for p makes the formula (*) true and therefore it is non-contradictory
Modality, axiomatization and interpretation Another L � ukasiewicz’s intention was to formalize the modal functors: of possibil ity M and necessity L. L � ukasiewicz postulated preservation of the consistency of middle ages’ intuitive theorems on modal propositions. Being aware of impossibil ity of expressing these functors in the truth-functional classical logic L � ukasiewicz took the three-valued logic as base. In 1921 Tarski produced simple definitions, � ukasiewicz’s using negation and implication, of the two connectives meeting the L requirements:6 x 0 1 /2 1
Mx 0 1 1
x 0 1 /2 1
Lx 0 0
1
M α =df ¬α → α Lα =df ¬M ¬α = ¬(α → ¬α)
Using M, L and other L � ukasiewicz connectives we get third modal connective “it is contingent that”or, “it is modally indifferent”, distinguishing the intermediate logical value α 0 1 /2 1
Iα 0 1 0
Iα = M α ∧ ¬Lα
Applying I allows the formulation within L � 3 , of counterparts of the law of the excluded middle and the principle of contradiction: p ∨ Ip ∨ ¬p ¬(p ∧ ¬Ip ∧ ¬p) 6 See
L � ukasiewicz [1930].
20
Grzegorz Malinowski
rendering altogether that L � ukasiewicz’s logic is three-valued. In spite of the promising combination of trivalence and modality the full elabo ration of modal logic on the basis of the three-valued logic never succeeded (with the mere exception of algebraic constructions of Moisil — see Section 6), which was the result of the further L � ukasiewicz’s investigations on modal sentences (see L � ukasiewicz [1930]). Many years after L � ukasiewicz comes back to the idea of construction of pluri-valued modal system and he exhibits a four-valued logic of possibility and necessity, L � ukasiewicz [1953]. L � 3 through the law of excluded fourth and the extended contradiction principle, expresses its three-valuedness. However, it is limited since not all connectives de scribed by {0, 1/2 , 1}-tables are definable through formulas. One important example is the constant connective T , such that T x = 1/2 for any x ∈ {0, 1/2 , 1}. The axiomatization of L � 3 due to Wajsberg [1931] is the first known axioma tization of a system of many-valued logic. Accepting the rules M P and SU B Wajsberg axiom system for (¬, →)-version of L � ukasiewicz’s three-valued proposi tional calculus is as follows: W1. W2. W3. W4.
p → (q → p) (p → q) → ((q → r) → (p → r)) (¬p → ¬q) → (q → p) ((p → ¬p) → p) → p.
� ukasiewicz con The result obviously applies to the whole L � 3 since the other L nectives are definable using those of negation and implication. S�lupecki [1936] enriched the set of primitives by T and adding to W1–W4: W5. W6.
T p → ¬T p ¬T p → T p
got an axiom system for the functionally complete three-valued logic, compare Section 4.
An intuitive interpretation In view of existing difficulties, see Section 1, S�lupecki [1964] undertook another � ukasiewicz’s logic. S�lupecki points out a definite attempt to interpret intuitively L language to describe the property of events determination in three-valued man � ukasiewicz’s truth-tables. The language has a set S comprising ner reconciling L propositions about events, which contain simple (atomic) propositions and com pound ones formed by means of disjunction (∨), conjunction (∧) and negation (¬) connectives. S�lupecki supposes the set of events Z described by propositions of S to be closed under the operations of union (∪), meet (or, intersection) (∩) and complementation (−) and, furthermore, the structure Z = (Z, ∪, ∩, −) to be a Boolean algebra. There is a causality relation → on Z (“f1 → f2 ” reads: the event f1 is a cause of the event f2 ”) providing the assumption that
Many-valued Logic and its Philosophy
(P1) (P2) (P3) (P4)
21
f → f1 ∪ f2 iff f → f1 or f → f2 .
f1 and f → f2 . f → f1 ∩ f2 iff f → If f → f1 for some f , then f + → −f1 for no f + .
f .
If f1 → f , then f1 ∩ f2 →
for any f, f1 , f2 ∈ Z. For the purpose of defining the property of determination, he then singles out a set of past and present events hereafter denoted by symbols: g, g1 , g2 . . ., and puts D(f ) D(f )
= df = df
there is a g ∈ Z such that g →
f ,
not D(f ) and not D(−f )
The intended meaning of D(f ) is that f is (at the present moment)determined, and D(f ) that f is (at the present moment) not determined . The relation ∗ between propositions in S and events in Z of describability (“p∗f ” reads: p describes (event) f ) has to satisfy the conditions: p ∨ p1 ∗ f ∪ f1 whenever p ∗ f and p1 ∗ f1 p ∧ p1 ∗ f ∩ f1 whenever p ∗ f and p1 ∗ f1 when p ∗ f, then ¬p ∗ −f .
(∗)
for any p, p1 ∈ S. In the end, S�lupecki defines the three properties 1(α), 0(α) and 1 /2 (α) : 1(α) = p is true, 0(α) = α is false, 1/2 (α) = α has the “third” logical value, as follows: (DT)
if α ∗ f, then {1(α) iff D(f )} if α ∗ f, then {0(α) iff D(−f )} if α ∗ f, then {1/2 (α) iff D(f )}.
Using (P1)–(P4) and (∗), it is easy to check that for x ∈ {0, 1/2 , 1} x(p ∨ q) = x(p) ∨ x(q)
x(p ∧ q) = x(p) ∧ (q)
x(¬p) = ¬x(p),
where ∨, ∧ and ¬ appearing on the right-hand side are the connectives of the three-valued L � ukasiewicz’s logic. Thus, (DT) to some extent justifies the L � ukasie wicz interpretation of logical values with reference to the property of determina tion. S�lupecki’s interpretation omits the implication connective. Admittedly, S�lupecki extends it onto the language with modal connectives M and L and in thus enriched � ukasiewicz is definable. However, the interpretation language the implication of L of the implication obtained is fairly unintuitive. On the other hand, more profound analysis of the whole construction reveals that the assumption concerning Z has to be weakened: Nowak [1988] proved the formal correctness of the interpretation exclusively when Z is de Morgan lattice and not a Boolean algebra. This result shows that the three-valued logic can thus be interpreted as a set of propositions
22
Grzegorz Malinowski
describing events which form a non-classical algebra. (DT) implies then that the � ukasiewicz, 1/2 , is assigned to propositions concerning non-boolean, third value of L undetermined events. Some time later, in 1922, L � ukasiewicz extended his three-valued construction onto further sets of values and defined important family of finite and infite valued logics, see Section 6.
3
THREE-VALUED LOGICS OF KLEENE AND BOCHVAR
Kleene [1938; 1952] is the author of two systems of propositional and predicate logic motivated by indeterminacy of some propositions at a certain stage of investi gation. Inspired by the studies of the foundations of mathematics and the theory of recursion Kleene aimed at getting tools that render the analysis of partially defined predicates possible. To be aware of a necessity of such logic(s) let us consider a simple example of such a predicate, the mathematical property P defined by the equivalence P (x)
1 ≤ 1/x ≤ 2,
if and only if
Where x is a variable ranging over the set of real numbers. It is apparent that due to the properties of division for x = 0 the propositional function P (x) is undetermined. More precisely, we then have that if 1 /2 ≤ a ≤ 1
true undetermined if a = 0
Proposition P (a) is false otherwise. The starting point of Kleene’s [1938] construction consists in considering also the propositions whose logical value of truth (t) or falsity (f) is undefined, unde termined by means of accessible algorithms, or not essential for actual considera tion. The third logical value of undefiniteness (u) is reserved for this category of propositions. Kleene’s counterparts of the standard connectives are defined by the following tables: α f u t
¬α t u f ∧ f u t
→ f u t f f f f
u f u u
f t u f t f u t
u t u u
∨ f u t
t t t t ≡ f u t
f t u f
f f u t u u u u
u u u t t f u t
t t t t
Many-valued Logic and its Philosophy
23
One may easily notice that as in L � ukasiewicz logic the connectives’ behaviour towards the classical logical values t and f remains unchanged. However, now also mutual definability of α → β and ¬α ∨ β is saved. Kleene takes t as the only distinguished value and, in consequence, obtains that no formula is a tautology — it follows from the fact that any valuation which assigns u to every propositional variable also assigns u to any formula. It is striking that so “conservative” extension of the two-valued logic rejects all classical tautologies, even such as p ∨ ¬p and p → p. An accurate and compatible interpretation of Kleene’s connectives was given by K¨ orner [1966]. K¨ orner defined the notion of an inexact class of a given non-empty domain A generated by a partial definition D(P ) of a property P of elements of A as a three-valued “characteristic function” XP : A → {−1, 0, +1}: −1 when P (a) according to D(P ) is false
0 when P (a) is D(P )-undecidable
XP (a) = +1 when P (a) according to D(P ) is true. Any family of inexact classes of a given domain A is a de Morgan lattice, the algebraic operations ∪, ∩ and −: (X ∪ Y )(a) = max{X(a), Y (a)} (X ∩ Y )(a) = min{X(a), Y (a)} (−X)(a) = −X(a). being counterparts of the Kleene connectives. K¨orner’s ideas have been recently revitalized in the rough sets theory of Pawlak [1991] and the approximation logic based on it, see e.g. Rasiowa [1991]. In 1952 in his monograph Introduction to metamathematics Kleene refers to the connectives of his 1938 logic as strong and introduces another set of weak connectives: retaining the negation and equivalence he defines the three others by the tables → f u t
f t u f
u u u u
t t u t
∨ f u t
f f u t
u u u u
t t u t
∧ f u t
f f u f
u u u u
t f u t
The novel truth-tables are to describe the employment of logical connectives in respect of those arithmetical propositional functions whose decidability depends on the effective recursive procedures. They are constituted according to the rule of saying that any single appearance of u results in the whole context taking u. The original arithmetic motivation states that indeterminacy occurring at any stage of computation makes the entire procedure undetermined.
24
Grzegorz Malinowski
Bochvar As we alredy mentioned, Bochvar [1938] three-valued logic has been directed to wards solving paradoxes emerging with the classical logic and set theory based on it. The propositional language of Bochvar logic has two levels, internal and exter nal, which correspond to the object language and to metalanguage. The both levels have their own connectives: the counterparts of negation, implication, disjunction, conjunction and equivalence. The two planes of Bochvar construction correspond to Kleene weak logic (internal) and to classical logic (external), respectively. The internal connectives are conservative generalizations of the classical ones and will be denoted here as ¬, →, ∨, ∧ and ≡. The external connectives express the rela tions between logical values of propositions and incorporate the expressions “... is true” and “... is false”. They are here marked as starred connectives and understand in the following way: external external external external external
negation: implication: disjunction: conjunction: equivalence:
¬∗ α α →∗ β α ∨∗ β α ∧∗ β α ≡∗ β
‘α is false’ ‘if α is true then β is true’ ‘α is true or β is true’ ‘α is true and β is true’ ‘α is true iff β is true’.
The truth tables of internal connectives have been compiled according to the rule which is a rejoinder of the Kleene’s principle: “every compound proposition including at least one meaningless component is meaningless, in other cases its value is determined classically”. One may then easily conclude that the internal Bochvar connectives coincide with the weak connectives of Kleene. Therefore, we will adopt the previous notation for logical values with u being now the value “meaningless” and will refer the Reader to the last Section. The truth-table de scription of the second collection of Bochvar connectives is the following: α f u t
¬∗ α t t f ∧∗ f u t
→∗ f u t f f f f
u f f f
f t t f
u t t f t f f t
∨∗ f u t
t t t t ≡∗ f u t
f t t f
f f f t u t t f
u f f t
t t t t
t f f t
An important property of Bochvar construction, making it more natural, is a compatibility of two levels. The passage from the internal to external level is assured by the external assertion “α is true”, A∗. Below we show the truth-table of this connective and the intuitively justified definitions of external connectives:
Many-valued Logic and its Philosophy
25
Bochvar takes t as the designated value and thus gets the weak Kleene logic on the internal level. So, Bochvar’s internal logic does not have tautologies. Finally, the external logic is the classical logic: the truth tables of all external connectives ‘identify’ the values u and f, whereas the behaviour of these connectives with regard to f and t is standard.
A logic of nonsense Bochvar idea has been undertaken by several authors, who aimed at construing other systems appropriate for dealing with vagueness or nonsense, the latter some times called nonsense-logic. So, in his monograph “The logic of nonsense” Halld´en [1949] rediscovers Bochvar logic for these purposes. Halld´en adopts three logic values: falsity (f), truth (t) and “meaningless” (u). As the policy accepted for compound propositions and thus the connectives of negation and conjunction is just like the Bochvar’s, the truth tables of these connectives are exactly the same as in Bochvar internal logic.7 The system, however, differs from the latter. First, it has a new one-argument connective + serving to express meaningfulness of propo sitions. Thus if α is meaningless, then +α is false. Otherwise, +α is true. Second, Halld´en distinguishes two logical values u and t. Therefore, a formula is valid if it never takes f. In consequence, the set of valid formulas not containing + coincides with the set of tautologies of CP C. The construction, however, differs from the classical logic by its inference properties. The logic of nonsense restricts heavily rules of inference, among them the rule of Modus Ponens: in general q does not follow from the two premises: p → q and p. To see that it suffices consider a valuation for which p is meaningless and q is false. Under such valuation q is not designated, while the premises as meaningless are both designated. Halld´en provides a readable axiomatization of his logic. To this aim, he intro duces the connectives of implication (→) and equivalence (≡) accepting standard classical definitions and two standard inference rules M P and SU B H1. (¬p → p) → p H2. p → (¬p → q) H3. (p → q) → ((q → r) → (p → r)) H4. +p ≡ +¬p H5. +(p ∧ q) ≡ +p ∧ +q H6. p → +p In the framework, it is also easy to define a dual to + connective putting: −α =df ¬ + α. Thus, as +α corresponds to “α is meaningful”, −α stands for “α is meaningless”. Further elaboration of Halld´en’s approach is made by Aqvist [1962] and Seger berg [1965]. Departing from the problems arising with normative sentences Aqvist � ukasiewicz created the calculus, which may be considered as a minor variant of L three-valued logic, or the fragment of Kleene strong logic. The three primitives 7 Coincidence with Bochvar is striking. However, Halld´ en work is independent and original, compare e.g. Williamson [1994].
26
Grzegorz Malinowski
are: negation (¬), disjunction (∨) and a special connective # . Their tables use the three values: f, u, t (in our notation). The intended meaning of f and t is standard and the only designated is “t”. The tables of negation and disjunction � ukasiewicz threeare much the same, modulo notation, as the truth-tables of L valued connectives. # is defined as follows: #(f ) = #(u) = f and #(t) = t and � ukasiewicz “necessity” operator L. coincides with the L In view of philosophical application of his formal approach Aqvist defines three “characteristic” functors of the system: F α =df #¬α,
Lα =df # ∨ F α,
M α =df ¬Lα,
whose reading is: “α is false” (F α), “α is meaningful” (Lα) and “α is meaningless” (M α). Two attempts of generalization of Bochvar’s approach onto n-valued case (n > 3) are worth mentioning. The first is due to Rescher [1975], who, rather hastily, transplanted the idea onto the finite and the infinite case. The second, by Finn and Grigolia [1980], stemmed from algebraic description of the Bochvar threevalued logic. Finn and Grigolia employed the algebraic counterparts of Rosser and Turquette’s j — operators as “graded” assertions. 4
LOGIC ALGEBRAS, MATRICES AND STRUCTURALITY
The methodology of propositional calculi and algebraic approach to classical and non-classical logics are highly efficient tools of logical investigation of several prob lems concerning the many-valuedness; cf. [W´ojcicki, 1988; Rasiowa, 1974] and more recent books by Czelakowski [2001] and Dunn and Hardegree [2001]. Our short presentation of the is limited to concepts used further in the Chapter.
Logic algebras A propositional language is viewed as an algebra of formulae L = (F or, F1 , . . . , Fm ), freely generated by the sets of propositional variables V ar = {p, q, r, . . .} and the finitary operations F1 , . . . , Fm on For playing the role of connectives. Accordingly, any interpretation structure A for L is an algebra A = (A, f1 , . . . , fm ). similar to it.8 Furthermore, rightly assumed property of the language’s free gen eration, implies that any mapping s : V ar → A, uniquely extends to the homo morphism hs : L → A, hs ∈ Hom(L, A). 8 See
[Suszko, 1957].
Many-valued Logic and its Philosophy
27
The most employed is the standard language of the classical logic Lk = (F or, ¬, →, ∨, ∧, ≡), with the connectives of negation, implication, disjunction, conjunction and equiv alence. In turn, the two-element algebra of the classical logic has the form A2 = ({0, 1}, ¬, →, ∨, ∧, ≡), here the same symbols ¬, →, ∨, ∧, ≡ as for connectives denote corresponding op erations on the set {0, 1} of “two values” 0 and 1 representing falsity and truth, respectively. A logic algebra is functionally complete when all finitary operations on its uni verse are definable by use of its original operations. That functional completeness is a property of the classical logic was proved by Post [1921]. In terminology just adopted we may equivalently say that the algebra A2 is functionally complete. Where n ≥ 2 is a given natural number, let us put En = {1, 2, . . . , n} and by Un denote any algebra of the form: Un = (En , f1 , . . . , fm ), f1 , . . . , fm being finitary operations on En . Un will be called functionally complete if every finitary mapping f : Enk → En (k ≥ 0, k finite)9 can be represented as a composition of the operations f1 , . . . , fm . Post [1921] reduced the complexity of the problem to small number of connec tives. If we require that for some finite m any k-argument operation on En , where k ≤ m, is definable then Un is functionally complete for m variables. That logical property warrants definability of all at most m-argument connectives. [Post (1921)]. If Un is functionally complete for m variables, where m ≥ 2, then is also functionally complete for m+1 variables and hence also functionally complete. Note that the last theorem reduces the functional completeness of A2 to the definability of all 4 unary and 16 binary connectives. In turn, it is easy to show that the connectives of the standard language define all twenty. Post himself provided several other small collections to do the same and there is also known a “minimalist” reduction of classical connectives to a single one, the so-called Sheffer’s stroke. Getting the functional completeness of n element algebras was another motivation for building many-valued logic. Post was the first to give such an algebra generating two functions: the one-argument cyclic rotation (negation) and the two-argument maximum function (disjunction). In the present notation they look like 1 if x = n x ∨ y = max(x, y). ¬n x = i + 1 if x = i = n 9 The
0-ary operations are constants, i.e. elements of En .
28
Grzegorz Malinowski
Every Post algebra Pn = (En , ¬n , ∨) is functionally complete, Post (1921). Obviously, P2 = (E2 , ¬2 , ∨) is the (¬, ∨) reduct of the algebra A2 . The functional completeness of the n-valued logic algebras is a matter of con sequence since the propositional logics founded on such algebras are logics of all possible extensional n-valued connectives (truth functional when n = 2) and, for every n, they, in a sense, are unique. Since functional completeness is a scarcely frequent property several criteria have been formulated which might help to de termine its presence or not. [S�lupecki (1939a)]. An n-valued algebra Un (n ≥ 0, n finite) is functionally com plete if and only if in Un there are definable: (i) all one-argument operations on En (ii) at least one two-argument operation f (x, y) whose range consists of all values i for 1 ≤ i ≤ n. [Picard (1935)]. Un is functionally complete whenever the functions H, R, S in Section 5 are definable in it. Using S�lupecki’s criterion we may easily establish the functional incomplete ness of all already considered three-valued logics excepting the Post logic. For � ukasiewicz three-valued logic L � 3 it suffices to remark that the one-argument the L constant function T : T x = 1/2 for any x ∈ {0,1/2 , 1} is not definable in terms of the basic connectives. To check that consider any compound function of oneargument and assume that x ∈ {0, 1}, note that due to the tables of the primitive connectives the output value must not be equal 1/2 . On the other hand the same � 3 leads to the func criterion implies that adding T to the stock of functions of L tionally complete logic algebra, S�lupecki [1936]. In the sequel we shall also deal with some known infinite logical constructions. Anticipating possible questions we inform that infinite logic algebras in principle are functionally incomplete. This is due to the fact that the set of possible functions of any algebra of this kind is uncountably infinite, while using a finite number of original operations one may define at most a countable family of functions.
Matrices The classical semantics of truth-valuations distinguishes 1, i.e. the logical value of truth, which corresponds to a specified kind of propositions. In a more general framework, interpretation structures equipped with a distinguished subset of ele ments corresponding to propositions of a specified kind are necessary. These are logical matrices. A pair
Many-valued Logic and its Philosophy
29
M = (A, D), with A being an algebra similar to a language L and D ⊆ A, a subset of A, will be thus referred to as a matrix for L. Elements of D will be called designated (or, distinguished ) elements of M . The set of formulae which take designated values only: E(M ) = {α ∈ F or : hα ∈ D for any h ∈ Hom(L, A)} is called the content of M . The relation |=M ⊆ 2F or × F or is said to be a matrix consequence of M provided that for any X ⊆ F or, α ∈ F or X |=M α if and only if for every h ∈ Hom(L, A)(hα ∈ D whenever hX ⊆ D). The content of a matrix is a counterpart of the set of tautologies and E(M ) = {α : ∅ |=M α}. The entailment |=M is a natural generalization of the classical consequence. In the terminology just adopted, the classical matrix has the form M2 = ({0, 1}, ¬, →, ∨, ∧, ≡, {1}), and the classical consequence relation is characterized as follows: X |=2 α if and only if for every h ∈ Hom(L, A2 ) (hα = 1 if hX ⊆ {1}). Notice that the set of tautologies is the content of M2 and it consists of formulas, which are “consequences” of the empty set, T AU T = E(M2 ) = {α : ∅ |=2 α}. The so-called deduction theorem for the classical logic expressed in terms of |=2 says now that for any set of formulas X and α, β ∈ F or, (ded2 )
X, α |=2 β if and only if X |=2 α → β.
To see how the framework of matrices works for three-valued logic of L � ukasiewicz � 3: let us consider the matrix of L M3 = ({0, 1/2 , 1}, ¬, →, ∨, ∧, ≡, {1}), with the connectives set by the tables in Section 2. The following deduction theorem (ded3 )
X, α |=3 β if and only if X |=3 α → (α → β),
expresses the mutual relation between the consequence and the implication.The left to right direction is essential. To see why the antecedent appears twice it suffices to consider a valuation h, sending all formulas from X into {1} and such that hα = 1/2 , hβ = 0. Accordingly, the classical counterpart of (ded3 ), (ded2 )
X, α |=3 β if and only if X |=3 α → β,
for exactly the same reasons fails.
30
Grzegorz Malinowski
Structural consequence and logics With every |=M there may be uniquely associated an operation CnM : 2For → 2For such that α ∈ CnM (X) if and only if X |=M α. Wherein K is a class (a set) of matrices for a given language L, the relation |=K is to be identified with the set-theoretical meet of {|=M : M ∈ K}. Consequently, CnK = {CnM : M ∈ K} i.e. for any X ⊆ For CnK (X) = {CnM (X) : M ∈ K}. CnM and CnK are special examples of the consequence operations considered in the general theory of deductive systems originated with Tarski (1936). A mapping C : 2For → 2For will be referred to as a consequence operation of the language L if and only if any X, Y ⊆ For (T0) X ⊆ C(X) (T1) C(C(X)) = C(X) (T2) C(X) ⊆ C(Y ) whenever X ⊆ Y . If, moreover, for any substitution e ∈ End(L) (S)
eC(X) ⊆ C(eX),
we shall say that C is structural. It is easy to prove that each matrix consequence operation CnM is structural. Conversely, each structural consequence C of L and any set of formulas X deter mine together a matrix LX = (L, C(X)) called a Lindenbaum matrix. The class of all Lindenbaum matrices of a given consequence C of L, LC = {(L, C(X)) : X ⊆ For} will be referred to as Lindenbaum bundle. Since the substitutions (i.e. endomor phisms) of the language L take the role of valuations one may easily show that any structural consequence operation C is uniquely determined by its Lindenbaum bundle: C = CnLC and ultimately that [W´ ojcicki (1970)] For every structural consequence operation there is a class K of matrices such that C = CnK . An arbitrary consequence C may be conceived as a rule composed of all pairs (X, α) where α ∈ C(X). Rules of the form (∅, α) are called axiomatic and their consequents axioms. A rule R is structural if (X, α) ∈ R implies (eX, eα) ∈ R, any substitution e ∈ End(L). Structural rules may be generated by some “generic”
Many-valued Logic and its Philosophy
31
pairs (X, α), one in particular. Modus Ponens (the Detachment Rule), M P , is a structural rule determined by the single pair: {p → q, p}/q and is represented through the following schema: ϕ → ψ, ϕ / ψ. Let X be a set of formulas and R a set of rules of inference. Then, X is R-closed iff for every α ∈ F or, Y ⊆ X, (Y, α) ∈ R implies α ∈ X. The operation CnR defined for every X ⊆ For by CnR (X) = {Y ⊆ For : X ⊆ Y, Y being R-closed} proves to be a consequence (structural if R is structural). Every R such that C = CnR is referred to as a base of C. In the case when R splits into the set of axiomatic rules RA and non-axiomatic rules RI i.e. R = RA ∪ RI , we may, putting A = {α : (∅, α) ∈ RA }, represent CnR as Cn(A, RI ) where Cn(A, RI ) (X) =
{Y : A ∪ X ⊆ Y and Y is RI -closed}.
A standard way of formalization of propositional logics (L, C) with implication consists in defining C as Cn(A, M P ) or Cn(A, {SU B, M P }) , where SU B is the sub stitution rule, SU B = {ϕ/eϕ : e ∈ End(L)}. In standard cases the implication is supposed to satisfy the Deduction Theorem: β ∈ C(X, α) if and only if α → β ∈ C(X)
(Ded)
Theory of logical matrices is a theory of models of propositional calculi and, from certain point of view, may be treated as a fragment of the algebraic systems theory, see Czelakowski [2001]. 5
POST LOGICS
As an outcome of the research on the classical logic Post [1920; 1921] construed a family of finite-valued propositional systems. The inspirations comprised Principia Mathematica of Whitehead and Russell (1910), the method of truth tables and Post’s own results concerning functional completeness of the classical logic.
Post n-element algebras Following Principia Mathematica Post takes negation (¬) and disjunction (∨) as primitives. For any natural n ≥ 2 a linearly ordered set Pn = {t1 , t2 , . . . , tn }, tn < tj iff i < j, is the set of values. Finally, the operations corresponding to connectives are: unary rotation (or cyclic negation) ¬ and binary disjunction ∨ defined by
32
Grzegorz Malinowski
¬ti =
ti+1 ti
if i = n if i = n
ti ∨ tj = timax {i,j} .
For a given n ≥ 2, these equations define n-element tables of negation and dis junction. Thus, e.g. for n = 5 tables are following:
x t1 t2 t3 t4 t5
¬x t2 t3 t4 t5 t1
∨ t1 t2 t3 t4 t5
t1 t1 t2 t3 t4 t5
t2 t2 t2 t3 t4 t5
t3 t3 t3 t3 t4 t5
t4 t4 t4 t4 t4 t5
t5 t5 t5 t5 t5 t5
It is easy to see that for n = 2 Post logic coincides with the negation-disjunction version of the classical logic: when P2 = {t1 , t2 } is identified with {0, 1}, the Post negation and disjunction are isomorphic variants of the classical connectives.10 The relation to CP C breaks for n > 2. In all these case the table of negation is not compatible with its classical counterpart. To see this remark that due to the disjunction t1 always corresponds to 0 and tn to 1. And, even if ¬tn = t1 , ¬t1 equals t2 and is not tn . Accordingly, the n-valued Post algebra Pn = ({t1 , t2 , . . . , tn }, ¬, ∨) either coincides with the negation-disjunction algebra of CP C(n = 2), or the latter algebra is not a subalgebra of it (n > 2). Post considers the “biggest” value tn as distinguished. Accordingly, among the laws of Post n-valued logics (n > 2) the counterparts of some significant tautologies of the classical logic like the n-valued law of the excluded middle: p ∨ ¬p ∨ ¬¬p ∨ . . . ¬¬ . . . ¬p. (n−1)times
appear. Contrary to that, an application of classical definitional patters of other standard connectives like conjunction, implication and equivalence leads to very strange results. Thus e.g. the definition of conjunction using de Morgan law, α ∧ β = ¬(¬α ∨ ¬β), results in getting the non-associative connective ∧. The source of these unexpected properties is, manifestly, the rotate character of Post negation. 10 It is worth to recall that this set of connectives permits to define all other classical connectives and thus warrants functional completeness of underlying algebra and logic.
Many-valued Logic and its Philosophy
33
The most important property of Post algebras is their functional completeness: by means of the two primitive functions, every finite-argument function on Pn can be defined. In particular, then, also the constant functions and hence the “logical values” t1 , t2 , . . . , tn . Getting functional completeness was one of the prime aims of the author.11
Semantic interpretation The construction, apparently algebraic, was eventually provided with an interest ing semantic interpretation. Post suggests to see the elements of Pn as objects corresponding to (n − 1)-tuples P = (p1 , p2 , . . . , pn−1 ) of ordinary two-valued propositions p1 , p2 , . . . , pn−1 subject to the condition that true propositions are listed before the false. Next, (¬) ¬P if formed by replacing the first false element by its denial, but if there is no false element in P , then all are to be denied, in which case ¬P is a sequence of false propositions. (∨) When P = (p1 , p2 , . . . , pn−1 ) and Q = (q1 , q2 , . . . , qn−1 ), then P ∨ Q = (p1 ∨ q1 , p2 ∨ q2 , . . . , pn−1 ∨ qn−1 ). The mapping i : E n−1 → Pn , of the set of tuples E n−1 onto Pn : i(P ) = ti iff P contains exactly (i − 1) true propositions establishes an isomorphism between (E n−1 , ∨, ¬) and the Post algebra Pn . The ex emplary universe E 4 corresponding to the case of five-valued Post logic, considered before, consists of the following 4-tuples: (0, 0, 0, 0) (1, 0, 0, 0) (1, 1, 0, 0) (1, 1, 1, 0) (1, 1, 1, 1)
t1 t2 t3 t4 t5 .
This interpretation of logic values and its algebra shows, among others, that the values in different Post logics should be understood differently. Post [1921] also defined a family of purely implicative n−valued logics. The family is fairly extensive and it covers implications designed by other authors, e.g. L � ukasiewicz and G¨ odel. The novelty of this proposal was that Post designated many logical values at a time. That possibility, which seems quite natural, was ignored by other originators of many-valued logics. 11 Compare
[Post, 1921] in Ssection 4.
34
Grzegorz Malinowski
The problem of axiomatization The original (¬, ∨) systems of Post’s logic are not axiomatized so far. However, the problem of their axiomatizability has been for years a foregone matter; hence S�lupecki [1939b] has constructed the largest possible class of functionally complete finite logics and gave a general method of their axiomatization. From this it evidently follows that also Post logics are axiomatizable albeit the problem of providing axioms for their original version still remains open. S�lupecki matrix Snk (n being a given natural number, 1 ≤ k ≤ n) is of the form: Snk = ({1, 2, . . . , n}, →, R, S, {1, 2, . . . , k}). where → is a binary (implication), and R, S unary operations defined in the fol lowing way: y if 1 ≤ x ≤ k x→y= , 1 if k < x ≤ n x + 1 if 1 ≤ x ≤ n − 1 R(x) = , 1 if x = n
2 if x = 1
1 if x = 2 S(x) = . x if 3 ≤ x ≤ n Functional completeness12 of each of these matrices results from Picard’s criterion: R and S are two of the Picard’s functions, in order to define the third, it suffices to put: 1 if x = 2 Hx = (x → R(x → x)) → Sx for k = 1, then Hx = 2
x if x = Hx = R(x → x) → x
for k > 1,
then
Hx =
1 if x = k k.
x if x =
S�lupecki produced an effective proof of axiomatizability of E(Snk ) (any pair (n, k) as above) giving a long list of axioms formulated in terms of implication and special one-argument connectives defined through the superpositions of R, S, and H. The chief line of approach here is to make capital of the standard character of implication,13 which can be classically axiomatized, using MP (the Detachment � ukasiewicz’s Rule). S�lupecki extends M P onto the whole language, taking the L formula: ((p → q) → r)) → ((r → p) → (s → p)) as the only axiom for implication and provides an inductive, combinatorial completeness proof. 12 A
finite matrix is functionally complete when its algebra has that property.
Section 7.
13 Compare
Many-valued Logic and its Philosophy
35
Algebraic interpretations The history of algebras corresponding to Post logics was quite different and it even established the current notion of n-valued Post logic. First, Rosenbloom [1942] de fined a Post algebra of order n (n ≥ 2) using the Post rotation (¬) and disjunction (∨) and some other auxiliary functions. Then, the concept has undergone several modifications, see Dwinger [1977]. The most important was the lattice-theoretical characterization by Epstein [1960]. Epstein presented Post algebra of order n as a distributive “chain based” lattice with involution and Boolean-valued endomor phisms. The concept thus presented has been very close to the- Moisil’s n-valued L � ukasiewicz algebra — the main difference is that Post algebras are additionally equipped with the set of constants. The history turned when Rousseau (1969) ob served that any Post algebra of order n is a pseudo-Boolean, or Heyting, algebra (see [Rasiowa, 1974]). Consequently, Rousseau proposed a definition of Post alge bra using a new binary operation of relative pseudo-complement →, a counterpart of an implication. Thus, a Post algebra of order n (n ≥ 2) is a structure (P, 1, →, ∪, ∩, ¬, D1 , D2 , ..., Dn−1 , e0 , e1 , ..., en−1 ) where 1, e0 , e1 , ..., en−1 are zero-argument operations (constants), ¬, D1 , D2 , ..., Dn−1 are one-argument operations and ∪, ∩ are two-argument operations, such that (p0 ) (P, 1, →, ∪, ∩, ¬) is a pseudo-Boolean algebra, see Rasiowa [1974], and for x, y ∈ P , the following equations hold: (p1 ) (p2 ) (p3 ) (p4 ) (p5 ) (p6 ) (p7 ) (p8 )
Dk (x ∪ y) = Dk (x) ∪ Dk (y) Dk (x ∩ y) = Dk (x) ∩ Dk (y) Dk (x → y) = (D1 (x) → D1 (y)) ∩ (D2 (x) → D2 (y)) ∩ ... ∩ (Dk (x) → Dk (y)) Dk (¬x) = ¬D1 (x) Dk (Dj (x)) = Dj (x) Dk (ej ) = 1 if k ≤ j and Dk (ej ) = ¬1 if k > j x = (D1 (x) ∩ e1 ) ∪ (D2 (x) ∩ e2 ) ∪ ... ∪ (Dn−1 (x) ∩ en−1 ) D1 (x) ∪ ¬D1 (x) = 1.
Among them, (p7 ) is of a special importance since it assures uniform monotonic representation of elements of Post algebra of order n in terms of constants and Boolean elements. This, in other terms, means that the algebra based on the chain e0 , e1 , ..., en−1 and that every Post algebra is determined by its Boolean part. The property apparently reflects the original Post’s interpretation of his n logical values. Intense investigation of L � ukasiewicz and Post algebras were motivated by their actual and expected applications, see Section 16. It is worth of mentioning that the redefinition of Post algebras in terms of pseudo-Boolean chain based lattices led to a new definition of n-valued Post logics and their generalization onto infinite cases.
36
Grzegorz Malinowski
6 L � UKASIEWICZ LOGICS In 1922 L � ukasiewicz generalized his three-valued logic and defined the family of � ukasiewicz n-valued matrix many-valued logics, both finite and infinite-valued.14 L has the form Mn = (Ln , ¬, →, ∨, ∧, ≡, {1}), where {0, 1/n−1 , 2/n−1 , . . . , 1} {s/w : 0 ≤ s ≤ w, s, w ∈ N and w = 0} Ln = [0, 1]
if n ∈ N, n ≥ 2 if n = ℵ0 if n = ℵ1 .
and the functions are defined on Ln as follows: ¬x = 1 − x x → y = min(1, 1 − x + y) (ii) x ∨ y = (x → y) → y = max(x, y)
x ∧ y = ¬(¬x ∨ ¬y) = min(x, y)
x ≡ y = (x → y) ∧ (y → x) = 1 − |x − y|. (i)
The introduction of new many-valued logics was not supported by any separate argumentation. L � ukasiewicz merely underlined, that the generalization was correct since for n = 3 one gets exactly the matrix of his 1920 three-valued logic. The � ukasiewicz logics have nice properties, future history will, however, show that L which locate them among the most important logical constructions. First, the L � ukasiewicz matrix M2 coincides with the matrix of the classical logic. � ukasiewicz connectives A2 And, since the set {0, 1} is closed with respect to all L is a subalgebra of any algebra (Ln , ¬, →, ∨, ∧, ≡) and M2 is a submatrix of Mn . � ukasiewicz propositional calculi are included in the Therefore all tautologies of L T AU T : E(Mn ) ⊆ E(M2 ) = T AU T. Next, the relations between the contents of finite matrices are established by the following Lindenbaum condition:15 For finite n, m ∈ N , E(Mn ) ⊆ E(Mm ) iff m − 1 is a divisor of n − 1. The proof of the last property may be based on the “submatrix” properties � ukasiewicz (see above). Using the same of the family of the finite matrices of L argument one may also prove the counterpart of Lindenbaum’s condition. for matrix consequence relations |=n of Mn : For finite n, m ∈ N, |=n ⊆ |=m iff m − 1 is a divisor of n − 1. 14 See 15 See
[�Lukasiewicz, 1970, p. 140].
(�Lukasiewicz and Tarski [1930]).
Many-valued Logic and its Philosophy
37
It may be proved that the infinite L � ukasiewicz matrices have a common content equal to the intersection of the contents of all finite matrices: E(Mℵ0 ) = E(Mℵ1 ) = {E(Mn ) : n ≥ 2, n ∈ N }. L � ukasiewicz n-valued logics L � n are not functionally complete. All what was established for n = 3 applies for each finite n. First, no constant except 0 and 1 is definable in (Ln , ¬, →, ∨, ∧, ≡). Second, adding the constants to the stock of connectives makes this algebra functionally complete. And, since Mn is one generated, either by 1/n−1 or by n−2/n−1 , also adding only one of them do the job as well. McNaughton [1951] proved an ingenious definability criterion, both � ukasiewicz’s logic finite and infinite, which shows the mathematical beauty of L constructions.
Axiomatizability A proof that finite matrices are axiomatizable was given in L � ukasiewicz and Tarski [1930]. However, the problem of formulation of a concrete axiom system fo finite L � ukasiewicz logics for n > 3 remains open till 1952. Rosser and Turquette [1952] are the authors of a general method of axiomatization of n-valued logics with con nectives satisfying the so-called standard conditions. The method can be applied, � n since such connectives are either primitive or definable in among others, to L L � ukasiewicz finite matrices. Hence, for every n an axiomatization of L � ukasiewicz’s n-valued propositional calculus can be obtained. The axiomatization, however, be comes very complicated due to the high generality of the method given by Rosser and Turquette. In [1930] L � ukasiewicz conjectured that his ℵ0 -valued logic was axiomatizable (�Lukasiewicz and Tarski [1930]) and that the axiomatization of the infinite-valued propositional calculus together with M P and SU B was the following: L1. L2. L3. L4. L5.
p → (q → p) (p → q) → ((q → r) → (p → r)) ((p → q) → q) → ((q → p) → p) (¬p → ¬q) → (q → p) ((p → q) → (q → p)) → (q → p).
Due to L � ukasiewicz16 this hypothesis was confirmed by Wajsberg in [1931]. Next comes the reduction of the axiom set: Meredith [1958] and Chang [1958a] independently showed that axiom L5 is dependent on the others. There are two main accessible completeness proofs of L1–L4 (with M P and SU B): based on syntactic methods and linear inequalities by Rose and Rosser [1958], and purely algebraic — by Chang [1959]. Chang’s proof is based on properties of M V algebras, algebraic counterparts � ukasiewicz logic, defined and studied in Chang [1958b].17 of the infinite-valued L 16 L � ukasiewicz 17 MV
[1970, p. 144]; no publication on the topic by Wajsberg exists.
algebras are presented in the sequel.
38
Grzegorz Malinowski
The key role in the approach have additional binary connectives + and ·. The two connectives directly correspond to the main algebraic operations of M V algebras are defined by α + β =df ¬α → β and α · β =df ¬(α → ¬β). Several axiomatizations for finite-valued L � ukasiewicz logics (n > 3) were ob tained by way of extension of the axiom system L1–L4. Grigolia [1977] employs multiplying use of the connectives + and ·. Let kα will be a replacement of the formula α + α + ... + α (k times) and αk a replacement of the formula α · α · ... · α (k times). Given a finite n > 3, Grigolia’s axiom system for L � n consists of the schemes of L1–L4 and Ln 5. Ln 6.
nα → (n − 1)α (n − 1)((¬α)j + (α · (j − 1)α)),
where 1 < j < n − 1 and j does not divide n − 1. Tokarz [1974] extension of L1–L4 is based on the characteristic functions of the set Ln in [0, 1] and the properties of the consequence relation of Mℵ0 . The axiom � ukasiewicz logic, including n = 2 (i.e. CP C), results set for a given n-valued L from L1–L4 by adding a single special “disjunctive” axiom p ∨ ¬p ∨ δn1 (p) ∨ . . . ∨ δnn−2 (p), where, for any k, 1 ≤ k ≤ n − 1, the corresponding algebraic operation δnk (x) is � ukasiewicz the “characteristic function” of the logical value k/n−1 in the infinite L matrix Mℵ0 . Another axiomatization of finite L � ukasiewicz logics, offered by Tuziak (1988), is formulated in the standard propositional language, using the sequences of ascend ing implications defined inductively by: p →0 q = q, p →k+1 q = p → (p →k q). The axiom set for n-valued L � ukasiewicz logic consists of ten formulas taken from the Hilbert-Bernays axiomatization of CP C and the following two “specific” ax ioms: T1.
(p →n q) → (p →n−1 q)
T2.
(p ≡ (p →s−2 ¬p)) →n−1 p for any 2 ≤ s ≤ n − 1 such that s is not a divisor of n − 1.
Algebraic interpretations The first attempts to obtain algebras corresponding to finite L � ukasiewicz logics, due to Moisil, are dated back to the 1940’s.18 Moisil algebras are bounded dis tributive lattices with involution and Boolean-valued endomorphisms. A structure 18 See
Moisil [1972].
Many-valued Logic and its Philosophy
39
(A, ∪, ∩, N, s1 , s2 , ..., sn−1 , 0, 1) is an n-valued L � ukasiewicz algebra19 provided that M1. (A, ∪, ∩) is a distributive lattice with 0 and 1. M2. N is an involution of A, i.e. N N x = x, and N (x ∪ y) = N (x) ∩ N (y), N (x ∩ y) = N (x) ∪ N (y). M3. sk ’s are endomorphisms of (A, ∪, ∩), i.e. for any k ∈ {1, 2, ..., n − 1}: sk (x ∪ y) = sk(x) ∪ sk (y) and sk (x ∩ y) = sk (x) ∩ sk (y), such that (i)
sk (x) ≤ sk+1 (x)
(ii) sk (st (x)) = st (x) (iii) sk (N (x)) = N sn−k (x) (iv) N sk (x) ∪ sk (x) = 1, N sk (x) ∩ sk (x) = 0 (v) If sk (x)) = sk (y) for every k, then x = y. The simplest finite n-valued L � ukasiewicz algebra is the linearly ordered algebra � ukasiewicz matrix of n-valued L (Ln , ∨, ∧, ¬, s1 , s2 , ..., sn−1 , 0, 1), with the one-argument functions s1 , s2 , ..., sn−1 defined by: 0 when 1 ≤ k ≤ n − j − 1
sk (j/n−1 ) = 1 when n − j − 1 < k ≤ n − 1.
The definability of sk functions is warranted by the McNaughton test; the “effec tive” definitions using L � ukasiewicz ¬ and → were given by Sucho´ n [1974]. Since for n ≥ 5, the L � ukasiewicz implication was not definable in n-valued Moisil algebras, Cignoli [1980] enlarged the set of basic operations with additional binary operators satisfying some simple equations. The resulting structures, called proper n-valued L � ukasiewicz algebras, proved to be real counterparts of L � ukasiewicz finite-valued logics, see Cignoli [1982]. In view of getting algebraic completeness proof of the infinite-valued L � ukasiewicz logic Chang [1958b] introduced the concept of M V algebra. An algebra A = (A, +, ·, −, 0, 1), where + and · are binary operations, − is a unary operation, 0 = 1, and ∪ and ∩ are binary operations defined by 19 Moisil
used this name.
40
Grzegorz Malinowski
x ∪ y = x : y− + y
x ∩ y = (x + y − ) : y
is an M V algebra if the following conditions are satisfied: C1. C2. C3. C4. C5. C6. C7. C9. C10. C11.
x+y =y+x x + (y + z) = (x + y) + z x + x− = 1 x+1=1 x+0=x (x + y)− = x− · y − (x− )− = x x∪y =y∪x x ∪ (y ∪ z) = (x ∪ y) ∪ z x + (y ∩ z) = (x + y) ∩ (x + z)
C1∗. C2∗. C3∗. C4∗. C5∗. C6∗. C8. C9∗. C10∗. C11∗.
x·y =y·x x · (y · z) = (x · y) · z x · x− = 0 x·0=0 x·1=x (x · y)− = x− + y − 0− = 1 x∩y =y∩x x ∩ (y ∩ z) = (x ∩ y) ∩ z x · (y ∪ z) = (x · y) ∪ (x · z).
The simplest example of the M V algebra is an arbitrary L � ukasiewicz matrix, the operations + and · are defined as above and ∪, ∩, − are the connectives of disjunction, conjunction and negation, respectively. An adaptation of M V � ukasiewicz logics was made in 1973 by R. Grigolia. An M V algebras to finite L algebra A is an M Vn algebra (n ≥ 2) provided that it satisfies additionally C12.
(n − 1)x + x = (n − 1)x
C12∗.
xn−1 · x = xn−1
and for n > 3: C13. C13∗.
{(jx) · (x− + ((j − 1)x)− )}n−1 = 0 (n − 1){xj + (x− · (xj−1 )− )} = 1
where 1 < j < n − 1 and j does not divide n − 1, see Grigolia (1977). All above algebras are conservative generalizations of Boolean algebras. Every Moisil algebra and every M V algebra has a Boolean subalgebra. {sk (x) : x ∈ A, � ukasiewicz algebra. 1 ≤ k ≤ n} is the set of all Boolean elements of a n-valued L The set {x ∈ A : x + x = x} = {x ∈ A : x · x = x} is the set of Boolean elements of an M V algebra A. Moisil and Chang developed representation theory of their algebras. Chang’s idea of associating to any M V algebra a totally ordered abelian � ukasiewicz group was the crucial point of the algebraic completeness proof of L axioms for infinte-valued logic, see Chang [1959].20 A group-theoretic flavour of M V algebras and their other mathematical prop erties attracted attention of many scholars. Several algebraic structures related to the original Chang’s algebras have been investigated and applied to logic. Among recent works it would be worth to note two new proofs of the completeness of L � ukasiewicz axioms: by Cignoli [1993], using the representation of free l-groups and by Panti [1995], using tools of the algebraic geometry. Cignoli et al. [1999] is 20 The original proof for the infinite case is non-constructive. Mundici [1994] gave a constructive proof of it.
Many-valued Logic and its Philosophy
41
a good source of results and studies of infinite-valued L � ukasiewicz logic and MV algebras.
7 STANDARD AXIOMATIZATION The problem of Hilbert-style axiomatization of many-valued logics rested open still many years after the inventory constructions. The 1930s brought mere syntactic characterizations of some systems of three-valued logic including Wajsberg’s ax � ukasiewicz logic, see L � ukasiewicz [1930]. In their iomatization of the three-valued L seminal analysis Rosser and Turquette [1952] set the conditions that make finitely many-valued logics resemble to the CP C and hence simplify the problem of the syntactic formalization.
Standard conditions The first semantical steps of the analysis resolve the principle of interpretation of propositional languages in matrices of the form Mn,k = (Un , Dk ), where Un = (En , f1 , . . . , fm ), En = {1, 2, . . . , n}, Dk = {1, 2, . . . , k}, n ≥ 2 is a natural number and 1 ≤ k < n. The authors assume that the natural number ordering conveys decreasing degree of truth. So, 1 always refers to “truth” and n takes the role of falsity. Next come the conditions concerning propositional connectives, which in Mn,k have to represent negation (¬), implication (→), disjunction (∨), conjunction (∧), equivalence (≡) and special one-argument connectives j1 , . . . , jn . Assume that the same symbols are used to denote the corresponding functions of Un and that a given Mn,k is the interpretation structure. Then we say that the respective connectives satisfy the standard conditions if for any x, y ∈ En and i ∈ {1, 2, . . . , n} ¬x ∈ Dk x → y ∈ Dk x ∨ y ∈ Dk x ∧ y ∈ Dk x ≡ y ∈ Dk ji (x) ∈ Dk
if if if if if if
and and and and and and
only only only only only only
if if if if if if
x ∈ Dk x ∈ Dk and y ∈ Dk x ∈ Dk or y ∈ Dk x ∈ Dk and y ∈ Dk either x, y ∈ Dk or x, y ∈ Dk x = i.
Any matrix Mn,k having standard connectives as primitive or definable is called standard. When only some of them are present we will use the term “Q-standard”, where Q is a subset of the set of all standard connectives. All Post and all finite L � ukasiewicz matrices are standard. The first case is easy. Post matrices are based on functionally complete algebras, see Section 5, and thus any possible connective is definable. A given n-valued L � ukasiewicz matrix may be
42
Grzegorz Malinowski
isomorphically transformed onto a matrix of the form Mn,1 : the isomorphism is es tablished by the mapping f (x) = n−(n−1) of the set {0,1/n−1 ,2/n−1 , . . . ,n−2 /n−1 , 1} onto {1, 2, . . . , n}. Notice that the mapping inverses the ordering. Accordingly, now the smallest element 1 is the designated value, whereas n corresponds to 0. A moment’s reflection shows that original L � ukasiewicz disjunction and conjunction satisfy standard conditions. In turn, the other required connectives are definable in Mn . Thus, x ⇒ y =df x → (x → . . . → (x → y)),
x ≈ y =df (x ⇒ y) ∧ (y ⇒ x)
(n−1)times
define the standard implication and equivalence (→ appearing on the right is the original L � ukasiewicz connective). The definability of js, ji (x) = 1 iff x = i follows easily from the McNaugthon criterion; see also Rosser and Turquette [1952]. Rosser and Turquette positively solved the problem of axiomatizability of known � ukasiewicz and Post logics. systems of many-valued logic, including n-valued L Actually, any logic determined by a {→, j1 , j2 , . . . , jn } — standard matrix Mn,k is axiomatizable by means of the rule M P and SU B and the following set of axioms: A1. A2. A3. A4. A5. A6. A7.
(α → (β → α)) (α → (β → γ)) → (β → (α → γ)) (α → β) → ((β → γ) → (α → γ)) (ji (α) → (ji (α) → β)) → (ji (α) → β) (jn (α) → β) → ((jn−1 (α) → β) → (. . . → ((j1 (α) → β) → β) . . .)) ji (α) → α for i = 1, 2, . . . , k ji(r) (αr ) → (ji(r−1) (αr−1 ) → (. . . → (ji(1) (α1 ) → jf (F (α1 , . . . , αr ))) . . .)) where f = f (i(1), . . . , i(r));
symbols f and F used in A7 represent, respectively, an arbitrary function of the matrix Mn,k and a propositional connective associated with it; Rosser and Tur quette [1952]. The axiom system A1–A7 consists of two parts. The first part, A1–A3, de scribes the properties of pure classical implication: in particular, due to them the deduction theorem (ded2 ) holds, cf. Section 4. The axioms of the second group, (A4)–(A7), bridge the semantic and syntactic properties of connectives. Check ing the soundness of the axioms is easy and it heavily bases on the procedures known from the classical logic. The completeness proof, however, requires much calculation quite a complicated induction. Rosser and Turquette’s approach to many-valued logics weights heavily on fur ther research of the topic. Especially, it yields that the two-valued logic is, to some degree, sufficient for the developments of many-valued logic. In turn, an expansion of techniques of the classical logic by the authors suggested further formalizations of the both, finite and infinite-valued logics. One example is the partial normal forms’ representation of formulas of a given finite-valued standard logic, mainly used in Many-valued logics for developing the quantification theory.
Many-valued Logic and its Philosophy
43
Partial normal forms The r-th (1 ≤ r ≤ n) partial normal form of a formula is a specification in terms of two-valued logic of the conditions under which the given formula takes the truth value r. To built this form we need any standard disjunction and conjunction con nectives and js. The r-th partial normal form Nr (α) of a formula α = α(p1 , . . . , ps ) is the disjunction of all conjunctions of the form: j1r (p1 ) ∧ j2r (p2 ) ∧ . . . ∧ jsr (ps ), where 1r , 2r , . . . , sr is a sequence of logical values such that v(α) = r for any valuation v meeting the requirement: v(pi ) = ir . The “specification” may also be considered as a formula of an external language comprising the connectives of the classical connectives of negation, disjunction and conjunction. Rosser and Turquette used the disjunctive-conjunctive forms, but extending the notions onto the conjunctive-disjunctive forms is immediate. Consider e.g. the simple three-valued L � ukasiewicz implication p → q, which in the notation just adopted has the following truth table: → 1 2 3
1 1 1 1
2 2 1 1
3 3 2 1
Let the superscript 1, 2 or 3 by a propositional variable denote that it takes a respective value. Thus e.g. p1 reads “p takes the value 1”, p2 reads “p takes the value 2”, and p3 reads “p takes the value 3”.Then the first partial normal form of p → q is the DC formula: q 1 ∨ (q 2 ∧ p2 ) ∨ (q 2 ∧ p3 ) ∨ (q 3 ∧ p3 ), its second partial normal form: (q 2 ∧ p1 ) ∨ (q 3 ∧ p2 ) and, finally, the third partial normal form of p → q is: q 3 ∧ p1 . So, the complete set of the above partial normal forms of formula is an equivalent to its truth table. Obviously, such a description of properties of formulas is external with respect to the system.21 It is interesting to note that in some cases the connectives are definable in standard logics to do the same effect. The next step is to ask for further classical connectives, including negation and implication. That 21 Such
was the approach by Bochvar, see Section 5.
44
Grzegorz Malinowski
question and possible consequences of a positive answer to it will be discussed later. The fact that the partial normal form’s method extends onto quantifiers opens an important door. First, an adaptation of the method to the first-order language led Rosser and Turquette to a formalization to a class of many-valued predicate calculi. On the other hand, the tool proved to be useful in investigation of natural deduction formalisations of finite-valued logics. An appropriate generalisation of the notion of normal form enables to construct rules of the sequent and tableaux systems directly from the finite element truth tables of their connectives. More over, as Zach [1993] explains, the partial normal forms provide a relationship between clause translation rules, sequent calculus introduction rule, and a natural deduction rule for a given connective. Many-valued logics as constructed through matrices are extensional with respect to their values. This property of the bunch of connectives may be identified as a generalized multiple-valued truth-functionality.
8
BACKGROUND TO PROOF THEORY
The studies of formal proofs, inaugurated by Gentzen [1934], now form a steady branch of logical investigations. Gentzen’s sequents and natural deduction22 for the classical and intuitionistic logic have been adapted soon to other non-classical systems, including the finite many-valued propositional and predicate calculi.
Sequents A sequent is an item of the form Γ ⇒ ∆, where Γ and ∆ are finite sequences, or multisets, of formulas. The sequent means that the conjunction of all formulas of Γ entails the disjunction of all formulas of ∆, in symbols ∧Γ ∨∆. In the classical case, the entailment, due to the deduction theorem, is equivalent to ∧Γ ⇒ ∨∆. Accordingly, the sequent receives a truth-functional interpretation: for any valuation, if all the formulas in Γ are true, then at least one formula in ∆ is not false. A version of the calculus using only sequents having a single formula in the place of ∆ was also used by Gentzen to formalize intuitionistic logic. In oter [1955] provided a direct generalisation of the classical sequent the end, Schr¨ approach onto the many-valued case. A natural, truth-functional approach to sequent formalisation of finite manyvalued logics is due to Rousseau [1967].23 Given a finite n ≥ 2, n-valued sequent Γ is an n-tuple Γ1 | Γ 2 | . . . | Γ n 22 Independently, Ja´ skowski [1934] presented a handy natural deduction system for the classical, intuitionistic and some version of free logic. 23 Takahashi [1967; 1970] gave a similar formalisation, see e.g. Bolc and Borowik [2003].
Many-valued Logic and its Philosophy
45
of finite sequences of formulas. Then, Γ is interpreted as true under a given interpretation if and only if at least one Γi , i ∈ {1, 2, . . . , n} has a formula, which takes the value i. Thus, the components Γ1 , Γ2 , . . . , Γn of Γ correspond to logical values of a logic under consideration. It is obvious that for n = 2 one gets the counterpart of the standard notion of a sequent Γ1 | Γ2 with the usual truth-falsity interpretation. The base of the construction of finite-valued sequent calculus is the expression of the n-valued truth-functionality by assumption that for any formula α, the sequent α | α | ... | α is an axiom. Next to that, there are the weakening rules for every place i, Γ1 | . . . | Γi | . . . | Γn Γ 1 | . . . | Γi , α | . . . | Γn and (i, j) cut rules Γ 1 | . . . | Γi , α | . . . | Γn ∆1 | . . . | ∆j , α | . . . | ∆n Γ1 , ∆1 | . . . | Γn , ∆n for every i = j, i, j ∈ 1, 2, . . . , n. The last and the hardest step consists in stating the admissible introduction rules for the connectives and, later,24 for quantifiers. Any F -introduction rule at the position i for a connective F of (finite) arity r, has the following form: Γ11 , ∆11 | . . . | Γ1n , ∆1n . . . Γj1 , ∆j1 | . . . | Γjn , ∆jn , Γ1 | . . . | Γi , F (α1 , . . . , αr ) | . . . | Γn where Γ1 = Γ11 ∪ . . . ∪ Γj1 , . . . , Γn = Γ1n ∪ . . . ∪ Γjn and, ∆1n , . . . , ∆jn are subsets of {α1 , . . . , αr }. To get an exhausting description of the connective in the sequents setting, one has to establish the rules for all positions, i.e. the original values of the logic. That may be done using conjunctive-disjunctive partial normal forms. However, a formula of a given many-valued logic may have several specific partial CD forms. This implies that the result of establishing the rules is not unique. Once, we have such a description for the connective, we may write the introduction rules of it, taking as the premises the set of sequents reflecting disjuncts, which have positioned the components at the corresponding places. To give an example, we stay with the L � ukasiewicz three-valued implication con sidered in Section 2 expressed as in Section 7. One may verify, that the following formulas are the CD partial normal forms of p → q: 24 See
Section 9.
46
Grzegorz Malinowski
(p3 ∨ p2 ∨ q 1 ) ∧ (p3 ∨ q 2 ∨ q 1 ) (p2 ∨ p1 ) ∧ (p2 ∨ q 2 ) ∧ (p1 ∨ q 3 ) p1 ∧ q 3
(the first; value 1) (the second; value 2) (the third; value 3).
Accordingly, we get the following three introduction rules for the L � ukasiewicz implication: Γ1 , q | Γ 2 , p | Γ3 , p Γ 1 , q | Γ 2 , q | Γ 3 , p Γ1 , p → q | Γ2 | Γ3 Γ1 , p | Γ 2 , p | Γ 3
(I →; 1)
Γ1 | Γ2 , p, q | Γ3 Γ1 , p | Γ2 | Γ3 , q Γ1 | Γ2 , p → q | Γ3
Γ1 , p | Γ 2 | Γ 3 Γ 1 | Γ 2 | Γ 3 , q Γ 1 | Γ2 | Γ3 , p → q
(I →; 2)
(I →; 3).
These rules, together with the rules for the negation connective on the set {1, 2, 3} assure a sequent formalisation of the three-valued propositional L � ukasiewicz logic. To finish with, we remark that the following introduction rules follow di rectly from the table of negation: Γ1 , p | Γ2 | Γ3 Γ1 | Γ2 | Γ3 , ¬p
Γ 1 | Γ2 , p | Γ3 Γ1 | Γ2 , ¬p | Γ3
Γ1 | Γ2 | Γ3 , p . Γ1 , ¬p | Γ2 | Γ3
Tableaux method The tableaux method raised by Beth [1955] is a refutation procedure, which proved to be useful not only as the proof procedure but also as a model search device. Beth was motivated by semantic concerns, what found its expression in the early terminology, when the most proper way of speaking about the procedure referred to it as to semantic tableaux, cf. Smullyan [1968]. The core of the method is putting a question on whether a given formula is valid or not or, equivalently, whether it is falsifiable. To show that a formula α is valid one begins with some expression intended to assert that α is not valid. Due to the already established tradition the “expression” is composed of a sign displaying the polarisation — the assertion of the truth or falsity — and a current formula, for the classical logic the most popular are two sets of signs: {T, F } and {+, −}, then the signed formulas are: T α, F α and +α, −α, respectively. Next, a set of elimination rules reducing signed formulas to simpler signed formulas, is given. In general, the procedure branches and at its final stage further productive application of the rules is impossible. A branch is closed if it contains two opposite signed formulas, i.e. T α, F α (or +α, −α), otherwise the branch is open. The former outcome locally denies the starting assumption on non validity — the integral deny is when all branches are closed, the latter gives a hint how to built a falsifying model. In case of classical logic there is a straightforward duality between the tableaux and sequents: any sequent system without cut may be reversed into the tableaux: the
Many-valued Logic and its Philosophy
47
elimination rules result as reversing the introduction rules for sequents, see e.g. D’Agostino [1999]. The signed tableaux systems for finitely many-valued logics were first given by Sucho´ n [1974] and Surma [1974]. The both authors presented their systems for � ukasiewicz propositional logics using the modal operators of the finite n-valued L Moisil algebras25 to play the role of signs. Further elaboration of the method is due to Surma [1984]. Carnielli [1987; 1991] developed the idea and established a “systematisation of finite many-valued logics through the method of tableaux”.26 Since some time, the research is dominated with issues concerning the automation. One of recently important issues is using sets of signs instead signs, see H¨ahnle [1993] as well as as specified versions of sequents with meta connectives, H¨ahnle [1999]. Early approaches to many-valued tableaux systems resemble the sequents of Rousseau. However, contrary to the sequential calculi, which are grounded on the introduction rules, the tableaux use elimination rules. In particular approaches the signs are either simulated by the connectives definable within the logic, they are possibly the values of the logical matrix or the elements of an external struc ture. The sequential format for tableaux is particularly useful and in eligible cases the tableaux rules of elimination may be received as reverse of the introduction � ukasiewicz connectives of negation and rules. Thus, e.g. for the three-valued L implication, one may have the following rules: Γ1 , p → q | Γ2 | Γ3 Γ 1 , q | Γ2 , p | Γ3 , p Γ1 , q | Γ2 , q | Γ3 , p Γ 1 , p | Γ2 , p | Γ3
Γ1 | Γ2 , p → q | Γ3 Γ1 | Γ2 , p, q | Γ3
(→ E; 1)
Γ 1 , p | Γ2 | Γ3 , q
Γ1 | Γ2 | Γ3 , p → q Γ 1 , p | Γ2 | Γ3 Γ 1 | Γ2 | Γ3 , q
(→ E; 2)
(→ E; 3).
Further to that other elimination rules may be established, using appropriately the partial normal forms. It should be said, however, that — in general — the partial normal forms are not unique, and due to that property one may get different sets of elimination rules for a given connective. See Baaz et al. [1993].
Natural deduction and resolution Resolution is still among the main tools of Automated Reasoning. Recently, also the natural deduction becomes more and more acknowledged device in that con text. The both, natural deduction and the resolution, are relatives of sequents 25 See
Section 6. is the title of the first Carnielli’s paper. It should be added that the characterisation was also extended onto quantifiers. 26 This
48
Grzegorz Malinowski
and, to a certain degree, are sequent expressible.27 Below, we shortly comment on them. The method of natural deduction is a special formalization, which establishes relations between premises and a set of conclusions. It operates with both kind of rules for all logical constants: rules of introduction and rules of elimination. Moreover, the set of conclusions may, in particular cases, consist of one formula. The history of natural deduction approach to many-valued logics is not very long. Probably the first paper on the topic is Becchio and Pabion [1977], who gave � ukasiewicz logic. Essentially a system of natural deduction for the three-valued L new systems using sequents are discussed in Baaz et al. [1993] and Zach [1993]. The common feature of all systems of this kind is the property of conserving some logical values. Obviously, the most popular option is to save one logical value corresponding to the truth. On the other hand, the choice of many logic values at once, or a subset of the set of all values, of the logic at work, is also worth consideration. Resolution is a refutation method organized on clauses i.e finite disjunctions of literals. A literal is a propositional variable (positive literal) or the negation of a propositional variable (negative literal). The procedure starts with a set of clauses and the refutation ends with an empty clause. It operates with a single resolution rule, which is a form of the cut rule. The earliest articles on resolution in many-valued logics are due to Or�lowska [1967] and Morgan [1976]. The pioneering works and their ancestrals have been based on special normal forms with multiple-valued literals, which used special unary connectives. The most recent outcome of investigation is an algebraic the ory of resolution proof deductive proof systems developed by Stachniak [1996]. The key idea on which the theory is based is that the refutational deductive proof systems based on a non-clausal resolution become finite algebraic structures, the so-called resolution algebras. In turn, the particular interpretation of the resolution principle shows it as the rule of consistency verification defined relative to an ap propriate propositional logic. The verification uses special formulas, the so-called verifiers “witnessing” the consistency of sets of formulas. In the classical case verifiers coincide with the formulas defining two standard truth values. The pro cess of selecting verifiers for resolution counterparts of non-classical proof systems usually goes beyond the search for defining truth values. Thus, e.g. the resolution counterparts of three-valued and five-valued L � ukasiewicz logics have, respectively, six and nine verifiers.28 What makes the last approach specially interesting from the point of view of many-valuedness is that the interpretation of the resolution � ukasiewicz, Tarski as principle is rooted in the logical tradition of Le´sniewski, L well as Couturat, Post and Schr¨ oder.29 Accordingly, it seems very interesting that in the counterparts of functionally complete systems of (finite) many-valued logic verifiers coincide with formulas defining logical values. 27 Consult
D’Agostino [1999].
[1996, pp. 181 and 187].
29 See Stachniak [1996, p. xii].
28 Stachniak
Many-valued Logic and its Philosophy
49
9 QUANTIFIERS IN MANY-VALUED LOGIC Rosser and Turquette [1952] extended the method of partial normal forms onto formulas with quantifiers and developed a general theory of quantification for a class of finitely many-valued logics.
Ordinary and generalized quantifiers They started from the intuition permitting to treat ordinary quantifiers as func tions on the set of pairs (x, F ), where x is a nominal variable and F a formula, with values in the set of formulae. A generalized quantifier of this type is any formula of the form: Q(x1 , x2 , ..., xm , F1 , F2 , ..., Ft ), where x1 , x2 , ..., xm are nominal variables and F1 , F2 , ..., Ft formulae built from predicates, nominal and propositional variables, and connectives. The intended meaning of Qi functions in n-valued logic is determined with the help of inter pretations assigning to formulae values from the set {1, 2, ..., n}. Operating on the links between formulae stated by means of connectives of basic logic enables the construction of non-classical quantifiers. The theory of representations al lows any generalized quantifier to be expressed by means of ordinary quantifiers. Standard n-valued predicate calculi with generalized quantifiers are axiomatizable using special “partial normal forms”. Many-valued predicate calculi are, however, usually built along the classical pattern. In that case a first-order language with two standard quantifiers: general ∀ and existential ∃ is considered. In general, the starting point is the substitutional conception of quantifiers according to which ∀ and ∃ are (infinite) generalizations of conjunction and disjunction, respectively. Accordingly, for a finite domain U = {a1 , a2 , ..., an }, the commutative and associative connectives of conjunction (∧) and disjunction (∨): ∀xF (x) ≡U F (a1 ) ∧ F (a2 ) ∧ ... ∧ F (an ) ∃xF (x) ≡U F (a1 ) ∨ F (a2 ) ∨ ... ∨ F (an ), (≡U means the equivalence of the formulae at any interpretation in U, a1 , a2 , ..., an being nominal constants ascribed to the objects of the domain). In finite-valued logical calculi constructed upon linear matrices, quantifiers are defined ‘directly’ through algebraic functions related the above-mentioned connectives. Thus, e.g. � ukasiewicz and Post logics, for any interpretation f in a domain U for finite L f (∀xF (x)) = min{f (F (a)) : a ∈ U } f (∃xF (x)) = max{f (F (a)) : a ∈ U }. For other calculi semantic description of quantifiers may vary. Thus, for example, the clauses defining quantifiers in the first-order Bochvar logic should be following:
50
Grzegorz Malinowski
t u f (∀xF (x)) = f f u f (∃xF (x)) = t
when f (F (a)) = t for every a ∈ U when f (F (a)) = u for some a ∈ U otherwise when f (F (a)) = f for every a ∈ U when f (F (a)) = u for some a ∈ U otherwise.
Axiomatic systems of many-valued predicate logics are extensions of axiom sys tems of the ground propositional calculi in the similar way as for the classical logic, cf. Rasiowa and Sikorski [1963] and Rasiowa [1974]. Proofs of completeness for for finitely-valued calculi do not, in general, create difficulties. Eventually, the axiomatizability of several calculi of this kind may be assured by the Rosser and Turquette’s method extending the standard approach to quantifiers, see above.
Distribution quantifiers Attempts to adopt the matrix method for the first order finite-valued logics led to the concept of distribution quantifiers. The semantics of any such operator is defined with mapping from distributions to truth values: their “matrix” counter parts are functions from sets of logical values to logical values. The very idea has been covered by a general framework of Mostowski [1957] and for the finite-valued logics was developed by Carnielli [1987; 1991]. An advantage of the distribution approach is that an appropriate description of a quantifier directly yields the elim ination rule for the corresponding tableau proof system. Thus, for example for the three-valued L � ukasiewicz logic presented as in Section 7, the standard quantifiers ∀ and ∃ may be defined in terms of distribution in the following way: 3 if 3 ∈ X 2 if 2 ∈ X and 3 ∈ X d∀ (X) = 1 if X = {1}, 3 if X = {3} 2 if 2 ∈ X and 1 ∈ X d∃ (X) = 1 if 1 ∈ X. 1 −1 The counter images of the two functions, d− ∀ and d∃ would be perhaps more displaying:
d−1 ∀ (3) = {{3}, {2, 3}, {1, 2, 3}, {1, 3}} 1 d− ∀ (2) = {{2}, {1, 2}} −1 d∀ (1) = {{1}}
d−1 ∃ (3) = {{3}} 1 d− ∃ (2) = {{2}, {2, 3}}
−1 d∃ (1) = {{1}, {1, 2}, {1, 2, 3}, {1, 3}}.
From the last description the tableaux elimination rules stem directly. Some ex amples will follow:
Many-valued Logic and its Philosophy
1∀xF (x) , t is any term; 1F (t)
2∀xF (x) , c1 , c2 , c3 are new constants. 2F (c1 ) 1F (c2 ) 2F (c3 )
3∃xF (x) , t is any term; 3F (t)
2∃xF (x) , c1 , c2 , c3 are new constants. 2F (c1 ) 2F (c2 ) 3F (c3 )
51
Quantifiers and infinite-valued logic Introducing quantifiers to logics with infinitely many values in the semantical plane may be problematic. Thus, e.g. applying the before mentioned procedure to the � ukasiewicz logic is impossible since in the case when U is infinite it may ℵ0 -valued L happen that the set {f (F (a)) : a ∈ U } does not contain the least or the greatest element and therefore min and max functions cannot be used in the definition. In � ukasiewicz logic, the interpretations of quantifiers are turn, in the the ℵ1 -valued L introduced provided that for any interpretation in a non-empty domain U f (∀xF (x)) = inf {f (F (a)) : a ∈ U } f (∃xF (x)) = sup{f (F (a)) : a ∈ U }, see Mostowski [1961]. However, it appeared that ℵ1 -valued predicate calculus thus obtained is not axiomatizable, Scarpelini [1962]. The investigations of other scholars complete, to some extent, the Scarpelini’s result characterizing sets of valid formulas30 in terms of recursive countability RC:31 Rutledge [1959] showed that the set of valid formulas of ℵ1 -valued monadic predicate calculus is RC. Hay [1963] proved that for any valid formula α of this calculus there exists a finite m > 0 such that mα is derivable from some “sound” axiomatics. Finally, a general result � ukasiewicz’s matrix of Mostowski [1961] implies that the set of formulas valid in L with the designated set (r, 1], 0 < r ≤ 1, is axiomatizable — the proof of Mostowski is not effective and the author provides no axiomatics. The adduced works allow, as we think, to estimate the complexity and subtlety of the problem. In this connection it is also worthwhile mentioning that the greatest hopes for proving completeness of ℵ1 -valued predicate calculus were combined with the algebraic method and MV algebras (see Section 6 and Belluce and Chang [1963]). The experience gathered while attempting to constitute such a proof finally yielded in the form of interpretation theory of the first-order language with values in compact Hausdorff spaces, the so-called continuous model theory in Chang and Keisler [1966]. 30 I.e. 31 See
formulas true at any interpretation.
e.g. [Kleene, 1952].
52
Grzegorz Malinowski
10
¨ INTUITIONISM AND GODEL’S MATRICES
Intuitionism constitutes a constructivistic trend in the studies of the foundations of mathematics. Its sources are found in some elements of the philosophy of Kant who perceived the base of mathematics in an a priori intuition of time and space and who emphasized the role of construction in justifying the existence of mathematical objects. The history of the intuitionistic conception is excessively rich and has links with so eminent mathematicians as L. Kronecker, H. Poincar´e, E. Borel, H. Lebesgue to mention only few of them. The systematic and mature development of the intuitionistic ideas initiated in 1907 is a life-work of L. E. J.Brouwer (see [Heyting, 1966]).
Postulates and axioms One of the main assumptions of intuitionism is the postulate of effectiveness of ex istential mathematical theorems: a proposition concerning the existence of math ematical objects can be accepted only when we are able to provide a method of construction of those objects. Proposed by Heyting [1930] the interpretation of logical constants and quantifiers allowed to formulate an axiomatization of intu itionistic logic generally acknowledged as adequate. According to this interpreta tion the validity of any proposition is identified with its provability, and proofs of compound propositions are composed of the proofs of simpler ones. Proof of
is a construction
α∧β α∨β α→β ¬ α ∃xΦ(x) ∀xΦ(x)
consisting of a proof of α and a proof of β; choosing one of the propositions α, β and laying down a proof of it; transferring any proof of α onto the proof of β and verifying that results of it are proofs of β indeed; equivalent to a proof of α → 0, where 0 is an absurd sentence (falsum);
choosing an object a and laying down
a proof of Φ(a);
which to every object a of a given domain assigns a proof of Φ(a) and subsequently verifies it.
Heyting [1930] presents the intuitionistic propositional calculus as a system INT based on the axioms:
Many-valued Logic and its Philosophy
(H1) (H2) (H3) (H4) (H5) (H6) (H7) (H8) (H9) (H10) (H11)
53
p → (p ∧ p)
(p ∧ q) → (q ∧ p)
(p → q) → ((p ∧ r) → (q ∧ r))
((p → q) ∧ (q → r)) → (p → r)
q → (p → q) (p ∧ (p → q)) → q
p → (p ∨ q)
(p ∨ q) → (q ∨ p)
((p → r) ∧ (q → r)) → ((p ∨ q) → r)
¬p → (p → q)
((p → q) ∧ (p → ¬q)) → ¬p
and the rules M P and SU B. The “soundness” of INT axiomatics can be demon strated through the above-mentioned interpretation of logical constants in terms of proof. It is readily checked that all the laws of the intuitionistic propositional calculus are classical tautologies. Notwithstanding, INT differs from CPC, which can be shown applying the following three-element Heyting matrix: H3 = ({0,1/2 , 1}, ¬, →, ∨, ∧, {1}), � ukasiewicz matrix while ¬ and → are charac in which ∨ and ∧ are defined as in L terized by the tables: α 0 1 /2 1
¬α 1 0@ 0
→ 0 1 /2 1
0 1 0@ 0
1
/2 1 1 1 /2
1 1 1 1
which differ from L � ukasiewicz tables in two places marked by @ , where according � ukasiewicz the value is 1/2 . to L INT ⊆ E(H3 ) since axioms (H1)–(H11) pertain to E(H3 ) and E(H3 ) is closed under the rules M P and SU B. Subsequently, such laws of the classical logic as p ∨ ¬p,
¬¬p → p,
(¬p → p) → p
are not tautologies of the matrix H3 : it suffices to consider any valuation h such that h(p) = 1/2 . It is also noteworthy that the strengthening of Heyting axiom system with the law of the excluded middle leads to the classical logic. The problems of relations between the intuitionistic and classical propositional calculi were given much attention, the so-called intermediate logics (intermediate between the intuitionistic and classical logics) were intensely studied (see e.g. the papers by Kabzi´ nski and Krajewski in: Marciszewski [1987] — the calculus determined by Heyting matrix can serve as an example of such a logic. The weakening of INT resulting from the omission of (H10) leads to the system of minimal logic (consult Johansson [1936]), closer to intuitionism than Heyting calculus.
54
Grzegorz Malinowski
G¨odel matrices G¨ odel [1932] showed that INT cannot be described by a finite matrix and, in consequence, by a finite set of finite matrices. G¨odel’s reasoning consists in the construction of a sequence of matrices approximating INT, and next in pointing out, on the base of the matrices of that sequence, a suitable set of formulas outside odel matrix (n ≥ 2, n finite) is of the form: INT: n-valued G¨ Gn = ({0, 1/n−1 , . . . , where ¬x =
1 0
n−2
if x = 0 , if x = 0
x→y=
/n−1 , 1}, ¬, →, ∨, ∧, {1}),
1 y
if x ≤ y , if x > y
x ∨ y = max(x, y), x ∧ y = min(x, y).
Notice that G2 = M2 , G3 = H3 . The tables of negation and implication in G4 are the following: α 0 1 /3 2 /3 1
¬α 1 0 0 0
→ 0 1 /3 2 /3 1
0 1 0 0 0
1
/3 1 1 1 /3 1 /3
2
/3 1 1 1 2 /3
1 1 1 1 1
In turn, each G¨ odel matrix Gn is a submatrix of Gn+1 - check that the mapping h from the set of values of Gn+1 onto Gn defined as h(i/n ) = /i n−1 for 0 ≤ i ≤ n − 1 and h(1) = 1 is a homomorphism of two matrices. Accordingly, INT ⊆| E(Gn−1 ) ⊆| . . . ⊆| E(G3 ) ⊆| E(G2 ) = TAU T . Let, further, ≡ be the connective of equivalence defined customarily; for any for mulas α, β, α ≡ β =df (α → β) ∧ (β → α). Then, α ≡ α ∈ INT and the functions of matrices Gn corresponding to ≡ are described by 1 when x = y x≡y= min(x, y) when x = y. Consider the sequence {di } (i ∈ N ) of formulas: (di )
(p1 ≡ p2 ) ∨ (p1 ≡ p3 ) ∨ . . . ∨ (p1 ≡ pi ) ∨ (p2 ≡ p3 ) ∨ (p2 ≡ p4 ) ∨ . . . . . . ∨ (p2 ≡ pi ) ∨ . . . ∨ (pi−2 ≡ pi−1 ) ∨ (pi−2 ≡ pi ) ∨ (pi−1 ≡ pi ).
E(Gn ) if i ≤ n and thus d2 , d3 , . . ., As everyone is quick to notice, di ∈ INT. The proof of the nonexistence of a finite matrix (weakly) adequate dn , . . . ∈ to INT can be viewed as follows: If INT = E(M ) for some M -element matrix M = (A, I), then v(α ≡ α) ∈ I for any valuation v. Then, by extensionality, for arbitrary formulas α, β (o)
v(α) = v(β) implies
v(α ≡ β) ∈ I.
Many-valued Logic and its Philosophy
55
Now, consider a formula dk where k > m. Since the number of propositional variables of this formula exceeds the cardinality of the matrix M , then for every pk1 , pk2 ∈ V ar(dk ) there is a v such that v(pk1 ) = v(pk2 ) and, in view of (o), v(pk1 ≡ pk2 ) ∈ I. Applying the fact that (H7) ∈ E(M ), v(dk ) ∈ I can be proved. Thus dk ∈ E(M ). A contradiction. Keeping the original definitions of G¨ odel’s connectives one may define an infinitevalued logic. Thus, taking the set of all rational numbers from the real interval odel’s matrix Gℵ0 . It follows, that INT ⊆ [0,1], we get the denumerable G¨ | E(Gℵ0 ; Dummett [1959] showed that the system of propositional logic thus received is axiomatizable: it may be obtained from INT by adjoining the formula (H12)
(p → q) ∨ (q → p)
to the axiom system (H1)–(H11), the rules of inference remain unchanged.
More on adequacy An infinite class of finite matrices, adequate for INT, was introduced by Ja´skowski [1936]. Ja´skowski’s sequence of matrices begins with the classical matrix and its succeeding terms are made out of the preceding ones by means of special operation G; an account and detailed proof of the completeness theorem can be found in Surma [1971]. Of our interest are investigations by Beth [1956] concentrated upon the ques tion what is “intuitionistically true tautology” and upon getting general method of finding “intuitionistic proofs” of the property. What appears to call for special attention is a topological interpretation provided by Tarski [1938]: here, proposi tional variables are associated with open sets val(p) of a fixed topological space (X, I) (I is an interior operation) and next this mapping extends onto all formulas thus setting: val(α ∨ β) = val(α) ∪ val(β) val(α ∧ β) = val(α) ∩ val(β) val(α → β) = I{(X − val(α)) ∪ val(β)} val(¬α) = I{X − val(α)}. If α ∈ INT, then val(α) = X. Conversely, if val(α) = X for any space X and for any valuation val, then α ∈ INT. Tarski’s interpretation inaugurated the character ization of the intuitionistic logic in lattice-theory terms i.e. pseudo-Boolean, called also Heyting (or Brouwer), algebras; see Rasiowa and Sikorski [1963]. Curiously enough, in practice almost all non-classical logical constructions, many-valued in cluding, are expressible by means of pseudo-Boolean algebras (compare Section 5).
56
Grzegorz Malinowski
11
ON BIVALENT DESCRIPTIONS
In the 1970s the investigations of logical formalizations bore several descriptions of many-valued constructions in terms of zero-one valuations. The interpretations associated with these descriptions shed new light on the problem of logical many valuedness. Below, we discuss two different ways of expression of many-valued logics: one establishing logical two-valuedness of structural consequence relations as a result of division of sets of logical valued into distinguished and undistin guished values (see Section 7) and the other, in which replacement of more logical values by more valuations goes on a par with neglecting the role of the said division.
Suszko’s thesis and beyond Suszko [1977] calls attention to the referential character of homomorphisms associ ating to propositions their (possible) semantic correlates. Subsequently, he opposes them to logical valuations being zero–one valued functions defined on For. Given a propositional language L and matrix M = (A, D) for L, the set of valuations T VM is defined as: T VM = {th : h ∈ Hom(L, A)},
where th (α) =
1 if h(α) ∈ D 0 if h(α) ∈ D.
h2 does not imply Notice that card(T VM ) ≤ card(Hom(L, A) (in general, h1 = th2 !). Notice, moreover, that that th1 = X |=M α
if and only if
for every t ∈ T VM t(α) = 1 whenever t(X) ⊆ {1}.
The definition of logical valuations can be simply repeated with respect to any structural consequence operation C (or, equivalently, for any relation C associ ated with C) since for each such C there is a class matrices K having the property that C = {CnM : M ∈ K}, see [Wojcicki, 1970], in Section 4. Thus, each (structural) propositional logic (L, C) can be determined by a class of logical valuations of the language L or, in other words, it is logically two-valued, Suszko [1977]. The justification of Suszko’s thesis that states logical two-valuedness of an im portant family of logics lacks the description of valuations (i.e. elements of T VC ) for an arbitrary relation C . Moreover, it seems, that giving a general method for the recursive description of these valuations not knowing precisely the structure of the class K of matrices adequate for C is hardly possible. At the same time, however, even for simple relations of inference the conditions defining valuations
Many-valued Logic and its Philosophy
57
are illegible. An example of a relatively easily definable set of logical valuations � ukasiewicz logic is LV3 , the class adequate for (→, ¬)-version of the three-valued L [Suszko, 1975]. LV3 is the set of all functions t : For → {0, 1} such that for any α, β, γ ∈ For the following conditions are satisfied: (0) (1) (2) (3) (4) (5) (6) (7)
either t(γ) = 0 or t(¬γ) = 0 t(α → β) = 1 whenever t(β) = 1 if t(α) = 1 and t(β) = 0, then t(α → β) = 0 if t(α) = t(β) and t(¬α) = t(¬β), then t(α → β) = 1 if t(α) = t(β) = 0 and t(¬α) = t(¬β), then t(α → β) = t(¬α) if t(¬α) = 0, then t(¬¬α) = t(α) if t(α) = 1 and t(β) = 0, then t(¬(α → β)) = t(¬β) if t(α) = t(¬α) = t(β) and t(¬β) = 1, then t(¬(α → β) = 0
Usually, the degree of complexity of the many-valued logics description increases with the the quantity of values. In some cases, however, it can be simplified by the application of extra connectives “identifying” original matrix values. Such a use of j-operators of Rosser and Turquette made possible to get e.g. a uniform � ukasiewicz logics, Malinowski [1977]. description of logical valuations for finite L The logical valuation procedure forms a part of a broader semantical programme related to the conception of so-called non-Fregean logics [Suszko, 1972]. Accord ing to Suszko there are situations which play the role of semantic correlates of propositions. Logical valuations, on their side, are nothing more than character istic functions of the sets of formulas being counterimages of the sets of positive situations, i.e. of those which obtain, under homomorphisms settling the interpre � ukasiewicz logic (n tation. Following Suszko, it can be said that the n-valued L � ukasiewicz finite) is a two-valued logic of n situations s1 , s2 , . . . , sn denoted by L as 0,1/n−1 , . . . , 1, respectively. Obviously then 0 and 1 must not be identified with the logical values of falsity and truth. In the literature one may find other, more or less justified, claims that any logic has a two-valued semantics. One of them, by Kotas and da Costa, deserves special attention. Kotas and da Costa [1980] proved independently from Suszko, that any logic C given by axioms and rules of inference C = (Σ, ). Given any such logic, a function ν : For → {0, 1} is called a (two-valued) valorization associated with C, when the following conditions are satisfied: (1) If α ∈ Σ, then ν(α) = 1, (2) If all premisses of an application of a rule of inference from have value 1, then the conclusion has also value 1, (3) there exists at least one formula α ∈ Σ, such that ν(α) = 0. The completeness of the inference c of C with respect to the inference relation |=c the class of all C -valorizations is standard: the valorizations are characteristic functions of saturated, or relatively maximal, sets of formulas: a set X of formulas
58
Grzegorz Malinowski
is α − saturated if X c α and for every β ∈ X, X ∪ {α} c α. Accordingly, a α-saturated set X defines a valorization ν such that ν(X) ⊆ {1} and ν(α) = {0}. The method of valorizations was used by Kotas and da Costa for getting seman tic two-valued description for the system C1 of the paraconsistent propositional logic.32 Batens [1980] developed a device simplifying and automating the process of getting descriptions of classes of valorizations corresponding to a set of axiom and rules of inference. Next to that Batens also invented the so-called n-tuple semantics “bridging two-valued and many-valued semantic systems”, see Batens [1982].
Scott valuations Scott [1973; 1974] regards the division of the set of values on designated and undesignated as unnatural. And, replacing more values by more valuations, Scott endeavours to bestow more intuitive character upon many-valued constructions. The valuations are bivalent functions and they generate a partition of the set of propositions of a given language into types corresponding to the original logical values. Scott considers only finite classes of valuations and he assumes that (many valued) logics are determined by single matrices. The above two papers comprise merely an outline of a general method and its exemplification within n-valued L � ukasiewicz logics. Let For be the set of formulas of a given propositional language L and V = {v0 , v1 , . . . , vn−1 } (n ≥ 1) a finite set of valuations: the elements of V are (for the moment) arbitrary functions vi : For → {t, f}, with t denoting truth and f falsity. By a type of propositions of L with respect to V we mean an arbitrary set Zβ of the form: Zβ = {α ∈ F or : vi (α) = vi (β) for any i ∈ {0, 1, . . . , n − 1}}. It is easily seen that using an n-element set of valuations one can induce maximally thus, for example, two-element set {w0 , w1 } of valuations 2n types: (see the table beside) defines four types: Z1 , Z2 , Z3 , Z4 . The confining of the valuations di w0 w1 minishes the number of types. The set of valu Z f f 1 ations just considered will define at most three f t Z 2 types Z1 , Z2 , Z4 when we require that w0 (α) ≤ t f Z3 w1 (α) for every α ∈ For, two types: Z2 , Z3 when t t Z 4 w1 (α) for every α ∈ For and Z1 , Z4 under w0 (α) = the condition that w0 = w1 . The types are counterparts of logical values: Scott [1973] refers to them as “indexes”. The above example shows that a given valency < 2n can be received on several ways. Which of these reductions should be taken into account, it depends 32 Paraconsisitent logics challenge the principle ex falso quodlibet. A logic is paraconsistent iff its consequence relation is not explosive, i.e. it is not true that {α, ¬α} |= β, see e.g. da Costa [1974].
Many-valued Logic and its Philosophy
59
on the properties of propositional connectives that, on their side, are type-valued operations i.e. mappings of sequences of types into types. An accurately-aimed choice of the limiting conditions leads to a relatively simple characterization of the connectives under consideration. Applying the above method, Scott gets a description of the implicative system � ukasiewicz logic through the (n − 1)-element set of valuations of n-valued L V L∗n = {v0 , v1 , . . . , vn−2 } such that for any i, j ∈ {0, 1, . . . , n − 1} and α ∈ For∗ , For∗ being used to denote set of formulas of the language L∗ comprising negation ¬ and implication → connectives, (mon)
whenever
vi (α) = t
and i ≤ j, then
vj (α) = t
and, moreover, v0 (α1 ) = f and vn−2 (α2 ) = t for some α1 , α2 ∈ For∗ . The table be low shows that the set V L∗n determines n types Z0 , Z1 , . . . , Zn−1 of propositions: Z0 Z1 Z2 . . . Zn−2 Zn−1
v0 t f f . . . f f
v1 t t f . . . f f
v2 t t t . . . f f
... ... ... ... ... ... ... ... ...
vn−3 t t t . . . f f
vn−2 t t t . . . t f.
The function f (Zi ) = n − i − 1 / n − 1 is 1 − 1 order-reversing mapping of the set of types onto the universe of the L � ukasiewicz matrix Mn : Z0 corresponds to 1 while Zn−1 to 0 in the matrix, compare Section 6. The negation and the implication connectives are characterized in the following way: Zi → Zj = Zmax(0,j−i) , ¬Zi = Zn−i−1 . Accordingly, for any k ∈ {0, 1, . . . , n − 2}, (¬)
vk (¬α) = t if and only if vn−i−1 (α) = t
(→)
vk (α → β) = t
if and only if i + k ≤ j, vi (α) = t and vj (β) = t.
Simple calculation shows that the set of all formulas of L∗ true under an arbitrary valuation vi ∈ V L∗n is just the content of Mn∗ , the (¬, →)-reduct of L � ukasiewicz matrix Mn (n finite!): E(Mn∗ ) = {α ∈ For∗ : vi (α) = t for i ∈ {0, 1, . . . , n − 2}}. ∗
Simultaneously, however, the consequence relation |=∗n ⊆ 2For → For∗ ; X |=∗n α
if and only if
vi (α) = t whenever vi (X) ⊆ {t}
for any vi ∈ V L∗n ,
60
Grzegorz Malinowski
does not coincide with |=n (reduced to the language L∗ ) — to verify this it suffices to check e.g. that {α → β, α} |=∗n β, while clearly {α → β, α} |=n β. |=∗n is called a conditional assertion. Whether and how it can be extended onto the whole language L is evident. Scott suggests that the equalities of the form “vi (α) = t”, for i ∈ {0, . . . , n − 2}, should be read as “(the statement) α is true to within the degree i”. Consequently, he assumes that the numbers in the range 0 ≤ i ≤ n − 2 stand for degrees of error in deviation from the truth. Degree 0 is the strongest and corresponds to “perfect” truth or no error: all the tautologies of L � ukasiewicz logic are schemas of � ukasiewicz implication the statements having 0 as their degree of error. Besides, L may conveniently be explained in these terms: assuming i + j ≤ n − 2 we get that vi (α → β) = t and vj (α) = t yield vi+j (β) = t. Thus, making use of propositions α → β, one may express the amount of shift of error between the degree of hypothesis to that of the conclusion as being the measure of error of the whole implication. An example accommodated from the Euclidean geometry justifies the construction: Where a, b, c . . . are points of the plane, let the metalinguistic statement “|a − b|” denote the distance between a and b. Let S be a propositional language having the set For of formulas consisting of all formulas made up from atomic formulas “a = b” (possibly others) by the use of the connective → (and possibly others such as “∨” and “∧”). Let us define the set of valuations Vε = {v0 , v1 , . . . , vn−2 } (n ≥ 2) for S putting vi (“a = b”) = t if and only if |a − b| ≤ i and assuming that → satisfies (i). Let, finally, |=ε ⊆ 2For → For be the conse quence relation determined in S by Vε , i.e. X |=ε α
if and only if vi (α) = t whenever for any vi ∈ Vε .
vi (X) ⊆ {t}
Depending on the choice of a unit distance, the relationship between a and b is one of “imperfect” equality and as such it is not transitive. The conditional assertion (P1)
{“a = b”, “b = c”} |=ε “a = c”
fails in general, while for any a, b, c it is true that (P2)
“a = b”|=ε “b = c → a = c”.
Hence, the use of the L � ukasiewicz implication permits to formulate a weakened version of the law of transitivity: (P2). 12
INTERPRETATION AND JUSTIFICATION
While some scholars of the philosophical foundation of logic criticised manyvalued constructions, the others tried to find convincing justifications for many valuedness. The most essential in the two categories were arguments concerning
Many-valued Logic and its Philosophy
61
L � ukasiewicz logics and the problem of the justified interpretation of non-orthodox logical values at all. Below we overview and discuss some for and against multi plying logical values.
Three-valued L ukasiewicz logic L � ukasiewicz [1920] explanation of the logical value 1/2 resorting to “future contin gents” and a “posibility” or undetermination of the 0-1 status of propositions was criticized on several occasions. As we have already mentioned, the first blow was inflicted by Gonseth, who in 1938 noticed — see Gonseth [1941], that the formal characterization of the connectives in L � ukasiewicz logic is incompatible with the suggested ways of interpreting the third logical value. The argumentation of Gon seth is sound and straightforward: Whenever α is undetermined, so is ¬α and then α ∧ ¬α is undetermined. That contradicts our intuition since, independently � ukasiewicz interpreta of α’s content, α ∧ ¬α is false. The upshot discovers that L tion neglect the mutual dependence of some “possible” propositions. Haack [1978] � ukasiewicz’s way of avoiding the fatalist conclusion derived from the analyses L assumption that the contingent statement “I shall be in Warsaw at noon on 21 December of the next year” is either true or false in advance of the event. She remarks that this way of rejecting bivalence is wrong, since it depends on a modal fallacy of arguing from “It is necessary that (if a, then b)” to “If a, then it is necessary that b”. Urquhart [1986] sees the third logical value as the set {0,1} of two “poten tial” classical values of a future contingent sentence and defines the implication as getting all possible values of implication. Thus, the implication having 0 as antecedent takes always value 1, the implication from 1 to {0,1} takes {0,1} and the implication from {0,1} to {0,1} has the value {0,1}. → 0 1 /2 1
0 1 1 /2 0
1
/2 1 1 /2 1 /2
1 1 1 1
The last point is inconsistent with the L � ukasiewicz stipulation, since the output � ukasiewicz table is of 1/2 → 1/2 had to be 1. Therefore, Urquhart claims, the L wrong. It may be of interest that the connective get by Urquhart is the Kleene strong implication. Reichenbach [1944] argued that adoption of three-valued logic would provide a solution to some problems raised by quantum mechanics. For the purpose of avoiding of “causal anomalies”, Reichenbach presents an extended version of the L � ukasiewicz logic, adding further negation and implication connectives. He refers to the third logical value as “indeterminate” and assigns it to anomalous state ments of quantum mechanics. The weak point of Reichenbach’s proposal is that as “indeterminate” are also classified certain laws, such as e.g. the principle of energy.
62
Grzegorz Malinowski
Temporal interpretation Urquhart [1973] provides a very interesting interpretation of values of finite values propositional logics. He takes the set Sn = {0, 1, . . . , n − 2} and considers the relation between numbers and formulas: ⊆ Sn × For. Urquhart generally assumes that (Tr)
If x α
x ≤ y ∈ Sn , then
and
y α.
and adopts to particular logics thus specifying n, the language, and providing recursive conditions which establish the meaning of connectives. Accordingly, in each of the cases considered we have to do with some Kripke-style semantics: Kn = (Sn , ≤, ). A formula α is Kn -true iff it is true at the point 0, i.e. provided that 0 α. Kn is a semantics of the system determined by a given matrix M when that set of all Kn -true formulas is equal to the content of M i.e. when E(M ) = {α ∈ F or : 0 a}. Urquhart provides the semantics for n-valued logics of L � ukasiewicz and Post, � ukasiewicz calculi has to satisfy and for the three-valued Bochvar’s system. For L the conditions: xα→β x ¬α xα∨β xα∧β xα≡β
iff iff iff iff iff
y α yields x + y β whenever (n − 2) − x α x α or x β x α and x β x α → β and x β → α.
x + y ∈ Sn
It is not hard to notice that it is possible to “translate” the Scott’s valuations33 in V L∗ to the instances of can be made according to the equivalence: i α if and only if vi (α) = t. The semantics for (¬, ∨)-variant of Post propositional logic is established through the conditions: x ¬α
iff
xα∨β
iff
y α for no y ∈ Sn or there is a such that y < x and y α x α or x β.
y ∈ Sn
To “reference points” x ∈ Sn , several meanings may be attached. For L � uka siewicz and Post logics Urquhart suggests a temporal interpretation: 0 being the present moment, x = 0 a future moment, then “x α” reads “α being true at 33 See
Section 11.
Many-valued Logic and its Philosophy
63
(the moment) x”. It is worthnoting that the assumption (Tr) guarantees that any proposition true at x is also true at every moment y future to x. That obviously means that in the framework elaborated, propositions are treated as temporally definitive units and, as such, they must not contain any occasional, time-depending expressions (such as e.g. “now”, “today” etc.). It may be appropriate, perhaps, to add that even the very originators of many-valued logics while using occasional words in the examples, they usually have in mind temporally-definite marks of reference. Under the above interpretation L � ukasiewicz implication α → β is true at x if and only if the truth of α at y yields β being true at x + y i.e. at the future moment y time-units distant from x. On its turn, L � ukasiewicz negation ¬α is true at x if and only if α is false at (n − 2) − x, i.e. at the moment back to n − 2 (the last in Sn ) of x time-units. Urquhart suggests that such a way of understanding exhibits the sources of difficulties in getting a plainly intuitive interpretation of many-valued L � ukasiewicz logics, and he claims that the “natural” connectives of implication and negation should rather satisfy the conditions: xα→β
iff
x ¬α
iff
for any y ∈ Sn (y β whenever x ≤ y y α for no y ∈ Sn .
and
y α),
Urquhart’s interpretation of Post logics is, as easily seen, entirely compatible with the original interpretation envisaged by Post himself.
Set theory and many-valued logic Russell’s paradox34 leads to a more general question, namely, whether in the set theory there can be adopted the Comprehension Axiom : (AC) The propositions of the form ∃x∀y(y ∈ x ≡ Φ(y)), where Φ(y) is a formula containing y, are true. The presence of (AC) signifies that every formula defines a certain set or, more concisely, that for any property a set of objects bearing that property can be chosen. The discovery of Russell excludes the acceptance of (AC) in the set theory based on the classical logic. Hence, the only method allowing to construct set theory preserving the Comprehension Principle is to change its logic. The suggestion of Bochvar may be obviously conceived as a step in this direction. However, it can hardly be accepted as satisfactory; though it enables to classify some formu las (the formula defining Russell set included) as senseless still, simultaneously, it commits to a very embarrassing, distinction between two categories of propo sitions. Next, as it soon turned out, the three-valued and, more generally, all 34 See
Section 1.
64
Grzegorz Malinowski
finite-valued L � ukasiewicz’s logics cannot seriously be taken into consideration ei ther. Moh Shaw-Kwei [1954] provided the following method of construction of “undesirable” sets in Ln : F or a given finite n ≥ 2 we put Zn = {x : x ∈ x →n p}.35 The set Zn being antinomial since the following absorption rule α →n β (absn )
α →n−1 β
is a rule of Ln (equivalently, (α →n β) → (α →n−1 β) ∈ E(Mn )). The assumption Zn ∈ Zn implies that Zn ∈ Zn →n p. Thus, after (n − 1)-ary application of (absn ) we get Zn ∈ Zn → p and, finally, as a result of the detachment (i.e. application of M P ), p. � ukasiewicz logics As absorption rules (absn ) are not the rules of infinite-valued L much attention was given to the possibility of foundation of set theory with (AC) on these logics. Skolem [1957] put forward a hypothesis that the proposition � ukasiewicz logic (or, more accurately, in the (AC) was consistent36 in ℵ1 -valued L predicate calculus with the predicate ∈). Up till now Skolem’s hypothesis was only partly supported. Using advanced proof theory techniques and applying Brouwer’s Fixed Point Theorem (for n-dimensional cube) Skolem showed that the set of formulas of the form (s1)
∀x1 . . . ∀xn ∃y∀t(t ∈ y ≡ U (t, y, x1 , . . . , xn )),
with U (t, y, x1 , . . . , xn ) being a formula containing no quantifiers wherein free vari � ukasiewicz ables are at the outmost t, y and x1 , . . . , xn , is consistent is ℵ1 -valued L logic.37 The result of Skolem, having applied his method of proof, was expanded by Chang and Fenstad. Chang [1963] showed that the assumption of the absence of quantifiers in formulas U (t, y, x1 , . . . , xn ) can be removed under the condition that bound variables in U appear in atomic formulas u ∈ w only on the second position. Chang also proved that in Lℵ1 any formula (c)
∃x∀y(y ∈ x ≡ Φ(y)),
(compare (AC)) where Φ(y) is a formula with one free variable y, is consistent. Fenstad [1964] obtained a similar result in this direction: he showed that the set 35 p stands for any formula inconsistent in L ; α →n β is an “ascending” implication n α → (α → (. . . → (α → β) . . .)) with n − 1 antecedents α. 36 α is consistent in the Predicate Calculus iff there exists an interpretation f (f ) such that D f (α) = 1. In L � ukasiewicz logic the concept of interpretation is defined according to the pattern of Section 6 applied in Lℵ1 . 37 The set X of closed (i.e. having no free variables) formulas is consistent iff three exists an interpretation f sending all formulas of X into true propositions i.e. such that f (X) ⊆ {1}.
Many-valued Logic and its Philosophy
65
of Skolem’s formulas is consistent (in ℵ1 -valued logic) under the assumption that free variable t takes only the place of w in atomic formulas u ∈ w. All this shows that the question of unlimited consistency of the Comprehension Axiom in many-valued logics still remains open. And, it obviously leaves the room for making several suppositions. For example, it can seem unnatural that Skolem attached the problem directly in Lℵ1 and not in the logic of countably many values. It should immediately be noticed that the endeavours to get a consistency proof of (AC) in Lℵ0 would have be connected with working out of a new method: Brouwer’s Fixed Point Theorem for the set of rational numbers of the interval [0,1] does not hold. In relation to the problems discussed a recent result by H´ajek et al. [2000] on the ajek shows the Liar paradox and the theory of dequotation should be mentioned. H´ consistency of the theory of arithmetic with the truth predicate over the infinite L � ukasiewicz predicate logic. To this aim, he considers the axiom of dequotation (DA) ϕ ≡ T r(ϕ), where T r is a unary predicate of truth, in the language of Peano arithmetic PA extended with T r, and ϕ is the G¨odel number of ϕ. As known, adding (DA) to the axioms of PA founded on the classical logic leads to the contradiction, since one may construct the formula α such that α ≡ ¬T r(α) and thus to prove α ≡ ¬α. Taking into account the fact that the last formula is � ukasiewicz logic H´ajek showed, that when formalized in the not inconsistent in L L � ukasiewicz predicate logic PA + DA is consistent. The proof of the claim uses the nonstandard models of the structure N of natural numbers with zero, successor, ajek constructs a formula, that over N behaves as addition and multiplication. H´ a formula saying “I am at least a little false”.
13
MODES OF MANY-VALUEDNESS
There are two main approaches to logic. One related to the notion of valid or tauto logical formulas and the other, which uses the consequence relation. Depending on the choice, we may therefore speak about two different kinds of many-valuedness. Taking this into account, we get rid on the problem of possible formulation of the status of many-valuedness. Next to the two notions, we introduce the third concept of inferential many-valuedness stemming from a natural generalization of the standard consequence relation.
Two kinds of many-valuedness A system of logic determined by a matrix M for the standard language Lk is tau tologically many-valued, whenever E(M ) does not coincide with the set of classical TAUT. The 1918 L � ukasiewicz example of such tautologies TAUT, i.e. if E(M ) = a matrix is M3 = ({0, 1/2 , 1}, ¬, →, ∨, ∧, ↔, {1})
66
Grzegorz Malinowski
where ¬x = 1 − x, x → y = min(1, 1 − x + y) etc. It is, however, fairly simple to construct a matrix for Lk operating on {0, 1/2 , 1}, whose content is T AU T and, thus, defining two-valued logic. Note that to this aim it suffices to enlarge the set of the distinguished values adding 1/2 . Thus, the matrix M3∗ = ({0, 1/2 , 1}, ¬, →, ∨, ∧, ↔), {1/2 , 1}) defines the tautologically two-valued logic. When a logic is understood as a consequence relation |=M then it is many-valued, or c-many-valued, if |=M is different from the classical consequence relation |=2 . Since E(M ) = {α ∈ F or : ∅ |=M α}, every tautologically many-valued logic is also c-many-valued. Notice, that still the L � ukasiewicz logic may serve as an example: |=2 This, however, cannot be reversed. There are few examples of logics, |=3 = which are tautologically two-valued, but are c-many-valued. Consider e.g. the matrix M for Lk for which the connectives are defined by the following truth tables: x 0 t 1
¬x 1 1 0 ∧ 0 t 1
→ 0 t 1 0 0 0 0
0 1 1 0 t 0 0 0
t 1 1 0 1 0 0 1
∨ 0 t 1
1 1 1 1 ≡ 0 t 1
0 1 1 0
0 0 0 1 t 1 1 0
t 0 0 1
1 1 1 1
1 0 0 1
Note, that E(M ) = TAUT, but |=M = |=M2 — since the rule of Modus Ponens fails for |=M , i.e. {α → β, α} |=M β does not hold. The above distinction between the two notions of many-valuedness is particu larly important, when the set of tautologies of a given logic is empty. We face this situation with Kleene and Bochvar logics. The matrix of the weak Kleene (internal Bochvar) logic is K3 = ({f, u, t}, ¬, →, ∨, ∧, ≡, {t}), with the first set of operations. As it was already stated, this logic is nontautological, E(K3 ) = ∅. However, Kleene logic is non-trivial since the conse quence |=K 3 consists of some special rules of the classical logic: 38 X |=K 3 α if and only if X |=2 α and V ar(α) ⊆ V ar(X).
for any classically consistent X ⊆ F or, i.e. such that h(X) ⊆ {1} for some interpretation h ∈ Hom(L, A2 ). 38 V
ar(α), V ar(X) are the sets of variables appearing in α and all formulas in X, respectively.
Many-valued Logic and its Philosophy
67
Multiple-element models of two-valued logic The use of logical matrices is undoubtedly the most natural way of achieving may-valuednes i.e. the consequence relation different from |=2 . We have already discussed two cases of getting a genuine logic of this kind. However, taking a multiple-element matrix as a base for the logical construction does not guarantee its many-valuedness. And, on the other hand, there are different kinds of that property. Consider, for instance, the matrix W3 = ({0, t, 1}, ¬, →, ∨, ∧, ≡, {t, 1}), x 0 t 1
→ 0 t 1
¬x 1 0 0 ∧ 0 t 1
0 0 0 0
0 1 0 0 t 0 t t
t t t t 1 0 t 1
∨ 0 t 1
1 1 t 1 ≡ 0 t 1
0 1 0 0
0 0 t 1 t 0 t t
t t t 1
1 1 1 1
1 0 t 1
Notice, that with every h ∈ Hom(L, W3 ) the valuation h∗ ∈ Hom(L, M2 ) corresponds in a one-to-one way such that hα ∈ {t, 1} iff h∗ α = 1. Therefore, |=W = |=M2 and W3 is nothing more then a three-valued model of the two-valued logic.39 The last, somewhat striking, case is when a multiple-element matrix retains all classical tautologies, i.e. its content coincides with TAUT, but its consequence relation differs from the classical by some rules of inference. The matrix K3∗ = ({f, u, t}, ¬, →, ∨, ∧, ≡, {u, t}), being like the Kleene-Bochvar matrix K3 but having two elements u and t des ignated has this property. Its consequence operation |=∗3 falsifies M P , since the inference {p → q, p} |=∗3 q does not hold.
Inferential many-valuedness Suszko [1977] stated that any matrix consequence, and, therefore every structural consequence relation,40 may be described using 0-1 valuations and thus that every logic is logically two-valued. The idea that shifted logical values over the set of matrix values refers to the division of matrix universe into two subsets of desig nated and undesignated elements and use the characteristic functions of the set of 39 Similar n-element models (any n ≥ 2) of the classical logic may be provided using matrices having standard connectives described in Section 7. 40 See Section 11.
68
Grzegorz Malinowski
designated elements D as logical valuations. A question whether many-valuedness of that kind is possible at all, led Malinowski [1990] to the next mode of logi cal many-valuedness, more precisely the three-valuedness, being a property of a natural consequence-like approach. The departure is a division of the matrix universe into three subsets of: rejected elements, accepted elements and all other elements. On such grounds it was pos sible to define the relation being a formal counterpart of reasoning admitting rules of inference which from non-rejected assumptions lead to accepted conclusions, see Malinowski [1990]. The relation was then called, somewhat inaccurately, a q-consequence. In the sequel, we shall use the term inference instead. An inference matrix for L is a triple M ∗ = (A, D∗ , D), where D∗ , D are disjoint subsets of rejected and accepted elements, respectively. |=M ∗ is said to be a matrix inference of M ∗ if for any X ⊆ F or, α ∈ F or: X |=M ∗ α iff for every h ∈ Hom(L, A)(hα ∈ D whenever hX ∩ D∗ = ∅). According to this, α is inferred from the set of premises X, whenever it is the case that if all premises are not rejected then α is accepted. Thus, the logical inference runs from non-rejected premises to the accepted conclusions. There are non-trivial reasons for which considering such inference relations is but a theoret ical enterprise, see Malinowski [1990; 1998]. Obviously, with each relation |=M ∗ one may associate the operation W nM ∗ : 2For → 2For putting W nM ∗ (X) = {α : X |=M ∗ α}. Notice that when D∗ ∪ D = A, W nM ∗ coincides with the consequence CnM determined by the matrix M = (A, D). In other cases the two operations dif fer from each other - too see this consider any inference matrix of the form ({e1 , e2 , e3 }, f1 , f2 , ..., fn , {e1 }, {e3 }). The inferential framework just introduced is a natural generalization of the standard one. So, when D∗ ∪ D = A, all concepts reduce to their standard coun terparts. The inference |=M ∗ coincides with the matrix consequence |=M , since D∗ and D are complementary. Accordingly, the inference becomes the relation of consequence. A It is easy to observe that for any inference matrix M ∗ for which D∗ ∪ D = no class TV of functions t : F or → {0, 1} exists such that for all X ⊆ F or and α ∈ F or, X |=M ∗ α iff for each t ∈ TV, (t(X) ⊆ {1} implies tα = 1). Thus, some “proper” W nM ∗ are not logically two-valued in the sense of Suszko. Now, for every h ∈ Hom(L, A) we define a three-valued function kh : F or → {0, 1/2 , 1} putting
Many-valued Logic and its Philosophy
1 1 /2 kh (α) = 0
69
if h(α) ∈ D if h(α) ∈ A − (D∗ ∪ D) if h(α) ∈ D∗ .
Given an inference matrix M ∗ for L let KVM ∗ = {kh : h ∈ Hom(L, A)}, X |=M ∗ α iff for every kh ∈ KVM ∗ if kh (X) ⊆ {1/2 , 1}, then Kh (α) = 1, This is a kind of a three-valued description of |=M ∗ . Notice that KVM ∗ reduces to T VM and KVM ∗ to T VM and |=M ∗ to |=M when D∗ ∪ D = A. In Malinowski[1990] an inference operation of which W nM ∗ is a prototype was introduced and studied. An operation W : 2For → 2For is an inference operation 41 provided that for every X, Y ⊆ For (W1) (W2)
W (X ∪ W (X)) = W (X)
W (X) ⊆ W (Y ) whenever
X ⊆ Y .
W is called structural if for any substitution e ∈ End(L) (S)
eW (X) ⊆ W (eX).
Where M ∗ is any inference matrix, W nM ∗ is structural. In turn, all Linden baum’s tools may be adopted to structural inference operations W to exactly the same effect. Thus, the bundle of Lindenbaum’s inference matrices WX = ( For , For − (X ∪ W (X)) , W (X)) may be used to prove, cf. Malinowski [1990], that for every structural inference operation W there is a class K of inferential matrices such that W nK (X) = {W nM ∗ (X) : M ∗ ∈ K}. We conclude that each structural logic (L, W ) is logically two- or three-valued. A generalization of the inferential approach onto more values seems technically possible. It also seems, however, that a natural explanation of such an inferential device might be much more difficult to get, see Malinowski [2002].
Towards many-valuedness inference Inferential three-valuedness discussed above is entirely consistent with the common understanding of logical system as a set of formulas closed under substitutions, usually defined as a content of a logical matrix: For any inferential matrix M ∗ = (A, D∗ , D) and a corresponding matrix M = (A, D), W nM ∗ (Ø) = CnM (Ø) = E(M ) 41 Originally
it was called a quasi consequence or a q-consequence.
70
Grzegorz Malinowski
This means that any logical system may equally well be extended to two-valued logic (L, CnM ) or to a three-valued logic (L, W nM ∗ ). Then, obviously, depending on the quality and cardinality of M the two extensions may define different logics. Perhaps the most striking is that even CPC i.e. the content of two-element matrix M2 can also be extended to the three-valued inference. The inference matrix M2∗ = (A2 , Ø, {1}) determines the operation W nM2∗ such that W nM2∗ (Ø) = E(M2 ) = TAUT. It would be in order to add, that the “inferential” part of this logic is, ia some sense, uninteresting since the class of non-axiomatic rules comprises only sequents X/α, where α is a tautology, α ∈ TAUT. The question on how the three-valued inference is characterized deductively, i.e. through the set of rules and appropriate conception of proof leads to interesting results. First, the proper notion of proof for the inference operation is the weakest possible when we retain the usual notion of a rule.42 To give an idea let us mention that it differs essentially from the standard proof in exactly one point: the repetition rule (rep) {α/α : α ∈ F or} is no longer unrestictedly accepted as the postulate that each premisse (or assumption) in the proof is automatically accepted as a conclusion (one of subsequent steps in the proof). Notice that the presence of the repetition rule is but an immediate consequence of the methodological Tarski postulate (T0) and not by a separate declaration i.e. it is not given as a rule per se. Note that this is no more true for the inference relation. The absence of (rep) in the general framework makes room for several modifica tions of inference and getting an infinitely many inferences which are still weaker than the consequence operation having the same system of theorems (tautologies) as its base. These may be received simply by adding only some instances of the rule. Thus, for instance, if W (Ø) is non-empty, for α ∈ W (Ø) α ∈ W (α). That is due to the fact that then at least { α/α : α ∈ W (Ø)} is a rule of W . Perhaps then, a slightly better way of providing a workable framework for ob taining logical many-valuedness would be to change the concept of a rule of infer ence.
14
FUZZY SETS AND FUZZY LOGICS
Everyday reasonings operate on imprecise concepts and are supported by approx imate inferences. That makes the possibility of applying the apparatus of the classical logic to formalize them very limited. Among special tools extending the formalization power of the standard approach are fuzzy sets theory and fuzzy log ics. Our aim now is to account for one of the most interesting but simultaneously most controversial conceptions inspired by logical many-valuedness. 42 See
Malinowski [1990].
Many-valued Logic and its Philosophy
71
Fuzzy sets Zadeh [1965] defines a fuzzy set A of a given domain U as an abstract object characterized by generalized characteristic function UA with values in the real set [0,1]: UA : U → [0, 1]. The values of UA are interpreted as degrees of membership of elements of U to the fuzzy set A. The extreme values of this function, 0 and 1, denote respectively: not belonging to A and entire membership to A. Limiting the scope of UA to {0, 1} results in an “ordinary” characteristic function and in this each “classical” set is a special case of a fuzzy set. Fuzzy sets are an instrument of modelling inexact predicates appearing in nat ural languages. Thus, for example the property of “being much greater than 1” defined on the set of real positives R+ can be assigned to a fuzzy set W with a non-decreasing characteristic function R+ → [0, 1] which meets the conditions like: RW (0) = 0, RW (1) = 0, RW (5) = 0.01, RW (100) = 0.95, RW (500) = 1 etc. Certainly, in the above example only values RW (0), RW (1) unquestionable and the selection of other values is somehow arbitrary. In the family F (U ) of fuzzy (sub)sets of a given domain the relation of inclusion reflexes the order between the reals: A⊆B
if and only if UA (x) ≤ UB (x)
for any a ∈ U ,
and the counterparts of the operations of complement (−), union (∪) and inter section (∩) are set by: U−A (x) = 1 − UA (x)
UA∪B (x) = max{UA (x), UB (x)}
UA∩B (x) = min{UA (x), UB (x)}.
Bellman and Giertz [1973] showed that UA∪B and UA∩B are the unique nondecreasing continuous functions warranting both the compatibility of the con struction with the standard algebra of sets and the fact that (F (U ), ∪, ∩, −) is a de Morgan lattice if and only if U−A is defined as above. It is in order to notice that, in spite of the naturalness of the proposal, several studies admit as (more) helpful, fuzzy sets algebras defined otherwise.43 The values of generalized characteristic functions may be identified with log ical values of propositions of the form “x ∈ X”, where ∈ is a “generalized” settheoretical predicate. Subsequently, using logical constants of a base logic one may set the inclusion and the operation s of fuzzy set algebra as: A ⊆ B =df ∀x(x ∈ A → x ∈ B) −A = {x : ¬(x ∈ A)} A ∪ B = {x : x ∈ A ∨ x ∈ B} A ∩ B = {x : x ∈ A ∧ x ∈ B}. 43 See
e.g. Zadeh [1976].
72
Grzegorz Malinowski
For Zadeh’s algebra the choice of a base logic is to great extent prejudiced: it (this logic) must be based on ℵ1 -element matrix, wherein negation is expressed by the function 1 − p, disjunction and conjunction, respectively by: max{p, q} and min{p, q}, and the universal quantifier as the greatest lower bound (inf ). The function of implication is not uniquely determined. However, evidently it should meet the requirement: (.)
If p → q = 1, then
p ≤ q.
Though L � ukasiewicz’s implication and, consequently, his ℵ1 -valued logic, have been the most intensely applied, similar connectives of other logics have been also taken into account. The commonly shared belief among scholars working on fuzziness, both theoreticians and practicians, is that only a concrete application of fuzzy sets algebra can decide about the final form of the base logic (see Gaines [1976a]).
Reasoning and inexact predicates In the initial applications of fuzzy sets theory much attention was focused on the analysis of reasoning using inexact predicates, standard propositional connec tives and quantifiers. Remarkably susceptible of experiment there appeared to be paradoxes, whose “successful” analysis consolidated the motivational layer of the conception of fuzziness. This account yielded the first understanding of the term “fuzzy logic” as a certain class of many-valued logics with uncountably many values, with L � ukasiewicz logic in the foreground. Goguen’s [1969] analysis of the classical paradox of a bald man may serve as an example. Intuitively, we would be ready to accept the two following propositions: (z1) (z2)
A man with 20.000 hairs on his head is not bald A man who has one hair less than somebody who is not bald is not bald as well.
So, applying the Detachment Rule 20.000 times, we shall get the conclusion that a man with no hair is not bald either. Naturally, the paradox stems from (z2) and more specifically from inexactness of the predicate “bald” or, equivalently, “not-bald”. The paradox will vanish when logical value of the proposition “A man with n hair is not bald” is identified with the degree of membership of a man with n hair to a fuzzy set “not-bald”, since then (z2) would have logical value less � ukasiewicz than 1, say 1 − ε, where ε > 0. If, for instance, in basic logic we use L implication then as result of 20.000 derivations we will obtain a proposition of the logical value amounting to 1 − 20.000ε, thus practically false. The development of fuzzy sets theory has surpassed all expectations. For its use there were adopted almost all important concepts of set theory, topology, algebra and probability calculus. It is remarkable that these were the applica tions in Computer Science and steering theory that gave an impetus to the most
Many-valued Logic and its Philosophy
73
extensive development of the theory: they have confirmed the usefulness of the unconventional methodology worked out by means of fuzzy set conception (see e.g. Gottwald [1981]).
Fuzzy logic proper Zadeh’s [1975] fuzzy logic is a method of modelling of imprecise reasoning oper ating on imprecise concepts and rules of approximate reasoning. Its construction conveyed the belief that thinking in terms of fuzzy sets is a typical feature of hu man perception. The examples of reasoning whose analysis might be possible due to fuzzy logic are such “inferences” as: Putin is very healthy Healthy men live a very long time
Bill likes women that are tall and wicked Monica is not very tall but very wicked
Putin will live a very long time
Bill will probably like Monica.
Fuzzy logic seeks to formulate several rules of approximate inference. For this purpose it attempts to formalize colloquial linguistic usage of certain “hedges” applied to imprecise concepts such as “very”, “more or less”, “too” etc. Zadeh’s logic is a two-level semantical construction allowing the fuzzines of predicates, their hedges and logical values. Its central elements are: (1) Denumerable set T V of linguistic logical values generated by its element “true” with the help of the hedge “very” and logical connectives. (2) Hedges of predicates and logical values, “very” being a special one. (3) The procedure of linguistic approximation compensating the lack of closure of the (object) language and the closure of the set T V onto logical connectives. Fuzzy logic is based on ordinary ℵ1 -valued logic with the connectives ¬, →,∨, ∧, ≡ and values in [0,1]. It identifies predicates with fuzzy subsets of a given universe and logical values with fuzzy subsets of the set of [0,1]. The most frequently used � ukasiewicz Lℵ1 (see and discussed is the “fundamental” system FL obtained on L Bellman and Zadeh [1977]). We shall confine our further considerations to some aspects of this construction. It is assumed that the set T V of linguistic logical values of FL is the set of the form: T V = { true, false, not true, not false, very true, more or less true, rather true, not very true, not very false, . . .}
74
Grzegorz Malinowski
where “true” is a fixed fuzzy subset of [0,1], “very” a fixed hedge, and all other elements are defined through “true”, “very” and (operations determined by) L � uka siewicz’s connectives. Obviously, the “names” of all logical values are conventional labels and their proper meanings follow from characteristic functions. Hedges are one-argument operations sending fuzzy sets to fuzzy sets. The most basic (a primitive) is a hedge reflecting the adverb “very“ and denoted as g. Zadeh [1972] supposes (g)
UgA (x) = (UA (x))2
and suggests that other hedges should be defined as superpositions of g and con nectives of the basic logic. The most important “derived” operator d is described as follows: (d)
UdA (x) = (UA (x))0,5 .
Zadeh urges that “more or less” is a linguistic counterpart of d. In the relevant literature g and d are called standard hedges and expressibility by their use has become a definability hedge criterion. The procedure of linguistic approximation stems from the lack of closure of T V under logical connectives. More specifically, if Utrue is a characteristic function of the value labelled “true” then, of course, all other elements of that set are thereby specified. Thus, for example the initial values of T V are defined by the following functions: Uf alse (x) Unot true (x) Uvery true (x) Umore or less true (x)
= = = =
Utrue (1 − x) 1 − Utrue (x) (Utrue (x))2 (Utrue (x))0,5 ,
(x ranges over the set of values of the base logic, x ∈ [0, 1]). Consequently, all linguistic logical values depend on the (subjective) introduction of the meaning of “true”. Zadeh calls this feature a localization and the elements of T V , local values. Thereby received, as a result of localization, the systems of FL are called local logics. For those logics there is the common way of defining logical connectives; it consists in identifying them with the operations of the algebra of fuzzy (subsets) of [0,1] and thus, in a sense, with connectives of the base logic. A linguistic approximation is a heuristic procedure assigning to any propositions linguistic logical values. For obvious reasons it is impossible to specify even a general principle of that procedure; what can said is merely that in a concrete application of a fuzzy logic it consists in searching for the closest value from T V 0 for a statement. As it has been already mentioned, fuzzy logic aims at formulating the rules of approximate reasoning (or inference). Basic as well standard rule of that kind is the Compositional Rule of Inference
Many-valued Logic and its Philosophy
u1 is F u1 and u2 are G
u1 and u2 are F u2 and u3 are G
u2 is LA{F ∗ G}
u1 and u3 are LA{F ∗ G}
75
where u1 and u2 are objects, F and G predicates (properties or relations) and ∗ an operation of relational composition, in the former case ∗ is defined as follows: UF ∗G (u2 ) = supx (UF (x) ∧ UG (x, u2 )), and LA{F ∗ G} is a linguistic approximation to the (unary) fuzzy relation F ∗ G. The following is an exemplification of the first scheme: a is small number a and b are approximately equal b is more or less small number In more complicated rules, the premisses are compound statements of several de grees of complexity e.g. if u1 is F , then u2 is G, and may be quantified by fuzzy quantifiers i.e. expressions like most, many, several, few etc. In the end, the for mulation of other rules, like e.g.the Rule of Compositional Modus Ponens special operations on fuzzy sets has to be used. In practical application of fuzzy inference rules the first set consists in assign ing fuzzy predicates fuzzy subsets of a given universe; in the case of (non-unary) relations, fuzzy subsets of relevant Cartesian products of their domains. This procedure, often referred to as fuzzy restriction, obviously exceeds logic. Notwith standing, within the scope of a logic it is possible to formulate general principles of restriction resulting from the peculiarity of formal devices. Zadeh’s “fuzzy” conception has found its place among accepted methods of Artificial Intelligence. It holds its ground due to reliable applications as e.g. in medical diagnosis, see Turner [1984].
15
RECENT DEVELOPMENTS
Algebraic and metamathematical studies of the infinite-valed L � ukasiewicz logic, see Cignoli et al. [1999], are among the most important issues of recent investigations. Somewhat related to these studies are activities and concerning “t-norm” based ajek [1998] fuzzy logics and delineating a class of propositional logics, called by H´ logics (in a narrow) sense. Further to this, at least two topics somewhat connected to the sciences of information should be mentioned: the lattices of truth and information, invented by Belnap [1977] and Ginsberg [1987], and the automatic deduction problems.
76
Grzegorz Malinowski
Truth functional fuzzy logics The influence of fuzzy set theory initiated the study of a class of systems of many-valued logics, whose semantics is based on the real interval [0,1]. Several comparisons between the systems serving as a base for particular constructions directed the scholar’s attention to, possibly idempotent, strong conjunctions con nectives, whose corresponding truth functions were associative, commutative, nondecreasing and have 1 as its neutral (unit) element. Such functions were called t-norms. Accordingly, a binary function ∗ on [0,1] is a t-norm (triangular norm) if for any x, y, z ∈ [0, 1] x ∗ (y ∗ z) = (x ∗ y) ∗ z x∗y =y∗x if x ≤ y, then x ∗ z ≤ y ∗ z x ∗ 1 = x. Connectives corresponding to t-norms are conjunctions. Further to this one may also define t-conorms which serve as truth functions of disjunctions and, possibly do relate the two functions using appropriate function of negation. In Section 6 we � ukasiewicz already had examples of both, the t-norm (the function min(x, y) of L � ukasiewicz disjunction). conjunction) and t-conorm (the function max(x, y) of L H´ajek’s [1998] is the main study of fuzzy logics in the narrow sense. More precisely, the study of logics defined by continuous t-norms (a t-norm is continuous is considered in the mathematical terms is continuous as a mapping). Among the important continuous t-norms are the following: L � ukasiewicz t-norm x ∗ y = max(0, x + y − 1),
G¨ odel t-norm x ∗ y = min(x, y),
product t-norm x ∗ y = x·y ;
it may be of interest that all these functions have been used in numerous applica tions of fuzzy set theory as well as fuzzy logics (compare Section 14). The connectives defined through the continuous t-norm conjunctions (continuity with respect to the left argument is sufficient) are special. Accordingly, there is algebraically nice procedure relating them with implications, which have having good metalogical properties. Any such implication → is defined as residuum of a given t-norm ∗, i.e. x → y = max{ x : x ∗ z ≤ y}. H´ajek introduces the basic fuzzy propositional logic, BL-logic, as the logic of continuous t-norms on [0,1]. The language of BL comprises the connectives of conjunction &, implication → and the constant ⊥ of falsity. The semantics of BL is established by the function of t-norm, all other functions corresponding to the connectives are derived. A formula is a BL tautology if and only if under each valuation of propositional variables compatible with the functions of connectives ajek’s [1998] axiom system adequate for BL logic is the it takes the value 1. H´ following:
Many-valued Logic and its Philosophy
77
(H1) (α → β)→ ((β → γ) → (α → γ) (H2) (α & β) → α) (H3) (α & β) →(β & α) (H4) (α & (α → β))→(β & (β → α) (H5a) (α →(β → γ)) → ((α & β ) → γ) (H5b) ((α & β)→ γ)→ (α →(β → γ )) (H6) ((α → β) → γ)→ (((β → α) → γ) → γ) (H7) ⊥ → α . Any system of propositional logic determined by a t-norm in the way indicated may be received as a strengthening of BL. For instance, L � ukasiewicz, G¨ odel and product logics result form BL by addition of one axiom schema marked by the first letter of its name: (�L) ¬¬α → α (G) α → (α & β) (P) ¬¬α → ((α → (α & β)) → (β & ¬¬β)). BL extends to the basic fuzzy predicate logic in a standard way. H´ ajek [1998] shows interesting features of t-norm based predicate calculi, see also H´ajek and others [2001], Montagna [2000].
Tableaux and sets of signs Tableaux are among valuable tools for automated deduction, see Bolc, Borowik [2003], the area of interest of scholars working in logic programming, automated software development and verification. That explains still big interest in exploring and developing the tableaux methods in many-valued logic. H¨ahnle [1993] improved essentially the multiple-valued proving based on the standard tableaux for finite-valued logic. The solution, which has to decrease re dundancy of tableaux systems uses truth value sets of signs as prefixes instead ahnle, let us start with the Surma-Carnielli method of refuta signs. Following H¨ � ukasiewicz logic. tion illustrated with an example anchored in the three-valued L The tableaux rules mirror entries of the truth-tables of the connectives. Thus, for the disjunction ∨ characterized by the max function i ∨ j = max(i, j), the disjunctive formula signed with 1/2 , the rule emerges simply from the entry on the table described by the formula /2 (ϕ ∨ ψ) iff (1/2 ϕ and 0ψ) or (1/2 ϕ and 1/2 ψ) or (0ϕ and 1/2 ψ)
1
and it has the following form: /2 (ϕ ∨ ψ) 1 /2 ϕ 0ϕ 1 1 /2 ψ /2 ψ .
1 1
/2 ϕ 0ψ
78
Grzegorz Malinowski
As usual the vertical line signifies branching. It is obvious that in general the in crease of logical value increases both the number of rules and the size of branching. Given a propositional logic L defined by a finite matrix M = (AM , D) , where AM = (AM , f1 , . . . , fr ), the algebra of signs for L is defined as an algebra AS = (S, f1 , . . . , fr ) similar to AM with the operations defined as mappings from finite sequences of elements of S into sets of signs: f1 (S1 , . . . , Sm ) = {fi (j1 , . . . , jm )|jk ∈ Sk , 1 ≤ k ≤ m}. Any algebra AS defines a semantics of L in terms of truth values sets correspond ing to the members of S. Thus, for a formula ϕ = F (ϕ1 , . . . , ϕm ) two related interpretations f and f of F in A and AS are associated. The definition of an L−tableau rule,44 specifies the conditions ensuring all expected properties, that is, soundness, completeness, and some minimizing requirements, expressed in terms of linear subtrees called extensions. A collection of extensions is a conclusion of a tableau rule when it satisfies four conditions which relate possible functions of the matrix with extensions and homomorphisms from the language L into the algebra of signs AS . The properties, which the class of homomorphisms associated to a given logic must satisfy, imply a kind of minimality of a number of extensions as well as exhaustiveness of the covering of the truth tables of the connectives. A minimal set of homomorphisms associated to a connective immediately leads to a tableau rule. For the disjunction {1/2 }(ϕ ∨ ψ) in the three-valued logic already considered, this set of homomorphisms has two elements h1 and h2 : h1 (ϕ) = {1/2 }, h1 (ψ) = {0,1/2 } h2 (ϕ) = {0,1/2 }, h2 (ψ) = {1/2 }. This, in turn, yields the following rule: {1/2 }(ϕ ∨ ψ) {0, /2 }ϕ {1/2 }ϕ 1 {0, 1/2 }ψ . { /2 }ψ 1
The new paradigm requires some further changes in the conceptual environment. To provide them all one should collect and consider all possible queries or, at least, reduce them to a small set. H¨ahnle is aware of that, and he gives a definition of a contradiction set of signed formulas. A signed formula for which no rule is defined is self-contradictory. Such is {1/2 }Iϕ : no rule for Iϕ exists since I ranges over � 3 are {1/2 }Lϕ, the set {0,1}. Further examples of self-contradictory formulas in L 1 { /2 }M ϕ and {0, 1}T ϕ. A full tableau system for the propositional part p of the three-valued logic L �3 presented in H¨ ahnle [1993] employs the following set of signs: {{0, }, {1/2 }, {1}, {0, 1/2 }, {1/2 , 1}} 44 See
H¨ ahnle [1993, p. 34].
Many-valued Logic and its Philosophy
79
and the set of rules consisting of schemes such as (1) for every set in the family � 3 . We show how the sets of signs work just specified and for every connective of L � 3 tableau proof of validity of the formula on the example45 which presents the L ¬p ⊃ (∼ p ∧ ¬p) with two L � 3 -definable connectives: ∼ i = 0 if i = 1, ∼ i = 1 otherwise; i ⊃ j = j if i = 1, i ⊃ j = 1 otherwise. (1) [−] {0, 1/2 }(¬p ⊃ (∼ p ∧ ¬p)) | (2) [1] {1}¬p | (3) [1] {0, 1/2 }(∼ p ∧ ¬p) | (4) [2] {0}p (5) [3] {0, 1/2 } ∼ p (6) [5] {1}p closed with (4,6)
|
(7) [3] {0, 1/2 }¬p (8) [7] {1/2 , 1}p closed with (4,8)
Lattices of truth and information Belnap [1977; 1977a] defined a four-valued logic, primarily designed for solving some problems of relevant logics. However, the logic and its generalization oc curred also important for automated reasoning, Artificial Intelligence and Com puter Science applications. The original motivation is based on the idea, that the data, which are used by the computer or another inferential device, including a human being, may be inconsistent. Accordingly, given a state of affairs S, the data base may not contain any information concerning it, or it may contain contain the both: information that S obtains and that S does not obtain. The Belnap’s logic has to handle that situation and its set of epistemic values B4 consists of four elements: f (falsity), t (truth), ⊥ (undetermined) and (overdetermined): B4 = { ⊥ f , t , }. Two lattice orderings on B4 are possible: the knowledge ordering ≤ k , which has ⊥ as the minimal and as the maximal elements, and the truth ordering ≤ t having f as the minimal and t as the maximal elements. Both orderings may be represented in the following way: 45 Example
4.9 in H¨ ahnle [1993]; all tableaux rules are on pages 38 and 39.
80
Grzegorz Malinowski
knowledge �
�� � � �t f� � � �
�
� �
⊥
�
truth
The last figure shows two lattices: the knowledge lattice, showed directly and the truth lattice, which results if if the diamond is rotated counterclockwise and the axes change their menings. The two lattices are similar, though they are applicable in different situations. The knowledge lattice is useful for relevant logics and to paraconsistency — Belnap employs the matrix having it as universe with and t as two distinguished elements. The truth lattice suits better for computer science applications — in this case it is natural to take t as the only designated element. Considering two partial orderings of B4 simultaneously was the major intuition behind the concept of bilattice, an ingenious generalization of the Belnap’s setting, see Ginsberg [1987; 1988]. The main idea was to get arbitrary set of values with two partial orders forming two lattices related as in B4. A bilattice is a structure ( B, ≤ t , ≤ k , − ) such that: (1) (B, ≤t ) and (B, ≤k ) are complete lattices (2) x ≤t y implies that −y ≤t −x for all x, y ∈ B (3) x ≤k y implies that −x ≤k −y for all x, y ∈ B (4) − − x = x for all x ∈ B In the next figure we have an example of the bilattice having nine elements. Arieli and Avron [1994; 1996] introduced the concept of logical bilattice. Logical bilattice is a pair (B,F ), where B is a bilattice and F is a prime bifilter on B , i.e. a prime filter with respect to ≤ k and a prime filter with respect to ≤ t . The investigations of bilattices went into at least two directions: algebraic and logical — see e.g. Avron [1996]. Fitting introduced the notion of interlaced bilattice: a bilattice is interlaced if the lattice operations of inf and sup defined by the two orders are monotone with respect to both, the ≤ k and ≤ t . One of the most important results concerning bilattices is the characterisation of the class logical bilattices in terms of B4. Avron [1998] showed that B4 plays similar role among bilattices as the two-element Boolean algebra in the class of all Boolean algebras.
Many-valued Logic and its Philosophy
81
knowledge � (1, 1) �� � � 1 (1/2 , 1)� � (1, /2 ) � �
�� � � � � �� (0, 1) � (1/2 , 1/2 ) � (1, 0)
�� � �
� �
� � �� � �
1 (0, 1/2 )� � ( /2 , 0) � � �� (0, 0) � truth
16
APPLICATIONS
Projections of the expected applications always constituted a distinguished moti vation for many-valued logical constructions. Some these conceptions, as e.g. in L � ukasiewicz, were to be a philosophical revolution. And, though it is quite uneasy to say whether and to what extent these expectations came actually to vain there are some concrete applications of many-valued logics and algebras to philosophical logic and to such practical areas as the switching theory and Computer Science. Below we present some examples.
Independence of axioms The logical method of testing axioms independence using algebras and matrices � ukasiewicz. To demonstrate that an axiom system is is credited to Bernays and L independent one singles out a property, mostly validity, which is common to all axioms besides of one chosen and is inherited, via accepted rules of inference, by all theorems of the systems. The procedure being repeated as many times as there is the number of axioms in the system. The application of the method can be illustrated by the following example: Consider (¬, →)-system of the classical propositional calculus originating with L � ukasiewicz. Its axioms are:
82
Grzegorz Malinowski
(A1) (A2) (A3)
(¬p → p) → p p → (¬p → q) (p → q) → ((q → r) → (p → r)),
and the rules M P and SU B. Let now M(A1) = ({0, 1}, ¬1 , →, {1}) ,
M(A2) = ({0, 1}, ¬2 , →, {1})
be matrices wherein the implication connective → is determined classically (by the well-known truth table), ¬1 (0) = ¬1 (1) = 0 and ¬2 (0) = ¬2 (1) = 1. Moreover let M(A3) = ({0, 1/2 , 1}, ¬, →, {1}) be a matrix with the connectives defined by the tables:
α 0 1 /2 1
¬α 1 1 /2 1
→ 0 1 /2 1
0 1 1 0
1
/2 1 0 0
1 1 1 1
It is readily seen that E(M(A1) ), E(M(A2) ) and E(M(A3) ) are closed under (M P ) and (SU B) and that (1) (2) (3)
A1 ∈ E(M(A1) ), A1 ∈ E(M(A2) ), A1 ∈ E(M(A3) ),
A2 ∈ E(M(A1) ) A2 ∈ E(M(A2) ) A2 ∈ E(M(A3) )
and and and
A3 ∈ E(M(A1) ), A3 ∈ E(M(A2) ), A3 ∈ E(M(A3) ).
Therefore the axiomatics (A1)–(A3) is independent. The application of the method described is not limited to the logical calculi. The proofs of independence in set theory through the use of matrices built on the base of Boolean algebras were presented by Scott and Solovay [1969].
Formalization of intensional functions L � o´s [1948] showed that, under some reasonable assumptions, the formalization of functions of the kind “John believes that p” or, more accurately, “John asserts, that p” naturally leads to many-valued interpretation of the belief-operators within the scope of the system of the classical logic. All propositions “John asserts, that p” are clearly substitutions of the schema “x asserts, that p”, whose formal counterpart is a function Lxp, assigning logical value to each couple (name, proposition). L � o´s gives the following axioms for his system in an appropriate language L:
Many-valued Logic and its Philosophy
83
Lxp ≡ ¬Lx(¬p) Lx(Ai), where (Ai), i ∈ {1, 2, 3}, is the ith axiom
� ukasiewicz
of (¬, →)-system of CPC of L Lx(p → q) → (Lxp → Lxq)
(∀x)Lxp → p LxLxp ≡ Lxp
(L1) (L2i) (L3) (L4) (L5)
and accepts the rules: MP, the substitution rule and generalization. The intuitions captured by the author are justified: so, e.g. (L3) expresses the fact that everyone uses MP : asserting a conditional statement and its antecedent commits one to assert the consequent. (L4) says that a sentence acknowledged by everyone is a theorem of the system. The operators Lx, Ly, . . . are certainly not the only intensional functions of the system considered. What is more, the closed formulas of the language define intensional propositional functions i.e. connectives; here the case is the function S: Sα =df ∃x∃y(Lxα ∧ Ly(¬α)), which can be interpreted as “it is questionable, that α”. Intuitively, the definition conveys the thought that saying “it is debatable that α” means to say “two people exist such that one asserts α, and the other asserts not-α”. Any interpretation of the system of L-operators starts with the selection of a definite range of nominal variables and a proposition set. In the simplest case of two persons A and B who do not agree in all the issues the set of propositions Z is divided into four classes, denoted as: 0, 1/3 , 2/3 , 1. The first class, 0, con tains propositions which are acknowledged by neither person, the second class, 1/3 , propositions which A acknowledges and B does not, the third class, 2/3 , propo sitions which B acknowledges and A does not. Finally, the forth class, 1, all propositions acknowledged by A and B i.e. all logical theorems and perhaps other propositions acknowledged by both men. Identifying the acceptance of a proposi tion α by a person s with the formula Lsα we get a truth-table assigning to classes 0, 1/3 , 2/3 , 1 the pairs of logical values of truth (t) and falsity (f). In turn, making use of truth-tables for t and f we get the characterization of implication, negation and the connective S by means of the tables whose elements are the symbols of the four considered classes of propositions.46 L 0 1 /3 2 /3 1
A f t f t
B f f t t
α 0 1 /3 2 /3 1
¬α 1 2 /3 1 /3 0
Sα 0 1 1 0
→ 0 1 /3 2 /3 1
0 1 2 /3 1 /3 0
1
/3 1 1 1 /3 1 /3
2
/3 1 2 /3 1 2 /3
1 1 1 1 1
46 0,1/ ,2/ , 1 are identified with pairs (x, y), where x, y ∈ {f, t}, defined by the table for L. 3 3 The connectives are defined just as in the product of matrices i.e. ¬(x, y) = (¬x, ¬y) and (x1 , y1 ) → (x2 , y2 ) = (x1 → x2 , y1 → y2 ).
84
Grzegorz Malinowski
L � o´s suggests that the objects 0, 1/3 , 2/3 , 1 may be treated as logical values. He further considers the matrix I4 = ({0, 1/3 , 2/3 1}, ¬, →, {1}) showing that E(I4) = TAU T {¬, →} (the set of classical (¬, →)-tautologies), and hence that many-valuedness of this system has but formal character. The shifting of L � o´s interpretation onto the cases with more persons is straight forward, and it results in next formally many-valued versions of CPC (described by matrices with more than four elements).
Many-valued algebras and switching theory Soon after the successful applications of the classical logic, Boolean algebras and other algebraic structures (e.g. groups) in switching theory, in the 1950s, the schol ars centered the interests on the possibility of the use of many-valued logic algebras for similar purposes (see e.g. Epstein, Frieder and Rine [1974]). These interests brought about the birth of several techniques of the analysis and synthesis of elec tronic circuits and relays based (mainly) on Moisil and Post algebras (see Rine [1977]). Below, we confine ourselves to some remarks justifying the purposefulness of using many-valued algebras in switching and relay circuits theory. The most elementary composite of the traditional electronic circuit is a mechanical contact opening and closing some fragment of an electrical network. The switch over of contacts is affected mechanically or electromechanically (i.e. using relays). And, among the contacts of a given network one may find such pairs of contacts which according to the technical assumptions have to change their positions into comple mentary simultaneously. The simplest example of such situation is the gear of two oppositely oriented contacts x1 and x2 positioned in parallel branches of a circuit (see Fig. 1): x1 is normally closed while x2 normally open. When considering the ideal model of the circuit one assumes x1
x2 Fig. 1
x1 •��◦ •��◦ •��◦
(1/2 )
x2 •��◦ •��◦
(0)
•��◦
(1)
Fig. 2
that both contacts react momentarily to an affection and thus stroking, as shown at Fig. 2, from the state (1) to (0). Practically, however, it may happen that x1 will open still before x2 would be closed and, consequently, contrary to the technical presumptions the gear during a time moment will be open. That is just the
Many-valued Logic and its Philosophy
85
reason for such a modelling in which the third state (1/2 ) (see Fig. 2) is considered; the table bez x1 x2 forehand characterizes the “real” switch-function 1 1 1 1 as a function of states and contact (1 inside the /2 0 1 table denotes normal contact’s state and 0 its de0 0 0 nial). On the other hand, one also may read the table treating x1 and x2 as (one-argument) functions of states i.e. of z, and their values as states as well putting: x1 = s1 (z), x2 = s2 (z) . Let us no tice that then s1 and s2 are Moisil’s operations on {0, 1/2 , 1} . Subsequently, to describe any network built of the contacts x1 , x2 and their complements x1, x2 one should define binary operations ∪ and ∩ corresponding to two pos sible types of connections and unary operation N such that xi = N xi (i = 1, 2) and that N N z = z for z ∈ {0, 1/2 , 1} . It appears that the most accurate ways of introducing these operations leads to the three-valued Moisil algebra on {0, 1/2 , 1} : ({0, 1/2 , 1}, ∪, ∩, N, s1 , s2 ). A generalization of the outlined construction onto the case of any number of contacts similarly results in n-valued algebras. The algebraic treatment of switch ing devices aims at providing several techniques of the analysis, the synthesis and the minimalization of multiplex networks. The most important advantage of the many-valued approach is the possibility of elimination of possible switching dis turbance through the algebraic synthesis of the networks, see e.g. Moisil [1966]. Application of many-valued algebras is not limited to binary contacts. Investi gations concerning multi-stable contacts and switches have also been undertaken. However, according to difficulties with technical realizations of devices working on voltage-mode and the progress of technology of binary highly integrated circuits these activities are not very common. Still, however, many-valued constructions attract attention of engineers. Thus, for instance, multiple values may be useful for describing transistors. Hayes [1986], H¨ahnle and Kernig [1993] give an example of such modelling M OS transistors. Due to a degradation of signals, a M OS transistor has different signal levels at source and terminals. It occurs that the natural way of modelling leads to a seven-valued , ⊥), whose values are organized in a form of a lattice logic N = (F, T, F, T, , �� � �
� T
F� � � �
� � �
� � � � � T F� � � � � �� ⊥
86
Grzegorz Malinowski
where the values represent respectively: F and T — full strength signals, F and — values which represent two modes of faulty nodes, T — degraded signals, , 47 and ⊥ — “no signal”). The reader interested in the current state of investigation in this field is advised to consult “Computer”, IEEE Computer Society monthly as well as the yearly editions of this influential American organization “Proceedings of the MultipleValued Symposia”.
Many-valuedness in Computer Science The full scale hardware realizations of ternary computers were successfully com pleted at least twice: in 1958 the arithmetical SETUN in USSR and in 1973 logico arithmetical TERNAC in USA. However, just the first emulation of TERNAC proved that both the speed and price are on the order of magnitude of the speed and price of binary computers. Since further experiments also showed the neces sity of complication of programming languages, more attention has been directed towards the using many-valued algebras for synthesis and construction of hardware devices working with 2n voltage levels (n ≥ 2), especially memories (see Epstein, Frieder and Rine [1974], Bauer et al. [1995]). Post algebras found an important application in the systematization of the oretical research concerning programs and higher level programming languages which contain instructions branching programs, such as e.g. CASE, SELECT etc. The application of these instructions considerably simplifies programs thus making them more readible. In turn, the structure reconstruction of a branched program naturally leads to Post algebra of an order n. The typical CASE (or SELECT ) situation is that in which one the (sub)programs P 1, . . . , P n should be performed according to whether conditions W 1 or . . . or W n are satisfied. Then, the con stant functions of Post algebra, e1 , . . . , en , may be interpreted as devices which keep track of which of W 1, . . . , W n are true. The most powerful tool of the contemporary methodology of programming languages, algorithmic logic (see Salwicki [1970]) is formulated in the language containing operators which represent composition, branching and iteration op erations on programs. The systems of this logic contain expressions represent ing programs and formulas describing properties of these programs. Rasiowa’s ω + -valued extension of algorithmic logic is not only fully adapted to arbitrary “wide” branching programs but it also constitutes a starting point for other more advanced logical constructions (see Rasiowa [1977]). Its semantics is based on Post algebras of order ω + defined similarly as Post algebras of order n in Rousseau version: the simplest algebra of that kind is of the following form: Pω = ({e0 , . . . , eω }, ∪, ∩, →, −, {Dk }k<ω , {ei }0≤i≤ω ) (0, 1, . . . , ω are ordi nal numbers), where: −eω = e0 < e1 < . . . < eω , ei ∪ ek = emax (i, k) , ei ∩ ek = emin (i, k) , ei → ek = eω when i ≤ k, ei → ek = ek when i > k, −ei = e0 for 47 See
also H¨ ahnle [1993].
Many-valued Logic and its Philosophy
87
i = 0, −e0 = eω , Di (ek ) = eω if i ≤ k and Di (ek ) = e0 otherwise (compare Section 5). Algorithmic logic is among the main predecessors of the recent outcome of com puting theory called dynamic logic, see e.g. Harel [1984]. The term dynamic logic is the generic name given to logical systems appropriate for reasoning about changes from one state to another, which ultimately may also represent programs. Though it is grounded in features of programming and program verification, dynamic logic borrowed heavily from modal logic and has its autonomous philosophical impor tance. Many-valued semantics founded on several algebraic structures have been widely used in logic programming. The framework for applications of bilattices in seman tics of logic programming is discussed in Fitting [1991].
BIBLIOGRAPHY [Ackermann, 1967*] R. Ackermann. Introduction to many-valued logics. Routledge and Kegan Paul, London, 1967. [Arieli and Avron, 1994] O. Arieli and A. Avron. Logical bilattices and inconsistent data. In Proceedings of the 9th IEEE Annual Symposium on logic and Computer Science. IEEE Press, 468–476, 1994. [Arieli and Avron, 1996] O. Arieli and A. Avron. Reasoning with logical bilattices. Journal of Logic, Language and Information, 5, no. 1, 25–63, 1996. [Avron, 1996] A. Avron. The structure of interlaced bilattices. Journal of Mathematical Struc tures in Computer Science, 6, no. 1, 287–299, 1996. [Avron, 1998] A. Avron. The value of the four values. Artificial nIntelligence, 102, 97–141, 1998. [Baaz et al., 1993] M. Baaz, C. Ferm¨ uller, and R. Zach. Systematic construction of natural de duction for many-valued logics. Proceedings of the 23rd International Symposium on Multiplevalued Logic, IEEE Press, Los Gatos, CA, 208–213, 1993. [Batens, 1980] D. Batens. A completeness-proof method for extensions of the implicational frag ment of the propositional calculus. Notre Dame Journal of Formal Logic, 20, 509–517, 1980. [Batens, 1982] D. Batens. A bridge between two-valued abd many-valued semantic systems: Ntuple semantics. Proceedings of the 12rth International Symposium on Multiple-valued Logic, IEEE Press, Los Angeles, 121–133, 1982. [Becchio and Pabion, 1977] D. Becchio and J.-F. Pabion. Gentzen’s techniques in the threevalued logic of L � ukasiewicz (Abstract). Journal of Symbolic Logic, 42(2), 123–124, 1977. [Bellman and Giertz, 1973] R. E. Bellman and M. Giertz. On the analytic formalism of the theory of fuzzy sets. Information Sciences, 5, 149–156, 1973. [Bellman and Zadeh, 1977] R. E. Bellman and L. A. Zadeh. Local and fuzzy logics. In Dunn, J. M. and Epstein, G. (eds) Modern uses of multiple-valued logic. D. Reidel, Dordrecht, 105–165, 1977. [Belluce and Chang, 1963] L. P. Belluce and C. C. Chang. A weak completeness theorem for infinite-valued first-order logic. The Journal of Symbolic Logic, 28, 43–50, 1963. [Belnap, 1970] N. D. Belnap. Conditional assertion and restricted quantification. Noˆ us, 4, 1–13, 1970. [Belnap, 1977] N. D. Belnap. A useful four-valued logic. In Dunn, J. M. and Epstein G. (eds) Modern uses of multiple-valued logic. D. Reidel, Dordrecht, 8–37, 1977. [Belnap, 1977a] N. D. Belnap. How computer should think. In Ryle G. (ed.) Contemporary aspects of philosophy. Oriel Press, 30–56, 1977. [Beth, 1956] E. W. Beth. Semantic construction of intuitionistic logic. Mededelingen der konin klijke Nederlandse Akademie van Wetenhappen, new series, 19, no. 11, 357–388, 1956.
88
Grzegorz Malinowski
[Bochvar, 1938] D. A. Bochvar. Ob odnom tr´ehznaˇ cnom isˇcisl´ enii i ´ ego prim´en´ enii k analizu para dosov klassiˇ c´ eskogo rasˇsirennogo funkcjonal’nogo isˇcisl´ enia (On a three-valued calculus and its ematiˇ c´ eskij application to analysis of paradoxes of classical extended functional calculus). Mat´ Sbornik, 4, 287–308, 1938. [Bolc and Borowik, 2003*] L. Bolc and P. Borowik. Many-valued logics. Vol. 2: Automated reasoning and practical applications. Springer Verlag, 2003. [Carnielli, 1987] W. A. Carnielli. Systematization of finite-valued logics through the method of tableaux. Journal of Symbolic Logic, 52(2), 473–493, 1987. [Carnielli, 1991] W. A. Carnielli. On sequents and tableaux for many-valued logics. Journal of Symbolic Logic, 8(1), 59–76, 1991. [Chang, 1958a] C. C. Chang. Proof of an axiom of L � ukasiewicz. Transactions of the American Mathematical Society, 87, 55–56, 1958. [Chang, 1958b] C. C. Chang. Algebraic analysis of many-valued logics. Transactions of the American Mathematical Society, 88, 467–490, 1958. [Chang, 1959] C. C. Chang. A new proof of the completeness of the L � ukasiewicz axioms. Trans actions of the American Mathematical Society, 93, 74–80, 1959. [Chang, 1963] C. C. Chang. The axiom of comprehension in infinite-valued logic. Mathematica Scandinavica, 13, 9–30, 1963. [Chang, 1966] C. C. Chang and H. J. Keisler. Continuous model theory. Princeton University Press, Princeton, New Jersey, 1966. [Chang and Keisler, 1973] C. C. Chang and H. J. Keisler. Model theory. North-Holland, Ams terdam, 1973. [Cignoli, 1980] R. Cignoli. Some algebraic aspects of many-valued logics. In Arruda, A. I. , da Costa, N. C. A. and Sette, A. M. (eds) Proceedings of the Third Brasilian Conference on Mathematical Logic, Sa˜ o Paulo, 49–69, 1980. [Cignoli, 1982] R. Cignoli. Proper n-valued L � ukasiewicz algebras as S-algebras of L � ukasiewicz n-valued propositional calculi. Studia Logica, 41, 3–16, 1982. [Cignoli et al., 1999*] R. Cignoli, I. M. L. D’Ottaviano, and D. Mundici. Foundations of manyvalued reasoning, Trends in Logic: Studia Logica Library, vol. 7. Kluwer Academic Publishers, Dordrecht, 1999. [Czelakowski, 2001] J. Czelakowski. Protoalgebraic logics. Trends in Logic: Studia Logica Li brary, vol. 10. Kluwer Academic Publishers, Dordrecht, 2001. [da Costa, 1974] N. C. A. da Costa. On the theory of inconsistent formal systems Notre Dame Journal of Formal Logic, 15, 497–510, 1974. [D’Agostino, 1999] M. D’Agostino. Tableaux methods for classical propositional logic. In ahnle, R., and Posegga, J. (eds) Handbook of tableau methods. D’Agostino, M., Gabbay, D., H¨ Kluwer Academic Publishers, Dordrecht, 45–123, 1999. [Dalen, 1986] D. van Dalen. Intuitionistic logic. In Gabbay, D. and Guenthner, F. (eds) Hand book of philosophical logic, vol. III. D. Reidel, Dordrecht, 225–339, 1986. [Dalen, 1986a] D. van Dalen. Intuitionistic logic. In Gabbay, D. and Guenthner, F. (eds) Hand book of philosophical logic, vol. III. D. Reidel, Dordrecht, 225–339, 1986. [Dummett, 1959] M. Dummett. A propositional matrix with denumerable matrix. The Journal of Symbolic Logic, 24, 97–106, 1969. [Dunn and Hardegree, 2001] J. M. Dunn and G. M. Hardegree. Algebraic methods in philosoph ical logic. Oxford Logic Guides 41, Clarendon Press, Oxford, 2001. [Dwinger, 1977] Ph. Dwinger. A survey of the theory of Post algebras and their generaliza tions. In Dunn, J. M. and Epstein, G. (eds) Modern uses of multiple-valued logic. D. Reidel, Dordrecht, 53–75, 1977. [Epstein, 1960] G. Epstein. The lattice theory of Post algebras. Transactions of the American Mathematical Society, 95, 300–317, 1960. [Epstein et al., 1974] G. Epstein, G. Frieder, and D. C. and Rine. The development of multiplevalued logic as related to Computer Science. Computer , 7, no. 9, 20–32, 1974. [Fenstad, 1964] J. E. Fenstad. On the consistency of the axiom of comprehension in the Lukasiewicz � infinite-valued logic. Mathematica Scandinavica, 14, 64–74, 1964. [Finn and Grigolia, 1980] V. Finn and R. Grigolia. Bochvar’s algebras and corresponding propo sitional calculi . Bulletin of the Section of Logic, 9, no. 1, 39–45, 1980. [Fitting, 1969] M. C. Fitting. Intuitionistic Logic, Model Theory and Forcing. North-Holland, Amsterdam, 1969.
Many-valued Logic and its Philosophy
89
[Fitting, 1991] M. C. Fitting. Bilattices and the semantics of logic programming. Journal of Logic Programming, 11, no. 2, 91–116, 1991. [Gaines, 1976a] B. R. Gaines. Foundations of fuzzy reasoning. International Journal of Man– Machine Studies, 8, 623–668, 1976. [Gaines, 1976b] B. R. Gaines. General fuzzy logics. In Proceedings of the 3rd European Meeting on Cybernetics and Systems Research. Vienna, 1976. [Gentzen, 1934] G. Gentzen. Untersuchungen uber ¨ das Logische Schliessen. Mathematisch Zeitscrift, 39, 176–210, 405–431, 1934. [Giles, 1974] R. Giles. A non-classical logic for physics. Studia Logica, 33, 397–416, 1974. [Ginsberg, 1987] M. L. Ginsberg. Multi-valued logics. In Ginsberg, M. L. (ed.) Readings in non-monotonic reasoning. Los-Altos, CA, 251–258, 1987. [Ginsberg, 1988] M. L. Ginsberg. Multi-valued logics: a uniform approach to reasoning in AI. Computer Intelligence, 4, 256–316, 1988. [G¨ odel, 1930] K. G¨ odel. Die Vollst¨ andigkeit der Axiome des logischen Funktionenkalk¨ uls. ur Mathematik und Physik , 37, 349–360, 1930. Monatschefte f¨ [G¨ odel, 1932] K. G¨ odel. Zum intuitionistischen Aussagenkalk¨ ul. Akademie der Wissenschaften in Wien, Mathematischnaturwissenschaftliche Klasse. Anzeiger, LXIX, 65–66, 1932. [G¨ odel, 1933] K. G¨ odel. Eine Interpretation des intuitionistischen Aussagenkalk¨ uls. Ergebnisse eines mathematischen Kolloquiums, IV, 34–40, 1933. [Goguen, 1969] J. A. Goguen. The logic of inexact concepts. Synthese, 19, 325–373, 1969. [Gonseth, 1941] F. Gonseth, ed. Les entretiens de Zurich sur les fondements et la m´ ethode des sciences math´ ematiques 6–9 d´ ecembre 1938 . Zurich, 1941. ¨ [Gottwald, 1981] S. Gottwald. Fuzzy-Mengen und ihre Anwendungen. Ein Uberblick. Elektron ische Informationsverarbeitung und Kybernetik , 17, 207–233, 1981. [Gottwald, 2001] S. Gottwald. A Treatise on Many-Valued Logics. Studies in Logic and Com putation, vol. 9, Research Studies Press, Baldock, Hertfordshire, England, 2001. [Grigolia, 1977] R. Grigolia. Algebraic analysis of L � ukasiewicz–Tarski’s n-valued logical systems. ojcicki, R. and Malinowski, G. (eds) Selected papers on L � ukasiewicz sentential calculi. In W´ Ossolineum, Wroc�law, 81–92, 1977. [H¨ ahnle, 1993*] R. H¨ ahnle. Automated deduction in multiple-valued logics, International Series of monographs on Computer Science, vol. 10. Oxford Univerity Press, 1993. [H¨ ahnle, 1999] R. H¨ ahnle. Tableaux for many-valued logics. In D’Agostino, Gabbay, D., H¨ ahnle, R., and Posegga, J. (eds) Hanbook of Tableaux Methods. Kluwer, Dodrdrecht, 529–580, 1999. [H¨ ahnle, 2001] R. H¨ ahnle. Advanced many-valued logics. In Gabbay, D. and Guenthner, F. (eds) Handbook of philosophical logic, 2nd ed., vol. II. D. Reidel, Dordrecht, 297–395, 2001. [H¨ ahnle and Kernig, 1993] R. H¨ ahnle and W. Kernig. Verification of switch level designs with many-valued logic. In Voronkov, A.(eds Proceedings LPAR’93, St. Petersburg, Russia , Lec ture Notes on Computer Science, vol. 698. Springer Verlag, 158–169, 1993. [H´ ajek, 1998*] P. H´ ajek. Metamathematics of fuzzy logics, Trends in Logic: Studia Logica Li brary, vol. 4. Kluwer Academic Publishers, Dordrecht, 1998. [H´ ajek et al., 2000] P. H ’ajek, J. Paris and J. Sheperdson. The liar paradox and fuzzy logic, The Journal of Symbolic Logic, 65, 339–346, 2000. [Halld´ en, 1949] S. Halld ’en. The logic of nonsense, Uppsala Universitets Arsskrift, Uppsala, 1949. [Harel, 1984] D. Harel. Dynamic logic. In Gabbay, D. and Guenthner, F. (eds) Handbook of philosophical logic, vol. II. D. Reidel, Dordrecht, 497–604, 1984. [Hay, 1963] L. S. Hay. Axiomatization of the infinite-valued predicate calculus. The Journal of Symbolic Logic, 28, 77–86, 1963. [Hayes, 1986] J. P. Hayes. Pseudo-Booleanlogic circuits. IEEE Transactions on Computers, C 35(7),602–612, 1986. [Heyting, 1966] A. Heyting. Intuitionism. An introduction. North-Holland, Amsterdam, 1966. [Ja´skowski, 1934] S. Ja´skowski. On the rules of suppositions in formal logic. Studia Logica, 1, 5–32, 1934. [Ja´skowski, 1936] S. Ja´skowski. Recherches sur le syst`eme de la logique intuitioniste. Actes du Congr` es International de Philosophie Scientifique VI . Philosophie de math´ematiques. Actu alit´ es scientifiques et industrielles 393, Paris, 58–61, 1936. [Johansson, 1936] I. Johansson. Der Minimalkalk¨ ul, ein reduzierter intuitionistischer Formalis mus. Compositio Mathematicae, 4, 119–136, 1936.
90
Grzegorz Malinowski
[Kleene, 1938] S. C. Kleene. On a notation for ordinal numbers. The Journal of Symbolic Logic, 3, 150–155, 1938. [Kleene, 1952] S. C. Kleene. Introduction to metamathematics. North-Holland, Amsterdam, 1952. [K¨ orner, 1966] S. K¨ orner. Experience and theory. Routledge and Kegan Paul, London, 1966. [Kotarbi´ nski, 1913] T. Kotarbi´ nski. Zagadnienie istnienia przysz�lo´sci (The problem of existence of the future). Przegl¸ ad Filozoficzny, VI.1, 1913. [Kotas and da Costa, 1980] J. Kotas and N. C. A. da Costa. Some problems on logical matrices and valorizations. In Arruda, A. I. , da Costa, N. C. A. and Sette, A. M. (eds) Proceedings of o Paulo, 158–169, 1980. the Third Brasilian Conference on Mathematical Logic, Sa˜ [Lo´ � s, 1948] J. Lo´ � s. Logiki wielowarto´sciowe a formalizacja funkcji intensjonalnych (Many-valued logics and the formalization of intensional functions). Kwartalnik Filozoficzny, 17, 59–78, 1948. [Lukasiewicz, � 1906] J. Lukasiewicz. � Analiza i konstrukcja poj¸ecia przyczyny. Przegl¸ ad Filo zoficzny, 105–179, 1906. [Lukasiewicz, � 1910] J. Lukasiewicz. � O zasadzie sprzeczno´sci u Arystotelesa. Studium krytyczne. Krak´ ow, 1910; English tr. On the principle of contradiction in Aristotle. Review of Meta physics, XXIV, 1971. [Lukasiewicz, � 1913] J. Lukasiewicz. � Die logischen Grundlagen der Wahrscheinlichkeitsrechnung. Krak´ ow, 1913; English tr. Logical foundations of probability theory. In Borkowski, L. (ed.) Selected works. North-Holland, Amsterdam, 16–63. [Lukasiewicz, � 1920] J. L � ukasiewicz. O logice tr´ ojwarto´sciowej. Ruch Filozoficzny, 5, 170–171, 1920. English tr. On three-valued logic. In Borkowski, L. (ed.) Selected works. North-Holland, Amsterdam, 87–88. [Lukasiewicz, � 1929] J. Lukasiewicz. � Elementy logiki matematycznej . Skrypt. Warszawa, 1929 (II edn, PWN, Warszawa 1958); English tr. Elements of Mathematical Logic translated by Wojtasiewicz, O. Pergamon Press, Oxford, 1963. [Lukasiewicz, � 1930] J. L � ukasiewicz. Philosophische Bemerkungen zu mehrwertigen Systemen des Aussagenkalk¨ uls. Comptes rendus des s´ eances de la Soci´ et´ e des Sciences et des Lettres de Varsovie Cl. III , 23, 51–77, 1930; English tr. Philosophical remarks on many-valued systems of propositional logic. In McCall, S. (ed.) Polish Logic 1920–1939 . Clarendon Press, Oxford, 1967, 40–65. [Lukasiewicz, � 1953] J. L � ukasiewicz. A system of modal logic. Journal of Computing Systems, 1, 111–149, 1953. [Lukasiewicz, � 1961] J. Lukasiewicz. � Z zagadnie´ n logiki i filozofii. Pisma wybrane. PWN, Warszawa, 1961; English tr. Selected works (ed. Borkowski, L.). North-Holland, Amsterdam, 1970. [Lukasiewicz � and Tarski, 1930] J. Lukasiewicz � and A. Tarski. Untersuchungen uber ¨ den Aus sagenkalk¨ ul. Comptes rendus des s´ eances de la Soci´ et´ e des Sciences et des Lettres de Varsovie Cl. III, 23, 30–50, 1930. [MacColl, 1897] H. MacColl. Symbolical reasoning. Mind, 6, 493–510, 1897. [McNaughton, 1951] R. McNaughton. A theorem about infinite-valued sentential logic. The Journal of Symbolic Logic, 16, 1–13, 1951. [Malinowski, 1977] G. Malinowski. Classical characterization of n-valued L � ukasiewicz calculi. Reports on Mathematical Logic, 9, 41–45, 1977. [Malinowski, 1990] G. Malinowski. Q-consequence operation. Reports on Mathematical Logic, 24, 49–59, 1990. [Malinowski, 1993*] G. Malinowski. Many-valued logics. Oxford Logic Guides 25, Clarendon Press, Oxford, 1993. [Malinowski, 1994] G. Malinowski. Inferential many-valuedness. In Wole´ nski, J. (ed.) Philosoph ical logic in Poland, Synthese Library, Kluwer Academic Publishers, Dordrecht, 74–84, 1994. [Malinowski, 2002] G. Malinowski. Referential and inferential many-valuedness. In W. A. Carnielli,W. A.,Coniglio, M. E.I. and D’Ottaviano M. L. (ed.) Paraconsistency the logical way to the inconsistent, Lecture Notes in Pure and Applied Mathematics, vol. 228, Marcel Dekker Inc., 341–352, 2002. [Marciszewski, 1987] W. Marciszewski, ed. Logika formalna. Zarys encyklopedyczny z zas tosowaniem do informatyki i lingwistyki (Formal logic: an encyclopaedic outline with in formatics and linguistics applied). PWN, Warszawa, 1987.
Many-valued Logic and its Philosophy
91
[Meredith, 1958] C. A. Meredith. The dependence of an axiom of L � ukasiewicz. Transactions of the American Mathematical Society, 87, 54, 1958. [Moh Shaw-Kwei, 1954] Moh Shaw-Kwei. Logical paradoxes for many-valued systems. The Journal of Symbolic Logic, 19, 37–40, 1954. [Moisil, 1966] G. Moisil. Zastosowanie algebr Lukasiewicza � do teorii uk�lad´ ow przeka´znikowo � ukasiewicz algebras to the study of relay-contact networks). Os stykowych (Application of L solineum, Wroc�law (vol. II, 1967 edn), 1966. [Moisil, 1972] G. Moisil. Essais sur les logiques non-chrisipiennes. Editions de l’Acad´emie de la Republique Socialiste de Roumanie. Bucharest, 1972. [Montagna, 2000] F. Montagna. An algebraic approach to propositional fuzzy logic, Journal of Logic, Language and Information, Special issue on many-valued Logics of Uncertainty. Mundici, D. (ed.), 9 (1), 91–124, 2000. [Morgan, 1976] C. G. Morgan. A resolution principle for a class of many-valued logics. Logique et Analyse, 19 (74-75-76), 311–339, 1976. [Mostowski, 1961] A. Mostowski. Axiomatizability of some many-valued predicate calculi. Fun damenta Mathematicae, 50, 165–190, 1961. [Nowak, 1988] M. Nowak. O mo˙zliwo´sci interpretowania tr´ ojwarto´sciowej logiki L � ukasiewicza metod¸ a S�lupeckiego (On the possibility of interpreting the three-valued Lukasiewicz � logic using S�lupecki’s method). Acta Universitatis Lodziensis, Folia Philosophica, 5, 3–13, 1988. [Or�lowska, 1967] E. Or�lowska. Mechanical proof procedure for the n-valued propositional cal emie Polonaise des Sciences, S´ erie des sciences math´ ematiques, culus. Bulletin de l’Acad´ astronomiques et physiques, 15 (8), 537–541, 1967. [Panti, 1999] G. Panti. Varieties of MV-algebras, Journal of Applied Non-classical Logics, Spe cial issue on many-valued logics. Carnieli, W. A. (ed.), 141–157, 1999. [Peirce, 1885] C. S. Peirce. On the algebra of logic: a contribution to the philosophy of notation. American Journal of Mathematics, 7, 180–202, 1885. [Picard, 1935] S. Picard. Sur les fonctions d´efinies dans les ensembles finis quelconques. Funda menta Mathematicae, 24, 198–302, 1935. [Post, 1920] E. L. Post. Introduction to a general theory of elementary propositions. Bulletin of the American Mathematical Society, 26, 437, 1920. [Post, 1921] E. L. Post. Introduction to a general theory of elementary propositions. American Journal of Mathematics, 43, 163–185, 1921. [Rasiowa, 1974*] H. Rasiowa. An algebraic approach to non-classical logics. North-Holland, Am sterdam; PWN, Warsaw, 1974. [Rasiowa, 1977] H. Rasiowa. Many-valued algorithmic logic as a tool to investigate programs. In Dunn, J. M. and Epstein, G. (eds) Modern uses of multiple-valued logic. D. Reidel, Dordrecht, 79–102, 1977. [Rasiowa, 1991] H. Rasiowa. On approximation logics: A survey. University of Warsaw, War saw, 1991. [Rasiowa and Sikorski, 1963] H. Rasiowa and R. Sikorski. The Mathematics of Metamathemat ics. PWN, Warsaw, 1963. [Reichenbach, 1935] H. Reichenbach. Wahrscheinlichkeitslehre. Leiden, 1935; English tr. The theory of probability. University of California Press, Berkeley, 1949. [Rescher, 1969*] N. Rescher. Many-valued logic. McGraw-Hill, New York, 1969. [Rine, 1977] D. C. Rine, ed. Computer Science and Multiple-valued Logic. Theory and Aplica tions. Amsterdam, North-Holland, 1977. [Rose and Rosser, 1958] A. Rose and J. B. Rosser. Fragments of many-valued statement calculi. Transactions of the American Mathematical Society, 87, 1–53, 1958. [Rosenbloom, 1942] P. C. Rosenbloom. Post algebra. I. Postulates and general theory. American Journal of Mathematics, 64, 167–188, 1942. [Rosser and Turquette, 1952*] J. B. Rosser and A. R. Turquette. Many-valued logics. NorthHolland, Amsterdam, 1952. [Rousseau, 1967] G. Rousseau. Sequents in many-valued logic. Fundamenta Mathematicae, LX, 1, 23–33, 1967. [Rousseau, 1969] G. Rousseau. Logical systems with finitely many truth-values. Bulletin de l’Acad´ emie Polonaise des Sciences, S´ erie des sciences math´ ematiques, astronomiques et physiques, 17, 189–194, 1969. [Rutledge, 1959] J. D. Rutledge. A preliminary investigation of the infinitely many-valued pred icate calculus. Ph.D. thesis, Cornell University, 1959.
92
Grzegorz Malinowski
[Salwicki, 1970] A. Salwicki. Formalized algorithmic languages. Bulletin de l’Acad´ emie Polon erie des sciences math´ ematiques, astronomiques et physiques, 18, 227– aise des Sciences, S´ 232, 1970. [Scarpelini, 1962] B. Scarpelini. Die Nichtaxiomatisierbarkeit des unendlichwertigen Pr¨ adikatenkalk¨ uls von L � ukasiewicz. The Journal of Symbolic Logic, 17, 159–170, 1962. [Schr¨ oter, 1955] K. Schr¨ oter. Methoden zur Axiomatisierung beliebiger Aussagen- und Pr¨ adikatenkalk¨ ule. Zeitschrift f¨ ur Mathematische Logik und Grunglagen der Mathematik , 1, 241–251, 1955. [Scott, 1973] D. Scott. Background to formalisation. In Leblanc, H. (ed.) Truth, Syntax and Modality. North-Holland, Amsterdam, 244–273, 1973. [Scott, 1974] D. Scott. Completeness and axiomatizability in many-valued logic. In Henkin, L. et al. (eds) Proceedings of Tarski Symposium. Proceedings of Symposia in Pure Mathematics, vol. 25, 411–436, 1974. [Scott and Solovay, 1969] D. Scott and R. Solovay. Boolean valued models for set theory, Pro ceedings of the American Mathematical Society Summer Inst. Axiomatic Set Theory 1967 . University of California, Los Angeles. Proceedings of Symposia in Pure Mathematics, 13, 1969. [Skolem, 1957] T. Skolem. Bemerkungen zum Komprehensionsaxiom. Zeitschrift f¨ ur Mathema tische Logik und Grundlagen der Mathematik , 3, 1–17, 1957. [S�lupecki, 1936] J. S�lupecki. Der volle dreiwertige Aussagenkalk¨ ul. Comptes rendus des s´ eances et´ e des Sciences et des Lettres de Varsovie Cl. III , 29, 9–11, 1936; English tr. de la Soci´ The full three-valued propositional calculus. In McCall, S. (ed.) Polish Logic 1920–1939 . Clarendon Press, Oxford, 1967, 335–337. [S�lupecki, 1939a] J. S�lupecki. Kryterium pe�lno´sci wielowarto´sciowych system´ ow logiki zda´ n (A criterion of completeness of many-valued systems of propositional logic). Comptes rendus des s´ eances de la Soci´ et´ e des Sciences et des Lettres de Varsovie Cl. III , 32, 102–109, 1939. [S�lupecki, 1939b] J. S�lupecki. Dow´ od aksjomatyzowalno´sci pe�lnych system´ ow wielowarto´scio wych rachunku zda´ n (Proof of the axiomatizability of full many-valued systems of propo eances de la Soci´ et´ e des Sciences et des Lettres de sitional calculus). Comptes rendus des s´ Varsovie Cl. III , 32, 110–128, 1939. [S�lupecki, 1964] J. S�lupecki. Pr´ oba intuicyjnej interpretacji logiki tr´ ojwarto´sciowej L � ukasiewicza � ukasiewicz logic). In Rozprawy (An attempt of intuitionistic interpretation of three-valued L Logiczne. PWN, Warszawa, 1964. [Stachniak, 1996] Z. Stachniak. Resolution proof systems: an algebraic theory. Kluwer, Dor drecht, 1996. [Sucho´ n, 1974] W. Sucho´ n. D´ efinition des founcteurs modaux de Moisil dans le calcul n-valent � ukasiewicz avec implication et n´egation. Reports on Mathematical Logic, des propositions de L 2, 43–47, 1974. [Surma, 1971] S. J. Surma. Ja´skowski’s matrix criterion for the intuitionistic propositional cal culus. Prace z logiki, VI, 21–54, 1971. [Surma, 1973] S. J. Surma. A historical survey of the significant methods of proving Post’s theorem about the completeness of the classical propositional calculus. In Surma, S. J. (ed.) Studies in the History of Mathematical Logic. Ossolineum, Wroc�law, 19–32, 1973. [Surma, 1974] S. J. Surma. An algorithm for axiomatizing every finite logic. Reports on Math ematical Logic, 3, 57–62, 1974. [Surma, 1984] S. J. Surma. An algorithm for axiomatizing every finite logic. In Rine D. C. (ed.) Computer Science and Multiple-Valued Logics, North Holland, Amsterdam, 143–149, 1984. [Suszko, 1957] R. Suszko. Formalna teoria warto´sci logicznych (A formal theory of logical val ues). Studia Logica, VI, 145–320, 1957. [Suszko, 1972] R. Suszko. Abolition of the Fregean Axiom. In Parikh, R. (ed.) Logic Colloquium, Symposium on Logic held at Boston, 1972–73 . Lecture Notes in Mathematics, vol. 453, 169– 239, 1972. [Suszko, 1975] R. Suszko. Remarks on L � ukasiewicz’s three-valued logic. Bulletin of the Section of Logic, 4, no. 3, 87–90, 1975. [Suszko, 1977] R. Suszko. The Fregean Axiom and Polish Mathematical Logic in the 1920’s. Studia Logica, 36, no. 4, 377–380, 1977. [Takahashi, 1967] R. Takahashi. Many-valued logics of extended Gentzen style I. Science Reports of the Tokyo Kyoiku Daigaku, Section A, 9(231), 95–116, 1967.
Many-valued Logic and its Philosophy
93
[Takahashi, 1970] R. Takahashi. Many-valued logics of extended Gentzen style II. Journal of Symbolic Logic, 35(231), 493–528, 1970. ¨ [Tarski, 1930] A. Tarski. Uber einige fundamentale Begriffe der Metamathematik. Comptes Ren eances de la Soci´ et´ e des Sciences et des Lettres de Varsovie Cl.III , 23, 22–29, 1930; dus des s´ English tr. In Tarski, A. Logic, Semantics, Metamathematics: Papers from 1923 to 1938 , translated by Woodger, J. H. Clarendon Press, Oxford, 1956, 30–37. [Tarski, 1936] A. Tarski. O poj¸eciu wynikania logicznego (On the concept of logical conse ad Filozoficzny, 39, 58–68, 1936; English tr. In Tarski, A. Logic, Semantics, quence). Przegl¸ Metamathematics: Papers from 1923 to 1938 , translated by Woodger, J. H. Clarendon Press, Oxford, 1956, 409–420. [Tarski, 1938] A. Tarski. Der Aussagenkalk¨ ul und die Topologie. Fundamenta Mathematicae, 31, 103–134, 1938; English tr. In Tarski, A. Logic, Semantics, Metamathematics: Papers from 1923 to 1938 , translated by Woodger, J. H. Clarendon Press, Oxford, 1956, 421–454. [Tokarz, 1974] M. Tokarz. A method of axiomatization of L � ukasiewicz logics. Bulletin of the Section of Logic, 3, no. 2, 21–24, 1974. [Traczyk, ] T. Traczyk. An equational definition of a class of Post algebras. Bulletin de l’Acad´ emie Polonaise des Sciences Cl. III , 12, 147–149, 1964. [Turner, 1984*] R. Turner. Logics for Artificial Intelligence. Ellis Horwood, Chichester, 1984. [Tuziak, 1988] R. Tuziak. An axiomatization of the finitely-valued L � ukasiewicz calculus. Studia Logica, 48, 49–56, 1988. [Urquhart, 1973] A. Urquhart. An interpretation of many-valued logic. Zeitschrift f¨ ur Mathe matische Logik und Grundlagen der Mathematik , 19, 111–114, 1973. [Urquhart, 1986*] A. Urquhart. Many-valued logic. In Gabbay, D. and Guenthner, F. (eds) Handbook of philosophical logic, vol. III. D. Reidel, Dordrecht, 71–116, 1986. [Wade, 1945] C. I. Wade. Post algebras and rings. Duke Mathematical Journal, 12, 389–395, 1945. [Wajsberg, 1931] M. Wajsberg. Aksjomatyzacja tr´ ojwarto´sciowego rachunku zda´ n. Comptes Rendus de la Soci´ et´ e des Sciences et des Lettres de Varsovie Cl. III , 24, 126–148, 1931; English tr. Axiomatization of the three-valued propositional calculus. In McCall, S. (ed.) Polish Logic 1920–1939 . Clarendon Press, Oxford, 1967, 264–284. [Wajsberg, 1933] M. Wajsberg. Eine erweiterter Klassenkalk¨ ul. Monatshefte f¨ ur Mathematik und Physik , 40, 113–126, 1933. [Webb, 1935] D. L. Webb. Generation of any n-valued logic by one binary operation. Proceedings of the National Academy of Sciences, 21, 252–254, 1935. [Whitehead and Russell, 1910] A. N. Whitehead and B. Russell. Principia Mathematica, vol. I. Cambridge University Press, 1910. [Williamson, 1994] T. Williamson. Vagueness. Routledge, London and New York, 1994. [Wole´ nski, 1989] J. Wole´ nski. Logic and philosophy in the Lvov–Warsaw School. Synthese Li brary, 198. D. Reidel, Dordrecht, 1989. [Wolf, 1977*] R. G. Wolf. A survey of many-valued logic (1966–1974), Appendix II. In Dunn, J. M. and Epstein, G. (eds) Modern uses of multiple-valued logic. D. Reidel, Dordrecht, 167–324, 1977. [W´ ojcicki, 1970] R. W´ ojcicki. Some remarks on the consequence operation in sentential logics. Fundamenta Mathematicae, 68, 269–279, 1970. [W´ ojcicki, 1977] R. W´ ojcicki. Strongly finite sentential calculi. In W´ ojcicki, R. and Malinowski, G. (eds) Selected papers on L � ukasiewicz sentential calculi. Ossolineum, Wroc�law, 53–77, 1977. [W´ ojcicki, 1988] R. W´ ojcicki. Theory of logical calculi. Basic theory of consequence operations. Synthese Library, 199. Kluwer Academic Publishers, Dordrecht, 1988. [Zach, 1993] R. Zach. Proof theory of finite-valued logics, Master’s thesis, Institut f¨ ur Algebra und Discrete Mathematik, TU Wien. 8, 338–353, 1993. [Zadeh, 1965] L. A. Zadeh. Fuzzy sets. Information and Control, 8, 338–353, 1965. [Zadeh, 1972] L. A. Zadeh. A fuzzy-set-theoretic interpretation of linguistic hedges. Journal of Cybernetics, 2, 4–34, 1972. [Zadeh, 1975] L. A. Zadeh. Fuzzy logic and approximate reasoning. Synthese, 30, 407–428, 1975. [Zadeh, 1976] L. A. Zadeh. A fuzzy-algorithmic approach to the definition of complex or impre cise concepts. International Journal of Man–Machine Studies, 8, 249–291, 1976.
94
Grzegorz Malinowski
[Zawirski, 1934a] Z. Zawirski. Znaczenie logiki wielowarto´sciowej i zwi¸azek jej z rachunkiem prawdopodobie´ nstwa (Significance of many-valued logic for cognition and its connection with ad Filozoficzny, 37, 393–398, 1934. the calculus of probability). Przegl¸ [Zawirski, 1934b] Z. Zawirski. Stosunek logiki wielowarto´sciowej do rachunku praw dopodobie´ nstwa (Relation of many-valued logic to the calculus of probability). Prace Komisji ol� Nauk , 4, 155–240, 1934. Filozoficznej Polskiego Towarzystwa Przyjaci´ [Zinov’ev, 1963*] A. A. Zinov’ev. Philosophical problems of many-valued logic, edited and trans ung, G. and Comey, D. D. D. Reidel, Dordrecht, 1963. lated by K¨
PRESERVATIONISM: A SHORT HISTORY
Bryson Brown Preservationism is a general approach to understanding consequence relations. Preservationist consequence relations dispense with the usual assumption that the semantic and syntactic properties preserved by consequence must be truth (or satisfiability) and consistency. Instead, this family of consequence relations draws on other semantic and syntactic features of premise sets, conclusion sets and even of consequence relations themselves. Preserving those features across extensions of sets of sentences, or a range of cases, provides new accounts of consequence. The central idea was proposed by R. E. Jennings and P. K. Schotch in a series of papers that appeared in the late 1970s and early 1980s. Since then, they, their students and colleagues have developed a wide range of new consequence relations, as well as some new readings of familiar consequence relations. In general, an interesting preservable property of premise sets will be preserved under some but not all extensions of the premise set. Philosophically, it will be a property we think of as “good” for a set to have — but what this comes to is not very constraining: What we require is not ideal goodness (something which lurks behind the conventional attachment to ‘truth-preservation’), but only a modest, comparative sort of goodness. Here two slogans, coined by Schotch and Jennings (respectively), fit nicely: Hippocrates: Don’t make things worse. Making do: Find something you like about your premises, and pre serve it. Properties dual to such premise-set properties make good candidates for preserv able properties of conclusion sets. Interesting new consequence relations also result when we insist that a truth-preserving consequence relation be preserved across a range of premise and conclusion sets based on given premise and conclusion sets. We begin with an account of the familiar classical consequence relation, empha sizing its preservational character. The main early motivation for preservationism emerges from this account: The need for a consequence relation that deals more constructively with inconsistent premises. The rest of the story will present, in rough chronological order, the main preservationist systems and what is known (and not yet known) about them.
Handbook of the History of Logic. Volume 8 Dov M. Gabbay and John Woods (Editors) © 2007 Elsevier B.V. All rights reserved.
96
Bryson Brown
1
SOME OBSERVATIONS ABOUT THE CLASSICAL VIEW OF CONSEQUENCE
We will say that a set Γ is consistent if and only if it is impossible to derive a sentence and its negation from Γ; Γ is satisfiable if and only if some allowed valuation assigns a designated value (usually read as a form of ‘truth’, indicating the correctness of an assertive commitment) to every sentence in Γ. A set is maximally consistent if it is consistent and adding any sentence to it would produce an inconsistent set. Similarly, a set is maximally satisfiable if it is satisfiable and no proper superset is satisfiable. The standard view of consequence relations results from a straightforward account of semantic and syntactic consequence relations ( and ): guarantees the preservation of truth, while preserves consistency. This can also be expressed (without appeal to the notion of a ‘guarantee’) by saying that preserves the satisfiability of all satisfiable extensions of Γ, and that preserves the consistency of all consistent extensions of Γ. Formally, 1. Γ α iff ∀Γ [(Γ ⊇ Γ&Γ is satisfiable) → Γ , α is satisfiable]. 2. Γ α iff ∀Γ [(Γ ⊇ Γ&Γ is consistent) → Γ , α is consistent].1 In English, if Γ extends Γ satisfiably or consistently, then every consequence of Γ must satisfiably or consistently extend Γ . This leads to an interesting observa tion: We can say that closing under these consequence relations begs no questions, construing question begging as treating sentences as part of the commitments that go with having accepted Γ, despite their being incompatible with some acceptable extensions of Γ. Conclusions that are incompatible with acceptable extensions of a premise set clearly go beyond the commitments that come with accepting those premises.2 Given the soundness and completeness of our system of derivation, 1 and 2 are simply alternative definitions of the same consequence relation, represented in the standard way as a set of ordered pairs of sets of sentences and individual sentences. The principle point here concerns the implications of this picture of consequence for the consequences of unsatisfiable or inconsistent premise sets. Both unsatisfiability and inconsistency are preserved when we form supersets. So if Γ is unsatisfiable 1 Here we’re using the notational convention that Γ, α = Γ ∪ {α}. We could also present 3 and 4 in slightly different form:
3 .
Γ � α iff ∀Γ [(Γ is a maximal satisfiable extension of Γ) → α ∈ Γ ].
4 .
Γ α iff ∀Γ [(Γ is a maximal consistent extension of Γ) → α ∈ Γ ].
However, both these formulations leave aside the issue of extension — and to our way of thinking, the notion of a consequence relation is very tightly linked to the idea of ‘acceptable’ extensions of sets of sentences. Of course we can re-capture this notion by appeal to extensions which are subsets of such maximal extensions. So the two versions will be distinct only if we have non-standard notions of unsatisfiability and inconsistency that are not always preserved under supersets. 2 Of course, those interested in induction and ampliative reasoning in general may balk at defining acceptability in terms of satisfiability or consistency alone — so they may still dispute Hume’s characterization of induction as question-begging.
Preservationism: A short history
97
or inconsistent, Γ has no satisfiable or consistent extensions. This implies that for an unsatisfiable or inconsistent premise set Γ, every sentence trivially preserves the satisfiability of every satisfiable extension of Γ; for such a Γ clauses 1 and 2 are satisfied for every α. Thus every sentence is a consequence of an unsatisfiable or inconsistent set. This trivialization of the consequences of unsatisfiable and inconsistent premise sets is deeply rooted in the standard account of consequence relations. Interest in paraconsistent consequence relations began with the recognition that, though this is all clear and perfectly correct as far as it goes, trivialization of these premise sets is also very unhelpful. In the course of events, we sometimes do end up with inconsistent sets of commitments. Classical logic’s response is to demand that we find another set of premises to work with. Though this seems to be good advice, it does not provide enough guidance, that is, it does not tell us how to do what it demands. Once we have arrived at inconsistent commitments, we need insight into those commitments to help us see how to improve on them. Classical logic simply tells us that our commitments are trivial, leaving behind neither an account of the content of conflicting commitments that could help us reflect on where and how we have gone wrong, nor any way of muddling through in the meanwhile. The classicists’ main response has been to interrogate the premises involved separately, on suspicion. Sometimes this is helpful. But sometimes the bona fides of each premise look perfectly sound, even though their collective consequences make it clear that something has gone wrong. As a simple example, consider a large collection of measurements, collectively inconsistent but each carefully made. No individual result need stand out as suspicious here, and repeating the measurements (if this is possible) is likely to produce yet another inconsistent set of results. Another sort of case arises when we develop formal theories: Simple sets of axioms each of which seems to express a clear, if informal, intuition that we want to capture often turn out to be inconsistent. Giving one or more up undermines the application that motivated the construction of the formal system in the first place. If we could find a constructive way of faute de mieux reasoning with inconsistent measurements and axioms, the results might be illuminating. But classical logic won’t allow it.
Paraconsistency A consequence relation that copes constructively with such sets of commitments must go beyond preserving the classical notions of truth or consistency. We say that a consequence relation Rp is minimally paraconsistent 3 iff this trivialization 3 The definition of ‘paraconsistent’, meaning either beyond or near consistent, remains con tested territory. Some, following da Costa, demand that a paraconsistent logic not have the law of non-contradiction, ¬(p ∧ ¬p), as a theorem. But most now focus on non-trivialization. The divide within this group separates those who insist on non-trivialization of contradictions, i.e. the failure of p ∧ ¬p α, for some α, and those who insist more weakly only on the non-trivialization of some inconsistent premise sets.
98
Bryson Brown
fails for Rp , i.e. iff for some classically unsatisfiable or inconsistent set of sentences Rp . There are two main strategies for Γ, there is a sentence α such that Γ, α ∈ producing such a consequence relation, based on different ways of changing clauses 1 and 2.
Strategy A: New accounts of “truth” and “consistency” This is the road most traveled in paraconsistent logic. Its practitioners include di aletheists, who defend a radical account of truth according to which some contra dictions are in fact true. But they also include more conservative figures who take the new semantic values they propose for sentences to express epistemic commit ment, or some other status more modest than truth, tout court. On our taxonomy, any paraconsistent semantics that provides non-trivial assignments of designated values to the members of some classically unsatisfiable sets of sentences falls into this group (the difference between the dialetheists and the rest being a matter of interpretation, rather than a substantive difference of formal approach). This approach retains the standard assumption that whenever α is not a semantic con sequence of Γ for a consequence relation R, this is because the proposed semantics provides a valuation V such that for all γ ∈ Γ, V (γ) ∈ {v : v is designated} and V (α) ∈ {v : v is designated}. While truth is the standard reading of a designated value, philosophers have not always interpreted the designated values of a formal semantics as forms of truth. For instance, in “How a Computer Should Think,” Belnap reads the values of Dunn’s four-valued logic epistemically, as “told true”, “told false”, “told both” and “told neither”. However, even when we keep this interpretational latitude in mind, this semantic approach to consequence relations remains formally constraining. It focuses our attention on the assignment of values to sentences and the distinction between designated and undesignated values. The resulting consequence relations insist that Γ α holds if and only if α is assigned a designated value in every valuation assigning designated values to all the members of Γ. The implications of this account are explored in a very general guise in Scott [1974]. Scott considers the properties of a consequence relation determined by a set of ‘allowed’ valuations from the sentences of a language L, defined as functions from sentences of L into {0,1}, where Γ α ⇔ ∀V ∈ allowed valuations: ∀γ ∈ Γ, V (γ) = 1 ⇒ V (α) = 1. All three of transitivity, monotonicity and reflexivity must hold for any such conse quence relation, and any consequence relation obeying these rules can be captured by such a set of allowed valuations. But there are interesting forms of consequence relation that do not fit this pattern. And some consequence relations that do fit the pattern can also be captured (and illuminated) by a different approach.
Preservationism: A short history
99
Strategy B: Preservationist Paraconsistency The preservationist approach has been less widely pursued. But it has some ad vantages over the first. The main idea is contained in our two opening slogans, Schotch’s Hippocratic principle and Jennings’ suggestion that we learn to make do. There are many properties whose preservation will constrain the acceptable extensions of sets of sentences. Whether we think of them as measures of how bad our premise set is, or of how good it is, they allow us to distinguish good extensions from bad, and thereby allow us to go on distinguishing consequences from nonconsequences even when our premise sets are logically imperfect. More radically, we can also consider dispensing with extensions in favour of a more general pic ture, in which we replace the set of allowed valuations with a function from sets of sentences to allowed valuations. The intersection of the sentences assigned ‘1’ by the valuations acceptable relative to Γ then determines Γ’s consequences. Insisting that the valuations acceptable relative to Γ assign ‘1’ to an extension of Γ forces reflexivity and transitivity on the consequence relation, while this generalization allows for consequence relations that are not monotonic, transitive or reflexive: Reflexivity obviously fails, when at least one of the allowed valuations relative to Γ fails to assign ‘1’ to a member of Γ. Transitivity fails in a somewhat subtler way: If some valuation acceptable relative to Γ assigns ‘0’ to β, while every valuation acceptable relative to Γ assigns ‘1’ to α and every valuation acceptable relative to Γ, α assigns ‘1’ to β, then β will fail to be a consequence of Γ even though β is a consequence of Γ,α and α is a consequence of β. This case is odd, indeed, but the formal account just given allows for it, as d’Entremont [1983] made clear. And there is something valuable in this, even if our proposals don’t exploit this possibility: By making room for these outr´e possibilities, we can illuminate the dif ference between systems that allow them and systems that don’t. Further, just as conditional forms of monotonicity apply to some preservationist logics, conditional forms of these properties, ensuring that reflexivity and transitivity hold except in certain ugly circumstances, provide more ways of coping when our premises do get ugly. For example, we might choose to ‘write out’ any contradictory sentences in a premise set Γ by refusing to assign them the value ‘1’ in the valuations allowed relative to Γ, while retaining reflexivity for all other sentences. From the classical point of view, there is nothing worse than an inconsistent, unsatisfiable set of sentences. Classical logic preserves satisfiability or consistency only; once these are lost nothing remains that a dogmatically classical logician cares to preserve. But this is short-sighted, narrow-minded, or both. Some other features of premise sets are worth preserving. Non-triviality is the most obvious example, but we will encounter several examples of specific preservable properties that can persist and be systematically preserved by a system of inference even in premise sets that are unsatisfiable and inconsistent. Beginning with a set of sentences that merely includes p and ¬p and applying our consequence relation to obtain the set of all sentences makes things worse by any reasonable measure: It takes us from a set that we could reasonably use to
100
Bryson Brown
represent someone’s (inconsistent) beliefs, or the contents of an interesting but in consistent theory, to the set of all sentences in the language, a set that is completely useless as a representation of either. Applying a non-paraconsistent consequence relation to inconsistent premise sets clearly violates Schotch’s Hippocratic advice on dealing with bad situations. And this implies that we have good reason to take up Jennings’ positive suggestion: We should seek other virtues that such premise sets can still possess, and ways to reason with them that respect those virtues. The preservationist alternative widens the options before us. It liberates conse quence relations from the tyranny of designated values. It does not demand that we find a way to assign a designated value to the premises of a rejected consequence while assigning a non-designated value to the conclusion. We can assign values to sentences just as classical logicians do,4 so long as we also recognize other features worth preserving. If some inconsistent/unsatisfiable sets possess these features and the features are not preserved by every extension of these sets, then the resulting consequence relation will be a paraconsistent one.
2 ORIGIN MYTH Preservationism developed out of work on deontic logic, begun roughly in 1975 by Raymond E. Jennings and Peter K. Schotch. But, like many innovative ideas, it arose from work aimed at other concerns. At the time, Jennings had recently been to New Zealand on a research trip to extend earlier work on the logic of preference and utilitarianism that he had done while working on his MA at Queen’s University. Jennings remarks that he found New Zealand ‘just like England before the war — the war of 1812, that is’. But he also found it a wonderful place to be as he worked on his ‘utilitarian semantics’. Wellington was friendly and accessible, and Jennings learned a lot of modal logic from both Rob Goldblatt and Max Cresswell. On his return from New Zealand, Jennings made a trip to Dalhousie University to visit Steven Burns, an old friend from student days at Queen’s. As the local logician, Peter Schotch was recruited to act as host. Jennings stayed with Schotch for about 5 days as the two worked through a list of 38 Henkin-style completeness proofs for various systems of modal logic. The next summer Jennings took a teaching appointment at Dalhousie and worked with Schotch on plans for a book on modal logic. Their aim was to update and refine the material in Hughes and Cresswell’s book in the light of Segerberg’s work on frame theory; they hoped to make the result ‘a little more readable’ than Segerberg. As they worked on their Primer on Modal Logic (only partly finished during that summer’s work), Jennings was also pursuing issues in deontic logic. One day he came into Schotch’s office and exclaimed that normal modal logic doesn’t work. His complaint was that it collapses distinctions that they both considered important. This collapse was particularly clear in the light of Segerberg’s topological semantics 4 Though,
of course, we need not!
Preservationism: A short history
101
for modal logic, [Segerberg, 1972], which defines a modal frame as an ordered pair, U, R, with U a set and R a non-empty binary relation on U . Each element of U determines a valuation on the modal language, with the modal operator having the truth condition: u α ⇔ ∀u : Ruu :u α. This class of modal frames is characterized by the following principles:5 K:
α ∧ β → (α ∧ β)
RM:
α → β ⇒ α → β
RN:
α ⇒ α
The following two equivalences are inescapable for any such logic: α → ♦α ⇔ (α → ♦α) p → ♦p ⇔ ¬⊥
But despite their equivalence in any normal modal logic, these pairs of statements are intuitively distinct, at least when read deontically: That ‘ought implies can’ seems distinct from ‘It’s not the case that it ought to be the case that the false’. Similarly, that ‘If it ought to be that it ought to be that α, then it ought to be permitted that α’ seems distinct from ‘It ought to be that, if it ought to be that α, then it is permitted that α’. Schotch and Jennings began to consider how to change the semantics so as to distinguish these principles. The obvious targets (as constraints on normal modal frames) were: 1. The requirement that the set of points in the frame be non-empty. 2. The central role of the binary ‘accessibility’ relation defined on the points. Pursuing empty frames seemed both odd and unhelpful, so Schotch and Jennings decided to explore changes to the relation. The only restriction normal modal logic imposes on the relation is that it must be binary, so the obvious alternative was to consider relations of higher ‘arity’.6 Beginning with a ternary relation treated as a function from worlds to ‘accessible’ world-pairs, they proposed a simple truth condition for ‘α’: M M M u α ⇔ ∀xy : uRxy →x α or y α.
Right away it was clear that on this semantics, α, β (α∧β). The first question they turned to was how to get 5 It can also be characterized by the elegant single rule, R� : Γ α ⇒ �[Γ] �α, where �[Γ] is the result of placing a ‘�’ in front of each element of Γ. 6 The possibility of multiple binary relations was also explored.
102
Bryson Brown
α ∧ β → (α ∧ β)
K:
back again in this semantic context. Requiring ∀x, y : ∃uuRxy → x = y is close enough (though not quite exactly right, since this approach to collapsing the ternary semantics into a binary semantics doesn’t correspond strictly to K). The second question was, what corresponds to modal aggregation in this context? The next day, Jennings pointed out that K2 :
α ∧ β ∧ γ ((α ∧ β) ∨ (α ∧ γ) ∨ (β ∧ γ))
holds in ternary frames, on pigeon-hole grounds. Similarly, the rule Kn−1 : α1 ∧ . . . ∧ αn (αi ∧ αj ), 1 ≤ i = j ≤ n7 holds in n-ary frames in general. Suspecting that these rules might constitute the general modal aggregation rules for these ‘diagonal’ n-ary frames, Schotch and Jennings began a long effort to provide a completeness proof for them. As the end of summer school approached, they found themselves still stuck on the completeness proof for the logic based on K2 . Both went on working on the completeness problem over the fall and winter, and work on the project continued during summer school in 1976 at Simon Fraser University. As this project continued, Schotch and Jennings also began to reflect on this new consequence relation and its implications for more traditional ideas about consequence. The upshot was a growing appreciation of the limits imposed by the central role generally granted truth in the semantics of logical consequence, and the possibility of casting wider logical nets. Preservationism was born. Since then, it has developed along several main lines, as well as contributing to a number of smaller investigations. Here we will focus on three main lines of preservationist research, commenting on some of the other projects along the way.
Weak Aggregation As we’ve already seen, preservationism began with weakly aggregative modal logics and the ‘forcing’ consequence relation. In this section we continue the story of these logics and some important results that have emerged from work on them. In the summer of 1976, Schotch recalled work he had done in the algebra of modal logic at while at the University of Waterloo. Dennis Higgs, an algebraist there, had introduced Schotch to Tarski and Jonson’s [1951], “Boolean Algebra with Operators”, which included consideration of n-ary frames: A ternary frame corresponds to a binary operator in Tarski and Jonson’s approach, and in general, an n-ary frame corresponds to an n − 1-ary operator. Higgs had encouraged Schotch to work on modal logic from this point of view. At the following NSRCC conference hosted by Steve Thomason, Jennings and Schotch discussed this work with Kit Fine, Krister Segerberg and Rob Goldblatt, 7 Called
(∨).
‘cockroach intro’ (∧∨-intro) for its combination of conjunction (∧) and disjunction
Preservationism: A short history
103
as well as (someone??) working on applications to computing and dynamic logics. Goldblatt had considered binary operators with a temporal reading of ♦: first this, and then that; he had done a Henkin completeness proof for that system. David Johnston, then a student of Jennings’, successfully applied this approach of Goldblatt’s to n-ary frames in general in his M.A. thesis [1976]. Still, like Schotch and Jennings, he didn’t manage to produce a completeness proof for the diagonal fragment corresponding to Schotch and Jennings’ truth condition for .8 Schotch and Jennings continued to pursue a completeness proof for the diagonal fragment in the summer of 1976. It was clear that the issue was closely connected to (n − 1)-ary partitions of premise sets: pigeon-hole argument established the soundness of Kn−1 for an n-ary frame relation, but a proof of completeness eluded them. While they were struggling with the proof, Max Cresswell passed through and encouraged them to keep at it, remarking that the same thing had happened to him before. After some time, they felt that the K2 case (for ternary frames) was proven. Jim Freeman organized a CPA workshop at which they planned to present the proof. Storrs McCall, Hughes Leblanc and Danny Daniels were there, on a very hot (40◦ ) day. Halfway through lunch Ray asked Peter, “Isn’t this a coun terexample?” Working through it again, Schotch anxious and excited (even manic, he says) and Jennings sleepy in the heat, they arrived at the notion of replacing the K2 rule with an appeal to a new consequence relation, the consequences that survive the n-ary partitions of a premise set. This consequence relation, written Γ[ α, holds if and only every n-partition of Γ includes a cell that classically proves α. With this notion of consequence in place of K2 , completeness for their diagonal modal logics could be proven straightforwardly. At the 1978 SEP meetings in Pittsburgh, this novel ‘forcing’ relation and aggre gation principles took the stage together, with Bill Harper, Teddy Seidenfeld and Bas van Fraassen among the audience. Chellas pointed out that Scott’s elegant rule for normal modal logic: Γα (Γ) α could be used to capture the diagonal n-ary modal logics Schotch and Jennings had formulated: Simply put the new forcing consequence relation in place of ‘’ in Scotts’ rule, and the diagonal n-ary modal logic would result. Barbara Partee pointed out that this consequence relation would allow non-trivial reasoning from inconsistent data. Earlier at the meeting, R. Wolf had read a paper, titled “Studies in Paraconsistent Logic I,” about work with Newton da Costa — this paper might have been the source of Partee’s suggestion. Partee’s intervention marked the first time that Schotch and Jennings heard the word ‘paraconsistency’. 8 This problem, which continued to be a central concern for Schotch, Jennings and their co workers, can be found (in what may be its first appearance in the literature) in Prior’s work on tense operators, where he defined the following pair of operators:
�u α · β ⇔ ∃xy : uRxy&(�x α∧ �y β) � α β ⇔ ∀xy : uRxy ⇒ (�x α∨ �y β) The ‘�α’ operator of the diagonal fragment of n-ary modal logic can be defined as α α.
104
Bryson Brown
Perhaps unsurprisingly, the reception for Wolf’s paper may not have been en tirely positive: Schotch reports a ‘fierce scowl’ on Rich Thomason’s face during the presentation, though he adds that this might not have indicated a negative response to the paper. At any rate, following the conference Schotch and Jennings went off to pursue more work on paraconsistency.9 The result was a series of papers by Schotch, Jennings and Johnston on paraconsistency and new ideas for consequence relations that appeared between 1979 and the mid-80’s. In 1979, in the IEEE annual conference proceedings, Schotch and Jennings presented their new measure of (departure from) consistency in a paper titled “Multiple Valued Consistency”. In Schotch and Jennings [1980], the links between modality and consequence were explored, paralleling Scott’s rule for the base modal logic K with the forcing rule for the Kn modal logics. Another topic in Schotch and Jennings’ investigations at the time grew out of the study of n-ary relations (where n > 2) that their semantic interest in these modal logics led them to. The theory of binary relations has dominated mathematical exploration of relations — even ternary and quaternary relations rarely come to the fore there. Special names are used to characterize particular families of binary relations: reflexive, binary, transitive, symmetric, Euclidean, serial, etc. But names for particular families of ternary relations are hard to find — as are explorations of any correspondence between the standard families of binary relations and relations of higher ‘arity’. While binary relations play important roles in our understanding of the modal logic of binary frames, there were many interesting questions to ask about the parallel cases (if any) for ternary and higher arity frames. D.K. Johnston took a special interest in these issues at the time. But the central target of preservationist work in this period was the forcing relation, its semantics and axiomatization. In the early 80’s Schotch and Jennings contributed “On Detonating” to a volume on paraconsistency being edited by Graham Priest and Richard Sylvan. This paper presented a multiple-conclusion version of forcing, with weakened aggregation used to treat both inconsistency on the left and the failure of consistent deniability on the right. The volume finally emerged in 1989 as [Priest et al., 1989].10 The issues pursued in this period include the completeness question, the axiomatization of forcing, frame correspondence issues, and the 1st order definability of frame conditions providing semantics for extensions of the base diagonal n-ary modal logics formulated in terms of the forcing relation. It was during this time that Schotch and Jennings’ exploration of 9 On the way home, Jennings found a pen on the plane that he went on to use in the course of writing five new papers. 10 Schotch and Jennings’ sense of urgency to get these early results published was justified — in 1980 David Lewis first presented “Logic for Equivocators” (published in 1984 in Nous); he subsequently inquired about exactly when Schotch and Jennings had first published their ideas. On finding they had published first, he later referred to their work for ‘technical details’ as an illustration of his own more conservative approach to paraconsistency. In fact, at least as I see it, Lewis’ motives in his [1984] suggest something closer to the ambiguity-based preservationist approach to Priest’s LP, first proposed in [Brown, 1999].
Preservationism: A short history
105
the semantics of forcing first provided a completeness proof for an axiomatization of forcing — however, the proof was so tangled and difficult to follow that Schotch and Jennings never published it. But several notions that emerged from that work played important roles in subsequent developments.
Coverings and level functions In Jennings and Schotch [1984], the forcing consequence relation arises from a definition of levels of incoherence, reflecting a formally tractable sense in which things can be made worse, as we extend a given premise set. As we’ve seen, the n-forcing relation can be invoked to axiomatize the modal logic of n + 1-ary frames, where a sentence α is an n-consequence of a set of formulae, Γ, if and only if α follows from some cell in every n-partition of Γ. The definition of levels of incoherence generalizes on this, providing the base for a new consequence relation that takes full advantage of the possibility of applying a range of stronger or weaker principles of aggregation to our premises. Level functions are defined very generally at first: With Γ a set of sentences of a propositional language L not including ⊥, 0. ∀Γ, (Γ) ≤ ω 1. (∅) = 0 2. ∀Γ ∈ 2At , (Γ) = 1 3. ∀Γ ⊆ {α| α}, Γ) = 0 4. If Γ ⊆ Γ then (Γ) ≤ (Γ ) 5. If (Γ) = n and level(Γ ) = m then (Γ ∪ Γ ) ≤ (n + m) The level function central to the forcing relation is most generally characterized in terms of coverings rather than partitions: Covering An indexed family of sets of sentences, A = ∅, Ai , 1 ≤ i ≤ ξ covers a set Γ, if and only if, for every γ ∈ Γ, ∃A ∈ A : A γ. The level of incoherence of Γ is then defined as:
(Γ) = Min ξ such that ∃A: A = ∅, A1 . . .Aξ , A covers Γ and ∀A ∈ A, A ⊥, if this limit exists.
(Γ) = ∞, otherwise. For example, ({α ∨ ¬α}) = 0 since the null set covers this set (and the same goes for every theorem, as 3 above requires). ({α, ¬α}) = 2, since the family: ∅, {α}, {α} is a consistent cover of {α, ¬α}, while no smaller family can consistently cover this set. Finally, ({α ∧ ¬α}) = ∞; this, of course, is the assigned ‘level’
106
Bryson Brown
of any set including a contradiction, and is added to our definition to extend the level function to all of 2L . But for any property P of sets of sentences, which is not preserved (in general) in supersets, we can define corresponding notions of covering and level that measure how far a given set departs from having the property. Further, as was first shown in [d’Entremont, 1983], if the initial property is compact, so is the corresponding level property.
Level-respecting consequence With the notion of a level of incoherence in hand, we can now define a new conse quence relation which preserves levels in the same way that classical logic preserves consistency (which amounts to preserving levels 0 and 1). Where ξ = (Γ), Γ[ α if and only if, ∀A : ∅, Ai : 1 ≤ i ≤ ξ ∧ A covers Γ ⇒ ∃A ∈ A : Aα As Schotch has observed, this consequence relation is interesting not just be cause of its subtle approach to aggregation, but also because, while it can be axiomatized and so proofs involving it can be conducted mechanically, which rules are correctly applicable to a given premise set depend on the set’s level. Because level is a generalization of consistency, we cannot, in general, finitely establish the level of an infinite premise set. This implies that while the rules for reasoning in accord with this notion of consequence are mechanically applicable and the con sequence relation is compact, we cannot mechanically decide which rules are the right ones to apply to any given premise set. The potential implications of such rules for foundational studies have yet to be explored.
Traces The central concept in the semantics of forcing is that of an n-trace. T is an n-trace on a set Γ if and only if T is a set of sets such that some member of T is covered (i.e. is a subset of some cell) in each n-partition of Γ. So, where Tn (Γ) is the set of n-traces on Γ and Πn is the set of n-partitions of Γ, T ∈ Tn (Γ) ⇔ ∀π ∈ Πn (Γ), ∃τ ∈ T, p ∈ π : τ ⊆ π. A (left) formulated n-trace on a set of sentences is a disjunction of the conjunc tions of the sentences in each element of the trace. Then every consequence that ‘survives’ the n-partitions of a set of sentences is implied by some such formulated trace on the set: By definition, such consequences are implied by some cell in every partition. So one trace implying such a consequence, α, is the set of all such cells, i.e. the set including a cell proving α chosen from every n-partition: Every such partition covers at least one member of this trace, and every member of the trace implies the consequence in question. Therefore the set of n-traces on the premise set captures the aggregative force of n-partitioning a premise set, and a proof that
Preservationism: A short history
107
a rule is sufficient to produce the n-traces will (when combined with rules sufficient to obtain the consequences of all singleton premises) be a completeness proof for forcing. Schotch and Jennings [1989] extends these ideas to a multiple-conclusion version of forcing, dualizing their weakening of aggregation on the left with a symmetrical weakening of aggregation on the right. In classical multiple-conclusion logics, any conclusion set at least one of whose members must be true is trivial, that is, it follows validly from any premise set. This trivialization of right-sets that cannot be consistently denied is the dual image of the classical trivialization of inconsistent sets on the left. In multiple-conclusion forcing, coverings of the conclusion set sufficient to divide it into consistently deniable cells are added to the coverings of the premise set already familiar from single conclusion forcing. Like premise sets, conclusion sets are assigned a (right-) level, defined as the least cardinality of a non-trivial covering of the conclusion set. A covering is non-trivial iff none of its members is classically trivial. Conclusion sets under multiple-conclusion forcing can be thought of as closed not under disjunction (which trivializes a conclusion set if at least one of its members must be true), but under 2/n + 1R , an operation forming the conjunction of pairwise disjunctions amongst any n + 1 members. Here the notion of a right-formulated n-trace comes in. Rather than a dis junction of conjunctions, a right-formulated trace is a conjunction of disjunctions. Any premise sentence that forces a conclusion set of level n must classically imply some right-formulated n-trace on the set. We can see this just by considering a special case in the definition of forcing. We define singleton-on-the-left forcing as follows: A singleton premise γ forces a conclusion set ∆ of level n if and only if some member of every n-covering of ∆ is a classical consequence of γ. But, just as for singleton conclusion forcing, all we need do to find a right-formulated trace that γ classically implies is to place each such member of the n-partitions into our n-trace, and form the conjunction of its disjunctions. Ex hypothesi, each of the disjunctions is implied by γ. Therefore their conjunction is as well.
Multiple Conclusion Forcing In multiple conclusion forcing, we say that Γ[ ∆ holds if and only if for every
(Γ) covering of Γ, A, and every (∆) covering of ∆, B, there is some pair of cells, a, b, a ∈ A and b ∈ B, such that a b; more formally: Γ[ ∆ iff ∀A = ∅, a1 , . . .ai |1 ≤ i ≤ (Γ)&∀γ ∈ Γ, ∃i : ai γ&∀i, ai ∅, ai , ∀B = ∅, b1 , . . .bj |1 ≤ j ≤ (∆)∀δ ∈ ∆, ∃ai : δ|ai &∀i, ∅ ∃ak ∈ A, bl ∈ B, ak bl A simple system of rules for multiple-conclusion forcing takes the form:
108
Bryson Brown
Γ[ α, α β, β[ ∆
Γ[ ∆
α∈Γ β∈∆ Ref: Γ[ α β[ ∆ Γ[ ∆, α1 . . . Γ[ ∆, αn+1 2/n + 1(L) : Γ[ ∆, (αi ∧ αj ), 1 ≤ i = j ≤n+1 Γ, α1 [ ∆, . . . , Γ, αn+1 [ ∆
2/n + 1(R) Γ, (αi ∨ αj )[ ∆, 1 ≤ i = j ≤n+1 Γ, α[ ∆, Γ[ α, ∆ Trans: Γ[ ∆
i. Pres : ii. iii. iv. v.
where n = (Γ) where n = (∆)
It turns out that whenever every n-covering of a premise set and every n covering of a conclusion set are such that one cell of the first classically implies one cell of the second, there is a singleton forced by the premise set and forcing the conclusion set. This singleton bridge principle, the main lemma of the completeness proof for multiple-conclusion forcing, was not established until 2001; the proof appears in Brown, “Refining Preservation”, presented at the 2003 meetings of the Society for Exact Philosophy.
Hypergraphs A student of Jennings, David Wagner, was the first to point out an important link between traces and graph-theory. A graph can be represented as a set of pairs, representing the edges of the graph. A hypergraph is defined as a set of sets; each element of the hypergraph is called an edge of the hypergraph A hypergraph can be (properly) n-coloured if and only if one of n colours can be assigned to each of its atoms in a way that leaves none of its elements monochrome. Thus what Scotch and Jennings had called an n-trace is a familiar mathematical object, a non-n-colourable hypergraph. Further, the aggregation rule for the Kn modal logics, j ≤n+1 2/n + 1 : α1 , . . .αn+1 / (αi ∧ αj ), 1 ≤ i = corresponds to the smallest non-n-colourable hypergraph, the complete graph on n+1 vertices. Completeness The first published solution to the completeness problem for single-conclusion forc ing was discovered by Brown in the winter of 1991. Having worked on the problem on and off since 1988, Brown was on sabbatical at the Center for Philosophy of Science in Pittsburgh. There he learned that Belnap and Massey had noticed an important role for the 2/n + 1 aggregation principles so central to forcing in their exploration of just how completely classical semantics determined the classi cal consequence relation (see [Belnap and Massey, 1990]). Brown returned to the problem with a new approach: his aim was to show that 2/n + 1 would suffice to
Preservationism: A short history
109
prove a contradiction from any n-inconsistent set of premises. The key step in the final proof was an induction on the cardinality of the premise set; a simple appeal to ∨-elimination (correct for singleton forcing) together with the monotonicity of n-forcing led to the result. A version of this proof was published in [Brown, 1993b], a collection of papers published in honour of Ray Jennings, on the occasion of his 50th birthday. A more formal presentation, showing completeness for Schotch and Jennings’ Kn modal logics, appeared in [Apostoli and Brown, 1995]. A further generalization of this work appears in a technical report by Paul Wong [1997], in which the completeness proof presented in [Apostoli and Brown, 1995] is extended to multi-ary modal operators. The connection with hypergraph colourings recognized by Wagner implies that if the completeness result holds, then a hypergraph operation corresponding to 2/n+ 1, forming the pairwise union of the edges of every pair out of n+1 input hypergraphs, together with trivial operations of edge-addition and edge-contraction, will produce all the non-n-colourable hypergraphs from the trivially non-n colourable singleton loop graphs. This result was later generalized, in the appendix of Brown and Schotch [1999]. The chromatic index of a hypergraph H is defined as the least number of colours required for a proper colouring of H. The generalization shows that using any hypergraph of chromatic index n+1 as a ‘template’ for aggregation together with edge-addition and contraction will allow the construction of all the non-n colourable hypergraphs. In a general spirit, Brown [2000], Brown and Schotch [1999], and Brown [2002] present an approach to aggregation that shifts aggregation from operator rules like 2/n + 1 to structural rules governing how conclusions from sets of premises. Such logics arise from consideration of the type-raising transition involved in go ing from from truth-preservation as a relation between sentences in a language to ‘truth-preservation’ as a relation between sets of sentences. The structural rule for aggregation applies the graph-theoretic completeness results, beginng with the closure of singleton premise sets (treated as hypergraphs with a single, singleton edge) under our graph-theoretical analogue of 2/n + 1 (along with edge-addition and contraction). The rule allows the derivation of anything provable in a base logic from every member of a resulting hypergraph. On this account, full aggre gation is not a matter of having the rule α, β α ∧ β, but a matter of the set of graphs we can construct from our singleton premise graphs. Classical (full) aggregation results when no chromatic index limit is imposed on the hypergraphs we can reason from. The advantage of this approach is that the resulting account of aggregation is independent of the connectives available in the object language. Subsequent explorations by T. (later D.) Nicholson, first an undergraduate and then a doctoral student of Jennings, led to dualized formulations of these logical results [Nicholson, Jennings and Sarenac, 2002] and to deeper graph-theoretical results, including an axiomatization of the notion of ‘family resemblance’ [Nichol son and Jennings, forthcoming] and a more general characterization of the non-n colourable hypergraphs and their duals, the n-chines. This has led to the latest formulation of these weakly aggregative logics, using dual formulations based on
110
Bryson Brown
the transverse hypergraphs. A new completeness proof based on this dualized ap proach to aggregation is due to Jennings, D. Sarenac, and especially D. (then T.) Nicholson — see [Nicholson et al., 2001]. This work is built on some interesting new concepts, and develops some striking results about them that have elegant and illuminating connections to the original presentation of forcing. Dual to the notion of an n-trace is an n-chine. We begin by redefining the notion of an n-trace in terms of colourings: Let an n-colouring of the elements of a set S be a function C in S → {1, . . .n}. Then an n-trace T is a set of sets, τi such that any n-colouring of the elements of T ’s members leaves at least one τi ∈ T monochrome. Similarly, the n-chines Xn are sets X whose members χi are such that any n-colouring of the elements of X’s members will be such that every element of X includes a member with one of the n-colours, i.e. ∃i ∈ n such that 1 (i) ∩ χj = ∅. A left-formulated n-chine on a set of sentences Γ is all χj ∈ X, C− a conjunction of disjunctions of the elements of an n-chine on Γ, while a rightformulated n-chine on a set of sentences ∆ is a disjunction of conjunctions of the elements of an n-chine on ∆. The original aggregation rule of forcing is 2/n + 1 : Γ[ α1 . . .Γ[ αn+1 /Γ[ (αi ∧ αj), 1 ≤ i = j ≤ n + 1 It is based, as we’ve seen, on the complete graph on n + 1 vertices, which is the smallest non-n colourable hypergraph. But we can replace that rule with a dual, chine-based rule: n/n + 1 : Γ[ α1 . . .Γ[ αn+1 /Γ[ (αi ∨ . . . ∨ αj ), 1 ≤ i = j ≤ n + 1 where the disjunctions are amongst the n-tuples drawn from the αi . One extremely elegant result of the exploration of this new formulation of forcing is a simple graph-theoretic criterion for n-chines: X is an n-chine if and only if the intersection of every n-tuple of elements of X is non-empty. An illuminating relation between chines and traces is that the set of least interceptors of an n-chine is a n-trace, and vice versa: T ∈ Tn ⇒ {χ|∀τ ∈ T : χ ∩ τ = ∅ & ∀χ , χ ⊂ χ → ∃τ ∈ T : χ ∩ τ = ∅} ∈ Xn X ∈ Xn ⇒ {τ |∀χ ∈ X : τ ∩ χ = ∅ & ∀τ , τ ⊂ τ → ∃χ ∈ X : τ ∩ χ = ∅} ∈ Tn Finally, new ideas about aggregation have emerged in an axiomatization of the notion of family resemblance [Nicholson and Jennings, forthcoming]. The theory of family resemblance Nicholson and Jennings propose is grounded in Wittgenstein’s suggestion that the similarities connecting various kinds of things (get some results in here) involve a collection of properties that members of the kind possess in overlapping, criss-crossing combinations. But the formal details are far richer than the apparently elementary nature of their proposal would suggest. Nicholson and Jennings define the formal notion of a family in a very general way: Let P be a set of properties. Then
Preservationism: A short history
111
A set F is a family on P if and only if F ⊆ 2P , where F = ∅ and ∅ ∈ F . Family resemblance is a matter of overlap between various members of the family, so what we need to produce a measure of resemblence here isa measure, or measures of that overlap. Where S is a set and q an integer, let Sq be the set of q-tuple subsets of S. Jennings and Nicholson next define the harmonic number of a family F:
def df η(F) = min n : ∃G ∈ Sn : G = ∅, if this limit exists; else = ∞. This by itself is not particularly new except as an application of earlier notions: In terms of our earlier vocabulary the greatest n such that F is an n-chine is F’s harmonic number. But Nicholson and Jennings generalize on this notion, defining the n(-harmonic) saturation number of F, σn (F): F def σn (F) = min m ≥ 1 : ∃k ∈ {1, 2, . . . , n}, ∃G ∈ :| ∩G |≤ m. k This notion measures the thickness of the minimal overlap amongst n-tuples drawn from F, set equal to one more than the cardinality of the minimum overlap. By measuring this minimal thickness of family resemblance for different cardinalities of selections from F, σn (F), these numbers provide a partial ordering of family resemblance that allows us to compare different families and their relations in a variety of ways. Recently, Jennings, Schotch and Brown have returned to work on the