Independence Friendly Logic

First published Mon Feb 9, 2009; substantive revision Thu Sep 15, 2022

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

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 ofuniform continuity isobtained from that of continuity by specifying that the quantifier‘there exists \(\delta\)’ depends only on the quantifier‘for all \(\varepsilon\),’ not on the quantifier‘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 uniformly continuouswould be \((\forall a)(\forall \varepsilon)(\exists \delta /\foralla)(\forall x) R\), to be contrasted with the form of the statementthat \(f\) merely is continuous, \((\forall a)(\forall\varepsilon)(\exists \delta)(\forall x) R\).

In the introductory examples in the present and the following section,let us confine attention to formulas inprenex form: a stringof quantifiers followed by a quantifier-free first-order formula. Ifin a first-order sentence of such a form an existential quantifier\(\exists y\) lies in the syntactic scope of a universal quantifier\(\forall x\), then by the semantics \(\exists y\) automaticallydepends on \(\forall x\). This is soe.g. with the sentence\((\forall x)(\exists y) R(x, y)\). The dependence of \(\exists y\) on\(\forall x\) means that thewitness of \(\exists y\) mayvary with the value interpreting \(\forall x\). In order for thesentence to be true in a model \(M\), it suffices that there be afunction \(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.\) For this sentence to be true in \(M\), one and the samewitness \(c\) for \(\exists y\) must be good against anyinterpretation \(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 sentence \((\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 a matter of fact, the expressive power of IFlogic exceeds that of first-order logic. Consider the sentence\((\forall x)(\exists y)(\forall z)(\exists w/\forall x) R(x, y, z,w)\). Its truth-condition is of the following form: there areone-argument functions \(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:

\[\tag{*}\begin{matrix}\forall x \exists y \\\forall z \exists w\end{matrix}R(x,y,z,w)\]

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 theSkolemnormal form of (*). It says that Skolem functions providingwitnesses for the quantifiers \(\exists y\) and \(\exists w\) in (*)exist. Finite partially ordered quantifiers – a.k.a.Henkinquantifiers orbranching quantifiers – wereproposed by Leon Henkin (1961) and have been subsequently studied extensively.^[8] They are two-dimensional syntactic objects

\[\begin{matrix}Q_{11} \ldots Q_{1n} \\\vdots \\Q_{m1} \ldots Q_{mn}\end{matrix}\]

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 a formula of \(\mathbf{FPO}\).^[9] With \(\mathbf{FPO}\) it is possible to express properties that arenot definable in first-order logic. The first example was provided byAndrzej 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 saw it, is that therelations of dependence and independence betweenquantifiersare the only way of expressing relations of dependence and independencebetweenvariables 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, dependson precisely those universal quantifiers within whose scope \(\existsx\) lies, but of which \(\exists x\) is not marked as independentusing the slash sign. What Hintikka means when he speaks of(in)dependence relations between variables, arefunctionaldependencies between quantities in a model. The kinetic energy ofa material body depends on its mass and its speed, but does not dependon the particular material body being considered. This fact can beexpressed in IF logic by the sentence

\((\forall b)(\forall m)(\forall v)(\exists e/\forall b)\)(if \(b\) isa 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), Sandu(2014).

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 games are most easily explained for sentences in prenex form.Universal quantifiers mark a move of player 1, while existentialquantifiers prompt a move by player 2. In both cases, the relevantplayer must choose an individual from the domain \(\rM\) of \(M\).^[12] If

\[\phi = (\forall x)(\exists y)(\forall z)(\exists w) R(x, y, z, w),\]

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)\) istruein \(M\) if there is a winning strategy for player 2 in the game justdescribed: a recipe telling player 2 what to do, when (a specifiedamount of) information about the opponent’s earlier moves isgiven. Technically, the requirement is that there bestrategyfunctions \(f\) and \(g\), such that for any choices \(a\) and\(c\) by player \(1, R(a, f(a), c, g(a, c))\) holds in \(M\). Observethat strategy function \(f\) is a Skolem function for the quantifier\(\exists y\) in \(\phi\), and similarly \(g\) is a Skolem functionfor 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 interpretation 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 with reference to asingle play; this can only be done with 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 the correlatedgame, and false iff there is a winning strategy for player 1 in thecorrelated game. There are sentences which under these criteria areneither 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. In connection withformulas in prenex form, a Skolem function for an existentialquantifier is a function of the values assigned to the precedinguniversal quantifiers, butnot a function of thevalues 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 difference between semantic games formulated interms of arbitrary strategy functions and those whose strategyfunctions are in effect Skolem functions; the variable \(x\) in\((\exists y/x)\) can be ‘bound’ by any syntacticallypreceding quantifier carrying the variable \(x\). Hodges proposed toemploy the former formulation, 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 afixed arity), function symbols (again each with a fixed arity), andconstant symbols. The first-order logic of vocabulary \(\tau\) will bereferred to as \(\mathbf{FO}[\tau]\). It is assumed here that amongthe logical symbols of first-order logic there is theidentitysymbol (=). The identity symbol is syntactically a binaryrelation symbol, but its semantic interpretation is fixed in a waythat the interpretations of the items in the non-logical terminologyare not.

A formula of \(\mathbf{FO}[\tau]\) is innegation normalform, if all occurrences of the negation symbol \({\sim}\)immediately precede an atomic formula. The set offormulas ofIF first-order logic of vocabulary \(\tau\) (or\(\mathbf{IFL}[\tau])\) can be defined as the smallest set suchthat:

If \(\phi\) is a formula of \(\mathbf{FO}[\tau]\) in negationnormal form, \(\phi\) is a formula.
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.
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.
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.
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)(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/\forallx) 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\), a two-player zero-sum game \(G(\phi , M, g)\) between player 1and player 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\).

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).
If \(\phi = t_1 = t_2\) and \(M, g \vDash t_1 = t_2\), player 2wins (and player 1 loses); otherwise player 1 wins (and player 2loses).
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).
If \(\phi = {\sim}t_1 = t_2\) and \(M, g \not\vDash t_1 = t_2\),player 2 wins (and player 1 loses); otherwise player 1 wins (andplayer 2 loses).
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)\).
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)\).
If \(\phi = (\forall x/\exists y_1 ,\ldots ,\exists y_n)\psi\),player 1 chooses an element \(a\) from \(\rM\), and the rest of thegame is as in \(G(\psi , M, g[x/a]\)).
If \(\phi = (\exists x/\forall y_1 ,\ldots ,\forall y_n)\psi\),player 2 chooses an element \(a\) from \(\rM\), and the rest of thegame is as 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 leftor the right disjunct when the token is a disjunction; and an elementof the domain when the token 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 independence will be implemented directly in terms ofthearguments of the strategy 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 said tofollow 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 player 1 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 false in \(M\). Asmentioned in the end ofSection 2, there are semantic gamesin 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, player1 has the role of ‘falsifier’ and player 2 that of‘verifier.’ The roles may get switched, but only for onereason: when an occurrence of the negation symbol is encountered. Allclauses defining semantic games must be rephrased in terms of rolesinstead of players. It is the player whose role is‘verifier’ who makes a move for disjunctions andexistential quantifiers, and similarly the player whose role is‘falsifier’ who moves for conjunctions and universalquantifiers. When a formula \({\sim}\psi\) is encountered, the playerschange roles and the game continues with \(\psi\). Finally, if theencountered atomic formula is true, ‘verifier’ wins and‘falsifier’ loses, otherwise the payoffs are reversed. Thenegation \({\sim}\) is variably referred to asstrongnegation,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/\forall x)\).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 aswell:

