Independence-friendly logic (
IF logic), proposed by
Jaakko HintikkaKaarlo Jaakko Juhani Hintikka is a Finnish philosopher and logician.Hintikka was born in Vantaa. After teaching for a number of years at Florida State University, Stanford, University of Helsinki, and the Academy of Finland, he is currently Professor of Philosophy at Boston University...
and Gabriel Sandu, aims at being a more natural and intuitive alternative to classical
first-order logicFirst-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
(FOL). IF logic is characterized by
branching quantifierIn logic a branching quantifier, also called a Henkin quantifier, finite partially ordered quantifier or even nonlinear quantifier, is a partial ordering\langle Qx_1\dots Qx_n\rangle...
s. It is more expressive than FOL because it allows one to express independence relations between quantified variables.
For example, the formula ∀a ∀b ∃c/b ∃d/a φ(a,b,c,d) ("x/y" should be read as "x independent of y") cannot be expressed in FOL. This is because c depends
only on a and d depends
only on b. First-order logic cannot express these independences by any linear reordering of the quantifiers.
Semantics
Since Tarskian semantics does not allow indeterminate truth values, it cannot be used for IF logic. Hintikka further argues that the standard semantics of FOL cannot accommodate IF logic because the
principle of compositionalityIn mathematics, semantics, and philosophy of language, the Principle of Compositionality is the principle that the meaning of a complex expression is determined by the meanings of its constituent expressions and the rules used to combine them. This principle is also called Frege's Principle,...
fails in the latter.
Wilfrid HodgesWilfrid Augustine Hodges is a British mathematician, known for his work in model theory. He was Professor of Mathematics at Queen Mary, University of London from 1987 to 2006, and is the author of numerous books on logic....
(1997) gives a compositional semantics for it in part by having the truth clauses for IF formulas quantify over sets of assignments rather than just assignments (as the usual truth clauses do).
The
game-theoreticGame semantics is an approach to formal semantics that grounds the concepts of truth or validity on game-theoretic concepts, such as the existence of a winning strategy for a player, somewhat resembling Socratic dialogues or medieval theory of Obligationes. In the late 1950s Paul Lorenzen was the...
semantics for FOL treats a FOL formula as a game of
perfect informationIn game theory, perfect information describes the situation when a player has available the same information to determine all of the possible games as would be available at the end of the game....
, whose players are Verifier and Falsifier. The same holds for the standard semantics of IF logic, except that the games are of imperfect information.
Independence relations between the quantified variables are modelled in the game tree as indistinguishability relations between game states with respect to a certain player. In other words, the players are not certain where they are in the tree (this ignorance simulates simultaneous play). The formula is evaluated as true if there Verifier has a winning strategy, false if Falsifier has a winning strategy, and indeterminate otherwise.
A winning strategy is informally defined as a strategy that is guaranteed to win the game, regardless of how the other players play. It can be given a completely rigorous, formal definition.
Critique
Feferman (2006) cites a theorem of Väänänen which states that "the general question of validity of IF sentences is recursively isomorphic to that for validity in full
second-order logicIn logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory....
". He argues (contra Hintikka) that while satisfiability might be a first-order matter, the question of whether there is a winning strategy for Verifier over all structures in general "lands us squarely in
full second order logic" (emphasis Feferman's).
See also
- Game Semantics
Game semantics is an approach to formal semantics that grounds the concepts of truth or validity on game-theoretic concepts, such as the existence of a winning strategy for a player, somewhat resembling Socratic dialogues or medieval theory of Obligationes. In the late 1950s Paul Lorenzen was the...
- Branching Quantifiers
In logic a branching quantifier, also called a Henkin quantifier, finite partially ordered quantifier or even nonlinear quantifier, is a partial ordering\langle Qx_1\dots Qx_n\rangle...
- Dependence Logic
External links