Tag: modal logic

The curious logic of falsifiability

Bas van FraassenLeave a comment

The notion of falsifiability, which has had such a run for its money in philosophy of science, seems logically rather odd.  A hypothesis A is true or false, and perhaps it is made true or false by some fact, such as the fact that A.  But this bit of logic or semantics was not what was in play.  A hypothesis is falsified if there is or was or has actually been a specific public event which showed that it is false.  

Nevertheless, we can say some things about falsifiability from a logical point of view.  

Logic.

The logical background here is classical sentential logic, and I want to note especially the principle, for any modal logic, that logical equivalents are mutually substitutable everywhere.  Symbols T and ⊥ will stand respectively for any classical tautologies and for any negation of a classical tautology.  The modal connector [F] will be read as  “It has been falsified that”.

I will call the logic of falsifiability Lfalse.  It is a system  of modal logic (as defined e.g. in Chellas 1980: section 2.4).

Obviously, if A is true then it has not been falsified that A.  Not truly, anyway.  This implies that the tautology has not been falsified (even if that were to make sense):

  1. A╞ ~F[A]
  2. ⊢ ~[F]T

It follows at once that the logic of falsifiability is not a normal modal logic.  In the usual possible world semantics for normal modal logics, only the two operators □ and ◊ and their combinations are definable, and both □T and ◊T are valid.  

But we can hope for accommodating the logic of falsifiability in neighborhood semantics. 

The most important principle of falsifiability is:  if it has been falsified that A, and B implies A, then B has been falsified (along the way).   Thus [F] is antitone: 

3. If A ⊢ B then [F]B  ⊢ [F]A   

What about self-contradictions?  

We might be inclined to say that anything and everything falsifies a self-contradiction.  But how?  Does it make sense at all to try and refute a self-contradiction by experiment? 

Maybe not, in common sense.  But logic, and specifically principle 3., saves us from worrying about that.  Because falsification is antitone, a conjunction is falsified if either conjunct has been falsified.  But note that, for any sentence B, if C is a self-contradiction, then C is logically equivalent to the conjunction (C & B).  Hence C can be falsified by falsifying B, and B can be anything whatsoever. Therefore, if any proposition at all has been falsified then so have all self-contradictions.  This gives us the principle 

4. [F]A ⊢ [F]⊥

Disjunction.

A disjunction has not been falsified unless both disjuncts have been falsified.  I suppose that is obvious – if we only falsify that radio-active decay is linear, we have not falsified that it is either linear or exponential.  So [F](A v B) implies that both [F]A and [F]B.

But also, a hypothesis can be falsified by exhausting its possibilities, case by case.  Most simply: the disjunction A v B will have been falsified if both A and B have been. These points require validity for:

5. [F]A & [F]B  ⊢ [F](A v B)

6. [F](A v B) ⊢ [F]A & [F]B

From 2. and 5. we deduce the corollary that it is not possible for both [F]A and [F]~A to be true.  Note also that 6. already follows from 3.

Conjunction.

Do we get dual principles for conjunction?  That would mean that if [F](A & B) then either [F]A or [F]B.  The converse is obvious, and follows from the fact that [F] is antitone.  But could there be some sort of holism, to allow that some experiment would fail to falsify either A or B but still rule out that both are the case?  (Thanks to Brandon Hopkins for talking me through all the implications.)

In fact, yes.  Imagine a room in which the central light is controlled by two switches, S1 and S2, one on each end.  The light is on if and only if both switches are Up or both switches are Down.  This is a disjunction of two conjunctions.  By showing that the light is on I falsify that disjunction.  A fortiori I falsify the conjunctions (S1 is Up and S2 is Up) and (S1 is Down and S2 is Down).  But of neither conjunction have I falsified either conjunct. I have not falsified either that S1 is Up or that S2 is Up or that S1 is Down or that S2 is Down.

So all we have as a principle for conjunction is 

7. [F]A ⊢ [F](A & B)

which already follows from 3.  So ‘and’ and ‘or’ or not simply each other’s dual in this context.

The class of SirK frames.

In neighborhood semantics each world has as its neighborhood a set of propositions, that is, a set of sets of worlds.  The sentence [F]A is true in a world w exactly if the set of worlds in which A is true belongs to the neighborhood of w.  

More formally:

The above principles of the logic of falsifiability will be valid in the following class of frames, which as historical homage I will call SirK:

  • A frame is A couple G = <W, N>, where W (the worlds) is a non-empty set, and N a function that assigns a set of subsets of W to each member of w (its neighborhood)
  • A frame G = <W, N> is a SirK frame if for each w in W, N(w) is a proper ideal (is closed downward, contains the join of two propositions iff it contains both, and does not contain W).
  • Truth conditions for sentences are as usual, with an assignment ||  || of a subset ||A|| of W to each sentence A (the set of worlds in which A is true), with [F]A true in w exactly if ||A|| is in N(w).

SPLIT.

It may be interesting to ask how it fares here with the SPLIT principle:

            SPLIT.  ⊢ A ⊃ { ~[F]~(A & [Q]A) &  ~[F]~(A & ~[Q]A)}

or equivalently, 

            SPLIT.  ⊢ A ⊃ { ~[F](~A v ~[Q]A) &  ~[F](~A v [Q]A)}

As established by Ding and Holliday (2020), SPLIT cannot be added consistently as an axiom to any modal logic which has theorem []T, and is sound in neighborhood semantics.  Their counterexample involves choosing a unit set {w} as the proposition ||A||, and showing that for this choice SPLIT is not true in w.

No such counterexample can appear for the logic of falsifiability with the neighborhood semantics as specified.  

To begin we can see that SPLIT is true in any world in which ~A has not been falsified (for then ||~A|| is not in the neighborhood and hence, for any B, ||~A v B|| is not in the neighborhood:  

Theorem.  ~[F]~A ⊃  SPLIT is valid in all SirK frames.

So the question is just whether there is any example in which A is true in a world w, but the neighbourhood of w must contain, for some B, either ||~A v B|| or ||~A v ~B||.  

The answer is (trivially) No: the empty set 𝜙 is a proper ideal.  

To get a counterexample to SPLIT, whatever ||A|| and ||Q(A)|| are, there must be a world w such that A is true in w and either  ||~A v ~[Q]A|| or   ||~A v [Q]A)|| is in N(w).    

Hence when A is true in w and N(w) = 𝜙, both ancedent and consequent of SPLIT are true.

APPENDIX. Completeness of logic Lfalse

Logic Lfalse has, as any modal logic, for sets of sentences X and sentence A, the rule of inference

RPL.  X├A if A is a classical tautological consequence of X.

Given the way we found it convenient to state the principles, we add:

X, A├ B iff X├ A ⊃ B

which appears otherwise as the Deduction Theorem, again valid for all modal logics.

In addition to these rules here are, this time with mnemonic names, the principles:

Verum. A╞ ~F[A]

Antitone.  if A ⊢ B then [F]B  ⊢ [F]A   

Falsum.  [F]A] ⊢ [F]⊥

V-intro.  [F]A & [F]B  ⊢ [F](A v B) 

and note that we have as theorems:

Verum+.  ⊢ ~[F]T

V-elim. [F](A v B) ⊢ [F]A & [F]B

&-intro. [F]A ⊢ [F](A & B).

While soundness of Lfalse for the class of SIRK frames is clear from the informal discussion above, the following will establish its completeness.

The smalllest canonical model (cf. Chellas 1980: 252-4) for Lfalse is the frame Gmin = <W, N> with the interpretation || ||, where:

  • W = the set of maximal consistents sets of Lfalse,
  • for w in W, N(w) = {||A||: [F]A is in w}
  • if p is an atomic sentence then ||p|| = {w in W: p is in w}

Note that it follows that for each sentence A, ||A|| = {w in W: A is in w}.

