Independence-friendly logic

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Independence-friendly logic (IF logic), proposed by Jaakko Hintikka and Gabriel Sandu in 1989 ([1]), is an extension of classical first-order logic (FOL) by means of slashed quantifiers of the form and ( being a finite set of variables). The intended reading of is "there is a which is functionally independent from the variables in ". IF logic allows one to express more general patterns of dependence between variables than those which are implicit in first-order logic. This greater level of generality leads to an actual increase in expressive power; the set of IF sentences can characterize the same classes of structures as existential second-order logic (). For example, it can express branching quantifier sentences, such as the formula which expresses infinity in the empty signature; this cannot be done in FOL. Therefore, first-order logic cannot, in general, express this pattern of dependency, in which depends only on and , and depends only on and . IF logic is more general than branching quantifiers, for example in that it can express dependencies that are not transitive, such as in the quantifier prefix ( depends on , and depends on , but does not depend on ).

The introduction of IF logic was partly motivated by the attempt of extending the game-theoretical semantics of first-order logic to games of imperfect information. Indeed, a semantics for IF sentences can be given in terms of these kinds of games (or, alternatively, by means of a translation procedure to existential second-order logic). A semantics for open formulas cannot be given in the form of a Tarskian semantics ([2]); an adequate semantics must specify what it means for a formula to be satisfied by a set of assignments of common variable domain (a team) rather than satisfaction by a single assignment. Such a team semantics was developed by Hodges ([3]).

IF logic is translation equivalent, at the level of sentences, with a number of other logical systems based on team semantics, such as dependence logic, dependence-friendly logic, exclusion logic and independence logic; with the exception of the latter, IF logic is known to be equiexpressive to these logics also at the level of open formulas. However, IF logic differs from all the above-mentioned systems in that it lacks locality (the meaning of an open formula cannot be described just in terms of the free variables of the formula; it is instead dependent on the context in which the formula occurs).

IF logic shares a number of metalogical properties with first-order logic, but there are some differences, including lack of closure under (classical, contradictory) negation and higher complexity for deciding the validity of formulas. Extended IF logic addresses the closure problem, but its game-theoretical semantics is more complicated, and such logic corresponds to a larger fragment of second-order logic, a proper subset of ([4]).

Hintikka has argued (e.g. in the book [5]) that IF and extended IF logic should be used as a basis for the foundations of mathematics; this proposal has been met in some cases with skepticism (see e.g.[6]).

Syntax[edit]

A number of slightly different presentations of IF logic have appeared in the literature; here we follow.[7]

Terms and atomic formulas[edit]

Terms and atomic formulas are defined exactly as in first-order logic with equality.

IF formulas[edit]

For a fixed signature σ, formulas of IF logic are defined as follows:

  1. Any atomic formula is an IF formula.
  2. If is an IF formula, then is an IF formula.
  3. If and are IF formulas, then and are IF formulas.
  4. If is a formula, is a variable, and is a finite set of variables, then and are also IF formulas.

Free variables[edit]

The set of the free variables of an IF formula is defined inductively as follows:

  1. If is an atomic formula, then is the set of all variables occurring in it.
  2. ;
  3. ;
  4. .

The last clause is the only one that differs from the clauses for first-order logic, the difference being that also the variables in the slash set are counted as free variables.

IF Sentences[edit]

An IF formula such that is an IF sentence.

Semantics[edit]

Three main approaches have been proposed for the definition of the semantics of IF logic. The first two, based respectively on games of imperfect information and on Skolemization, are mainly used in the definition of IF sentences only. The former generalizes a similar approach, for first-order logic, which was based instead on games of perfect information. The third approach, team semantics, is a compositional semantics in the spirit of Tarskian semantics. However, this semantics does not define what it means for a formula to be satisfied by an assignment (rather, by a set of assignments). The first two approaches were developed in earlier publications on if logic ([8][9]); the third one by Hodges in 1997 ([10][11]).

In this section, we differentiate the three approaches by writing distinct pedices, as in . Since the three approaches are fundamentally equivalent, only the symbol will be used in the rest of the article.

Game-Theoretical Semantics[edit]

Game-Theoretical Semantics assigns truth values to IF sentences according to the properties of some 2-player games of imperfect information. For ease of presentation, it is convenient to associate games not only to sentences, but also to formulas. More precisely, one defines games for each triple formed by an IF formula is an IF formula, a structure , and an assignment .

