Logic, belief and language.

Some small gifts for Johan van Benthem on the occasion of his 50^{th} birthday ^{∗}

Elias Thijsse

Abstract

I discuss three different and, as a matter of fact, totally unrelated topics, reflecting part of my research interests, which are (hopefully) properly included in Johan van Benthem’s: (1) a generalization of the Lindenbaum lemma with a connection to Universal Algebra, (2) an account of real or exclusive belief, as opposed to knowledge and subordinated under general belief, and (3) a reconciliation of some proposals concerning prenominal genitive possessives by means of generalized quantifiers. The order is somewhat arbitrary. Since (3) is an outgrowth of my master thesis and (1) and (2) are (remotely) related to the subject of my dissertation, both of which were supervised by van Benthem, this is meant to show his importance for my work.

Contents

1 A useful operation for finite closures 2

2 Real or exclusive belief 4

3 Generalized quantifiers – 15 years later 6

∗Written while being a visiting scholar at CSLI/Stanford University, where I spent part of my sabbatical term, for which CSLI is gratefully acknowledged

A spoken message

Consult my j50 webpage or click on elias.wav in a file listing of the CD contents.

1 A useful operation for finite closures

Sometimes essentially the same result pops up in various areas. Here is one such result, with connections to universal algebra and the standard Lindenbaum construction, a common technique used for proving completeness.

Let A be a countable set. Consider a closure operation F on ℘(A) for which A is finitely generated and which furthermore satisfies a compactness property. Let us call this, appropriate to the occasion, a Van Benthem operation. So, more formally,

F : ℘(A) ⟶ ℘(A) is a Van Benthem operation on ℘(A) if for all X, X′ ⊆ A:

1. X ⊆ F (X) (extension)

2. F F (X) ⊆ F (X) (weak idempotence)

3. X ⊆ X′ ⇒ F (X) ⊆ F (X′) (monotonicity)

4. There is a finite Y ⊆ A such that F (Y) = A (finite generation)

5. F (X) ⊆ ⋃ {F (Y) | Y ⊆ X & Y is finite} (finiteness)

Observe the following easy consequences for Van Benthem operations F:

• F F (X) = F (X) (idempotence)

• F (X) = ⋃ {F (Y) | Y ⊆ X & Y is finite} (compactness)

The first follows immediately from (1) and (2), the second from (3) and (5). Also notice that F (A) = A, so F has at least one fixpoint. In general, it has many fixpoints, as we will see.

Theorem. Let F be a Van Benthem operation on ℘(A) and L = rng(F)−{A}. Then every X ∈ L has a maximal extension X^{∗} in L.

Proof. Assume that A is countably infinite (when A is finite the proof trivializes). Let {a_{n}}_{n} be an enumeration of A. Define the following sequence {X_{n}}_{n} in ℘(A) and its limit X^{∗}:

• X_{0} = X