It is a general theorem for the family of modal logics, as defined in Chellas (1980), that if G is any canonical model for a modal logic then A is a theorem of that logic if and only A is valid in G.  Hence for Gmin:

Lemma. A ⊢ B in Lfalse if and only if ||A|| ⊆ ||B|| in Gmin

To be shown here is that this canonical model of Lfalse belongs to the class SirK of frames.  That is to say: in Gmin, for each w in W, N(w) is a proper ideal in the ⊆ ordering of the propositions.  

Theorem.  In Gmin, for all w, N(w) is a proper ideal.

For each w in W, we argue that its neighbourhood is:

Downward closed.  If ||A|| is in N(w) and ||B|| ⊆ ||A|| then [F]A is in w and B ⊢ A.  So [F]B is in w, and hence ||B|| is in N(w).

Closed under unions.   If ||A|| and ||B|| are in N(w) then [F]A and[F]B are in w.  Hence [F](A v B) is in w, and therefore ||A v B|| = ||A|| ∪ ||B|| is in N(w).

Proper.  W is in N(w) iff [F]T is in w.  But w contains ~[F]T, by theorem Verum+, and w is consistent.  Therefore W is not in N(w).

REFERENCES

Chellas, Brian F.  (1980) Modal Logic: An Introduction.  Cambridge

Ding, Yifeng and Holliday, Wesley Halcrow (2020) “Another Problem in Possible World Semantics”.  Berkeley Faculty Publications.

Modality and Negation before 1932

Bas van FraassenLeave a comment

Lewis and Langford’s Symbolic Logic (1932) was the culmination of work over the previous half-century.  This is a well-studied development, and I do not have anything new to say.  But I would like to add some comments on the role of negation.

1.      Exclusion, choice, and strong negation

When Gerrit Mannoury discussed Intuitionism he placed much weight on the distinction between exclusion negation and choice negation.  The latter is a form of negating a proposition that presupposes a definite contrast class, with a meaning that is something like “not this, but one of the others”. For example, “the apple is not ripe” would typically be understood as asserting that the apple is a real apple in one of the stages before ripeness.  The context would supply that definite contrast class.  If we read that statement with “not” as exclusion negation, the contrast would be totally indefinite: the apple is raw, or it is rotten. or it is a fake porcelain apple, or it is a painted apple in a Rembrandt still life, or ….  

That distinction shed some light on the Intuitionists’ approach to infinity.  But Intuitionist negation, as it appears in Heyting’s logic, does not fit either.  Within mathematics, as the Intuitionists present it, a statement can be negated only on the basis that it leads to a self-contradiction. In the logic, the negation of A is A → f, where f is the falsum, the absolute absurdity.

I will call this third form strong negation.  Outside Intuitionism, or at least outside its original presentation in terms of proofs and refutations, we can explain it this way:  

        to assert ¬A, in the sense of a strong negation, is to assert that A is not possibly true. 

Strong negation appears in modal logic generally, and specifically in Lewis’ early work.

However, the principles that govern strong negation are saliently different from the familiar ones characteristic of choice negation.

2.      Choice negation is ‘classical’

In lattice theory the complement x’ of element x is the largest element y such that x ∧ y = 0 (‘x and y are disjoint’), if it exists.[1]  That it is the largest means that if z is any element disjoint from x then z  ≤  x’.   Clearly, if we have several negations in the language they cannot all be like that.  

In view of the many options that have been broached on this subject, it may be best to mention some suggested characteristics in various treatments of negation, and to ask which are satisfied in specific cases.

I will call a negation classical if its corresponding operation ‘ on a lattice of propositions meets three conditions:

x ∧ x’ = 0           (disjointness)

(x’)’ = x                 (involution)

x ≤ y  iff  y’ ≤ x’    (antitone)

So when negation corresponds to an operation of that sort on a lattice of propositions, then negation obeys the principles

            (A & ¬A) implies the falsum                         (Non-Contradiction)

¬¬A entails, and is entailed by A                    (Double Negation)

A entails B if and only if ¬B entails ¬A.        (Contraposition)

Choice negation is classical.  For example, if the contrast class is a range of colors then “the apple is not-not red” is true iff the apple has a color in this range that is not one of the colors other than red, hence is red.  And, taking e.g scarlet to imply red, it is also the case that being other than red (in the intended range) implies being other than scarlet.

We may also note that if negation is defined by the two-valued truth-table, it is a choice negation, hence classical.

Is Exclusion negation classical?  I’ll discuss that in the Appendix.

Strong negation is not classical.  That the law of Double Negation does not hold in Intuitionistic logic is well known.  Contraposition is closely related to Reductio ad Absurdum of which one form (negation elimination) fails in Intuitionistic logic.  Below we’ll see how Contraposition fares in normal modal logic.  

3.      A quick note on Lewis’ relation to MacColl

Lewis’ theory of strong negation and the conditional is the same as MacColl’s, whose work he acknowledges.  (Lewis 1918, p. 292: “The fundamental ideas of the system are similar to those of MacColl’s Symbolic Logic and its Applications”.)

I will go chronologically backward for a moment to discuss Lewis first and then the earlier work by MacColl.

(I will adapt their notation, or use my own, as convenient.)

4.      C. I. Lewis chose strong negation as modal primitive

Lewis published his Survey of Symbolic Logic in 1918, and there presented his logic of strict implication with as modal primitive a strong negation connective ~.  

Notation:  I will now keep ¬ for just the truth-functional (material) negation. 

 The sentence ‘~p’ is to be read as ‘it is impossible that p’.  Then the strict conditional → is defined by:  

p → q =def ~(p & ¬q)

Lewis’ strong negation is intuitively at least the same as the Intuitionist’s.    For by the above definition,

            p → (q & ~q) = ~(p & ¬ (q & ¬q)) = ~p

given that logically equivalent formulas are mutually substitutable everywhere (and in normal modal logic the falsum is equivalent to any self-contradiction).

But Lewis was not guided by any precise semantics for modality,  and his vague intuitions led him astray.  Specifically he assumed that strong negation obeys Contraposition.  He had the, at first sight so innocent looking, principle

            2.21 (~q → ~p) → (p → q)

Two years later Lewis  published an emendation (Lewis 2020).  Emil Post had pointed out to him that this principle led to the theorem

            ~p = ¬ p

thus collapsing strong negation into material negation.  Lewis commented “Mr. Post’s example which demonstrates the falsity of 2.21 is not here reproduced, since it involves the use of a diagram and would require considerable explanation.” 

With our current preference for □ as primitive, we understand his 2.21 as

            2.21*.  □(¬◊q ⊃ ¬◊p) → □(p ⊃ q)

In the Appendix I will sketch a possible world model that gives us a counterexample to 2.21* [Hint: focus on the case of  ¬ ◊q being false.]

Dropping the ill-fated 2.21 did not do great damage to the logic of strict implication, which then eventually appeared in Lewis and Langford.

5.      Oskar Becker to C. I. Lewis:  nesting and iteration

But the theory of strict implication was not unchanged in other ways.  In 1930 there had appeared Oskar Becker’s monograph (Becker 1930) which discussed iterations and nestings of modal operators, with questions about how they are to be understood.  Lewis and Langford acknowledged this in their preface and wrote their famous Appendix II in response.  

Becker had proposed the following principles as possible additions to Lewis’ logic:

C10. □□p = □p

C11.  ◊p → □◊p

C12.  p → □◊p  (which Becker called the Brouwersche Axiom)

Lewis and Langford then defined five modal logics, S1-S5, in which (our familiar) S4 is S3 plus C10, and S5 is (our familiar) S4 plus C11 and C12.

But Becker’s questions about how C10.-C12. are to be understood were not very well answered.  We’ll see below how MacColl made a determined effort to establish the truth conditions for one case of an iterated modality, one that involves negation.

