Independence friendly logic (IF logic, IF first-order logic) is anextension of first-order logic. In it, more quantifier dependenciesand independencies can be expressed than in first-order logic. Itsquantifiers range over individuals only; semantically IF first-orderlogic, however, has the same expressive power as existentialsecond-order logic. IF logic lacks certain metaproperties thatfirst-order logic has (axiomatizability, Tarski-type semantics). Onthe other hand, IF logic admits a self-applied truth-predicate –a property that first-order logic notoriously does not enjoy.Philosophical issues discussed in connection with IF logic includereformulating the logicist program, the question of truth in axiomaticset theory, and the nature of negation. Work in IF logic has alsoinspired alternative generalizations of first-order logic: slash logicanddependence logic.

• 1. Introduction: Quantifier Dependence
• 2. The Background of IF Logic: Game-theoretical Semantics
  • 2.1. Semantic games
  • 2.2. Imperfect information
• 3. The Syntax and Semantics of IF First-order Logic
  • 3.1. Syntax
  • 3.2. Semantics
  • 3.3. Basic properties and notions
  • 3.4. Extended IF first-order logic
• 4. Metalogical Properties of IF First-order Logic
  • 4.1. First-order logic and existential second-order logic
  • 4.2. Intricacies of negation
  • 4.3 Failure of axiomatizability
  • 4.4 Compositionality and the failure of Tarski-type semantics
  • 4.5 Defining truth
  • 4.6 Properties of extended IF first-order logic
• 5. Philosophical Consequences
  • 5.1 Place in type hierarchy
  • 5.2 Philosophy of set theory
  • 5.3 Extended IF first-order logic and mathematical theorizing
  • 5.4 Informational independence in natural languages
• 6. Related Logics
  • 6.1 Slash logic
  • 6.2 Dependence logic
• 7. Conclusion
• Bibliography
• Academic Tools
• Other Internet Resources
• Related Entries

1. Introduction: Quantifier Dependence

In mathematical prose, one can say things such as ‘for all realnumbers \(a\) and for all positive real numbers \(\varepsilon\), thereexists a positive real number \(\delta\) depending on \(\varepsilon\)but not on \(a\), such that…’ What is important here isquantifier dependence. The existential quantifier ‘there exists\(\delta\)’ is said to depend on the universal quantifier‘for all \(\varepsilon\)’ but not on the universalquantifier ‘for all \(a\).’ It was an essential part ofKarl Weierstrass’s (1815–1897) work in the foundations ofanalysis that he defined the notions of limit, continuity, andderivative in terms of quantifier dependence.^[1] For a concrete example, a function \(f : D \rightarrow \mathbf{R}\)iscontinuous, if for all \(a\) in the set \(D\) and for all\(\varepsilon \gt 0\) there exists \(\delta \gt 0\) such that for all\(x\) in \(D\), if \(|x - a| \lt \delta\), then \(|f(x) - f(a)| \lt \varepsilon\). The definition ofuniformcontinuity is obtained from that of continuity by specifying thatthe quantifer ‘there exists \(\delta\)’ depends only onthe quantifier ‘for all \(\varepsilon\),’ not on thequantifier ‘for all \(a\).’^[2]

Independence friendly first-order logic (a.k.a.IFfirst-order logic,IF logic) was introduced by JaakkoHintikka and Gabriel Sandu in their article ‘InformationalIndependence as a Semantical Phenomenon’ (1989); other earlysources are Hintikka’s bookletDefining Truth, the WholeTruth, and Nothing but the Truth (1991) and Sandu’s Ph.D.thesis (1991).^[3] IF first-order logic is an extension of first-order logic, involvinga specific syntactic device ‘/’ (slash, independenceindicator), which has at the object language level the same effect asthe meta-level modifier ‘but does not depend on’ has inthe example just considered. In the notation of IF logic, the logicalform of the statement that a function \(f\) is uniformlycontinuous would be\((\forall a)(\forall \varepsilon)(\exists \delta /\forall a)(\forall x)R\), to be contrasted with the form of the statement that\(f\) merely is continuous,\((\forall a)(\forall \varepsilon)(\exists \delta)(\forall x)R\).

If in a first-order sentence an existential quantifier \(\existsy\) lies in the syntactic scope of a universal quantifier \(\forallx\), then by the semantics \(\exists y\) automatically depends on\(\forall x\). This is soe.g. with the sentence \((\forallx)(\exists y) R(x, y)\). The dependence of \(\exists y\) on \(\forallx\) means that thewitness of \(\exists y\) may vary with thevalue interpreting \(\forall x\). It suffices that there be a function\(f\) such that \(R(a, f(a))\) holds in \(M\), for any \(a\)interpreting \(\forall x\). Such functions, spelling out thedependencies of witnesses for existential quantifiers oninterpretations of universal quantifiers, are known in logicalliterature asSkolem functions.^[4] For comparison, in the sentence \((\exists y)(\forall x) R(x, y)\)the quantifier \(\exists y\) does not depend on the quantifier\(\forall x.\) One and the same witness \(c\) for \(\exists y\) mustbe good against any interpretation \(a\) of \(\forall x\), so that\(R(a, c)\) holds in \(M\). The corresponding Skolem function is a constant.^[5]

In IF first-order logic, syntactic scopes no longer determine thesemantic relation of dependence. In the formula \((\forall x)(\forally)(\exists z/\forall y) R(x, y, z)\), for instance, \(\exists z\) issyntactically subordinate to both \(\forall x\) and \(\forall y\), butis marked as independent of \(\forall y\), and is hence dependent onlyon \(\forall x\). Semantically this means that the witness of\(\exists z\) must be given by a function taking as an argument theinterpretation of \(\forall x\), but not that of \(\forall y\). Inorder for \((\forall x)(\forall y)(\exists z/\forall y) R(x, y, z)\)to be true in \(M\), there must be a function \(f\) of one argumentsuch that \(R(a, b, f(a))\) holds in \(M\), for any \(a\) interpreting\(\forall x\) and any \(b\) interpreting \(\forall y\).

What is gained with the slash notation? After all, clearlye.g.\((\forall x)(\forall y)(\exists z/\forall y)R(x, y, z)\) is true in a model\(M\) iff^[6] the first-order sentence\((\forall x)(\exists z)(\forall y)R(x, y, z)\) is true therein. As amatter of fact, the expressive power of IF logic exceeds that offirst-order logic. Consider the sentence\((\forall x)(\exists y)(\forall z)(\exists w/\forall x)R(x, y, z, w)\). Itstruth-condition is of the following form: there are one-argumentfunctions \(f\) and \(g\) such that \(R(a,f(a), b, g(b))\) holds in\(M\), for any \(a\) interpreting \(\forall x\) and\(b\) interpreting \(\forall z\).^[7] So the sentence is true iff the following sentence (*) containing afinite partially ordered quantifier is true:

For, by definition (*) is true in a model \(M\) iff the second-ordersentence \((\exists f)(\exists g)(\forall x)(\forall z) R(x, f(x), z,g(z))\) is true therein. The latter may be termed theSkolem normal form of (*). It says that Skolem functionsproviding witnesses for the quantifiers \(\exists y\) and\(\exists w\) in (*) exist. Finite partially ordered quantifiers– a.k.a.Henkin quantifiers orbranchingquantifiers – were proposed by Leon Henkin (1961) and havebeen subsequently studied extensively.^[8] They are two-dimensional syntactic objects

where each \(Q_{ij}\) is either \(\exists x_{ij}\) or \(\forallx_{ij}\). They are naturally interpreted by making systematic use ofSkolem functions.

Let us denote by \(\mathbf{FPO}\) the logic of finite partiallyordered quantifiers obtained from first-order logic as follows: if\(\phi\) is a first-order formula and \(\mathbf{Q}\) is a finitepartially ordered quantifier, then \(\mathbf{Q}\phi\) is aformula of \(\mathbf{FPO}\).^[9] With \(\mathbf{FPO}\) it is possible to express properties thatare not definable in first-order logic. The first example was providedby Andrzej Ehrenfeucht (cf. Henkin 1961): a sentence that is true in amodel iff the size of its domain is infinite. It turns out that\(\mathbf{FPO}\) can be translated into IF logic (seeSubsect. 4.1). Therefore IF logic is more expressive thanfirst-order logic.

The deepest reason for IF logic, as Hintikka sees it, is that therelations of dependence and independece betweenquantifiersare the only way of expressing relations of dependence and independecebetweenvariables on the first-order level (Hintikka 1996:34–35, 73–74; 2002a: 404–405; 2006a: 71, 515). Tounderstand this remark properly, recall that relations of quantifier(in)dependence aresemantic relations, butsyntacticallyexpressed. More precisely, in IF logic the (in)dependencerelations are syntactically expressed by the interplay of two factors:syntactic scope and the independence indicator ‘/’. In agiven sentence, an existential quantifier \(\exists x\), say,depends on precisely those universal quantifiers within whose scope\(\exists x\) lies, but of which \(\exists x\) is not markedas independent using the slash sign. What Hintikka means when hespeaks of (in)dependence relations between variables, arefunctional dependencies between quantities in a model. Thekinetic energy of a material body depends on its mass and its speed,but does not depend on the particular material body being considered.This fact can be expressed in IF logic by the sentence

\((\forall b)(\forall m)(\forall v)(\exists e/\forall b)\)(if\(b\) is a material body which moves at the velocity \(v\)and has the mass \(m\), then the kinetic energy \(e\) of\(b\) equals \(\frac{1}{2} mv^2 )\).

That this sentence states the existence of a functional dependence ofkinetic energy on mass and speed is particularly clearly seen from thefact that if the sentence is true, the unique Skolem function for thequantifier \(\exists e\) actuallyis the physical lawconnecting masses, speeds and kinetic energies (cf. Hintikka 1996:34–35).

While first-order logic can only express some relations betweenvariables, IF first-order logic with its greater expressive power canexpress more. Actually, IF logic is calculated to capture all suchrelations (Hintikka 1996: 75–77; 2002a: 404–405; 2002b:197; 2006a: 72). This idea must, in its full generality, be seen asprogrammatic. For a more general framework, cf. Hintikka (2006a: 515,536, 752; 2008), Sandu & Sevenster (2010), Sandu (2013).

Among philosophical issues that have been addressed in connection withIF logic are the reconstruction of mathematical reasoning on thefirst-order level (Hintikka 1996, 1997), definability of aself-applied truth predicate (Hintikka 1991, 1996, 2001; Sandu 1998),truth and axiomatic set theory (Hintikka 1996, 2004a), and insightsinto the nature of negation (Hintikka 1991, 1996, 2002; Hintikka &Sandu 1989; Sandu 1994). These issues will be discussed inSections 4 and 5.

2. The Background of IF Logic: Game-theoretical Semantics

2.1. Semantic games

Inspired by Ludwig Wittgenstein’s idea of a language-game,Hintikka (1968) introduced the basic framework of what came to beknown asgame-theoretical semantics (a.k.a. GTS). The basiclesson Hintikka adopts from Wittgenstein is that words – inparticular quantifiers – are associated with activities thatrender them meaningful: words often have meaning only in the contextof certain types of action (Hintikka 1968: 55–56). Wittgensteinsaid that by ‘language-game’ he means ‘the whole,consisting of language and the actions into which it is woven’(Wittgenstein 1953: I,Sect. 7).

It becomes natural to ask which are the activities that go togetherwith quantifiers. As Hintikka explains (see Hintikka 2006a: 41, 67),Wittgenstein had taken it as a criterion for something to be an objectthat it can be looked for and found. Applying this idea to quantifierswith such objects as values, Hintikka was led to formulatesemantic games for quantifiers. Crucially, these semanticgames can be formulated as games in the strict sense of game theory;but at the same time they are exact codifications of language-games inWittgenstein’s sense, at least if one accepts that theactivities associated with quantifiers are ‘looking for’and ‘finding.’^[10]

Semantic games \(G(\phi , M)\) for first-order sentences \(\phi\) aretwo-player zero-sum games of perfect information, played on a givenmodel \(M\). Let us call the two players simply player 1 and player 2.^[11] The gamesare most easily explained for sentences in prenex normal form: astring of quantifiers followed by a quantifier-free first-orderformula. Universal quantifiers mark a move of player 1, whileexistential quantifiers prompt a move by player 2. In both cases, therelevant player must choose an individual from the domain \(\rM\) of \(M\).^[12] If

the game is played as follows. First, player 1 picks out an individual\(a\), whereafter player 2 chooses an individual \(b\). Then player 1proceeds to choose a further individual \(c\), to which player 2responds by picking out an individual \(d\). Thereby a play of thegame has come to an end. The tuple \((a, b, c, d)\) of individualschosen determines the winner of the play. If the quantifier-freeformula \(R(a, b, c, d)\) holds in \(M\), player 2 wins, if not,player 1 wins.

The fact that one of the players wins a single play of game \(G(\phi ,M)\) does not yet tell us anything about the truth-value of thesentence \(\phi\). Truth and falsity are characterized in terms of thenotion ofwinning strategy. The sentence \((\forallx)(\exists y)(\forall z)(\exists w) R(x, y, z, w)\) istrue in \(M\) if there is a winning strategy for player2 in the game just described: a recipe telling player 2 what to do,when (a specified amount of) information about the opponent’searlier moves is given. Technically, the requirement is that there bestrategy functions \(f\) and \(g\), such that forany choices \(a\) and \(c\) by player \(1,R(a, f(a), c, g(a, c))\) holds in \(M\). Observe thatstrategy function \(f\) is a Skolem function for the quantifier\(\exists y\) in \(\phi\), and similarly \(g\) is a Skolemfunction for the quantifier \(\exists w\). The sentence \(\phi\) isfalse in \(M\) if there is a winning strategy (set ofstrategy functions) for player 1 in the corresponding game: a constant\(c\) and a function \(h\) such that for any choices \(b\) and \(d\)by player \(2, R(c, b, h(b), d)\) fails to hold in \(M\).

Game-theoretical interpretaton of quantifiers was already suggested byHenkin (1961; cf. Hintikka 1968: 64). Henkin also pointed out, ineffect, the connection between a full set of Skolem functions and awinning strategy for player 2. Hintikka (1968) noted that conjunctionsare naturally interpreted by a choice between the two conjuncts, madeby player 1; similarly, disjunctions can be interpreted by a choice byplayer 2 between the two disjuncts.^[13] Further, Hintikka proposed to interpret negation as a transpositionof the roles of ‘verifier’ and ‘falsifier’(for more details, seeSubsect. 3.2).

The game-theoretical description of semantic games does not mentionthe activities of searching and finding; for such an abstractdescription it suffices to speak of the players making a move. Also,the characterization of truth and falsity as the existence of awinning strategy for player 2 and player 1, respectively, does notrefer to efforts on the part of the players – say efforts toestablish truth or to find witnesses. The truth or falsity of asentence is a matter of ‘combinatorics’: it is an issue ofthe existence of a set of functions with certain properties (cf.Hintikka 1968, 1996; Hodges 2013). So what happened to the originalphilosophical conception according to which the meanings ofquantifiers are tied to the activities of searching and finding?Hintikka’s idea is that asserting a sentence involvingquantifiers is to make a claim about what can and what cannot happenwhen a certain language-game is played; using language involvingquantifiers requires mastering the rules of the corresponding semanticgames (Hintikka 1968:Sect. 8, 1996: 128, 2006a: 538). Whatis the content of such a claim in connection with the sentence\(\forall x\exists y R(x, y)\)? That whichever individual player 1chooses from the domain for \(\forall x\), player 2 can find a witnessindividual for \(\exists y\). In other words, given a value for\(\forall x\) (which itself can be seen as the result of the search byplayer 1), if player 2 is allowed to search free from any practicalconstraints, she will find a value for \(\exists y\) so that player 2wins the resulting play. Even though semantic games themselves can bedefined without recourse to activities such as looking for or finding,these activities play an important conceptual role when the languageuser reasonsabout these games.

