Independence-Friendly Logic Without Henkin Quantification

We analyze from a global point of view the expressive resources of \(\mathrm {IF}\) logic that do not stem from Henkin (partially-ordered) quantification. When one restricts attention to regular \(\mathrm {IF}\) sentences, this amounts to the study of the fragment of \(\mathrm {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 (\(\mathrm {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 \(\mathrm {ESO}\) expressive power can be achieved using neither Henkin nor signalling patterns.