6.      Tracing it all back to Hugh MacColl

From a distance MacColl’s symbolism looks rather like arithmetic.  He introduces five modalities: true, false, certain, impossible, and variable.  Each has a Greek letter as its symbol, with ε (epsilon) for certainty  and η(eta) for impossibility, for example.  

But there seems at first to be a curious ambiguity.  The proposition that A is certain or necessary is symbolized Aε.  But then we also see ε entering as a propositional constant, for the absolutely certain, the ‘top’ or ‘unit’ of the algebra.

I think we can understand that this is not just a notational quirk.  In arithmetic, consider the sentences “3 + 2 = 5” and “32 = 9”.  The numeral “2” appears first as the name of a number, and then, in superscript, as the name of the squaring function.  We can give a good account of this: the symbol “32” the denotes the value of a certain function (exponentiation) applied to the ordered couple <3, 2>.  Superscripting is a convention to symbolize exponentiation.

modal statements, strong negation

In the same way we should understand MacColl’s formulation of modal statements.  In his commentary and examples they are clearly taken as de dicto: the assertion that it is certain that A is the assertion that A has a certain modal property, namely certainty.  The symbol “Aε” denotes the proposition which is the value of a certain function (we may call it propositional exponentiation) applied to the ordered couple <A, ε>.  The function is symbolized by the superscripting convention.

In the same way the assertion that A is impossible is symbolized Aη.  This is strong negation, it is what Lewis later symbolized as ~A.

propositional constants

But impossibility too is itself a proposition, the ‘bottom’ of the algebra, and we have the laws (MacColl uses ‘ for ordinary negation and . for conjunction):

A . ε = A                (ε is the unit, the top, the tautology)

A . η = η                (η is the bottom, the absurdity)

(A . A’)η                 (Law of Non-Contradiction)

Aε . (A’)ε = η

6.3 the strict conditional

MacColl defines a conditional:

            A : B =def  (A . B’)η   (It is impossible that A and not B)

That is exactly the definition that Lewis then chose for his strict conditional.  MacColl, who has the connective + for disjunction, points out that, equally, A : B = (A’ + B)ε, it is certain that either not-A or B.  

6.4 iterated and nested modal operators

Especially interesting is iterated propositional exponentiation, to symbolize nested modalities, a subject which, as we saw above, did not return in the literature till 1930.  MacColl writes (section 9, page 7):

The symbol ABC means (AB)C; it asserts that the statement AB belongs to the class C, in which C may denote true, or false, or possible, &c. Similarly ABCD means (ABC)D, and so on.  (MacColl 1906: 7)

So for example, (Aε)η is the statement that it is impossible that A is certain: what we would write as ~◊□A.

MacColl returns to this in section 22, where he writes “But, it may be asked, what is meant by statements of the second, third, &c., degrees, when the primary subject is itself a statement?”   What follows in that section, and in many other pasages, points to an understanding of logic as pertaining to information processing.  There is the suggestion that, for example, Aη may be a revision if A, made when new data arrive that are incompatible with A.  But I will leave that aside for now.

There is an interesting discussion of a nested modality in a later paper (MacColl 1910).  Here he finds what he takes at first blush to be an antinomy.  In his system the symbol θ stands for the modality variable, it is his term for what is possible but not certain, or equivalently, what is neither impossible nor certain.  So it could be defined:

Aθ = (Aε)’.(Aη)’ 

MacColl then writes:

The symbol Aθθ, in my system, is short for  (Aθ)θ and asserts that the statement Aθ is a variable.  The antinomy consists in the conflict of two arguments, of which the one professes to prove that the second-degree proposition Aθθ is an impossibility or self-contradiction; while the other professes to prove that it is not. (MacColl 1910: 196, with the initial “Aθ” corrected to “Aθθ”)

A first blush its natural reading looks entirely intelligible, or at least perfectly grammatical:

“It is neither certain nor impossible that it is neither certain nor impossible that A”.

But it becomes puzzling when we try to see under what conditions, or for what sort of statement A, this would be true or definitely false.

To prove the first option in the antinomy MacColm argues, first of all:

 A will itself be either certain, or impossible, or neither certain nor impossible.  If A is either certain or impossible then Aθ is clearly false.  

That seems correct, but then MacColl argues:

if A is neither certain nor impossible then it is certain (and hence not neither certain nor impossible) that Aθ.  And so again, Aθθ is false.  

Therefore Aθθ is false under all conditions, hence impossible. 

The reasoning about the case in which A is itself neither certain nor impossible, is not obviously correct.  The inference appears to rely on an unstated modal principle, perhaps one as strong as the S5 principle, that statements asserting or denying certainty or possibility are certain if true.  With such an assumption added, the first horn of the dilemma is established.

Accordingly, MacColl’s contrary argument, that Aθθ is possible, is not needed if we can push back to a prior question:  

whether, or under what conditions, Aθ is certain if true. 

The most reasonable attitude to take would seem to be that there are many modes of modality, pertaining to different subject matters – in some cases S5 is the correct logic and in other cases not.

7.      APPENDIX. 

[1] Is Exclusion negation classical?

Suppose we assert that the apple is not red, while intending no definite contrast whatsoever.  One option may be to assert that nevertheless, all the ways the apple might or could be, ways that do not involve its being red, form a class.  Then, just as for choice negation it will follow that not being in any of those ways implies being red.  

This ostensibly simple view may have difficulties, with vagueness and the vagueness of vagueness, or with Russel-type paradoxes, or with more general questions about whether the class could or could not be a set.  

If we are uneasy with the idea of reifying ways things might or could be as a definite class, then we will certainly begin to doubt inference by Reductio ad Absurdum (as Intuitionists do), and almost certainly Contraposition and Double Negation as well, whenever the negation in play is exclusion negation.  

In a many-valued logic that defines the connectives in terms of a ‘many-truthvalue-table’, it is possible to have a negation that is not classical.  For example, if ¬1 = 0, ¬2 = 1, ¬0 = 1 then ¬¬2 ≠ 2.  We could reckon this as an exclusion negation (‘value other than the designated value’), though a simple case.  In a language with truth-value gaps, where conjunction and disjunction are typically not functional (not compositional), it may also be possible to have a non-functional negation.

It is perhaps a failing in formal semantics to take negation (in our language in use) for granted as understood and unequivocal.  

[2] Counterexample to Lewis 2.21:  (~q → ~p) → (p → q) in normal modal logic

In our preferred notation, and assuming the Duality □¬ = ¬◊, we can write 2.21 as

*. □{□(¬ ◊q ⊃ ¬ ◊p)  ⊃ □(p ⊃ q) }

Recall that in a normal modal logic possible world model M = <W, R>, the sentence □A is true at world w in W iff A is true in all worlds in R(w).  

I will sketch a model, describing only just enough to show that it provides a counterexample to *.

The worlds w1, w2, w3, w4 in W are related as follows:

  1. w2 is in R(w1)
  2. w3 and w4 are in R(w2)
  3. For any world w in W, if w is in R(w2) then R(w) = R(w2)
  4. p and ¬q are true in w3
  5. p and q are true in w4

Argument

  1. q is true in w4
  2. ◊q is true in all members of R(w2)                             
  3. (¬ ◊q ⊃ ¬ ◊p) is true in all members of R(w2)
  4. □(¬ ◊q ⊃ ¬ ◊p)  is true in w2
  5. (p & ¬q) is true in w3
  6. □(p ⊃ q) is false in w2                                   since w3 is in R(w2)
  7. □(¬ ◊q ⊃ ¬ ◊p)  ⊃ □(p ⊃ q) is false in w2,                by 4. and 6.
  8. □{□(¬ ◊q ⊃ ¬ ◊p)  ⊃ □(p ⊃ q) } is false in w1          since w2 is in R(w1)