(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. That is,bivalence fails in \(\mathbf{IFL}\). However, it should be noted thatit does not fail due to the postulation of a third truth-value or atruth-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 equivalentand falsity 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 universal andexistential quantifiers appear slashed,e.g.,

\[\phi : (\forall x)(\exists y/\forall x)(\forall z/\exists y) R(x, y, z).\]

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 containing noslashed 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 and non-truthdo not coincide. An extension of \(\mathbf{IFL}\) can be introduced,where it is possible to speak of the non-truth of sentences. To thisend, let us introduce a new negation symbol, \(\neg\), referred to asweak negation,contradictory negation orclassical 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\) isnot. For the crucial restriction that \(\neg\) may not occur in thescope of a quantifier, see Hintikka (1991: 49; 1996: 148). Forcounterexamples to this restriction see, however, Hintikka (1996: 148;2002c) and especially Hintikka (2006b) in which the so-calledfully extended IF first-order logic (FEIFL)is considered. InFEIFL, any occurrences of \(\neg\)are allowed which are subject to the following syntactic condition: if(Q\(x/W)\) is a quantifier in the syntactic scope of an occurrence of\(\neg\), then all quantifiers listed in \(W\) are likewise in thesyntactic scope of that occurrence of \(\neg\).

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

\[M, g \vDash \neg \phi \text{ iff } M, g \not\vDash \phi.\]

From the viewpoint of GTS, the connective \(\neg\) behaves in anunusual way. For all connectives of \(\mathbf{IFL}\), there is a gamerule (which can be seen as specifying the meaning of the connective).For contradictory negation there is no game rule, and its semantics isnot explained 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, to say that \(\neg\phi\) is true in \(M\) is to say that player 2 doesnot havea winning strategy in game \(G(\phi , M)\). If, again, there is indeeda winning strategy for player 2 in \(G(\phi , M)\), by stipulation\(\neg \phi\) is false in \(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 5it will be seen how Hintikka has proposed to make use of\(\mathbf{EIFL}\) when discussing issues in the philosophy ofmathematics.

4. Metalogical Properties of IF First-order Logic

The metalogical properties of \(\mathbf{IFL}\) have been discussed inseveral 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 over relationand function symbols in a first-order formula. The skolemization\(\mathrm{sk}[\phi]\) of an \(\mathbf{IFL}\) formula \(\phi\) is afirst-order formula of a larger vocabulary. It explicates interms of function symbols how existential quantifiers and disjunctionsymbols of \(\phi\) depend on preceding universal quantifiers. Forexample, a skolemization of the \(\mathbf{IFL}\) sentence \(\phi =(\forall x)(\exists y)(\forall z)(\exists v/\forall x)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)(\existsh)(\forall x)(\forall z)R(x, f(x), z, h(z))\). The first-ordersentence \(\mathrm{sk}[\phi]\) must not be confused with thesecond-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 set of\(\mathbf{IFL}\) formulas. The standard semantics of \(\mathbf{FO}\)is not the one provided by GTS, but the Tarskian semantics specifyingrecursively 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 thestandard sense iff there is a winning strategy 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 expressive power.

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, substantially speaking, afirst-order logic: the entities its quantified variablesrange over areindividuals, and so are all entities withwhich 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 achieved onthe first-order level.

