zbMATH — the first resource for mathematics

Classical negation and game-theoretical semantics. (English) Zbl 1342.03030
Summary: Typical applications of Hintikka’s game-theoretical semantics (GTS) give rise to semantic attributes – truth, falsity – expressible in the \(\Sigma^1_1\)-fragment of second-order logic. Actually a much more general notion of semantic attribute is motivated by strategic considerations. When identifying such a generalization, the notion of classical negation plays a crucial role. We study two languages, \(L_1\) and \(L_2\), in both of which two negation signs are available: \(\rightharpoondown\) and \(\sim\). The latter is the usual GTS negation which transposes the players’ roles, while the former will be interpreted via the notion of mode. Logic \(L_1\) extends independence-friendly (IF) logic; \(\rightharpoondown\) behaves as classical negation in \(L_1\). Logic \(L_2\) extends \(L_1\), and it is shown to capture the \(\Sigma_1^2\)-fragment of third-order logic. Consequently the classical negation remains inexpressible in \(L_2\).

03B60 Other nonclassical logic
03C80 Logic with extra quantifiers and operators
03B15 Higher-order logic; type theory (MSC2010)
Full Text: DOI Euclid
[1] Burgess, J. P., “A remark on Henkin sentences and their contraries,” Notre Dame Journal of Formal Logic , vol. 44 (2003), pp. 185-88. · Zbl 1071.03023 · doi:10.1305/ndjfl/1091030856
[2] Caicedo, X., F. Dechesne, and T. M. V. Janssen, “Equivalence and quantifier rules for logic with imperfect information,” Logic Journal of the IGPL , vol. 17 (2009), pp. 91-129. · Zbl 1160.03007 · doi:10.1093/jigpal/jzn030
[3] Carlson, L. and J. Hintikka, “Conditionals, generic quantifiers, and other applications of subgames” pp. 179-214 in Game-Theoretical Semantics , edited by E. Saarinen, vol. 5 of Synthese Language Library , Reidel, Dordrecht, Netherlands, 1978.
[4] Enderton, H. B., “Finite partially-ordered quantifiers,” Zeitschrift für mathematische Logik und Grundlagen der Mathematik , vol. 16 (1970), pp. 393-97. · Zbl 0193.29405 · doi:10.1002/malq.19700160802
[5] Figueira, S., D. Gorín, and R. Grimson, “On the formal semantics of IF-like logics,” Journal of Computer and System Sciences , vol. 76 (2010), pp. 333-46. · Zbl 1197.03028 · doi:10.1016/j.jcss.2009.10.006
[6] Figueira, S., D. Gorín, and R. Grimson, “On the expressive power of IF-logic with classical negation,” pp. 135-45 in Logic, Language, Information and Computation , edited by L. Beklemishev and R. de Queiroz, Springer, Berlin, 2011. · Zbl 1328.03029 · doi:10.1007/978-3-642-20920-8_16
[7] Hintikka, J., “Language-games for quantifiers” pp. 46-72 in Studies in Logical Theory , edited by N. Rescher, Basil Blackwell, Oxford, 1968.
[8] Hintikka, J., The Principles of Mathematics Revisited , with an appendix by G. Sandu, Cambridge Univ. Press, Cambridge, 1996. · Zbl 0869.03003
[9] Hintikka, J., “Negation in logic and in natural language,” Linguistics and Philosophy , vol. 25 (2002), pp. 585-600.
[10] Hintikka, J., “Truth, negation and other basic notions of logic” pp. 195-219 in The Age of Alternative Logics: Assessing Philosophy of Logic and Mathematics Today , edited by J. van Benthem, et al., Springer, Berlin, 2006.
[11] Hintikka, J., and J. Kulas, The Game of Language: Studies in Game-Theoretical Semantics and Its Applications , vol. 22 of Synthese Language Library , D. Reidel, Dordrecht, Netherlands, 1983.
[12] Hodges, W., “Compositional semantics for a language of imperfect information,” Logic Journal of the IGPL , vol. 5 (1997), pp. 539-63. · Zbl 0945.03034 · doi:10.1093/jigpal/5.4.539
[13] Hodges, W., “Some strange quantifiers,” pp. 51-65 in Structures in Logic and Computer Science , edited by J. Mycielski, G. Rozenberg, and A. Salomaa, vol. 1261 of Lecture Notes in Computer Science , Springer, Berlin, 1997. · doi:10.1007/3-540-63246-8_4
[14] Hodges, W., “Elementary predicate logic” pp. 1-129 in Handbook of Philosophical Logic, Vol. 1 , edited by D. M. Gabbay and F. Guenthner, Kluwer, Dordrecht, Netherlands, 2001. · doi:10.1007/978-94-015-9833-0_1
[15] Hodges, W., “Logics of imperfect information: Why sets of assignments?” pp. 117-33 in Interactive Logic , edited by J. van Benthem, B. Löwe, and D. Gabbay, vol. 1 of Texts in Logic and Games , Amsterdam Univ. Press, Amsterdam, 2007.
[16] Janssen, T. M. V., “Independent choices and the interpretation of IF logic: Logic and games,” Journal of Logic, Language and Information , vol. 11 (2002), pp. 367-87. · Zbl 1003.03025 · doi:10.1023/A:1015542413718
[17] Kontinen, J., and V. Nurmi, “Team logic and second-order logic,” Fundamenta Informaticae , vol. 106 (2011), pp. 259-72. · Zbl 1250.03048 · doi:10.3233/FI-2011-386
[18] Kontinen, J., and J. Väänänen, “A remark on negation in dependence logic,” Notre Dame Journal of Formal Logic , vol. 52 (2011), pp. 55-65. · Zbl 1216.03048 · doi:10.1215/00294527-2010-036
[19] Krynicki, M., “Henkin quantifiers” pp. 193-262 in Quantifiers: Logics, Models and Computation, Vol. 1 , edited by M. Krynicki, M. Mostowski, and L. Szczerba, Kluwer, Dordrecht, Netherlands, 1995.
[20] Mostowski, M., “Arithmetic with the Henkin Quantifier and its Generalizations,” pp. 1-25 in Séminaire du Laboratoire Logique, Algorithmique et Informatique Clermontois, Vol. 2 , edited by F. Gaillard and D. Richard, Institut universitaire de technologie de Clermont-Ferrand, Aubière, 1991.
[21] Väänänen, J., Dependence Logic: A New Approach to Independence Friendly Logic , vol. 70 of London Mathematical Society Student Texts , Cambridge Univ. Press, Cambridge, 2007.
[22] Walkoe, W., “Finite partially-ordered quantification,” Journal of Symbolic Logic , vol. 35 (1970), pp. 535-55. · Zbl 0219.02008 · doi:10.2307/2271440
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.