Note that, for simplicity, I made clause c. stronger than it needs to be to justify line 2.  Apart from that I have left <W, R> with as little constraint as possible.

 

8.      REFERENCES 

Becker, Oskar (1930)  “Zur Logik der Modalitäten”.  Jahrbuch  für Philosophie und Phänomenologische ForschungXI: 497-548.

Gabbay, Dov M. and John Woods (2006)  Handbook of the History of Logic. Vol. 7: Logic and the Modalities in the Twentieth Century.  Amsterdam: Elsevier.

Lewis, Clarence I. and C. H. Langford (1932) Symbolic Logic. New York: The Century Company. 

Lewis, Clarence Irving (1920) “Strict implication – an emendation”. The Journal of Philosophy, Psychology, and Scientific Methods 17: 300-302. 

MacColl, Hugh  (1906) Symbolic Logic and ‘its Applications. London: Longmans, Green and Co.

MacColl, Hugh (1910) “Linguistic misunderstandings (I)”. Mind, n.s., 19: 186–199. 

Read, Stephen (1998) “Hugh MacColl and the algebra of strict implication”. Nordic Journal of Philosophical Logic 3: 59-84.

Wolenski, Jan (1998) “MacColl on Modalities”. Nordic Journal of Philosophical Logic 3:133-140.

[1] In a Boolean algebra it exists, is unique, and x ∧ x’ = 0, x v x’ = 1.  

Modal logic: generalizing on general frames

Bas van FraassenLeave a comment

Frames in the semantics of modal logic

In normal modal logic a frame is a couple <W, R>, with R a map of W into the powerset P(W) of W and  with the operator □ on P(W) defined by 

            □X = {w: R(w) ⊆ X}

In neighborhood semantics a frame is a couple <W, N>, with N a map of W into the powerset P(P(W)) of P(W), and with the operator □ on P(W) defined by 

            □X = {w: X is in N(w)}.

That is a generalization: in a normal modal logic frame we can define N(w) = {X: w is in □X}, which is of course the family of supersets of R(w).

A general frame is a triple <W, N, P>, where <W, N> is as above, P is a Boolean algebra of subsets of W (‘the propositions’), and the operator □ is defined as above but only on P, not on P(W).  (When the corresponding syntax is interpreted in a general frame, the semantic values assigned to sentences are all in P.)

That too is a generalization: When P = P(W) we have the special case of an ordinary neighborhood frame.

These three types of frames are clearly special instances of a more general type, which I will call the truly general frames:

A truly general frame is a triple <W, 𝜙, P> where 𝜙 is some mathematical entity or other, P is a Boolean algebra of subsets of W, and the operator □ is an monotone operator on P which is a function of W and 𝜙.

(I take the monotonicity of □ to be the most basic, and inalienable, characteristic of the subject of modal logic, however broadly construed.)  

This truly general type can be put to work: I will give a simple example of its use for showing the independence of certain basic principles of modal logic.

Preliminary: a little possible world story

In one kind of world all the inhabitants are enormously cheerful, elated, they think everything is just great.  I call these the Elated worlds.  In another kind of world the inhabitants are odious for their negativity and pessimism, they think everything sucks, nothing is great.  These are the Odious worlds.   To describe what is the case in these worlds we introduce sentential unary connective □, read as “It is considered great that”.  Note that for any sentence A, □A is true in all and only the Elated worlds.  So for instance □(A v ~A) is not true in all worlds.  But in other respects it’s all pretty normal.  For instance, □ is monotone: if A implies B then □A implies □B.

Representation of the example

For convenience I will represent these worlds by natural numbers, with even numbers representing the Elated worlds and odd numbers the Odious worlds.

Frame ARITH = <W, 𝜙, P> with W the set of natural numbers (starting with 1), 𝜙 its natural ordering, P just P(W), and the operator □ on P defined by □X = the set of even numbers that are members of X.

Before interpreting the modal logic syntax in ARITH let’s just note a few features of  this operator:

  • T1. □ is a monotone operator on P:  if X ⊆ Y then □X ⊆ □Y
  • T2. □X ⊆ X
  • T3. (□X ∩ □Y) = □(X ∩ Y)
  • T4. □X= □□X
  • T5. □⊥ = ⊥ 
  • T6. □W ≠ W

(The proofs are straightforward, but see Appendix for some details.)

Interpretation, logic

I take the modal sentential syntax to be familiar and will use ‘□’ for the modal connective, the symbols ‘&’ and ‘~’ for conjunction and negation,  ‘⊥’ for the falsum and ‘T’ for ‘~⊥’ (with the context preventing confusion).

A model is a frame together with an interpretation of this syntax in this frame, which is an assignment of propositions (subsets of W) to the sentences, by the recipe:

|A & B| = |A| ∩ |B|

|~A| = W minus |A|

|□A| = □|A|

|⊥| = Λ, the empty set

Validity in a model.  If M is a model, with frame <W, 𝜙, P> and interpretation | |, we write ‘╞M A’ for |A| = W, and ‘A1, A2, …╞M B’ for (|A1| ∩  |A2|  ∩ … )  ⊆ |B|.

Let us consider the following principles familiar in modal logic, dividing them into two groups (roughly following Chellas’ (1980) nomenclature).

Group One. 

RM.      If A├B then □A  ⊢ □B  (Monotonicity)

M.        □(A & B) ⊢  (□A & □B)

C.         (□A & □B)  ⊢   □(A & B)

K.         □(A ⊃ B) ⊢   (□A ⊃ □B) 

N◊.      ⊢ ~□ ⊥

D.         □A     ⊢   ~□~A

T.         □A     ⊢   A

S4.       □A   ⊢   □ □A

Group Two.

RN.     If ├A then  ⊢ □A  

N.        ⊢ □T

B.         A  ⊢  □ ~□~A

S5.       ~□~A    ⊢  □~□~A

 Satisfaction and Violation in a model

I will call any such principle satisfied in model M if replacing ‘⊢’ in the principle by ‘╞M’ yields a true statement about M, and violated in M if it is not satisfied in M.

Independence.

A principle Q of modal logic is independent of principles Q1, Q2, Q3, … if there is a model M with a truly general frame such that Q1, Q2, Q3, … are sound in M and Q is violated in M.

Theorem.  The modal logic principles in Group Two are independent of the principles in Group One.

Let M be a model with frame ARITH and interpretation | |.  The proof is that all principles in Group One are satisfied in M, and all the principles in Group Two are violated in M. 

The satisfaction of Group One follows in the main from facts T1. through T5. about ARITH.  The violation of N, which implies the violation of RN, is due to fact T6., that □W is the set of even numbers, while W is the set of all natural numbers.  B is similarly violated because |□~□~T| is some set of even numbers.  For the violation of S5 we have to look to a proposition other than W, e.g the set <4] = {1, 2, 3, 4}.  If |A| = <4] then |~□~A|  contains all the odd numbers (as well as 2 and 4), while  |□~□~A| ={2, 4}.  (For more details see Appendix.)

APPENDIX

Let E be the set of even numbers.  Then to prove T1. – T5., replace in each case ‘□’ by ‘E ∩’.  The crucial fact that □W¹ W is simply that E is a proper subset of W.  Note that if we look at ARITH as a augmented neighborhood frame, N(x) is not closed under supersets but under supersets within E, with E as fixed point, and that suffices to make □ monotone.

To prove the theorem, the remarks there suffice to show that the principles in Group Two are violated.  To spell out the argument for S5, I used the intuitive notation <n] for the initial segment {1, …, n} of W, and we can equally set [ n> for the final segment {n+1, …} of W.

Then ~□~<4] =    ~□[5> = ~{6, 8, …}  =  {1,2,3,4, 5, 7, 9, …}= the union of <4] with the odd numbers.  But  then □~□~<4] = {2, 4}, which includes no odd numbers.

