Independence Friendly Logic, introduced by Hintikka, is a logic in which a quantifier can be marked for being independent of other quantifiers. Dependence logic, introduced by Väänänen, is a logic with the complementary approach: for a quantifier it can be indicated on which quantifiers it depends. These logics are claimed to be useful for many phenomena, for instance natural language semantics. In this contribution we will compare these two logics by investigating their application in a compositional analysis of the de (...) dicto - de re ambiguity in natural language. It will be argued that Independence Friendly logic is suitable, whereas Dependence Logic is not. (shrink)

The properties of the ${\forall^{1}}$ quantifier defined by Kontinen and Väänänen in [13] are studied, and its definition is generalized to that of a family of quantifiers ${\forall^{n}}$ . Furthermore, some epistemic operators δ n for Dependence Logic are also introduced, and the relationship between these ${\forall^{n}}$ quantifiers and the δ n operators are investigated.The Game Theoretic Semantics for Dependence Logic and the corresponding Ehrenfeucht- Fraissé game are then adapted to these new connectives.Finally, it is proved that the ${\forall^{1}}$ quantifier (...) is not uniformly definable in Dependence Logic, thus answering a question posed by Kontinen and Väänänen in the above mentioned paper. (shrink)

A dichotomy result of Sevenster (2014) [29] completely classified the quantifier prefixes of regular Independence-Friendly (IF) logic according to the patterns of quantifier dependence they contain. On one hand, prefixes that contain “Henkin” or “signalling” patterns were shown to characterize fragments of IF logic that capture NP-complete problems; all the remaining prefixes were shown instead to be essentially first-order. In the present paper we develop the machinery which is needed in order to extend the results of Sevenster to non-prenex, regular (...) IF sentences. This involves shifting attention from quantifier prefixes to a (rather general) class of syntactical tree prefixes. We partially classify the fragments of regular IF logic that are thus determined by syntactical trees; in particular, a) we identify four classes of tree prefixes that are neither signaling nor Henkin, and yet express NP-complete problems and other second-order concepts; and b) we give more general criteria for checking the first-orderness of an IF sentence. (shrink)

We analyse the two definitions of generalized quantifiers for logics of dependence and independence that have been proposed by F. Engström, comparing them with a more general, higher order definition of team quantifier. We show that Engström’s definitions can be identified, by means of appropriate lifts, with special classes of team quantifiers. We point out that the new team quantifiers express a quantitative and a qualitative component, while Engström’s quantifiers only range over the latter. We further argue that Engström’s definitions (...) are just embeddings of the first-order generalized quantifiers into team semantics, and fail to capture an adequate notion of team-theoretical generalized quantifier, save for the special cases in which the quantifiers are applied to flat formulas. We also raise several doubts concerning the meaningfulness of the monotone/nonmonotone distinction in this context. In the appendix we develop some proof theory for Engström’s quantifiers. (shrink)

In this paper, we introduce a new approach to independent quantifiers, as originally introduced in Informational independence as a semantic phenomenon by Hintikka and Sandu [9] under the header of independence-friendly languages. Unlike other approaches, which rely heavily on compositional methods, we shall analyze independent quantifiers via equilibriums in strategic games. In this approach, coined equilibrium semantics, the value of an IF sentence on a particular structure is determined by the expected utility of the existential player in any of the (...) game’s equilibriums. This approach was suggested in Henkin quantifiers and complete problems by Blass and Gurevich [2] but has not been taken up before. We prove that each rational number can be realized by an IF sentence. We also give a lower and upper bound on the expressive power of IF logic under equilibrium semantics. (shrink)

Typical applications of Hintikka’s game-theoretical semantics give rise to semantic attributes—truth, falsity—expressible in the $\Sigma^{1}_{1}$-fragment of second-order logic. Actually a much more general notion of semantic attribute is motivated by strategic considerations. When identifying such a generalization, the notion of classical negation plays a crucial role. We study two languages, $L_{1}$ and $L_{2}$, in both of which two negation signs are available: $\rightharpoondown $ and $\sim$. The latter is the usual GTS negation which transposes the players’ roles, while the former (...) will be interpreted via the notion of mode. Logic $L_{1}$ extends independence-friendly logic; $\rightharpoondown $ behaves as classical negation in $L_{1}$. Logic $L_{2}$ extends $L_{1}$, and it is shown to capture the $\Sigma^{2}_{1}$-fragment of third-order logic. Consequently the classical negation remains inexpressible in $L_{2}$. (shrink)