Hintikka (1973a) initiated the application of GTS to the study ofnatural language. This work was continued notably by Hintikka &Kulas (1983, 1985), where game-theoretical rules for such items asnegation, anaphoric pronouns, genitives, tenses, intensional verbs,certain prepositional constructions, and proper names were given, andthe distinction between abstract meaning and strategic meaning drawn.^[14]

2.2. Imperfect information

The framework of GTS enables asking questions of a game-theoreticalnature about semantic evaluation. Hintikka (1973a) observed thatsemantic games with imperfect information are devised without anydifficulty. As logical examples he used \(\mathbf{FPO}\)sentences. (For examples related to natural languages, seeSubsect. 5.4.)

From the vantage point of GTS, independence friendly first-order logicdiffers from first-order logic in that semantic games correlated withformulas of the former are, in general, games of imperfectinformation, while any game associated with a first-order formula is agame of perfect information. Consider the game for \(\forall x\existsy\forall z(\exists w/\forall x) R(x, y, z, w)\), played on a model\(M\). A play of this game proceeds exactly as plays of the gamecorresponding to \(\forall x\exists y\forall z\exists w R(x, y, z,w)\). First, player 1 chooses an individual \(a\), whereafter player 2chooses an individual \(b\). Then player 1 proceeds to pick out afurther individual \(c\), to which player 2 responds by choosing anindividual \(d\). So a play of the game has come to an end. The playis won by player 2, if indeed \(R(a, b,c, d)\) holds in \(M\);otherwise it is won by player 1. But \(\exists w\) was marked asindependent of \(\forall x\) – why does not this fact show inany way in the course of a play?

One might be tempted to add to the description of a play:‘player 2 chooses a value for \(\exists w\) in ignorance of thevalue for \(\forall x\).’ However, such a paraphrase would notclarify the conceptual situation. It makes no sense to speak of theindependence of a move from other given moves by reference to a singleplay; this can only be done by reference to a multitude ofplays. Quantifier independence can be conceptualized ingame-theoretical terms making use of the notion ofstrategy.In the example, a strategy of player 2 is a set \(\{f, g\}\) ofstrategy functions, function \(f\) providing a value for \(\exists y\)depending on the value of \(\forall x\), and function \(g\) providinga value for \(\exists w\) depending on the value chosen for \(\forallz\) but not on the value chosen for \(\forall x\). The strategy \(\{f,g\}\) is, then, a winning strategy for player 2, iff \(R(a, f(a), c,g(c))\) holds in \(M\), for all values \(a\) chosen for \(\forall x\)and \(c\) chosen for \(\forall z\). One precise way of implementingthe idea that player 2 is ‘ignorant’ of the move player 1made for \(\forall x\) is to say that(a) strategyfunctions always only take as arguments the opponent’s moves,and(b) the strategy function corresponding to\(\exists w\) may not take as its argument the move player 1 made for\(\forall x\).

A sentence of IF first-order logic is by definition true in a model\(M\) iff there is a winning strategy for player 2 in thecorrelated game, and false iff there is a winning strategy for player1 in the correlated game. There are sentences which under thesecriteria are neither true nor false; they are callednon-determined (seeSubsect. 3.3).

In Hintikka’s judgement, the game-theoretical semantics ofquantifiers can be taken to have the same rationale that was mentionedas the deepest reason for IF first-order logic at the end ofSection 1: GTS is a method of representing, on thefirst-order level, the (in)dependence relations between variables bymeans of informational (in)dependence in the sense of game theory(Hintikka 1991: 12–13, 2006a: 535).

3. The Syntax and Semantics of IF First-order Logic

In the literature one can find essentially different formulations of‘IF first-order logic.’ The differences are not restrictedto syntax – examples of applying different semantic ideas can befound as well.

As already noted, there is a systematic connection between the Skolemfunctions and strategy functions of player 2. A Skolem function for anexistential quantifier is a function of the values assigned to theprecedinguniversal quantifiers, butnot a functionof the values assigned to the preceding existential quantifiers.^[15] Skolem functions are strategy functions taking as argumentsexclusively moves made by player 1. Generally a strategy for a playerin a two-player gamecan perfectly well make use of theprevious choices of either player. Hodges (2007) stresses that itmakes a difference on which notion – Skolem function or strategyfunction – the semantics of imperfect information is based.Hodges (1997a) adopted the notational convention of writing, say,\((\exists y/x)\) where Hintikka writes\((\exists y/\forall x)\), hence marking the differencebetween semantic games formulated in terms of arbitrary strategyfunctions and those whose strategy functions are in effect Skolemfunctions; the variable \(x\) in \((\exists y/x)\)can be ‘bound’ by any syntactically preceding quantifiercarrying the variable \(x\). Hodges proposed to employ the formerformulation, while in Hintikka (1991, 1995, 1996, 2002) and Sandu(1993, 1994) the latter formulation is employed. Hodges (2007: 119)writes:

[W]e refer to the logic with my notation and the general gamesemantics asslash logic. During recent years many writers inthis area (but never Hintikka himself) have transferred the name‘IF logic’ to slash logic, often without realising thedifference. Until the terminology settles down, we have to beware ofexamples and proofs that don’t make clear which semantics theyintend.

The distinction that Hodges makes between slash logic and IF logicserves to bring order to the mishmash of different formulations of IFfirst-order logic to be found in the literature.^[16]

3.1. Syntax

IF first-order logic is an extension of first-order logic. Now, anyfirst-order formula is equivalent to a first-order formula in which novariable occurs both free and bound, and in which no two nestedquantifiers carry the same variable. Formulas meeting these twosyntactic conditions will be termedregular. Henceforth wesystematically restrict attention to regular first-order formulas.^[17] Avocabulary (signature, non-logical terminology) is anycountable set \(\tau\) of relation symbols (each of which carries a fixedarity), function symbols (again each with a fixed arity), and constantsymbols. The first-order logic of vocabulary \(\tau\) will be referred toas \(\mathbf{FO}[\tau]\). A formula of \(\mathbf{FO}[\tau]\)is innegation normal form, if all occurrences of thenegation symbol \({\sim}\) immediately precede an atomic formula. The set offormulas of IF first-order logic of vocabulary \(\tau\) (or\(\mathbf{IFL}[\tau])\) can be defined as the smallest set suchthat:

1. If \(\phi\) is a formula of \(\mathbf{FO}[\tau]\) in negationnormal form, \(\phi\) is a formula.
2. If \(\phi\) is a formula and in \(\phi\) a token of \((\existsx)\) occurs in the syntactic scope of a number of universalquantifiers which include \((\forall y_1),\ldots ,(\forall y_n)\), theresult of replacing in \(\phi\) that token of \((\exists x)\) by\((\exists x/\forall y_1 ,\ldots ,\forall y_n)\) is a formula.
3. If \(\phi\) is a formula and in \(\phi\) a token of \(\vee\)occurs in the syntactic scope of a number of universal quantifierswhich include \((\forall y_1),\ldots ,(\forall y_n)\), the result ofreplacing in \(\phi\) that token of \(\vee\) by \((\vee /\forall y_1,\ldots ,\forall y_n)\) is a formula.
4. If \(\phi\) is a formula and in \(\phi\) a token of \((\forallx)\) occurs in the syntactic scope of a number of existentialquantifiers which include \((\exists y_1),\ldots ,(\exists y_n)\), theresult of replacing in \(\phi\) that token of \((\forall x)\) by\((\forall x/\exists y_1 ,\ldots ,\exists y_n)\) is a formula.
5. If \(\phi\) is a formula and in \(\phi\) a token of \(\wedge\)occurs in the syntactic scope of a number of existential quantifierswhich include \((\exists y_1),\ldots ,(\exists y_n)\), the result ofreplacing in \(\phi\) that token of \(\wedge\) by \((\wedge /\existsy_1 ,\ldots ,\exists y_n)\) is a formula.

Clauses (2) and (3) allow the degenerate case that the list ofuniversal quantifiers is empty \((n = 0)\). The resulting expressions\((\exists x\)/) and \((\vee\)/) are identified with the usualexistential quantifier \((\exists x)\) and the usual disjunction\(\vee\), respectively. Similar stipulations are made about clauses(4) and (5).

In a suitable vocabulary, each of the following is a formula:

• \((\forall x)(\forall y)(\exists z/\forall x) R(x, y, z, v)\),
• \((\forall x)(\forall y)(P(x, y) \; (\vee /\forall x) \; Q(x,y))\),
• \((\exists x)(S(x) \; (\wedge /\exists x) \; T(x))\),
• \((\forall x)(\exists y)(\forall z/\exists y)(\exists v/\forall x)R(x, y, z, v)\).

By contrast, none of the following sequences of symbols is aformula:

• \((\exists y/\forall x) P(x, y)\),
• \((\exists x)(\exists y/\exists x) P(x, y)\),
• \((\forall x)(\forall y/\forall x) P(x, y)\),
• \((\forall x)(S(x) \; (\vee /\exists y) \; T(x))\).

If \(\phi\) is an \(\mathbf{IFL}\) formula, generated by the aboveclauses from some \(\mathbf{FO}\) formula \(\phi^*\), thefreevariables of \(\phi\) are simply the free variables of\(\phi^*\). \(\mathbf{IFL}\) formulas without free variables are\(\mathbf{IFL}\)sentences.^[18]

3.2. Semantics

Defining the semantics of a logic using GTS is a two-step process. Thefirst step is to define the relevantsemantic games. Thesecond step is to define the notions of ‘true’ and‘false’ in terms of the semantic games; this happens byreference to the notion ofwinning strategy. Semantic gamesmay be defined by specifying recursively the alternative ways in whicha game associated with a given formula \(\phi\) can be begun.^[19]

For every vocabulary \(\tau\), \(\mathbf{IFL}[\tau]\) formula \(\phi\),model \((\tau\) structure) \(M\), and variable assignment \(g\), atwo-player zero-sum game \(G(\phi , M, g)\) between player 1 andplayer 2 is associated.^[20] If \(g\) is a variable assignment, \(g[x/a]\) is the variableassignment which is otherwise like \(g\) but maps the variable \(x\)to the object \(a\).

1. If \(\phi = R(t_1 ,\ldots ,t_n)\) and \(M, g \vDash R(t_1 ,\ldots,t_n)\), player 2 wins (and player 1 loses); otherwise player 1 wins(and player 2 loses).
2. If \(\phi = {\sim}R(t_1 ,\ldots ,t_n)\) and \(M, g \not\vDashR(t_1 ,\ldots ,t_n)\), player 2 wins (and player 1 loses); otherwiseplayer 1 wins (and player 2 loses).
3. If \(\phi = (\psi \; (\wedge /\exists y_1 ,\ldots ,\exists y_n) \;\chi)\), player 1 chooses \(\theta \in \{\psi ,\chi \}\) and the restof the game is as in \(G(\theta , M, g)\).
4. If \(\phi = (\psi \; (\vee /\forall y_1 ,\ldots ,\forall y_n) \;\chi)\), player 2 chooses \(\theta \in \{\psi ,\chi \}\) and the restof the game is as in \(G(\theta , M, g)\).
5. If \(\phi = (\forall x/\exists y_1 ,\ldots ,\exists y_n)\psi\),player 1 chooses an element \(a\) from \(\rM\), and the rest of the game isas in \(G(\psi , M, g[x/a]\)).
6. If \(\phi = (\exists x/\forall y_1 ,\ldots ,\forall y_n)\psi\),player 2 chooses an element \(a\) from \(\rM\), and the rest of the game isas in \(G(\psi , M, g[x/a]\)).

Observe that the independence indications play no role in the gamerules. Indeed, quantifier independence will be implemented on thelevel of strategies.

If a token of \((\vee /\forall y_1 ,\ldots ,\forall y_n)\) or\((\exists x/\forall y_1 ,\ldots ,\forall y_n)\) appears in theformula \(\phi\) in the scope of the universal quantifiers \(\forally_1 ,\ldots ,\forall y_n,\forall z_1 ,\ldots ,\forall z_m\) (and onlythese universal quantifiers), astrategy function of player 2for this token in game \(G(\phi , M, g)\) is any function \(f\)satisfying the following:

The arguments of \(f\) are the elements\(a_1 ,\ldots ,a_m\) thatplayer 1 has chosen so as to interpret the quantifiers\(\forall z_1 ,\ldots ,\forall z_m\).The value \(f(a_1 ,\ldots ,a_m)\) is the left or the right disjunctwhen the token is a disjunction; and an element of the domain when thetoken is an existential quantifier.

The notion of the strategy function of player 1 for tokens of\((\wedge /\exists y_1 ,\ldots ,\exists y_n)\) and \((\forallx/\exists y_1 ,\ldots ,\exists y_n)\) can be defined dually. Strategyfunctions are construed as Skolem functions – the more generalnotion of strategy function operative in slash logic is not consideredhere (cf. the beginning ofSect. 3 andSubsect. 6.1). Quantifier indepenencewill be implemented directly in terms of thearguments of thestrategy functions.

Astrategy of player 2 in game \(G(\phi , M, g)\) is a set\(F\) of her strategy functions, one function for each token of\((\vee /\forall y_1 ,\ldots ,\forall y_n)\) and \((\exists x/\forally_1 ,\ldots ,\forall y_n)\) appearing in \(\phi\). Player 2 is saidtofollow the strategy \(F\), if for each token of \((\vee/\forall y_1 ,\ldots ,\forall y_n)\) and \((\exists x/\forall y_1,\ldots ,\forall y_n)\) for which she must make a move when game\(G(\phi , M, g)\) is played, she makes the move determined by thecorresponding strategy function. Awinning strategy forplayer 2 in \(G(\phi , M, g)\) is a strategy \(F\) such that againstany sequence of moves by player 1, following strategy \(F\) yields awin for player 2. The notions of strategy and winning strategy can besimilarly defined for player 1.^[21]

Thesatisfaction anddissatisfaction of the\(\mathbf{IFL}\) formula \(\phi\) in the model \(M\) under theassignment \(g\) are thendefined as follows:^[22]

• (Satisfaction) \(\phi\) is satisfied in \(M\)under \(g\) iff there is a winning strategy for player 2 in game\(G(\phi , M, g)\).
• (Dissatisfaction) \(\phi\) is dissatisfied in\(M\) under \(g\) iff there is a winning strategy for player1 in game \(G(\phi , M, g)\).

As with \(\mathbf{FO}\), variable assignments do not affect the(dis)satisfaction of sentences,i.e., formulas containing nofree variables. Indeed, we may define:^[23]