IFL is more expressive than FO. The following areexamples of properties expressible in \(\mathbf{ESO}\) – andtherefore in \(\mathbf{IFL}\) – but not in \(\mathbf{FO}\):Dedekind-infinity of the domain, non-completeness of a linear order,ill-foundedness of a binary relation, disconnectedness of a graph,equicardinality of the extensions of two first-order formulas\(\phi(x)\) and \(\psi(x)\), infinity of the extension of afirst-order formula \(\phi(x)\), and the topological notion of openset (see,e.g., Hintikka 1996, Väänänen 2007).

As an example, the Dedekind-infinity of the domain may be considered.A set \(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}\):^[37]

\[(\exists t)(\forall x)(\exists z)(\forall y)(\exists v/\forall x)((x = y \leftrightarrow z = v) \wedge z \ne t).\]

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

\[(\exists f)(\exists g)(\exists t)(\forall x)(\forall y)((x = y\leftrightarrow f(x) = g(y)) \wedge f(x) \ne t).\]

Relative to a model \(M\), this \(\mathbf{ESO}\) sentence asserts theexistence of functions \(f\) and \(g\) and an element \(t\) such that\(f = g\) (implication from left to right), this function is injective(implication from right to left), and its domain is the whole domainof \(M\) but the element \(t\) does not appear in its range.Consequently the range is a proper subset of the domain of \(M\). Inother words, the sentence \(\phi_{inf}\) is true in a model \(M\) iffthe domain of \(M\) is infinite.

Be it still noted that when attention is restricted tofinitemodels, Ronald Fagin’s famous theorem (1974) connects\(\mathbf{ESO}\) and the complexity class \(\mathbf{NP}\): acomputational problem is solvable by an algorithm running innon-deterministic polynomial time iff it is definable in\(\mathbf{ESO}\) relative to the class of all finite structures. Thefollowing are \(\mathbf{NP}\)-complete properties and henceexpressible in \(\mathbf{IFL}\), over the class of all finite models:evenness of the domain, oddness of the domain, 3-colorability of agraph, and the existence of a Hamiltonian path on a graph.^[38]

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

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

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

The separation theorem holds in \(\mathbf{IFL}\) in a strengthenedform; the ‘separation sentence’ \(\theta\) is inparticular a sentence 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\) isvalid (true in all models), trivially \(\mathbf{FO}\) also has a soundand complete disproof procedure.^[40] The latter property extends to \(\mathbf{IFL}\) (while the formerdoes not, seeSubsect. 4.3):

Existence of a complete disproof procedure. (Hintikka1996: 68–70, 82) The set of inconsistent \(\mathbf{IFL}\)sentences is recursively enumerable.

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 thespecial case of \(\mathbf{FO}\), the strong negation \({\sim}\)clearly defines a semantic 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 IFlogic this property is lost in a very strong sense. In fact there areIF sentences \(\chi\) and \(\theta\) such that while \([\chi] =[\theta]\), the sets \([{\sim}\chi]\) and \([{\sim}\theta]\) are notonly 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})\) is not truthequivalent to any sentence of \(\mathbf{IFL}\). This follows from thewell-known fact that \(\mathbf{ESO}\) is not closed under negation 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 ofdetermined \(\mathbf{IFL}\) sentences. In the determined fragmentcontradictory negationis syntactically expressible by thestrong negation. By the strong inexpressibility of contradictorynegation, the determined fragment of \(\mathbf{IFL}\) has the sameexpressive power as \(\mathbf{FO}\). Membership in the determinedfragment is a sufficient but not necessary condition for an\(\mathbf{IFL}\) sentence to have its contradictory negationexpressible in \(\mathbf{IFL}\). The sentence \((\forall y)(\existsx/\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\) such that —,’i.e., it givesrise to truth-conditions expressible in \(\mathbf{ESO}\). By thestrong inexpressibility of contradictory negation, there is no single\(\mathbf{IFL}\) sentence, not translatable into \(\mathbf{FO}\),whose contradictory negation has a truth-condition of that form. Thisfact makes 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 interpretedby introducing an additional component in game positions: amode. At the play level, the negation \(\neg\) triggers notonly a role switch (like the dual negation \({\sim})\), but it alsoinvolves changing the mode from positive to negative or vice versa.The semantic effect of modes becomes visible at the strategy level:modes regulate the way in which the truth condition of a sentenceinvolves existentially or universally quantifying over strategyfunctions. Like independence indications, also occurrences of \(\neg\)are, then, interpreted in terms of conditions that act on the strategylevel. For related research, see Figueiraet al. (2011,2014).

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 is the same asthe class of problems whose complement is solvable in \(\mathbf{NP}\).By Fagin’s theorem (1974), this open problem can be equivalentlyformulated as follows: Is \(\mathbf{IFL}\) closed under negationover finite models? That is, is there for every IF sentence\(\phi\) another IF sentence \(neg(\phi)\) such that for any finitemodel \(M\), \(neg(\phi)\) is true in \(M\) iff \(\phi\) is not truein \(M\)? Proving that the answer is negative would settle thenotorious \(\mathbf{P} = \mathbf{NP}\) problem, i.e., establish thatthere are computational problems for which one can efficientlyverify whether a proposed solution is correct although onecannot efficientlyfind a solution.^[44]

4.3 Failure of axiomatizability

As is well known, \(\mathbf{FO}\) admits of a sound and complete proofprocedure: there is a mechanical way of generating precisely thosefirst-order sentences that are valid (true in all models). This factcan also be expressed by saying that \(\mathbf{FO}\) is axiomatizable,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}\) is semantically 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 is true in all and only infinitemodels. Note, then, that an \(\mathbf{FO}\) sentence \(\chi\) is truein allfinite models iff the \(\mathbf{IFL}\) sentence\((\phi_{inf} \vee \chi)\) is valid. Given a valid \(\mathbf{IFL}\)sentence, it can be effectively checked whether the sentence issyntactically of the form \((\phi_{inf} \vee \chi)\), where \(\chi\)is a first-order sentence. Hence the recursive enumeration of allvalid \(\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 isnotrecursively 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}\) which doesnot 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 realm oflogic, thus delineated.^[48]