• X_{n+1} = \{ \begin{matrix}F (X_{n} ∪ \{a_{n}\}) & if F (X_{n} ∪ \{a_{n}\}) ≠ A \\ X_{n} & otherwise \end{matrix}

• X^{∗} = ⋃_{n} X_{n}.

Notice that {X_{n}}_{n} is an ascending chain in L, since all its members are F - images and different from A. Next observe that we usually get many other fixpoints:

(i) F (X_{n}) = X_{n} for all n (by idempotence and definition X_{n}).

(ii) Also F (X^{∗}) = X^{∗} since (⊇) X^{∗} = ⋃_{n} X_{n} = (i) ⋃_{n} F (X_{n}) ⊆ (mon)

F (⋃_{n} X_{n}) = F (X^{∗}), and (⊆) suppose a ∈ F (X^{∗}) ⇒ (5) there exists a finite Y ⊆ X^{∗} such that a ∈ F (Y) ⇒ for some n : Y ⊆ X_{n}, so (mon) a ∈ F (X_{n}) ⊆ X^{∗}.

(iii) X^{∗} ≠ A, for suppose X^{∗} = A. By (4) there is some finite Y ⊆ A so that F (Y) = A. Thus Y ⊆ X^{∗}, so again for some n : Y ⊆ X_{n}, and therefore A = F (Y) ⊆ F (X_{n}) = X_{n}, which implies X_{n} = A, contradicting X_{n} ∈ L.

(iv) X^{∗} is maximal, for suppose not. Then for some Y ∈ L: X^{∗} ⊂ Y, so there is a a ∈ Y −X^{∗}. Let a = a_{n}, then a_{n} ∉ X^{∗} ⊇ X_{n+1} ⇒ F (X_{n}∪{a_{n}}) = A ⇒ (mon) F (X^{∗} ∪{a}) = A. Yet also X^{∗} ∪{a} ⊆ Y, hence A = F (X^{∗} ∪{a}) ⊆ F (Y) = Y, contradicting Y ∈ L.

In all, from (ii) and (iii) it follows that X^{∗} ∈ L and so, by (iv), X^{∗} is maximal in L. QED

We now turn to two applications of this theorem. Both results are well-known, although their relation has not been observed, to my knowledge. Also the conditions of the second application are less restrictive than usually.

Application 1: Lindenbaum lemma. Let A = F orm (the well-formed formulas of some standard logical language) and ⊢ be a (finite) classical inference relation. Putting Cn(X) = {φ | X ⊢ φ}, it is easily verified that Cn is a Van Benthem operation on ℘(F orm), e.g. (4) follows from ex falso: Cn({⊥}) = F orm. Next, notice that L amounts to the set of consistent theories. Now, if X is a consistent set of formulas, i.e. Cn(X) ≠ F orm, then (idempotence) Cn(X) ∈ L, and so Cn(X) and, therefore, also X can be extended to a maximal consistent set X^{∗}.

Application 2: Universal Algebra. Let A = O_{k}, the set of operations on base k, which can be regarded as a set of k truth values. A closed set (E.Post) or a clone (P.Hall) is a subset of O_{k} which contains all projections (functions π_{i} : k^{n} ⟶ k s.t. for all x⃗ ∈ k^{n} : π_{i}(x⃗) = x_{i}) and is closed under composition. The intersection of clones is again a clone, and since both O_{k} and the set of projections are clones, these are the resp. top and bottom element of the lattice of clones in O_{k}. See [6] for a general account of clones in universal algebra and [8, 11] for a detailed study of some important clones in three- and four-valued logic and the Galois connection to the relations they preserve. So, every X ⊆ O_{k} is contained in a least clone [X].

The completion operation involved is here F (X) = [X]. O_{k} is finitely generated by one of the many functionally complete sets of operators, e.g. the one consisting of the (0-place) constants and (2-place) max, min and cyclic permutation. Finally, compactness results from the fact that any operation in the clone [X] is constructed by means of finitely many compositions of elements of X and projections, thus only a finite number of elements of X actually have been used.

So the conditions of the theorem are fulfilled: let L be the set of proper clones in O_{k}, i.e. the clones properly contained in O_{k}. Then [·] is a Van Benthem operation, thus every proper clone in O_{k} is contained in a maximal (proper) clone.

This result is usually attributed to Jablonskij [4]. Its proof given in the literature [5, 6] invokes Zorn’s lemma, which is known to be equivalent to the Axiom of Choice (AC), an axiom of set theory not everyone is willing to accept. However, the proof of the above theorem shows we can do without AC. For example, the element a in (iv) is simply the first a_{n} occurring in Y − X^{∗}.

Maximal clones are essential for establishing the fine structure of the lattice of clones (in which they are the so-called dual atoms): every proper clone can be generated as an intersection of maximal clones. In fact, the given existence result has a funny, yet useful consequence. It immediately provides a completeness criterion: X ⊆ O_{k} is complete in O_{k} (i.e [X] = O_{k}) iff X is not contained in a maximal clone. The criterion can be implemented, since the maximal clones are explicitly described in a famous result by Rosenberg: every maximal clone is the set of operations preserving one out of six types of relations on k, among which there are non-trivial equivalence relations and bounded partial orders (i.e. partial orders on k with least and greatest element).

2 Real or exclusive belief

There is a very usual sense of belief that can be characterized as real or exclusive belief. It is the common way of expressing ‘belief’ as opposed to ‘knowledge’, as demonstrated in the following examples.

(a) I believe that black holes exist.
(b) I believe that Milosevic endangers world peace.
(c) I believe the Euro will not become a strong currency.

I take it that, in a scientific and philosophical sense, we do not really know that black holes exist (or that the earth is round, etcetera), but there certainly is strong evidence to believe so. In its most extreme form, this implies the rejection of a posteriori knowledge, even in cases of direct perception.

In colloquial language, however, one would probably say that one knows there is a computer on the desk, if one sees it. Or, one simply says: ‘there is a computer on the desk’, which, at least pragmatically, has the same effect (if knowledge is true and positively introspective, using a strong form of the Gricean maxim of quality, cf. [8, 12]). So, when we use ‘believe’ instead of ‘know’, this usually indicates that we do not consider the evidence entirely conclusive. This is, of course, by no means restricted to scientific propositions. Even without contrastive stress on ‘believe’, uttering (b) implies that the agent does not know the expressed opinion. Though conceivably correct, it may be the result of biased media reports and western propaganda. The same goes for (c), which in fact reflects my personal, hopefully incorrect view. In all such cases choosing ‘believe’ instead of ‘know’ implies that one does not know. This, of course, is nothing but what is predicted by a straightforward application of the Gricean maxim of quantity. If one really would know (or rather, if one thinks one knows), there would be no point in using a weaker (and possibly even longer) expression.

Therefore, this sense of ‘real’ or ‘exclusive’ belief (R) is both quite common and definable in terms of the more general notions of belief (B) and knowledge (K). Construed as modal operators, they are simply related by the equation:

Rφ = Bφ ∧ ¬Kφ

This analysis is somewhat reminiscent of that of ‘Bewirken’ [3] or ‘deliberatively seeing-to-it-that’ (‘dstit’) [2, 14, 17]^{1} as suggested in Action Logic, which also involves both a positive and a negative condition.^{2} Though very simple, this equation has some remarkably nice properties. Even when B and K are □-like operators described by normal systems (for example, K4 and S5, resp.) and K implies B, the construal leads to avoidance of many types of logical omniscience, without need of any special mechanism to block inference. Some of the most usual types of omniscience are listed below (See [8, 9, 10, 13] for other accounts of the logical omniscience problem).

\begin{aligned}N & ⊢ φ ⇒ ⊢ □φ \\ I & ⊢ φ → ψ ⇒ ⊢ □φ → □ψ \\ E & ⊢ φ ↔ ψ ⇒ ⊢ □φ ↔ □ψ \\ K & ⊢ □(φ → ψ) → (□φ → □ψ) \\ C & ⊢ □φ ∧ □ψ) → □(φ ∧ ψ) \\ C_{c} & ⊢ □(φ ∧ ψ) → (□φ ∧ □ψ) \end{aligned}

