Notes to Independence Friendly Logic
1. The work of providing solid foundations to analysis was initiated by Augustin Cauchy (1789–1857).
2. For references to uses of the device ‘depends on…but not on…’ in actual mathematical literature, see Dechesne (2005), Hintikka (1996), Hintikka & Kulas (1983), Hodges (1997a, 1997b), Mann et al. (2011), Mostowski & Krynicki (1995), Pietarinen (2001); for dependent quantifiers, see also Quine (1970).
3. In order to properly assess the origins of IF first-order logic in light of available documents, also the following should be noted. Hintikka writes (1991: 7): ‘IF first-order languages are introduced and studied in my paper, "What is Elementary Logic?" (forthcoming).’ This paper appeared as Hintikka (1995). Hintikka (1991: 8,67) refers to the papers published in Sandu's Ph.D. thesis, saying that in them Sandu has also studied independence friendly languages; he mentions specifically Sandu's study of informationally independent connectives in Sandu & Väänänen (1992), as well as Hintikka & Sandu (1989). In Hintikka & Sandu (1997: 368) it is stated that IF languages were introduced in Hintikka & Sandu (1989) – contradicting what is said in Hintikka (1991). Hintikka (1996: 52) mentions Sandu (1993) and Hintikka (1995) as sources for earlier discussions on IF first-order logic; Hintikka & Sandu (1989) is not mentioned. In Sandu & Hyttinen (2001: 37) it is said that IF first-order languages were introduced in Hintikka (1996), but on the next page it is affirmed that these languages were introduced in Hintikka & Sandu (1989).
The slash notation used for indicating quantifier independence appears already in Hintikka (1988: 22). A general notation for separately indicating those preceding operators of which a given one is independent – more general than the notation of partially ordered quantifiers – was proposed in connection with epistemic logic even earlier, in Hintikka (1982: 164).
4. Thoralf Skolem (1887–1963) introduced Skolem functions in Skolem (1920). For uses of Skolem functions in model theory, see e.g. Hodges (1993). They have also found use in automated theorem proving; cf. Portoraro's entry on Automated Reasoning in this encyclopedia. On how they are employed in linguistics, cf. footnote 90.
5. I.e., a function with zero arguments.
6. Here and henceforth, ‘iff’ abbreviates ‘if and only if.’
7. The function f yields a witness for ∃y depending on the interpretation of ∀x, and similarly g provides a witness for ∃w depending on the interpretation of ∀z.
8. Henkin introduced the general idea of dependent quantifier Qm, n, d, which in effect leads to the notion of (arbitrary) partially ordered quantifier (p.o.q.) with m universal quantifiers and n existential quantifiers, where d is a function that determines for each existential quantifier on which universal quantifiers it depends; m and n may be any cardinal numbers. The notion of finite p.o.q. results by letting m and n be finite. Well-known papers on finite p.o.q.s include Enderton (1970), Walkoe (1970), Barwise (1979), Krynicki & Lachlan (1979), Blass & Gurevich (1986), Krynicki (1993); for an overview, see Krynicki & Mostowski (1995). In Barwise (1979) generalized partially ordered quantifiers were also studied.
9. FPO is not syntactically closed under negation, conjunction, or disjunction.
10. For a critique, see Hodges (2001), Marion (2009).
11. Let us agree that player 1 is male (‘he’) and player 2 female (‘she’). In the literature, the players have been called by many names: Myself (or I) and Nature, ∃ and ∀, Eloise and Abelard, as well as the initial Verifier and the initial Falsifier (by reference to the players' initial roles).
12. Henceforth, whenever M is a model, M is its domain.
13. Note that while quantifier moves pertain to ‘objects out there’ (elements of the domain), moves for conjunction and disjunction concern syntactic items (conjuncts and disjuncts).
14. For abstract and strategic meaning, cf. also Hintikka & Sandu (1997: 397–398). For research on GTS and natural language, see Saarinen (1979), Hintikka & Sandu (1991), Sandu (1991), Pietarinen (2001), Clark (2012); Hintikka & Sandu (1997) offers an overview.
15. In any event, this is the way in which Hintikka uses the word ‘Skolem function,’ see, e.g., Hintikka (1996: 31; 2002). Cf. Sandu (2001), where ‘two ways of Skolemizing’ are discussed. One of the two ways corresponds to Hintikka's notion of Skolem function, the other corresponding to a generalized notion of strategy function. What results from the latter choice is, in Hodges's terminology, a slash logic, not an IF logic; cf. the quote below.
16. Excluding slash logic still underdetermines the choice between several proposed formulations of IF first-order logic. However, all these formulations use in their semantics Skolem functions, or strategy functions all of whose arguments are moves by the opponent. Publications in which a slash logic is actually formulated – yet referred to as an IF logic – include Hyttinen & Sandu (2000), Pietarinen (2001), Väänänen (2002), Sandu (2007), Caicedo et al. (2009) and Mann et al. (2011).
17. For the term ‘regular formula,’ see Caicedo et al. (2009). The logical symbols of first-order logic considered here are negation (~), disjunction (∨), conjunction (∧), existential quantifier (∃), universal quantifier (∀), and parentheses. A vocabulary (signature, non-logical terminology) is any countable set τ of relation symbols (each of which carries a fixed arity), function symbols (again each with a fixed arity) and constant symbols. See Shapiro's entry on Classical Logic in this encyclopedia for a detailed presentation of first-order logic.
Note that implication is not among the logical symbols of IF first-order logic. Material implication (φ → ψ) can be defined in the so-called extended IFL (Subsect. 3.4) by the formula (¬φ ∨ ψ). In the special case that φ is ‘truth equivalent’ to a first-order formula (see Subsect. 4.2), it is possible to express (φ → ψ) in IFL by the formula (~φ ∨ ψ). For different ways of treating conditionals in GTS, including conditionals in natural language, see e.g. Hintikka & Kulas (1983; Ch. 3), Hintikka & Sandu (1991).
18. In the literature, the syntax of IFL is invariably given for formulas. By contrast, the semantics is often formulated for sentences only (see Hintikka 1991, 1995, 1996; Hintikka & Sandu 1996, 1997; Sandu 1993, 1994). In Sandu (1996, 1998), the semantics is given for arbitrary formulas.
19.
See, e.g.,
Hintikka (1991, 1995, 1996), Sandu (1993, 1994); for defining GTS for
FO in this way, see e.g. Hintikka & Kulas (1983),
cf. Hintikka (1968, 1973a). The semantics of IFL to be
presented will be its game-theoretical semantics, sketched in Hintikka
& Sandu (1989) and Hintikka (1991) and presented in a more detailed
fashion e.g. in Hintikka (1995, 1996), Sandu (1993, 1994). The
semantics is defined explicitly to arbitrary formulas and variable
assignments in Sandu (1996, 1998). The original approach to the GTS of
first-order logic in Hintikka (1968) avoided variable assignments by
letting the players name the objects they had chosen; this approach
could be adapted to IFL as well. Janssen
(2002) and Janssen & Dechesne (2006) address the issue of whether
the game-theoretical semantics of IFL does justice to
the idea of ‘informational independence’ among logical operators.
20. Models (τ structures) are termed interpretations in Shapiro's entry on Classical Logic in this encyclopedia. Recall that in the degenerate case that n = 0, the expression (∃x/∀y1,…,∀yn) equals by stipulation (∃x), and similarly in the case of the other connectives followed by a slash. This is why we need not give separate clauses for (∃x), ∨, (∀x), and ∧. If g is a variable assignment, g[x/a] is the variable assignment which is otherwise like g but maps the variable x to the object a.
21. The notion of the strategy of a player must not be confused with the game-theoretical notion of strategy profile. The latter means a set of strategies, one strategy for each player. For semantic games, a strategy profile would be a set {F1, F2}, where each Fi itself is a set, namely a set of strategy functions of player i.
22. The term ‘dissatisfaction’ is used as a dual of ‘satisfaction.’ The distinction between these notions generalizes the distinction between ‘truth’ and ‘falsity.’ Hodges (1997a) conceptualizes a related distinction in his compositional framework by speaking of ‘trumps’ and ‘cotrumps.’
23. To be precise, below game G(φ, M) equals by definition game G(φ, M, g0), where g0 is an arbitrarily chosen variable assignment.
24. When negation symbol is allowed to appear in arbitrary syntactic positions in FO formulas, it is no longer the case that universal quantifiers and conjunction symbols are automatically of universal force while existential quantifiers and disjunction symbols are of existential force. The force of an operator depends on the number of negation signs in whose syntactic scope it lies. If we wish to retain in the general setting the characteristic feature distinguishing IFL from slash logic – namely the requirement that strategy functions of a player only take as arguments moves made by the adversary – the syntax must be formulated paying attention to the force that each quantifier has (cf. however Sandu 1993, 1994; Hintikka & Sandu 1997: 373). In the general formulation of IFL, hence formulated, an operator O can be marked as independent from any preceding quantifiers of the opposite force, but not from any preceding quantifier having the same force as O. For example (∀x)~(∃y)(∀z/∀x,∃y) S(x, y, z) would be well formed, unlike ~(∀x)~(∃y/∀x) R(x, y).
25. See e.g. Hintikka (1991: 147, 2002: 409), Hodges (1997a: 546), Sandu (1993, 1994).
26. For non-determinacy and IF logic, see Hintikka (1996), Burgess (2003), Väänänen (2006).
27. No third truth-value is stipulated in the semantics of IFL. Truth-value gaps may arise when neither truth nor falsity can be meaningfully ascribed to a sentence (because a presupposition of the sentence is not satisfied). This is not what non-determinacy means. Non-determinacy is a model-relative complex negative property, which can be ascribed to a sentence. A sentence has this property iff neither of the simple positive properties of truth and falsity can be correctly ascribed to the sentence. An ascription of non-determinacy is correct or incorrect depending exclusively on the model relative to which the ascription is effected.
28. For ‘truth equivalence’ Hintikka uses the term ‘weak equivalence’ and for ‘logical equivalence’ the term ‘strong equivalence’ (cf. Hintikka 1996: 150). He characterizes strong equivalence as the preservation of truth and falsity. Thus if ψ and χ are strongly equivalent, nothing prevents ψ from being non-determined in a model, as long as χ also is. (On other occasions, e.g. in Hintikka 1991: 20, Hintikka defines ‘strong equivalence’ differently, by the requirement that either ψ and χ are both true or both false; this precludes the possibility that one or both of two strongly equivalent sentences would be non-determined.) The term ‘truth equivalence’ used by Dechesne (2005: 32) is more descriptive. The term ‘falsity equivalence’ also stems from Dechesne. She follows Hintikka in terming ‘strong equivalence’ what is here for simplicity referred to as ‘logical equivalence’.
29. Cf. Hintikka (1996: 147), Hodges (1997a: 546), Sandu (1993, 1994).
30. In Hintikka (1996: 149) this logic is termed truth-functionally extended IF first-order logic – in contradistinction to ‘extended IF first-order logic,’ which in Hintikka (1991: 47, 1996: 149) and Hintikka & Sandu (1997) is defined as containing, in addition to IFL formulas, only formulas ¬φ, where φ is an IFL formula (or sentence). The considerations that motivate the introduction of ¬ in the first place, actually call for the more general syntax (witness Hintikka 1996: 149, 195–196), which is why it is natural to define extended IF first-order logic as it is done here. For extended IF first-order logic, see also Hintikka (1991: 49; 1997; 2004). For the crucial restriction that ¬ may not occur in the scope of a quantifier, see Hintikka (1991: 49; 1996: 148). For counterexamples to this restriction see, however, Hintikka (1996: 148; 2002c) and especially Hintikka (2006b) in which the so-called fully extended IF first-order logic is considered. In fully extended IF first-order logic any occurrences of ¬ are allowed which are subject to the following syntactic condition: if (Qx/W) is a quantifier in the syntactic scope of an occurrence of ¬, then all quantifiers listed in W are likewise in the syntactic scope of that occurrence of ¬.
31. Cf. Hintikka (1991: 49; 1996: 147–149; 2002), Hintikka & Sandu (1997: 375), Sandu (1993, 1994).
32. Cf. Hintikka (1991, 1995, 1996, 1997), Hintikka & Sandu (1996), Sandu (1993, 1996, 1998). Analogous properties of (what on substantial criteria is) slash logic are discussed in Sandu (2007) and Mann et al. (2011); recall Hodges's distinction between independence friendly logic and slash logic (see the beginning of Sect. 3). Properties of another related logic, Väänänen's dependence logic, are in a mathematically detailed fashion covered in Väänänen (2007).
33. For (existential) second-order logic, see Enderton's entry on Second-order and Higher-order Logic in this encyclopedia. See also van Benthem and Doets (2001).
34. For the Axiom of Choice (AC), see Jech's entry on Set Theory in this encyclopedia.
35. In Hodges (2006: 527; 2001), it is pointed out that a strengthened version of this theorem can be proven if a weakened notion of strategy is applied (cf. also Hintikka 2006a: 536). Related observations are made in Forster (2006). Namely, the standard notion of strategy employed in GTS is that of deterministic strategy: a set of single-valued functions yielding for any given tuple of arguments a unique move. A nondeterministic strategy of player 2 consists of a set of instructions, each instruction yielding a set of moves for any tuple of earlier moves by player 1. A nondeterministic strategy of player 2 is winning if it guarantees a win for player 2, regardless of which move, among those given by the strategy, player 2 makes in each case when it is her turn to move.
Theorem (without AC). (Hodges 2001) Let τ be any vocabulary, M any τ structure, g any variable assignment and φ any FO[τ] formula. Then M, g ⊨ φ holds in the standard sense iff there is a nondeterministic winning strategy for player 2 in game G(φ, M, g).
For finite partially ordered quantifiers and AC, see Krynicki & Mostowski (1995; Sect. 2).
36.
The
intertranslatability of the two logics is discussed in Hintikka (1991,
1996, 1997), Hintikka & Sandu (1997), Sandu (1998).
37. A Hamiltonian path on a graph is a path visiting every node exactly once. For Fagin's theorem and references to NP-complete problems, see e.g. Ebbinghaus & Flum (1999), Grädel et al. (2007), Papadimitriou (1994). For partially ordered quantifiers, partially ordered connectives, and NP-complete problems, see Blass & Gurevich (1986), Hella & Sandu (1995).
38. If φ and ψ are IFL formulas, let us write (φ → ψ) for (~φ ∨ ψ), and (φ ↔ ψ) for ((φ → ψ) ∧ (ψ → φ)); cf. footnote 17.
39. For a discussion, see Hintikka (1991, 1995, 1996), Hintikka & Sandu (1997), Sandu (1993). Paying due attention to Hodges's warning against confusing slash logic and IF logic, one may reconstruct proofs for various properties of IFL on the basis of Väänänen's results concerning his dependence logic (Väänänen 2007). The results pertaining to (what in substance is) slash logic discussed in (Sandu 2007) and in (Mann et al. 2011) can likewise be compared to the analogous results concerning IFL.
40. A complete disproof procedure is a procedure for recursively enumerating all inconsistent sentences. The term ‘complete proof procedure for inconsistency’ might involve a smaller risk of being misunderstood (cf., e.g., Quine 1970: 90). In any event, disproving must be understood as ‘establishing inconsistent,’ not as ‘establishing not provable’ (or ‘establishing not valid’).
41. For the fact that ESO is not closed under negation, cf. e.g. Hinman (1978: 82).
42. For a proof phrased in terms of FPO, see Barwise (1979: 56, 73–74).
43. Actually, it is non-determined in all domains with at least two elements.
44. Fragments of ESO are subject to lively interest in finite model theory and complexity theory, see e.g. Ebbinghaus & Flum (1999), Grädel et al. (2007), Papadimitriou (1994). For related work on partially ordered quantifiers and connectives, see Blass & Gurevich (1986), Hella & Sandu (1995), Hella, Sevenster & Tulenheimo (2008). For the P = NP problem, see e.g. Fortnow (2009).
45. That there is a sound and complete proof procedure for FO was first proven by Kurt Gödel (1930). There are different variants of axiomatizability. Let L be a logic, A a set of sentences of L, and P a proof procedure for L. Then A is an axiomatization of L relative to P, if the sentences of L provable in P from the sentences of A are precisely the valid sentences of L. The logic L is finitely axiomatizable (resp. recursively axiomatizable, resp. axiomatizable) relative to P, if it has a finite (resp. recursive, resp. recursively enumerable) axiomatization A relative to P.
46. See Hintikka (1991, 1995, 1996, 2000).
47. The theorem was proven by Boris Trakhtenbrot (1950). For Trakhtenbrot's theorem, see Ebbinghaus, Flum & Thomas (1984). Andrzej Mostowski (1957) proved, without recourse to Trakhtenbrot's theorem, that extending FO with a quantifier capable of saying that a formula of one free variable is satisfied by finitely many elements only, results in a logic that is not axiomatizable.
48. The fact that FPO fails to have a sound and complete proof procedure can be seen by reference to Trakhtenbrot's theorem. In 1958 Ehrenfeucht showed that φinf can be expressed in FPO; see Henkin (1961). From this he concluded – making use of Mostowski's result mentioned in footnote 47 – that the Boolean closure of FPO (i.e., its closure under the operations ¬, ∧, and ∨) is not axiomatizable. From Mostowski's result the non-axiomatizability of FPO itself does not follow (since the finiteness of an extension is not expressible in FPO).
49. See e.g. Hintikka (2006a: 65), Sandu & Hintikka (2001: 49). For compositionality and GTS, see Hintikka & Kulas (1983), Hintikka & Sandu (1997). For a discussion on different senses of compositionality and IFL, see Hintikka (1996), Sandu & Hintikka (2001). Cf. also Szabó's entry on Compositionality in this encyclopedia.
50. See e.g. Hintikka & Kulas (1983), Hintikka (1988, 1996, 2000, 2006a).
51. See e.g. Hintikka & Kulas (1983), Hintikka (1988, 1996, 2000).
52. See e.g. Hintikka & Kulas (1983), Hintikka (1988, 1996, 2000), Hintikka & Sandu (1997).
53. See e.g. Hintikka & Kulas (1983), Hintikka (1988, 1995, 1996).
54. Barwise (1979) suggested that a compositional semantics must satisfy the condition that the relation ‘M ⊨ φ’ be an inductive verifiability relation in the sense of Barwise & Moschovakis (1978). He proved that FPO does not admit of a compositional semantics subject to this condition. Hodges (1997a) finds the condition suggested by Barwise unmotivated. It rather begs the question: in order for a relation to be an inductive verifiability relation, the relevant inductive clauses must be first-order. That they cannot be first-order in connection with FPO is hardly surprising; cf. Hodges (2007: 118).
Hintikka had on many occasions stated that there is no realistic hope of formulating compositional truth-conditions for IFL sentences (Hintikka 1991, 1995, 1996; see also Hintikka & Sandu 1997). Hodges (1997a,b) wanted to prove Hintikka's statement wrong. The syntax Hodges opted for is that of slash logic (cf. Sect. 3 and Subsect. 6.1). Since Hodges considers variants of slash logic, his results are not, strictly speaking, about IFL. However, it is clear that the framework of Hodges (1997b) can be adapted to the syntax of IFL proper.
55. It was pointed out already in Hintikka & Kulas (1983: 20) that at least in some cases compositionality can be restored by resorting to higher-order entities, specifically to functions embodying strategies of player 2. In the same connection it was noted that such higher-order entities are much less realistic philosophically and psycholinguistically than the original individuals. See also Zadrozny (1995), Janssen (1997), Hodges (1998); cf. Westerståhl (1998), Sandu & Hintikka (2001).
56. Note that (N, TRUEN) is an expansion of N to the vocabulary τ ∪ {TRUE}.
57. For details about truth-definitions of FO, see Hodges's entry on Tarski's Truth Definitions in this encyclopedia; further, see e.g. Kaye (1991), Sandu (1998), Väänänen (2007).
58. The proof of this result is sketched in Hintikka (1991, 1996), and later in more detail in Sandu (1998). See also Hintikka (1998, 2001), Hyttinen & Sandu (2000), Sandu & Hyttinen (2001), Väänänen (2007). For a technically analogous result, see Hodges's comments about self-applied truth-predicates for Σn formulas in Azriel Levy's set-theoretical hierarchy (Hodges's entry on Tarski's Truth Definitions in this encyclopedia); see also de Rouilhan and Bozon's (2006: 700) comments about John Myhill's and Craig Smorynski's similar results.
59. If one attempts to construct Liar's paradox for IFL, the assertion that the Liar sentence is true will itself be non-determined (Hintikka 1991: 44–51, 1996: 142; cf. Väänänen 2007: 108–109).
60. See also Hintikka (1996: 106–108; 2001: 23–24; 2006a: 65–66).
61. See Hintikka (1996: 123–125; 2001), Hintikka & Sandu (1997).
62. Enderton (1970) proved that the logic L* obtained from FO by closing it under arbitrary Henkin quantifiers, as well as under the operations ¬, ∧, and ∨, can be translated into the so-called Δ12 fragment of second-order logic. (For this fragment, see, e.g., Hinman 1978.) Marcin Mostowski (1991) showed that in fact L* does not suffice to cover Δ12; cf. Krynicki & Mostowski (1995: 217). Now, (1) EIFL has the same expressive power as the Boolean closure of ESO (i.e., its closure under ¬, ∧, and ∨), (2) the Boolean closure of ESO has the same expressive power as the Boolean closure of FPO, and (3) the Boolean closure of FPO is a fragment of L*. Therefore we may conclude that EIFL is strictly weaker than the Δ12 fragment of second-order logic.
63. The standard interpretation in the sense of Henkin (1950) construes second-order quantifiers as follows. If R is an n-ary relation symbol, f is an n-ary function symbol, and M is a domain, then under the standard interpretation of second-order logic, the second-order quantifiers (∃R) and (∀R) range over all (extensionally possible) subsets of Mn, and the second-order quantifiers (∃f) and (∀f) range over all (extensionally possible) functions from Mn to M.
64. Similar requirements need be expressed concerning eventual second-order quantifiers (∃f).
65. See Hintikka (1955; 1991: 47–48; 1995: 12–13; 2006a: 476–477), and especially Hintikka (1996: 194–195). For details about the reduction of the validity problem of full second-order logic to that of ESO, see e.g. Leivant (1994).
66. For an algebraic study of slash logic, see Mann (2007).
67. For the relation of Jónsson and Tarski's Theorem 3.14 to modal logic, cf. Copeland's entry on Arthur Prior in this encyclopedia.
68. For these observations relating the propositional part of EIFL, the modal logic S4, and intuitionistic propositional logic, see Hintikka (2004b; 2006a: 471).
69. See Hintikka (1991; 1995; 1996: 129,190,198,201,205; 2000: 133; 2002a: 409; 2006a: 472). It may be of interest to note that Quine (1970: 90) affirms without hesitation that FPO formulas are not ontologically committed to higher-order entities (even if their expressive power goes beyond FO). On the same basis Quine would, no doubt, have accepted that IFL is only committed to first-order entities. (Quine's reasons for not considering FPO as a logic were related to its non-axiomatizability; cf. Subsect. 4.3.) For ontological commitments of FPO formulas, see also Patton (1991). For the status of FPO as a first-order logic, cf. Hintikka & Kulas (1983: 50).
70. See Westerståhl's entry on Generalized Quantifiers in this encyclopedia.
71. For, in a play of the semantic game for the formula Q≥κz P(z) and the model M, player 2 would choose a function f : κ → M, whereafter player 1 would choose distinct ordinals α, β < κ. Player 2 would win iff f(α) ≠ f(β) and the individual f(α) satisfies the predicate P.
72. Cf. Subsect. 4.6. For details, see e.g. Leivant (1994).
73. Both sets are Π2 complete; for Π2 completeness, see e.g. Väänänen (2007; Ch. 7).
74. Cf. Feferman (2006: 461,463), Hintikka (1996: 129,193,198).
75. Cf., e.g., Hintikka (1991; 1995; 2002: 407; 2006a: 40–41).
76. Together with witnesses for disjunction symbols, likewise depending in general on the values chosen for the preceding universal quantifiers.
77. For the argument, see Hintikka (1996; 1998; 2004a; 2006a: 74).
78. For limited formal truth definitions for set theory, see Hodges's entry on Tarski's Truth Definitions in this encyclopedia.
79. These individuals are ‘sets’ only in the sense that they belong to a domain of a model of an axiomatic set theory; they are not sets in the sense in which the entities over which second-order quantifiers range are sets (namely sets of individuals of the domain considered).
80. See e.g. Hintikka (1996: 172–177; 1998: 319–323, 326–32; 2006a: 74). For the continuum hypothesis, and Gödel's and Cohen's independence results, see Jech's entry on Set Theory in this encyclopedia.
81. See Hintikka (1991: 47–48; 1996: 192–193); see also Väänänen (2007: 139–141).
82. See Hintikka (1986; 1993; 1996: 208–209). The axiom of completeness appears in the second edition (1903) of Hilbert (1898). Saying that a model M is maximal requires, at least on the face of it, quantification over individuals (or sets) outside the domain of M.
83. Actually, Hintikka sees it as a conceptual confusion to speak of ‘axiomatizations’ in connection with logic as well as mathematical theories. In the former case, when possible, an axiomatization is simply a recursive enumeration of validities of the logic considered. By contrast, one can view an axiomatization of a mathematical theory as a way of compressing all the truths (not logical truths or validities) about the subject matter of the theory into a finite or recursively enumerable set of axioms (Hintikka 1996: 1–4).
84. Quantifiers occurring in conjoint constituents, quantifiers occurring in different nested of phrases, and relative clauses with several antecedents; see Hintikka (1973a, 1976a, 1979).
85. For a discussion, see e.g. Peters & Westerståhl (2006: 66–72) and the literature referred to there.
86. This is because the set of valid FPO sentences is not recursively enumerable. As Hintikka himself recognizes, to produce a rigorous argument, it would be necessary to show for an arbitrary FPO sentence Qφ, not only that there is an English sentence that is naturally represented using the prefix Q, but also that the grammatical constructions used allow an English counterpart of φ: whether the formula Qφ can be translated to FO crucially depends on the matrix φ.
87. The example is from Hintikka (1982); in this paper Hintikka does not use the slash sign. By reference to Hintikka's theory of the semantics of questions (Hintikka 1976b), Carlson and ter Meulen (1979) called attention to wh-questions formed out of suitable sentences with a branching quantifier reading, and argued that the desideratum of such a question will involve informational independence of the usual quantifiers from the intensional know-construction.
88. In epistemic logic, the knowledge operator Ka is construed as a universal modal operator ranging over scenarios compatible with the knowledge of the agent a considered. For further information, see Hendricks & Symons's entry on Epistemic Logic in this encyclopedia.
89. The impossibility to express the condition KI (∀x)(∃y/KI) admires(x, y) in FPO is pointed out in both Carlson & ter Meulen (1979) and Hintikka (1982). Here the existential quantifier depends on the universal quantifier but not on the knowledge operator, while the knowledge operator must precede the universal quantifier in order for the formula to imply the presupposed de dicto sentence ‘I know that everybody admires someone.’ According to the formula (∀x) KI (∃y/KI) admires(x, y), the agent's knowledge would pertain to all actual individuals and it would merely imply that the agent knows of all actually existing individuals that each of them admires someone. If it is compatible with the agent's knowledge that there are further individuals beside those which happen to exist actually, this would not guarantee the truth of the de dicto sentence.
90. Cf. Hintikka (1982, 1987, 1990), Engdahl (1986). For the uses of Skolem functions and related ideas in linguistics – notably the so-called choice functions – see e.g. Reinhart (1997), von Heusinger (2004), Steedman (2012). In logical terms, a choice function is a function taking a formula of one free variable as its argument and returning as its value an individual that satisfies this formula – if at least one such individual exists.
91. In Hintikka & Sandu (1989: 575–576) it is said that informational independence is a relation between applications of game rules, but also that it is a relation that a move prompted by an expression in a semantic game bears to a number of earlier moves prompted by further expressions (cf. also Hintikka & Sandu 1997: 367). The latter construal complies with the way informational independence is understood in game theory, while the former led to some confused examples in Hintikka and Sandu's paper (examples about neg-raising, pp. 577–580, see also Hintikka 1990, Sandu 1993).
92. The belief operator Ba is a universal modal operator, just like the knowledge operator Ka; its range is the set of scenarios compatible with all that the agent a believes in the scenario relative to which the sentence is evaluated (cf. footnote 88).
93. Cf. Hintikka & Sandu (1989: 584–585, 587–589), Hintikka (1990). Some exceptions were noted in Hintikka (1973a), cf. footnote 84. However, even when informational independence can be syntactically indicated, the indicators are different from case to case.