Hintikka finds this type of allegation unfounded. First,\(\mathbf{IFL}\) shares many of the important metalogical results with\(\mathbf{FO}\) (cf.Subsect. 4.1). Second, just like\(\mathbf{IFL}\), also \(\mathbf{FO}\) can be translated intosecond-order logic. The only difference is that in the former case alarger variety of quantifier (in)dependencies must be encoded bySkolem functions than in the latter. Why would the former translationrender \(\mathbf{IFL}\) a part of mathematics while the latter wouldallow \(\mathbf{FO}\) to remain a logic (Hintikka 1991: 26–27)?Third, one must make a distinction between what is needed tounderstand an \(\mathbf{IFL}\) sentence, and what is needed tomechanically 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 know whatthings are like when it istrue, not to know what things arelike when it islogically true (Hintikka 1995: 13–14).Fourth, because of non-axiomatizability, the valid inference patternsin \(\mathbf{IFL}\) cannot be exhausted by any recursive enumeration.Insofar as important mathematical problems can be reduced to questionsabout the validity of \(\mathbf{IFL}\) formulas (Subsect.5.3), progress in mathematics can be seen to consist (not of thediscovery of stronger set-theoretical axioms but) of ever morepowerful rules for establishing validity in \(\mathbf{IFL}\) (Hintikka1996: 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 determined bythe semantic attributes of its constituent expressions and thestructure of \(E\). In particular, the semantic attribute of interest(e.g., truth) may be determined in terms of one or moreauxiliary 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 be given acompositional semantics.^[54] The semantics is given by recursively defining the satisfactionrelation ‘\(M \vDash_X \phi\)’ (read: \(\phi\) issatisfied in \(M\) by \(X)\), where \(X\) is aset ofvariable assignments. While the Tarskian semantics for \(\mathbf{FO}\)is in terms of single variable assignments, Hodges’s semanticsemploys sets of variable assignments. The game-theoretical semanticsof \(\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 the condition \(M \vDash_{\{g\}}\phi\) holds. Due to Hodges’s semantic clauses for existentialquantifiers and disjunctions involving independence indications, theevaluation of \(\phi\) relative to the singleton set \(\{g\}\)generally leads to evaluating syntactic components of \(\phi\)relative to sets of (possibly infinitely) many variable assignments.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 existence of\(\mathbf{IFL}\) proves that rejecting compositionality is no obstaclefor the formulation of a powerful logic (Hintikka 1995). It shouldalso 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 interms 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 latter evaluates 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-type compositionalsemantics 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 ‘satisfactionby a single variable assignment’ would be a natural auxiliaryattribute in connection with \(\mathbf{IFL}\). By the result ofCameron and Hodges, no semantics for \(\mathbf{IFL}\) exists thatwould be compositional in this restricted 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 thestandard model \(N\) of Peano’s axioms. Each sentence \(\phi\)of vocabulary \(\tau\) can then be represented by a natural number\(\ulcorner \phi \urcorner\), its Gödel number. It is assumedthat \(\tau\) contains a numeral \(\boldsymbol{{}^\ulcorner \phi{}^\urcorner}\) for each number \(\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 that every sentence \(\phi\) of \(L\) satisfies:

\[N \vDash \phi \text{ iff } N \vDash \TRUE(\boldsymbol{{}^\ulcorner \phi {}^\urcorner}),\]

then \(\TRUE(x)\) is said to be atruth-predicate(explicit truth-definition) of logic \(L\)in logic \(L'\) for the model \(N\). By Alfred Tarski’s famoustheorem of theundefinability of truth (Tarski 1933), thereis no truth-predicate for \(\mathbf{FO}\) in \(\mathbf{FO}\) itselffor the model \(N\). More generally, Tarski showed that under certainassumptions, a truth-definition for a logic \(L\) can only be given ina metalanguage which is essentially stronger than \(L\). One of theassumptions is that the negation used behaves like contradictorynegation. On the other hand, Tarski also pointed out that an implicittruth-definition for \(\mathbf{FO}\) in \(\mathbf{FO}\) itselfis possible. Let \(\tau\) be an arithmetical vocabulary, andlet us stay with 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-definition for\(\mathbf{FO}[\tau]\) in \(\mathbf{FO}[\tau \cup \{\TRUE\}]\) for\(N\), if for every \(\mathbf{FO}[\tau]\) sentence \(\phi\), thefollowing holds:

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

Intuitively, \(\TRUE^N\) is the set of those natural numbers that areGödel numbers of true arithmetic sentences of vocabulary\(\tau\); and \(\psi(x)\) says that \(x\) is a Gödel number inthe extension of the predicate \(\TRUE\). The formula \(\psi(x)\) is aconjunction including clauses that mimic, on the object-languagelevel, the metalogical recursive clauses of the Tarski-typetruth-definition for \(\mathbf{FO}\).E.g., one of theconjuncts is

\[\begin{align*} (\forall y)(\forall z)(y = \boldsymbol{{}^\ulcorner \chi {}^\urcorner} &\wedge z = \boldsymbol{{}^\ulcorner \theta {}^\urcorner} \wedge x = \boldsymbol{{}^\ulcorner (\chi \wedge \theta) {}^\urcorner} \rightarrow \\ &[\TRUE(x) \leftrightarrow (\TRUE(y) \wedge \TRUE(z))]).\end{align*}\]

The implicit nature of the truth-definition is seen from the fact thatthe predicate \(\TRUE\) appears on both sides of the equivalence signin these clauses.^[57] The above implicit truth-definition of \(\mathbf{FO}\) for \(N\) isof the form ‘there is a set \(S\) interpreting the predicate\(\TRUE\) such that \(\psi(x)\).’ Thus the implicittruth-definition of \(\mathbf{FO}\) in \(\mathbf{FO}\) gives rise tothe 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 contradict Tarski’s undefinability result,because here non-determined sentences are possible; the negation usedis not contradictory negation.^[59]

Tarski (1983) adopted a view according 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 compositional semantics,but it admits of formulating a self-applied truth-predicate. Theproposed reason why Tarski believed it not to be possible to discussthe notion of truth in natural languages themselves cannot, then, beentertained from the viewpoint of \(\mathbf{IFL}\). For, the case of\(\mathbf{IFL}\) shows that the failure of Tarski-typecompositionality for a language does not entail the impossibility forthe language to define its own truth-predicate.^[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}\) but notin \(\mathbf{IFL}\) (Hintikka 1996: 188–190): finiteness of thedomain, well-foundedness of a binary relation, connectedness of agraph, 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, and the existenceof a complete disproof procedure all fail for \(\mathbf{EIFL}\)(Hintikka 1991: 49, 1996: 189). No self-applied truth-predictate ispossible for \(\mathbf{EIFL}\). The definition of such atruth-predicate would have to contain the clause

\[\begin{align*}(\forall y)(y = \boldsymbol{{}^\ulcorner \theta {}^\urcorner} &\wedge x = \boldsymbol{{}^\ulcorner \neg \theta {}^\urcorner} \rightarrow \\ &[\TRUE(x) \leftrightarrow \neg \TRUE(y)]).\end{align*}\]

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 and satisfiability problems of the full second-order canbe effectively reduced to the corresponding problems concerning\(\mathbf{EIFL}\). Namely, why cannot a second-order sentence simplybe thought of as a two-sorted first-order sentence? Because in orderto capture the standard interpretation 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 sort 2having those and only those elements as members, for all arities \(n\)such that the second-order sentence contains a quantifier \((\existsR)\) where \(R\) is \(n\)-ary.^[64] Now, such additional conditions can be expressed by a finiteconjunction \(X\) of \(\mathbf{USO}\) sentences, where\(\mathbf{USO}\) (universal second-order logic) is obtainedfrom \(\mathbf{FO}\) by allowing universal quantification overrelation and function symbols in a first-order formula. Each of these\(\mathbf{USO}\) sentences can be expressed as the contradictorynegation of an \(\mathbf{ESO}\) sentence and therefore as thecontradictory negation of an \(\mathbf{IFL}\) sentence. Consequently,there is an \(\mathbf{IFL}\) sentence \(Y\) such that \(X\) itself islogically equivalent to \(\neg Y\). And here \(\neg Y\) is a sentenceof \(\mathbf{EIFL}\). Therefore, if \(\phi\) is a second-ordersentence and \(\phi^*\) its reconstruction in two-sorted first-orderlogic, we have: \(\phi\) is satisfiable iff \((X \wedge \phi^*)\) issatisfiable iff \((\neg Y \wedge \phi^*)\) is satisfiable. And:\(\phi\) is valid iff \(\phi^*\) is a logical consequence of \(X\) iff\((\neg X \vee \phi^*)\) is valid iff \((Y \vee \phi^*)\) is valid.Here, both \((\neg Y \wedge \phi^*)\) and \((Y \vee \phi^*)\) aresentences of \(\mathbf{EIFL}\), the latter even a sentence of\(\mathbf{IFL}\). It follows that the satisfiability (validity) of anysecond-order sentence can be expressed as the satisfiability(respectively, validity) of a sentence of \(\mathbf{EIFL}\).^[65]

Algebraic structure. The two negations available in\(\mathbf{EIFL}, \neg\) and \({\sim}\), agree on true sentences, aswell as on false ones: if \(\phi\) is true (false) in \(M\), then both\({\sim}\phi\) and \(\neg \phi\) are false (true) in \(M\). Bycontrast, if \(\phi\) is non-determined in \(M\), then \({\sim}\phi\)is non-determined as well, but \(\neg \phi\) is true. The combination\(\neg{\sim}\) of the two negations 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 the question of the algebraic structure induced by theseoperators, when any two truth equivalent sentences are identified. Theoperators \(\neg , \wedge\), and \(\vee\) give rise to a Booleanalgebra – but what does the strong negation \({\sim}\) add tothis structure?

Restricting attention to truth equivalence, \({\sim}\) is definablefrom the operators \(\neg\) and \(\neg{\sim}\). For, \({\sim}\phi\) istrue in \(M\) iff \(\neg(\neg{\sim}\phi)\) is true in \(M\). Insteadof \({\sim}\), the operator \(\neg{\sim}\) may then be considered.Hintikka points out that the propositional part of \(\mathbf{EIFL}\)(formulated in terms of the operators \(\vee , \wedge , \neg\) and\(\neg{\sim})\) is a Boolean algebra with an operator in the sense ofJónsson & Tarski (1951). The additional 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 to Gödel(1933) and McKinsey & Tarski (1948), intuitionistic propositionallogic can be interpreted in \(\mathbf{S4}\), via a translation \(t\)such that \(\phi\) is intuitionistically provable iff \(t(\phi)\) is avalid \(\mathbf{S4}\) formula. Thus, intuitionistic propositionallogic 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

\[Q[z_1] \ldots [z_k] (\phi_1 ,\ldots ,\phi_k)\]

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 ageneralized quantifier \(Q_{\ge \kappa}\) such that \(Q_{\ge \kappa}zP(z)\) is true in a model \(M\) iff there are at least \(\kappa\)elements that satisfy the predicate \(P\). Hence generalizedquantifiers can besemantically higher-order. (The notion ofcardinality is a higher-order notion.) The fact that the variables ina formula range over individuals only, does not offer a reliablecriterion for the logic’s first-order status.

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 as theset 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 strong commitmentto full second-order logic. Hintikka (2006a: 476–477) looks atthese results from the opposite direction: for him they mean thatindeed one can speak of validity in full second-order logic in termsof validity in \(\mathbf{IFL}\). What is more, Hintikka (1997) affirmsthat even \(\mathbf{EIFL}\) is a first-order logic. If so, anymathematical theory that can be expressed by the truth of an\(\mathbf{EIFL}\) sentence is likewise free from problems of setexistence.

Hintikka’s position leads to a puzzle. If \(\phi\) is a sentenceof \(\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 set ofall strategies of player 2: \(\neg \phi\) is true in model \(M\) iffforall strategies of player 2 in game \(G(\phi , M)\), thereis a sequence of moves by player 1 such that player 1 wins theresulting play. The set of all strategies of player 2 is undeniably ahigher-order entity. How can commitment to entities other thanindividuals be said to have been avoided here? Can the meaning of thesentence \(\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 existenceof a full set of Skolem functions for \(\phi\). In Hintikka’sview, then, our ordinary notion of first-order truth is conceptualizedin terms of (existential) second-order logic. What happens when thisidea is applied to axiomatic set theory, say Zermelo-Fraenkel settheory with the Axiom of Choice \((\mathbf{ZFC})\)? It should be bornein mind 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 ‘Skolemfunctions’ 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‘Skolem functions’ asserted to exist by \(\phi^*\)actually exist in the model.

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, byTarski’s undefinability result the situation cannot be improvedby adding further axioms to \(\mathbf{ZFC}\). In Hintikka’sjudgment, axiomatic set theory is a systematic but futile attempt tocapture on the first-order level truths of standardly interpretedsecond-order logic. Like Gödel (1947), also Hintikka holds thatthe concepts needed to state, say, the continuum hypothesis aresufficiently well-defined to determine the truth-value of thisconjecture. The continuum hypothesis does not receive its meaning fromphrasing it in \(\mathbf{ZFC}\). Gödel and Hintikka agree thatthe independence results due to Gödel himself and Paul Cohen donot by themselves show anything about the truth or falsity of thecontinuum hypothesis. But unlike Gödel, Hintikka finds thederivability of any conjecture whatever in \(\mathbf{ZFC}\) (or in anyof its extensions) simply irrelevant for the truth of the conjecture.For Hintikka, it is a ‘combinatorial’ question whetherevery infinite subset of the reals is either countable or else has thecardinality of the set of all reals – a question properlyconceptualized within second-order logic. This is what Hintikka takesto be the pretheoretical sense of the truth of the continuumhypothesis, and that 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 all normalmathematical reasoning on the first-order level. This result isessentially dependent on the acceptability of Hintikka’s claimthat \(\mathbf{EIFL}\) is ontologically committed to individuals only(Subsect. 5.1). But how would \(\mathbf{EIFL}\) serve toreconstruct an important part of all mathematical reasoning?

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

Any higher-ordermathematical theory \(T\) gives rise to amany-sorted first-order theory \(T^*\). If the theory is finite, thereis a finite conjunction \(J\) formulated in \(\mathbf{EIFL}\) –equivalent to a sentence of \(\mathbf{USO}\) and therefore equivalentto the contradictory negation of an \(\mathbf{ESO}\) sentence and soindeed equivalent to the contradictory negation of an \(\mathbf{IFL}\)sentence – expressing the requirement that the standardinterpretation of higher-order logic is respected. The question of thetruth of the higher-order theory \(T\) is thus reduced to the truth ofthe sentence \((J \wedge T^*)\) of \(\mathbf{EIFL}\) (cf.Subsect. 4.6).

Themathematical problem of whether a given sentence \(C\) isa logical consequence of a finite higher-order theory \(T\) coincideswith the problem of whether the second-order sentence \((\neg(J \wedgeT^*) \vee C^*)\) is valid. Recalling that there is a sentence \(\chi\)of \(\mathbf{IFL}\) such that \(J\) is equivalent to \(\neg \chi\), itfollows that \(\neg(J \wedge T^*)\) is equivalent to a sentence of\(\mathbf{IFL}\). Consequently there is a sentence of \(\mathbf{IFL}\)which is valid iff the sentence \((\neg(J \wedge T^*) \vee C^*)\) isvalid (cf.Subsect. 4.6). Mathematical problems can beunderstood as questions of thevalidity of an\(\mathbf{IFL}\) sentence. Among mathematical problems thusreconstructible using \(\mathbf{IFL}\) are the continuum hypothesis,Goldbach’s conjecture, Souslin’s conjecture, the existenceof an inaccessible 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 the statusof 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 carried out(Hintikka 1996: 205, 2006a: 477). For a critique of Hintikka’sconclusions, see Väänänen (2001), Feferman (2006), andBazzoni (2015).

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 a representationof an English sentence. From this it would follow that the logic ofidiomatic English quantifiers is much stronger than \(\mathbf{FO}\),and that no effective procedure exists for classifying sentences asanalytical 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 thisquestion 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 desideratum is satisfied by an answer pointing out a function\(f\) which yields for each person a suitable admired person. Such afunction can behis or her father. Importantly, the value\(f(b)\) of this function only depends on the person \(b\)interpreting ‘everybody,’ but does not depend on thescenario \(w\), compatible with the questioner’s knowledge, thatinterprets the construction ‘I know.’ Interestingly, thedesideratum \(K_I (\forall x)(\exists y/K_I)\) admires\((x, y)\) isnot expressible without an explicit independence indicator. It is alsoworth noting that this case cannot be represented in the notation of\(\mathbf{FPO}\). This is because several types of semanticinteractions are possible among quantifiers and intensional operators,and blocking interactions of one type does not automatically blockinteractions of other types. In the example, the witness of \(\existsy\) must not vary with the scenario \(w\) interpreting the operator\(K_I\), but still the values of both variables \(x\) and \(y\) mustbelong to the domain of the particular scenario \(w\) chosen tointerpret \(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, ade dicto attribution suchas

\(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 ‘Ralphbelieves 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 semantics relativeto 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

Syntactically slash logic uses quantifiers like \((\exists x/y)\)instead of quantifiers such as \((\exists x/\forall y)\). Semanticallyslash logic is otherwise like \(\mathbf{IFL}\) except that itsgame-theoretical semantics is based on the idea that a player’sstrategy functions may utilize as their argumentsanypreceding moves made in the current play, save for those whose use is,by the slash notation, explicitly indicated as forbidden (cf.Sect. 3). That is, also a player’s own earlier movesmay appear as arguments of a strategy function. This can make adifference in the presence of imperfect information. For example,consider evaluating the slash-logic sentence \((\forall x)(\existsy)(\exists z/x) x = z\) containing the vacuous quantifier \(\existsy\). This sentence is true on a two-element domain, since player 2 cancopy as the value of \(y\) the value that player 1 has chosen for\(x\), and then select the value of \(z\) using a strategy functionwhose only argument is the value of \(y\). (For this phenomenon of‘signaling,’ see Hodges 1997a, Sandu 2001, Janssen &Dechesne 2006, Barbero 2013.) By contrast, the IF sentence \((\forallx)(\exists y)(\exists z/\forall x) x = z\) fails to be true on such adomain, since there a strategy function for \((\exists z/\forall x)\)must be a constant, and no such strategy function can guarantee a winfor player 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}\).

All authors having studied slash logic, apart from Hodges himself,have opted for not following Hodges’s terminological recommendationmentioned at the beginning of Section 3: they have referred to slashlogic as ‘IF logic.’

Kuusisto (2013) studies the expressive power of fragments of slashlogic whose formulas are formed without employing the identity symbol.Kontinenet al. (2014) investigate the complexity-theoreticproperties of the two-variable fragment of slash logic and comparethis fragment to the corresponding fragment of dependence logic.Hodges (1997a,b) and Figueiraet al. (2009, 2011, 2014)discuss an extension of slash logic in which the contradictorynegation of slash-logic sentences can be expressed.

In Sevenster (2014), patterns of quantifier dependence andindependence in quantifier prefixes of slash-logical formulas aresystematically studied in order to determine which quantifier prefixesallow slash logic to gain the expressive power of \(\mathbf{ESO}\).Sevenster identifies two such patterns – thesignalingpattern and theHenkin pattern – and proves that theyare able to express \(\mathbf{NP}\)-hard decision problems. He furthershows that these two are the only patterns allowing slash logic toexceed the expressive power of \(\mathbf{FO}\) insofar as attention isconfined to formulas in prenex form. An example of the signalingpattern would be \( (\forall u)(\exists v)(\exists w/u) \) and of theHenkin pattern \( (\forall x)(\exists u)(\forall y)(\exists v/x,u) \).^[94]

Barbero (2021) and Barberoet al. (2021) take up the task ofinvestigating fragments of the general syntax of slash logic (not allof whose formulas are in prenex form). Thereby these authors wish tostudy systematically those expressive resources of slash logic thatallow it to exceed the expressive power of \(\mathbf{FO}\) and that donot simply derive from its capacity to mimick Henkin quantifiers.While many of the features studied in these two papers depend on theEigenart of slash logic, the phenomenon ofsignaling bydisjunction occurs in IF logic, as well. In Section 3.3, it wasseen that the IF-logical sentence \((\forall x)(\exists y/\forall x) x= y\) is non-determined in any model whose domain has exactly twoelements. The slash-logical sentence \((\forall x)(\exists y/ x) x =y\) is likewise non-determined in such a model. Now, consider theresult of replacing in the latter sentence the expression \((\existsy/ x) x = y\) by the disjunction \(((\exists y/x) x = y \vee (\existsy/ x) x = y))\), with a token of the initial expression in bothdisjuncts: \[(\forall x)((\exists y/ x) x = y \vee (\exists y/x) x = y).\] The sentence that has been thus obtained isactuallytrue in a model whose domain consists of the objects\(a\) and \(b\). Let \(f\), \(g\), and \(h\) be respectively thestrategy functions of player 2 for the unique token of the disjunctionsymbol, the left token of the existential quantifier, and the righttoken of the existential quantifier – defined as follows. First,\(f\) selects the left disjunct if player 1 has chosen \(a\) as avalue of \(x\), selecting the right disjunct otherwise. Further, \(g\)and \(h\) are constants (zero-place functions): \(g= a\) and \(h= b\).The set \(\{f, g, h\}\) is clearly a winning strategy for player 2.Either of the tokens of the existential quantifier occur in a specificdisjunct. Using the strategy function \(f\) to arrive at such adisjunct makes sure that the disjunct arrived at reveals the choicethat player 1 has made to interpret \(\forall x\). The constants \(g\)and \(h\) are selected so as to render this information explicit.Thus, the resulting values of \(x\) and \(y\) indeed satisfy theformula \(x= y\). By the same reasoning it is seen that the sentence\((\forall x)((\exists y/ \forall x) x = y \vee (\exists y/\forall x)x = y)\) of \(\mathbf{IFL}\) is true in the model considered.

6.2 Dependence logic

Jouko Väänänen (2007) formulated a new approach to IFlogic that he dubbeddependence logic \((\mathbf{DL})\); forfurther work on \(\mathbf{DL}\), seee.g. Kontinenetal. (2013). The syntax of \(\mathbf{DL}\) is obtained from thatof \(\mathbf{FO}\) by allowing atomic formulas of the followingspecial form:

\[=(x_1 ,\ldots ,x_n; x_{n+1}).\]

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:

\(x_1\)	\(x_2\)	\(x_3\)
7	5	8

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:

\(x_1\)	\(x_2\)	\(x_3\)
7	5	8
9	5	6
7	11	8
7	3	8
9	19	6

The set \(X\) consisting of the above five assignments satisfies theformula \(=(x_1\); \(x_3)\): the value of \(x_3\) depends only on thevalue 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 interesting novelty of \(\mathbf{DL}\) is that claimsabout variable dependencies are made at the atomic level. Quantifiersof \(\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 from itsgreater 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 by it– 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(2): 254–280.
–––, 2017, “Cooperation in Games andEpistemic Readings of Independence-Friendly Sentences,”Journal of Logic, Language, and Information, 26(3):221–260.
–––, 2021, “Complexity of Syntactical TreeFragments of Independence-Friendly Logic,”Annals of Pureand Applied Logic, 172(1): article 102859 (43 pages).
Barbero, F., Hella, L., and Rönnholm, R., 2021,“Independence-Friendly Logic Without HenkinQuantification,”Archive for Mathematical Logic, 60:547–597.
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.
Bazzoni, A., 2015, “Hintikka on the Foundations ofMathematics: IF Logic and Uniformity Concepts,”Journal ofPhilosophical Logic, 44(5): 507–516.
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.
–––, 2011, “On the Expressive Power ofIF-Logic with Classical Negation” inLogic, Language,Information, and Computation, L. Beklemishev and R. de Queiroz(eds.), Berlin: Springer, pp. 135–145.
–––, 2014, “Independence Friendly Logicwith Classical Negation via Flattening is a Second-Order Logic withWeak Dependencies,”Journal of Computer and SystemSciences, 80: 1102–1118.
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 aLanguage 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 2013Edition), E. Zalta (ed.), URL = <https://plato.stanford.edu/archives/spr2013/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., Kuusisto, A., Lohmann, P., and Virtema, J. (eds.),2014, “Complexity of Two-Variable Dependence Logic andIF-Logic,”Information and Computation, 239:237–253.
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.
Kuusisto, A., 2013. “Expressivity of Imperfect InformationLogics without Identity,”Studia Logica, 101(2):237–265.
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 MeetsNelson’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.
–––, 2014, “Truth and Probability inGame-Theoretical Semantics,”Teorema: Revista Internacionalde Filosofía, 33(2): 151–170.
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.
–––, 2014, “Dichotomy Result forIndependence-Friendly Prefixes of Generalized Quantifiers,”Journal of Symbolic Logic, 79(4): 1224–1246.
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 topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO).
Enhanced bibliography for this entryatPhilPapers, with links to its database.

Other Internet Resources

[Please contact the author with suggestions.]

Open access to the SEP is made possible by a world-wide funding initiative.
The Encyclopedia Now Needs Your Support
Please Read How You Can Help Keep the Encyclopedia Free

Browse

About

Support SEP

Mirror Sites

View this site from another server:

USA (Main Site)Philosophy, Stanford University

Info about mirror sites

Library of Congress Catalog Data: ISSN 1095-5054

Movatterモバイル変換