Independence-Friendly Logic

0.1 Introduction A series of recent papers of the Finnish logicians Jaakko Hintikka and Gabriel Sandu - and, in particular, Hintikka’s 1996 treatise The Principles of Mathe- matics Revisited - revived the interest in a minor generalization of first-order logic, the logic of branching quantifiers. Introduced in the early sixties by Leon Henkin ([6]), the logic of branching quantifiers was shown not to be recursively axiomatizable; it turned out to be equivalent, from a semantical viewpoint, to a fragment of second-order logic known as Σ11 logic; and it was even employed to prove an old conjecture on first-order logic ([20]). The intuition behind the branching quantifiers is that quantifiers establish dependences among variables; whenever an existential quantifier occurs within the scope of a universal quan- tifier, the existentially quantified variable depends on the universally quantified variable; the branching quantifiers permit any possible pattern of dependence, while first-order syntax allows only patterns with a peculiar structure. Hintikka and Sandu introduced a new, linear notation for branching quantifi- cation, featuring tokens like ∃y/∀x1, . . . ,∀xn (y is specified to be independent of x1, . . . , xn); they called the logic that bears this syntax Independence-Friendly (IF) logic. They also provided an alternative semantics based on game theory; and they investigated the role of negation. Allowing negations in front of IF sentences leads out of Σ11 logic; the new logic thus obtained was called extended IF logic. But, above all, Jaakko Hintikka tried to to persuade mathematicians and philosophers of mathematics that IF logic had a central role in the foundations of mathematics; that it was, in a sense, the true first-order logic, freed from unnatural restrictions. It was hard to judge of the correctness of his claims, because of two reasons at least. The first is the style adopted in The Princi- ples of Mathematics Revisited : lots of mathematical results are quoted without demonstrations, and the argumentations seem to be chosen and ordered so as to convince rather than clarify. Other difficulties spring from IF logic itself. The law of the excluded middle turned out to fail in IF logic; that is, there are IF sentences that are neither true nor false. As a consequence, “false” and “non-true”, “true” and “non- false” become distinct concepts; the crucial semantic notions of equivalence and logical implication have no more a univocal, “canonical” definition. On such unusual grounds, it is an hard matter to decide whether IF logic really resembles first-order logic or not, and whether results concerning IF logic have the same philosophical import than they would have if they were proved for more regular logics. The purpose of the present work is to provide the reader with some of the instruments that are needed to understand the debates around IF logic. The presentation is more formal than Hintikka’s; proofs are often provided, except for when the results are already well-known from more traditional areas of logic. Hintikka’s arguments in favor of IF logic are presented and criticized. But they come in the end, in the third and last chapter, when the technical and problematic aspects of IF logic have already been discussed. It is proved that 3