• (Truth) \(\phi\) is true in \(M\) iff there is awinning strategy for player 2 in game \(G(\phi , M)\).
• (Falsity) \(\phi\) is false in \(M\) iff there isa winning strategy for player 1 in game \(G(\phi , M)\).

The fact that \(\phi\) is true in \(M\) will be denoted by ‘\(M\vDash \phi\).’ Writing \(M \not\vDash \phi\) indicates, then,that \(\phi\) is not true in \(M\). This doesnot mean that \(\phi\) would in the above-defined sense be falsein \(M\). As mentioned in the end ofSection 2, thereare semantic games in which neither player has a winning strategy.

The syntax of \(\mathbf{IFL}\) can be generalized by removing therestriction according to which the negation sign may only appear asprefixed to an atomic formula.^[24]. In order to interpret negation in GTS, tworoles are addedas a new ingredient in the specification of the games: those of‘verifier’ and ‘falsifier.’ Initially player 1has the role of ‘falsifier’ and player 2 that of‘verifier.’ The roles may get switched, but only for onereason: when negation is encountered. All clauses defining semanticgames must be rephrased in terms of roles instead of players. It isthe player whose role is ‘verifier’ who makes a move fordisjunctions and existential quantifiers, and similarly the playerwhose role is ‘falsifier’ who moves for conjunctions anduniversal quantifiers. When a formula \({\sim}\psi\) is encountered, theplayers change roles and the game continues with \(\psi\). Finally, ifthe encountered atomic formula is true, ‘verifier’ winsand ‘falsifier’ loses, otherwise the payoffs are reversed.The negation \({\sim}\) is variably referred to asstrong negation,dual negation, orgame-theoretical negation.^[25] It works as one would expect: \(\phi\) is false in \(M\) iff itsnegation \({\sim}\phi\) is true therein (cf. Sandu 1993).

3.3. Basic properties and notions

Failure of bivalence. There are sentences \(\phi\) of\(\mathbf{IFL}\) and models \(M\) such that \(\phi\) is neither truenor false in \(M\). Consider evaluating the sentence \((\forallx)(\exists y/\forall x) x = y\) on a model whose domain has exactlytwo elements, \(a\) and \(b\). Player 1 has no winning strategy. If hechooses \(a\) to interpret \(\forall x\), he loses the play in whichplayer 2 chooses \(a\) to interpret \((\exists y/\forallx)\). Similarly, if player 1 chooses \(b\), he loses the play in whichplayer 2 likewise chooses \(b\). Neither does player 2 have a winningstrategy. Her strategy functions for \((\exists y/\forall x)\) areconstants (zero-place functions). There are two such constantsavailable: \(a\) and \(b\). Whichever one of these strategy functionsplayer 2 assumes, there is a move by player 1 defeating it. If player2 opts for \(a\), player 1 wins the play in which he chooses \(b\);and if player 2 applies \(b\), player 1 wins the play in which hechooses \(a\). Game \(G(\phi , M)\) isnon-determined:neither player has a winning strategy.^[26] The notion of non-determinacy may be extended to formulas as well:

• (Non-determinacy) \(\phi\) is non-determined in\(M\) under \(g\) iff there is no winning strategy for player 1, norfor player 2, in game \(G(\phi , M, g)\).

In \(\mathbf{IFL}\), falsity does not ensue from non-truth. Thatis, bivalence fails in \(\mathbf{IFL}\). However, it should benoted that it does not fail due to the postulation of a thirdtruth-value or a truth-value gap (cf. Hintikka 1991: 20, 55).^[27] Rather, the failure is a consequence of the basic assumptions of theentire semantic theory (GTS). Non-determinacy corresponds to astructural property: the fact that certain kinds of functions do notexist on the model considered.

Due to the failure of bivalence, the logical law of excluded middlefails for the dual negation \({\sim}\). Actually, \(\phi\) isnon-determined in \(M\) iff \(M \not\vDash(\phi\vee{\sim}\phi)\).

Logical equivalence. Sentences \(\psi\) and \(\chi\) of\(\mathbf{IFL}\) aretruth equivalent if they are true inprecisely the same models, andfalsity equivalent if they arefalse in precisely the same models. Sentences \(\psi\) and \(\chi\) arelogically equivalent if they are both truth equivalent andfalsity equivalent.^[28] Due to the failure of bivalence, in \(\mathbf{IFL}\) truthequivalence does not guarantee logical equivalence.

Truth, falsity, and independence indications. Thesyntax of \(\mathbf{IFL}\) allows formulas in which both universaland existential quantifiers appear slashed,e.g.,

On the other hand, quantifier independence is implemented at the levelof strategies. Consequently independence indications following auniversal quantifier are vacuous, when the satisfaction of a formula(truth of a sentence) is considered. Similarly, independenceindications following an existential quantifier are vacuous when thedissatisfaction of a formula (falsity of a sentence) is at stake. Thesentence \(\phi\) is true in the model \(M\) iff player 2 has awinning strategy \(F=\{c\}\) in game \(G(\phi , M)\). This, again,means that whichever elements \(a\) and \(b\) player 1 chooses tointerpret \((\forall x)\) and \((\forall z/\exists y)\), respectively,the constant interpretation \(c\) of \((\exists y/\forall x)\) givenby the (zero-place) strategy function \(c\) satisfies \(R(a, c, b)\)in \(M\). But this amounts to the same as requiring that whicheverelements \(a\) and \(b\) player 1 chooses to interpret \((\forall x)\)and \((\forall z)\), respectively, the constant interpretation \(c\)of \((\exists y/\forall x)\) satisfies \(R(a, c, b)\) in\(M\). Indeed, \(\phi\) is truth equivalent to a sentence containingno slashed universal quantifiers:

\(\phi\) is true in a model \(M\) iff the sentence \((\forallx)(\exists y/\forall x)(\forall z) R(x, y, z)\) is true in \(M\).

Similarly, \(\phi\) is falsity equivalent to a sentence containing noslashed existential quantifiers: \(\phi\) is false in a model \(M\)iff the sentence \((\forall x)(\exists y)(\forall z/\exists y) R(x, y,z)\) is false therein.

3.4. Extended IF first-order logic

If \(\phi\) is a sentence of \(\mathbf{FO}\), \(\phi\) is false in amodel \(M\) iff \({\sim}\phi\) is true in \(M\) iff \(\phi\) is nottrue in \(M\). By contrast, in \(\mathbf{IFL}\) falsity andnon-truth do not coincide. An extension of \(\mathbf{IFL}\) can beintroduced, where it is possible to speak of the non-truth ofsentences. To this end, let us introduce a new negation symbol, \(\neg\),referred to asweak negation,contradictory negationorclassical negation.^[29] The set of formulas ofextended IF first-order logic (to bedenoted \(\mathbf{EIFL})\) is obtained from the set of formulas of\(\mathbf{IFL}\) by closing it under the operations \(\neg\), \(\wedge\),and \(\vee\):^[30]

• All formulas of \(\mathbf{IFL}\) are formulas of\(\mathbf{EIFL}\).
• If \(\phi\) and \(\psi\) are formulas of \(\mathbf{EIFL}\), thenso are \(\neg \phi , (\phi \wedge \psi)\) and \((\phi \vee\psi)\).

So if \(\phi\) and \(\psi\) are \(\mathbf{IFL}\) formulas,e.g.\(\neg \phi\) and \((\neg \phi \vee \psi)\) are \(\mathbf{EIFL}\)formulas; by contrast \((\forall x)\neg \phi\) is not. For thecrucial restriction that \(\neg\) may not occur in the scope of aquantifier, see Hintikka (1991: 49; 1996: 148). For counterexamples tothis restriction see, however, Hintikka (1996: 148; 2002c) andespecially Hintikka (2006b) in which the so-calledfully extendedIF first-order logic (FEIFL) is considered. InFEIFL, any occurrences of \(\neg\) are allowed which aresubject to the following syntactic condition: if(Q\(x/W)\) is a quantifier in the syntactic scope of anoccurrence of \(\neg\), then all quantifiers listed in \(W\) arelikewise in the syntactic scope of that occurrence of \(\neg\).

The semantics of an \(\mathbf{EIFL}\) formula formed bycontradictory negation is simply this:

From the viewpoint of GTS, the connective \(\neg\) behaves in an unusualway. For all connectives of \(\mathbf{IFL}\), there is a game rule(which can be seen as specifying the meaning of the connective). Forcontradictory negation there is no game rule, and its semantics is notexplained in terms of plays of semantic games. A formula \(\neg \phi\)serves to say, globally, something about an entire game\(G(\phi , M, g)\). If \(\phi\) is a sentence, tosay that \(\neg \phi\) is true in \(M\) is to say that player 2 doesnot have a winning strategy in game \(G(\phi ,M)\). If, again, there is indeed a winning strategy for player2 in \(G(\phi , M)\), by stipulation \(\neg \phi\) is falsein \(M\).^[31]

Not only is \(\neg \phi\) not itself a formula of \(\mathbf{IFL}\),but it cannot in general even be expressed in \(\mathbf{IFL}\)(seeSubsect. 4.2). The law of excluded middle holds for thecontradictory negation: for all sentences \(\phi\) and all models\(M\), indeed \(M \vDash(\phi \vee \neg \phi)\). InSection 5 it will be seen how Hintikka has proposed to makeuse of \(\mathbf{EIFL}\) when discussing issues in the philosophyof mathematics.

4. Metalogical Properties of IF First-order Logic

The metalogical properties of \(\mathbf{IFL}\) have been discussedin several publications, by Hintikka as well as Sandu.^[32] When presenting them, reference will be made toexistentialsecond-order logic \((\mathbf{ESO})\);^[33] further important notions are those of theskolemization andSkolem normal form of an \(\mathbf{IFL}\) formula. Forprecise definitions of these notions,the supplementary document can be consulted. In brief, \(\mathbf{ESO}\) is obtained from\(\mathbf{FO}\) by allowing existential quantification overrelation and function symbols in a first-order formula. Theskolemization \(\mathrm{sk}[\phi]\) of an \(\mathbf{IFL}\) formula \(\phi\) isafirst-order formula of a larger vocabulary. It explicatesin terms of function symbols how existential quantifiers anddisjunction symbols of \(\phi\) depend on preceding universalquantifiers. For example, a skolemization of the \(\mathbf{IFL}\)sentence \(\phi = (\forall x)(\exists y)(\forall z)(\exists v/\forallx)R(x, y, z, v)\) of vocabulary \(\{R\}\) is the \(\mathbf{FO}\)sentence \(\mathrm{sk}[\phi] = (\forall x)(\forall z)R(x, f(x), z, h(z))\) ofvocabulary \(\{R, f, h\}\). Its Skolem normal form, again, is the\(\mathbf{ESO}\) sentence \(\mathrm{SK}[\phi] = (\exists f)(\exists h)(\forallx)(\forall z)R(x, f(x), z, h(z))\). The first-order sentence\(\mathrm{sk}[\phi]\) must not be confused with the second-order sentence\(\mathrm{SK}[\phi]\).

4.1. First-order logic and existential second-order logic

Game-theoretical vs. Tarskian semantics of FO. Theset of formulas of \(\mathbf{FO}\) is a proper subset of the setof \(\mathbf{IFL}\) formulas. The standard semantics of\(\mathbf{FO}\) is not the one provided by GTS, but the Tarskiansemantics specifying recursively the satisfaction relation \(M,g \vDash \phi\). If theAxiom of Choice is assumed,^[34] the two semantics of \(\mathbf{FO}\) coincide:

Theorem (assuming AC). (Hodges 1983: 94, Hintikka& Kulas 1985: 6–7) Let \(\tau\) be any vocabulary, \(M\)any \(\tau\) structure, \(g\) any variable assignment and \(\phi\) any\(\mathbf{FO}[\tau]\) formula. Then \(M, g \vDash \phi\) holds in the standard sense iff there is a winningstrategy for player 2 in game \(G(\phi , M, g)\).^[35]

Relation to ESO.\(\mathbf{IFL}\) and \(\mathbf{ESO}\) are intertranslatable:^[36]

Theorem(assuming AC)\(\mathbf{ESO}\) and \(\mathbf{IFL}\) have the same expressivepower.

That is, (1) for every \(\mathbf{IFL}[\tau]\) formula \(\phi\) thereis an \(\mathbf{ESO}[\tau]\) formula \(\phi'\) such that for all\(\tau\) structures \(M\) and variable assignments \(g\), we have:\(M, g \vDash \phi\) iff \(M, g \vDash \phi'\). Actually,\(\mathrm{SK}[\phi]\) is a suitable \(\mathbf{ESO}\) formula. And (2)for every \(\mathbf{ESO}[\tau]\) formula \(\psi\) there is an\(\mathbf{IFL}[\tau]\) formula \(\psi'\) such that \(M, g \vDash\psi\) iff \(M, g \vDash \psi'\), for all \(\tau\) structures \(M\)and variable assignments \(g\). This follows from the fact that\(\mathbf{ESO}\) can be translated into \(\mathbf{FPO}\) (Enderton1970, Walkoe 1970), which again can be translated into\(\mathbf{IFL}\).

Hintikka suggests that \(\mathbf{IFL}\) is, substantiallyspeaking, afirst-order logic: the entities its quantifiedvariables range over areindividuals, and so are all entitieswith which the players of the semantic games operate. (SeeSubsect. 5.1 for a discussion of this idea.) A part of theinterest of the intertranslatability theorem lies in the fact that ifHintikka’s controversial claim is accepted, this would mean thatthe expressive power of \(\mathbf{ESO}\) can actually be achievedon the first-order level.

IFL is more expressive than FO. The following areexamples of properties expressible in \(\mathbf{ESO}\) but not in\(\mathbf{FO}\): infinity of the domain, non-completeness of alinear order, ill-foundedness of a binary relation, disconnectednessof a graph, equicardinality of the extensions of two first-orderformulas \(\phi(x)\) and \(\psi(x)\), infinity of theextension of a first-order formula \(\phi(x)\), and thetopological notion of open set (see,e.g., Hintikka 1996,Väänänen 2007). When attention is restricted tofinite models, Ronald Fagin’s famous theorem (1974)connects \(\mathbf{ESO}\) and the complexity class\(\mathbf{NP}\): a computational problem is solvable by analgorithm running in non-deterministic polynomial time iff it isdefinable in \(\mathbf{ESO}\) relative to the class of all finitestructures. The following are \(\mathbf{NP}\)-complete propertiesand hence expressible in \(\mathbf{IFL}\), over the class of allfinite models: evenness of the domain, oddness of the domain,3-colorability of a graph, and the existence of a Hamiltonian path ona graph.^[37]

As an example the Dedekind-infinity of the domain may be considered. Aset \(S\) is Dedekind-infinite precisely when there exists aninjective function from \(S\) to its proper subset. Let\(\phi_{inf}\) be the following sentence of \(\mathbf{IFL}\):^[38]

The Skolem normal form of \(\phi_{inf}\) is

Relative to a model \(M\) this\(\mathbf{ESO}\) sentence asserts the existence of functions \(f\) and\(g\) and an element \(t\) such that \(f = g\) (implication from leftto right), this function is injective (implication from right toleft), and its domain is the whole domain of \(M\) but the element\(t\) does not appear in its range. Consequently the range is a propersubset of the domain of \(M\). In other words, the sentence\(\phi_{inf}\) is true in a model \(M\) iff the domain of \(M\) isinfinite.

