Article ID Journal Published Year Pages File Type
430237 Journal of Computer and System Sciences 2014 17 Pages PDF
Abstract

•We study Independence Friendly logic extended with Hodge's flattening operator.•We prove that this logic corresponds to a weak syntactic fragment of second order.•We prove that this logic is equivalent to the logic of Henkin quantifiers.•We argue that Hodge's notion of negation is adequate.

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(↓)SL(↓), IF-logic extended with Hodges' flattening operator ↓, which allows to define a classical negation. SL(↓)SL(↓) contains Extended IF-logic and hence it is at least as expressive as the Boolean closure of Σ11. We prove that SL(↓)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(↓)SL(↓) is equivalent to the logic of Henkin quantifiers, which shows, we argue, that Hodges' notion of negation is adequate.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,