That the principles in Group One are all satisfied in model M follows mainly from facts T1.-T5 about M.  For N◊, see from T5 that |~□ ⊥| = W.  For K, suppose that n is in |□(A ⊃ B)|.  Then n is even and belongs either to |~A| or to |B|.  If it belongs to |~A| then it is not in |A|, and hence not in |□A|.  Therefore it either does not belong to |□A| or belongs |□B|.

The curious roles atomic sentences can play (2)

Bas van FraassenLeave a comment

[A reflection on some papers by Hallden, Lemmon, Hiz, Makinson, and Segerberg, listed at the end.  Throughout I will use my own symbols for connectives, to keep the text uniform.]

Lemmon (1966) proved a theorem that I found quite startling at first sight, and I wondered what to make of it.  But then I found that Makinson (1973) used it, to prove an interesting result for modal logics – one that is related to the role of atomic sentences — and it really kindled my interest. 

It’s a story that spans several decades, and I will begin with Hallden.  But let me note beforehand that each of these authors had the same target, which they specified clearly though informally, namely the class of propositional modal logics.  

A class of logics.

Some logics, e.g. FDE, have a consequence relation but no theorems.  There are also logics that have the same theorems but different consequence relations.  So I’ll take a logic to be identified by a consequence relation or operator.  I’ll spell this out just for propositional logics.

Definition.  A syntax is sentential iff its non-logical vocabulary is a set of zero or more propositional constants and countably infinitely many propositional variables. 

The propositional constants and variables are the atomic sentences from which the complex sentences are built.

Definition. If S is a sentential syntax and SS its set of sentences then L is a logical consequence operator (or briefly, a logic) on S exactly if

  1. L is a closure operator on the subsets of SS
  2. L is invariant under substitution for propositional variables

That is, if X is a set of sentences and X = L(X), and P a propositional variable, and Y the result of substituting a specific sentence A for all occurrences of P in the sentences in X, then Y = L(Y).

So I make closure under the relevant rule of substitution part of the meaning of “logical consequence operator” or “logic”. [1]  

The set L(∧) is the set of theorems of L, or the set of L-theorems.  

Definition.  A logic L on a sentential syntax is classical iff that syntax has at least all the ‘truth-functional’ connectives (primitive or defined), and the set of theorems of L contains (in some form or other) all theorems of the classical propositional calculus, and for all sentences A, B, if A and (A ⊃ B) are in X then B is in L(X). (Compare with Lemmon’s formulation. [2])

For the last clause I will also use “ X is closed  under detachment”. I will here abbreviate “classical logic on a sentential syntax” to just “classical logic”, since we will look only at the sentential logic case.[3]   A modal logic, as defined by the authors I mentioned, is a classical logic on a syntax that contains a modal propositional operator.

Hallden 

When C. I. Lewis introduced his family of modal logics they were five, but only two of them, S4 and S5, seemed easy to interpret.  Sören_Halldén (1951) diagnosed the strangeness of S1,S2, and S3 as due to what we now call 

Hallden incompleteness.  A  logical system L is Hallden incomplete iff there are sentences A and B which share no propositional variables and are not theorems of L while their disjunction (A v B) is a theorem of L.

The incompleteness, Hallden suggests, is this: “for S1, S2, and S3 the class of true formulas cannot coincide with the class of theorems” (Hallden 1951: 127).  His reason is straightforward:  if the class of true formulas includes a disjunction then it also includes the disjuncts.

But this looks quite beside the point: a logic is not meant to capture all truths, but all logical truths.  Hallden is not attending to the difference between a logic and a theory.  

Definition.  If L is a classical logic on syntax S then a set of sentences of S is an L-theory iff X contains all L-theorems and is closed under detachment.

The rule of substitution does not enter into it: we cannot deduce q from atomic sentence p.  Unlike detachment, the rule of substitution is not a rule designed to preserve truth but to preserve validity.  The set of L-theorems is an L-theory, but unlike most L-theories it is closed under substitution.  

We can do better than Hallden, I think, with the reflection that if A and B have propositional variables, but have none in common, then they could be interpreted to be about just any two different things altogether, with no connection at all – so if they are not logical truths, how could their disjunction be?  If they are not logical truths then they could be false, and if there is no connection between them they could both be false.  We’ll see arguments like this below.

 It was soon shown, after Hallden’s paper, that our familiar normal modal logics T, B, S4, S5 are all Hallden complete.

Lemmon

What Lemmon (1966) proved was this:

A classical logic L is Hallden incomplete if and only if there are classical logics L1 and L2, distinct from each other and from L, such that L = L1 ∩ L2.

Attention to closure under substitution is important for this theorem.  For example, If L i s a classical logic, X is any L-theory, and P a propositional variable, then X may well be the intersection of two least L-theories that contain (X ∪ {P}) and (X ∪ ~P) respectively.  But the least logic L’ that contains the theorems of a logic L, and also P, has as theorems all sentences of the syntax – because of closure under substitution. And similarly for the one with ~P, if the logic is classical, due to double negation, so those two extensions of L are then identical.

In the Appendix I will sketch Lemmon’s proof.  But we can see from the definitions that if L is Halden-incomplete, with A v B the relevant disjunction, then we can take L1 and L2 to be the least logics containing L that have A, B respectively as theorems. 

The proof that in that case L1 and L2 are distinct from each other, as well as from L, is straightforward.  For suppose that B is a theorem also of L1 as well.  In that case there are certain substitution instances A1, …, Am of A, which are of course not in L, such that (A1 & …& Am) ⊃ B is a theorem of L.  But L also contains all of A1 v B, …, Am v B, since they are substitution instances of its theorem A v B.  Their conjunction is tautologically equivalent to (A1 & …& Am) vB.  By Modus Ponens and disjunction elimination, it follows that B is a theorem of L, contrary to supposition. 

Makinson and Segerberg

Hiz’s paper that I discussed in the previous post was called “A Warning …”.  

David Makinson also called his 1973 paper “A Warning …”.  Segerberg titled a section in his book “Makinson’s warning”.  I won’t say just now what the warning was, I’ll come to that later.  

Instead I’ll begin by present Makinson’s argument in a general form, somewhat generalized from his presentation, and only afterward turn to his specific conclusion.

Makinson defines the class of modal logics, his target, as follows. (I will use my terminology as set out at the beginning here.)  The sentential syntax S has as all ‘truthfunctional’ connectives (whether primitive or as defined, we will leave this open for now), as well as the unary connective □, and it has no propositional constants.  

Definition.  A modal logic is a classical logic on S.

So modal logics will differ by including some formulas in which □ occurs (axioms for specific modal logics like K or S5).  Any intersection of modal logics is a modal logic.  The smallest is L0, the intersection of all, and its theorems are all and only instances of classical tautologies. 

But here is a variant: we introduce the notion of a propositional constant to form a slightly different family of logics.  The sentential syntax S+ is exactly like S except that it has one propositional constant, q.  

Definition. A modal+ logic is a classical logic on S+.

The smallest modal+ logic on S+, let us say, is L1. Its theorems too are just the instances of classical tautologies. Propositional constants and propositional variables are both atomic sentences.  As a syntactic distinction it may look arbitrary, but the difference comes in the logic: the rule of substitution applies only to the propositional variables. 

Theorem. L1, the smallest modal+ logic is Hallden incomplete.

Relying on Lemmon’s theorem this follows from the proof that L1 is the intersection of two logics that are distinct from each other and from L1.

The first part is interesting but easy.  The proof is by display of an example.  Let La be the least modal logic that contains L1 and □~q, and let Lb be least modal logic that contains L1 and ~ □~q.  Obviously L1 is part of both La and Lb.  Also, since the added formulas are not classical tautologies, and are contraries, La and Lb are distinct from each other and from L1.

