Dependence and Independence
Erich Grädel, Jouko Väänänen
Abstract:
We introduce an atomic formula \vec{y} ⊥_\vec{x} \vec{z} intuitively
saying that the variables \vec{y} are independent from the variables
\vec{z} if the variables \vec{x} are kept constant. We contrast this
with dependence logic D based on the atomic formula =(\vec{x},
\vec{y}), actually a special case of \vec{y} ⊥_\vec{x} \vec{z},
saying that the variables y are totally determined by the variables
\vec{x}. We show that \vec{y} ⊥_\vec{x} \vec{z} gives rise to a
natural logic capable of formalizing basic intuitions about
independence and dependence. We show that \vec{y} ⊥_\vec{x} \vec{z}
can be used to give partially ordered quantifiers and IF-logic a
compositional interpretation without some of the shortcomings related
to so called signaling that interpretations using =(\vec{x}, \vec{y})
have.