by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]
[Logic and Semantics, entry directory]
[Graham Priest, entry directory]
[Priest, Introduction to Non-Classical Logic, entry directory]
[The following is summary of Priest’s text, which is already written with maximum efficiency. Bracketed commentary and boldface are my own, unless otherwise noted. I do not have specialized training in this field, so please trust the original text over my summarization. I apologize for my typos and other unfortunate mistakes, because I have not finished proofreading, and I also have not finished learning all the basics of these logics.]
Summary of
Graham Priest
An Introduction to Non-Classical Logic: From If to Is
Part I
Propositional Logic
6
Intuitionistic Logic
6.3
Possible Worlds Semantics for Intuitionism
Brief summary:
(6.3.1) We will examine a certain sort of possible world semantics to capture the ideas of intuitionistic logic. (6.3.2) The only connectives in our intuitionist logic are ∧, ∨, ⇁ and ⊐ (with the last two being negation and the conditional, respectively). (6.3.3) Our intuitionistic possible worlds semantics takes the structure ⟨W, R, v⟩. It is mostly the same as logic Kρτ, meaning that it is a normal modal logic in which the R accessibility relation is reflexive (all worlds have access to themselves) and transitive (whenever a first world has access to a second and that second to a third, then the first has access to that third as well.) There is one additional constraint, called the heredity condition, which means that when a proposition is true in one world, it it is true in all other worlds that are accessible from it. (6.3.4) By means of certain rules we evaluate molecular formulas. Negation and the conditional involve accessible worlds. (6.3.5) The heredity condition holds not just for propositional parameters but for all formulas. (6.3.6) To see how the above interpretation captures intuitionist ideas, we first conceive of the way that information accumulates over time as being like one world (like our world at one moment) as being a set of proven things and another world accessible from the first having the same proven things and maybe more (like our world progressing later into a world perhaps with more information). (6.3.7) The possible world semantics for intuitionism captures the ideas in the proof conditions. (6.3.8) We define validity in intuitionistic logic as truth preservation over all worlds of all interpretations, and we write intuitionistic logical consequence as ⊨I. (6.3.9) If there is only one world, the intuitionistic interpretation is equivalent to a classical one. And intuitionistic logic is a sub-logic of classical logic, because everything that is intuitionistically valid is classical valid, but not everything classical valid is intuitionistically valid. (6.3.10) By adding constraints the R accessibility relation in intuitionistic logics, we can generate stronger ones.
[Possible-World Semantics for Intuitionism]
[The Connectives of Intuitionistic Logic (∧, ∨, ⇁ and ⊐)]
[The Structure and Constraints of Intuitionistic Possible Worlds Semantics]
[Evaluating Molecular Formulas]
[Heredity Condition for Formulas]
[Worlds as Information States. Time and Proof Accumulation]
[Proof Conditions Corresponding to Semantics for Molecular Formulas]
[Validity and Logical Consequence]
[Intuitionistic Logic’s Relation to Classical Logic]
[Constraining R]
Summary
[Possible-World Semantics for Intuitionism]
[We will examine a certain sort of possible world semantics to capture the ideas of intuitionistic logic.]
[Briefly recall some of the main ideas from the prior section. We first noted that we can understand the meaning of sentences we never heard of before (6.2.1). One explanation for this is compositionality, which says that “the meaning of a sentence is determined by the meanings of its parts, and of the grammatical construction which composes these” (p.103, section 6.2.2). If meaning is given by truth-conditions, then by compositionality the meaning of sentences built-up using connectives is based on the truth-functionality of the connectives (6.2.3). Truth itself according to a correspondence theory is the correspondence of what a formula says and the facts of an extra-linguistic reality. But what about mathematical formulas? Are there real, extra-linguistic mathematical objects? (6.2.4) Mathematical realists hold that there is an extra-linguistic reality corresponding to the truths of mathematical formulations like “2 + 3 = 5;” they think for example that there are “objectively existing mathematical objects, like 3 and 5.” Intuitionists however think rather that we should not apply the correspondence theory of truth to mathematical formulations (6.2.5). Intuitionism expresses a statement’s meaning on the basis of its proof conditions, which are the conditions under which the sentence is proved (6.2.6). The proof condition of a simple sentence is whatever we would take to be a sufficient proof, and those for complex sentences that are built up using connectives will be similar to the normal conditions only now using the notion of proof (note that ⇁ and ⊐ symbolize negation and the conditional):
A proof of A ∧ B is a pair comprising a proof of A and a proof of B.
A proof of A ∨ B is a proof of A or a proof of B.
A proof of ⇁A is a proof that there is no proof of A.
A proof of A ⊐ B is A construction that, given any proof of A, can be applied to give a proof of B.
(104, section 6.2.7)
Lastly, we noted that these proof conditions cannot validate excluded middle, because there are formulas that cannot be proved nor can it be proven that there is no proof for them (6.2.8).] In order to capture these intuitionistic ideas, we turn now to a certain sort of possible world semantics (105).
[The Connectives of Intuitionistic Logic (∧, ∨, ⇁ and ⊐)]
[The only connectives in our intuitionist logic are ∧, ∨, ⇁ and ⊐ (with the last two being negation and the conditional, respectively).]
[Recall from section 6.2.7 that our intuitionistic logic has conjunction, disjunction, negation, and the condition, only now defined in terms of proof conditions and with ⇁ and ⊐ symbolizing negation and the conditional, respectively:
A proof of A ∧ B is a pair comprising a proof of A and a proof of B.
A proof of A ∨ B is a proof of A or a proof of B.
A proof of ⇁A is a proof that there is no proof of A.
A proof of A ⊐ B is A construction that, given any proof of A, can be applied to give a proof of B.
(p.104, section 6.2.7)
] “The language of propositional intuitionist logic is a language whose
only connectives are ∧, ∨, ⇁ and ⊐” (105).
[The Structure and Constraints of Intuitionistic Possible Worlds Semantics]
[Our intuitionistic possible worlds semantics takes the structure ⟨W, R, v⟩. It is mostly the same as logic Kρτ, meaning that it is a normal modal logic in which the R accessibility relation is reflexive (all worlds have access to themselves) and transitive (whenever a first world has access to a second and that second to a third, then the first has access to that third as well.) There is one additional constraint, called the heredity condition, which means that when a proposition is true in one world, it it is true in all other worlds that are accessible from it.]
[Let us take a moment to recall some matters of possible worlds semantics for modal logics. The most basic modal logic is called K.(section 2.1.2). The interpretation in our modal semantics will involve the truth-valuation function v, but it also requires that we specify the world in question (from the set of worlds, W); and for the modal operators, we specify the accessibility relation (R) of the worlds in question. ‘uRv’ means either, “world v is accessible from u” or “in relation to u, situation v is possible” (or “world u accesses world v.”) The interpretation then takes the form: ⟨W, R, v⟩ (section 2.3.3). To evaluate for connectives, we must keep in mind which world the evaluation is for:
vw(¬A) = 1 if vw(A) = 0, and 0 otherwise.
vw(A ∧ B) = 1 if vw(A) = vw (B) = 1, and 0 otherwise.
vw(A ∨ B) = 1 if vw(A) = 1 or vw(B) = 1, and 0 otherwise.
(p.21, section 2.3.4)
The accessibility relation was important for evaluating the modal operators, so let us recall them too, because we will use the accessibility relation for negation and the conditional in our intuitionistic semantics.
For any world w ∈ W:
vw(◊A) = 1 if, for some w′ ∈ W such that wRw′, vw′(A) = 1; and 0 otherwise.
vw(□A) = 1 if, for all w′ ∈ W such that wRw′, vw′(A) = 1; and 0 otherwise.
(22, section 2.3.5)
And validity was defined in the following way:
An inference is valid if it is truth-preserving at all worlds of all interpretations. Thus, if Σ is a set of formulas and A is a formula, then semantic consequence and logical truth are defined as follows:
Σ ⊨ A iff for all interpretations ⟨W, R, v⟩ and all w ∈ W: if νw(B) = 1 for all B ∈ Σ, then νw(A) = 1.
⊨ A iff φ ⊨ A, i.e., for all interpretations ⟨W, R, v⟩ and all w ∈ W, νw(A) = 1.
(p.23 section 2.3.11)
As we said, the most basic normal modal logic is called K (section 3.2.2). Certain constraints on the accessibility relation, R, can generate variations on this modal logic, including:
ρ (rho), reflexivity: for all w, wRw.
σ (sigma), symmetry: for all w1, w2, if w1Rw2, then w2Rw1.
τ (tau), transitivity: for all w1, w2, w3, if w1Rw2 and w2Rw3, then w1Rw3.
η (eta), extendability: for all w1, there is a w2 such that w1Rw2.
(p.36, section 3.2.3)
Our intuitionistic possible worlds semantics will have this same structure of ⟨W, R, v⟩. It will also be the same interpretation as a normal logic Kρτ, meaning that it is reflexive (all worlds have access to themselves) and transitive (whenever a first world has access to a second and that second to a third, then the first has access to that third as well.) There is one additional constraint, called the heredity condition, which means that when a proposition is true in one world, it it is true in all other worlds that are accessible from it.]
An intuitionist interpretation for the language is a structure, ⟨W, R, v⟩, which is the same as an interpretation for the normal modal logic Kρτ (so that R is reflexive and transitive) apart from one further constraint, namely that for every propositional parameter, p:
for all w ∈ W, if vw(p) = 1 and wRw′, vw′ (p) = 1
This is called the heredity condition.
(105)
[Evaluating Molecular Formulas]
[By means of certain rules we evaluate molecular formulas. Negation and the conditional involve accessible worlds.]
[We can assign values to formulas that are built up using connectives by using certain rules. A conjunction is true in a world if in that same world both conjuncts are true (and otherwise false). A disjunction is true in a world if in that same world either disjunct is true (and otherwise false). A negation is true in a world if in all worlds accessible from it are false (and otherwise the negation is false). And a conditional is true in a world if in all worlds accessible from it, either the antecedent is false or the consequent is true (and otherwise the conditional is false). Now recall that:
vw(¬A) = 1 if vw(A) = 0, and 0 otherwise.
(p.21, section 2.3.4)
vw(□A) = 1 if, for all w′ ∈ W such that wRw′, vw′ (A) = 1; and 0 otherwise.
(22, section 2.3.5)
Our intuitionistic rule here for negation is:
vw(⇁A) = 1 if for all w′ such that wRw′, vw′ (A) = 0; otherwise it is 0.
(105)
In intuitionistic logics, suppose that in one world (⇁A) = 1. According to the heredity condition, that means all worlds accessible from the first also have (⇁A) = 1. That would furthermore satisfy the definition for the necessity operator. I am just guessing that this is what Priest means by “Note that ⇁A is, in effect, □¬A.” And perhaps it is for similar reasons that “A⊐B is, in effect, □(A ⊃ B).”]
The assignment of values to molecular formulas is given by the following conditions:
vw(A ∧ B) = 1 if vw(A) = 1 and vw(B) = 1; otherwise it is 0.
vw(A ∨ B) = 1 if vw(A) = 1 or vw(B) = 1; otherwise it is 0.
vw(⇁A) = 1 if for all w′ such that wRw′, vw′ (A) = 0; otherwise it is 0.
vw(A⊐B) = 1 if for all w′ such that wRw′, either vw′ (A) = 0 or vw′ (B) = 1; otherwise it is 0.
Note that ⇁A is, in effect, □¬A, and A⊐B is, in effect, □(A ⊃ B).1
(105)
1. Sometimes, the language is taken to contain a propositional constant, ⊥, which is true at no world. The truth conditions of ⇁A then reduce to those of A⊐⊥.
(105)
[Heredity Condition for Formulas]
[The heredity condition holds not just for propositional parameters but for all formulas.]
Priest then notes that on account of these truth conditions, the heredity condition holds for all formulas, not just the propositional parameters. The proof is in a footnote [see the quotation below for the details.]
Given these truth conditions, the heredity condition holds, as a matter of fact, not just for propositional parameters, but for all formulas. The proof is relegated to a footnote, which can be skipped if desired.2
(105)2. The proof is by induction on the construction of formulas. Suppose that the result holds for A and B. We show that it holds for ⇁ A, A ∧ B, A ∨ B and A ⊐ B. For ⇁ A: we prove the contrapositive. Suppose that wRw′, and ⇁ A is false at w′. Then for some w′′ such that w′Rw′′, A is true at w′′. But then wRw′′, by transitivity. (cont. on next page) | Hence, ⇁ A is false at w. For A ∧ B: suppose that A ∧ B is true at w, and that wRw′. Then A and B are true at w. By induction hypothesis, A and B are true at w′. Hence, A ∧ B is true at w′. For A ∨ B: the argument is similar. For A ⊐ B: we again prove the contrapositive. Suppose that wRw′ and A ⊐ B is false at w′. Then for some w′′ such that w′Rw′′, A is true and B is false at w′′. But, by transitivity, wRw′′. Hence A ⊐ B is false at w.
(105-106)
[Worlds as Information States. Time and Proof Accumulation]
[To see how the above interpretation captures intuitionist ideas, we first conceive of the way that information accumulates over time as being like one world (like our world at one moment) as being a set of proven things and another world accessible from the first having the same proven things and maybe more (like our world progressing later into a world perhaps with more information).]
Priest now shows how the above intuitionist interpretation “captures the intuitionist ideas of the previous section” (106). Priest has us conceive of a world as being constituted by a state of information at some particular time. And he says that “intuitively, the things that hold at it are those things which are proved at this time” (106). [So the idea seems to be that a world is a body of knowledge, which is made of proven things. For the next idea perhaps we should think about how our human knowledge accumulates as we continue to learn new things. And so we can think of the next moment when we have more or the same amount of proven things to be like another world that is accessible from the previous one. That accessibility I suppose means that whatever was true in the past remains true in the future, and maybe new proven things are added.]
Before we complete the definition of validity, let us see how an intuitionist interpretation arguably captures the intuitionist ideas of the previous section. Think of a world as a state of information at a certain time; intuitively, the things that hold at it are those things which are proved at this time. uRv is thought of as meaning that v is a possible extension of u, obtained by finding some number (possibly zero) of further proofs. Given this understanding, R is clearly reflexive and transitive. (For τ: any extension of an extension is an extension.) And the heredity condition is also intuitively correct. If something is proved, it stays proved, whatever else we prove.
(106)
[Proof Conditions Corresponding to Semantics for Molecular Formulas]
[The possible world semantics for intuitionism captures the ideas in the proof conditions.]
[In section 6.3.4 above, Priest listed the following recursive conditions for evaluating molecular formulas.
vw(A ∧ B) = 1 if vw(A) = 1 and vw(B) = 1; otherwise it is 0.
vw(A ∨ B) = 1 if vw(A) = 1 or vw(B) = 1; otherwise it is 0.
vw(⇁A) = 1 if for all w′ such that wRw′, vw′ (A) = 0; otherwise it is 0.
vw(A⊐B) = 1 if for all w′ such that wRw′, either vw′ (A) = 0 or vw′ (B) = 1; otherwise it is 0.
(105)
Priest says that the these follow naturally from the provability conditions from section 6.2.7:
A proof of A ∧ B is a pair comprising a proof of A and a proof of B.
A proof of A ∨ B is a proof of A or a proof of B.
A proof of ⇁A is a proof that there is no proof of A.
A proof of A ⊐ B is A construction that, given any proof of A, can be applied to give a proof of B.
(p. 104, section 6.2.7)
Priest looks first at conjunction. Compare:
A proof of A ∧ B is a pair comprising a proof of A and a proof of B.
vw(A ∧ B) = 1 if vw(A) = 1 and vw(B) = 1; otherwise it is 0.
We want to capture the idea behind the first line, that a conjunction is proven if each conjunct is proven. I am not certain, but Priest might be suggesting that part of the idea or thinking behind that first line is that the proofs would be available at the same time. (For, if something will be proven in the future, we now do not have a proof of it.) So with what we said above in section 6.3.6 about time, we would say that the second line, by designating the same world for both conjunctions, captures that notion that the proofs for both conjuncts are available at the same time. Similar reasoning seems to be used in the case of disjunction. For negation, things get more interesting. Compare:
A proof of ⇁A is a proof that there is no proof of A.
vw(⇁A) = 1 if for all w′ such that wRw′, vw′ (A) = 0; otherwise it is 0.
The idea in the first line is that a negation under intuitionistic assumptions means not that there is no proof but rather we have a proof that there is no proof. That implies that at no moment in the future will there be any such proof. So with the ideas regarding worlds and time, that means no accessible world (or no future state of our world) will have a proof for the formula. A similar sort of reasoning seems to be involved with the conditional, but it is a little more complex (see the quotation below).]
Given the provability conditions of 6.2.7, the recursive conditions of 6.3.4 are also very natural. A ∧ B is proved at a time iff A is proved at that time, and so is B; A ∨ B is proved at a time iff A is proved at that time, or B is. If ⇁ A is proved at some time, then we have a proof that there is no proof of A. Hence, A will be proved at no possible later time. Conversely, if ⇁ A is not proved at some time, then it is at least possible that a proof of A will turn up, so A will hold at some possible future time. Finally, if A ⊐ B is proved at a time, then we have a construction that can be applied to any proof of A to give a proof of B. Hence, at any future possible time, either there is no proof of A, or, if there is, this gives us a proof of B. Conversely, if A ⊐ B is not proved at a time, then it is at least possible that at a future time, A will be proved, and B will not be. That is, A holds and B fails at some possible future time.
(106)
[Validity and Logical Consequence]
[We define validity in intuitionistic logic as truth preservation over all worlds of all interpretations, and we write intuitionistic logical consequence as ⊨I.]
Validity in intuitionist logic “is defined as truth preservation over all worlds of all interpretations” (106). And, “We will write intuitionistic logical consequence as ⊨I, when necessary” (106).
[Intuitionistic Logic’s Relation to Classical Logic]
[If there is only one world, the intuitionistic interpretation is equivalent to a classical one. And intuitionistic logic is a sub-logic of classical logic, because everything that is intuitionistically valid is classical valid, but not everything classical valid is intuitionistically valid.]
[The next idea is that if we only have one world, then the rules from section 6.3.4 reduce to classical conditions. But what about negation?
vw(⇁A) = 1 if for all w′ such that wRw′, vw′ (A) = 0; otherwise it is 0.
The idea here might be that our one world has access to itself, so it is just like saying that a negation is true if its non-negated formulation is false in that world (and the negation is false otherwise). The next idea is harder for me to grasp, so please jump to the quotation. I will guess it is the following. Suppose something is intuitionistically valid. I am not sure, but I assume that means it holds in all accessible worlds. But in a classical interpretation, there would only be one reflexively accessible world. And it only needs to hold for that world. So anything that is intuitionistically valid is also valid under a classical interpretation, because perhaps we simply think of it as being valid in the one and only world. Priest says that not everything that is classically valid is intuitionistically valid, and thus intuitionistic logic is a sub-logic of classical logic.]
Observe that if an intuitionist interpretation has just one world, the recursive conditions for the connectives of 6.3.4 just reduce to the standard classical conditions. A one-world intuitionist interpretation is, in | effect, therefore, a classical interpretation. Thus, if truth is preserved at all worlds of all intuitionist interpretations, it is preserved in all classical interpretations. If an inference is intuitionistically valid, it is therefore classically valid (when ⇁ and ⊐ are replaced with ¬ and ⊃, respectively). The converse is not true, as we shall see. Hence, intuitionist logic is a sub-logic of classical logic.3
(106-107)
3. This is not true of intuitionist mathematics in general. Intuitionist mathematics endorses some mathematical principles which are not endorsed in classical mathematics; in fact, they are inconsistent classically. But because intuitionist logic is weaker than classical logic, the principles are intuitionistically consistent. For the record, it is worth noting that there is a certain way of seeing classical logic as a part of intuitionist logic too. For it can be shown that if Σ ⊢ A in classical logic, then ⇁⇁Σ ⊢I⇁⇁A, when all occurrences of ¬ and ⊃ are replaced by ⇁ and ⊐, and ⇁⇁Σ = {⇁⇁A: A ∈ Σ}. (The converse is obviously the case, given that intuitionist logic is a sub-logic of classical logic, and the law of double negation holds for the latter.) This was proved by V. Glivenko in 1929. It also follows (unobviously) that the logical truths of classical logic, expressible using only ∧ and ¬, are identical with those of intuitionist logic (when ¬ is replaced by ⇁). Every sentence of classical propositional logic is logically equivalent to one employing only ∧ and ¬. On these matters, see Kleene (1952, pp. 492–3).
(107)
[Constraining R]
[By adding constraints the R accessibility relation in intuitionistic logics, we can generate stronger ones.]
[Priest ends by noting certain logics that are stronger than intuitionistic logic but weaker than classical. They can be obtained by adding constraints to the accessibility relation. One kind has the constraint that the R relation must place the worlds into a linear order. (I am wondering if this is in any way related to the notion of a linear progress of time.) See the quotation for details.]
Note, finally, that logics stronger than intuitionist logic, but still weaker than classical logic, can be obtained by putting further constraints on the accessibility relation, R. These are usually known as intermediate logics. Perhaps the best known of these is a logic called LC, obtained by insisting that R be a linear order, that is, by adding the constraint that for all w1,w2 ∈ W, w1Rw2 or w2Rw1 or w1 =w2.
(107)
From:
Priest, Graham. 2008 [2001]. An Introduction to Non-Classical Logic: From If to Is, 2nd edn. Cambridge: Cambridge University.
Texts cited by Priest:
Kleene, S. C. (1952), Introduction to Metamathematics (Amsterdam: North-Holland).
.
No comments:
Post a Comment