For the converse, suppose that A is a theorem of both La and Lb.  Note that there are no propositional variables in either □~q or ~ □~q.   Therefore, if formula A belong to both La and Lb then (□~q ⊃ A) and (~□~q ⊃ A) are theorems of L1. But then, A is a theorem of L1, by classical sentential logic.

Hence by Lemmon’s theorem,  this means that L1 is Hallden-incomplete.   And the point is very general, no axioms for □ were assumed.  The result is just due to the presence of a propositional constant.  Illustrative examples of an ‘offending’ disjunction in L1 are easy to find.  (□~q v ~ □~q) is a tautology, hence a theorem of L1, but its disjuncts are not.  For an example that has some propositional variables involved, let r and s be distinct propositional variables.  Then L1 has theorem

            (r ⊃ □~q) v (s ⊃ ~□~q)

for that too is a truth-functional tautology, but neither disjunct (which have propositional variables but share none) is a theorem of L1.

Makinson’s result about choice of primitive operators

The full title of Makinson’s paper is “A Warning about the Choice of Primitive Operators in Modal Logic”. Makinson’s logic L0 is like my L0 (the least modal logic on S) except that Makinson considers two specific options for syntax.  The first is that the primitive ‘truth-functional’ connectives are ⊃ and  ⊥ (the falsum) and the second option is that they are & and ~.  Then he proves that if we take the first option, then L0 is the intersection of two logics L and L’, distinct from each other and from L.  (And so, we may note, Hallden incomplete.)

His proof is the one of which I gave the general version above, except that “q” is replaced by “⊥”.  We can classify the falsum as a logical sign, a 0-adic operator, but syntactically it (also) plays the role of a sentence:  ~⊥ is a sentence,  ⊥&⊥ is a sentence, ⊥ is a sentence ….  The proof does not rely on any specific features of the falsum, but only on the fact that it plays the same role as any propositional constant.

On the second option L0 is not Hallden-incomplete (see Appendix for a sketch of his proof).  But the two options yield languages that are entirely inter-translatable.  As Segerberg (1982: 104) comments, the two options give us languages that “even  though [they] have the same ‘internal’ properties, they do not share all the ‘external’ ones”.  

Makinson recognizes that his result about the choice of primitives does not affect any of the more familiar modal logics.  In those, □~⊥ is a theorem.[4]  He took the result as being important for an insight into the structure of the lattice of modal logics. But as we also saw, his main argument generalizes to the presence of any propositional constant.  So it also gives an insight into the curious roles that atomic sentences can play.

APPENDIX.  Sketches of Lemmon’s and Makinson’s proofs

Outline of Lemmon’s proof that a classical logic L is Hallden incomplete if and only if there are classical logics L1 and L2, distinct from each other and from L, such that L = L1 ∩ L2.

Lemmon’s proof of the ‘only if’ part is straightforward, but made lengthy by the need to take the rule of substitution into account.  Suppose that L is Hallden incomplete.  Let A v B be an L-theorem, while A, B are not L-theorems and share no propositional variables.  Let L1 and L2 be the extensions of L made by adding A,  B respectively.  Clearly the L-theorems are all L1-theorems as well as L2-theorems. 

Suppose now that C is both an L1-theorem and an L2 theorem.  The proofs for C in L1 and in L2 must be from premises that are substitution instances A1, …, Am of A,  and substitution instances B1, …, Bn of B respectively. So the following are both L-theorems:

(A1 & …& Am) ⊃ C

(B1 & … & Bn) ⊃ C

therefore [(A1 & …& Am) v (B1 & … & Bn)] ⊃ C is an L-theorem.  But that is tautologically equivalent to [(A1 v  B1 ) & …& (Am v Bn)] ⊃ C.  Since the L-theorems include all substitution instances (Ai v  Bi) of L-theorem (A v B), it follows that C is an L-theorem.

The proof that if L is the intersection of two distinct logics L1 and L2 then it is Hallden incomplete is shorter but more interesting.  Select a theorem A of L1 that is not a theorem of L2, and a theorem B of L2 that is not a theorem of L1.  Clearly, neither is a theorem of L.  Since L1 is closed under substitution it will contain an ‘isomorphic’ substitution instance A’ of A formed by substituting propositional variables foreign to B, for the propositional variables in A.  Both L1 and L2 contain the disjunction (A’ v B).  Therefore so does their intersection L.

Outline of Makinson’s proof that on the second option, L0 is not Hallden-incomplete.

Suppose per absurdum that sentences A and B have no propositional variables in common, and that (A v B) is a theorem of L0, while A, B are not theorems.  So (A v B) is a classical tautology.  Let f assign truth-values 0, 1 to the atomic sentences in A such that f(A) = 0.  This is possible since A is not a tautology and does not contain the falsum or any propositional constant.  Similarly let g assign truthvalues to the atomic sentences in B such that g(B) = 0.   Since the domains of f and g do not overlap, we can combine them to yield a function h such that h(A) = h(B) =0.  Thus h(A v B) = 0 which contradicts the supposition that (A v B) is a tautology.

REFERENCES

Sören Halldén (1951) “On The Semantic Non-Completeness Of Certain Lewis Calculi”. The Journal Of Symbolic Logic 16: 127-129. 

E. J. Lemmon (1966) “A Note On Hallden-Incompleteness”. Notre Dame Journal Of Formal Logic VII 1966: 296-300

David Makinson (1973) “A Warning about the Choice of Primitive Operators in Modal Logic”. Journal of Philosophical Logic 2: 193- 196.

Notes

[1] I do not mean that it is a substantive constraint.  Rather, we classify logics by what is substitutable.  A propositonal logic is one for which the class of substitutables is a set of sentences, a predicate logic is one where the substitutables are or include a set of primitive predicates.  If a closure operator on a syntax has no substitutables at all, however, I do not think it can count as a logic, whatever else it may be.

[2] Compare Lemmon (1966: 300) “Throughout this paper, a logical system is understood to be a propositional logic whose class of theorems is closed with respect to substitution as well as detachment, and which contains (in some form or other) the classical propositional calculus.”

[3] Since I refer to Segerberg below, I should note that this is not the same as his definition of “classical logic”, though it is not far.

[4] Makinson makes the stronger point that choice of primitive truth-functional operators will not make a difference in any congruential  modal logic. 

The curious roles atomic sentences can play (1)

Bas van FraassenLeave a comment

[A reflection on papers by Hiz and Thomason, listed at the end.  Throughout I will use my own symbols for connectives, to keep the text uniform.]

Atomic sentences, we say, are not a special species.  They could be anything; they are just the ones we leave unanalyzed.  What we study is the structures built from them, such as truth-fuctional compounds.

But that innocuous looking “They could be anything” opens up some leeway.  It allows that the atomic sentences could have values or express propositions that the complex sentences cannot.  I will discuss two examples of how this leeway can be exploited for proofs of incompleteness.

The story I want to tell starts with a small error by Paul Halmos in 1956.

Halmos and Hiz

 In his 1956 paper Paul Halmos wanted to display the classical propositional calculus with just & and ~ as primitive connectives.  (Looks familiar, what could be the problem?)  As guide he took the presentation in Hilbert and Ackermann, with v and ~ as primitives. For brevity and ease of reading they had introduced “x ⊃ y” as abbreviation for “~x v y”.

  1. (x v x) ⊃ x
  2. x ⊃ (x v y)
  3. (x v y) ⊃ (y v x)
  4. (x v y) ⊃ (z v x . ⊃ . z v y )

Knowing how truth functions work, Halmos (1956: 368) treated “x v y”  as abbreviation of “~(~x & ~y)” and “x ⊃ y” as abbreviation of “~(x & ~y), to read Hilbert and Ackermann’s axioms. That means that his formulation, with ~ and & primitive, was this:

  1. ~[~(~x & ~y) & ~x]
  2. ~[x & ~~(~x & ~y)]
  3. ~[~(~x & ~y) & ~~(~y & ~x)]
  4. ~[~(~x & ~y) & ~[~[~(~z & ~x) & ~~(~z & ~y)]]]

