Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies

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 arti...

Descripción completa

Detalles Bibliográficos
Autores principales:	Figueira, Santiago Daniel, Gorín, Daniel Alejandro
Publicado:	2014
Materias:	Expressive power Flattening operator Imperfect information logic Independence friendly logic Second order logic Computer networks Systems science Imperfect information Second-order logic Formal logic
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v80_n6_p1102_Figueira http://hdl.handle.net/20.500.12110/paper_00220000_v80_n6_p1102_Figueira
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_00220000_v80_n6_p1102_Figueira
record_format	dspace
spelling	paper:paper_00220000_v80_n6_p1102_Figueira2023-06-08T14:45:03Z Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies Figueira, Santiago Daniel Gorín, Daniel Alejandro 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 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. Fil:Figueira, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Gorín, D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2014 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v80_n6_p1102_Figueira http://hdl.handle.net/20.500.12110/paper_00220000_v80_n6_p1102_Figueira
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	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
spellingShingle	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 Figueira, Santiago Daniel Gorín, Daniel Alejandro Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies
topic_facet	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
description	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.
author	Figueira, Santiago Daniel Gorín, Daniel Alejandro
author_facet	Figueira, Santiago Daniel Gorín, Daniel Alejandro
author_sort	Figueira, Santiago Daniel
title	Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies
title_short	Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies
title_full	Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies
title_fullStr	Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies
title_full_unstemmed	Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies
title_sort	independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies
publishDate	2014
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v80_n6_p1102_Figueira http://hdl.handle.net/20.500.12110/paper_00220000_v80_n6_p1102_Figueira
work_keys_str_mv	AT figueirasantiagodaniel independencefriendlylogicwithclassicalnegationviaflatteningisasecondorderlogicwithweakdependencies AT gorindanielalejandro independencefriendlylogicwithclassicalnegationviaflatteningisasecondorderlogicwithweakdependencies
_version_	1768543880597209088

Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies

Ejemplares similares