↑ arvau

Wikipedia / Independence-friendly logic

Independence-friendly logic (IF logic; proposed by Jaakko Hintikka and in 1989) is an extension of classical first-order logic". 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 depends only depends only. IF logic is more general than branching quantifiers.

The introduction of IF logic was partly motivated by the attempt of extending the game 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; 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.

Independence-friendly 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.

Independence-friendly 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 \Delta_2^1.

Hintikka argued that IF and extended IF logic should be used as a basis for the foundations of mathematics; this proposal was met in some cases with skepticism.

Syntax

A number of slightly different presentations of independence-friendly logic have appeared in the literature; here we follow Mann et al (2011).

Terms and atomic formulas

For a fixed signature σ, terms and atomic formulas are defined exactly as in first-order logic with equality.

IF formulas

Formulas of IF logic are defined as follows:

  1. is an IF formula.

  2. is an IF formula.

  3. are IF formulas.

  4. are also IF formulas.

Free variables

is defined inductively as follows:

  1. is an atomic formula is the set of all variables occurring in it.

  2. ;

  3. ;

  4. .

are counted as free variables.

IF Sentences

is an IF sentence.

Semantics

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; the third one by Hodges in 1997.

will be used in the rest of the article.

Game-Theoretical Semantics

.

Players

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

Game rules

is in negation normal form, with negations symbols occurring only in front of atomic subformulas.

  1. (in the first-order sense), then Eloise wins; otherwise, Abelard wins.

  2. is played.

  3. is played.

  4. is played.

  5. is played.

in which the roles of Verifiers and Falsifier are switched.

Histories

the assignment associated to the subformula occurrence associated to. The player associated to.

of allowed moves.

.

.

Strategies

for the set of histories of Abelard.

A strategy. One can define dually the strategies of Abelard.

A strategy for Eloise is uniform.

for Eloise is winning. Similarly for Abelard.

Truth, falsity, indeterminacy

is true. It is false) if Abelard has a winning strategy. It is undetermined if neither Eloise nor Abelard has a winning strategy.

Conservativity

in the Tarskian sense.

Open formulas

, by a team 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

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

, is defined by the following inductive clauses:

  1. is a literal.

  2. .

  3. .

  4. .

  5. .

.

Kreiselization

, is defined by the following inductive clauses:

  1. is a literal.

  2. .

  3. .

  4. .

.

Truth, falsity, indeterminacy

.

iff neither of the previous conditions holds.

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

Team Semantics

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

be a structure.

Duplicating and supplementing teams

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

  1. .

  2. .

.

Uniform functions on teams

.

.

Semantic clauses

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).

  2. ).

  3. .

  4. .

  5. .

  6. .

  7. .

Negative satisfaction:

  1. .

  2. .

  3. .

  4. .

  5. .

  6. .

  7. .

Truth, falsity, indeterminacy

.

Relationship with Game-Theoretical Semantics

.

.

Notions of equivalence

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

Equivalence of formulas

be two IF formulas.

truth entails.

is truth equivalent.

falsity entails.

is falsity equivalent.

strongly entails.

is strongly equivalent.

Equivalence of 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

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.

is truth equivalent to relative to of domain.

Model-theoretic properties

Sentence level

IF sentences can be translated in a truth-preserving fashion into sentences of (functional) existential second-order logic can be translated into an IF sentence by means of a variant of the Walkoe-Enderton translation procedure for partially-ordered quantifiers ( and in many cases similar to properties of FOL.

a (possibly infinite) set of IF sentences.

  • has an infinite model, or arbitrarily large finite models, than it has models of every infinite cardinality.

  • has a model.

  • . This is a difference from FOL.

  • . This is a consequence of Craig's interpolation theorem for FOL.

  • Burgess' theorem: (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: denotes a Gödel numbering). A weaker statement also holds for nonstandard models of Peano Arithmetic ().

Formula level

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

  • .

  • .

  • .

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 of IF formulas into sentences of relational. With this conventions, an IF formula is related to its translation thus:

.

of n free variables defines).

In 2009, Kontinen and Väänänen, occurs only negatively).

Extended IF logic

IF logic is not closed under classical negation. The boolean closure of IF logic is known as extended IF logic (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

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 for any finite m and n. Väänänen (2007, pp.136–139) summarizes the complexity results as follows: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 do not admit a game-theoretic interpretation.

See also

Notes

References