We continue the work on the relations between independence logic and the model-theoretic analysis of independence, generalizing the results of [15] and [16] to the framework of abstract independence relations for an arbitrary AEC. We give a model-theoretic interpretation of the independence atom and characterize under which conditions we can prove a completeness result with respect to the deductive system that axiomatizes independence in team semantics and statistics.

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.

In this paper, we axiomatize the negatable consequences in dependence and independence logic by extending the systems of natural deduction of the logics given in [22] and [11]. We prove a characterization theorem for negatable formulas in independence logic and negatable sentences in dependence logic, and identify an interesting class of formulas that are negatable in independence logic. Dependence and independence atoms, first-order formulas belong to this class. We also demonstrate our extended (...) system of independence logic by giving explicit derivations for Armstrong's Axioms and the Geiger-Paz-Pearl axioms of dependence and independence atoms. (shrink)

Dependence is a common phenomenon, wherever one looks: ecological systems, astronomy, human history, stock markets - but what is the logic of dependence? This book is the first to carry out a systematic logical study of this important concept, giving on the way a precise mathematical treatment of Hintikka’s independence friendly logic. Dependence logic adds the concept of dependence to first order logic. Here the syntax and semantics of dependence logic are studied, dependence (...) class='Hi'>logic is given an alternative game theoretic semantics, and results about its complexity are proven. This is a graduate textbook suitable for a special course in logic in mathematics, philosophy and computer science departments, and contains over 200 exercises, many of which have a full solution at the end of the book. It is also accessible to readers, with a basic knowledge of logic, interested in new phenomena in logic. (shrink)

Accounts of logical independence which coincide when applied in the case of classical logic diverge elsewhere, raising the question of what a satisfactory all-purpose account of logical independence might look like. ‘All-purpose’ here means: working satisfactorily as applied across different logics, taken as consequence relations. Principal candidate characterizations of independence relative to a consequence relation are that there the consequence relation concerned is determined by only by classes of valuations providing for all possible truth-value combinations for (...) the formulas whose independence is at issue, and that the consequence relation ‘says’ nothing special about how those formulas are related that it does not say about arbitrary formulas. Each of these proposals returns counterintuitive verdicts in certain cases—the truth-value inspired approach classifying certain cases one would like to describe as involving failures of independence as being cases of independence, and the de Jongh approach counting some intuitively independent pairs of formulas as not being independent after all. In final section, a modification of the latter approach is tentatively sketched to correct for these misclassifications. The attention is on conceptual clarification throughout, rather than the provision of technical results. Proofs, as well as further elaborations, are lodged in the ‘longer notes’ in a final Appendix. (shrink)

This paper investigates formal logics for reasoning about determinacy and independence. Propositional Dependence Logic D and Propositional Independence Logic I are recently developed logical systems, based on team semantics, that provide a framework for such reasoning tasks. We introduce two new logics L_D and L_I, based on Kripke semantics, and propose them as alternatives for D and I, respectively. We analyse the relative expressive powers of these four logics and discuss the way these systems relate to (...) natural language. We argue that L_D and L_I naturally resolve a range of interpretational problems that arise in D and I.We also obtain sound and complete axiomatizations for L_D and L_I . (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)

A systematic introduction suitable for readers who have little familiarity with logic. Provides numerous examples and complete proofs.

In this paper it is argued that Hintikka's game theoreticalsemantics for Independence Friendly logic does not formalize theintuitions about independent choices; it rather is aformalization of imperfect information. Furthermore it is shownthat the logic has several remarkable properties (e.g.,renaming of bound variables is not allowed). An alternativesemantics is proposed which formalizes intuitions aboutindependence.