In this article we investigate the family of independence-friendly (IF) logics in the equality-free setting, concentrating on questions related to expressive power. Various natural equality-free fragments of logics in this family translate into existential second-order logic with prenex quantification of function symbols only and with the first-order parts of formulae equality-free. We study this fragment of existential second-order logic. Our principal technical result is that over finite models with a vocabulary consisting of unary relation symbols only, this fragment of second-order (...) logic is weaker in expressive power than first-order logic (with equality). Results about the fragment could turn out useful for example in the study of independence-friendly modal logics. In addition to proving results of a technical nature, we address issues related to a perspective from which IF logic is regarded as a specification framework for games, and also discuss the general significance of understanding fragments of second-order logic in investigations related to non-classical logics. (shrink)

The paper proposes a novel solution to the problem of scope posed by natural language indefinites that captures both the difference in scopal freedom between indefinites and bona fide quantifiers and the syntactic sensitivity that the scope of indefinites does nevertheless exhibit. Following the main insight of choice functional approaches, we connect the special scopal properties of indefinites to the fact that their semantics can be stated in terms of choosing a suitable witness. This is in contrast to bona fide (...) quantifiers, the semantics of which crucially involves relations between sets of entities. We provide empirical arguments that this insight should not be captured by adding choice/Skolem functions to classical first-order logic, but in a semantics that follows Independence-Friendly Logic, in which scopal relations involving existentials are part of the recursive definition of truth and satisfaction. These scopal relations are resolved automatically as part of the interpretation of existentials. Additional support for this approach is provided by dependent indefinites, a cross-linguistically common class of special indefinites that can be straightforwardly analyzed in our semantic framework. (shrink)

Team semantics is a highly general framework for logics which describe dependencies and independencies among variables. Typically, the dependencies considered in this context are properties of sets of configurations or data records. We show how team semantics can be further generalized to support languages for the discussion of interventionist counterfactuals and causal dependencies, such as those that arise in manipulationist theories of causation. We show that the “causal teams” we introduce in the present paper can be used for modelling some (...) classical counterfactual scenarios which are not captured by the usual causal models. We then analyse the basic properties of our counterfactual languages and discuss extensively the differences with respect to the Lewisian tradition. (shrink)

We analyze the expressive resources of \ logic that do not stem from Henkin quantification. When one restricts attention to regular \ sentences, this amounts to the study of the fragment of \ logic which is individuated by the game-theoretical property of action recall. We prove that the fragment of prenex AR sentences can express all existential second-order properties. We then show that the same can be achieved in the non-prenex fragment of AR, by using “signalling by disjunction” instead of (...) Henkin or signalling patterns. We also study irregular IF logic and analyze its correspondence to regular IF logic. By using new methods, we prove that the game-theoretical property of knowledge memory is a first-order syntactical constraint also for irregular sentences, and we identify another new first-order fragment. Finally we discover that irregular prefixes behave quite differently in finite and infinite models. In particular, we show that, over infinite structures, every irregular prefix is equivalent to a regular one; and we present an irregular prefix which is second order on finite models but collapses to a first-order prefix on infinite models. (shrink)

We analyze the behaviour of declarations of independence between existential quantifiers in quantifier prefixes of Independence-Friendly (IF) sentences; we give a syntactical criterion to decide whether a sentence beginning with such prefix exists, such that its truth values may be affected by removal of the declaration of independence. We extend the result also to equilibrium semantics values for undetermined IF sentences.

We study the expressive power of independence-friendly quantifier prefixes composed of universal$\left$, existential$\left$, and majority quantifiers$\left$. We provide four quantifier prefixes that can express NP hard properties and show that all quantifier prefixes capable of expressing NP-hard properties embed at least one of these four quantifier prefixes. As for the quantifier prefixes that do not embed any of these four quantifier prefixes, we show that they are equivalent to a first-order quantifier prefix composed of$\forall x$,$\exists x$, and Mx. In unison, (...) our results imply a dichotomy result: every independence-friendly quantifier prefix is either decidable in LOGSPACE or NP hard. (shrink)

Independence‐Friendly logic introduced by Hintikka and Sandu studies patterns of dependence and independence of quantifiers which exceed those found in ordinary first‐order logic. The present survey focuses on the game‐theoretical interpretation of IF‐logic, including connections to solution concepts in classical game theory, but we shall also present its compositional interpretation together with its connections to notions of dependence and dependence between terms.