Properties in common with FO. IF first-order logicshares many metalogical properties with first-order logic.^[39]

Compactness. A set of \(\mathbf{IFL}\) sentenceshas a model iff all its finite subsets have a model.

Löwenheim-Skolem property. Suppose \(\phi\) is an\(\mathbf{IFL}\) sentence that has an infinite model, orarbitrarily large finite models. Then \(\phi\) has models of all infinitecardinalities.

The separation theorem holds in \(\mathbf{IFL}\) in a strengthenedform; the ‘separation sentence’ \(\theta\) is in particular asentence of \(\mathbf{FO}\).

Separation theorem. Suppose \(\phi\) is an\(\mathbf{IFL}\) sentence of vocabulary \(\tau\), and \(\psi\) an\(\mathbf{IFL}\) sentence of vocabulary \(\tau'\). Suppose furtherthat \(\phi\) and \(\psi\) have no models in common. Then there is afirst-order sentence \(\theta\) of vocabulary \(\tau \cap \tau'\) such that every model of \(\phi\) is a model of \(\theta\), but\(\theta\) and \(\psi\) have no models in common.

It is well known that for \(\mathbf{FO}\) there is a sound andcomplete proof procedure. Because a first-order sentence \(\phi\) isinconsistent (non-satisfiable) iff its negation \({\sim}\phi\) is valid (truein all models), trivially \(\mathbf{FO}\) also has a sound andcomplete disproof procedure.^[40] The latter property extends to \(\mathbf{IFL}\) (while the formerdoes not, seeSubsect. 4.3):

Existence of a complete disproof procedure. The setof inconsistent \(\mathbf{IFL}\) sentences is recursivelyenumerable.

4.2. Intricacies of negation

InSubsection 3.4, the contradictory negation \(\neg\) wasdistinguished from the strong negation \({\sim}\). In \(\mathbf{FO}\)the two coincide: for any first-order sentence \(\phi\), we have \(M\vDash{\sim}\phi\) iff \(M \vDash \neg \phi\).

Strong negation fails as a semantic operation. Let uswrite \([\phi]\) for the set of models of sentence \(\phi\). In the specialcase of \(\mathbf{FO}\), the strong negation \({\sim}\) clearly defines asemantic operation: whenever \(\chi\) and \(\theta\) are sentences such that\([\chi] = [\theta]\), we have \([{\sim}\chi] = [{\sim}\theta]\). Burgess (2003)observed that in the context of IF logic this property is lost in avery strong sense. In fact there are IF sentences \(\chi\) and \(\theta\)such that while \([\chi] = [\theta]\), the sets \([{\sim}\chi]\) and \([{\sim}\theta]\)are not only distinct but even disjoint.

Inexpressibility of contradictory negation. In\(\mathbf{IFL}\) the strong negation \({\sim}\) and the contradictorynegation \(\neg\) donot coincide: we may have \(M \vDash\neg \phi\) without having \(M \vDash{\sim}\phi\). This fact by itselfstill leaves open the possibility that the contradictory negation ofevery sentence \(\phi\) of \(\mathbf{IFL}\) could be defined in\(\mathbf{IFL}\),i.e., that there was a sentence\(neg(\phi)\) of \(\mathbf{IFL}\) such that \(M \vDash\) \(neg(\phi)\)iff \(M \not\vDash \phi\), for all models \(M\). All we know by thefailure of the law of excluded middle is that not in all cases can\(neg(\phi)\) be chosen to be \({\sim}\phi\). However, as a matter offact contradictory negation is inexpressible in\(\mathbf{IFL}\). There are sentences \(\phi\) of \(\mathbf{IFL}\)such that \(\neg \phi\) (which is a sentence of \(\mathbf{EIFL})\) isnot truth equivalent to any sentence of \(\mathbf{IFL}\). This followsfrom the well-known fact that \(\mathbf{ESO}\) is not closed undernegation and \(\mathbf{IFL}\) has the same expressive power as \(\mathbf{ESO}\).^[41]

Strong inexpressibility of contradictory negation. Asa corollary to the separation theorem, the result holds in a muchstronger form. If \(\phi\) and \(\psi\) are sentences of\(\mathbf{IFL}\) such that \(M \vDash \phi\) iff \(M \not\vDash\psi\), then each of \(\phi\) and \(\psi\) is truth equivalent to asentence of \(\mathbf{FO}\). Hence the contradictory negation \(\neg\phi\) is only expressible in \(\mathbf{IFL}\) for those\(\mathbf{IFL}\) sentences \(\phi\) that are truth equivalent to an\(\mathbf{FO}\) sentence.^[42]

Determined fragment. Let us say that an\(\mathbf{IFL}\) sentence \(\phi\) isdetermined if itsatisfies: \(M \vDash(\phi \vee{\sim}\phi)\), for all models\(M\). Thedetermined fragment of \(\mathbf{IFL}\)is the set of determined \(\mathbf{IFL}\) sentences. In thedetermined fragment contradictory negationis syntacticallyexpressible by the strong negation. By the strong inexpressibility ofcontradictory negation, the determined fragment of\(\mathbf{IFL}\) has the same expressive power as\(\mathbf{FO}\). Membership in the determined fragment is asufficient but not necessary condition for an \(\mathbf{IFL}\)sentence to have its contradictory negation expressible in\(\mathbf{IFL}\). The sentence\((\forall y)(\exists x/\forall y) x = y\) is not determined;^[43] yet its contradictory negation \((\forall x)(\exists y) x \ne y\) isexpressible in \(\mathbf{IFL}\).

Contradictory negation and GTS. The truth-conditionsthat GTS yields are of the form ‘there are strategy functions\(f_1 ,\ldots ,f_n\) suchthat —,’i.e., it gives rise to truth-conditionsexpressible in \(\mathbf{ESO}\). By the strong inexpressibility ofcontradictory negation, there is no single \(\mathbf{IFL}\)sentence, not translatable into \(\mathbf{FO}\), whosecontradictory negation has a truth-condition of that form. This factmakes it understandable why contradictory negation should not beexpected to admit of a game-theoretical interpretation along the samelines in which the other logical operators are interpreted. Differentways of assigning a game-theoretical interpretation to contradictorynegation can, however, be developed. To this end, in the context offully extended IF first-order logic (FEIFL,cf. Subsect. 3.4), Hintikka has proposed to use semantic games withsubgames. (See Hintikka 2002c, 2006b; for subgames, seeCarlson & Hintikka 1979, Hintikka & Kulas 1983.) This approachleads to mixing the play level with the strategy level: choices ofindividuals made in a subgame may depend on strategy functions chosenin earlier subgames. In Tulenheimo (2014), a game-theoreticalsemantics is formulated for the fragment ofFEIFLthat consists of formulas in prenex form. Plays of the correlatedgames do not involve choosing any second-order objects, such asstrategy functions. Contradictory negation \((\neg)\) is interpreted byintroducing an additional component in game positions: amode. At the play level, the negation \(\neg\) triggers not only arole switch (like the dual negation \({\sim})\), but it also involves changingthe mode from positive to negative or vice versa. The semantic effectof modes becomes visible at the strategy level: modes regulate the wayin which the truth condition of a sentence involves existentially oruniversally quantifying over strategy functions. Like independenceindications, also occurrences of \(\neg\) are, then, interpreted in terms ofconditions that act on the strategy level. For related research, seeFigueiraet al. (2011).

Contradictory negation and finite models. Certainmajor open questions in logic and theoretical computer science can beformulated in terms of \(\mathbf{IFL}\). It is an open question incomplexity theory whether \(\mathbf{NP} = \mathbf{coNP}\),that is, whether the class of \(\mathbf{NP}\)-solvable problems isthe same as the class of problems whose complement is solvable in\(\mathbf{NP}\). By Fagin’s theorem (1974), this openproblem can be equivalently formulated as follows: Is\(\mathbf{IFL}\) closed under negationover finitemodels? That is, is there for every IF sentence \(\phi\) another IFsentence \(neg(\phi)\) such that for any finite model\(M\), \(neg(\phi)\) is true in \(M\) iff \(\phi\) is nottrue in \(M\)? Proving that the answer is negative would settlethe notorious \(\mathbf{P} = \mathbf{NP}\) problem, i.e.,establish that there are computational problems for which one canefficientlyverify whether a proposed solution is correctalthough one cannot efficientlyfind a solution.^[44]

4.3 Failure of axiomatizability

As is well known, \(\mathbf{FO}\) admits of a sound and completeproof procedure: there is a mechanical way of generating preciselythose first-order sentences that are valid (true in all models). Thisfact can also be expressed by saying that \(\mathbf{FO}\) isaxiomatizable, or that the set of valid sentences of\(\mathbf{FO}\) is recursively enumerable.^[45] Due to its greater expressive power, axiomatizabilityfailsfor \(\mathbf{IFL}\). In other words, \(\mathbf{IFL}\) issemantically incomplete.^[46]

One way to show this is as follows. Suppose for the sake ofcontradiction that the set of valid \(\mathbf{IFL}\) sentences isrecursively enumerable. Recall that the sentence\(\phi_{inf}\) discussed inSubsection 4.1 istrue in all and only infinite models. Note, then, that an\(\mathbf{FO}\) sentence \(\chi\) is true in allfinitemodels iff the \(\mathbf{IFL}\) sentence\((\phi_{inf} \vee \chi)\) is valid. Given a valid\(\mathbf{IFL}\) sentence, it can be effectively checked whetherthe sentence is syntactically of the form\((\phi_{inf} \vee \chi)\), where \(\chi\) is afirst-order sentence. Hence the recursive enumeration of all valid\(\mathbf{IFL}\) sentences yields a recursive enumeration offirst-order sentences \(\chi\) true in all finite models. But thiscontradicts Trakhtenbrot’s theorem, according to which the setof \(\mathbf{FO}\) sentences true in all finite models isnot recursively enumerable.^[47]

What is the relevance of the failure of axiomatizability of\(\mathbf{IFL}\)? Discussing finite partially ordered quantifiers,Quine (1970: 89–91) suggests that we should refuse to give thestatus of logic to any generalization of \(\mathbf{FO}\) whichdoes not have a sound and complete proof procedureboth forvalidityand for inconsistency. For Quine, any suchgeneralization belongs to mathematics rather than logic. Since\(\mathbf{FPO}\) is not axiomatizable, it falls outside the realmof logic, thus delineated.^[48]

Hintikka finds this type of allegation unfounded. First,\(\mathbf{IFL}\) shares many of the important metalogical resultswith \(\mathbf{FO}\) (cf.Subsect. 4.1). Second, justlike \(\mathbf{IFL}\), also \(\mathbf{FO}\) can be translatedinto second-order logic. The only difference is that in the formercase a larger variety of quantifier (in)dependencies must be encodedby Skolem functions than in the latter. Why would the formertranslation render \(\mathbf{IFL}\) a part of mathematics whilethe latter would allow \(\mathbf{FO}\) to remain a logic (Hintikka1991: 26–27)? Third, one must make a distinction between what isneeded to understand an \(\mathbf{IFL}\) sentence, and what isneeded to mechanically deal with the validities (logical truths) of\(\mathbf{IFL}\). Due to its non-axiomatizability, there are nomechanical rules for generating the set of all validities of\(\mathbf{IFL}\). However, to understand a sentence is to knowwhat things are like when it istrue, not to know what thingsare like when it islogically true (Hintikka 1995:13–14). Fourth, because of non-axiomatizability, the validinference patterns in \(\mathbf{IFL}\) cannot be exhausted by anyrecursive enumeration. Insofar as important mathematical problems canbe reduced to questions about the validity of \(\mathbf{IFL}\)formulas (Subsect. 5.3), progress in mathematics can be seento consist (not of the discovery of stronger set-theoretical axiomsbut) of ever more powerful rules for establishing validity in\(\mathbf{IFL}\) (Hintikka 1996: 100; 2000: 135–136).

4.4 Compositionality and the failure of Tarski-type semantics

The principle of compositionality (a.k.a. Frege principle) states thatsemantic attributes of a complex expression \(E\) are determinedby the semantic attributes of its constituent expressions and thestructure of \(E\). In particular, the semantic attribute ofinterest (e.g., truth) may be determined in terms of one ormore auxiliary semantic attributes (e.g., satisfaction).^[49] Hintikka has argued that compositionality amounts tosemanticcontext-independence: semantic attributes of a complex expressiondependonly on the semantic attributes of its constituentexpressions, plus its structure – they donot depend onthe sentential context in which the expression is embedded. Semanticcontext-independence makes it possible to carry out semantic analysisfrominside out – from simpler expressions to morecomplex ones.^[50] This is what is needed for recursive definitions of semanticattributes – such as Tarski-type definitions of truth andsatisfiability – to be possible.^[51] By contrast, the GTS analysis of sentences is anoutside inprocess: a semantic game starts with an entire sentence, and stepwiseanalyzes the sentence into simpler and simpler components, eventuallyreaching an atomic formula (together with an appropriate variableassignment). Therefore GTS allows accounting for semanticcontext-dependencies that violate the principle of compositionality.^[52]

In \(\mathbf{IFL}\) an existential quantifier may depend only onsome of the universal quantifiers in whose scope it lies.Accordingly, its interpretation depends on its relation to quantifiersoutside its own scope. Such an existential quantifier is context-dependent.^[53] On the face of it, then, \(\mathbf{IFL}\) cannot but violate theprinciple of compositionality and does not admit of a Tarski-typetruth-definition.

Hodges (1997a,b) showed, however, that \(\mathbf{IFL}\) can begiven a compositional semantics.^[54] The semantics is given by recursively defining the satisfactionrelation ‘\(M \vDash_X \phi\)’(read: \(\phi\) is satisfied in \(M\) by \(X)\), where\(X\) is aset of variable assignments. While theTarskian semantics for \(\mathbf{FO}\) is in terms of singlevariable assignments, Hodges’s semantics employs sets ofvariable assignments. The game-theoretical semantics of\(\mathbf{IFL}\) is captured by this compositional semantics: forevery formula \(\phi\) of \(\mathbf{IFL}\), player 2 has a winningstrategy in \(G(\phi , M, g)\) iff thecondition \(M \vDash_{\{g\}} \phi\) holds.Hintikka remarks (2006a: 65) that if one is sufficiently ruthless, onecan always save compositionality by building the laws of semanticinteraction of different expressions into the respective meanings ofthose expressions.^[55]

It is methodologically worth pointing out that compositionality is notneeded for defining \(\mathbf{IFL}\). The very existenceof \(\mathbf{IFL}\) proves that rejecting compositionality is noobstacle for the formulation of a powerful logic (Hintikka 1995). Itshould also be noted that what makes Hodges’s result work is itstype-theoretical ascent. Let us say that aTarski-typecompositional semantics is a compositional semantics which interpretseach formula \(\phi(x_1 ,\ldots ,x_n)\) of \(n\) free variables in terms of an\(n\)-tuple of elements of the domain. Hence the standardsemantics of \(\mathbf{FO}\) is Tarski-type, but Hodges’ssemantics employing the satisfaction relation ‘\(M \vDash_X \phi\)’ is not, because the latterevaluates a formula \(\phi(x_1 ,\ldots ,x_n)\) of \(n\) free variables relative to anentireset of \(n\)-tuples of elements. Cameron &Hodges (2001) proved that actually there is \(no\) Tarski-typecompositional semantics for \(\mathbf{IFL}\).

