A constructive view of truth Challenging the paradigm
The non-classical logical systems presented in the previous sections kept the usual logical rules for introducing and eliminating connectives, but incorporated different paradigms of reasoning by restricting the structural rules which define inference at a more abstract level. In this section, we look at another alternative logical paradigm based on a radically different concept of truth.
A fundamental assumption of the classical logical outlook is that every proposition has one of two truth values: either it is true or it is false, in virtue of the facts constituting the world. This principle of bivalence is directly reflected in the inferences validated by classical logic, and most obviously in the "law of the excluded middle"
⊢ p OR NOTp
According to this, where p is absolutely any proposition whatsoever, either it is a correct description of reality or else its negation is. Such a view, however, invites the question of what makes p true or makes it false. In the case of a garden-variety claim such like 'There is a book on the table' perhaps it is plausible to think of the truth value of the statement as arising from the relationship between it and a piece of physical reality: there stands the table; if there is a book on it, then there is a piece of the universe that contains the items mentioned in the statement, related to each other as the statement says, so there is some sort of correspondence between the facts in the world and the statement made about it; if there is no book on the table, then the bits and pieces of reality are disposed in a way inconsistent with the statement, which is to say conforming to its negation, so in that case we can think of the falsehood of the statement as determined by the facts. The facts here do not depend on anything extraneous such as our theories, our investigations or even our language. The world stands as it does independently of us, finished and complete, and provides a truth value for every assertion we can make.
This picture of truth as correspondence with an external and complete reality, however, looks less plausible when applied to certain other uses of language. Consider mathematical claims, for instance. We may well feel less comfortable with the idea that there is a mathematical reality "out there", independent of our mathematical theories, of which those theories are a true or false description. The law of the excluded middle is the assertion that every question has an answer, and this seems a strong claim to make about a mathematical domain that we have not even constructed yet, especially as some questions about it may be undecidable in principle. It is therefore at least worth considering an alternative view, that the world—everything that is the case—is not entirely determined by the disposition of "stuff out there"; on the contrary, it may be incomplete pending further construction.
Suppose, then, that truth is not absolute and fixed, but is relative to a state of the world, and that there might be many such states, at least potentially. Cases in which such an idea is at least interesting include:
-
Mathematics, where what makes a statement true is that
it has a proof. If our mathematical theories get
extended (resulting in a new "state") then more things
will be provable, but there will always be
formulae A such that neither A
nor NOTA has a
proof.
-
Statements about the future, if we want to investigate
the logic of a world view on which the past and
present are fixed, but the future is not real until it
has been brought about.
- Vague descriptions (see the page of these notes on vagueness and the sorites paradox). We might model a "state" of the world as one imposing some degree of precision on certain vague predicates. We could see statements as being made true where the boundaries of properties have been sufficiently fixed, but perhaps as remaining undetermined in less definite states.
A state of the world, then, supports some statements and not others. The statements it supports are those made true by the information which that state provides, so assertion of them would be correct given the state of things. Extensions of the state support more statements, because it is in the nature of "extension" that no information is lost, so truth increases with extension. Falsehood, however, does not enter the picture in the same way. An assertion p may fail to be true (locally), but mere failure to be true is not the right surrogate for being made false by the local information, as there may be extensions of the state in which p is true after all. If p were made false, any such extension would contain whatever information made it false as well as new information making it true, and would hence be incoherent. In a good sense, falsehood is not another "truth value" as it is in the semantics of classical logic. On the view being considered here, the relationship between states and propositions is that of support, so the only value conferred by the information in a state is truth, and all we get in possible extensions of the state is more truth. A statement may fail to be made true, but that just means it lacks the value "true", not that it gets a different value. The only case in which we may properly regard p as false is that in which no extension of the state supports p.
The logic corresponding to this "constructive" notion of truth is known in the literature as intuitionistic logic. The semantic account of truth-functional connectives in intuitionistic logic follows the thoughts outlined above. Truth tables work in essentially the familiar way, but allowing for the possibility of extensions of the state where truth is being assessed. Conjunction and disjunction behave exactly in the classical manner, but negation does not. A conjunction A AND B is true in a state s if and only if both A and B are true in s. A disjunction A OR B is true in s if and only if at least one disjunct, A or B, is true in s. However, a negation NOTA is made true by s iff there is no extension of s in which A, is true. This is a rather strong condition, which is met if, for instance, s provides the means to derive a contradiction from A.
The conditional A IMP B is more of the same. Exactly as on the classical account, it records the availability of an inference from A to B, but naturally the warrant for such an inference remains in force if the state is extended, so a true conditional must support the IMPE inference from its antecedent to its consequent not only locally, but also in every possible extension of the local state. The upshot is that A IMP B is true in a state s iff B is true in every extension of s in which A is true. Since the absurd constant BAD can never be made true in any state, a good way to think of the negation NOTA is as simply an abbreviation for A IMP BAD.
Click here for a walkthrough of some examples using these semantic ideas to show sequents to be valid.
Quantifiers fit the picture as well. The domain over which the variables range is not fixed, but may increase as more things get constructed. Once an object has been constructed, it remains in existence through any extensions of the state, but until it has been constructed it is not there to be talked about. Hence the domain of a "larger" state is a superset of the domain of a "smaller" one. That means that names may fail to refer in a given state, and only get their references in extensions—in that case, atomic formulae in which those names occur cannot be true in the base state, but they may or may not be false depending on how things turn out when the objects denoted by those names get constructed. Now the universal quantifier ALL(x: Fx) Gx is like a conditional allowing an inference from F to G, so it is evaluated in much the same way as the corresponding implication: all the Fs which exist are also Gs, not only locally but at any "greater" stage as well even though it may, contain things that have not been constructed at the stage where the universal is being evaluated. The same is true of the unrestricted universal quantifier: ALLx Fx says that everything locally is F and everything that will be constructed in possible extensions will be F there. The existential quantifier, on the other hand, can be construed as saying that something satisfying a description exists here in the local state.
So the picture of multi-stage evaluation of truth conditions gives us an account of what the connectives and quantifiers might mean on a non-realist or "constructivist" view of truth. To turn this into a logic, we have to extend the story to deal with sequents. It isn't hard. A sequent X ⊢ A is valid if and only if every interpretation making everything in X true in any state makes A true in that same state as well. Clearly this is a consequence relation, and as an account of logic moreover it fits the motivating talk in Chapter 1 of these notes. It is not classical logic, however. Crucially, the sequent
NOTNOTp ⊢ p
is not valid. This can be seen from the simplest possible non-classical structure consisting of two states, one extending the other. We can let p be true in just the extended state; then NOTp is true in neither state, so its negation NOTNOTp holds in the "smaller" state although p does not. Other simple classical "laws" which are refuted by the same little two-state structure include:
⊢ p OR NOTp
NOTp IMP q ⊢ p OR q
NOTp IMP q ⊢ NOTq IMP p
(p IMP q) IMP p ⊢ p
NOTALLx NOTFx ⊢ SOMEx Fx
ALLx (Fx OR Gx) ⊢ ALLxFx OR SOMExGx
Others which still hold in the two-state model but can fail if we introduce more states include:
⊢ NOTp OR NOTNOTp
NOT(p AND q) ⊢ NOTp OR NOTq
p IMP (q OR r) ⊢ (p IMP q) OR (p IMP r)
⊢ (p IMP q) OR (q IMP p)
Click here and here to walk through some of these examples.
For intuitively convincing counter-examples, consider some cases based on the motivating applications given above. Look at the inference from NOT(p AND q) to NOTp OR NOTq for instance. For a case from mathematics, consider that we can obviously prove that a given real number is not both rational and irrational, but we may not be able to prove that it is not rational or that it is not irrational: the question may be undecidable given current mathematical theory. Again, consider an example from the indeterminacy of the future: suppose Joe is in the process of deciding whether to marry Mary or marry Jane. It is already determinately the case that he won't marry both of them, but it is not yet determined which of the two he won't marry, so there is nothing in the world (yet) to make the disjunction true.
We obtain a natural deductive calculus for intuitionistic logic in two steps. The first step is to drop from the classical systyem the rule NOTNOTE, leaving everything else as it stands. The resulting logical system is called minimal logic and it is of course properly weaker than classical logic. A convenient way to think of minimal logic is to think of negation as a defined connective, and see NOTA as meaning A IMP BAD. With this reading, the rules NOTI and NOTE are just the special cases of IMPI and IMPE where the consequent of the conditional is BAD. The false constant BAD has no special properties in minimal logic: its role could be played by an arbirary formula such as q, and the logic of negation is simply part of the logic of implication. This is the version of intuitionistic natual deducion implemented in the proof editor: to prove sequents constructively, simply choose "Constructive" from the drop-down menu of available logics, or pass "l=int" as a field in the url query string.
To obtain the full intuitionistic logic we must strengthen minimal logic by giving BAD the special property of being an absurd proposition. We do this by adding a rule saying that it implies everything. Alternatively, and perhaps preferably, the NOTE rule can simply be strengthened to state that any B is an immediate consequence of A and NOTA. This form of the rule has the existing NOTE as a special case, and removes the need for a separate "absurdity" rule.
All rules of the orthodox natural deduction calculus with the exception of NOTNOTE are intuitionistically valid—indeed, they are all valid in minimal logic. It follows that every classical proof of an intuitionistically invalid sequent such as any of the above sequents must use NOTNOTE somewhere.
Notes and further reading
Intuitionistic logic is presented here simply as a formal system, as an alternative to the orthodox "classical" one. The semantic account in terms of what are usually termed "Kripke models" and the natural deduction system were chosen in order to present the logic as a theory of valid inference, in keeping with the rest of these notes, rather than as a theory about mathematical proof or about computable functions. No particular philosophy of mathematics is presupposed, and no particular philosophy of language either: we simply take it that the state of the world supports (somehow) some assertions, that such a state may be incomplete and hence extensible, and that any extension will support at least the same assertions. That idea may be congenial to certain "anti-realist" theories of truth, but such a viewpoint is not required here.
The logic originated around a century ago and has been investigated intensively, as has the related field of constructive mathematics. Fragments of intuitionistic logic, in particular the negation-free part and the part whose only connective is 'IMP', have been found to have deep connections to the theory of computation, and explanations of this and similar logics are frequently given in terms of "realizability" (first formulated by Kleene in 1945). Care must be taken in combining the notion of "extension" with readings of the connectives in terms of provability, since if a state t extends a state s then in state t, "provable" has to mean "provable in s"—otherwise formulae would not mean the same in t as they did in s, so we would not expect truth to be preserved by extensions of states.
As entry points to the literature, see Mark van Atten's excellent Stanford Encyclopedia article vanAtten on the development of intuitionistic logic and the one on intuitionistic logic itself Moschovakis by Joan Moschovakis in the same collection. The classic exposition is that of Arend Heyting Heyting. See also Michael Dummett's Elements of Intuitionism DummettI for a perspective from the philosophy of language. For a readable introduction to realizability, see Jaap van Oosten's 2002 "historical essay" vanOosten which however touches on mathematical fields beyond the scope of these notes.