Modulo some usual propositional laws,^{3} these principles are not independent, but related by NK ⇒ I ⇒ E, C_{c}; EC_{c} ⇒ I; IK ⇒ C and IC ⇒ K. I.e., the following equivalences hold: I ≡ EC_{c}, IK ≡ IC, and NK ≡ NIC. Now with R replacing □, omniscience of types N, I, and C_{c} is avoided, as can be easily demonstrated by using standard possible worlds models.^{4} Some forms of omniscience remain: E (closure under equivalence, a weak principle), K and C still hold for this particular construal. The latter are, generally, less desirable for notions of conscious belief, but may be acceptable for exclusive belief. For example, real belief seems to satisfy C: If one really believes that John will come and one really believes Mary will come, then certainly one really believes that John and Mary will come. What may be surprising, is that the converse need not hold for this sense of belief. However, it is related to the fact that it is consistent to say that one believes that John and Mary will come, when one merely believes that John will come, but in fact knows that Mary will come.

1I want to thank Heinrich Wansing for kindly allowing reference to his paper [14], which induced this analysis of the ‘pragmatically enforced’ sense of belief.

2Although I do wish to enter a subtle philosophical debate whether even direct perception involves voluntary belief acquisition, I am inclined to think that in such cases, where the evidence is indeed overwhelming, we are forced to assuming such perceptions. So, the observed parallelism with [2, 3, 14] does not imply that I share the voluntarist position, for that matter.

3Such as (φ ∧ (φ → ψ)) → ψ and φ → (ψ → (φ ∧ ψ)), which at least hold in classical propositional logic.

4The semantics of these modal operators does not require a temporal dimension, as is usual in the Action Logic accounts.

3 Generalized quantifiers – 15 years later

Finally, I want to return to the subject which was the starting point of my scientific career. In the early eighties I got engaged into Generalized Quantifier Theory (GQT). As a student I was able to contribute to this by then (at least in linguistic circles) new subject and I think it is fair to say I was part of what is now known as ‘the Semantic Wave’, rather than just surfing on it. Despite a number of publications the resulting master thesis [7] unfortunately did not get a proper follow-up in the form of a scholarship or regular Ph.D. position.^{5} One part actually was never really published, and for good reasons. It dealt with the application of GQT to a notorious issue in natural language semantics: the analysis of possessive genitives in English. Examples of prenominal possessive genitives occur in John’s car, a boy scout’s manual, the girl’s spectacles, some students’ books, and most journals’ editors.

The semantic analysis of such constructions requires an underlying possessive relation P on the set of individuals E. For any a ∈ E, A ⊆ E let P [A] = {y | ∃x ∈ A : xP y} and P [a] = {y | aP y}. Then for quantified NPs with a prenominal genitive, i.e. constructions of the form

QA’ s B C

the following interpretations are suggested in resp. [16] and [7]:^{6}

(I) QA{a | P [a] ∩ B ⊆ C} (Westerståhl)
(II) Q(P [A] ∩ B)C  (Thijsse)