The projection latticesP(ℳ1),P(ℳ2) of two von Neumann subalgebras ℳ1, ℳ2 of the von Neumann algebra ℳ are defined to be logically independent if A ∧ B≠0 for any 0≠AεP(ℳ1), 0≠BP(ℳ2). After motivating this notion in independence, it is shown thatP(ℳ1),P(ℳ2) are logically independent if ℳ1 is a subfactor in a finite factor ℳ andP(ℳ1),P(ℳ2 commute. Also, logical independence is related to the statistical independence conditions called C*-independence W*-independence, and strict locality. Logical independence ofP(ℳ1,P(ℳ2 turns (...) out to be equivalent to the C*-independence of (ℳ1,ℳ2) for mutually commuting ℳ1,ℳ2 and it is shown that if (ℳ1,ℳ2) is a pair of (not necessarily commuting) von Neumann subalgebras, thenP(ℳ1,P(ℳ2 are logically independent in the following cases: ℳ is a finite-dimensional full-matrix algebra and ℳ1,ℳ2 are C*-independent; (ℳ1,ℳ2) is a W*-independent pair; ℳ1,ℳ2 have the property of strict locality. (shrink)

Directed acyclic graphs (DAGs) constitute a qualitative representation for conditional independence (CI) properties of a probability distribution. It is known that every CI statement implied by the topology of a DAG is witnessed over it under a graph-theoretic criterion of d-separation. Alternatively, all such implied CI statements are derivable from the local independencies encoded by a DAG using the so-called semi-graphoid axioms. We consider Labeled Directed Acyclic Graphs (LDAGs) modeling graphically scenarios exhibiting context-specific independence (CSI). Such CSI statements (...) are modeled by labeled edges, where labels encode contexts in which the edge vanishes. We study the problem of identifying all independence statements implied by the structure and the labels of an LDAG. We show that this problem is coNP-hard for LDAGs and formulate a sound extension of the semi-graphoid axioms for the derivation of such implied independencies. Finally we connect our study to certain qualitative versions of independence ubiquitous in database theory and teams semantics. (shrink)

The main goal of this work is to present the proof-theoretical and model-theoretical approaches to probabilistic logics which allow reasoning about independence and probabilistic support. We extend the existing formalisms [14] to obtain several variants of probabilistic logics by adding the operators for independence and confirmation to the syntax. We axiomatize these logics, provide corresponding semantics, prove that the axiomatizations are sound and strongly complete, and discuss decidability issues.

We give a negative solution to the problem, posed by A. Chagrov and M. Zakharyaschev, of whether every quasi-normal propositional modal logic can be axiomatized by an independent set of axioms, with the inference rules of Substitution and Modus Ponens.

A distinction between the epistemic practices in mathematics and in the empirical sciences is rehearsed to motivate the epistemic role puzzle. This is distinguished both from Benacerraf's 1973 epistemic puzzle and from sceptical arguments against our knowledge of an external world. The stipulationist position is described, a position which can address this puzzle. Methods of avoiding the stipulationist position by using pure logic to provide knowledge of mathematical abstracta are discussed and criticized.

The working assumption of this paper is that noncommuting variables are irreducibly interdependent. The logic of such dependence relations is the author's independence-friendly (IF) logic, extended by adding to it sentence-initial contradictory negation ¬ over and above the dual (strong) negation ∼. Then in a Hilbert space ∼ turns out to express orthocomplementation. This can be extended to any logical space, which makes it possible to define the dimension of a logical space. The received Birkhoff and von (...) Neumann "quantum logic" can be interpreted by taking their "disjunction" to be ¬(∼A & ∼ B). Their logic can thus be mapped into a Boolean structure to which an additional operator ∼ has been added. (shrink)

This paper considers non-standard analysis and a recently introduced computational methodology based on the notion of ①. The latter approach was developed with the intention to allow one to work with infinities and infinitesimals numerically in a unique computational framework and in all the situations requiring these notions. Non-standard analysis is a classical purely symbolic technique that works with ultrafilters, external and internal sets, standard and non-standard numbers, etc. In its turn, the ①-based methodology does not use any of these (...) notions and proposes a more physical treatment of mathematical objects separating the objects from tools used to study them. It both offers a possibility to create new numerical methods using infinities and infinitesimals in floating-point computations and allows one to study certain mathematical objects dealing with infinity more accurately than it is done traditionally. In these notes, we explain that even though both methodologies deal with infinities and infinitesimals, they are independent and represent two different philosophies of Mathematics that are not in a conflict. It is proved that texts :539–555, 2017; Gutman and Kutateladze in Sib Math J 49:835–841, 2008; Kutateladze in J Appl Ind Math 5:73–75, 2011) asserting that the ①-based methodology is a part of non-standard analysis unfortunately contain several logical fallacies. Their attempt to show that the ①-based methodology can be formalized within non-standard analysis is similar to trying to show that constructivism can be reduced to the traditional Mathematics. (shrink)

In order to be able to express all possible patterns of dependence and independence between variables, we have to replace the traditional first-order logic by independence-friendly (IF) logic. Our natural concept of truth for a quantificational sentence S says that all the Skolem functions for S exist. This conception of truth for a sufficiently rich IF first-order language can be expressed in the same language. In a first-order axiomatic set theory, one can apparently express this same (...) concept in set-theoretical terms, since the existence of functions can be expressed there. Because of Tarski's theorem, this is impossible. Hence there must exist set-theoretical statements, even provable ones, which are said to be true in first-order models of axiomatic set theory but whose Skolem functions do not all exist. Hence there are provable sentences in axiomatic set theory that are false in accordance with our ordinary conceptions of set-theoretical truth. Such counter-intuitive propositions have been known to exist, but they have been blamed on the peculiarities of very large sets. It is argued here that this explanation is not correct and that there are intuitively false theorems not involving very large sets. Hence the provability or unprovability of a set-theoretical statement, e.g. of the continuum hypothesis (CH) in axiomatic set theory is not necessarily relevant to the truth of CH. (shrink)

Nous introduisons une extension aux points fixes de la logique IF (faite pour l’indépendance) de Hintikka et Sandu. Nous donnons des résultats sur sa complexité et son pouvoir expressif. Nous la relions aux jeux de parité à information imparfaite, et nous montrons une application à la définition d’un mu-calcul modal fait pour l’indépendance.

In this paper we relax the assumption that the logical constants of ordinary first-order logic be linearly ordered. As a consequence, we shall have formulas involving not only partially ordered quantifiers, but also partially ordered connectives. The resulting language, called the language of informational independence will be given an interpretation in terms of games of imperfect information. The II-logic will be seen to have some interesting properties: It is very natural to define in this logic two (...) negations, weak negation as failure to verify a sentence, and strong negation as the existence of a falsifying strategy: One can express in this logic complete problems of finite structures, like the non-connectedness and 3-colorability of finite graphs, the satisfiability problem for Boolean circuits built up from NAND-gates, etc. (shrink)

Nous introduisons une extension aux points fixes de la logique IF (faite pour l’indépendance) de Hintikka et Sandu. Nous donnons des résultats sur sa complexité et son pouvoir expressif. Nous la relions aux jeux de parité à information imparfaite, et nous montrons une application à la définition d’un mu-calcul modal fait pour l’indépendance.

A Kripke-style semantics developed by de Jongh and Veltman is used to investigate relations between several extensions of interpretability logic, IL.

Short-circuit evaluation denotes the semantics of propositional connectives in which the second argument is evaluated only if the first argument does not suffice to determine the value of the expression. Free short-circuit logic is the equational logic in which compound statements are evaluated from left to right, while atomic evaluations are not memorised throughout the evaluation, i.e. evaluations of distinct occurrences of an atom in a compound statement may yield different truth values. We provide a simple semantics for (...) free short-circuit logic and an independent axiomatisation. Finally, we discuss evaluation strategies, some other SCLs, and side effects. (shrink)

We show that the join of two classical [respectively, regular, normal] modal logics employing distinct modal operators is a conservative extension of each of them.

Let us assume that you are entrusted by UNESCO with an important task. You are asked to devise a universal logical language, a Begriffsschrift in Frege's sense, which is to serve the purposes of science, business and everyday life. What requirements should such a “conceptual notation” satisfy? There are undoubtedly many relevant desiderata, but here I am focusing on one unmistakable one. In order to be a viable lingua universalis, your language must in any case be capable of representing any (...) possible configuration of dependence and independence between different variables. For if such a configuration is possible in principle, there is no guarantee that it might not one day show up among the natural, human or social phenomena we have to study.But how are dependencies and independencies between variables expressed in our familiar logical notation? Every logician worth his or her truth-table knows the answer. Dependencies between two variables are expressed by dependencies between the quantifiers to which they are bound. For instance, inthe variable y depends on x, while inz depends on x but not on y, while u depends on both x and y.But how is the dependence of a quantifier on another one expressed in familiar logical languages? Obviously by occurring in its scope, indicated by the pair of parentheses following it. But the nesting of scopes is a transitive and antisymmetrical relation which allows branching only in one direction. Hence other kinds of structures of dependence and independence between variables are not representable in the received logical notation. Such previously inexpressible structures form the subject matter of what has been referred to as independence-friendly logic. (shrink)

Radical skepticism about the external world is founded on two assumptions: one is that the mind and the external world are logically independent; the other is that all our evidence for the nature of that world consists of facts about our minds. In this paper, I explore the option of denying the epistemic, rather than the logical assumption. I argue that one can do so only by embracing externalism about justification, or, after all, by rejecting the logical independence assumption. (...) Since (I argue) externalism is not a solution to the problem of skepticism, this means that skepticism is false only if the mind and the world are not logically independent. (shrink)

We formulate several statements in Algebraic Logic that turn out to be independent of ZFC. We relate such statements to Martin's axiom, omitting types for variants of first order logic and topological properties of Baire spaces.

The notion of absolute independence, considered in this paper has a clear algebraic meaning and is a strengthening of the usual notion of logical independence. We prove that any consistent and countable set in classical prepositional logic has an absolutely independent axiornatization.

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.

This paper continues the work begun by Crispin Wright of identifying, articulating, and explaining the relations between various realist-relevant axes that emerge when it is conceded that any predicate capable of satisfying a small range of platitudes is syntactically and semantically adequate to count as a truth predicate for a discourse. I argue that the fact that a given discourse satisfies the three realist-relevant axes that remain if evidence-transcendent truth and reference to evidence-transcendent facts are ruled out by Dummettian meaning-theoretic (...) considerations is not sufficient for what I have elsewhere called “modest metaphysical realism.” I conclude that mind-independence marks yet another realist-relevant axis and explore the relationships between the proposed mind-independence axis and the realist-relevant axes identified by Wright. (shrink)

We fix a family of actions A which represents the set of possible choices of the players in a game. A sequence (a1, ..., an) of actions represents the consecutive choices of the players, ai ∈ A.

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.

Throughout the twentieth century, the automation of formal logics in computers has created unprecedented potential for practical applications of logic—most prominently the mechanical verification of mathematics and software. But the high cost of these applications makes them infeasible but for a few flagship projects, and even those are negligible compared to the ever-rising needs for verification. One of the biggest challenges in the future of logic will be to enable applications at much larger scales and simultaneously at much (...) lower costs. This will require a far more efficient allocation of resources. Wherever possible, theoretical and practical results must be formulated generically so that they can be instantiated to arbitrary logics; this will allow reusing results in the face of today’s multitude of application-oriented and therefore diverging logical systems. Moreover, the software engineering problems concerning automation support must be decoupled from the theoretical problems of designing logics and calculi; this will allow researchers outside or at the fringe of logic to contribute scalable logic-independent tools. Anticipating these needs, the author has developed the Mmt framework. It offers a modern approach towards defining, analyzing, implementing, and applying logics that focuses on modular design and logic-independent results. This paper summarizes the ideas behind and the results about Mmt. It focuses on showing how Mmt. provides a theoretical and practical framework for the future of logic. (shrink)