Players[edit]

The semantic game has two players, called Eloise (or Verifier) and Abelard (or Falsifier).

Game rules[edit]

The allowed moves in the semantic game are determined by the synctactical structure of the formula under consideration. For simplicity, we first assume that is in negation normal form, with negations symbols occurring only in front of atomic subformulas.

  1. If is a literal, the game ends, and, if is true in (in the first-order sense), then Eloise wins; otherwise, Abelard wins.
  2. If , then Abelard chooses one of the subformulas , and the corresponding game is played.
  3. If , then Eloises chooses one of the subformulas , and the corresponding game is played.
  4. If , then Abelard chooses an element of , and game is played.
  5. If , then Eloise chooses an element of , and game is played.

More generally, if is not in negation normal form, we can state, as a rule for negation, that, when a game is reached, the players begin playing a dual game in which the roles of Verifiers and Falsifier are switched.

Histories[edit]

Informally, a sequence of moves in a game is a history. At the end of each history , some subgame is played; we call the assignment associated to , and the subformula occurrence associated to . The player associated to is Eloise in case the most external logical operator in is or , and Abelard in case it is or .

The set of allowed moves in a history is if the most external operator of is or ; it is ( being any two distinct objects, symbolizing 'left' and 'right') in case the most external operator of is or .

Given two assignments of same domain, and we write if on any variable .

Imperfect information is introduced in the games by stipulating that certain histories are indistinguishable for the associated player; indistinguishable histories are said to form an 'information set'. Intuitively, if the history is in the information set , the player associated to does not know whether he is in or in some other history of . Consider two histories such that the associated are identical subformula occurrences of the form ( or ); if furthermore , we write (in case ) or (in case ), in order to specify that the two histories are indistinguishable for Eloise, resp. for Abelard. We also stipulate, in general, reflexivity of this relation: if , then ; and if , then .

Strategies[edit]

For a fixed game , write for the set of histories to which Eloise is associated, and similarly for the set of histories of Abelard.

A strategy for Eloise in the game is any function that assigns, to any possible history in which it is Eloise's turn to play, a legal move; more precisely, any function such that for every history . One can define dually the strategies of Abelard.

A strategy for Eloise is uniform if, whenever , ; for Abelard, if implies .

A strategy for Eloise is winning if Eloise wins in each terminal history that can be reached by playing according to . Similarly for Abelard.

Truth, falsity, indeterminacy[edit]

An IF sentence is true in a structure () if Eloise has a uniform winning strategy in the game . It is false () if Abelard has a winning strategy. It is undetermined if neither Eloise nor Abelard has a winning strategy.

Conservativity[edit]

The semantics of IF logic thus defined is a conservative extension of first-order semantics, in the following sense. If is an IF sentence with empty slash sets, associate to it the first-order formula which is identical to it, except in that each IF quantifier is replaced by the corresponding first-order quantifier . Then iff in the Tarskian sense; and iff in the Tarskian sense.

Open formulas[edit]

More general games can be used to assign a meaning to (possibly open) IF formulas; more exactly, it is possible to define what it means for an IF formula to be satisfied, on a structure , by a team (a set of assignments of common variable domain and codomain ). The associated games begin with the random choice of an assignment ; after this initial move, the game is played. The existence of a winning strategy for Eloise defines positive satisfaction (), and existence of a winning strategy for Abelard defines negative satisfaction (). At this level of generality, Game-theoretical Semantics can be replaced by an algebraic approach, team semantics (defined below).

Skolem Semantics[edit]

A definition of truth for IF sentences can be given, alternatively, by means of a translation into existential second-order logic. The translation generalizes the Skolemization procedure of first-order logic. Falsity is defined by a dual procedure called Kreiselization.

Skolemization[edit]

Given an IF formula , we first define its skolemization relativized to a finite set of variables. For every existential quantifier occurring in , let be a new function symbol (a "Skolem function"). We write for the formula which is obtained substituting, in , all free occurrences of the variable with the term . The Skolemization of relative to , , is defined by the following inductive clauses:

  1. if is a literal.
  2. if .
  3. .
  4. , where is a list of the variables in .

