Source-linked AI summary
Dependence and Independence
Erich Grädel, Jouko Väänänen
TL;DR
The paper asks how independence among variables can be represented and related to dependence logic. It introduces generalized independence atoms and builds independence logic around them. The resulting system has complete basic independence axioms, includes dependence logic, and matches dependence logic on sentences, while its full team characterization remains open.
Problem
The paper seeks a logic that formalizes independence alongside dependence and asks whether independence logic has a corresponding expressive-power characterization.
Method
The paper adds generalized independence atoms to first-order logic and studies their axioms, semantics, expressive power, and interaction with dependence logic.
Results
Independence axioms are complete, dependence logic is included, and independence and dependence logic are equivalent in expressive power for sentences.
Takeaways & Limitations
Independence atoms provide a natural framework that captures dependence as a special case and supports compositional semantics for partially ordered quantifiers.
Takeaways & Limitations
A similar full expressive-power characterization for independence logic is not known, and its formulas need not be closed downward under subteams.
Abstract
from arXiv · showhide
We introduce an atomic formula intuitively saying that given variables are independent from given other variables if a third set of variables is kept constant. We contrast this with dependence logic. We show that our independence atom gives rise to a natural logic capable of formalizing basic intuitions about independence and dependence.
Abstract
The paper develops independence atoms and a logic extending dependence logic, gives complete axioms for basic independence, and characterizes important expressive-power relationships. It also identifies limits in team behavior and in the known characterization of independence logic.
- Functional dependence is introduced as deterministic determination among variables, building on database-theoretic properties such as Armstrong’s axioms.
- Independence is generalized to mean that variables are independent of other variables when a third group is held fixed.
- Constancy and symmetry are established as basic properties: a constant variable is independent of every variable, and independence is symmetric.
- The independence axioms are complete: every finite-team consequence of independence atoms is derivable from the stated rules, and conversely.
- Independence logic is formed by adding independence atoms to first-order logic, thereby including dependence logic because dependence is a special case of generalized independence.
- The paper supplies an existential-second-order upper bound for independence logic and notes that the matching characterization question remains open.
- For sentences, independence logic and dependence logic have equivalent expressive power, while independence formulas need not be closed downward under subteams.
- Independence atoms also support compositional semantics for partially ordered quantifiers, although a weaker independence condition does not validate a corresponding dependence implication.