We develop a semantics for independence logic with respect to what we will call general models. We then introduce a simpler entailment semantics for the same logic, and we reduce the validity problem in the former to the validity problem in the latter. Then we build a proof system for independence logic and prove its soundness and completeness with respect to entailment semantics.

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)

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)

Jaakko Hintikka, in a series of talks in Brazil in 2008, defended that IF logic and paraconsistent logic are, in a sense, very similar. Having sketched the proposal of a new paraconsistent system, he maintains that several achievements of IF logic could be reproducible in paraconsistent logic. One of the major difficulties, left as a challenge, would be to formulate some truth conditions for this new paraconsistent first-order language in order to make IF logic and paraconsistent logic more inter-related. My (...) proposal is that this would demand an innovative game-theoretical semantic approach to paraconsistentism, but also that the syntax of the paraconsistent “Logics of Formal Inconsistency” can model the internal logic of Socratic elenchi. I aim to discuss these, and other points posed by Hintikka, as challenges and opportunities for paraconsistentism, paraconsistent logics and IF logics, as well as to raise some criticisms on Hintikka’s view about paraconsistency. (shrink)

This volume presents mathematical game theory as an interface between logic and philosophy.

We take a fresh look at the logics of informational dependence and independence of Hintikka and Sandu and Väänänen, and their compositional semantics due to Hodges. We show how Hodges’ semantics can be seen as a special case of a general construction, which provides a context for a useful completeness theorem with respect to a wider class of models. We shed some new light on each aspect of the logic. We show that the natural propositional logic carried by the semantics (...) is the logic of Bunched Implications due to Pym and O’Hearn, which combines intuitionistic and multiplicative connectives. This introduces several new connectives not previously considered in logics of informational dependence, but which we show play a very natural rôle, most notably intuitionistic implication. As regards the quantifiers, we show that their interpretation in the Hodges semantics is forced, in that they are the image under the general construction of the usual Tarski semantics; this implies that they are adjoints to substitution, and hence uniquely determined. As for the dependence predicate, we show that this is definable from a simpler predicate, of constancy or dependence on nothing. This makes essential use of the intuitionistic implication. The Armstrong axioms for functional dependence are then recovered as a standard set of axioms for intuitionistic implication. We also prove a full abstraction result in the style of Hodges, in which the intuitionistic implication plays a very natural rôle. (shrink)

The present paper provides novel results on the model theory of Independence friendly modal logic. We concentrate on its particularly well-behaved fragment that was introduced in Tulenheimo and Sevenster (Advances in Modal Logic, 2006). Here we refer to this fragment as ‘Simple IF modal logic’ (IFML s ). A model-theoretic criterion is presented which serves to tell when a formula of IFML s is not equivalent to any formula of basic modal logic (ML). We generalize the notion of bisimulation familiar (...) from ML; the resulting asymmetric simulation concept is used to prove that IFML s is not closed under complementation. In fact we obtain a much stronger result: the only IFML s formulas admitting their classical negation to be expressed in IFML s itself are those whose truth-condition is in fact expressible in ML. (shrink)

The hybrid logic and the independence friendly modal logic IFML are compared for their expressive powers. We introduce a logic IFML c having a non-standard syntax and a compositional semantics; in terms of this logic a syntactic fragment of IFML is singled out, denoted IFML c . (In the Appendix it is shown that the game-theoretic semantics of IFML c coincides with the compositional semantics of IFML c .) The hybrid logic is proven to be strictly more expressive than IFML (...) c . By contrast, and the full IFML are shown to be incomparable for their expressive powers. Building on earlier research (Tulenheimo and Sevenster 2006), a PSPACE -decidable fragment of the undecidable logic is disclosed. This fragment is not translatable into the hybrid logic and has not been studied previously in connection with hybrid logics. In the Appendix IFML c is shown to lack the property of ‘quasi-positionality’ but proven to enjoy the weaker property of ‘ bounded quasi-positionality’. The latter fact provides from the IFML internal perspective an account of what makes the compositional semantics of IFML c possible. (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 show that for any pair $\phi$ and $\psi$ of contradictory formulas of dependence logic there is a formula $\theta$ of the same logic such that $\phi\equiv\theta$ and $\psi\equiv\neg\theta$. This generalizes a result of Burgess.

In the literature on logics of imperfect information it is often stated, incorrectly, that the Game-Theoretical Semantics of Independence-Friendly quantifiers captures the idea that the players of semantical games are forced to make some moves without knowledge of the moves of other players. We survey here the alternative semantics for IF logic that have been suggested in order to enforce this “epistemic reading” of sentences. We introduce some new proposals, and a more general logical language which distinguishes between “independence from (...) actions” and “independence from strategies”. New semantics for IF logic can be obtained by choosing embeddings of the set of IF sentences into this larger language. We compare all the semantics proposed and their purported game-theoretical justifications, and disprove a few claims that have been made in the literature. (shrink)

Independence-friendly logic is a conservative extension of first-order logic that has the same expressive power as existential second-order logic. We attempt to algebraize IF logic in the same spirit as cylindric algebra. We define independence-friendly cylindric set algebras and investigate to what extent they satisfy the axioms of cylindric algebra. We ask whether the equational theory of IF algebras is finitely axiomatizable, and prove two partial results. First, every IF algebra over a structure is an expansion of a Kleene algebra. (...) Moreover, the class of such Kleene algebras generates the variety of all Kleene algebras. Second, every one-dimensional IF algebra over a structure is an expansion of a monadic Kleene algebra. However, the class of such monadic Kleene algebras does not generate the variety of all monadic Kleene algebras. (shrink)

We introduce several senses of the principle ofcompositionality. We illustrate the difference between them with thehelp of some recent results obtained by Cameron and Hodges oncompositional semantics for languages of imperfect information.

We study the expressive power of open formulas of dependence logic introduced in Väänänen [Dependence logic (Vol. 70 of London Mathematical Society Student Texts), 2007]. In particular, we answer a question raised by Wilfrid Hodges: how to characterize the sets of teams definable by means of identity only in dependence logic, or equivalently in independence friendly logic.

A semantics may be compositional and yet partial, in the sense that not all well-formed expressions are assigned meanings by it. Examples come from both natural and formal languages. When can such a semantics be extended to a total one, preserving compositionality? This sort of extension problem was formulated by Hodges, and solved there in a particular case, in which the total extension respects a precise version of the fregean dictum that the meaning of an expression is the contribution it (...) makes to the meanings of complex phrases of which it is a part. Hodges' result presupposes the so-called Husserl property, which says roughly that synonymous expressions must have the same category. Here I solve a different version of the compositional extension problem, corresponding to another type of linguistic situation in which we only have a partial semantics, and without assuming the Husserl property. I also briefly compare Hodges' framework for grammars in terms of partial algebras with more familiar ones, going back to Montague, which use many-sorted algebras instead. (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.