Independence-Friendly Logic Without Henkin Quantification

摘要

We analyze from a global point of view the expressive resources of IF logic that do not stem from Henkin (partially-ordered) quantification. When one restricts attention to regular IF sentences, this amounts to the study of the fragment of IF logic which is individuated by the game-theoretical property of Action Recall. We prove that the fragment of Action Recall can express all existential second-order (ESO) properties. This can be accomplished already by the prenex fragment of Action Recall, whose only second-order source of expressiveness are the so-called signalling patterns. The proof shows that a complete set of Henkin prefixes is explicitly definable in the fragment of Action Recall. In the more general case, in which also irregular IF sentences are allowed, we show that full ESO expressive power can be achieved using neither Henkin nor signalling patterns.