But, unlike what it translates (Hilbert and Ackermann’s), this set  of axioms is not complete!

Henryk Hiz (1958) showed why not.  (He mentioned that Halmos had raised the possibility himself in a conversation, and Rosser had done so as well, in a letter to Halmos.)

Let’s look for a difference in the roles of atomic sentences and of complex sentences in Halmos’ axiom set.  What springs to the eye in Axiom b. is that there is an occurence of x that is preceded by ~, and one that is not so preceded but ‘stands by itself’.  So we can make trouble by allowing an atomic sentence x to take values that a negated sentence ~x cannot have.  

That is what Hiz does, with this three-valued truth-table where an atomic sentence x could have value 1, 2, or 3, but ~x can only have values 1 or 3. 

(He writes A and N for my  & and ~.) 

So if x has value 2 then ~(~x & x) has value ~ (~2 & 2) = ~(1 & 2) = ~1 = 3, which is not designated.  So there is a classical tautology, the traditional Non-Contradiction Principle, that does not receive a designated value.  

In this three-valued logic neither conjunction nor negation behaves classically, but all of Halmos’ axioms have the designated value 1.  So his formulation of classical sentential logic is sound but not complete.

Thomason

Thomason’s (2018) argument and technique, which I discussed in a previous post, were very close to Hiz’, but applied to modal logic.

In modal logic the basic K axiom can be formulated in at least these three ways:

  1. □(x ⊃ y) ⊃ (□x ⊃ □y)
  2. ◊(x v y) ≡  (◊x v ◊y)
  3. ~◊~(x ⊃ y) ⊃ (~◊~x ⊃ ~◊~y)

The third is a translation of the first with “□” translated as “~◊~”.  In the previous post (“Is Possiblity-Necessity Duality Just a Definition”, 07/17/2025) I explained Thomason’s model in which that third formulation of K is satisfied, but the Duality principle is shown to be independent.  Here I will show that satisfaction of Axiom (iii) is compatible with a violation of Axiom (ii). 

Thomason presented a model with 8 values for the propositions.  I’ll use here the smaller 5-valued model which I described in the post. My presentation here, in a slightly adapted form, is sufficient for our purpose.  

This structure (matrix)is made up of the familiar 2-atom Boolean lattice B = {T, 1, ~1, ⊥} with the addition of an ‘alien’ element k.  The meet and join on B are operators ∧ and  +. The operator ~ is the usual complement on on B.  The only designated element is T.

To extend the operators to the alient element, we set ~k = ~1.  So x can take any of the five values but ~x can only have a value in B.

What about the joins and meets of elements when one of them is alien?  They are all in B too, with these definitions:

Define.  x* = ~~x, called the Twin of x.  (Clearly x = x* except that k* = 1.) 

Define.  For any elements x and y:   x & y = x* ∧ y*, and x v y = x* + y*.

Finally the possibity operator is defined by: ◊x = T iff x = 1 or T;  ◊x =  ⊥ otherwise.  

Instances of Axiom (iii.) always get the desigated value (by inspection; note that every non-modal sentential part starts with ~). 

But in Axiom (ii) we see the leeway, due to the fact that x can be any element.  The negation, join, or meet of anything with anything can only take values in B.  So Axiom (ii) does not always get a designated value, for if we set x = y = k, we get the result:

◊(k v k) = ◊(k* + k*) = ◊1 = T

(◊k v ◊k) =  ⊥* +  ⊥* =  ⊥

In Thomason’s article this technique is used to show that with formulation (iii) of K, the duality ¬◊¬x = □x is independent, and needs to be added as an axiom rather than a definition.  

Axiom (ii.), with the attendant rules changed mutatis mutandis, and the Duality introduced as a definition, is a complete formulation of system K (cf. Chellas 1980: 117, 122).  A formulation that has Axiom(iii) instead of Axiom (ii) is not.  

Hiz’ warning was well taken.

References

Chellas, Brian F. (1980) Modal Logic: An Introduction. Cambridge.

Hiz, Henryk  (1958) “A Warning about Translating Axioms”. Am. Math. Monthly 65: 613-614.

Thomason, Richmond H. (2018) “Independence of the Dual Axiom in Modal K with Primitive  ◊”.  Notre Dame Journal of Formal Logic 59: 381-385.

Is Possibility-Necessity Duality Just a Definition?

Bas van FraassenLeave a comment

[A reflection on Richmond Thomason’s “Independence of the Dual Axiom in Modal K with Primitive ◊”]

Within modal logic we customarily take necessary to be equivalent to not possibly not.  Thomason shows that the answer to my title question is NO: if we formulate the logic with ◊ as primitive, we need to add that equivalence as an axiom.  There is an interpretation of K in which the duality fails.  The interpretation, he says, is exotic ….  It is, but also startling and provocative.  

I’ll explain his model and reasoning, and then explore his method with a smaller model (which gives a weaker result).  His method: construction of a small language that is classical (truth-functional connectives) and hyper-intensional.

In Thomason’s paper the family of propositions is represented by the union B ∪ B’ of two Boolean algebras with two atoms each: 

The partial order within this union is just within each of the parts: if x and y belong to B and B’ they are not ordered relative to each other, they have no meet or join.  Think of this as a matrix, with only V and V’ designated values (‘true’).

There is a sort of complement operator, which I will symbolize as ¬, that is ordinary in B but takes elements in B’ to B.  

As a result, of course, ¬¬ x is always in B, and is called Twin(x).  Specifically, ¬1 = 2,  ¬2 = 1.  But  ¬ 2’ = 1 as well, so Twin(2’) = ¬ ¬ 2’ = 2.  Similarly, ¬1’ = 2, so Twin(1’) = 1.

Then there is sort of conditional operator (x → y) = (¬Twin(x) v Twin(y)); its values are always in B.  Thus when sentences are given these propositions as their semantic values, and “not” and “if then” are assigned ¬ and →, classical propositional logic is sound.

Clearly ¬ is not an involution on B ∪ B’, but like in Intuitionistic logic, doubly complimented propositions act classically.  

So, as far as that is concerned, the strange algebraic structure of the family of propositions is hidden from sight.  But that strangeness can be utilized in the interpretation of ◊.

That interpretation is simple:  each of B and B’ is divided into ‘possible’ and ‘impossible’ regions: the ‘possible’ propositions are those inside the dotted ellipses.

The possibility operator, too, when applied to an element of B’, shifts attention to B:

◊1 = V, ◊V = V, but if x is in B’, we still refer to V in B:  ◊2’ = V, ◊V’ = V.  In all other cases ◊x=  ∧.   Notice that for all x, ◊x is in B, so this addition cannot affect the soundness of classical sentential logic.

With this interpretation we can verify the K axiom formulated with ◊ as primitive:

¬  ◊¬ (x →  y) → [¬◊¬x → ¬◊¬y]

To check that no assignment of values to x, y yields a counterexample is straightforward.

What has happened to duality?  If we define □ x as ~◊~x, what is the status of 

            Duality. ◊x → ~□~x,  and ~□~x   → ◊x ?

The first part is the same as ◊x  → ~~◊~~x, which is the same as ◊x → ◊~~x.  If x = 2’ then this is (◊2’ → ◊~~2’), which is (V → 2) = 2, hence not true.

The second part is similarly seen not to be true, using 1’ rather than 2’.

Adding Duality as an axiom will eliminate the ‘exotic’ interpretation.

PART TWO.

Thomason’s method has a general form: 

choose a structure and interpretation in such a way that all the semantic values of complex sentences belong to a Boolean algebra, and use extra structure in the interpretation of non-Boolean operators.  

