Abstract
We analyze from a global point of view the expressive resources of \(\mathrm {IF}\) logic that do not stem from Henkin (partially-ordered) quantification. When one restricts attention to regular \(\mathrm {IF}\) sentences, this amounts to the study of the fragment of \(\mathrm {IF}\) logic which is individuated by the game-theoretical property of Action Recall. We prove that the fragment of Action Recall can express all existential second-order (\(\mathrm {ESO}\)) properties. This can be accomplished already by the prenex fragment of Action Recall, whose only second-order source of expressiveness are the so-called signalling patterns. The proof shows that a complete set of Henkin prefixes is explicitly definable in the fragment of Action Recall. In the more general case, in which also irregular IF sentences are allowed, we show that full \(\mathrm {ESO}\) expressive power can be achieved using neither Henkin nor signalling patterns.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The notion of regularity will be defined in Sect. 2.
- 2.
- 3.
This point is exemplified by the \(\mathrm {IF}\) rendition of the \(\mathrm {H}_2^1\) prefix, shown above: its “slash set” \(\{x^1_1, y_1\}\) contains an existentially quantified variable, \(y_1\).
References
Barbero, F.: On existential declarations of independence in IF logic. Rev. Symb. Log. 6, 254–280 (2013)
Barbero, F.: Complexity of syntactical tree fragments of Independence-Friendly logic. pre-print arXiv:1610.03406
Caicedo, X., Dechesne, F., Janssen, T.M.V.: Equivalence and quantifier rules for logic with imperfect information. Log. J. IGPL 17, 91–129 (2009)
Caicedo, X., Krynicki, M.: Quantifiers for reasoning with imperfect information and \(\Sigma _1^1\)-logic. In: Carnielli, W.A., D’Ottaviano, I.M.L. (eds.) Contemporary Mathematics, vol. 235, pp. 17–31. American Mathematical Society (1999)
Cameron, P., Hodges, W.: Some combinatorics of imperfect information. J. Symb. Log. 66, 673–684 (2001)
Dahlhaus, E.: Reduction to NP-complete problems by interpretations. In: Proceedings of the Symposium “Rekursive Kombinatorik” on Logic and Machines: Decision Problems and Complexity, pp. 357–365 (1983)
Enderton, H.B.: Finite partially ordered quantifiers. Math. Log. Q. 16(8), 393–397 (1970)
Grandjean, E.: First-order spectra with one variable. J. Comput. Syst. Sci. 40, 136–153 (1990)
Henkin, L.: Some remarks on infinitely long formulas. In: Infinitistic Methods. Pergamon Press, Oxford, New York (1961)
Hintikka, J., Sandu, G.: Informational independence as a semantical phenomenon. In: Fenstad, J.E., et al. (eds.) Logic, Methodology and Philosophy of Science VIII, pp. 571–589. Elsevier Science Publishers B.V, Amsterdam (1989)
Hodges, W.: Compositional semantics for a language of imperfect information. Log. J. IGPL 5, 539–563 (1997)
Hodges, W.: Some strange quantifiers. In: Mycielski, J., Rozenberg, G., Salomaa, A. (eds.) Structures in Logic and Computer Science. LNCS, vol. 1261, pp. 51–65. Springer, Heidelberg (1997). doi:10.1007/3-540-63246-8_4
Hyttinen, T., Tulenheimo, T.: Decidability of IF modal logic of perfect recall. In: Advances in Modal Logic, vol. 5 (2005)
Krynicki, M.: Hierarchies of partially ordered connectives and quantifiers. Math. Log. Q. 39, 287–294 (1993)
Mann, A.L., Sandu, G., Sevenster, M.: Independence-Friendly Logic - a Game-Theoretic Approach. London Mathematical Society Lecture Note Series, vol. 386. Cambridge University Press, Cambridge (2011)
Sevenster, M.: Branches of imperfect information: logic, games, and computation. Ph.D. thesis, ILLC, Universiteit van Amsterdam (2006)
Sevenster, M.: Dichotomy result for independence-friendly prefixes of generalized quantifiers. J. Symbol. Log. 79(04), 1224–1246 (2014)
Väänänen, J., Logic, D.: A New Approach to Independence Friendly Logic. London Mathematical Society Student Texts, vol. 70. Cambridge University Press, Cambridge (2007)
Virtema, J.: Approaches to finite variable dependence. Ph.D. thesis, University of Tampere (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer-Verlag GmbH Germany
About this paper
Cite this paper
Barbero, F., Hella, L., Rönnholm, R. (2017). Independence-Friendly Logic Without Henkin Quantification. In: Kennedy, J., de Queiroz, R. (eds) Logic, Language, Information, and Computation. WoLLIC 2017. Lecture Notes in Computer Science(), vol 10388. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-55386-2_2
Download citation
DOI: https://doi.org/10.1007/978-3-662-55386-2_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-55385-5
Online ISBN: 978-3-662-55386-2
eBook Packages: Computer ScienceComputer Science (R0)