If is an IF sentence, its (unrelativized) Skolemization is defined as .

Kreiselization[edit]

Given an IF formula , associate, to each universal quantifier occurring in it, a new function symbol (a "Kreisel function"). Then, the Kreiselization of relative to a finite set of variables , is defined by the following inductive clauses:

  1. if is a literal.
  2. .
  3. .
  4. , where is a list of the variables in .

If is an IF sentence, its (unrelativized) Kreiselization is defined as .

Truth, falsity, indeterminacy[edit]

Given an IF sentence with existential quantifiers, a structure , and a list of functions of appropriate arities, we denote as the expansion of which assigns the functions as interpretations for the Skolem functions of .

An IF sentence is true on a structure () iff there is a tuple of functions such that . Similarly, iff there is a tuple of functions such that ; and iff neither of the previous conditions holds.

For any IF sentence, Skolem Semantics returns the same values as Game-theoretical Semantics.

Team Semantics[edit]

By means of team semantics, it is possible to give a compositional account of the semantics of IF logic. Truth and falsity are grounded on the notion of 'satisfiability of a formula by a team'.

Teams[edit]

Let be a structure and let be a finite set of variables. Then a team over with domain is a set of assignments over with domain , that is, a set of functions from to .

Duplicating and supplementing teams[edit]

Duplicating and supplementing are two operations on teams which are related to the semantics of universal and existential quantification.

  1. Given a team over a structure and a variable , the duplicating team is the team .
  1. Given a team over a structure , a function and a variable , the supplementing team is the team .

It is customary to replace repeated applications of these two operation with more succinct notations, such as for .

Uniform functions on teams[edit]

As above, given two assignments with same variable domain, we write if for every variable .

Given a team on a structure and a finite set of variables, we say that a function is -uniform if whenever .

Semantic clauses[edit]

Team semantics is three-valued, in the sense that a formula may happen to be positively satisfied by a team on a given structure, or negatively satisfied by it, or neither. The semantics clauses for positive and negative satisfaction are defined by simultaneous induction on the synctactical structure of IF formulas.

Positive satisfaction:

  1. if and only if, for every assignment , in the sense of first-order logic (that is, the tuple is in the interpretation of ).
  2. if and only if, for every assignment , in the sense of first-order logic (that is, ).
  3. if and only if .
  4. if and only if and .
  5. if and only if there exist teams and such that and and .
  6. if and only if .
  7. if and only if there exists a -uniform function such that .

Negative satisfaction:

  1. if and only if, for every assignment , the tuple is not in the interpretation of .
  2. if and only if, for every assignment , .
  3. if and only if .
  4. if and only if there exist teams and such that and and .
  5. if and only if and .
  6. if and only if there exists a -uniform function such that .
  7. if and only if .

Truth, falsity, indeterminacy[edit]

According to team semantics, an IF sentence is said to be true () on a structure if it is satisfied on by the singleton team , in symbols: . Similarly, is said to be false () on if ; it is said to be undetermined () if and .

Relationship with Game-Theoretical Semantics[edit]

For any team on a structure , and any IF formula , we have: iff and iff .

From this it immediately follows that, for sentences , , and .

Notions of equivalence[edit]

Since IF logic is, in its usual acception, three-valued, multiple notions of formula equivalence are of interest.

Equivalence of formulas[edit]

Let be two IF formulas.

( truth entails ) if for any structure and any team such that .

( is truth equivalent to ) if and .

( falsity entails ) if for any structure and any team such that .

( is falsity equivalent to ) if and .

( strongly entails to ) if and .

( is strongly equivalent to ) if and .

Equivalence of sentences[edit]

The definitions above specialize for IF sentences as follows. Two IF sentences are truth equivalent if they are true in the same structures; they are falsity equivalent if they are false in the same structures; they are strongly equivalent if they are both truth and falsity equivalent.

Intuitively, using strong equivalence amounts to considering IF logic as 3-valued (true/undetermined/false), while truth equivalence treats IF sentences as if they were 2-valued (true/untrue).

Equivalence relative to a context[edit]

Many logical rules of IF logic can be adequately expressed only in terms of more restricted notions of equivalence, which take into account the context in which a formula might appear.

For example, if is a finite set of variables and , one can state that is truth equivalent to relative to () in case for any structure and any team of domain .