That makes it possible to construct non-standard interpretations of even normal modal logics.

I thought I’d try my hand it with a small familiar lattice that has a Boolean sublattice.  As it turns out (not surprisingly) it (only) gets half of Thomason’s result.

This is N5, the smallest non-modular (hence non-distributive) lattice, the ‘pentagon lattice’.  Let us define operations on it in the way Thomason did:

a sort of complement:  ┐1 = ⎯ 1, ┐ ⎯ 1 = 1, ┐k = ⎯ 1, ┐T = ⊥,   ┐⊥ = T.

We define the Twin x* of x to be ┐┐x.  Note that k* = 1.

N5 has a Boolean sublattice B = {T, 1, ⎯ 1, ⊥} = {x*: x in N5}

 a sort of conditional:   (x  → y) = (┐x* v y*)

Only T is designated (‘true’). Interpretation of the syntax: as above; once again all semantic values of complex sentences are located in the Boolean sublattice, so classical sentential logic theorems are all true.  

a sort of possibility operator: ◊x = T iff x = 1 or T;  ◊x = ⊥ otherwise.

Verification of the K axiom

            ¬ ◊¬ (x → y) → [¬ ◊¬x → ¬◊¬y]

Note:

¬◊¬T = T,                               ¬◊¬1 = T

¬ ◊¬k = ¬◊(⎯  1) =  T              ¬◊¬(⎯ 1) = ¬◊1 = ⊥

¬◊¬ ⊥ = ⊥

For the consequent  of the K axiom to be ⊥ means that [◊¬x v ¬◊¬y] =  ⊥, so:

 x is k or T or 1, and y is (⎯1) or ⊥

 In these cases the antecedent is ¬◊¬ followed by:

(k  → ⎯ 1) =  (¬k*  v ⎯ 1) =  ⎯ 1

(k  → ⊥) =    (¬k*  v ⊥) = ⎯ 1

(T→ ⎯ 1) =    ⎯ 1       

(T  →  ⊥ ) =      ⊥

(1 → ⎯ 1) =    ⎯ 1        

(1  →  ⊥ ) =    ⎯ 1

and the result of prefixing ¬◊¬ is in each case  ⊥.  So any attempt at a counterexample fails.

Now for the duality axiom:

Duality. ◊x → ¬¬□~x,      and ¬□¬x   → ◊x 

The second part is the same as  ¬¬◊¬¬x→ ◊x, which is the same as ◊¬¬x → ◊x.  But  (◊¬¬k → ◊k) = (◊1 →◊k) = (T  →  ⊥) = ⊥.

However, the converse holds, so only half of Duality is refuted.

PART THREE.  How can we generalize this method?

Note that in the above, for all x, ¬x = ¬¬¬x = ¬Twin(x).  So the mapping of B’ into B does not need to be defined in terms of ¬.

So we can simply say: we have a map Twin, and we define ¬ and  → to be as usual on B, and for x, y in B’ we define   (x → y) = (Twin(x) → Twin(y)), and define ¬x = ¬Twin(x).  

For x in B, set Twin(x) = x to make it a map of the entire structure into itself.

So that is one map, then choose another map of the structure into itself, call it α , whose values are all in B.  (That is necessary to make sure that classical propositional theorems remains valid.) Any other properties you like.  

Now you have a model of a classical sentential calculus extended with addition of a single unitary propositional operator, which will satisfy any axioms of your desire.  

For example, thinking about the K□ axiom for α, you could specify that if x  ≤ y then Twin(x) ≤  Twin(y).    But you could do the opposite, so that if p implied q then αq would imply αp, acting like negation (but perhaps not just like negation).  Or you could want α to be read “It is so in the story that …” and the story could be by Graham Priest.

Remark: hyper-intentionality

It is remarkable that by such simple means Thomason created a language that is at once classical and hyperintensional:  

Hyper-intensionality. For all x in B and in B’, x → ¬ ¬x and ¬¬x  → x.  But it is not the case that ◊x  → ◊¬ ¬x.  For example, ◊2’ = V but ◊¬ ¬2’ = ◊2 =  ⊥.  

Note that if x is in B then so is ¬ ¬x.  For how Thomason interprets the language, we can add that if A is any complex sentence then ◊A will imply ◊¬ ¬A. Only by using an atomic sentence (with value in B’) there is a counterexample to Duality.

In the case of axiom ¬ ◊¬ (A → B) → [¬◊¬A → ¬◊¬B], the  ◊ operator is applied only to sentences that begin with ¬, hence are complex.  So no such way of providing counter-examples applies there.

The created language, at once classical and hyper-intensional, is intriguingly unusual! 

REFERENCE

Thomason, Richmond (2018) “Independence of the Dual Axiom in Modal K with Primitive  ◊”.  Notre Dame Journal of Formal Logic 59: 381-385.

Logic of belief, omega-inconsistency

Bas van FraassenLeave a comment

In the past I have mainly thought of the logic of belief (if not connected with probability) as one of the family of normal modal logics.  Now I realize that there is a problem which that cannot accommodate, while it seems that neighborhood semantics can.

Think of the agent who believes, for each natural number n, that there are at least n stars,  but also believes that the number of stars is finite.  Such examples take the simple form:  something is F, 1 is not F, 2 is not F, ….  

We get a geometric example with intervals: I dropped a point-particle on the interval [0,1] on the real line.  My first belief is that it fell in the half-open interval [1/2,1).  My other relevant beliefs are that it fell in each of the intervals (1/2, 1], (1/4, 1], …, (1/2^n,1]….  My first belief has a non-empty intersection with each of the other beliefs.  But the intersection of those other beliefs is [1], which is excluded by my first belief.

From any finite subset of such a family of beliefs it is not possible to deduce a contradiction but the family as a whole is not satisfiable.  Goedel called this omega-inconsistency.

These examples are, to be reader friendly, generated by simple recipes, and hence amenable to an argument by mathematical induction, leading to a straight contradiction.  There are examples not of that sort, I just can’t write them down.  In any case, the agent may not have mastered mathematical induction.

The Problem.  In the normal modal logic approach, the agent in world w believes that A if and only if A is true in all the worlds w’ which bear a certain relation R to w.  If propositions are sets of worlds, and [A] is the proposition that A expresses, with B the ‘the agent believes that’ connective, this amounts to: 

BA = {w’: wRw’} ⊆ [A].

But in the case of the omega-inconsistent believer {w’: wRw’} would then have to be part of every proposition in his set of beliefs.  And there is no world in which all of those are true.  Thus, that case, {w’: wRw’}is empty.  But that is no different from a believer who believes that A & ~A.

So there is, in normal modal semantics, no way to distinguish the omega-inconsistent believer from the believer who believes a simple self-contradiction.

The Solution.  Here I will rely on my previous post, about logic of belief and neighborhood semantics.

Given simply that world w has neighborhood N(w) and p is believed in w iff p is a member of w, that distinction between ‘ordinary’ and omega-inconsistency can be respected.  For N(w) is a filter on the algebra of propositions, merely closed under finite intersections and superset formation. 

So suppose the agent in w believes p = (something is F), q(1) = (1 is not F), q(2) = (2 is not F), ….  and those propositions generate filter N(w).  In that case ~p is not in N(w), so ~B~p is true in w.  At the same time, there is no world in which all of N(w) is true, so the agent’s beliefs, taken altogether, imply all propositions, including B~p.

This is an adequate representation of omega-inconsistent belief, with the empty set not in N(w).  That shows that condition

            (cd)  Λ is not in N(w)

must not be read as ‘N(w) is consistent’ but only as ‘Each finite subset of N(w) is consistent’.

The Upshot

What this means is that you can be entirely wrong about what the world is like, with ideas that are not realistic under any possible conditions, and still live a useful, productive, and happy life.  And your family and friends might never find out.