Independence-friendly logic
Encyclopedia
Independence-friendly logic (IF logic), proposed by Jaakko Hintikka
and Gabriel Sandu, aims at being a more natural and intuitive alternative to classical first-order logic
(FOL). IF logic is characterized by branching quantifier
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.
fails in the latter. Wilfrid Hodges
(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-theoretic
semantics for FOL treats a FOL formula as a game of perfect information
, 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.
". 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).
Jaakko Hintikka
Kaarlo 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 logic
First-order logic
First-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 quantifier
Branching quantifier
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...
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 compositionalityPrinciple of compositionality
In 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 Hodges
Wilfrid Hodges
Wilfrid 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-theoretic
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...
semantics for FOL treats a FOL formula as a game of perfect information
Perfect information
In 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 logicSecond-order logic
In 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 SemanticsGame semanticsGame 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 QuantifiersBranching 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...
- Dependence Logic