Tag: relevance logic

What Could Be the Most Basic Logic?

Bas van Fraassen1 Comment

It was only in the 19th century that alternatives to Euclidean geometry appeared.  What was to be respected as the most basic geometry for the physical sciences: Euclidean, non-Euclidean with constant curvature, projective?  Frege, Poincare, Russell, and Whitehead were, to various degrees, on the conservative side on this question.>[1]  

In the 20th, alternatives to classical logic appeared, even as it was being created in its present form.  First Intuitionistic logic, then quantum logic, and then relevant and paraconsistent logics, each with a special claim be more basic, more general in its applicability, than classical logic.

Conservative voices were certainly heard.  John Burgess told his seminars “Heretics in logic should be hissed away!”.  David Lewis described relevant and paraconsistent logic as logic for equivocators.  The other side was not quiet.  Just as Hans Reichenbach gave a story of coherent experience in a non-Euclidean space, so Graham Priest wrote a story of characters remaining seemingly coherent throughout a self-contradictory experience.

Unlike in the case of Euclidean geometry, the alternatives offered for propositional logic have all been weaker than classical logic.  So how weak can we go?  What is weaker, but still sufficiently strong, to qualify as “the” logic, logic simpliciter? 

I am very attracted to the idea that a certain subclassical logic (FDE) has a better claim than classical logic to be “the” logic, the most basic logic.  It is well studied, and would be quite easy to teach as a first logic class. Beall (2018) provides relevant arguments here – the arguments are substantial, and deserve discussion.  But I propose to reflect on what the question involves, how it is to be understood, from my own point of view, to say why I find FDE attractive, and what open questions I still have.

1.      A case for FDE

The question what is the most basic logic sounds factual, but I cannot see how it could be.  However, a normative claim of the form

Logic L is the weakest logic to be respected in the formulation of empirical or abstract theories

seems to make good sense.  We had the historical precedent of Hilary Putnam’s claiming this for quantum logic.  I will come back to that claim below, but I see good reasons to say that FDE is a much better candidate.

2.      Starting a case for FDE

FDE has no theorems.  FDE is just the FDE consequence relation, the relation originally called tautological entailment, and FDE recognizes no tautologies.  Let us call a logic truly simple if it has no theorems.

To be clear: I take L to be a logic only if it is a closure operator on the set of sentences of a particular syntax.  The members of L(X) are the consequences of X in L, or the L-consequences of X; they are also called the sentences that X entails in L.  A sentence A is a theorem  of L iff A is a member of L(X) for all X.  The reason why FDE has no theorems is that it meets the variable-sharing requirement: that is to say, B is an L-consequence of A only there is an atomic sentence that is a component of both B and A.

So the initial case for FDE can be this: it is truly simple, as it must be, because

logic does not bring us truths, it is the neutral arbiter for reasoning and argumentation, and supplies no answers of its own. 

To assess this case we need a clear notion of what counts as a logic (beyond its being a closure operator), and what counts as supplying answers.  If I answered someone’s question with “Maybe so and maybe not”, she might well say that I have not told her anything.  But is that literally true?  A. N. Prior once made a little joke, “What’s all the fuss about Excluded Middle?  Either it is true or it is not!”.  We would have laughed less if there had been no Intuitionistic logic.

3.      Allowance for pluralism

My colleague Mark Johnston like to say that the big lesson of 20th century philosophy was that nothing reduces to anything else.  In philosophy of science pluralism, the denial that for every scientific theory there is a reduction to physics, has been having a good deal of play.

As I mentioned, FDE’s notable feature is the variable-sharing condition for entailment.  If A and B have no atomic sentences in common, then A does not entail B in FDE.  So to formulate two theories that are logically entirely independent, choose two disjoint subsets of the atomic sentences of the language.  Within FDE, theories which are formulated in the resulting disjoint sublanguages will lack any connection whatsoever.    

4.      Could FDE be a little too weak?

The most conservative extension, it seems to me, would be to add the falsum, ⊥.  It’s a common impression that adding this as a logical sign, with the stipulation that all sentences are consequences of ⊥, is cost-less.  

But if we added it to FDE semantics with the stipulation that ⊥ is false and never true, on all interpretations, then we get a tautology after all: ~⊥.  The corresponding logic, call it FDE+, then has ~ ⊥ as a theorem.   So FDE+ is not truly simple, it fails the above criterion for being “the” logic.  Despite that common impression, it is stronger than FDE, although the addition looks at once minimal and important.  Is FDE missing out on too much?

How should we think of FDE+?  

Option one is to say that ⊥, a propositional constant, is a substantive statement, that adding it is like adding “Snow is white”, so its addition is simply the creation of a theory of FDE.

Option two is to say that FDE+ is a mixed logic, not a pure logic.  The criterion I would propose for this option is this:

A logic L defined on a syntax X is pure if and only if every syntactic category except that of the syncategoremata (the logical and punctuation signs) is subject to the rule of substitution.

So for example, in FDE the only relevant category is the sentences, and if any premises X entails A, in FDE, then any systematic substitution of sentences for atomic sentences in X entails the corresponding substitution in A.  

But in FDE+ substitution for atomic sentence ⊥ does not preserve entailment in general.  Hence FDE is a pure logic, and FDE+ is not.

The two options are not exclusive.  By the usual definition, a theory of logic L is a set of sentences closed under entailment in L.  So the set of theorems of FDE+ is a theory of FDE.  However, it is a theory of a very special sort, not like the sort of theory that takes the third atomic sentence (which happens to be “Snow is white”) as its axiom.  

Open question: how could we spell out this difference between these two sorts of theories?  

5.      Might FDE be too strong?

FDE is weak compared to classical logic, but not very weak.  What about challenges to FDE as too strong?  

It seems to me that any response to such a challenge would have be to argue that a notion of consequence weaker than FDE would be at best a closure operator of logical interest.  But the distinction cannot be empty or a matter of fiat.

Distributivity

The first challenge to classical logic that is also a challenge to FDE came from Birkhoff and von Neumann, and was to distributivity.  They introduced quantum logic, and at one point Hilary Putnam championed that as candidate for “the” logic.  Putnam’s arguments did not fare well.[2]  

But there are simpler examples that mimic quantum logic in the relevant respect.

Logic of approximate value-attributions  

Let the propositions (which sentences can take as semantic content) be the couples [m, E], with E  an interval of real numbers – to be read as “the quantity in question (m) has a value in E”.

The empty set 𝜙 is counted as an interval.  The operations on these propositions are defined:

[m, E]  ∧ [m, F] = [m, E ∩ F]

[m, E]  v [m, F]  =  [m, E Θ F], 

where E Θ F the least interval that contains E ∪ F

Then if E, F, G are the disjoint intervals  (0.3, 0.7), [0, 0.3], and [0.7, 1],  

