Thomason

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

[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 N₅, 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 N₅}

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.