Logic Journal of IGPL Advance Access originally published online on August 4, 2009
Logic Journal of IGPL 2009 17(6):719-754; doi:10.1093/jigpal/jzp029
Independence-friendly cylindric set algebras
IHPST (Paris 1/CNRS/ENS), 13 rue du Four, 75006 Paris, France.
E-mail: allen.l.mann{at}gmail.com
Independence-friendly logic (IF logic) is a conservative extension of first-order logic that has the same expressive power as existential second-order logic. We attempt to algebraize IF logic in the same spirit as cylindric algebra.
We define independence-friendly cylindric set algebras (IF algebras) and investigate to what extent they satisfy the axioms of cylindric algebra. We ask whether the equational theory of IF algebras is finitely axiomatizable, and prove two partial results. First, every IF algebra over a structure is an expansion of a Kleene algebra. Moreover, the class of such Kleene algebras generates the variety of all Kleene algebras. Second, every one-dimensional IF algebra over a structure is an expansion of a monadic Kleene algebra. However, the class of such monadic Kleene algebras does not generate the variety of all monadic Kleene algebras.1
Key Words: independence-friendly logic • cylindric algebra • De Morgan algebra • monadic De Morgan algebra
Received for publication 21 October 2007.
1Revisions to the present paper were supported by the European Science Foundation collaborative research project Logic for Interaction (LINT).
References
-
[1] Balbes Raymond, Dwinger Philip. Distributive Lattices (1974) University of Missouri Press.
[2] Caicedo Xavier, Dechesne Francien, Theo MV. Janssen. Equivalence and quantifier rules for logic with imperfect information. To appear in. Logic Journal of the IGPL.
[3] Caicedo Xavier, Krynicki Micha. Quantifiers for reasoning with imperfect information and 
-logic. Carnielli Walter A, D’Ottaviano Itala M, eds. (1999) American Mathematical Society. Advances in Contemporary Logic and Computer Science: Proceedings of the Eleveth Brazilian Conference on Mathematical Logic, May 6-10, 1996, volume 235 of Contemporary Mathematics.
[4] Cameron Peter, Hodges Wilfrid. Some combinatorics of imperfect information. Journal of Symbolic Logic (Jun 2001) 66(2):673–684.[CrossRef][Web of Science]
[5] Cignoli Roberto. Quantifiers on distributive lattices. Discrete Mathematics (Dec 1991) 96(3):183–197.[CrossRef][Web of Science]
[6] Dechesne Francien. Game, Set, Maths: Formal investigations into logic with imperfect information (2005) Universiteit van Tilburg. PhD thesis.
[7] Enderton Herbert B. Finite partially-ordered quantifiers. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik (1970) 16(5):393–397.[CrossRef][Web of Science]
[8] Halmos Paul R. Algebraic Logic (1962) New York: Chelsea.
[9] Henkin Leon. Some remarks on infinitely long formulas. (1961) Pergamon Press. 167–183. In Infinitistic Methods: Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 2–9 September 1959.
[10] Henkin Leon, Donald Monk J, Tarski Alfred. Cylindric Algebras: Part I (1971) North-Holland. volume 64 of Studies in Logic and the Foundations of Mathematics.
[11] Henkin Leon, Donald Monk J, Tarski Alfred. Cylindric Algebras: Part II (1985) North-Holland. volume 115 of Studies in Logic and the Foundations of Mathematics.
[12] Hintikka Jaakko. The Principles of Mathematics Revisited (1996) Cambridge University Press.
[13] Hintikka Jaakko, Sandu Gabriel. Informational independence as a semantical phenomenon. In: Logic, Methodology and Philosophy of Science VIII—Fenstad Jens Erik, et al, eds. (1989) North-Holland. 571–589. volume 126 of Studies in Logic and the Foundations of Mathematics.
[14] Hintikka Jaakko, Sandu Gabriel. Game-theoretical semantics. In: Handbook of Logic & Language—van Bethem Johan, ter Meulen Alice, eds. (1997) Elsevier Science. 361–410. chapter 6.
[15] Hodges Wilfrid. Compositional semantics for a language of imperfect information. Logic Journal of the IGPL (1997) 5(4):539–563.[CrossRef]
[16] Hodges Wilfrid. Some strange quantifiers. In: Structures in Logic and Computer Science: A Selection of Essays in Honor of A. Ehrenfeucht—Mycielski Jan, Rozenberg Grzegorz, Salomaa Arto, eds. (1997) Springer. 51–65. number 1261 in Lecture Notes in Computer Science.
[17] Jónsson Bjarni. Algebras whose congruence lattices are distributive. Mathematica Scandinavica (1967) 21:110–121.[Web of Science]
[18] Kalman JA. Lattices with involution. Transactions of the American Mathematical Society (Mar 1958) 87(2):485–491.[CrossRef]
[19] Koppelberg Sabine. Handbook of Boolean Algebras (1989) 1. North-Holland.
[20] McKinsey JCC, Tarski Alfred. The algebra of topology. The Annals of Mathematics, 2nd Series (Jan 1944) 45(1):141–191.
[21] Donald Monk J. Nonfinitizability of classes of representable cylindric algebras. Journal of Symbolic Logic (Sep 1969) 34(3):331–343.[CrossRef][Web of Science]
[22] Petrovich Alejandro. Distributive lattices with an operator. Studia Logica (1996) 56:205–224.[CrossRef]
[23] Petrovich Alejandro. Monadic De Morgan algebras. In: Models, Algebras, and Proofs—Caicedo Xavier, Montenegro Carlos H, eds. (1999) New York: Marcel Decker. 315–333. volume 203 of Lecture Notes in Pure and Applied Mathematics.
[24] Väänänen Jouko. Dependence Logic: A New Approach to Independence Friendly Logic (2007) London Mathematical Society Student Texts. Cambridge University Press.
[25] John Walkoe Wilbur Jr. Finite partially-ordered quantification. Journal of Symbolic Logic (Dec 1970) 35(4):535–555.[CrossRef][Web of Science]
CiteULike 
Connotea 
Del.icio.us What's this?
| ||||||||||||||||||||||||||||||||||||||||||||||