[m, E]  ∧ ([m, F] v [m, G]) = [m, E] ∧ ([ m, [0,1]]  = [m, E]

([m, E]  ∧ ([m, F]) v ([m, E]  ∧ ([m, G]) = [m, 𝜙]

which violates distributivity.

This looks like a good challenge to distributivity if the little language I described is a good part of our natural language, and if it can be said to have a logic of its own.

The open question:  

if we can isolate any identifiable fragment of natural language  and show that taken in and by itself, it has a logical structure that violates a certain principle, must “the” logic, the basic logic, then lack that principle?

Closure and conflict

We get a different, more radical, challenge from deontic logic.  In certain deontic logics there is allowance for conflicting obligations.  Suppose an agent is obliged to do X and also obliged to refrain from doing X, for reasons that cannot be reconciled.  By what logical principles do these obligations imply further obligations?  At first blush, if doing X requires doing something else, then he is obliged to do that as well, and similarly for what ~X requires.  But he cannot be obliged to both do and refrain from doing X: ought implies can.

Accordingly, Ali Farjami introduced the Up operator.  It is defined parasitic on classical logic: a set X is closed under Up exactly if X contains the classical logical consequences of each of its members.  For such an agent, caught up in moral conflict, the set of obligations he has is Up-closed, but not classical-logic closed.

If we took Up to be a logic, then it would be a logic in which premises A, B do not entail (A & B). Thus FDE has a principle which is violated in this context.

To head off this challenge one reposte might be that in deontic logic this sort of logical closure applies within the scope of a prefix.  The analogy to draw on may be with prefixes like “In Greek mythology …”, “In Heinlein’s All You Zombies …”.  

Another reposte can be that FDE offers its own response to the person in irresolvable moral conflict.  He could accept that the set of statements A such that he is obliged to see to it that A, is an FDE theory, not a classical theory.  Then he could say: “I am obliged to see to it that A, and also that ~A, and also that (A & ~A).  But that does not mean that anything goes, I have landed in a moral conflict, but not in a moral black hole.”

Deontic logic and motivation from ethical dilemmas only provide the origin for the challenge, and may be disputed.  Those aside, we still have a challenge to meet.

We have here another departure from both classical logic and FDE in and identifiable fragment of natural language.  So we have to consider the challenge abstractly as well.  And it can be applied directly to FDE.

Up is a closure operator on sets of sentences, just as is any logic.  Indeed, if C is any closure operator on sets of sentences then the operator

Cu:   Cu(X) = ∪{C({A}): A in X}

is also a closure operator thereon.  (See Appendix.)

So we can also ask about FDEu.  Is it a better candidate to be “the” logic?  

FDEu is weaker than FDE, and it is both pure and truly simple.  But it sounds outrageous, that logic should lack the rule of conjunction introduction!

6.      Coda

We could give up and just say: for any language game that could be played there is a logic – that is all.

But a normative claim of form

Logic L is the weakest logic to be respected in the formulation of empirical or abstract theories

refers to things of real life importance.  We are not talking about just any language game.  

Last open question:  if we focus on the general concept of empirical and abstract theories, can we find constraints on how strong that weakest logic has to be?

FDE is both pure and truly simple. Among the well-worked out, well studied, and widely applicable logics that we already have, it is the only one that is both pure and truly simple.  That is the best case I can make for it so far.

7.      APPENDIX

An operator C on a set X is a closure operator iff it maps subsets of X to subsets of X such that:

  1. X ⊆ C(X)
  2. CC(X) = C(X)
  3. If X ⊆ Y then C(X) ⊆ C(Y)

Definition.  Cu(X) = ∪{C({A}): A in X}.  

Proof that Cu is a closure operator:

  •  X ⊆ Cu(X).  For if A is in X, then A is in C({A}), hence in Cu(X).
  •  CuCu (X) = Cu(X).  Right to left follows from the preceding.  Suppose A is in CuCu (X).  Then there is a member B of Cu(X) such that A is in C({B}), and a member  E of X such that B is in C({E}). Therefore A is in CC({E}).  But CC({E}) = C({E}), so A is in  Cu(X).  
  • If X ⊆ Y then Cu(X) ⊆ Cu(Y).  For suppose X ⊆ Y. Then {C({A}): A in X} ⊆ {C({A}): A in Y}, so Cu(X) ⊆  Cu(Y).

8.      REFERENCES

Beall, Jc. (2018) “The Simple Argument for Subclassical Logic”. Philosophical Issues.

Cook, Roy T.  (2018) “Logic, Counterexamples, and Translation”.  Pp. 17- 43 in Geoffrey Hellman and Roy T. Cook (Eds.) (2018) Hilary Putnam on Logic and Mathematics.  Springer.

Hellman, Geoffrey (1980). “Quantum logic and meaning”. Proceedings of the Philosophy of Science Association 2: 493–511.

Putnam, Hilary (1968) “Is Logic Empirical” Pp. 216-241 in Cohen, R. and Wartofsky, M. (Eds.). (1968). Boston studies in the philosophy of science (Vol. 5). Dordrecht.   Reprinted as “The logic of quantum mechanics”. Pp. 174–197 in Putnam, H. (1975). Mathematics, matter, and method: Philosophical papers (Vol. I). Cambridge.

Russell, Bertrand (1897) An Essay on the Foundations of Geometry. Cambridge.

NOTES

[1] For example, Russell concluded that the choice between Euclidean and non-Euclidean geometries is empirical, but spaces that lack constant curvature “we found logically unsound and impossible to know, and therefore to be condemned a priori (Russell 1897: 118).

[2] See Hellman (1980) and Cook (2018) especially for critical examination of Putnam’s argument.

Boolean Aspects of De Morgan Lattices

Bas van FraassenLeave a comment
  1. Trivial answers                       1
  2. Important answer                    2
  3. Example of a non-trivial Boolean center                    2
  4. Generalization of this answer             2
  5. Non-trivial Boolean families              3
  6. Analysis, and generalization              3
  7. Non-minimal augmentation of Boolean lattices         5
  8. Discussion : what about logic ?                      6

Appendix and Bibliographical Note               7

The question re classical vis-a-vis subclassical logic

After the initial astonishment that self-contradictions need not be logical black holes, there is a big question:  how can classical reasoning find a place in a subclassical logic, such as the minimal subclassical logic FDE?

Classical propositional logic is, in  a fairly straightforward sense, the theory of Boolean algebras.  In the same sense we can say that the logic of tautological entailment, aka FDE, is the theory of De Morgan algebras.  

In previous posts I have also explored the use of De Morgan algebras for truthmakers of imperatives and for the logic of intension and comprehension.  So FDE’s algebraic counterpart has some application beyond FDE. 

How, and to what extent, can the sub-classical logic FDE accommodate classical logic, or classical theories, as a special case?  A corresponding question for algebraic logic is how, or to what extent, Boolean algebras are to be found inside De Morgan algebras.  

Terminology. Unless otherwise indicated I will restrict the discussion to bounded De Morgan algebras, that is, ones with top (T) and bottom (⊥), these are distinct elements and ¬T =  ⊥.  If L is a De Morgan lattice, an element e of L is normal iff e ≠¬e, and L is normal iff all its elements are normal. Both sorts of algebras are examples of distributive lattices.  From here on I will use “lattice” rather than “algebra”.

1 Trivial answers

There are some simple, trivial answers first of all, and then two answers that look more important.

First, a Boolean lattice is a De Morgan lattice in which, for each element e, (e v ¬e ) = T (the top), or equivalently, (e  ∧¬e) = ⊥ (the bottom).

Secondly, in a De Morgan lattice, the set {T, ⊥} is a Boolean lattice.  

Thirdly, if L is De Morgan lattice and its element e is normal, then the quadruple {(e v ¬ e), e, ¬e, (e  ∧ ¬e)} is a Boolean sub lattice of L.

2 Important answer

More important is this:  If L is a De Morgan lattice then B(L) = {x in L: (x v ¬ x) = T} is closed under  ∧, v, and ¬ and is therefore a sub-lattice of L.  It is a Boolean lattice: the Boolean Center of L.

3 Example of non-trivial Boolean center

Mighty Mo:

Figure 1 The eight-element De Morgan lattice Mo

The Boolean Center B(Mo) = {+3, +0, -0, -3}.

4 Generalization of this answer

My aim here is to display Boolean lattices that ‘live’ inside De Morgan lattices. My general term for them will be Boolean families. They will not all be of the type, and I hope that their variety will itself offer us some insight.

The fact that a De Morgan lattice has a Boolean center can be generalized: 

 Suppose element e is such that (e v ¬e) is normal, and define B(e) = {x in L: (x v ¬ x) = (e v ¬e)}.  Then (see Appendix for proof) B(e) is a Boolean family, with top = (e v ¬e) and bottom = (e  ∧ ¬e).

5    Non-trivial Boolean families

The big question:  are there examples of non-trivial Boolean families distinct from the Boolean center?

We can construct some examples by adding ‘alien’ points to a Boolean lattice. For example this, which I will just call L1.

Figure 2  L1, augmented B3

This lattice L1 is made up from the three-atom Boolean lattice B3 by adding an extra top and bottom.  This sort of addition to a lattice I will call augmentation, and I will call L1 augmented B3.  For the involution we keep the Boolean complement in B3, and extend this operation by adding that T = ¬ ⊥ , and ⊥ = ¬T.  

L1 is distributive, hence a De Morgan lattice (proof in Appendix).  The clue to the proof is that for all elements e of L1, T  ∧ e = e and T v e = T.

The Boolean center B(L1) = {T, ⊥} is trivial, and the sublattice B3 is a non-trivial Boolean family.

6     Analysis of this example, and generalization

In the above reasoning nothing hinged on the character of B3, taken as example.  Augmenting any Boolean lattice B in this way will result in a De Morgan lattice with trivial Boolean center and B as a Boolean sublattice.  But this still does not go very far.  For the concept of Boolean families in De Morgan lattices to be possibly significant requires at least that there is a large variety of non- or not-nearly trivial examples.

To have a large class of examples with more than such a single central Boolean sublattice, we have to look for a construction to produce them. And this we can do by ‘multiplying’ lattices.  I will illustrate this with B3, and then generalize.

B3 as a product lattice

The Boolean lattice B3 is the product B1 x B2 of the one-atom and two-atom Boolean lattices.  The product of lattices L and L’ is defined to be the lattice whose elements are the pairs <x,y> with x in L and y in L’, and with operations defined pointwise.   That is:

<x,y> v <z,w>   =  <x v z, y v w>

<x,y>  ∧ <z,w>=  <x  ∧ z, y  ∧ w>

¬<x, y> = < ¬x, ¬y>

<x,y> ≤  <z,w>   iff   <x,y>  ∧ <z,w>  = <x, y>, iff  x ≤ z,  and  y ≤ w

Any such product of Boolean lattices is a Boolean lattice.

Figure 3. B3 as a product algebra.

It looks a bit like ordinary multiplication:  B1 has 2 elements, B2 has 4 elements, 2 x 4 = 8, the number of elements of their product B3.

Inspecting the diagram, and momentarily ignoring the involution, we can see that B3 has two sublattices, that are each isomorphic to B2.  (The definition of ‘sublattice’ refers only to the lattice operations  ∧ and v.)  That is to say, the components of the product construction show up as copies in the product.  And that is also the case once we take the involution into account, given a careful understanding of this ‘copy’ relation.  

The way we find these sublattices:  choose one element in B1 to keep fixed and let the second element vary over B2:

sublattice B3(1) has elements T2, T1, T ⎯ 1, T0

sublattice B3(2) has elements ⊥2, ⊥1, ⊥⎯ 1, ⊥0

Sublattices so selected will be disjoint, for in one the elements have T as first element and in the other the elements have ⊥ as first element.

These sublattices are intervals in B3, e.g. B3(1) = {x in B3: T0 ≤ x ≤ T2}.  

What about the involution? The restriction of the operator ¬ on B3 to interval B3(1) is not well-defined, for in B3, ¬ T2 is not in B3(1), it is  ¬ T2 = ⊥0 which is in B3(2). 

However, there is a unique extension to a Boolean complement on B3(1): start with what we have from B3, namely that ¬T1 = T ⎯1 and  ¬ (T ⎯1) = T1, then add that ¬T2 = T0 and ¬T0 = T2  (“relative complement”; cf. remark about Theorem 10 on Birkhoff page 16, about relative complements in distributive lattices).  It is this relatively complemented interval that is the exact copy of B2, which is a different example of a Boolean family.

(Looking back to section 5, we can now see that the example there was a simple one, where the restriction of the lattice’s involution, to the relevant sublattice, was well-defined on that sub lattice.)

Thus if we have a product of many Boolean algebras, that product will contain many Boolean families:  

If L1, L2, …, LN, are Boolean lattices and L = L1 x L2 x … x LN, then L has disjoint Boolean families isomorphic to L1, L2, …, LN

For example, if e1, e2, …, eN are elements of  L1, L2, …, LN respectively, then the set of  elements S(k) = {<e1, e2, …, ek-1, x, ek+1, …eN>: x in Lk} form a sublattice of L that is (with the relative complement on S(k) defined as above) isomorphic to Lk. (See Halmos, page 116, about the projection of L onto Lk, for precision.)

And if we then augment that product L, in the way we formed L1,  we arrive at a non-Boolean De Morgan lattice, augmented  L.  The result contains many Boolean families, but (e  ∧ ¬e) is in general not the bottom, so it lends itself to adventures in sub classical logic.

But we need to turn now to a less trivial form of augmentation.

7 Non-minimal augmentation of Boolean lattices

A product of distributive lattices is distributive (by a part of the argument that a product of Boolean lattices is Boolean).

The product of De Morgan lattices is a De Morgan lattice.  To establish that, we need now only to check that the point-wise defined operation ¬ on the product is an involution (see Appendix for the proof).

So suppose we have, as above, a Boolean lattice product B, that has many Boolean families, and we form its product with some other, non-trivial non-Boolean De Morgan lattice, of any complexity.

The result is then a non-trivial non-Boolean De Morgan lattice with many Boolean families.

8 Discussion:  what about logic?

The basic sub-classical logic FDE has as non-logical signs only ¬ , v, and  ∧.  That is not enough to have Boolean aspects of De Morgan lattices reflected in the syntax.  

For example, the equation  (a v ¬ a) = (b v ¬ b) defines an equivalence relation between the propositions (a, b).  But the definition involves identity of propositions, which for sentences  corresponds to a necessary equivalence.  To express this, a modal connective, say <=>, could be introduced, in order to identify a fragment of the language suitable for formulating classical theories.

There is much to speculate.

APPENDIX

[1]  Define, for any De Morgan lattice L,  B(e) = {x in L: (x v ¬ x) = (e v ¬e)}.  

Theorem. If L is a De Morgan lattice and its element (e v ¬e) is normal, then B(e) is a Boolean sublattice of L.

First, all elements of B(e) are normal. For (e v ¬e) is normal, and if x is not normal then (x v ¬x) = x.

For B(e) to be a sublattice with involution of L it suffices that B(e) is closed under under the operations ∧, v, and ¬ on L. 

Define t = (e v ¬e).  If d and f are in B(e) then 

  • ¬d is also in B(e), for ¬d v ¬ ¬d = d v ¬d = t
  • (d v f) is also in B(e) because 

[(d v f) v ¬(d v f) ]      = [(¬ d  ∧ ¬f) v (d v f)]

                                    = [(¬ d  v d v f)]  ∧ (¬f  v d v f)]

                                    = t  ∧ t

(d  ∧ f) is also in B(e) because 

[(d  ∧ f) v ¬(d  ∧ f) ]   = [(d  ∧ f) v (¬ d  v ¬f)]

                                    = [(d  v ¬ d v ¬ f)]  ∧ (f v ¬ d v ¬ f)]

                                    = t  ∧ t

So B(e) is a sublattice of L, and hence distributive.  It has involution ¬, its top is t and bottom ¬t.  So B(e) is a bounded De Morgan lattice.  B(e) is Boolean, because all its elements x are such that (x v ¬ x) = t.

B(T) is the Boolean center of the lattice.

[2] Theorem.  The lattice L1, the augmented lattice B3, is a De Morgan lattice.

(a) The operation ¬ extended from B3 to L1 by adding that T = ¬ ⊥ , and ⊥ = ¬T, is an involution.  The addition cannot yield exceptions:  each element e of L1 is such that ⊥ ≤ e ≤ T, which is equivalent to, for all elements e of L1,   ¬ T ≤  ¬ e  ≤   ¬⊥.

(b) To prove that L1 is distributive, we note that, for all elements e of L1,

             T  ∧ e = e  and  T v e = T.

            ⊥ ∧ e = ⊥  and ⊥ v e = e.

To prove: If x, y, z are elements of L1 then x  ∧ (y v z) = (x  ∧ y) v (x  ∧ z).

  • clearly, that is so when x, y, z all belong to B3
  • T ∧ (y v z) = (y v z) and (T  ∧ y) v (T ∧ z) = y v z
  • x  ∧ (T v z) = (x  ∧ T) = x and  (x  ∧ T) v (x  ∧ z) = x v (x  ∧ z) = x 
  • ⊥ ∧ (y v z) = (⊥ ∧ y) v (⊥ ∧ z) = ⊥
  • x  ∧ (⊥  v z) = (x  ∧ ⊥) v (x  ∧ z) = ⊥  v (x  ∧ z) = x  ∧ z

The remaining cases are similar.

[3] Theorem.  A product of De Morgan lattices is a De Morgan lattice.

The product of any distributive lattices is a distributive lattice (Birkhoff 1967: 12)

To establish that the product of De Morgan lattices is a De Morgan lattice, we need then only to check that the point-wise defined operation ¬ on the product is an involution.

Let L1 and L2 be De Morgan lattices and L3 = L1 x L2. Define ¬<x. y> = <¬x, ¬y>

  • ¬¬<x,y> = ¬<¬x, ¬y> =  <¬ ¬x, ¬ ¬y> = <x, y>
  • suppose <x, y>  ≤  <z, w>.  Then, x  ≤ z and y  ≤ w, and therefore ¬ z  ≤  ¬ x and ¬ w  ≤ ¬ y.  So ¬<z, w>  ≤ ¬<x, y>

Bibliographical note.

For the relation between FDE and De Morgan lattices see section 18 (by Michael Dunn) of Anderson, A. R. and N. D. Belnap (1975) Entailment: The Logic of Relevance and Necessity. Princeton.

For distributive lattices in general and relative complementation see Birkhoff, Garrett (1967)  Lattice Theory.  (3rd ed.).  American Mathematical Society and Grätzer, George (2009/1971) Lattice Theory: First Concepts and Distributive Lattices.  Dover.

For products of Boolean lattices see section 26 of Halmos, P. R. (2018/1963) Lectures on Boolean Algebras. Dover. 

Urquhart: semilattices of possibilities (2)

Bas van FraassenLeave a comment

What exactly is so different and difficult about relevance logic? 

I will illustrate with Urquart’s 1972 paper that I discussed in the previous post. I’ll assume my post was read, but won’t rely on it too much. 

1.   A parting of the ways: two concepts of validity

At first, we feel we are on familiar ground. The truth condition for conditionals Urquhart offers is this:

v(A → B, x) = T iff for all y, if v(A, y) = T then v(B, x ∪ y) = T

We see at once that Modus Ponens is valid.  For if A → B is true at x, and A is true at x , then B is true at  x ∪ x, for that is just x itself.

But used to the usual and familiar, we’ll have one puzzle immediately

This semilattice semantics yields as valid sentences precisely the theorems of the implicational fragment of R.  

The first axiom of that logic is A → A.  So, what about v(A → A, x)?   

We might think that it must be T because if v(A, y) = T then v(A, x ∪ y) = T, because x ∪ y has in it all the information that x had and more.  But that is not so!  Urquhart points out emphatically that 

the information in x ∪ y may not bestow T on A, because dragging in y may have dragged in irrelevant information.

So A → A is supposed to be a valid sentence although it does not receive T from all valuations?  

Right!  The criterion of validity is a different one:  

a sentence is valid if there is an argument to it from no premises at all, from the empty set of premises. 

 (Being used to the usual and familiar, we would have thought that the two criteria would coincide …)

So Urquhart’ semilattice has an zero, 0, which is the empty piece of information.  And A is valid if and only if v(A, 0) = T for all evaluations v.

And the join operation obeys the semi-lattice laws, so for example (x ∪ 0) = (x ∪ x) = x.  

Now we can see that the first axiom is indeed valid.  The condition for A → A to be valid is the tautology: if v(A, 0) = T then for all x, if v(A, x) = T then v(A, x ∪ 0) = T.

So within this approach:

That a sentence is valid does not imply that it is True in every possibility.  Valid conditionals, specifically, are False in many possibilities.

And that is a significant departure from how possibilities are generally understood, however different they may be from possible worlds.

But it is right and required for relevance logic, where valid sentences are not logically equivalent.  In general A → A does not imply, and is not implied by B → B, since there may be nothing relevant to B in what A is about.

2.   Validity versus truth-preservation

What happens to validity of arguments?  The first, and good, news is that Modus Ponens for → is not just validity-preservation but truth-preservation, in the good old way, as I mentioned above.

Btu after this, in relevance logic we will depart from the usual notion of valid argument.  We can have instead:

The argument from A1, …, An to B is valid (symbolically, X =>> A) if and only if A1 →. →. An → B is a valid sentence.

That is different from our familiar valid-argument relation.  Some characteristics are the same.

By Urquhart’s completeness theorem, the valid sentences are the theorems of the implicational fragment of R.  This logic has, apart from the rule of Modus Ponens, the axioms:

  1. A → A
  2. (A →. A → B) → (A → B)
  3. (A → B) → .(C → A) → (C → B)
  4. [A → (B → C)] → [B → (A → C)] 

By axiom 4), the order of the premises does not matter.  Therefore =>> is still a relation from sets of sentences to sentences.    So, for example, the argument from A and B to C is valid exactly if A → (B → C) is a valid sentence, which is equally the case if B → (A → C) is a valid sentence.