Model-theoretic properties[edit]

Sentence level[edit]

IF sentences can be translated in a truth-preserving fashion into sentences of (functional) existential second-order logic () by means of the Skolemization procedure (see above). Vice versa, every can be translated into an IF sentence by means of a variant of the Walkoe-Enderton translation procedure for partially-ordered quantifiers ([12][13]). In other words, IF logic and are expressively equivalent at the level of sentences. This equivalence can be used to prove many of the properties that follow; they are inherited from and in many cases similar to properties of FOL.

We denote by a (possibly infinite) set of IF sentences.

  • Löwenheim-Skolem property: if has an infinite model, or arbitrarily large finite models, than it has models of every infinite cardinality.
  • Existential compactness: if every finite has a model, then also has a model.
  • Failure of deductive compactness: there are such that , but for any finite . This is a difference from FOL.
  • Separation theorem: if are mutually inconsistent IF sentences, then there is a FOL sentence such that and . This is a consequence of Craig's interpolation theorem for FOL.
  • Burgess' theorem:[14] if are mutually inconsistent IF sentences, then there is an IF sentence such that and (except possibly for one-element structures). In particular, this theorem reveals that the negation of IF logic is not a semantical operation with respect to truth equivalence (truth-equivalent sentences may have non-equivalent negations).
  • Definability of truth:[15] there is an IF sentence , in the language of Peano Arithmetic, such that, for any IF sentence , (where denotes a Gödel numbering). A weaker statement also holds for nonstandard models of Peano Arithmetic ([16]).

Formula level[edit]

The notion of satisfiability by a team has the following properties:

  • Downward closure: if and , then .
  • Consistency: and if and only if .
  • Non-locality: there are such that .

Since IF formulas are satisfied by teams and formulas of classical logics are satisfied by assignments, there is no obvious intertranslation between IF formulas and formulas of some classical logic system. However, there is a translation procedure[17] of IF formulas into sentences of relational (actually, one distinct translation for each finite and for each choice of a predicate symbol of arity ). In this kind of translation, an extra n-ary predicate symbol is used to represent an n-variable team . This is motivated by the fact that, once an ordering of the variables of has been fixed, it is possible to associate a relation to the team . With this conventions, an IF formula is related to its translation thus:

where is the expansion of that assigns as interpretation for the predicate .

Through this correlation, it is possible to say that, on a structure , an IF formula of n free variables defines a family of n-ary relations over (the family of the relations such that ).

In 2009, Kontinen and Väänänen,[18] showed, by means of a partial inverse translation procedure, that the families of relations that are definable by IF logic are exactly those that are nonempty, downward closed and definable in relational with an extra predicate (or, equivalently, nonempty and definable by a sentence in which occurs only negatively).

Extended IF logic[edit]

IF logic is not closed under classical negation. The boolean closure of IF logic is known as extended IF logic and it is equivalent to a proper fragment of (Figueira et al. 2011). Hintikka (1996, p. 196) claimed that "virtually all of classical mathematics can in principle be done in extended IF first-order logic".

Properties and critique[edit]

A number of properties of IF logic follow from logical equivalence with and bring it closer to first-order logic including a compactness theorem, a Löwenheim–Skolem theorem, and a Craig interpolation theorem. (Väänänen, 2007, p. 86). However, Väänänen (2001) proved that the set of Gödel numbers of valid sentences of IF logic with at least one binary predicate symbol (set denoted by ValIF) is recursively isomorphic with the corresponding set of Gödel numbers of valid (full) second-order sentences in a vocabulary that contains one binary predicate symbol (set denoted by Val2). Furthermore, Väänänen showed that Val2 is the complete Π2-definable set of integers, and that it is Val2 not in for any finite m and n. Väänänen (2007, pp. 136–139) summarizes the complexity results as follows:

Problem first-order logic IF/dependence/ESO logic
Decision (r.e.)
Non-validity (co-r.e.)
Consistency
Inconsistency

Feferman (2006) cites Väänänen's 2001 result to argue (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). Feferman also attacked the claimed usefulness of the extended IF logic, because the sentences in do not admit a game-theoretic interpretation.

Notes[edit]

See also[edit]

