On the expressive power of IF-logic with classical negation

RAFAEL GRIMSON; SANTIAGO FIGUEIRA; DANIEL GORÍN

Philadelphia

Workshop; Logic, Language, Information, and Computation: 18th International Workshop, WoLLIC 2011; 2011

It is well-known that Independence Friendly (IF) logic is equivalent to existential second-order logic ($Sigma^1_1$) 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 $Delta^1_2$. In this paper we consider IF-logic extended with Hodges´ flattening operator, which allows classical negation to occur also under the scope of IF quantifiers. We show that, nevertheless, the expressive power of this logic does not go beyond $Delta^1_2$. As part of the proof, we give a prenex normal form result and introduce a non-trivial syntactic fragment of full second-order logic that we show to be contained in $Delta^1_2$.