But there are crucial differences.

3.   What it is to be a sub-structural logic

This consequence relation =>> does not obey the Structural Rules, and the consequence operator is not a closure operator.

Let  X╞A mean that the argument from sentences X to sentence A is valid: the semantic entailment relation.  The Structural Rules (which are the rules that can be stated without reference to specific features of the syntax) are these:

Identity            if A is in X then X╞A

Weakening      If X ⊆ Y and X╞A then Y╞A

Transitivity      If X╞A for each member A of Y and Y╞ B then X╞ B

 The corresponding semantic consequence operator is defined:  Cn(X) = {A: X╞A}.  If the Structural Rules hold then this is a closure operator. 

In relevance logic, Weakening is seen as a culprit and interloper:  extra premises may bring irrelevancies, and so destroy validity.  

And the new argument-validity criterion above does not include Weakening.  If A, …, N =>> B it does not follow that C, A, …, N =>> B.  

Here is an extreme example, that actually throws some doubt on the motivating intuitions about the role of irrelevancy.  Even A does not in general entail A → A in this sense. For:

v(A → (A → A), 0) = T only if:

for all y, if v(A, y) = T then v(A →A, y ∪ 0) = T, 

  …… then v(A → A, y) = T,

    …….. then for all z, if v(A, z) = T then v(A, y ∪ z) = T