The notion of compositionality can be refined by imposing constraintson the auxiliary semantic attributes. Sandu and Hintikka (2001: 60)suggested, by analogy with \(\mathbf{FO}\), that‘satisfaction by a single variable assignment’ would be anatural auxiliary attribute in connection with \(\mathbf{IFL}\).By the result of Cameron and Hodges, no semantics for\(\mathbf{IFL}\) exists that would be compositional in thisrestricted sense.

4.5 Defining truth

The definability of truth can only be discussed in connection withlanguages capable of speaking of themselves. Let us consider anarithmetical vocabulary \(\tau\) and restrict attention to the standardmodel \(N\) of Peano’s axioms. Each sentence \(\phi\) ofvocabulary \(\tau\) can then be represented by a natural number\(\ulcorner \phi \urcorner\), its Gödel number. Itis assumed that \(\tau\) contains a numeral\(\boldsymbol{{}^\ulcorner \phi {}^\urcorner}\) for eachnumber \(\ulcorner \phi \urcorner\). If \(L\) and\(L'\) are abstract logics of vocabulary \(\tau\), such as\(\mathbf{FO}\) or \(\mathbf{IFL}\), and\(\TRUE(x)\) is a formula of \(L'\) such thatevery sentence \(\phi\) of \(L\) satisfies:

