Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-26T18:51:27.908Z Has data issue: false hasContentIssue false
  • English
  • Français

Some combinatorics of imperfect information

Published online by Cambridge University Press:  12 March 2014

Peter Cameron  and
Wilfrid Hodges
Peter Cameron
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, Mile End Road London El 4NS, England, E-mail: [email protected]
Wilfrid Hodges
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London El 4NS, England, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

We can use the compositional semantics of Hodges [9] to show that any compositional semantics for logics of imperfect information must obey certain constraints on the number of semantically inequivalent formulas. As a corollary, there is no compositional semantics for the ‘independence-friendly’ logic of Hintikka and Sandu (henceforth IF) in which the interpretation in a structure A of each 1 -ary formula is a subset of the domain of A (Corollary 6.2 below proves this and more). After a fashion, this rescues a claim of Hintikka and provides the proof which he lacked:

… there is no realistic hope of formulating compositional truth-conditions for [sentences of IF], even though I have not given a strict impossibility proof to that effect.

(Hintikka [6] page 110ff.) One curious spinoff is that there is a structure of cardinality 6 on which the logic of Hintikka and Sandu gives nearly eight million inequivalent formulas in one free variable (which is more than the population of Finland).

We thank the referee for a sensible change of notation, and Joel Berman and Stan Burris for bringing us up to date with the computation of Dedekind's function (see section 4). Our own calculations, utterly trivial by comparison, were done with Maple V.

The paper Hodges [9] (cf. [10]) gave a compositional semantics for a language with some devices of imperfect information. The language was complicated, because it allowed imperfect information both at quantifiers and at conjunctions and disjunctions.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 66 , Issue 2 , June 2001 , pp. 673 - 684
Copyright
Copyright © Association for Symbolic Logic 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Berman, J., Algebraic properties of k-valued logics, Proceedings of the Tenth International Symposium on Multiple- Valued Logic (Evanston, Illinois), 1980.Google Scholar
[2]Berman, J. and Köhler, P., Cardinalities of finite distributive lattices, Mitteilungen aus dem mathem. Seminar Glessen, no. 121, 1976, pp. 103–124.Google Scholar
[3]Birkhoff, G., Lattice theory, American Mathematical Society, 1961.Google Scholar
[4]Blumer, A.et al., Learnability and the Vapnik-Chervonenkis dimension, Journal of the Association for Computing Machinery, vol. 36 (1989), pp. 929–965.CrossRefGoogle Scholar
[5]Cameron, P. J., Combinatorics, Cambridge University Press, 1994.Google Scholar
[6]Hintikka, J., The principles of mathematics revisited. Cambridge University Press, Cambridge, 1996.CrossRefGoogle Scholar
[7]Hintikka, J. and Sandu, G., Game-theoretic semantics, Handbook of logic and language (van Benthem, J.et al., editors), Elsevier, 1996, pp. 361–410.Google Scholar
[8]Hodges, W., Formal features of compositionality., Journal of Logic, Language and Information, to appear.Google Scholar
[9]Hodges, W., Compositional semantics for a language of imperfect information, Logic Journal of the IGPL, vol. 5 (1997), pp. 539–563.CrossRefGoogle Scholar
[10]Hodges, W., Some strange quantifiers. Structures in logic and computer science, Lecture Notes in Computer Science (Mycielski, J.et al., editors), no. 1261, Springer, Berlin, 1997, pp. 51–65.Google Scholar
[11]Kleitman, D., On Dedekind's problem: the number of monotone boolean functions, Proceedings of the American Mathematical Society, vol. 21, 1969, pp. 677–682.Google Scholar
[12]Lunnon, F., The IU function: the size of a free distributive lattice, Combinatorial mathematics and its applications (Welsh, D. J. A., editor), Academic Press, London, 1971, pp. 173–181.Google Scholar
[13]Wiedemann, D., A computation of the eighth Dedekind number, Order, vol. 8 (1991), pp. 5–6.CrossRefGoogle Scholar