Logic Journal of IGPL

Logic Journal of IGPL Advance Access originally published online on January 23, 2009
Logic Journal of IGPL 2009 17(1):91-129; doi:10.1093/jigpal/jzn030

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by Caicedo, X. Articles by Janssen, T. M.V. Search for Related Content Social Bookmarking          What's this?

© The Author 2009. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Equivalence and quantifier rules for logic with imperfect information

Xavier Caicedo^*, Francien Dechesne and Theo M.V. Janssen

*Dept. of math., Univ. de los Andes, Bogotá, Colombia, xcaicedo{at}uniandes.edu.co
Dept. math. & comp.sc., Techn. Univ, Eindhoven, the Netherlands, f.dechesne{at}tue.nl
ILLC, Universiteit van Amsterdam, Amsterdam, the Netherlands, t.m.v.janssen{at}uva.nl

In this paper, we present a prenex form theorem for a version of Independence Friendly logic, a logic with imperfect information. Lifting classical results to such logics turns out not to be straightforward, because independence conditions make the formulas sensitive to signalling phenomena. In particular, nested quantification over the same variable is shown to cause problems. For instance, renaming of bound variables may change the interpretations of a formula, there are only restricted quantifier extraction theorems, and slashed connectives cannot be so easily removed. Thus we correct some claims from Hintikka [8], Caicedo & Krynicki [3] and Hodges [11]. We refine definitions, in particular the notion of equivalence, and sharpen preconditions, allowing us to restore (restricted versions of) those claims, including the prenex form theorem of Caicedo & Krynicki [3], and, as a side result, we obtain an application to Skolem forms of classical formulas. It is a known fact that a complete calculus for IF-logic is impossible, but with our results we establish several quantifier rules that form a partial calculus of equivalence for a general version of IF-logic reflecting general properties of information flow in games.

Received for publication 19 January 2007.

References

[1]  van Benthem J. ‘Logic games are complete for game logics’, Studia Logica (2003) 75:183–203. Special issue on Game Logic and Game Algebra (M. Pauly and R. Parikh eds).[CrossRef]

[2]  van Benthem J. The epistemic logic of IF games. Auxier E, Hahn LE, eds. (2006) 481–513R. ‘The Philosophy of Jaakko Hintikka’, Vol. XXX of Library of living philosophers, Open Court Publishers, chapter 13.

[3]  Caicedo X, Krynicki M. Quantifiers for reasoning with imperfect information and -logic. In: ‘Contemporary Mathematics’.—Carnielli WA, Ottaviano IML, eds. (1999) 235. American Mathematical Society. 17–31.

[4]  Dechesne F. Game, Set, Maths: formal investigations into logic with imperfect information. (2005) Tilburg University. PhD thesis.

[5]  Dechesne F. ‘Thompson transformations for IF-logic?’, Synthese (2006) 149:285–309.[CrossRef]

[6]  Henkin L. Some remarks on infinitely long formulas. In: ‘Infinitistic methods’. (1961) Pergamon Press. 167–183.

[7]  Hilbert D, Ackermann W. Grundzüuge der theoretischen Logik. (1959) fourth edn. Springer Verlag.

[8]  Hintikka J. The Principles of Mathematics Revisited. (1996) Cambridge University Press.

[9]  Hintikka J, Saarinen E. (1979) Reidel. Game Theoretical Semantics, Vol. 5 of Synthese language library.

[10]  Hintikka J, Sandu G. Game-theoretical semantics. In: ‘Handbook of Logic & Language’.—van Benthem J, ter Meulen A, eds. (1997) Elsevier Science. 361–410.

[11]  Hodges W. ‘Compositional semantics for a language of imperfect information’, Logic journal of the IGPL (1997a) 5(4):539–563.[CrossRef]

[12]  Hodges W. Some strange quantifiers. In: ‘Structures in Logic and Computer Science’.—Mycielski J, et al, eds. (1997b) number 1261 in ‘Lecture notes in computer science’, Springer, Berlin, pp. 51–65.

[13]  Janssen TMV, Dechesne F. Signalling in IF games: a tricky business. In: Logic, epistemology, and the unity of science.—van Benthem J, Heinzmann G, Rebuschi M, Visser H, eds. (2006) 3. Dordrecht, the Netherlands: Springer. 221–241. ‘The age of alternative logics. Assessing philosophy of logic and mathematics today’.[Web of Science]

[14]  Kuhn HW, ed. Classics in Game Theory. (1997) Princeton University Press.

[15]  Nurmi V. On consequence in a fragment of IF-logic. In: ‘Proceedings of the Tenth ESSLI student session’.—Gervais J, ed. (2005) 222–233. ESSLI website.

[16]  Thompson FB. Equivalence of games in extensive form. (1952) Technical Report RM-759, The Rand Corporation. 1952. Reprinted in [14].

[17]  Väänänen J. ‘On the semantics of informational independence’, Logic Journal of the IGPL (2002) 10(3):339–352.[CrossRef][Web of Science]

CiteULike    Connotea    Del.icio.us    What's this?

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by Caicedo, X. Articles by Janssen, T. M.V. Search for Related Content Social Bookmarking          What's this?