Who is right? Well, in some sense both are right, and in some sense neither are. Let me explain. (I) amounts the definite construal by which a boy scout’s manual can be paraphrased as the manual of a boy scout, (II) to what might be called the adjectival construal, in which there is a manual which is typically or originally meant for boy scouts. Now in fact both readings may occur (the ambiguity was observed by e.g. Erich Woisetschläger), although numerical restrictions, imposed by the syntactic numbers of the determiner and the nouns, may exclude certain readings. In general, the preferred reading is the definite one, whereas the adjectival reading is dominant in fixed, more or less idiomatic phrases (‘a bird’s eye view’, ‘not to have a dog’s chance’). So both proposals are correct, in some sense.

However, (II) was intended to cover the interpretation in which Q has narrow scope (i.e. in which ’s has wide scope), so I was definitely wrong there.^{7} Apart from the fact that Westerståhl does not notice the ambiguity, (I) also seems incorrect in certain cases. An example of this is the determiner no. For No student’s books were stolen the analysis (I) would produce the incorrect reading (a) ‘there is no student of whom all books were stolen’ (¬∃∀) whereas (b) ‘there is no student of whom some books were stolen’ (¬∃∃) seems intended.

5For this happy event, I do no want to enter into the reasons for the unjust rejection of a corresponding Ph.D. proposal, but if I once start writing my memoirs, I will surely include a detailed account of this period.

6Suppressing denotational brackets.

7As was observed by Henk Verkuyl and others during my talk on this subject in Amsterdam, 1984.

There are several ways to remedy this. One would be to impose an ad hoc constraint which excludes the definite reading in such cases, leaving the adjectival interpretation which correctly produces the desired reading. An elegant alternative is given in [1], where an independently motivated presupposition is added to (a), producing the desired (b) reading. Needless to say, many problems, such as the effect of numerical conditions and contextual restrictions, remain to be solved.

April 1999, CSLI, Stanford University

References

[1] Ilke D. van den Ende, A Semantic Analysis of Prenominal Possessive Genitives in English, Master thesis TKI, Tilburg University, 1998

[2] John F. Horty & Nuel Belnap, ‘The Deliberative stit: a Study of Action, Omission, Ability and Obligation’, Journal of Philosophical Logic 24, (583– 644), 1995

[3] Franz von Kutschera, ‘Bewirken’, Erkenntnis 24, (253–281), 1986

[4] Sergej V. Jablonskij, ‘Functional constructions in a k-valued logic’ [in Russian], Trudy Mat. Inst. Steklov 51, (5–142). Mathematical Reviews 21, # 3331, 1958

[5] Ivo Rosenberg, Completeness properties of multiple–valued logic algebras’, D. Rine (ed.) Computer Science and Multiple–valued Logic, pp. 144–186, North–Holland, Amsterdam etc., 1977

[6] Ágnes Szendrei, Clones in universal algebra, Séminaire de mathématiques supérieure/Séminaire de scientifique OTAN, vol. 99, Université de Montréal, 1986

[7] Elias Thijsse, Laws of Language, Master thesis, Rijksuniversiteit Groningen, 1983

[8] Elias Thijsse, Partial Logic and Knowledge Representation, dissertation Tilburg University, Eburon Publishers, Delft, 1992

[9] Elias Thijsse, ‘Logics of Consciousness Explained and Compared: Partial Approaches to Actual Belief’. Logique et Analyse, vol. 133-134, (221–250), 1991 (submitted and appeared in 1994).

[10] Elias Thijsse, ‘Combining partial and classical semantics. A hybrid approach to belief and awareness’ in: Partiality, Modality, Nonmonotonicity, P.Doherty (ed.), Studies in Logic, Language and Information, CSLI Publications, Stanford (USA), 1996.

[11] Elias Thijsse, ‘Expressibility of Partial Truth Functions: results on 3- and 4-valued clones’, Logic and Combinatorics of Finite Structures (LCFS’95), Leipzig, 1999 [12] Elias Thijsse, ‘The doxastic-epistemic force of declarative utterances’, in

W.Black & H.Bunt (eds.), Abduction, Belief and Context: Studies in Computational Pragmatics, University College Press, to appear

[13] Heinrich Wansing, ‘A general possible worlds framework for reasoning about knowledge and belief’, Studia Logica 49, (523–539), 1990

[14] Heinrich Wansing, A Reduction of Doxastic Logic to Action Logic, 18 pp., submitted for publication, Dresden University of Technology, 1999

[15] Wolfgang Wechler, Universal Algebra for Computer Scientists, Springer-Verlag, Berlin, 1992

[16] Dag Westerståhl, ‘Quantifiers in Formal and Natural Languages’, in Gabbay and Günthner (eds.) Handbook of Philosophical Logic, vol. 4, Reidel, Dordrecht, 1989

[17] Ming Xu, ‘Axioms for Deliberative stit’, Journal of Philosophical Logic 27, (505–552), 1998