Philosophy.su.se

Editorial Introduction
Suppose a table of data concerning three variables x, y and z is given, forexample: If we look at the values of x and y we may observe that when x is thesame also y is the same. The converse is not true: y can be the same ona row without x being the same. In the light of this data we say that yfunctionally depends on x but not conversely. If the concept “functionallydepends” is imported into first order logic, dependence logic [5] emerges. Thisspecial issue contains nine research papers investigating different aspects ofdependence logic and its predecessor, independence friendly logic [2].
to first order logic with the meaning that y functionally depends on x. Wethink of the rows of the table (I) as assignments that assign values to vari-ables. Thus we have a background model and the variables are meant torange over the elements of the model. Such tables of assignments are calledteams in [5]. A team X satisfies (II) if ∀s, s′ ∈ X(s(x) = s′(x) → s(y) = s′(y)). The concept of a team satisfying a formula extends to all of dependence logicin a canonical way. The traditional concept of a single assignment s satisfyinga first order formula corresponds to the singleton team {s} satisfying theformula in the above sense, so dependence logic is a conservative extensionof first order logic.
Special issue: Dependence and Independence in Logic
Edited by Juha Kontinen, Jouko V¨
anen, Dag Westerst˚
Partially ordered quantification [1] can be expressed compositionally in ϕ ↔ ∀x∃y∀u∃v(=(u, v) ∧ ϕ). Independence friendly logic ([2]) extends first order logic by quantifiers of the form ∃y/x with the intuitive meaning “there is a y independently ofx”. The semantics was originally game theoretic but can be also given interms of teams ([3]) as follows: A team X satisfies ∃y/xϕ if there is a teamY , obtained from X by adding a column for y (or modifying the y-columnif it already exists) such that Y satisfies ϕ, the teams X and Y agree aboutvariables other than y, and∧ ∀s, s′ ∈ Y ([ s(z) = s′(z)] → s(y) = s′(y)), where z runs through relevant variables other than x. A simpler version,dependence friendly logic, obtains if instead of quantifiers ∃y/x we add quan-tifiers ∃y\x with the meaning: A team X satisfies ∃y\xϕ if the above holdswith (III) replaced by ∀s, s′ ∈ Y (s(x) = s′(x) → s(y) = s′(y)). ∃y\xϕ ↔ ∃y(=(x, y) ∧ ϕ). As is the case with partially ordered quantification, the expressive power of sentences of dependence logic and (in)dependence friendly logic is exactlyΣ1 i.e. existential second order logic. Since the semantics of dependence logic is defined via teams, we cannot reduce the semantics of formulas to thesemantics of sentences obtained from the formulas by substituting constantsymbols for free variables. So there is the new question, what the expressivepower of formulas of dependence logic is. It turns out that if we use anew predicate symbol to refer to the team, the expressive power of formulasof dependence logic is exactly existential second order logic with the newpredicate for the team occurring only negatively [4].
Dependence can be added also to other logics than first order logic. In propositional logic we can consider tables like and observe that p1 functionally depends on p0, but p2 does not. We canadd the atoms (and more general similar atoms) to propositional logic and define truth withrespect to a set X of valuations by saying that X satisfies =(p0, p1) if ∀v, v′ ∈ X(v(p0) = v′(p0) → v(p1) = v′(p1)). There is a canonical way to extend this to modal logic, leading to a modaldependence logic. Other systems where dependence has led to interestingdevelopments, recorded in the papers of this issue, are logic without identity,quantifier-free logic, intuitionistic logic, epistemic logic, probabilistic logic,and formal semantics.
The above discussion makes perfect sense in finite models leading to the observation that dependence logic gives a new language for N P , non-deterministic polynomial time. This observation has led to complexity the-oretic investigations, which are largely still under way.
The “independence” in independence friendly logic is hidden in the clause “other than x” in (III). So this is independence by means of functionaldependence on other. Recently a stronger form of independence was intro-duced. This new form is closely related to the concept of independenceof random variables, but also to concepts of outcome-independence andparameter-independence in quantum physics. We include in this issue twocontributions on this topic.
The goal of the study of dependence and independence in logic is to establish a basic theory of dependence and independence phenomena under-lying seemingly unrelated subjects such as game theory, random variables,database theory, scientific experiments, and probably many others. Themonograph [5] stimulated an avalanche of new results which have demon-strated remarkable convergence in this area. The concepts of (in)dependencein the different fields of science have surprising similarity and a common logicis starting to emerge. This special issue will give an overview of the state ofthe art of this new field.
References
[1] Henkin, L., ‘Some remarks on infinitely long formulas’, in Infinitistic Methods (Proc. Sympos. Foundations of Math., Warsaw, 1959), Pergamon, Oxford, 1961, pp. 167–183.
[2] Hintikka, Jaakko, and Gabriel Sandu, ‘Informational independence as a seman- tical phenomenon’, in Logic, methodology and philosophy of science, VIII (Moscow, 1987), vol. 126 of Stud. Logic Found. Math., North-Holland, Amsterdam, 1989, pp.
[3] Hodges, Wilfrid, ‘Compositional semantics for a language of imperfect information’, Log. J. IGPL 5(4):539–563, 1997 (electronic).
anen, ‘On definability in dependence logic’, J. Log. Lang. Inf. 18(3):317–332, 2009.
anen, Jouko, Dependence logic, vol. 70 of London Mathematical Society Student Texts, Cambridge University Press, Cambridge, 2007. A new approach to independence Juha KontinenDepartment of Mathematics and StatisticsUniversity of [email protected] Department of Mathematics and StatisticsUniversity of HelsinkiFinlandandInstitute for Language, Logic and ComputationUniversity of AmsterdamThe [email protected] Department of PhilosophyUniversity of [email protected]

Source: http://www.philosophy.su.se/polopoly_fs/1.165901.1391710696!/menu/standard/file/2013%20StudiaLogicaDepIndepIntro.pdf