and that does not follow at all.  For A’s being true at z and at y is no guarantee that A will be true at  y ∪ z.

So even A → (A → A) is not a valid sentence form.  

This can’t very well be because A has too much information in it, irrelevant to A → A. 

Rather, the opposite: A → A has too much information in it to be concluded on the basis of A.  We have to think of valid conditionals as not being ‘empty tautologies’ at all, but as carrying much information of their own.

4.   Attempting to look at this algebraically

In subsequent work referring back to Urquhart’s paper the focus is on the ‘join’ operation, and the approach is called operational semantics.  But the structures on which the models are based are still, unavoidably, semilattices. 

The properties of the join operation are these: it is associative and commutative, but also idempotent (x ∪ x = x), and 0 is the identity (x ∪ 0 = x).  So far this amounts to a semigroup.  But there is a definable partial order: relation x ≤ y iff x ∪ y = y is a partial ordering:

x ∪ x = x, so x ≤ x

        if x ∪ y = y and y ∪ z = z then x ∪ z = (x  ∪ (y ∪ z) = (x ∪ y) ∪ z = y ∪ z = z ; so ≤ is transitive.

This partial order comes free, so to speak, and that makes it a semilattice.

Can we find some ordering directly related to truth or validity?

Relative to any specific evaluation v we can see a partial order R in the sentences defined by:

ARB iff v(A → B,0) = T

Then we see that:

R is idempotent:  ARA

R is transitive: if v(A → B, 0) = T and v(B → C, 0) = T then v(A → C, 0) =T.

For suppose for all y, if v(A, y) = T then v(B, y ∪ 0) = T. Suppose also that all y, if v(B, y) = T then v(C, y ∪ 0) = T. Since y ∪ 0 = y, we see that for all y, if v(A, y) = T then v(C, y ∪ 0) = T.

So R s a partial order, defined in terms of truth-conditions, to be discerned on the sentences, relative to a valuation.  

But trying to find a connection between this ordering of sentences relative to v, and the order in the semilattice, we are blocked.  For example, define

If A is a sentence and v an evaluation then [[A]](v) = {x: v(A,x) = T} is the proposition that v assigns to A. 

The proposition that v assigns to A will most often not have 0 in it, so it is not closed downward.  Nor is it closed upward, for if x is in [[A]](v) it does not follow that x ∪ y is in [[A]](v). So the propositions, so defined, are neither the ideals nor the filters in the semilattice.

I have a feeling, Toto, that we are not in Kansas anymore …….

REFERENCES

Standefer, S. (2022). “Revisiting Semilattice Semantics”. In: Düntsch, I., Mares, E. (eds) Alasdair Urquhart on Nonclassical and Algebraic Logic and Complexity of Proofs. Outstanding Contributions to Logic, vol 22. Springer, Cham. https://doi.org/10.1007/978-3-030-71430-7_7

Urquhart, Alasdair (1972) “Semantics for Relevant Logics”.  Journal of Symbolic Logic 37(1); 159-169.

Urquhart: semilattices of possibilities

Bas van FraassenLeave a comment

(and of possibilities coupled with possible worlds)

Possibilities versus possible worlds    page 1

Truth and falsity of sentences   page  2

Urquhart’s initial results: relevance logic versus intuitionistic logic   page 2

The discreet charm of the relevantist   page 3

How can we think about Urquhart’s possibilities?   page 3

Possibilities with worlds on the side   page 4

How can we think of Urquhart’s world-coupled possibilities?   page 4

What we may regret   page 5

Possible worlds, as they appear in the semantics of modal logic, trade on our imagination schooled by Leibniz.  They are complete and definite:  the set of sentences that is true in a given world — that world’s description — leaves no question unanswered. 

Possibilities versus possible worlds

This notion of a world soon had its rivals in various approaches to non-classical logic.  

One of the first appeared in Urquhart’s 1972 semantics for relevant logic.  In his informal commentary, the elements (not yet named “possibilities”) are something to be thought of as possible pieces of information.  Urquhart emphasizes that his concept “contrasts strongly with that of a possible world [since] a set of sentences exhaustively describing a possible world must satisfy the requirements of consistency and completeness.” (p. 164). At the same time he sees his enterprise as generalizing the form familiar from possible world semantics:

“The leading idea of the semantics is that just as in modal logic validity may be defined in terms of certain valuations on a binary relational structure so in relevant logics validity may be defined in terms of certain valuations on a semilattice-interpreted informally as the semilattice of possible pieces of information.” (p. 159)

Yet in most of the paper there is no, or little, role for the distinction between the description and the described.  Indeed, Urquhart goes on quickly to specify that a piece of information, as he conceives of it, is a set of sentences. In later work in this area, his approach tends to be presented more abstractly, with the nature of the elements of the semilattice left as characterless as is the nature of possible worlds in the standard analysis of modal logic. 

Lloyd Humberstone (1981) introduced “possibilities” as the general term for what may be “less determinate entities than possible worlds … [which] are what sentences … are true or false with respect to.”  This term is now standard (witness e.g. the paper by Holliday and Mandelkern referenced in my recent posts), and I will use it.

When we think about possibilities, with the intuitive guide that they must correspond to partial descriptions of worlds, it is natural to see the possibilities as forming a partially ordered set (poset): x may have as much as or more information in it than y.  That partial ordering relation is reflexive and transitive.  Urquhart introduces in addition a join operation: if x, y are possibilities then so is (x ∪ y).  The more sentences the more information, so (x ∪ y) has at least as much as, or more than, x or y.  Urquhart adds the empty set of information, 0, which has the least information.  A poset with this sort of operation defined on it is a semilattice (specifically, a join-semilattice).

Truth and falsity of sentences

Sentences may be evaluated as true or false ‘on the basis of’ given information.  That is not as straightforward as it may look at first.  Urquhart encourages us to think of it as the relation of premises to conclusion in an argument which commits no fallacies of relevance.  His target, after all, is relevance logic, so that must be his main guide.  

Given that, we cannot assume that if A is in x then A is true at x.  Not so.  There would have to be an argument from x to A, with all the sentences in x being relevant, playing an indispensable role, in that argument.  While this notion of relevance, in the role it plays in the informal commentary, cannot be made more precise, what can be done is to show the form that any evaluation must take. 

An evaluation is a function v that assigns truth-values to sentences relative to elements of the semilattice.  Given such an assignment to atomic sentences, it is completed for conditionals by the clause

v(A → B, x) = T iff for all y, either v(A,y) = F or v(B, x ∪ y) = T

with the more friendly formulation being

                                    iff for all y, if V(A, y) = T then v(B, x ∪ y) = T

with “if … then” understood in our metalanguage as the material conditional.  Since (x ∪  x) = x, it follows that Modus Ponens is valid for the arrow.

Urquhart’s initial results: relevance logic versus intuitionistic logic

Urquhart proves quickly that the set of formulas involving just →  which are valid in the sense of always receiving T relative to all elements of such a semilattice, are the theorems of Church’s weak theory of implication.  That is also the implicational fragment RI of the relevance logic R.

Urquhart notes secondly that if we as an additional principle that 

(*)  if V(A, x) = T  then V(A, x ∪  y) = T

then we leave relevance logic and arrive at the implicational fragment of intuitionistic logic.  

That we get a characteristic irrelevancy is clear:  if V(B, x) = T, then (given *), it will be the case for all y, that whether or not V(A, y) = T, V(B, x ∪ y) = T.  In that case the irrelevancy [B →( A → B)] is valid.  

The underlying difference between the two sorts of logic is that, if relevance is taken into account, then the structural rule

Weakening:  if X entails B then X ∪ {A} entails B

is invalid.   A relevance logic is a sub-structural logic.

The discreet charm of the relevantist

Relevance logics, which are Urquhart’s main target in this study, are, in many people’s eyes, weird.  Something surprising surely springs to the eye when we note the omission of condition (*) in the semantics for RI.   Although in the visualized picture (x ∪ y) contains all the information included in x, we are not to assume that if A is true at x then it is true at (x ∪ y).   For the truth evaluation clause for A → B to make sense, we must think of (x ∪ y) as produced by adding the information in x to whatever makes A true at y.  Nevertheless, the result (x ∪ y) may apparently lack some information, which was present in x, or have in it some information that renders some of the content of x impotent.

It is instructive to look at the model Urquhart constructs to show the completeness of RI.  The elements of the semilattice are the finite sets of formulas of the language of RI, ∪ is set union, and 0 is the empty set.  Then the evaluation defined is

V(B, {A(1), …, A(n)} = T if and only if A(1)→ … →. A(n) → B is a theorem of RI

In this notation (due to Church) a dot stands for a left hand parenthesis, and you have to imagine the right hand parenthesis.  So A→. B → A is the same as A → (B  → A).  Since that is not a theorem, it is clear that in general V(A, {A, B}) may be F.

How can we think about Urquhart’s possibilities?

How can we think of this?  I see two ways.  The first is the one always evident in discussions of relevance logic:  an irrelevant premise is a blemish, a blot on the escutcheon, anathema to natural logical thinking.  So if some premises provide a good argument for global warming, say, the addition of a premise about the beauty of the Mona Lisa spoils the argument, removes its validity.

There is a second way, it seems to me.  As a monologue or dialogue continues there are accepted devices for rendering something impact-less, though it was previously or elsewhere entered into the context.  You may take back what you said.  So if each element of the semilattice is a record, with times of entry noted, of things said in a conversation, then some of the content of x might be impact-less in the combination (x ∪ y).

It may also be interesting to think of what could happen here to the notion of updating, or conditionalizing.  Suppose x is the information a person has, who then learns that A. So then his new information is x ∪ {A}.  This will presumably mean that he now has some beliefs (counts as true) some statements he did not have as beliefs before.  But we can also see that, due to the strictures on relevance, he will in general lose beliefs that he had.  

We can imagine examples:  someone believes that Verdi is Italian, and Bizet is French, and now is told (and accepts) that they are compatriots.  He will clearly have to lose at least one of his beliefs about them, but which one?  Or should he lose both the original beliefs; then should he at least retain that they are both from countries with Romance languages?  Accommodating loss of beliefs has been not easy to handle in logical treatments of updating.  Perhaps the advice to consider is that he should believe all and only what is relevantly implied by his information.  That works even if his total information is made inconsistent by the addition.

Possibilities with worlds on the side

Lewis and Langford’s classic text distinguished the strict conditional “Necessarily, if A then B” from the ordinary conditional “If A then B”, in their creation of modern modal logic.  That relation, between strict and ordinary, is intuitively also the relation between the conditional in relevance logic E and relevance logic R.  (“E” for “entailment”, “R” for “relevant”.)  

To elaborate the semantics for RI into one for EI Urquhart accompanies each possibility with a possible world.  To determine the truth value of a sentence, he submits, “we may have to consider not only what information may be available, but also what the facts are”.  So the new sort of model has as its elements pairs x, w, with x an element of the semilattice and w a member of a set of worlds.  That set of worlds is equipped, in the familiar way, with a ‘relative possibility’ relation, which Urquhart stipulates to be reflexive and transitive.

Now the correct evaluation clause for the conditional is this:  

v(A → B, x, w) = T iff for all y, and all worlds u which are possible relative to w, 

if  v(A,y, u) = T then  v(B, x ∪ y, u) = T

No special symbol is introduced for necessity: “Necessarily A” is symbolized as “(A→ A)→ A”.  The implicational fragment EI of E is sound and complete on this semantics.

How can we think of Urquhart’s world-coupled possibilities?

An obvious way is this:  in the couple x,w the world w represents what is actually the case and the element x represents the information a certain privileged inhabitant has.  Here “information” is to be read very neutrally:  it may be true or false information, even inconsistent information,  Now there may be a distinction in the language between purely factual statements, whose truth value is entirely determined by the world w and information-dependent statements whose truth value is at least in part determined by the possibility x.  The conditionals are of the latter sort.  

On this reading, a person who says, in sequence, “It rains” and “If it rains then it pours” is, by intention, if s/he understands her own language, first asserting that something is the case and then, after that, expressing his belief as to what things are really like in this vale of tears.  

What we may regret

I have been hinting along the way that there may be interesting connections between Urquhart’s semantics for relevant logic and current discussions about conditionals – even if not immediately obvious.  There are two disparities with current discussions, such as about epistemic modals, probabilities of conditionals, and the like.  The first is that in the latter reference to roles for inconsistent information, let alone to relevance logics, is hard to find if not absent altogether.  The second is that in the extensive literature concerning relevant implication that developed since the 1970s, reference to any natural language examples, let alone to work in philosophy of language, is scarce to the point of being negligible.

But the salience of similarities, between the exploration of liberal conceptions of possibilities and worlds suggest to me that they should perhaps be kept in mind.

SOURCES

Anderson, Alan R. and Nuel Belnap (1975) Entailment: The Logic of Relevance and Necessity.  Princeton: Princeton University Press.

Humberstone, I. L. (1981) “From Worlds to Possibilities”.  Journal of Philosophical Logic 10: 313-339.

Standefer, S. (2022). “Revisiting Semilattice Semantics”. In: Düntsch, I., Mares, E. (eds) Alasdair Urquhart on Nonclassical and Algebraic Logic and Complexity of Proofs. Outstanding Contributions to Logic, vol 22. Springer, Cham. https://doi.org/10.1007/978-3-030-71430-7_7

Urquhart, Alasdair (1972) “Semantics for Relevant Logics”.  Journal of Symbolic Logic 37(1); 159-169.

Tautological entailment (3) intensional negation

Bas van FraassenLeave a comment

Complementation

Each atomic fact has a complement; above I called it its evil twin. The fact that his words were apropos has as its complement the fact that his words were malapropos, and conversely.

Since we are treating the atomic facts as unanalyzed wholes, we cannot define this relationship, but introduce it by means of an operator and a postulate:

Postulate: every atomic fact has a unique complement which is also an atomic fact, and is the complement of its own complement.

The operator ^ maps an atomic fact into its complement:

b^^ = b (idempotent)

Complex facts do not have complements, for there are no disjunctive facts. There is no direct route to defining complementation on propositions. But there is an indirect way.

A direct way would be this: the propositions, which are the closed sets of facts, form (as we found above) a complete distributive lattice — now take on the task of defining a complementation operation on this lattice!

The indirect way that I shall follow is this: I will identify sub-lattices on which there is a well-defined complementation operation, and these will suffice for the semantic analysis of the logic of tautological entailment.

In fact, the clue to this is precisely that the propositions of interest are those expressed by the sentences of a language. It is these that should form (to use the term introduced by Nuel Belnap) an intentionally complemented distributive lattice.

The point about sentences is that they are built up systematically from atomic sentences, in each case from a finite number of atomic sentences. An interpretation of the language which assigns propositions to sentences follows this structure, and so produces a countably generated sub-lattice of the right sort.

Prior to the assignment of propositions to sentences I will associate with each sentence A two bases, its T-base T(A) and its F-base F(A), which are the sets of primary facts that make A true, respectively false.

For each atomic sentence p there is an associated fact e, and T(p) = {e}, F(p) = {e^}. Building on that assignment of atomic facts to the atomic sentences, the definition of the bases follows the recursive definition of the set of sentences of a sentential logic. For all sentences A, B:

  • T(~A) = F(A); F(~A) = T(A)
  • T(A & B) = T(A) . T(B); F(A & B) = F(A) ∪ F(B)
  • T(A v B) = T(A) ∪ T(B); F(A v B) = F(A) . F(B)

where the product X.Y = {e.f: e is in X and f is in Y}.

Next we use this to associate a proposition T*(A) with each sentence A, defining it as the closure of the T-base:

T*(A) = [T(A)].

The theorems about propositions in the previous post apply, so that the meet and join are just intersection and union.

T*(A & B) = T*(A) ∩ T*(B), and T*(A v B) = T*(A) ∪ T*(B)

The following two lemmas show that there exists a complementation operation on these propositions.

Lemma. T*(~~A) = T*(A), F(~~A) = F(A)

Proof. T(~~A) = F(~A) = T(A); and since T(~~A) = T(A) their closures are also the same; similarly for the second part.

Lemma. If T*(A) ⊆ T*(B) then T*(~B) ⊆ T*(~A)

Proof: Suppose that T*(A) ⊆ T*(B). Then all facts subordinate to facts in T(A) are subordinate to facts that are subordinate to facts in T(B). But subordination of facts is transitive, so all facts subordinate to facts in T(A) are subordinate to facts in T(B).

So T*(B) includes both T(A) and T(B), hence also T(A) ∪ T(B), that is, T(Av B). So T*(B) = T*(A v B), since all facts subordinate to facts in T(A) are already included among the ones subordinate to those in T(B).

Hence T*(~B) = T*(~(A v B)) = [F(A vB)] = [F(A).F(B)]. This includes all facts subordinate to facts in F(A), because if e is thus, so is e.f for any fact f.

Hence T*(~B) ⊆ [F(A)] = [T(~A)] = T*(~A).

Definition. The operation ^ is defined on the family of propositions {T*(A): A is a sentence}, and Y = X^ if and only if there is a sentence A such that X = T*(A) and Y = T*(~A).

Theorem. The family {T*(A): A is a sentence} form a countably generated sublattice L+ of the lattice of propositions, which is distributive and intensionally complemented, that is, there is an operation ^ such that for all propositions X in L+, X^^ = A (idempotent) and if X ⊆ Y then Y^ ⊆ X^ (order inverting).

Since the family L+ is closed under both intersection and union it is a lattice, and the proof of distributivity is the same as in the preceding post. But it can only be a sublattice, since each element is a proposition generated by a finite base.

The above lemmas show that the operation ^ is idempotent and order inverting.

The logic of tautological entailment is sound and complete for countably generated intensionally complemented distributive lattices (Nuel Belnap 1967). This guarantees then that this logic is sound under the present interpretation.

The claim of completeness for this logic under our interpretation does not follow in the same way. What is peculiar about the sublattice L+ is that its set of atoms (the propositions which are closest to the zero element) is closed under complementation: [{e}]^ = [{e^}]. That is not typical: for example, if a Boolean lattice has three atoms, the complement of one of them is the join of the other two.

Nevertheless our lattices of propositions suffice for the logic of tautological entailment. We need to take the bull by the horns to prove completeness! I will put that in the Appendix, it is the more technical part.

NOTE. That completeness proof is in my 1969 article “Facts and Tautological Entailment”. What is new in these posts, and continued in the Appendix, is to present this semantic analysis in the form that aligns it with the lattice-theoretic approach which Nuel Belnap introduced. At the same time, by doing this, I can show how it fits into the general framework that I presented in the posts called “An Oblique Look at Propositions”.

APPENDIX

Recall from the first post on Tautological Entailment its basic principle (where an atom is either an atomic sentence or the negation of an atomic sentence):

If A is a conjunction of atoms, and B a disjunction of atoms, then A tautologically entails B if and only if at least one conjunct in A is a disjunct in B.

Definition. A primitive entailment (A, hence B) is an argument whose single premise A is a conjunction of atoms and its conclusion B is a disjunction of atoms.

Theorem. A primitive entailment (A, hence B) is valid if and only if A tautologically entails B.

This means that A =(p(1) & … & p(k)) while B = (q(1) v … v q(m)), with each p(i) and q(j) an atom, and hence each has as its T-base a set containing a single atomic fact. The T-base of A is then a single molecular fact e and the T-base of B is a set containing m atomic facts f(1), … ., f(m). For T*(A) to be included in T*(B) requires that at least one component of e is identical with one of the facts f(j). And this requires that at least one conjunct in A is a disjunct in B.

So what about all the other arguments, that don’t have this simple form? In the full exposition of the logic of tautological entailment by Anderson and Belnap, a number of principles are added, which together guarantee that to check any argument will consist in checking a family of primitive entailments. (“conversion into normal form”)

These principles include the basic lattice laws as well as distribution, which we have already dealt with along the way. In addition of course they include the principles of double negation and De Morgan’s Law, which correspond to the idempotency an order inversion of intensional negation. The only thing that we still have to address then, is De Morgan’s Law, which allows the replacement of ~ (A & B) by (~A v ~ B)) and ~(A v B) by (~A & ~B).

Lemma. T(~(A & B)) = T(~A v ~B); T(~(A vB) = T(~A & ~B)

Proof. T(~(A & B)) = F(A & B) = F(A) ∪ F(B) = F(~~A) ∪F(~~B) = T(~A) ∪ T(~B) = T(A v B). Argument for the second part is similar.

Tautological entailment (2) truth-making

Bas van FraassenLeave a comment

In the preceding post I outlined, intuitively, what Anderson and Belnap’s logic of tautological entailment is, and sketched an accompanying semantics framed in a rudimentary theory of facts as truth-makers. Here I will make this explicit to the extent of governing conjunction and disjunction. We’ll see that the lattice of propositions is rather a simple one, but also that it has the additional property of distributivity, corresponding to the classical logical law of Distribution.

I said that there are atomic facts and complex facts, the latter being something like bundles of atomic facts. There is no order in these bundles, so you can think of them as sets or as mereological sums. But nothing hinges on that, so for generality I will just indicate how facts combine to make more facts.

A model has as first ingredient a set of facts, and I specify that the facts are countable, there are no more than there are natural numbers. There is, as second ingredient, an operation (combination) on facts to produce other facts, symbolized by a dot. So if b, c are facts, then so is b.c. (See Appendix for some clarifying remarks.)

Postulate: every fact is a combination of atomic facts; and facts are identical if and only if they are combinations of the same atomic facts.

Note that this Postulate does not imply that a combination must be finite; there is even a fact that is the combination of all atomic facts. Because there is no significant ordering, if A is a set of facts, we can legitimately refer to the combination of all A’s members, and denote it ΠA.

As third ingredient there is a relation ≤ among facts, subordination, that we can define:

Fact b is subordinate to fact c ( b ≤ c) if and only if there is a fact d such that b = d.c

By this definition, it follows that b ≤ b, as well as that ≤ is transitive, and in view of the Postulate, if b ≤ c and c ≤ b then b=c..

Fourth ingredient: The propositions are the sets of facts that are closed under subordination. Finally, fifth, the relation of making true, e » Q, holds just iff fact e is a member of proposition Q. So, if e makes proposition Q true, then so does every fact that is subordinate to e.

Being the closed sets of facts, as we know from earlier discussion, the propositions form a complete lattice L, partially ordered by set inclusion. The meet of Q and R is their intersection, and their join is the closure of their union. But this lattice construction is simpler than some that we saw before, and so has some special properties.

Distributivity

Theorem 1. If Q, R are propositions then fact g is in Q ∩ R if and only if there are facts e and f such that g = e.f, where e is in Q and f is in R.

In other words, Q ∩ R = {e.f : e is in Q and f is in R}.

Proof. It is clear that if e is in Q then e.f is as well, because e.f ≤ e, and similarly that e.f is in R if f is in R. So if e is in Q and f in R then e.f is in Q ∩ R.

Conversely, suppose that g = (e.f) is in Q ∩ R. Then g is in Q and also in R. But then we can recast that as: there are facts h, k such that g = h.k with h in Q and k in R, namely, g = h = k = (e.f), recalling that combination is idempotent.

Theorem 2. If Q and R are propositions then [Q ∪ R]= Q ∪ R

For suppose that e ≤ f for some member of Q ∪ R. If f is in Q, then e is also in Q, for it is subordinate to f. And similarly if f is in R. So all the facts subordinate to any member of Q or R is already in Q ∪ R. Since ≤ is transitive, this applies also to any facts that are subordinate to facts that are subordinate to … subordinate to facts in Q ∪ R. Hence all of the members of [Q ∪ R] are already in Q ∪ R.

So we do not need a special symbol for the join operation on propositions, it is just union. Note well though that this does not go for set of facts in general; a set is not typically its own closure! Note also that this holds because there is here no subordination relation of facts to sets of facts that is more complicated than their subordination to specific members of those sets.

Theorem 3. L is distributive: if Q, R, S are propositions then Q ∩ (R ∪ S) = (Q ∩ R) ∪(Q ∩ S).

That is obvious now, given that we are dealing with just set union and set intersection, for propositions. (But given how fact-combination works, it is as well to spell this out properly: see the Appendix.)

The next, final post in this series, will take up negation, and complete the semantics for tautological entailment.

APPENDIX

So that order is automatically absent, combination has the properties:

b.b = b (idempotent)

b.c = c.b (commutative)

b.(c.d) = (b.c).d (associative)

Call b an atomic fact exactly if for all facts c, b = b.c implies that b = c. (Note that, in view of the postulate, b = c is the case if and only if there is a set A of facts such that both b and c are the fact ΠA.

Long, perhaps more insightful, proof of Theoremm 3: Q ∩ (R ∪ S) = (Q ∩ R) ∪(Q ∩ S).

By theorem 1, fact g is in Q ∩ (R ∪ S) exactly if there are facts e, f such that g = e.f while e is in Q and f is in (R ∪ S), that is to say, in R or in S. So g = e.f with e in Q and f in R or e in Q and f in S, thus g is either in Q ∩ R or in Q ∩ S), that is, g is in (Q ∩ R) ∪ (Q ∩S).

Conversely, if g is in (Q ∩ R) ∪(Q ∩ S) then g is in either (Q ∩ R) or (Q ∩ S). The two cases are similar, so suppose the former. In that case g = e.f with e in Q and f in R, for some facts e, f. This g = e.f for some fact e in Q and f in (R ∪ S), and therefore g is in Q ∩ ( R ∪ S).