References[edit]

  • Burgess, John P., "A Remark on Henkin Sentences and Their Contraries", Notre Dame Journal of Formal Logic 44 (3):185-188 (2003).
  • Cameron, Peter and Hodges, Wilfrid (2001), "Some combinatorics of imperfect information". Journal of Symbolic Logic 66: 673-684.
  • Eklund, Matti and Kolak, Daniel, "Is Hintikka’s Logic First Order?" Synthese, 131(3): 371-388 June 2002, [1].
  • Enderton, Herbert B., "Finite Partially-Ordered Quantifiers", Mathematical Logic Quarterly Volume 16, Issue 8 1970 Pages 393–397.
  • Feferman, Solomon, "What kind of logic is “Independence Friendly” logic?", in The Philosophy of Jaakko Hintikka (Randall E. Auxier and Lewis Edwin Hahn, eds.); Library of Living Philosophers vol. 30, Open Court (2006), 453-469, http://math.stanford.edu/~feferman/papers/hintikka_iia.pdf.
  • Figueira, Santiago, Gorín, Daniel and Grimson, Rafael "On the Expressive Power of IF-Logic with Classical Negation", WoLLIC 2011 proceedings, pp. 135-145, ISBN 978-3-642-20919-2,[2].
  • Hintikka, Jaakko (1996), "The Principles of Mathematics Revisited", Cambridge University Press, ISBN 978-0-521-62498-5.
  • Hintikka, Jaakko, "Hyperclassical logic (a.k.a. IF logic) and its implications for logical theory", Bulletin of Symbolic Logic 8, 2002, 404-423http://www.math.ucla.edu/~asl/bsl/0803/0803-004.ps .
  • Hintikka, Jaakko and Gabriel Sandu (1989), "Informational independence as a semantical phenomenon", in Logic, Methodology and Philosophy of Science VIII (J. E. Fenstad, et al., eds.), North-Holland, Amsterdam, doi:10.1016/S0049-237X(08)70066-1.
  • Hintikka, Jaakko and Sandu, Gabriel, "Game-theoretical semantics", in Handbook of logic and language, ed. J. van Benthem and A. ter Meulen, Elsevier 1996 (1st ed.) Updated in the 2nd second edition of the book (2011).
  • Hodges, Wilfrid (1997), "Compositional semantics for a language of imperfect information". Journal of the IGPL 5: 539–563.
  • Hodges, Wilfrid, "Some Strange Quantifiers", in Lecture Notes in Computer Science 1261:51-65, Jan. 1997.
  • Janssen, Theo M. V., "Independent choices and the interpretation of IF logic." Journal of Logic, Language and Information, Volume 11 Issue 3, Summer 2002, pp. 367-387 doi:10.1023/A:1015542413718[3].
  • Kolak, Daniel, On Hintikka, Belmont: Wadsworth 2001 ISBN 0-534-58389-X.
  • Kolak, Daniel and Symons, John, "The Results are In: The Scope and Import of Hintikka’s Philosophy" in Daniel Kolak and John Symons, eds., Quantifiers, Questions, and Quantum Physics. Essays on the Philosophy of Jaakko Hintikka, Springer 2004, pp. 205-268 ISBN 1-4020-3210-2, doi:10.1007/978-1-4020-32110-0_11.
  • Kontinen, Juha and Väänänen, Jouko, "On definability in dependence logic" (2009), Journal of Logic, Language and Information 18 (3), 317-332.
  • Mann, Allen L., Sandu, Gabriel and Sevenster, Merlijn (2011) Independence-Friendly Logic. A Game-Theoretic Approach, Cambridge University Press, ISBN 0521149347.
  • Sandu, Gabriel, "If-Logic and Truth-definition", Journal of Philosophical Logic April 1998, Volume 27, Issue 2, pp 143–164.
  • Sandu, Gabriel, "On the Logic of Informational Independence and Its Applications", Journal of Philosophical Logic Vol. 22, No. 1 (Feb. 1993), pp. 29-60.
  • Väänänen, Jouko, 2007, 'Dependence Logic -- A New Approach to Independence Friendly Logic]', Cambridge University Press, ISBN 978-0-521-87659-9, [4].
  • Walkoe, Wilbur John Jr., "Finite Partially-Ordered Quantification", The Journal of Symbolic Logic Vol. 35, No. 4 (Dec., 1970), pp. 535-555.

External links[edit]