logic – Bas van Fraassen's philosophy blog

[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”.

(x v x) ⊃ x
x ⊃ (x v y)
(x v y) ⊃ (y v x)
(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:

~[~(~x & ~y) & ~x]
~[x & ~~(~x & ~y)]
~[~(~x & ~y) & ~~(~y & ~x)]
~[~(~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:

□(x ⊃ y) ⊃ (□x ⊃ □y)
◊(x v y) ≡ (◊x v ◊y)
~◊~(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.

I’ve encountered Moore’s Paradox in too many philosophical issues to count. The import of this paradox is that there are statements which could certainly be true, hence consistent in that sense, but cannot be believed, on pain of incoherence.

The form of the typical example is “A, and I do not believe that A” or “It is not the case that A, and I believe that A”. That is not precisely how Moore himself presented it, but rather Wittgenstein’s formulations in his Philosophical Investigations:

“Moore’s paradox can be put like this: the expression “I believe that this is the case” is used like the assertion “This is the case”; and yet the hypothesis that I believe that this is the case is not used like the hypothesis that this is the case.” ( p. 190 in the 2nd edition, Oxford 1998))

Many instances of this form are actually true. For example, I neither believe nor disbelieve that it is presently raining in Peking, but either it is or it is not. So one of the instances of Moore’s paradox is true: either “it is raining in Peking and I do not believe that”, or “it is not raining in Peking and I do not believe that” is true.

But I would reveal a serious incoherence in my state of opinion if I genuinely and correctly asserted either of these statements.

My take on this situation is that we are looking at two linguistic functions. The same words can be used either to state of fact (in this case, stating that I have a certain belief) or to express a belief.

The logic of statements is the very familiar one that we all learn in elementary logic courses. The logic of expression (or avowal) has drawn attention but has not been much explored.

I have thought of a parallel we can explore between these two logics, if we are careful about how we formulate the relevant consequence relations.

In the logic of statements A is a consequence of premise B, on pain of logical inconsistency, exactly if premise B cannot be true together with anything contrary to A. For example, that the cloth is red is a consequence of the premise that the cloth is scarlet because the cloth cannot be scarlet while having any color disjoint from red.

In the logic of belief expression I’ll say that A is a consequence of premise B, on pain of incoherence, exactly if premise B cannot be coherently believed together with anything contrary to A. You cannot coherently believe (the content of) “it is raining in Peking and I do not believe that it is raining in Peking”, nor “it is raining in Peking and I neither believe nor disbelieve that it is raining in Peking”. So, “I believe that it is raining in Peking” follows from “It is raining in Peking” on pain of incoherence, in the sense here defined.

What must the logic of expression be like then?

First, it must have a lot in common with the logic of statements. If A is tautology in the logic of statements I can certainly not coherently believe anything contrary to A. Therefore, if A is a tautology in the logic of statements it is also a tautology (defined analogously) in the logic of expression.

But the properties of the consequence relation are not the same all told. In the logic of statements there is the principle (sometimes called the Deduction Theorem) that if A is a consequence of premise B then the conditional “If B then A” (in the material sense, i.e. “Either not B, or A”) is a tautology. If that principle also held in the logic of expression then the following would be tautologies there:

“If it is raining in Peking then I believe that it is raining in Peking”

“If I believe that it is raining in Peking then it is raining in Peking”

which, if expressed by me as beliefs would show that I was convinced of my own powers of clairvoyance. Clearly they are not tautologies in the logic of expression.

This situation, that the analogue of the Deduction Theorem fails, is not unknown in philosophical logic. It appears quite typically in the logic of statements of a language in which there can be sentences which are neither true nor false (failure of the principle of Bivalence). So here, in the logic of expression, it clearly has to do with the fact that coherence does not require me to be highly opinionated: I can suspend both belief and disbelief, if I wish.