then \(\TRUE(x)\) is said to be atruth-predicate (explicittruth-definition) of logic \(L\) in logic\(L'\) for the model \(N\). By Alfred Tarski’sfamous theorem of theundefinability of truth (Tarski 1933),there is no truth-predicate for \(\mathbf{FO}\) in\(\mathbf{FO}\) itself for the model \(N\). More generally,Tarski showed that under certain assumptions, a truth-definition for alogic \(L\) can only be given in a metalanguage which isessentially stronger than \(L\). One of the assumptions is thatthe negation used behaves like contradictory negation. On the otherhand, Tarski also pointed out that an implicit truth-definition for\(\mathbf{FO}\) in \(\mathbf{FO}\) itselfispossible. Let \(\tau\) be an arithmetical vocabulary, and let us staywith the standard model \(N\) of Peano’s axioms. Let‘\(\TRUE\)’ be a unary predicate not appearing in\(\tau\). An \(\mathbf{FO}\) formula \(\psi(x)\) of vocabulary\(\tau \cup \{\TRUE\}\) is animplicit truth-definitionfor \(\mathbf{FO}[\tau]\) in \(\mathbf{FO}[\tau \cup \{\TRUE\}]\) for \(N\), if for every\(\mathbf{FO}[\tau]\) sentence \(\phi\), the following holds:

\(N \vDash \phi\) iff there is an interpretation\(\TRUE^N\) of the unary predicate \(\TRUE\) such that \((N, \TRUE^N ) \vDash \psi(\boldsymbol{{}^\ulcorner \phi {}^\urcorner})\).^[56]

Intuitively, \(\TRUE^N\) is the set of thosenatural numbers that are Gödel numbers of true arithmeticsentences of vocabulary \(\tau\); and \(\psi(x)\) says that\(x\) is a Gödel number in the extension of the predicate\(\TRUE\). The formula \(\psi(x)\) is a conjunctionincluding clauses that mimic, on the object-language level, themetalogical recursive clauses of the Tarski-type truth-definition for\(\mathbf{FO}\).E.g., one of the conjuncts is

The implicit nature of the truth-definition is seen from the fact thatthe predicate \(\TRUE\) appears on both sides of the equivalencesign in these clauses.^[57] The above implicit truth-definition of \(\mathbf{FO}\) for \(N\) isof the form ‘there is a set \(S\) interpreting thepredicate \(\TRUE\) such that \(\psi(x)\).’ Thus theimplicit truth-definition of \(\mathbf{FO}\) in \(\mathbf{FO}\) givesrise to the explicit truth-definition \(\exists \TRUE\, \psi(x)\) of\(\mathbf{FO}[\tau]\) in \(\mathbf{ESO}[\tau]\) for \(N\). Since\(\mathbf{ESO}\) and \(\mathbf{IFL}\) have the same expressive power,a truth-predicate of \(\mathbf{FO}\) for \(N\) can be formulated in\(\mathbf{IFL}\).

The same reasoning can be applied to \(\mathbf{ESO}\) itself, andthereby to \(\mathbf{IFL}\) (Hintikka 1991, 1996; Hyttinen & Sandu2000; Sandu 1996, 1998). Namely, an \(\mathbf{ESO}\) formula\(\chi(x)\) of vocabulary \(\tau \cup \{\TRUE\}\) can be formulatedwhich is animplicit truth-definition of\(\mathbf{ESO}[\tau]\) for \(N\). Therefore the \(\mathbf{ESO}[\tau]\)formula \(\exists \TRUE\, \chi(x)\) is anexplicittruth-definition of \(\mathbf{ESO}[\tau]\) for \(N\). Here thetruth-predicate is formulated in the very same language whose notionof truth is being defined: \(\mathbf{ESO}\). Hence \(\mathbf{ESO}\),and thereby \(\mathbf{IFL}\), is capable of explicitly defining itsown truth-predicate relative to \(N\).^[58] This result does not contradictTarski’s undefinability result, because here non-determinedsentences are possible; the negation used is not contradictorynegation.^[59]

Tarski (1983) adopted a view accoding to which truth cannot be definedfor natural languages. It has been argued in Hintikka & Sandu(1999) that this was due to Tarski’s belief thatcompositionality fails in natural languages.^[60] \(\mathbf{IFL}\) does not have a Tarski-type compositionalsemantics, but it admits of formulating a self-appliedtruth-predicate. The proposed reason why Tarski believed it not to bepossible to discuss the notion of truth in natural languagesthemselves, cannot be entertained from the viewpoint of \(\mathbf{IFL}\).^[61]

4.6 Properties of extended IF first-order logic

Expressive power. Since \(\mathbf{IFL}\) is notclosed under contradictory negation, \(\mathbf{EIFL}\) is strictlymore expressive than \(\mathbf{IFL}\) (cf.Subsect. 4.2).^[62] The following properties are expressible in \(\mathbf{EIFL}\) butnot in \(\mathbf{IFL}\) (Hintikka 1996: 188–190): finitenessof the domain, well-foundedness of a binary relation, connectedness ofa graph, principle of mathematical induction, Bolzano-Weierstrasstheorem, and the topological notion of continuity.

Metalogical properties. The nice metatheorems that\(\mathbf{IFL}\) shares with \(\mathbf{FO}\) are lost:Compactness, Löwenheim-Skolem property, separation theorem, andthe existence of a complete disproof procedure all fail for\(\mathbf{EIFL}\) (Hintikka 1991: 49, 1996: 189). No self-appliedtruth-predictate is possible for \(\mathbf{EIFL}\). The definitionof such a truth-predicate would have to contain the clause

But this clause is not a well-formed formula of \(\mathbf{EIFL}\),since \(\neg\) appears in the scope of the universal quantifier\((\forall y)\) (cf. Hintikka 1996: 151).

The validity problem of the full second-order can be effectivelyreduced to the validity problem of \(\mathbf{EIFL}\). Namely, whycannot a second-order sentence simply be thought of as a two-sortedfirst-order sentence? Because in order to capture the standardinterpretation of second-order logic,^[63] it must be said that for every extensionally possible set of\(n\)-tuples of elements of sort 1 there exists a member of sort2 having those and only those elements as members, for all arities\(n\) such that the second-order sentence contains a quantifier\((\exists R)\) where \(R\) is \(n\)-ary.^[64] Such additional conditions can be expressed by a finite conjunction\(X\) of contradictory negations of \(\mathbf{ESO}\)sentences. So there is an \(\mathbf{ESO}\) sentence \(Y\)such that \(X\) itself is logically equivalent to\(\neg Y\). Therefore, if \(\phi\) is a second-order sentence and\(\phi^*\) its reconstruction in two-sorted first-order logic, we have:\(\phi\) is valid iff \((\neg X \vee \phi^*)\) is valid iff\((Y \vee \phi^*)\) is valid. The validity of \((\neg X \vee \phi^*)\) means that \(\phi^*\) is a logical consequence of \(X\).Because \(Y\) is an \(\mathbf{ESO}\) sentence, it can beexpressed in \(\mathbf{IFL}\). It follows that the validity of anysecond-order sentence can be expressed as the validity of a sentenceof \(\mathbf{IFL}\).^[65]

Algebraic structure. The two negations available in\(\mathbf{EIFL}, \neg\) and \({\sim}\), agree on true sentences, as wellas on false ones: if \(\phi\) is true (false) in \(M\), then both\({\sim}\phi\) and \(\neg \phi\) are false (true) in \(M\). By contrast, if\(\phi\) is non-determined in \(M\), then \({\sim}\phi\) is non-determinedas well, but \(\neg \phi\) is true. The combination \(\neg{\sim}\) of the twonegations applied to a sentence \(\phi\) asserts that \(\phi\) is not false.^[66]

The propositional part of \(\mathbf{EIFL}\) involves the fouroperators \(\neg , {\sim}, \wedge\), and \(\vee\). Hintikka (2004b) raises thequestion of the algebraic structure induced by these operators, whenany two truth equivalent sentences are identified. The operators\(\neg , \wedge\), and \(\vee\) give rise to a Boolean algebra – but whatdoes the strong negation \({\sim}\) add to this structure?

Restricting attention to truth equivalence, \({\sim}\) is definable from theoperators \(\neg\) and \(\neg{\sim}\). For, \({\sim}\phi\) is true in \(M\) iff\(\neg(\neg{\sim}\phi)\) is true in \(M\). Instead of \({\sim}\), the operator\(\neg{\sim}\) may then be considered. Hintikka points out that thepropositional part of \(\mathbf{EIFL}\) (formulated in terms ofthe operators \(\vee , \wedge , \neg\) and \(\neg{\sim})\) is a Boolean algebra withan operator in the sense of Jónsson & Tarski (1951). Theadditional operator \(\neg{\sim}\) is a closure operator.

Jónsson and Tarski (1951, Thm. 3.14) showed that any closurealgebra is isomorphic to an algebraic system formed by a set equippedwith a reflexive and transitive relation.^[67] As a matter of fact, the relevant algebraic structure is preciselythat of the propositional modal logic \(\mathbf{S4}\). Hence thepropositional part of \(\mathbf{EIFL}\) has the same algebraicstructure as \(\mathbf{S4}\). By a well-known result due toGödel (1933) and McKinsey & Tarski (1948), intuitionisticpropositional logic can be interpreted in \(\mathbf{S4}\), via atranslation \(t\) such that \(\phi\) is intuitionistically provableiff \(t(\phi)\) is a valid \(\mathbf{S4}\) formula. Thus,intuitionistic propositional logic is interpretable in \(\mathbf{EIFL}\).^[68]

5. Philosophical Consequences

Hintikka (2006a: 73–77) takes the following to be amongconsequences of the novel insights made possible by (extended) IFfirst-order logic: reconstruction of normal mathematical reasoning onthe first-order level, a novel perspective on the notion of truth inaxiomatic set theory, insights into the nature of negation, and theformulation of a self-applied truth-predicate. A related topic ofgeneral interest is the phenomenon of informational independence innatural languages. The ideas related to negation and definability oftruth have been discussed inSubsections 4.2 and 4.5,respectively. Let us consider here the remaining issues.

5.1 Place in type hierarchy

Hintikka maintains that the only reasonable way of making adistinction between first-order logic and higher-order logic is byreference to the entities that one’s quantified variables rangeover. A first-order logic is, then, a logic in which all quantifiersrange over individuals, in contrast to higher-order entities(e.g., subsets of the domain). On this basis Hintikka holdsthat substantially speaking, \(\mathbf{IFL}\) and even\(\mathbf{EIFL}\) arefirst-order logics.^[69] Solomon Feferman (2006: 457–461) criticizes the criterion thatHintikka employs for judging the first-order status of a logic.Feferman makes use of generalized quantifiers in his argument.^[70] The formulas

involving generalized quantifiers aresyntacticallyfirst-order, insofar as the quantified variables \(z_{i1},\ldots,z_{in_i} = [z_i]\) are first-order \((1 \le i \le k)\). The semanticsof a generalized quantifier \(Q\) is formulated by associating witheach domain M a \(k\)-ary relation \(Q_M\) on M, with \(Q_M\subseteq\) M\(^{n_1} \times \ldots \times\)M\(^{n_k}\).E.g., for any infinite cardinal \(\kappa\),there is a generalized quantifier \(Q_{\ge \kappa}\) such that\(Q_{\ge \kappa}z P(z)\) is true in a model \(M\) iff there are atleast \(\kappa\) elements that satisfy the predicate \(P\). Hencegeneralized quantifiers can besemantically higher-order. Thefact that the variables in a formula range over individuals only, doesnot offer a reliable criterion for the logic’s first-orderstatus.

Hintikka’s criterion could be reformulated by saying that alogic is of first order, if anyplay of a semantic gameassociated with a formula of this logic only involves (in addition tochoices interpreting conjunctions and disjunctions) choices ofindividuals, as opposed to choices of higher-order entities. By thiscriterion \(\mathbf{IFL}\) (and even \(\mathbf{EIFL})\) arefirst-order logics, but the logic of generalized quantifiers such as\(Q_{\ge \kappa}\) is not.^[71] Feferman (2006: 461) anticipates the possibility of such a reply, butfinds it unconvincing.

By a result of Hintikka (1955), the problem of deciding whether asentence of second-order logic is valid can be effectively reduced tothe validity problem of \(\mathbf{IFL}\).^[72] Väänänen (2001) has shown that the set of validsentences of \(\mathbf{IFL}\) has the same very high complexity asthe set of validities of the full second-order logic.^[73] Väänänen (2001) and Feferman (2006) conclude thatspeaking of validity in \(\mathbf{IFL}\) leads to a strongcommitment to full second-order logic. Hintikka (2006a: 476–477)looks at these results from the opposite direction: for him they meanthat indeed one can speak of validity in full second-order logic interms of validity in \(\mathbf{IFL}\). What is more, Hintikka(1997) affirms that even \(\mathbf{EIFL}\) is a first-order logic.If so, any mathematical theory that can be expressed by the truth ofan \(\mathbf{EIFL}\) sentence is likewise free from problems ofset existence.

Hintikka’s position leads to a puzzle. If \(\phi\) is a sentence of\(\mathbf{IFL}\) not truth equivalent to any \(\mathbf{FO}\)sentence, the truth-condition of the sentence \(\neg \phi\) of\(\mathbf{EIFL}\) cannot be formulated without recourse to the setof all strategies of player 2: \(\neg \phi\) is true in model \(M\)iff for all strategies of player 2 in game \(G(\phi ,M)\), there is a sequence of moves by player 1 such that player1 wins the resulting play. The set of all strategies of player 2 isundeniably a higher-order entity. How can commitment to entities otherthan individuals be said to have been avoided here? Can the meaning ofthe sentence \(\neg \phi\) be well understood without presupposing thegenuinely second-order idea of all strategies of a given player?^[74] Rather than being nominalistic, Hintikka’s position appears tobe a variant ofuniversalia in rebus. While rules of semanticgames pertain to actions performed on first-order objects,combinatorial properties of sets of plays can only be formulated insecond-order terms. As soon as game rules are defined for a languagefragment, also the corresponding combinatorial properties are fullydetermined, among them the properties labeled as truth andfalsity.

5.2 Philosophy of set theory

According to Hintikka, our pretheoretical idea of the truth of aquantified sentence \(\phi\) (in negation normal form) is that thereexist ‘witness individuals’ for the existentialquantifiers, usually depending on values corresponding to thepreceding universal quantifiers.^[75] It is the existence of such witnesses that constitutes the truth of\(\phi\). Providing witnesses is precisely what Skolem functions for\(\phi\) do.^[76] The truth of a quantified sentence \(\phi\) amounts to the existence ofa full set of Skolem functions for \(\phi\). In Hintikka’s view,then, our ordinary notion of first-order truth is conceptualized interms of (existential) second-order logic. What happens when this ideais applied to axiomatic set theory, say Zermelo-Fraenkel set theorywith the Axiom of Choice \((\mathbf{ZFC})\)? It should be born inmind that the very idea of axiomatic set theory is to dispense withhigher-order logic; its underlying logic is taken to be\(\mathbf{FO}\). Hintikka argues as follows.^[77]

For each sentence \(\phi\) of \(\mathbf{ZFC}\), there is anothersentence \(\phi^* = (\exists f_1)\ldots(\exists f_n)\psi^*\)of \(\mathbf{ZFC}\) which says, intuitively, that ‘Skolemfunctions’ for \(\phi\) exist. These ‘Skolem functions’are certain individuals of the domain of a model of\(\mathbf{ZFC}\). Here both \(\phi^*\) and \(\phi\) are first-ordersentences. But if for every sentence \(\phi\) of \(\mathbf{ZFC}\) wehave \(\phi\) and \(\phi^*\) being logically equivalent, why could thesentences \(\phi^*\) not be used for formulating a truth-predicate for\(\mathbf{ZFC}\) in \(\mathbf{ZFC}\) itself? However, byTarski’s undefinability result, no such truth-predicate exists.^[78] So there must be a model of \(\mathbf{ZFC}\) and a sentence \(\phi\)true in that model such that \(\phi^*\) is false: not all ‘Skolemfunctions’ asserted to exist by \(\phi^*\) actually exist in themodel.

This reasoning shows that \(\mathbf{ZFC}\) does not fully capture theidea of truth according to which the truth of a sentence \(\phi\)means that the Skolem functions for \(\phi\) exist. Furthermore, italso shows that the standard interpretation of higher-order logic isnot fully captured by \(\mathbf{ZFC}\). To see this, observe that forevery sentence \(\phi\) there is a logically equivalentsecond-order sentence \(\phi^{**} = (\existsF_1)\ldots(\exists F_n)\psi^{**}\) actually asserting the existence ofSkolem functions for \(\phi\). Thefirst-order sentence\(\phi^* = (\exists f_1)\ldots(\exists f_n)\psi^*\) must not beconfused with the second-order sentence \(\phi^{**} = (\existsF_1)\ldots(\exists F_n)\psi^{**}\). The Skolem functions \(F_i\) ofwhich the sentence \(\phi^{**}\) speaks aresets built out ofindividuals of the set-theoretical universe, while the ‘Skolemfunctions’ \(f_i\) spoken of by \(\phi^*\) areindividuals.^[79]

The conclusion of Hintikka’s argument is that our ordinarynotion of truth is misrepresented by \(\mathbf{ZFC}\).Furthermore, by Tarski’s undefinability result the situationcannot be improved by adding further axioms to \(\mathbf{ZFC}\).In Hintikka’s judgment, axiomatic set theory is a systematic butfutile attempt to capture on the first-order level truths ofstandardly interpreted second-order logic. Like Gödel (1947),also Hintikka holds that the concepts needed to state, say, thecontinuum hypothesis are sufficiently well-defined to determine thetruth-value of this conjecture. The continuum hypothesis does notreceive its meaning from phrasing it in \(\mathbf{ZFC}\).Gödel and Hintikka agree that the independence results due toGödel himself and Paul Cohen do not by themselves show anythingabout the truth or falsity of the continuum hypothesis. But unlikeGödel, Hintikka finds the derivability of any conjecture whateverin \(\mathbf{ZFC}\) (or in any of its extensions) simplyirrelevant for the truth of the conjecture. For Hintikka, it is a‘combinatorial’ question whether every infinite subset ofthe reals is either countable or else has the cardinality of the setof all reals – a question properly conceptualized withinsecond-order logic. This is what Hintikka takes to be thepretheoretical sense of the truth of the continuum hypothesis, andthat is not captured by \(\mathbf{ZFC}\).^[80]

5.3 Extended IF first-order logic and mathematical theorizing

Hintikka sees \(\mathbf{EIFL}\) as allowing to reconstruct allnormal mathematical reasoning on the first-order level. This result isessentially dependent on the acceptability of Hintikka’s claimthat \(\mathbf{EIFL}\) is ontologically committed to individualsonly (Subsect. 5.1). But how would \(\mathbf{EIFL}\)serve to reconstruct an important part of all mathematicalreasoning?

Hintikka (1996: 194–210) discusses mathematicaltheories (or mathematical axiomatizations) and mathematicalproblems (or questions of logical consequence)separately.

Any higher-ordermathematical theory \(T\) gives rise toa many-sorted first-order theory \(T^*\). If the theory is finite,there is a finite conjunction \(J\) formulated in\(\mathbf{EIFL}\) (equivalent to the contradictory negation of an\(\mathbf{ESO}\) sentence) expressing the requirement that thestandard interpretation of higher-order logic is respected. Thequestion of the truth of the higher-order theory \(T\) is thusreduced to the truth of the sentence \((T^* \wedge J)\) of\(\mathbf{EIFL}\) (cf.Subsect. 4.6).

Themathematical problem of whether a given sentence\(C\) is a logical consequence of a finite higher-order theory\(T\) coincides with the problem of whether the second-ordersentence \((\neg(T^* \wedge J) \vee C^*)\) isvalid. Recalling that there is a sentence \(\chi\) of\(\mathbf{IFL}\) such that \(J\) is equivalent to \(\neg \chi\),it follows that \(\neg(T^* \wedge J)\) is equivalent to asentence of \(\mathbf{IFL}\). Consequently there is a sentence of\(\mathbf{IFL}\) which is valid iff the sentence\((\neg(T^* \wedge J) \vee C^*)\) is valid (cf.Subsect. 4.6). Mathematical problems can be understood asquestions of thevalidity of an \(\mathbf{IFL}\)sentence. Among mathematical problems thus reconstructible using\(\mathbf{IFL}\) are the continuum hypothesis, Goldbach’sconjecture, Souslin’s conjecture, the existence of aninaccessible cardinal, and the existence of a measurable cardinal.^[81]

As conceptualizations apparently transcending the proposed framework– not expressible in a higher-order logic – Hintikkaconsiders the maximality assumption expressed by David Hilbert’sso-called axiom of completeness. The axiom says that no mathematicalobjects can be added to the intended models without violating theother axioms.^[82]

If indeed problems related to the idea ofall subsets areavoided in \(\mathbf{EIFL}\) (Hintikka 1997), it offers a way ofdefending a certain form logicism. Unlike in historical logicism, theidea is not to consider logic as an axiom system on the same level asmathematical axiom systems (Hintikka 1996: 183),^[83] and to attempt to reduce mathematics to logic. Rather, Hintikka(1996: 184) proposes to ask:(a) Can the crucialmathematical concepts be defined in logical terms?(b) Can the modes of semantically valid logicalinferences used in mathematics be expressed in logical terms? The ideais not to concentrate on deductive rules of logic: no complete set ofdeductive rules exist anyway for \(\mathbf{IFL}\). Because thestatus of higher-order logic is potentially dubious – due to theproblems associated with the notion of powerset – a positivesolution to questions (a) and (b) calls for a first-order logic morepowerful than \(\mathbf{FO}\).

The suggested reduction of all mathematics expressible in higher-orderlogic to the first-order level would be philosophically significant inshowing that mathematics is not a study of general concepts, but ofstructures consisting of particulars (Hintikka 1996: 207). This is notto say that actual mathematics would be best carried out in terms of\(\mathbf{IFL}\), only that it could in principle be so carriedout (Hintikka 1996: 205, 2006a: 477). For a critique ofHintikka’s conclusions, see Väänänen (2001),Feferman (2006).

5.4 Informational independence in natural languages

When Hintikka began to apply GTS to the study of natural language(Hintikka 1973a), he took up the question of whether branchingquantifiers occur in natural languages. He was led to ask whetherthere are semantic games with imperfect information. He detectedvarious types of grammatical constructions in English that involveinformational independence.^[84] An often cited example is the sentence

Some relative of each villager and some relative of each townsmanhate each other,

true under its relevant reading when the choice of a relative of eachtownsman can be made independently of the individual chosen for‘each villager.’^[85] Hintikka (1973a) sketched an argument to the effect that actuallyevery \(\mathbf{FPO}\) sentence can be reproduced as arepresentation of an English sentence. From this it would follow thatthe logic of idiomatic English quantifiers is much stronger than\(\mathbf{FO}\), and that no effective procedure exists forclassifying sentences as analytical or nonanalytical, synonymous or nonsynonymous.^[86] This would be methodologically a very important result, showing thatsyntactic methods are even in principle insufficient in linguistictheorizing. Jon Barwise (1979) suggested that particularly convincingexamples supporting Hintikka’s thesis can be given in terms ofgeneralized quantifiers.

Lauri Carlson and Alice ter Meulen (1979) were the first to observecases of informational independence between quantifiers andintensional operators. Consider the question^[87]

Who does everybody admire?

Under one of its readings, the presupposition of this question is\((\forall x)(\exists y)\) admires\((x,y)\). The desideratum of this question is

I know who everybody admires.

Writing ‘\(K_I\)’ for ‘I know,’^[88] the desideratum has a reading whose logical form is

\(K_I (\forall x)(\exists y/K_I)\) admires\((x, y)\).

This desireratum is satisfied by an answer pointing out a function\(f\) which yields for each person a suitable admired person.Such a function can behis or her father. Importantly, thevalue \(f(b)\) of this function only depends on theperson \(b\) interpreting ‘everybody,’ but does notdepend on the scenario \(w\), compatible with thequestioner’s knowledge, that interprets the construction‘I know.’ Interestingly, the desideratum\(K_I (\forall x)(\exists y/K_I)\)admires\((x, y)\) is not expressible without an explicitindependence indicator. It is also worth noting that this case cannotbe represented in the notation of \(\mathbf{FPO}\). This isbecause several types of semantic interactions are possible amongquantifiers and intensional operators, and blocking interactions ofone type does not automatically block interactions of other types. Inthe example, the witness of \(\exists y\) must not vary with thescenario \(w\) interpreting the operator\(K_I\), but still the values of bothvariables \(x\) and \(y\) must belong to the domain of theparticular scenario \(w\) chosen to interpret \(K_I\).^[89]

Hintikka’s ideas on desiderata of wh-questions were influencedby his exchange with the linguist Elisabet Engdahl.^[90] These wh-questions, again, functioned as important test cases for theappearance of informational independence in natural languages.

Hintikka and Sandu (1989) took up the task of formulating an explicitunified formal treatment for the different varieties of informationalindependence in natural language semantics. They posed the question ofwhich are the mechanisms that allow English to exceed the expressivepower of \(\mathbf{FO}\). For, natural languages typically do notresort to higher-order quantifiers. Hintikka and Sandu suggested thatinformational independence plays a key role in increasing theexpressive power of natural languages.^[91]

In GTS as developed for English in Hintikka & Kulas (1983, 1985),game rules are associated with a great variety of linguisticexpressions (cf.Subsect. 2.1). As Hintikka (1990) hasstressed, informational independence is a cross-categoricalphenomenon: it can occur in connection with expressions of widelydifferent grammatical categories. Hintikka and Sandu (1989) proposeseveral examples from English calculated to show that there is anabundance of instances of informational independence in naturallanguages. Among examples are wh-questions of the kind discussedabove, and the distinction between thede dicto anddere readings of certain English sentences. Hintikka and Sandusuggest that representing such readings in terms of IF logic is moretruthful to the syntax of English than the alternative, non-IFrepresentations are.

In connection with knowledge, adedicto attribution such as

\(K_{\textit{Ralph}} (\exists x) (x\) is a spy)

can be turned into ade re attribution by marking theexistential quantifier as independent of the knowledge-operator (cf.Hintikka and Sandu 1989):

\(K_{\textit{Ralph}} (\exists x/K_{\textit{Ralph}}) (x\) is a spy).

Because knowledge is a factive attitude (the actual world is amongRalph’s epistemic alternatives), this amounts indeed to the sameas the condition

\((\exists x) K_{\textit{Ralph}} (x\) is a spy).

Rebuschi & Tulenheimo (2011) observed that independent quantifiersare of special interest in connection with non-factive attitudes suchas belief. The logical form of a statement ascribing to Ralph a beliefpertaining to a specific but non-existent object is

\(B_{\textit{Ralph}} (\exists x/B_{\textit{Ralph}}) (x\) is a spy),

where ‘\(B_{\textit{Ralph}}\)’ stands for‘Ralph believes that.’^[92]

Attitudes of this form were dubbedde objecto attitudes.Since the (intentional) object of such an attitude need not existactually, thede objecto attitude is weaker than thedere attitude

\((\exists x) B_{\textit{Ralph}} (x\) is a spy).

On the other hand, the pattern of operators \(B_{\textit{Ralph}}(\exists x/B_{\textit{Ralph}})\) requires that the witness of theexistential quantifier \(\exists x\) be the same relative to alldoxastic alternatives of Ralph, so thede objecto attitude isstronger than thede dicto attitude

\(B_{\textit{Ralph}} (\exists x) (x\) is a spy).

Janssen (2013) discusses the possibility of providing in terms of\(\mathbf{IFL}\) a compositional analysis of thede re /de dicto ambiguity in natural languages. Brasoveanu andFarkas (2011) argue that scopal properties of natural languageindefinites are best elucidated in terms of a semantics inspired by\(\mathbf{IFL}\), more precisely by formulating the semanticsrelative to sets of variable assignments as done in Hodges’scompositional semantics for slash logic.

As a rule, informational independence is not indicated syntacticallyin English.^[93] Methodological consequences of this fact are discussed in Hintikka(1990), where he tentatively puts forward theSyntactic SilenceThesis, according to which sufficiently radical cross-categoricalphenomena are not likely to be marked syntactically in naturallanguages. Evidence for this thesis would, for its part, be evidenceagainst the sufficiency of syntax-oriented approaches tosemantics.

6. Related logics

6.1 Slash logic

Syntatically slash logic uses quantifiers like\((\exists x/y)\) instead of quantifiers such as\((\exists x/\forall y)\). Semantically slash logic isotherwise like \(\mathbf{IFL}\) except that its game-theoreticalsemantics is based on the idea that a player’s strategyfunctions may utilize as their argumentsany preceding movesmade in the current play, save for those whose use is, by the slashnotation, explicitly indicated as forbidden (cf.Sect. 3).That is, also a player’s own earlier moves may appear asarguments of a strategy function. This can make a difference in thepresence of imperfect information. For example, consider evaluatingthe slash-logic sentence\((\forall x)(\exists y)(\exists z/x)x = z\) containing the vacuous quantifier\(\exists y\). This sentence is true on a two-element domain,since player 2 can copy as the value of \(y\) the value thatplayer 1 has chosen for \(x\), and then select the value of\(z\) using a strategy function whose only argument is the valueof \(y\). (For this phenomenon of ‘signaling,’ seeHodges 1997a, Sandu 2001, Janssen & Dechesne 2006, Barbero 2013.)By contrast, the IF sentence\((\forall x)(\exists y)(\exists z/\forall x)x = z\) fails to be true on such a domain, since therea strategy function for \((\exists z/\forall x)\) must bea constant, and no such strategy function can guarantee a win forplayer 2 against both possible values that player 1 can choose for\(x\). As mentioned inSubsection 4.4, Hodges (1997a,b)showed that slash logic admits of an alternative, compositionalsemantics. This requires evaluating formulas relative to sets ofvariable assignments, instead of single assignments as in connectionwith \(\mathbf{FO}\). Hodges (1997a,b) and Figueiraetal. (2009, 2011) discuss an extension of slash logic in which thecontradictory negation of slash logic sentences can be expressed.

6.2 Dependence logic

Jouko Väänänen (2007) formulated a new approach to IFlogic that he dubbeddependence logic \((\mathbf{DL})\);for further work on \(\mathbf{DL}\), seee.g. Kontinenet al. (2013). The syntax of \(\mathbf{DL}\) is obtainedfrom that of \(\mathbf{FO}\) by allowing atomic formulas of thefollowing special form:

Intuitively such a formula means that the value of \(x_{n+1}\) dependsonly on the values of \(x_1 ,\ldots ,x_n\). The semantics of\(\mathbf{DL}\) cannot be formulated relative to single variableassignments like that of \(\mathbf{FO}\): we cannot explicate what itmeans for the value of \(x_{n+1}\) to depend on those of \(x_1 ,\ldots,x_n\) with reference to a single assignment on the variables \(x_1,\ldots ,x_{n+1}\). For example, consider the assignment describedbelow:

Relative to this assignment, all of the following claims hold:whenever the value of \(x_1\) equals 7, the value of \(x_3\) equals 8;whenever the value of \(x_2\) equals 5, the value of \(x_3\) equals 8;whenever the value of \(x_1\) equals 7 and the value of \(x_2\) equals5, the value of \(x_3\) equals 8; irrespective of the values of\(x_1\) and \(x_2\), the value of \(x_3\) equals 8. The question ofdependence only becomes interesting and non-vacuous relative to a setof assignments:

The set \(X\) consisting of the above five assignments satisfiesthe formula \(=(x_1\); \(x_3)\): thevalue of \(x_3\) depends only on the value of\(x_1\). As is readily observed, any two assignments in\(X\) which assign the same value to \(x_1\)assign also the same value to \(x_3\). The interestingnovelty of \(\mathbf{DL}\) is that claims about variabledependencies are made at the atomic level. Quantifiers of\(\mathbf{IFL}\) and those of slash logic with their independenceindications easily lead to somewhat messy formulas, whereas\(\mathbf{DL}\) looks exactly like \(\mathbf{FO}\), apart fromits greater flexibility in forms of atomic formulas.

7. Conclusion

In this entry IF first-order logic and extended IF first-order logichave been surveyed. Their metalogical properties have been explainedand the philosophical relevance of these properties has beendiscussed. The suggested consequences of these logics forphilosophical issues such as the existence of a self-appliedtruth-predicate, the logicist program, the philosophical relevance ofaxiomatic set theory, and informational independence in naturallanguages have been covered as well. Slash logic and dependence logic– both closely related to \(\mathbf{IFL}\) and inspired byit – were also briefly considered.

Bibliography

• Auxier, R. E. and Hahn, L. E. (eds.), 2006,The Philosophy ofJaakko Hintikka, (Library of Living Philosophers, Volume 30),Chicago: Open Court.
• Barbero, F., 2013, “On Existential Declarations ofIndependence in IF Logic,”Review of Symbolic Logic, 6:254–280.
• Barwise, J., 1979, “On Branching Quantifiers inEnglish,”Journal of Philosophical Logic, 8:47–80.
• Barwise, J., and Moschovakis, Y. N., 1978, “Global InductiveDefinability,”Journal of Symbolic Logic, 43(3):521–534.
• van Benthem, J., and Doets, K., 2001, “Higher-OrderLogic,” inHandbook of Philosophical Logic, (2ndedition, Vol. 1), D. M. Gabbay, and F. Guenthner (eds.), Berlin:Springer, pp. 189–244.
• Blass, A., and Gurevich, Y., 1986, “Henkin Quantifiers andComplete Problems,”Annals of Pure and Applied Logic,32: 1–16.
• Brasoveanu, A., and Farkas, D. F., 2011, “How IndefinitesChoose Their Scope,”Linguistics and Philosophy, 34(1):1–55.
• Burgess, J. P., 2003, “A Remark on Henkin Sentences andTheir Contraries,”Notre Dame Journal of Formal Logic,44: 185–188.
• Caicedo X., Dechesne, F., and Janssen, T. M. V., 2009,“Equivalence and Quantifier Rules for Logic with ImperfectInformation,”Logic Journal of the IGPL, 17(1):91–129.
• Cameron, P., and Hodges, W., 2001, “Some Combinatorics ofImperfect Information,”Journal of Symbolic Logic, 66:673–684.
• Carlson, L., and Hintikka, J., 1979, “Conditionals, GenericQuantifiers, and Other Applications of Subgames,” inGame-Theoretical Semantics, E. Saarinen (ed.), Dordrecht:Reidel, pp. 179–214.
• Carlson, L., and ter Meulen, A., 1979, “InformationalIndependence in Intensional Contexts,” inEssays in Honourof Jaakko Hintikka, E. Saarinen, I. Niiniluoto, R. Hilpinen, andM. Provence (eds.), Dordrecht: Reidel, pp. 61–72.
• Clark, R., 2012,Meaningful Games: Exploring Language withGame Theory, Cambridge, MA: The MIT Press.
• Dechesne, F., 2005,Game, Set, Math: Formal Investigationsinto Logic with Imperfect Information, Ph.D. Thesis, Eindhoven:University of Tilburg.
• Ebbinghaus, H.-D., and Flum, J., 1999,Finite ModelTheory, Berlin: Springer, 2nd edition.
• Ebbinghaus, H.-D., Flum, J., and Thomas, W., 1994,Mathematical Logic, New York: Springer, 2nd edition.
• Enderton, H. B., 1970, “Finite Partially-OrderedQuantifiers,”Zeitschrift für matematische Logik undGrundlagen der Mathematik, 16: 393–397.
• Engdahl, E., 1986,Constituent Questions: The Syntax andSemantics of Questions with Special Reference to Swedish,Dordrecht: Reidel.
• Fagin, R., 1974, “Generalized First-Order Spectra andPolynomial-Time Recognizable Sets,” inComplexity ofComputation, (SIAM-AMS Proceedings, Volume 7), R. M. Karp (ed.),pp. 43–73.
• Feferman, S., 2006, “What Kind of Logic is‘Independence-Friendly’ Logic?,” in Auxier &Hahn (2006), pp. 453–469.
• Figueira, S., Gorín, D., and Grimson, R., 2009, “Onthe Formal Semantics of IF-like Logics,”Journal of Computerand System Sciences, 76: 333–346.
• Figueira, S., Gorín, D., and Grimson, R., 2011, “Onthe Expressive Power of IF-Logic with Classical Negation” inLogic, Language, Information, and Computation, L. Beklemishevand R. de Queiroz (eds.), Berlin: Springer, pp. 135–145.
• Forster, T., 2006, “Deterministic and NondeterministicStrategies for Hintikka Games in First-Order and Branching-QuantifierLogic,”Logique et Analyse, 195: 265–269.
• Fortnow, L., 2009, “The Status of the P versus NPProblem,”Communications of the ACM, 52(9):78–86.
• Gödel, K., 1930, “Die Vollständigkeit der Axiomedes logisch Funktionenkalküls,”Monatshefte fürMathematik und Physik, 37: 349–360.
• –––, 1933, “Eine Interpretation desintuitionistischen Aussagenkalkuls,”Ergebnisse einesmathematischen Kolloquiums, 4: 39–40.
• –––, 1947, “What is Cantor’sContinuum Problem?,”The American Mathematical Monthly,54: 515–525.
• Grädel E., Kolaitis, P. G., Libkin, L., Marx, M., Spencer,J., Vardi, M. Y., Venema, Y., and Weinstein, S., 2007,FiniteModel Theory and Its Applications, Berlin: Springer.
• Hella, L., and Sandu, G., 1995, “Partially OrderedConnectives and Finite Graphs,” inQuantifiers: Logics,Models and Computation, Vol. 2, M. Krynicki, M. Mostowski, and L.W. Szczerba (eds.), Dordrecht: Kluwer, pp. 79–88.
• Hella, L., Sevenster, M., and Tulenheimo, T., 2008,“Partially Ordered Connectives and Monadic Monotone StrictNP,”Journal of Logic, Language and Information, 17(3):323–344.
• Henkin, L., 1950, “Completeness in the Theory ofTypes,”Journal of Symbolic Logic, 15:81–91.
• –––, 1961, “Some Remarks on InfinitelyLong Formulas,” inInfinitistic Methods (no ed. given),New York: Pergamon Press, pp. 167–183.
• Hilbert, D., 1903,Grundlagen der Geometrie, Leipzig:Teubner, 2nd edition. (1st edition: “Grundlagen derGeometrie,” inFestschrift zur Feier der Enthüllung desGauss-Weber-Denkmals in Göttingen 3–92, Leipzig:Teubner, 1899.)
• Hinman, P. G., 1978,Recursion-Theoretic Hierarchies,Berlin: Springer, 1978.
• Hintikka, J., 1955, “Reductions in the Theory ofTypes,” Acta Philosophica Fennica, 8, pp. 61–115.
• –––, 1968, “Language-Games forQuantifiers,” inAmerican Philosophical Quarterly MonographSeries 2: Studies in Logical Theory, Oxford: Basil Blackwell, pp.46–72; reprinted in Hintikka 1973b,Ch. III.
• –––, 1973a, “Quantifiers vs.Quantification Theory,”Dialectica, 27: 329–358;reprinted in 1974 inLinguistic Inquiry, 5:153–177.
• –––, 1973b,Logic, Language-Games andInformation: Kantian Themes in the Philosophy of Logic, Oxford:Clarendon Press.
• –––, 1976a, “Quantifiers in Logic andQuantifiers in Natural Languages,” inPhilosophy ofLogic, S. Körner (ed.), Oxford: Basil Blackwell, pp.208–232.
• –––, 1976b,The Semantics of Questions andthe Questions of Semantics, Acta Philosophica Fennica,28(4).
• –––, 1979, “Quantifiers in NaturalLanguages: Some Logical Problems,” inGame-TheoreticalSemantics, E. Saarinen (ed.), Dordrecht: Reidel, pp.81–117.
• –––, 1982, “On Games, Questions, andStrange Quantifiers,” inPhilosophical Essays Dedicated toLennart Åqvist on his Fiftieth Birthday, T. Pauli (ed.),Department of Philosophy, Uppsala: University of Uppsala, pp.159–169.
• –––, 1986, “Extremality Assumptions in theFoundations of Mathematics,”Proceedings of the BiennialMeeting of the Philosophy of Science Association 1986, Vol. 2,pp. 247–252.
• –––, 1987, “Is Scope a Viable Concept inSemantics?,” inESCOL ‘86. Proceedings of the ThirdEastern States Conference on Linguistics, A. Miller, and Z.-S.Zhang (eds.), pp. 259–270.
• –––, 1988, “On the Development of theModel-Theoretic Viewpoint in Logical Theory,”Synthese,77: 1–36.
• –––, 1990, “Paradigms for LanguageTheory” inLanguage, Knowledge and Intentionality:Perspectives on the Philosophy of Jaakko Hintikka, L. Haaparanta,M. Kusch, and I. Niiniluoto (eds.): Acta Philosophia Fennica, 49, pp.181–209; reprinted in Hintikka, J., 1998,Paradigms forLanguage Theory and Other Essays (Jaakko Hintikka: SelectedPapers, Volume 4), Dordrecht: Kluwer, pp. 146–174.
• –––, 1991,Defining Truth, the Whole Truthand Nothing but the Truth, Reports from the Department ofPhilosophy, no. 2, Helsinki: University of Helsinki; a revised versionreprinted in Hintikka, J., 1997,Lingua Universalis vs. CalculusRatiocinator: An Ultimate Presupposition of Twentieth-CenturyPhilosophy (Jaakko Hintikka: Selected Papers, Volume 2),Dordrecht: Kluwer, pp. 46–103.
• –––, 1993, “New Foundations forMathematical Theories,” inLogic Colloquium ‘90,Lecture Notes in Logic 2, J. Väänänen, and J.Oikkonen (eds.), Berlin: Springer, pp. 122–144; reprinted inHintikka, J., 1998,Language, Truth and Logic in Mathematics(Jaakko Hintikka: Selected Papers, Volume 3), Dordrecht: Kluwer, pp.225–247.
• –––, 1995, “What is Elementary Logic?Independence-Friendly Logic as the True Core Area of Logic,” inPhysics, Philosophy and the Scientific Community, K.Gavroglu, J. J. Stachel, and M. W. Wartofsky (eds.), Dordrecht:Kluwer, pp. 301–326; page reference is to the reprint inHintikka, J., 1998,Language, Truth and Logic in Mathematics(Jaakko Hintikka: Selected Papers, Volume 3), Dordrecht: Kluwer, 1998,pp. 1–26.
• –––, 1996,The Principles of MathematicsRevisited, Cambridge: Cambridge University Press.
• –––, 1997, “No Scope for Scope?,”Linguistics and Philosophy, 20: 515–544; reprinted inHintikka, J., 1998,Paradigms for Language Theory and OtherEssays (Jaakko Hintikka: Selected Papers, Volume 4), Dordrecht:Kluwer, pp. 22–51.
• –––, 1997, “A Revolution in theFoundations of Mathematics?,”Synthese, 111:155–170; reprinted in Hintikka, J., 1998,Language, Truthand Logic in Mathematics (Jaakko Hintikka: Selected Papers,Volume 3), Dordrecht: Kluwer, pp. 45–61.
• –––, 1998, “Truth Definitions, SkolemFunctions and Axiomatic Set Theory,”Bulletin of SymbolicLogic, 4: 303–337.
• –––, 1999,Inquiry as Inquiry: A Logic ofScientific Discovery (Jaakko Hintikka: Selected Papers, Volume5), Dordrecht: Kluwer.
• –––, 2000, “Game-Theoretical Semantics asa Challenge to Proof Theory,”Nordic Journal ofPhilosophical Logic, 4(2): 127–141.
• –––, 2001, “Post-Tarskian Truth,”Synthese, 126: 17–36.
• –––, 2002a, “Hyperclassical Logic (a.k.a.IF Logic) and its Implications for Logical Theory,”Bulletinof Symbolic Logic, 8: 404–423.
• –––, 2002b, “Quantum Logic is a Fragmentof Independence-Friendly Logic,”Journal of PhilosophicalLogic, 31: 197–209.
• –––, 2002c, “Negation in Logic and inNatural Language,”Linguistics and Philosophy, 25:585–600.
• –––, 2003, “A Second-Generation EpistemicLogic and Its General Significance,” inKnowledgeContributors, V. F. Hendricks, K. F. Jørgensen, and S. A.Pedersen (eds.), Dordrecht: Kluwer, pp. 33–55; reprinted inHintikka, J., 2007,Socratic Epistemology, New York:Cambridge University Press, pp. 61–82.
• –––, 2004a, “Independence-Friendly Logicand Axiomatic Set Theory,”Annals of Pure and AppliedLogic, 126: 313–333.
• –––, 2004b, “What is the True Algebra ofLogic,” inFirst-Order Logic Revisited, V. F.Hendricks, F. Neuhaus, S. A. Pedersen, U. Scheffler, and H. Wansing(eds.), Berlin: Logos Verlag, pp. 117–128.
• –––, 2006a, “IntellectualAutobiography” and Hintikka’s replies to the contributorsin Auxier & Hahn (2006).
• –––, 2006b, “Truth, Negation and OtherBasic Notions of Logic” inThe Age of AlternativeLogics, J. van Benthem, G. Heinzmann, M. Rebuschi, and H. Visser(eds.), Berlin: Springer, pp. 195–219.
• –––, 2008, “IF Logic in a Wider Setting:Probability and Mutual Dependence,” inDialogues, Logics andOther Strange Things, C. Dégremont, L. Keiff, and H.Rückert (eds.), London: College Publications, pp.195–211.
• Hintikka, J., and Kulas, J., 1983,The Game of Language:Studies in Game-Theoretical Semantics and Its Applications,Dordrecht: Reidel.
• –––, 1985,Anaphora and DefiniteDescriptions: Two Applications of Game-Theoretical Semantics,Dordrecht: Reidel.
• Hintikka, J., and Sandu, G., 1989, “InformationalIndependence as a Semantical Phenomenon,” inLogic,Methodology and Philosophy of Science, Vol. 8, J. E. Fenstad, I.T. Frolov, and R. Hilpinen (eds.), Amsterdam: Elsevier, pp.571–589; reprinted in Hintikka, J., 1998,Paradigms forLanguage Theory and Other Essays (Jaakko Hintikka: SelectedPapers, Volume 4), Dordrecht: Kluwer, pp. 52–70.
• –––, 1991,On the Methodology ofLinguistics: A Case Study, Oxford: Basic Blackwell.
• –––, 1996, “A Revolution in Logic?,”Nordic Journal of Philosophical Logic, 1(2): 169–183;reprinted in Hintikka, J., 1998,Language, Truth and Logic inMathematics (Jaakko Hintikka: Selected Papers, Volume 3),Dordrecht: Kluwer, 1998, pp. 27–44.
• –––, 1997, “Game-TheoreticalSemantics,” inHandbook of Logic and Language, J. vanBenthem, and A. ter Meulen (eds.), Amsterdam: Elsevier, pp.361–410.
• –––, 1999, “Tarski’s Guilty Secret:Compositionality,” inAlfred Tarski and the ViennaCircle, J. Wolenski, and E. Köhler (eds.), Dordrecht:Kluwer, pp. 217–230.
• Hodges, W., 1983, “Elementary Predicate Logic,” inHandbook of Philosophical Logic, Vol. 1, D. M. Gabbay, and F.Guenthner (eds.), Dordrecht: Reidel, pp. 1–131.
• –––, 1993,Model Theory, inEncyclopedia of Mathematics and its Applications (Volume 42),Cambridge: Cambridge University Press.
• –––, 1997a, “Compositional Semantics for aLangauge of Imperfect Information,”Logic Journal of theIGPL, 5: 539–563.
• –––, 1997b, “Some StrangeQuantifiers,” inStructures in Logic and Computer Science: ASelection of Essays in Honor of A. Ehrenfeucht, (Lecture Notes inComputer Science, Volume 1261) J. Mycielski, G. Rozenberg, and A.Salomaa (eds.), London: Springer, pp. 51–65.
• –––, 1998, “Compositionality Is Not theProblem,”Logic and Logical Philosophy, 6:7–33.
• –––, 2006, “The Logic ofQuantifiers,” in Auxier & Hahn (2006), pp.521–534.
• –––, 2007, “Logics of ImperfectInformation: Why Sets of Assignments?,” inInteractiveLogic, J. van Benthem, D. M. Gabbay, and B. Löwe (eds.),Amsterdam: Amsterdam University Press, pp. 117–133.
• –––, 2013, “Logic and Games,” inThe Stanford Encyclopedia of Philosophy (Spring 2013 Edition),E. Zalta (ed.), URL = <https://plato.stanford.edu/archives/spring2013/entries/logic-games/>.
• Hyttinen, T., and Sandu, G., 2000, “Henkin Quantifiers andthe Definability of Truth,”Journal of PhilosophicalLogic, 29: 507–527.
• Janssen, T. M. V., 1997, “Compositionality,” inHandbook of Logic and Language, J. van Benthem, and A. terMeulen (eds.), Amsterdam: Elsevier, pp. 417–473.
• –––, 2002, “Independent Choices and theInterpretation of IF Logic,”Journal of Logic, Language andInformation, 11: 367–387.
• –––, 2013, “Compositional Natural LanguageSemantics using Independence Friendly Logic or DependenceLogic,”Studia Logica, 101(2): 453–466.
• Janssen, T. M. V., and Dechesne, F., 2006, “Signaling inIF-Games: A Tricky Business,” inThe Age of AlternativeLogics, J. van Benthem, G. Heinzmann, M. Rebuschi, and H. Visser(eds.), New York: Springer, pp. 221–241.
• Jónsson, B., and Tarski, A., 1951, “Boolean Algebraswith Operators, Part I,”American Journal ofMathematics, 73: 891–939.
• Kaye, R., 1991,Models of Peano Arithmetic, Oxford:Clarendon Press.
• Kontinen, J., Väänänen, J., and Westerståhl,D. (eds.), 2013,Dependence and Independence in Logic,special issue ofStudia Logica, 101(2).
• Krynicki, M., 1993, “Hierarchies of Partially OrderedConnectives and Quantifiers,”Mathematical LogicQuarterly, 39: 287–294.
• Krynicki, M., and Lachlan, A. H., 1979, “On the Semantics ofthe Henkin Quantifier,”Journal of Symbolic Logic,44(2): 184–200.
• Krynicki, M., and Mostowski, M., 1995, “HenkinQuantifiers” inQuantifiers: Logics, Models andComputation, Vol. 1, M. Krynicki, M. Mostowski, and L. W.Szczerba (eds.), Dordrecht: Kluwer, pp. 193–262.
• Leivant, D., 1994, “Higher Order Logic,” inHandbook of Logic in Artificial Intelligence and LogicProgramming, Vol. 2, D. M. Gabbay, C. J. Hogger, J. A. Robinson,and J. H. Siekmann, (eds.), Oxford: Clarendon Press, pp.229–321.
• Mann, A. L., 2007,Independence-Friendly Cylindric SetAlgebras, Ph.D. thesis, University of Colorado at Boulder.
• Mann, A. L., Sandu, G., and Sevenster, M., 2011,Independence-Friendly Logic: A Game-Theoretic Approach,Cambridge: Cambridge University Press.
• Marion, M., 2009, “Why Play Logical Games?,” inGames: Unifying Logic, Language and Philosophy, O. Majer,A.-V. Pietarinen, and T. Tulenheimo (eds.), New York: Springer-Verlag,pp. 3–25.
• McKinsey, J. C. C., and Tarski, A., 1948, “Some TheoremsAbout the Sentential Calculi of Lewis and Heyting,”Journalof Symbolic Logic, 13(1): 1–15.
• Mostowski, A., 1957, “On a Generalization ofQuantifiers,”Fundamenta Mathematicae, 44:12–36.
• Mostowski, M., 1991, “Arithmetic with the Henkin Quantifierand its Generalizations,” inSéminaire du LaboratoireLogique, Algorithmique et Informatique Clermontoise, Vol. 2, F.Gaillard, and D. Richard (eds.), pp. 1–25.
• Odintsov, S., Speranski, S., and Shevchenko, I., 2018. “Hintikka’s Independence-Friendly Logic Meets Nelson’s Realizability,”Studia Logica, 106(3): 637–670.
• Papadimitriou, C. H., 1994,Computational Complexity,Reading, MA: Addison-Wesley.
• Patton, T. E., 1991, “On the Ontology of BranchingQuantifiers,”Journal of Philosophical Logic, 20:205–223.
• Peters, S., and Westerståhl, D., 2006,Quantifiers inLanguage and Logic, Oxford: Oxford University Press.
• Pietarinen, A.-V., 2001,Semantic Games in Logic andLanguage, Ph.D. thesis, Helsinki: University of Helsinki.
• Quine, W. V. O., 1970,Philosophy of Logic, EnglewoodCliffs, NJ: Prentice-Hall.
• Rebuschi, M., and Tulenheimo, T., 2011, “BetweenDeDicto andDe Re:De Objecto Attitudes,”The Philosophical Quarterly, 61(245): 828–838.
• Reinhart, T., 1997, “Quantifier Scope: How Labor is Dividedbetween QR and Choice Functions,”Linguistics andPhilosophy, 20: 335–397.
• de Rouilhan, P., and Bozon, S., 2006, “The Truth of IF: HasHintikka Really Exorcised Tarski’s Curse?,” in Auxier& Hahn (2006), pp. 683–705.
• Sandu, G., 1991,Studies in Game-Theoretical Logics andSemantics, Ph.D. thesis, Helsinki: University of Helsinki.(Includes Hintikka & Sandu 1989; Sandu 1993, 1994; Sandu &Väänänen 1992.)
• –––, 1993, “On the Logic of InformationalIndependence and its Applications,”Journal of PhilosophicalLogic, 22: 29–60.
• –––, 1994, “Some Aspects of Negation inEnglish,”Synthese, 99(3): 345–360.
• –––, 1996, Appendix to Hintikka (1996), pp.254–270.
• –––, 1998, “IF-Logic andTruth-Definition,”Journal of Philosophical Logic, 27:143–164.
• –––, 2001, “Signalling in Languages withImperfect Information,”Synthese, 127:21–34.
• –––, 2007, Appendix toLes principes desmathématiques revisités, French transl. of Hintikka(1996) by M. Rebuschi, Paris: Vrin, pp. 285–300. (The appendixis new and the translation of the book is based on Hintikka’srevision of Hintikka 1996.)
• –––, 2013, “Probabilistic IF Logic,”inLogic and Its Applications, K. Lodaya (ed.), Heidelberg:Springer, pp. 69–79.
• Sandu, G., and Hintikka, J., 2001, “Aspects ofCompositionality,”Journal of Logic, Language andInformation, 10: 49–61.
• Sandu, G., and Hyttinen, T., 2001, “IF logic and TheFoundations of Mathematics,”Synthese, 126:37–47.
• Sandu, G., and Sevenster, M., 2010, “Equilibrium Semanticsof Languages of Imperfect Information,”Annals of Pure andApplied Logic, 161: 618–631.
• Sandu, G., and Väänänen, J., 1992, “PartiallyOrdered Connectives,”Zeitschrift für matematischeLogik und Grundlagen der Mathematik, 38: 361–372.
• Sevenster, M., 2006,Branches of Imperfect Information: Logic,Games, and Computatation, Ph.D. thesis, Amsterdam: University ofAmsterdam.
• Skolem, T., 1920, “Logisch-kombinatorische Untersuchungenüber die Erfüllbarkeit oder Beweisbarkeit mathematischerSätze nebst einem Theoreme über dichte Mengen,”Skrifter utgit av Videnskabsselskapet i Kristiania, I.Matematisk-naturvidenskabelig klasse no. 4, pp. 1–36;reprinted inT. Skolem,Selected Works in Logic, J.E. Fenstad (ed.), Oslo: Universitetsforlaget, 1970, pp.103–136.
• Steedman, M., 2012,Taking Scope. The Natural Semantics ofQuantifiers, Cambridge, MA: The MIT Press.
• Tarski, A., 1933, “The Concept of Truth in the Languages ofthe Deductive Sciences” (Polish),Prace TowarzystwaNaukowego Warszawskiego, Wydzial III Nauk Matematyczno-Fizycznych34, Warsaw; expanded English translation in Tarski 1983, pp.152–278.
• –––, 1983,Logic, Semantics,Metamathematics: Papers from 1923 to 1938, 2nd and revisededition, J. Corcoran (ed.), Indianapolis: Hackett PublishingCompany.
• Trakhtenbrot, B., 1950, “Impossibility of an Algorithm forthe Decision Problem in Finite Classes” (Russian),DokladyAkademii Nauk SSSR, 70: 569–572. (English translation:American Mathematical Society,Translation Series 2,23, 1963, pp. 1–5.)
• Tulenheimo, T., 2014, “Classical Negation andGame-Theoretical Semantics,”Notre Dame Journal of FormalLogic, 55: 469–498.
• Väänänen, J., 2001, “Second-Order Logic andFoundations of Mathematics,”Bulletin of SymbolicLogic, 7: 504–520.
• –––, 2002, “On the Semantics ofInformational Independence,”Logic Journal of the IGPL,10(3): 337–350.
• –––, 2006, “A Remark on Nondeterminacy inIF Logic,” Acta Philosophica Fennica, 78, pp. 71–77.
• –––, 2007,Dependence Logic: A New Approachto Independence Friendly Logic, Cambridge: Cambridge UniversityPress.
• von Heusinger, K., 2004, “Choice Functions and the AnaphoricSemantics of Definite NPs,”Research on Language andComputation, 2: 309–329.
• Walkoe, W. J. Jr., 1970, “Finite Partially-OrderedQuantification,”Journal of Symbolic Logic, 35:535–555.
• Westerståhl, D., 1998, “On Mathematical Proofs of theVacuity of Compositionality,”Linguistics andPhilosophy, 21: 635–643.
• Wittgenstein, L., 1953,Philosophische Untersuchungen(Philosophical Investigations), Oxford: Basil Blackwell,transl. by G. E. M. Anscombe.
• Zadrozny, W., 1994, “From Compositional to SystematicSemantics,”Linguistics and Philosophy, 17:329–342.

Academic Tools

	How to cite this entry.
	Preview the PDF version of this entry at theFriends of the SEP Society.
	Look up this entry topic at theInternet Philosophy Ontology Project (InPhO).
	Enhanced bibliography for this entryatPhilPapers, with links to its database.

Other Internet Resources

[Please contact the author with suggestions.]

Related Entries

compositionality |game theory |generalized quantifiers |logic: and games |logic: classical |logic: dependence |logic: dialogical |logic: epistemic |logic: intensional |logic: intuitionistic |logic: modal |logic: second-order and higher-order |model theory |reasoning: automated |set theory |Tarski, Alfred: truth definitions