Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

It is well-known that Independence Friendly (IF) logic is equivalent to existential second-order logic (Σ11) and, therefore, is not closed under classical negation. The Boolean closure of IF sentences, called Extended IF-logic, on the other hand, corresponds to a proper fragment of Δ21. In this article we consider SL(↓), IF-logic extended with Hodges' flattening operator ↓, which allows to define a classical negation. SL(↓) contains Extended IF-logic and hence it is at least as expressive as the Boolean closure of Σ11. We prove that SL(↓) corresponds to a weak syntactic fragment of SO which we show to be strictly contained in Δ21. The separation is derived almost trivially from the fact that Σn1 defines its own truth-predicate. We finally show that SL(↓) is equivalent to the logic of Henkin quantifiers, which shows, we argue, that Hodges' notion of negation is adequate. © 2014 Elsevier Inc.

Registro:

Documento: Artículo
Título:Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies
Autor:Figueira, S.; Gorín, D.; Grimson, R.
Filiación:Departamento de Computación, FCEyN, Universidad de Buenos Aires, Argentina
Escuela de Ciencia y Tecnología, Universidad Nacional de San Martín, Argentina
Ciudad Universitaria, Pabellon i, C1428EGA Buenos Aires, Argentina
CS Dept., Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany
Palabras clave:Expressive power; Flattening operator; Imperfect information logic; Independence friendly logic; Second order logic; Computer networks; Systems science; Expressive power; Flattening operator; Imperfect information; Independence friendly logic; Second-order logic; Formal logic
Año:2014
Volumen:80
Número:6
Página de inicio:1102
Página de fin:1118
DOI: http://dx.doi.org/10.1016/j.jcss.2014.04.004
Título revista:Journal of Computer and System Sciences
Título revista abreviado:J. Comput. Syst. Sci.
ISSN:00220000
CODEN:JCSSB
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v80_n6_p1102_Figueira

Referencias:

  • Hintikka, J., Sandu, G., Informational independence as a semantic phenomenon (1989) Logic, Methodology and Philosophy of Science, 126 VOL., pp. 571-589. , J. Fenstad, I. Frolov, R. Hilpinen, Stud. Logic Found. Math. Elsevier Amsterdam
  • Hintikka, J., (1996) The Principles of Mathematics Revisited, , Cambridge University Press
  • Hintikka, J., Sandu, G., Game-theoretical semantics (1997) Handbook of Logic and Language, pp. 415-465. , J. van Benthem, A. ter Meulen, The MIT Press (Chapter 6)
  • Enderton, H., Finite partially-ordered quantifiers (1970) Z. Math. Log. Grundl. Math., 16, pp. 393-397
  • Mostowski, M., Arithmetic with the Henkin quantifier and its generalizations (1991) Séminaire du Laboratoire Logique, Algorithmique et Informatique Clermontoise, Vol. 2, pp. 1-25. , F. Gaillard, D. Richard
  • Hodges, W., Compositional semantics for a language of imperfect information (1997) Log. J. IGPL, 5 (4), pp. 539-563
  • Hinman, P.G., (1978) Recursion Theoretic Hierarchies, , Springer Berlin
  • Kleene, S.C., Hierarchies of number-theoretic predicates (1955) Bull. Am. Math. Soc., 61, pp. 193-213
  • Figueira, S., Gorín, D., Grimson, R., On the formal semantics of IF-like logics (2009) J. Comput. Syst. Sci., 76 (5), pp. 333-346
  • Figueira, S., Gorín, D., Grimson, R., On the expressive power of IF-logic with classical negation (2011) 18th Workshop on Logic, Language, Information and Computation, 6642 VOL., pp. 135-145. , Lect. Notes Comput. Sci
  • Dechesne, F., (2005) Game, Sets, Maths: Formal Investigations into Logic with Imperfect Information, , PhD thesis Department of Philosophy, University of Tilburg The Netherlands
  • Caicedo, X., Dechesne, F., Janssen, T.M., Equivalence and quantifier rules for logic with imperfect information (2009) Log. J. IGPL, 17 (1), pp. 91-129
  • Caicedo, X., Krynicki, M., Quantifiers for reasoning with imperfect information and Σ 1 1 -logic (1999) Contemp. Math., 235, pp. 17-31
  • Janssen, T.M.V., Independent choices and the interpretation of if logic (2002) J. Log. Lang. Inf., 11 (3), pp. 367-387
  • Janssen, T.M.V., Dechesne, F., Signalling in if games: A tricky business (2006) The Age of Alternative Logics, pp. 221-241. , Springer (Chapter 15)
  • Väänänen, J.A., On the semantics of informational independence (2002) Log. J. IGPL, 10 (3), pp. 339-352
  • Krynicki, M., Mostowski, M., Henkin quantifiers (1995) Quantifiers: Logics, Models and Computation, Vol. i, pp. 193-262. , M. Krynicki, M. Mostowski, L. Szczerba, Kluwer Academic Publishers
  • Walkoe, Jr.W., Finite partially-ordered quantification (1970) J. Symb. Log., 35 (4), pp. 535-555
  • Hyttinen, T., Sandu, G., Henkin quantifiers and the definability of truth (2000) J. Philos. Log., 29 (5), pp. 507-527
  • Hartley Rogers, J., (1987) Theory of Recursive Functions and Effective Computability, , MIT Press Cambridge, MA, USA
  • Sandu, G., IF-logic and truth-definition (1998) J. Philos. Log., 27 (2), pp. 143-164
  • Morgenstern, C., On generalized quantifiers in arithmetic (1982) J. Symb. Log., 47 (1), pp. 187-190
  • Kołodziejczyk, L.A., (2002) The Expressive Power of Henkin Quantifiers with Dualization, , Master's thesis Institute of Philosophy, Warsaw University Poland
  • Väänänen, J.A., Dependence Logic: A New Approach to Independence Friendly Logic (2007) Lond. Math. Soc. Stud. Texts, 70 VOL.. , Cambridge University Press

Citas:

---------- APA ----------
Figueira, S., Gorín, D. & Grimson, R. (2014) . Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies. Journal of Computer and System Sciences, 80(6), 1102-1118.
http://dx.doi.org/10.1016/j.jcss.2014.04.004
---------- CHICAGO ----------
Figueira, S., Gorín, D., Grimson, R. "Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies" . Journal of Computer and System Sciences 80, no. 6 (2014) : 1102-1118.
http://dx.doi.org/10.1016/j.jcss.2014.04.004
---------- MLA ----------
Figueira, S., Gorín, D., Grimson, R. "Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies" . Journal of Computer and System Sciences, vol. 80, no. 6, 2014, pp. 1102-1118.
http://dx.doi.org/10.1016/j.jcss.2014.04.004
---------- VANCOUVER ----------
Figueira, S., Gorín, D., Grimson, R. Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies. J. Comput. Syst. Sci. 2014;80(6):1102-1118.
http://dx.doi.org/10.1016/j.jcss.2014.04.004