RWTH Aachen University<EMAIL_ADDRESS>RWTH Aachen
University<EMAIL_ADDRESS>R. Albert, E. Grädel <ccs2012>
<concept> <concept_id>10003752.10003790</concept_id> <concept_desc>Theory of
computation Logic</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>
[500]Theory of computation Logic

# Unifying Hidden-Variable Problems from Quantum Mechanics by Logics of
Dependence and Independence

Rafael Albert  Erich Grädel

###### Abstract

We study hidden-variable models from quantum mechanics and their abstractions
in purely probabilistic and relational frameworks by means of logics of
dependence and independence, which are based on team semantics. We show that
common desirable properties of hidden-variable models can be defined in an
elegant and concise way in dependence and independence logic. The relationship
between different properties and their simultaneous realisability can thus be
formulated and proven on a purely logical level, as problems of entailment and
satisfiability of logical formulae. Connections between probabilistic and
relational entailment in dependence and independence logic allow us to
simplify proofs. In many cases, we can establish results on both probabilistic
and relational hidden-variable models by a single proof, because one case
implies the other, depending on purely syntactic criteria. We also discuss the
‘no-go’ theorems by Bell and Kochen-Specker and provide a purely logical
variant of the latter, introducing _non-contextual choice_ as a team-
semantical property.

###### keywords:

Hidden-variables, logics of dependence and independence, relational versus
probabilistic team semantics, Kochen-Specker Theorem, Bell’s Theorem

##  1 Introduction

Hidden-variable models have been proposed since the 1920s as an alternative to
the standard interpretation, sometimes called the Copenhagen interpretation,
of quantum mechanics with the goal to explain and remove counterintuitive
aspects of quantum mechanics. In particular, quantum systems behave, according
to the standard interpretation, probabilistically rather than
deterministically, non-local interactions between agents or particles that are
widely separated in space are possible through entanglement, and there is an
unavoidable dependence between an observer of a quantum mechanical system and
the observed properties. Due to such features, Einstein, Podolsky, and Rosen
[19] considered a quantum mechanical state an ‘incomplete’ description of
physical reality. The basic idea of hidden-variable models is to ‘complete’
quantum mechanics by adding unobservable, ‘hidden’, variables to the
description of a system, to obtain models that are consistent with the
predictions of quantum mechanics, but which do not exhibit counterintuitive
behavior.

The question to what extent hidden-variable models can indeed explain quantum
mechanical effects in a satisfactory way, has been studied for a long time by
many researchers. John von Neumann [35], who has coined the term ‘hidden-
variable models’, claimed to have established the impossibility of such an
endeavour:

> It should be noted that we need not go any further into the mechanism of the
> ‘hidden parameters,’ since we now know that the established results of
> quantum mechanics can never be re-derived with their help.

However, this claim was not generally accepted. Some of the most outspoken
criticism came from Grete Hermann, Davin Mermin, and John Bell [8], who even
went as far as calling von Neumann’s proof “not merely false, but foolish”
(see [14]). Further, David Bohm and Lois de Broglie developed non-standard,
deterministic interpretations of quantum mechanics using hidden-variables
referred to as Bohmian mechanics or de Broglie-Bohm theory [11, 12, 17].

Many different variants of determinism, locality, and independence properties
of hidden-variable models have been studied. The attempts to build hidden-
variable models that jointly realise these can be seen as attempts to avoid
the counter-intuitive consequences of the standard formalism of quantum
mechanics. However, the famous ‘no-go’ theorems of quantum mechanics, such as
the ones by Bell [7] and Kochen-Specker [31], show that one cannot really
escape such consequences, and that there are severe limitations for the
hidden-variable programme in general. The dominant attitude today is to accept
the quantum mechanical formalism at face value and to make use of its counter-
intuitive features such as entanglement and contextuality in modern
applications like quantum computing and quantum cryptology.

A survey of the most important properties of determinism, locality, and
independence in hidden-variable models has been given in an influential paper
by Brandenburger and Yanofsky [13], in an abstract and purely probabilistic
framework that does not make explicit reference to quantum mechanics. It makes
precise the relationship between the different properties and discusses the
question which combinations of them can be realised simultaneously in a
probabilistic hidden-variable model. Despite the general limitations of the
hidden-variable programme, there are interesting combinations of properties
that are jointly realisable, and the work of Brandenburger and Yanovsky [13]
gives a detailed account of what is possible in a probabilistic setting. A
further fundamental step for the understanding of hidden-variable phenomena
has been Abramsky’s proposal of a purely relational (rather than
probabilistic) framework [1] for hidden-variable models, with discrete
analogues of the probabilistic dependence and independence properties studied
in [13]. He showed that the main structure of the theory is preserved under
this simplification. Abramsky’s work opens the possibility to study hidden-
variable questions on a much more general level leaving aside quantum
mechanical details. But on the other side, Abramsky also discusses the issue
of quantum realisations of empirical models (which has also been studied on a
more general level in [4]). An important point is that among the emipirical
models that cannot be extended to hidden-variable models with specific
locality and independence properties there are models that are not just
abstract mathematical constructions but do indeed arise from quantum
mechanical experiments, such as Bell test.

We propose here a study of hidden-variable properties by means of modern
logics of dependence and independence. These logics are based on team
semantics, introduced by Hodges [29]. While a classical logical formula (from
first-order logic, for instance) is evaluated for a single assignment, mapping
its free variables to values in some mathematical structure, team semantics
evaluates a formula for a _set_ of such assignments, called a team. Further,
while previous formalisms for studying dependence and independence (such as
Henkin quantifiers or independence-friendly logic) had modeled dependencies by
special quantifiers, the modern dependence and independence logics treat them,
following a proposal by Väänänen [34], as _atomic properties of teams_. While
these logics are syntactically very simple, extending the atomic team
properties by the standard first-order operators $\lor$, $\land$, $\exists$
and $\forall$, they are semantically rather powerful. Indeed, team semantics
admits the manipulation of second-order objects by first-order syntax and, in
fact, independence logic [24] has the full expressive power of existential
second-order and can thus define all team properties in the complexity class
NP [21].

There are several reasons why logics of dependence and independence are
natural tools for reasoning about hidden-variable models. First of all, the
desirable properties of hidden-variable models, in particular the ones studied
in [1] and [13], are obviously properties of dependence and independence. We
shall see that in the logics we are using, their definition is extremely
simple and transparent, mostly just conjunctions of dependence or independence
atoms. Second, the models studied in hidden-variable theories, both empirical
models and hidden-variable models, and both in the relational and the
probabilistic setting, can readily be understood and presented as teams. This
means that formulae in dependence and independence logic can be directly
evaluated on the models we are interested in. Moreover, it turns out that
operators on the team side are naturally compatible with the structure of
hidden-variable models – for instance, the connection between probabilistic
and relational models corresponds directly to the relationship between
relational and probabilistic team semantics.

Although our study does not establish new results on quantum mechanical
hidden-variable models as such, we think that our spelling out of the
connections between logics with team semantics and hidden-variable models in
detail is useful and provides the following contributions:

  * •

We show that the properties of empirical and hidden-variable models can be
defined in a very concise and elegant way in logics of dependence and
independence. This also helps to make implicit assumptions in the definition
of such properties explicit.

  * •

Our team-semantical framework enables a full unification of the probabilistic
and relational theory. In fact, for all the properties that we study, the same
formula can be used for both settings, evaluated over relational teams in the
first case, and over probabilistic teams in the second case. This provides a
very elegant perspective on the connection between relational and
probabilistic hidden-variables, complementing earlier work on the connection
between the two such as [4], which used a more algebraic approach based on
distributions over semirings.

  * •

Connections between different properties of hidden-variable models can be
formulated in terms of _logical entailment_ between the team-semantical
formulae defining these properties and can thus been proved on a purely
logical level. This may also be beneficial for formalising such proofs in an
appropriate proof system or theorem prover.

  * •

Similarly, the existence of an empirically equivalent hidden-variable model
that satisfies some combination of desirable properties corresponds to the
_satisfiability_ of a suitable formula by an extension of the team which
represents a given empirical model.

  * •

On a purely logical level, we establish connections between probabilistic
entailment and relational entailment of formulae from dependence and
independence logic, which we believe to be of independent interest. Applying
these connections to the entailment and satisfiability problems related to
properties of hidden-variable models, we often need only one proof to
establish both the probabilistic and the relational case because, depending on
purely syntactic criteria, one case implies the other. This provides more
general reasons why the relational variant of hidden-variable models is so
closely related to their probabilistic counterpart, and further motivates
Abramsky’s translation as a special case of a more general framework.

  * •

We further show that the famous ‘no-go’ theorems by Bell and Kochen-Specker
can be formulated in a natural way in the team semantical framework. In
particular we provide logical variants of the Kochen-Specker Theorem,
highlighting the aspect of contextuality in a different way compared to the
classical formulation, and discuss the related notion of _non-contextual
choice_.

By different methods, not directly related to team semantics, but based on
sheaf theory, a full unification of the relational and probabilistic theory
has already been obtained in [4]. This work further gives a unified treatment
of non-locality and contextuality in a very general setting. It remains to be
seen whether meaningful connections between this approach and logics with team
semantics can be established.

Acknowledgments.  Researchers studying logics of dependence and independence
have been aware for some time of the possibility to use these logics for
reasoning about hidden-variable models in quantum mechanics, and this idea was
informally discussed in this research community at several occasions. However,
when we started our work, no systematic study in this direction had been
conducted yet. Only at a point where this paper was almost finished, it was
brought to our attention that Joni Puljujärvi and Jouko Väänänen at the
University of Helsinki have simultaneously pursued a similar line of research,
and we had interesting discussions with them on this topic. Meanwhile they
have written a joint paper with Samson Abramsky on this work [6]. We also wish
to thank an anonymous referee for valuable comments and additional references
that helped us to improve this paper.

##  2 Hidden-Variable Models and Teams

We introduce the setup required to understand both relational and
probabilistic hidden-variable models. We also define teams and explain how
hidden-variable models can be cast as teams. Finally, we show that the
structure of hidden-variable models is compatible with operators on the team
side and thereby demonstrate that teams are very well suited to express
hidden-variable phenomena.

###  2.1 Relational Models and Teams

A purely relational setting to speak about hidden-variable models was
introduced by Abramsky [1].

######  Definition 2.1.

Let $M_{1},\dots,M_{n}$ and $O_{1},\dots,O_{n}$ be finite sets. We set
$M=\prod_{i=1}^{n}M_{i}$ and $O=\prod_{i=1}^{n}O_{i}$. An arbitrary relation
$e\subseteq M\times O$ is called an empirical model over $(M,O)$. In this
setting, $n$ is called the arity of the system, $M$ the measurement set, and
$O$ set of outcomes.

We usually interpret such a system as having $n$ components which may but need
not be separated in space. We interpret $M_{i}$ as the set of measurements
that can be performed in component $i$ and $O_{i}$ as potential outcomes in
that component. The measurement-outcome pairs $(\bar{m},\bar{o})\in e$ are
interpreted to be _possible_ in the model. To make sure that the underlying
sets $M$ and $O$ can be inferred from the empirical model, we tacitly assume
that every value $m_{i}\in M_{i}$ and $o_{j}\in O_{j}$ appears in at least one
tuple of the relation $e$; in database terms this means that $\bigcup_{i\leq
n}M_{i}\cup\bigcup_{i\leq n}O_{i}$ coincides with the active domain of $e$.

######  Example 2.2.

Let us consider a system with 2 components, called Alice and Bob. Let
$M_{1}=\\{a_{1},a_{2}\\}$ and $M_{2}=\\{b_{1}\\}$. Thus, Alice has a choice
between two measurements while Bob can perform only one. In this example, all
measurements reveal a single bit of information, i.e. we let
$O_{1}=O_{2}=\\{+,-\\}$. An example of an empirical model over $(M,O)$ is

$e$ | $(+,+)$ | $(+,-)$ | $(-,+)$ | $(-,-)$
---|---|---|---|---
$(a_{1},b_{1})$ | 1 | 0 | 0 | 1
$(a_{2},b_{1})$ | 0 | 1 | 1 | 0

In this example, the outcome of Alice’s measurement is always identical to
Bob’s if Alice chooses $a_{1}$ and always opposite to Bob’s if she chooses
$a_{2}$.

######  Definition 2.3.

Let $M$ and $O$ be as in Definition 2.1, and let $\Lambda$ be a finite set. A
_hidden-variable model_ over $(M,O,\Lambda)$ is a relation $h\subseteq M\times
O\times\Lambda$. The elements $\lambda\in\Lambda$ are called hidden-variables.

The interpretation of hidden-variable models is similar to that of empirical
models. The hidden-variables are assumed to be unobservable parameters of the
system that may influence outcomes. A triplet $(\bar{m},\bar{o},\lambda)\in h$
means that the measurement-outcome pair $(\bar{m},\bar{o})$ is possible in the
system when the hidden-variable takes the value $\lambda$. Again, we tacitly
assume that every $\lambda\in\Lambda$ appears in at least one tuple of $h$.
The original motivation behind the introduction of hidden-variables was that
seemingly unintuitive phenomena on the empirical side in quantum mechanics
might be explained by ignorance about the hidden-variables and not by an
intrinsically non-classical system. However, as we shall see later, certain
non-classical phenomena remain even if hidden-variables are introduced.

Hidden-variable models induce empirical models by projecting back onto the
empirically observable parameters $M\times O$, giving rise to a notion of
empirical equivalence, i.e. a notion of which systems we can distinguish by
experiment and which not.

######  Definition 2.4.

Let $h$ be a hidden-variable model over $(M,O,\Lambda)$. We call

$e:=\\{(\bar{m},\bar{o})\in M\times
O:(\exists\lambda\in\Lambda)(\bar{m},\bar{o},\lambda)\in h\\}$

its _induced empirical model_ , and say that $h$ and $e$ _empirically
equivalent_.

Now that we have defined relational models, we present them as teams.

######  Definition 2.5.

A team is a set $X$ of assignments $s:D\rightarrow A$ with a common finite
domain $D=\mathrm{dom}(X)$ of variables and values in a set $A$. For a tuple
of variables $\bar{x}=(x_{1},\dots,x_{m})\in X$, we write
$X(\bar{x}):=\\{(s(x_{1}),\dots,s(x_{m}))\colon s\in X\\}\subseteq A^{m}$ for
the set of values of $\bar{x}$ in $X$. Thinking of an arbitrary but fixed
enumeration of the finite domain of a team $X$ as
$\mathrm{dom}(X)=\\{x_{1},\dots,x_{k}\\}$, we often identify $X$ with its
_relational encoding_ $X(\bar{x})=\\{s(\bar{x})\colon s\in X\\}\subseteq
A^{k}$ and assignments $s\in X$ with corresponding tuples.

With that in mind, the interpretation of hidden-variable models as teams is
very natural. To make sure that the underlying sets of measurements
$M=\prod_{i=1}^{n}M_{i}$, outcomes $O=\prod_{i=1}^{n}O_{i}$, and hidden-
variables $\Lambda$ can be inferred from the team we again assume that every
$m_{i}\in M_{i},o_{j}\in O_{j}$ and $\lambda\in\Lambda$ appears in at least
one assignment of the team. Then we have a one-to-one correspondence between
hidden-variable models and teams (and similarly for empirical models).

######  Definition 2.6.

A team $X$ over variables
$\operatorname{Var}_{n}^{h}:=\\{m_{1},\dots,m_{n},\allowbreak
o_{1},\dots,{o_{n}},\lambda\\}$ induces a hidden-variable model, denoted
$h_{X}$, with $M_{i}:=X(m_{i})$, $O_{i}:=X(o_{i})$, and $\Lambda:=X(\lambda)$
such that

$(\bar{a},\bar{b},c)\in h_{X}\quad:\Longleftrightarrow\quad(\exists s\in
X)s(\bar{m})=\bar{a},s(\bar{o})=\bar{b},\text{ and }s(\lambda)=c.$

We denote by $e_{X}$ the empirical model that is induced by $h_{X}$.

Analogously, empirical models $e\subseteq M\times O$ are represented by teams
over $\operatorname{Var}_{n}^{e}:=\\{m_{1},\dots,m_{n},o_{1},\dots,o_{n}\\}$.

###  2.2 Probabilistic Models and Probabilistic Teams

Systems arising from quantum mechanics are probabilistic in nature. Thus, the
literature primarily investigates probabilistic hidden-variable models. A
comprehensive discussion of such models can be found in [13]. However, the
relevant definitions of probabilistic models and their properties are
presented here in a somewhat different way, on the basis of our team
semantical framework.

######  Definition 2.7.

Let $(M,O)$ be as in Definition 2.1. A probability distribution
$e_{\mathbb{P}}\colon M\times O\to[0,1]$ is called a probabilistic empirical
model over $(M,O)$. Analogously, a probabilistic hidden-variable models is a
probability distributions $h_{\mathbb{P}}$ over $M\times O\times\Lambda$. We
make use of standard notation for marginalization and conditionals when
speaking about probabilistic models. For example, for a probabilistic hidden-
variable model $h_{\mathbb{P}}\colon M\times O\times\Lambda\to[0,1]$, we call
the marginalization $e_{\mathbb{P}}\colon M\times O\to[0,1]$ with
$e_{\mathbb{P}}(\bar{m},\bar{o}):=h_{\mathbb{P}}(\bar{m},\bar{o})=\sum_{\lambda\in\Lambda}h_{\mathbb{P}}(\bar{m},\bar{o},\lambda)$
its induced empirical model. In this case, $h_{\mathbb{P}}$ and
$e_{\mathbb{P}}$ are called empirically equivalent.

The intuition behind empirical equivalence is that empirically equivalent
models cannot be distinguished by experiment as they agree on the observable
parameters of the system. For this purpose, the conditional distributions
$h_{\mathbb{P}}(\bar{o}\mid\bar{m})$ are actually slightly more relevant than
the joint probabilities $h_{\mathbb{P}}(\bar{o},\bar{m})$ as they define the
outcome distributions for fixed measurements; $h_{\mathbb{P}}(\bar{m})$ has no
meaningful interpretation without going into discussions about the
experimenters’ free will. Thus, the literature regards a slightly different
notion of empirical equivalence. [13] defines an empirical model
$e_{\mathbb{P}}$ and a hidden-variable model $h_{\mathbb{P}}$ to be
empirically equivalent if they agree on all suitable conditional
probabilities, i.e. if
$h_{\mathbb{P}}(\bar{o}\mid\bar{m})=e_{\mathbb{P}}(\bar{o}\mid\bar{m})$ always
holds. We think that the definition we have chosen, i.e. requiring the
slightly stronger
$h_{\mathbb{P}}(\bar{o},\bar{m})=e_{\mathbb{P}}(\bar{o},\bar{m})$, is more
natural and elegant for our purposes since empirical equivalence reduces to
marginal equivalence in the standard probability theoretic sense. For all
relevant results it makes no difference which choice is made. The probability
distribution $h_{\mathbb{P}}(\bar{m},\bar{o},\lambda)$ can be decomposed into
$h_{\mathbb{P}}(\bar{m}),h_{\mathbb{P}}(\lambda\mid\bar{m})$ and
$h_{\mathbb{P}}(\bar{o}\mid\bar{m},\lambda)$. For all properties of interest
only the latter two components matter. Thus, we could adjust
$h_{\mathbb{P}}(\bar{m})$ to enforce agreement with the empirical model
without harming properties of $h_{\mathbb{P}}$. In particular, all existence
and non-existence results which we will show later in this work are
independent of this technical detail.

The connection between probabilistic and relational models is one of
possibilistic collapse, i.e. we consider the set of tuples with probability
greater than zero. This corresponds to our understanding of relational models
where we interpret $(\bar{m},\bar{o})\in e$ as statement “it is _possible_ in
$e$ to obtain the measurement-outcome pair $(\bar{m},\bar{o})$”.

######  Definition 2.8.

A probabilistic empirical model $e_{\mathbb{P}}$ over $(M,O)$ induces the
relational model $e:=\\{(\bar{m},\bar{o})\in M\times
O:e_{\mathbb{P}}(\bar{m},\bar{o})>0\\}$. Analogously, probabilistic hidden-
variable models induce relational hidden variable models.

Again, we cast probabilistic models as teams, using the notion of
probabilistic teams, which have been considered for instance in [18, 25, 26].

######  Definition 2.9.

A _probabilistic team_ is a pair $\mathbb{X}=(X,\mathbb{P}_{\mathbb{X}})$,
where $X$ is a relational team and $\mathbb{P}_{\mathbb{X}}\colon X\to(0,1]$
is a probability distribution over $X$. $X$ is referred to as the underlying
team of $\mathbb{X}$. We denote $\mathbb{P}$ instead of
$\mathbb{P}_{\mathbb{X}}$ if the context is clear.

As in the relational case, there is a one-to-one correspondence between
probabilistic hidden-variable models and probabilistic teams.

######  Definition 2.10.

A probabilistic team $\mathbb{X}=(X,\mathbb{P})$ over variables
$\operatorname{Var}_{n}^{h}=\\{m_{1},\dots,\allowbreak m_{n},\allowbreak
o_{1},\allowbreak\dots,{o_{n}},\lambda\\}$ induces a hidden-variable model
$h_{\mathbb{X}}$ with $M_{i}:=X(m_{i})$, $O_{i}:=X(o_{i})$, and
$\Lambda:=X(\lambda)$, such that, for every $\bar{a}\in M$, $\bar{b}\in O$,
and $c\in\Lambda$

$h_{\mathbb{X}}(\bar{a},\bar{b},c):=\begin{cases}\mathbb{P}(s)&\text{ if
}s(\bar{m},\bar{o},\lambda)=(\bar{a},\bar{b},c)\\\ 0&\text{ if
}(\bar{a},\bar{b},c)\not\in X(\bar{m},\bar{o},\lambda)\end{cases}$

We denote the underlying probabilistic empirical model by $e_{\mathbb{X}}$.

###  2.3 Compatibility of Models and Teams

Team semantics admits elegant formulations of hidden-variable phenomena
because the structure of hidden-variable and empirical models nicely
interplays with operators on the team side. First, we observe the following
relationship between probabilistic and relational hidden-variable models.

######  Lemma 2.11.

Let $\mathbb{X}=(X,\mathbb{P})$ be a probabilistic team over
$\operatorname{Var}_{n}^{h}$ and let $h_{\mathbb{X}}$ be the corresponding
hidden-variable model. Then $X$ is the team representation of the induced
relational model $h$ of $h_{\mathbb{X}}$.

Indeed, $X$ is the underlying support team of $\mathbb{X}$, containing all
assignments with non-zero probability, and this corresponds to the notion of
possibilistic collapse. This holds of course also for empirical models.
Further, we observe that the induced empirical model of a hidden-variable
model corresponds to the restriction to $\operatorname{Var}_{n}^{e}$ on the
team side.

######  Lemma 2.12.

Let $X$ be a relational team over $\operatorname{Var}_{n}^{h}$, let $h_{X}$ be
its corresponding hidden-variable model and $e_{X}$ its induced empirical
model. Then, $X\upharpoonright\operatorname{Var}_{n}^{e}$ is the team
representation of $e_{X}$. Similarly, let $\mathbb{X}$ be a probabilistic team
over $\operatorname{Var}_{n}^{h}$ representing the probabilistic hidden-
variable model $h_{\mathbb{X}}$, and let $e_{\mathbb{X}}$ be its induced
empirical model. Then, $\mathbb{X}\upharpoonright\operatorname{Var}_{n}^{e}$
is the team representation of $e_{\mathbb{X}}$.

This allow us to cast properties of the underlying model as properties of the
hidden-variable model. We can also formulate sort of a reverse.

######  Corollary 1.

Let $X$ be a team over $\operatorname{Var}_{n}^{e}$ with corresponding model
$e_{X}$. A team $Y$ over $\operatorname{Var}_{n}^{h}$ represents an
empirically equivalent hidden-variable model if, and only if,
$Y\upharpoonright\operatorname{Var}_{n}^{e}=X$. Analogously, let $\mathbb{X}$
be a probabilistic team over $\operatorname{Var}_{n}^{e}$. A team $\mathbb{Y}$
over $\operatorname{Var}_{n}^{h}$ represents an empirically equivalent hidden-
variable model if, and only if,
$\mathbb{Y}\upharpoonright\operatorname{Var}_{n}^{e}=\mathbb{X}$.

All these correspondences are neatly summarized by the commutative diagram in
Figure 1.

${\mathbb{X}}$${\mathbb{X}\upharpoonright\operatorname{Var}_{n}^{e}}$${X}$${X\upharpoonright\operatorname{Var}_{n}^{e}}$${h_{\mathbb{X}}}$${e_{\mathbb{X}}}$${h_{X}}$${e_{X}}$
Figure 1: Compatibility of team and model structure

##  3 Relational and Probabilistic Team Semantics

We now introduce the logical machinery that we need to reason about teams and
the hidden-variable models that they represent. We first recall the main
definitions for logics with relational and probabilistic team semantics. Then,
we develop novel correspondences between the two frameworks that will then
allow us to unify relational and probabilistic hidden-variables models and
enable us to develop their theory in parallel.

###  3.1 Relational Team Semantics

Modern logics of dependence and independence are based on atomic properties of
teams and on an interpretation of the classical logical operators $\land$,
$\lor$, $\exists$ and $\forall$ in the framework of teams. There are many
atomic team properties that have been studied in the context of such logics.
In this paper, we shall need only dependence, inclusion, and independence,
which are defined as follows, for any team $X$, and for tuples
$\bar{x},\bar{y},\bar{z}$ of variables in the domain of $X$.

Dependence:

$X\models\operatorname{dep}(\bar{x},\bar{y})$ if for all $s,s^{\prime}\in X$
such that $s(\bar{x})=s^{\prime}(\bar{x})$, also
$s(\bar{y})=s^{\prime}(\bar{y})$;

Inclusion:

$X\models\bar{x}\subseteq\bar{y}$ if $X(\bar{x})\subseteq X(\bar{y})$;

Independence:

$X\models\bar{x}\perp_{\bar{z}}\bar{y}$ if for all $s,s^{\prime}\in X$ such
that $s(\bar{z})=s^{\prime}(\bar{z})$, there exists some $s^{\prime\prime}\in
X$ such that
$s^{\prime\prime}(\bar{z})=s(\bar{z}),s^{\prime\prime}(\bar{x})=s(\bar{x})$,
and $s^{\prime\prime}(\bar{y})=s^{\prime}(\bar{y})$.

Thus $\operatorname{dep}(\bar{x},\bar{y})$ describes functional dependence of
$\bar{y}$ from $\bar{x}$, in the sense that there exist a function $f\colon
X(\bar{x})\rightarrow X(\bar{y})$ such that $s(\bar{y})=f(s(\bar{x}))$ for
every assignment $s\in X$. Independence however is more than the absence of
dependence. The atom $\bar{x}\perp_{\bar{z}}\bar{y}$ expresses that for any
fixed value for $\bar{z}$ in the team, the values of $\bar{x}$ and $\bar{y}$
are completely independent in the sense that additional information about the
value of $\bar{x}$ does not constrain the possible values of $\bar{y}$ in any
way, and vice versa. This variant of independence is sometimes called
_conditional independence_. A _simple independence atom_ instead has the form
$\bar{x}\perp\bar{y}$. We then have that $X\models\bar{x}\perp\bar{y}$ if, and
only if, $X(\bar{x}\bar{y})=X(\bar{x})\times X(\bar{y})$, so any value for
$\bar{x}$ in the team co-exists with any value for $\bar{y}$ in a common
assignment in $X$.

Syntactically, dependence logic ${\rm FO}(\operatorname{dep})$ is built from
dependence atoms $\operatorname{dep}(\bar{x},\bar{y})$ and first-order
literals, i.e. atoms and negated atoms of a fixed vocabulary $\tau$, by the
operators $\land$, $\lor$, $\exists$ and $\forall$. All formulae are written
in negation normal form and negation is only applied to first-order atoms, not
to dependence atoms. Independence logic ${\rm FO}(\perp)$ is built
analogously, using independence atoms $\bar{x}\perp_{\bar{z}}\bar{y}$ instead.

We now present the relational team semantics of ${\rm FO}(\operatorname{dep})$
and ${\rm FO}(\perp)$. Recall that the traditional Tarski semantics for first-
order formulae $\varphi(\bar{x})$ is based on single assignments $s$ whose
domain must comprise the variables in ${\rm free}(\varphi)$; we write
$\mathfrak{A}\models\varphi[s]$ for saying that $\mathfrak{A}$ satisfies
$\varphi$ with the assignment $s$.

The _team semantics_ for a formula $\varphi(\bar{x})$ in a logic of dependence
and independence is instead defined by inductive clauses for the satisfaction
relation $\mathfrak{A}\models_{X}\varphi$ saying that the team $X$ satisfies
$\varphi$ in $\mathfrak{A}$. Since the underlying structure $\mathfrak{A}$ is
not of interest for the purposes of this paper, we shall simplify notation and
simply write $X\models\varphi$ instead. For a classical first-order literal,
i.e. an atom or its negation, we simply say that $X\models\varphi$ if
$\varphi[s]$ is true in the underlying structure for all $s\in X$. To present
the inductive rules of team semantics, we shall need two basic operations that
(possibly) extend the domain of a given team $X$ (with values in $A$) to new
variables.

######  Definition 3.1.

Given an assignment $s$, a variable $x$, and a value $a\in A$, we write
$s[x\mapsto a]$ for the assignment that extends, or updates, $s$ by mapping
$x$ to $a$ (and leaving the values of all other variables unchanged). The
unrestricted _generalisation_ of $X$ over $A$ is $X[x\mapsto A]:=\\{s[x\mapsto
a]\colon s\in X,a\in A\\}$, and the _Skolem-extension_ for a function $F\colon
X\rightarrow\mathcal{P}(A)\setminus\\{\varnothing\\}$ is $X[x\mapsto
F]:=\\{s[x\mapsto a]\colon s\in X,a\in F(s)\\}$.

The following inductive rules then extend the team semantics of atomic team
properties and first-order literals to arbitrary formulae in ${\rm
FO}(\operatorname{dep})$ or ${\rm FO}(\perp)$:

  * •

$X\models\varphi_{1}\wedge\varphi_{2}$ if $X\models\varphi_{i}$ for $i=1,2$;

  * •

$X\models\varphi_{1}\vee\varphi_{2}$ if $X=X_{1}\cup X_{2}$ for two teams
$X_{i}$ such that $\mathfrak{A}\models_{X_{i}}\varphi_{i}$;

  * •

$X\models\forall x\varphi$ if $X[x\mapsto A]\models\varphi$;

  * •

$X\models\exists x\varphi$ if $X[x\mapsto F]\models\varphi$, for some suitable
Skolem extension of $X$ by a function $F\colon
X\rightarrow\mathcal{P}(A)\setminus\\{\varnothing\\}$.

Since
$\operatorname{dep}(\bar{x},\bar{y})\equiv\bar{y}\perp_{\bar{x}}\bar{y}$, we
can freely use dependence atoms in ${\rm FO}(\perp)$, and it is known [21]
that inclusion atoms $\bar{x}\subseteq\bar{y}$ are definable in ${\rm
FO}(\perp)$ as well. In fact, the logic ${\rm
FO}(\operatorname{dep},\subseteq)$ with both inclusion and dependence atoms is
equivalent to ${\rm FO}(\perp)$ and it suffices to use simple independence
atoms to get the full power of ${\rm FO}(\perp)$.

###  3.2 Probabilistic Team Semantics

To understand probabilistic hidden-variable phenomena, we make use of a
probabilistic variant of team semantics. Our definitions are essentially the
same as in [18, 25, 26] with deviations in some details. However, we stress
the fact that we consciously select notations that invite jumping back and
forth between probabilistic and relational semantics. In particular, we use
precisely the same syntax for the probabilistic variants of ${\rm
FO}(\operatorname{dep})$ and ${\rm FO}(\perp)$, but we evaluate the formulae
now over probabilistic teams $\mathbb{X}=(X,\mathbb{P}_{\mathbb{X}})$. To
define the probabilistic semantics for these logics, we first have to describe
the meaning of first-order literals and of dependence and independence atoms.

  * •

For first-order literals $\varphi$, we let $\mathbb{X}\models\varphi$ if, and
only if, $X\models\varphi$ in the relational sense.

  * •

${\mathbb{X}}\models\operatorname{dep}(\bar{x},\bar{y})$ if for all
$\bar{a}\in X(\bar{x})$ there is a $\bar{b}\in X(\bar{y})$ such that
$\mathbb{P}(\bar{y}=\bar{b}\mid\bar{x}=\bar{a})=1$. Note that this corresponds
to a deterministic sense of dependence.

  * •

${\mathbb{X}}\models\bar{x}\perp_{\bar{z}}\bar{y}$ if we have conditional
stochastic independence between $\bar{x}$ and $\bar{y}$ for any given
$\bar{z}$. Formally, this means that for all $\bar{a}\in X(\bar{x}),\bar{b}\in
X(\bar{y}),\bar{c}\in X(\bar{z})$,

$\mathbb{P}(\bar{x}=\bar{a},\bar{y}=\bar{b}\mid\bar{z}=\bar{c})=\mathbb{P}(\bar{x}=\bar{a}\mid\bar{z}=\bar{c})\cdot\mathbb{P}(\bar{y}=\bar{b}\mid\bar{z}=\bar{c}).$

The probabilistic team semantics of the logical operators generalises the
relational semantics. To make this precise, we have to give appropriate
definitions for the split, the generalisation, and the Skolem extension of a
probabilistic team.

######  Definition 3.2.

Let $\mathbb{X}=(X,\mathbb{P}_{\mathbb{X}})$ be a probabilistic team with $A$
as its set of values, and let $\Delta(A)$ denote the set of all probability
distributions over $A$. Consider a function ${\cal F}\colon X\to\Delta(A)$
that maps every $s\in X$ to a probability distribution ${\cal
F}_{s}\in\Delta(A)$ on $A$. It induces a function $F\colon
X\to\mathcal{P}(A)\setminus\\{\varnothing\\}$ via the support of the
distributions ${\cal F}_{s}$, i.e. by setting $F(s):=\\{a\in A:{\cal
F}_{s}(a)>0\\}$. Then, the Skolem extension $\mathbb{X}[x\mapsto{\cal F}]$ is
defined as the probabilistic team over $X[x\mapsto F]$ with distribution

$\mathbb{P}(s[x\mapsto a]):=\sum_{\begin{subarray}{c}t\in X,\\\ t[x\mapsto
a]=s[x\mapsto a]\end{subarray}}\mathbb{P}_{\mathbb{X}}(t)\cdot F_{t}(a).$

Note that the right-hand side simplifies to $\mathbb{P}_{\mathbb{X}}(s)\cdot
F_{s}(a)$ if $x$ is a new variable.

Intuitively, this means that the probability mass of $s$ is split over
multiple extensions $s[x\mapsto a]$ where the proportion assigned to each $a$
is given by $F_{s}(a)$. Thus, we can interpret $F_{s}(a)$ as the probability
of the event $x=a$ conditional on agreement with $s$ on $\mathrm{dom}(s)$. The
function $F$ tells us how we have to extend our underlying relational support
team.

Note that the marginalization of Skolem extensions by ${\cal F}$ gives back
the original team. More formally, for $\mathbb{X}=(X,\mathbb{P})$ with
$x\not\in\mathrm{dom}(X)$ and a Skolem extension
$\mathbb{Y}=\mathbb{X}[x\mapsto{\cal F}]$, it holds that
$\mathbb{X}=\mathbb{Y}\upharpoonright\mathrm{dom}(X)$.

######  Definition 3.3.

The _uniform extension_ $\mathbb{X}[x\mapsto A]$ of $\mathbb{X}$ is the
special case of a Skolem extension $\mathbb{X}[x\mapsto{\cal F}]$ where ${\cal
F}$ maps all $s\in X$ to the uniform distribution over $A$. Explicitly, we get
the distribution

$\mathbb{P}(s[x\mapsto a])=\frac{1}{\lvert
A\rvert}\sum_{\begin{subarray}{c}t\in X\\\ t[x\mapsto a]=s[x\mapsto
a]\end{subarray}}\mathbb{P}_{\mathbb{X}}(t).$

Again this simplifies to $\mathbb{P}(s[x\mapsto
a])=\mathbb{P}_{\mathbb{X}}(s)/{\lvert A\rvert}$ if $x$ is a new variable.
This corresponds to a uniform split of the probability mass of $s$ over all
$\lvert A\rvert$ extensions.

######  Definition 3.4.

Let $\mathbb{X}$ be a probabilistic team with $X$ as its underlying team. We
now define the probabilistic team semantics of the logical operators as
follows:

  * •

$\mathbb{X}\models\varphi_{1}\land\varphi_{2}$ if
$\mathbb{X}\models\varphi_{i}$ for $i=1,2$. Thus, conjunctions are defined in
the straightforward way, as in relational team semantics.

  * •

$\mathbb{X}\models\varphi_{1}\lor\varphi_{2}$ if there are probabilistic teams
$\mathbb{X}_{1},\mathbb{X}_{2}$ and $\lambda\in[0,1]$ with $X=X_{1}\cup X_{2}$
and
$\mathbb{P}_{\mathbb{X}}=(1-\lambda)\mathbb{P}_{\mathbb{X}_{1}}+\lambda\mathbb{P}_{\mathbb{X}_{2}}$
such that $\mathbb{X}_{i}\models\varphi_{i}$ for $i=1,2$. In other words, this
means that we can split $\mathbb{X}$ into a convex combination of two teams
that satisfy the formulae $\varphi_{i}$.

  * •

$\mathbb{X}\models\forall x\varphi$ if $\mathbb{X}[x\mapsto A]\models\varphi$,
i.e. if the uniform extension of $\mathbb{X}$ satisfies $\varphi$.

  * •

$\mathbb{X}\models\exists x\varphi$ if $\mathbb{X}[x\mapsto{\cal
F}]\models\varphi$ for some ${\cal F}\colon X\to\Delta(A)$, i.e. if a suitable
Skolem extension of $\mathbb{X}$ satisfies $\varphi$.

The existential quantifier is most relevant for our purposes and we want to
provide more intuition for it. For a variable $x\not\in\mathrm{dom}(X)$,
$\mathbb{X}\models\exists x\varphi$ expresses the existence of another
probabilistic team $\mathbb{Y}$ over $\mathrm{dom}(X)\cup\\{x\\}$ such that

  1. 1.

$\mathbb{Y}$ satisfies $\varphi$, and

  2. 2.

$\mathbb{Y}$ marginalizes to $\mathbb{X}$ if restricted to $\mathrm{dom}(X)$.
This means that for all $s\in X$ we have that
$\mathbb{P}_{\mathbb{X}}(s)=\sum_{a\in A}\mathbb{P}_{\mathbb{Y}}(s[x\mapsto
a])$.

###  3.3 Back and Forth between Relational and Probabilistic Teams

We now compare probabilistic and relational team semantics. We start with the
satisfaction relation. Note that it is essential for the formulation of this
theorem that we use the same syntax for both variants.

######  Theorem 3.5.

Let $\mathbb{X}$ be a probabilistic team and $X$ its underlying team. For
every formula $\psi\in{\rm FO}(\perp)$, we have that $\mathbb{X}\models\psi$
implies $X\models\psi$. For every $\varphi\in{\rm FO}(\operatorname{dep})$, we
also have the converse, so that $\mathbb{X}\models\varphi$ if, and only if,
$X\models\varphi$.

######  Proof 3.6.

We proceed by induction.

  * •

For first-order literals $\varphi$, we obviously have that
$\mathbb{X}\models\varphi$ if, and only if, $X\models\varphi$.

  * •

Assume that $\mathbb{X}\models\bar{x}\perp_{\bar{z}}\bar{y}$. Now let
$s,s^{\prime}\in X$ with $s(\bar{z})=s^{\prime}(\bar{z})=\bar{c}$. With
$\bar{a}=s(\bar{x})$ and $\bar{b}=s^{\prime}(\bar{y})$ we get that

$\mathbb{P}(\bar{x}=\bar{a},\bar{y}=\bar{b}\mid\bar{z}=\bar{c})=\underbrace{\mathbb{P}(\bar{x}=\bar{a}\mid\bar{z}=\bar{c})}_{\geq\mathbb{P}(s)>0}\cdot\underbrace{\mathbb{P}(\bar{y}=\bar{b}\mid\bar{z}=\bar{c}}_{\geq\mathbb{P}(s^{\prime})>0})>0.$

Since $X$ is the support team of $\mathbb{X}$, there exists
$s^{\prime\prime}\in X$ with
$s^{\prime\prime}(\bar{x},\bar{y},\bar{z})=(\bar{a},\bar{b},\bar{c})$ which
proves that $X\models\bar{x}\perp_{\bar{z}}\bar{y}$.

  * •

For dependence atom, the implication from left to right follows from the fact
that dependence atoms can be understood as special cases of independence
atoms, the other direction is straightforward since $X$ is defined to be the
support of $\mathbb{P}$.

It remains to be shown that the logical operators preserve the implications in
both directions. This is obvious for conjunctions.

  * •

For $\mathbb{X}\models\psi\lor\vartheta$, we choose $\mathbb{Y}\models\psi$
and $\mathbb{Z}\models\vartheta$ with
$\mathbb{X}=(1-\lambda)\mathbb{Y}+\lambda\mathbb{Z}$ so that $X=Y\cup Z$. By
induction hypothesis, $Y\models\psi$ and $Z\models\vartheta$, hence
$X\models\psi\lor\vartheta$. Conversely, given a probabilistic team
$\mathbb{X}$ and a decomposition $X=Y\cup Z$ of the underlying team with
$Y\models\psi$ and $Z\models\vartheta$, it is straightforward to construct
$\mathbb{Y}$ and $\mathbb{Z}$ with underlying $Y$ and $Z$ such that
$\mathbb{P}_{\mathbb{X}}=(1-\lambda)\mathbb{P}_{\mathbb{Y}}+\lambda\mathbb{P}_{\mathbb{Z}}$
for some $\lambda\in[0,1]$. By induction hypothesis $\mathbb{Y}\models\psi$
and $\mathbb{Z}\models\vartheta$, hence $\mathbb{X}\models\psi\lor\vartheta$.

  * •

For formulae $\forall x\psi$, the induction step follows from the fact that
the underlying team of $\mathbb{X}[x\mapsto A]$ is $X[x\mapsto A]$.

  * •

If $\mathbb{X}\models\exists x\psi$ by means of ${\cal F}\colon
X\to\mathcal{P}(A)\setminus\\{\varnothing\\}$, we put $F(s)=\\{a\in A:{\cal
F}_{s}(a)>0\\}$ to get the Skolem extension $X[x\mapsto F]$ as underlying team
of $\mathbb{X}[x\mapsto{\cal F}]$, so $X[x\mapsto F]\models\psi$ and hence
$X\models\exists x\psi$. Conversely, let $X\models\exists x\psi$, hence
$X[x\mapsto F]\models\psi$ for some $F\colon
X\to\mathcal{P}(A)\setminus\\{\varnothing\\}$. Let ${\cal
F}:X\mapsto\Delta(A)$ be the function that maps every $s\in X$ to the uniform
distribution over $F(s)$. Then, $\mathbb{X}[x\mapsto{\cal F}]$ has $X[x\mapsto
F]$ as underlying team and the induction hypothesis is applicable.

We next address the matter of logical entailment.

######  Definition 3.7.

Let $\psi,\varphi\in{\rm FO}(\perp)$. We write
$\psi\models_{\text{rel}}\varphi$ if for all suitable relational teams $X$
with $X\models\psi$ also $X\models\varphi$ holds. Analogously, we define
$\psi\models_{\text{prob}}\varphi$ as entailment according to probabilistic
team semantics. If both $\psi\models_{\text{rel}}\varphi$ and
$\psi\models_{\text{prob}}\varphi$ hold, we write
$\psi\models_{\text{all}}\varphi$.

Results that are analogous to the theorem below have been established for
databases but apparently not applied to teams so far.

######  Theorem 3.8.

  1. 1.

For formulae in ${\rm FO}(\operatorname{dep})$, $\models_{\text{rel}}$ and
$\models_{\text{prob}}$ coincide.

  2. 2.

If $\psi\in{\rm FO}(\operatorname{dep}),\varphi\in{\rm FO}(\perp)$, then
$\psi\models_{\text{prob}}\varphi\implies\psi\models_{\text{rel}}\varphi$.

  3. 3.

If $\psi\in{\rm FO}(\perp)$ and $\varphi\in{\rm FO}(\operatorname{dep})$, then
$\psi\models_{\text{rel}}\varphi\implies\psi\models_{\text{prob}}\varphi$.

  4. 4.

For $\varphi,\psi\in{\rm FO}(\perp)$, neither implication holds in general.
Conjunctions of conditional independence atoms suffice to generate
counterexamples.

######  Proof 3.9.

Notice that (2) and (3) follow immediately from Theorem 3.5 and that (1)
follows by combining (2) and (3) since ${\rm
FO}(\operatorname{dep})\subseteq{\rm FO}(\perp)$. (4) remains to be shown. We
adapt formulae and counterexamples from [36].

We first show that, in general, $\psi\models_{\text{rel}}\varphi$ does not
imply $\centernot\implies\psi\models_{\text{prob}}\varphi$. Let
$\psi_{1}=z\perp_{x}w\land z\perp_{y}w\land x\perp_{wz}y$ and
$\varphi_{1}=z\perp_{xy}w$. The intuition behind
$\psi_{1}\models_{\text{rel}}\psi_{2}$ is that we can combine $z\perp_{x}w$
and $z\perp_{y}w$ to get $z\perp_{xy}w$ by using $x\perp_{wz}y$ to enforce
agreement on $xy$.

Let $X\models\psi_{1}$ and $s_{1},s_{2}\in X$ with
$(a,b)=s_{1}(x,y)=s_{2}(x,y)$. Further, let $c:=s_{1}(z)$ and $d:=s_{2}(w)$.
Since $X\models z\perp_{x}w$, there exists $s_{3}\in X$ with $s_{3}(x)=a$ and
$s_{3}(z,w)=(c,d)$. Similarly, we obtain $s_{4}\in X$ with $s_{4}(y)=b$ and
$s_{4}(z,w)=(c,d)$ via $X\models z\perp_{y}w$. By applying $X\models
x\perp_{wz}y$ on $s_{3}$ and $s_{4}$, we finally obtain $s_{5}\in X$ with
$s_{5}(x,y,z,w)=(a,b,c,d)$ which shows that $X\models\varphi_{1}$. Thus,
$\psi_{1}\models_{\text{rel}}\varphi_{1}$. Howver, it is straightforward to
verify that the probabilistic team given below satisfies $\psi_{1}$ but not
$\varphi_{1}$.

$x$ | $y$ | $z$ | $w$ | $\mathbb{P}$
---|---|---|---|---
0 | 0 | 0 | 0 | 0.2
0 | 0 | 0 | 1 | 0.2
0 | 0 | 1 | 0 | 0.2
0 | 0 | 1 | 1 | 0.1
0 | 1 | 1 | 1 | 0.1
1 | 0 | 1 | 1 | 0.1
1 | 1 | 1 | 1 | 0.1
$x$ | $y$ | $z$ | $w$
---|---|---|---
0 | 0 | 0 | 0
0 | 0 | 0 | 1
0 | 1 | 0 | 0
1 | 0 | 0 | 0
1 | 1 | 0 | 0
1 | 1 | 1 | 0

$\psi_{1}\not\models_{\text{prob}}\varphi_{1}$
$\psi_{2}\not\models_{\text{rel}}\varphi_{2}$

To prove that $\psi\models_{\text{prob}}\varphi$ does not necessarily imply
that $\psi\models_{\text{rel}}\varphi$, we use the fact from [33, equation
(A3), p. 15] that $\psi_{2}\models_{\text{prob}}\varphi_{2}$, for
$\psi_{2}=x\perp_{yz}y\land z\perp_{x}w\land z\perp_{y}w\land x\perp y$ and
$\varphi_{2}=z\perp w$ (proven in a different context with techniques
employing measure theory and information theory). On the other side, a team
proving that $\psi_{2}\not\models_{\text{rel}}\varphi_{2}$ is given above (to
the right).

We remark that if $\varphi,\psi\in{\rm FO}(\perp)$ are conjunctions of _simple
independence atoms_ , then
$\psi\models_{\text{rel}}\varphi\Longleftrightarrow\psi\models_{\text{prob}}\varphi$.
This follows by observing that the proof calculi provided in the literature,
see [22] for the relational and [23] for the probabilistic case, coincide.

##  4 Reasoning about Hidden-Variable Properties in Independence Logic

We now define and investigate properties of hidden-variable models by means of
dependence and independence logic.

###  4.1 Logical Definitions of Properties of Hidden-Variable Models

In the literature, many properties of hidden-variable and empirical models are
investigated. Given that these models can be seen as (relational or
probabilistic) teams, we can define properties of such models by logical
formulae that are evaluated over such teams. Actually, since natural
properties are defined for models of arbitrary arity, their logical definition
is not given by a single formula, but by a uniform family of such formulae,
one for each arity. That is, for a property $P$ of probabilstic hidden-
variable models, we present a family of formulae $\psi_{n}\in{\rm FO}(\perp)$,
with free variables in $\operatorname{Var}_{n}^{h}$ such that for any
probabilistic team $\mathbb{X}$ that represents a hidden-variable model
$h_{\mathbb{X}}$ of arity $n$, we have that $h_{\mathbb{X}}$ has property $P$
if, and only if, $\mathbb{X}\models\psi_{n}$. Similarly, for empirical models,
and for the relational case.

Actually, it is a fundamental observation that for all elementary properties,
syntactically identical formulae work for the relational and the probabilistic
case simultaneously. Also, our formulae are in fact very simple; essentially
just conjunctions of atoms. This is quite elegant and another indication that
team semantics is very well suited to express hidden-variable phenomena.

#### Properties of empirical models

We start with presenting three fundamental properties that empirical models
may or may not have. Note that in our formulae, the role of $n$ is hidden in
notations such as $\bar{m}$ for $m_{1}\dots m_{n}$ and $\bar{o}$ for
$o_{1}\dots,o_{n}$. The following notation is helpful: For a tuple
$\bar{z}=(z_{1}\dots z_{n})$, let $\bar{z}_{-i}=(z_{1}\dots
z_{i-1}z_{i+1}\dots z_{n})$.

Weak Determinism:

An empirical model is weakly deterministic if the combined measurements
$\bar{m}$ in all components deterministically determine the outcome $\bar{o}$
of all components. However, this property does not forbid that the outcome of
the $i$-th component depends on the measurement choice in components other
than $i$. This property is defined by

$\mathrm{WeakDet}^{e}_{n}:=\operatorname{dep}(\bar{m},\bar{o}).$

Strong Determinism:

If we strengthen Weak Determinism and require that the outcome of the $i$-th
component is uniquely determined by the measurement choice in that component,
we obtain the notion of Strong Determinism, defined by

$\mathrm{StrongDet}^{e}_{n}:=\bigwedge_{i=1}^{n}\operatorname{dep}(m_{i},o_{i}).$

No-Signalling:

This property is a bit more complicated. Roughly speaking, the idea is to
formalize that no information can be transmitted to component $i$ by choice of
measurement in components other than $i$. Thus, the outcome of the $i$-th
component (which for example Alice receives) may, conditional on her choice of
measurement, not depend on other measurements. An illustration of this point
is given in Example 4.1 below. No-Signalling is closely related to the famous
No-Communication Theorem in Quantum Mechanics. Formally,

$\mathrm{NoSig}^{e}_{n}:=\bigwedge_{i=1}^{n}o_{i}\perp_{m_{i}}\bar{m}_{-i}.$

It may not be completely obvious why the formulae $\mathrm{NoSig}^{e}_{n}$
have the intended meaning. Intuitively, an independence atom
$\bar{x}\perp_{\bar{z}}\bar{y}$ expresses that conditional on knowing
$\bar{z}$, getting information about $\bar{x}$ does not give additional
information about $\bar{y}$. Thus, $\mathrm{NoSig}^{e}_{n}$ states that if
$m_{i}$ is known, the other measurements $\bar{m}_{-i}$ do not give additional
information about $o_{i}$.

######  Example 4.1.

To illustrate how a violation of No-Signalling allows communication, consider
the empirical model defined by the following team $X$:

$m_{1}$ | $m_{2}$ | $o_{1}$ | $o_{2}$
---|---|---|---
$a$ | $b_{1}$ | $+$ | $-$
$a$ | $b_{2}$ | $-$ | $-$

In this case, $X\not\models o_{1}\perp_{m_{1}}m_{2}$ which allows Bob to
instantly transmit information to Alice by choice of his measurement. If Bob
makes measurement $b_{1}$, Alice receives a $+$ in her experiment; if he
chooses $b_{2}$, Alice receives a $-$. In this configuration, Bob can send a
full bit of information to Alice by means of his measurement choice; No-
Signalling is rightfully violated. Also note that this example satisfies Weak
Determinism but not Strong Determinism.

It is a relevant feature of team semantics, often called locality, that the
meaning of a formula depends only on those variables that occur free in it.
Thus, even if we evaluate a formula over a hidden-variable model, we can
express properties of the underlying empirical model (if the variable
$\lambda$ is not used in the formula). Properties of the underlying empirical
model can therefore be cast as properties of the hidden-variable model itself.
This is made precise in the following proposition.

######  Proposition 2.

Let $\mathbb{X}$ be a probabilistic team over $\operatorname{Var}_{n}^{h}$,
and let $\psi^{e}\in{\rm FO}(\perp)$ be a formula over
$\operatorname{Var}_{n}^{e}$ that formalizes a property $P$ of probabilistic
empirical models. Then $\mathbb{X}\models\psi^{e}$ if, and only if,
$e_{\mathbb{X}}$ has property $P$.

######  Proof 4.2.

By locality, $\mathbb{X}\models\psi^{e}$ is equivalent to
$\mathbb{X}\upharpoonright\operatorname{Var}_{n}^{e}\models\psi^{e}$. By Lemma
2.12, $\mathbb{X}\upharpoonright\operatorname{Var}_{n}^{e}$ is the team
representation of $e_{\mathbb{X}}$.

By the same argument, the analogous statement for relational teams and models
also holds.

#### Properties of hidden-variable models

We now show, in a similar fashion, that common properties of hidden-variable
models are definable in dependence and independence logic. The reader may want
to compare our formula with the definitions in [1, 13]. Except in the case of
locality (which we shall discuss separately), it is straightforward to see
that our definitions capture the properties from the literature. We feel that
our definitions by formulae of team semantics are more compact and precise,
and they highlight the essential features better than an explicit unrolling of
the semantic of dependence and independence atoms in every instance.

Weak Determinism:

For hidden-variable models, Weak Determinism means that for every fixed value
of a hidden-variable the chosen measurements in all components determine the
outcomes. It is essential that the outcomes may also depend on the hidden-
variable, which allows explaining non-deterministic empirical models by
deterministic hidden-variable models with more fine-grained internal states.
Formally

$\mathrm{WeakDet}^{h}_{n}:=\operatorname{dep}(\bar{m}\lambda,\bar{o}).$

Strong Determinism:

Strong Determinism strengthens Weak Determinism by requiring that for every
fixed value of the hidden-variable the measurement in the $i$-th component
determines the outcome in the $i$-th component. Formally,

$\mathrm{StrongDet}^{h}_{n}:=\bigwedge_{i=1}^{n}\operatorname{dep}(m_{i}\lambda,o_{i}).$

Single-Valuedness:

A hidden-variable model is single valued if the hidden-variable set $\Lambda$
has only one element. Such a model is essentially just an empirical model,
because a single-valued variable does not provide any additional freedom.

$\mathrm{SingVal}^{h}_{n}:=\operatorname{dep}(-,\lambda).$

$\lambda$-Independence:

This formalizes the idea that the measurement process and the hidden-variable
should be independent. It is related to the intuition that the physical
reality we measure shall be independent of the experimenters’ choices. A
particularly pathological counterexample to $\lambda$-Independence would be a
system where the hidden-variable of the system uniquely determines which
measurements will be done by the experimenters.

$\lambda\text{\rm-Indep}^{h}_{n}:=\bar{m}\perp\lambda.$

Outcome Independence:

This property states that outcomes of measurements in different components
shall be independent from each other when conditioning on $\bar{m}\lambda$.
This means that when we perform the same measurements in the same hidden
states, the outcomes of the various components shall not provide information
about each other. Note that violation of this property is related to the
phenomenon of quantum entanglement where we obtain correlations between
outcomes even in case of spatially separated particles.

$\text{\rm Out-
Indep}^{h}_{n}:=\bigwedge_{i=1}^{n}o_{i}\perp_{\bar{m}\lambda}\bar{o}_{-i}.$

Parameter Independence:

This is essentially the hidden-variable analogue of No-Signalling. For fixed
$m_{i}\lambda$, the outcome $o_{i}$ of component $i$ shall be independent of
the measurements taken in the other components:

$\text{\rm Par-
Indep}^{h}_{n}:=\bigwedge_{i=1}^{n}o_{i}\perp_{m_{i}\lambda}\bar{m}_{-i}.$

Locality:

A hidden-variable model is local if all components are independent of each
other. Roughly speaking, to understand a system satisfying Locality, one only
needs to understand every component and piece them together independently.
Jarrett has shown that this is adequately expressed by the conjunction of
Parameter Independence and Outcome Independence [30]:

$\mathrm{Loc}^{h}_{n}:=\text{\rm Out-Indep}^{h}_{n}\land\text{\rm Par-
Indep}^{h}_{n}.$

Heuristically speaking, Outcome Independence gives independence of the $i$-th
component of the other outcomes while Parameter Independence gives
independence of the other measurements. Put together, they give full
independence the other components. This argument is made precise below.

######  Example 4.3.

We adapt Example 4.1 to a hidden-variable model satisfying Single-Valuedness:

$m_{1}$ | $m_{2}$ | $o_{1}$ | $o_{2}$ | $\lambda$
---|---|---|---|---
$a$ | $b_{1}$ | $+$ | $-$ | $\lambda_{1}$
$a$ | $b_{2}$ | $-$ | $-$ | $\lambda_{1}$

The resulting model does satisfy neither Parameter Independence nor Strong
Determinism but satisfies Weak Determinism and Outcome Independence.

An intuitive and precise semantic characterization of Locality is shown in the
following two lemmata for the relational and probabilistic case respectively.

######  Lemma 4.4.

Let $X$ be a relational team of arity $n$ over $\operatorname{Var}_{n}^{h}$.
$X\models\mathrm{Loc}^{h}_{n}$ if, and only if, for every tuple
$(\bar{a},c)\in X(\bar{m},\lambda)$ and for all $b_{1},\dots,b_{n}$ with
$b_{i}\in X(o_{i})$ the following condition (*) holds: If there is an
assignment $s_{i}\in X$ with $s_{i}(m_{i},o_{i},\lambda)=(a_{i},b_{i},c)$ for
all $i$, then there is an $s\in X$ with
$s(\bar{m},\bar{o},\lambda)=(\bar{a},\bar{b},\bar{c})$.

######  Proof 4.5.

Assume that $X\models\mathrm{Loc}^{h}_{n}$, i.e., $X\models\text{\rm Out-
Indep}^{h}_{n}\land\text{\rm Par-Indep}^{h}_{n}$. Let $(\bar{a},c)\in
X(\bar{m},\lambda)$ and $b_{i}\in X(b_{i})$ for every $i\leq n$. Let $s_{i}\in
X$ with $s_{i}(m_{i},o_{i},\lambda)=(a_{i},b_{i},c)$. We need to construct
some $t\in X$ with $t(\bar{m},\bar{o},\lambda)=(\bar{a},\bar{b},c)$. Since
$(\bar{a},c)\in X(\bar{m},\lambda)$, there exists $\tilde{s}\in X$ with
$\tilde{s}(\bar{m},\lambda)=(\bar{a},c)$. By applying Parameter Independence
on $s_{i}$ and $\tilde{s}$ we get $\tilde{s_{i}}\in X$ which fulfills
$\tilde{s_{i}}(\bar{m},\lambda)=(\bar{a},c)$ and $\tilde{s_{i}}(o_{i})=b_{i}$.
By inductively applying Outcome Indpendence, we can now construct a sequence
$t_{1},\dots,t_{n}$ with $t_{i}(\bar{m},\lambda)=(\bar{a},c)$ and
$t_{i}(o_{1},\dots,o_{i})=(b_{1},\dots,b_{i})$. Choosing $t:=t_{n}$ completes
the argument for the first implication.

For the converse, suppose that $X$ satisfies condition (*). We prove that
$X\models\text{\rm Out-Indep}^{h}_{n}$. Let $s_{1},s_{2}\in X$ with
$s_{1}(\bar{m},\lambda)=s_{2}(\bar{m},\lambda)$ and let $i\leq n$. Condition
(*) immediately gives that $s_{3}$ given by
$s_{3}(\bar{m},\lambda)=s_{1}(\bar{m},\lambda)$, $s_{3}(o_{i})=s_{1}(o_{i})$,
and $s_{3}(\bar{o}_{-i})=s_{2}(\bar{o}_{-i})$ is indeed in $X$; this proves
Outcome Independence. Parameter Independence is shown similarly.

Condition (*) in Lemma 4.4 is a common alternative definition of Locality. In
words it essentially states that the question whether a measurement-outcome
pair $(\bar{a},\bar{b})$ is possible for a fixed value of $\lambda$ reduces to
whether the measurement-outcome pair $(a_{i},b_{i})$ is possible in every
component $i$. However, a slight technical complication is that we require
this to only hold for measurements $\bar{a}$ that are possible for a fixed
value of $\lambda$: We explicitly do not require that $(a_{i},c)\in
X(m_{i},\lambda)$ for all $i$ implies $(\bar{a},c)\in X(\bar{m},\lambda)$. The
latter condition is called Measurement Locality in [1] and rather natural but
not entailed in the usual definition of Locality.

######  Example 4.6.

Consider the hidden-variable model given by the following team:

$m_{1}$ | $m_{2}$ | $o_{1}$ | $o_{2}$ | $\lambda$
---|---|---|---|---
$a$ | $b$ | 1 | 0 | $\lambda_{1}$
$a$ | $b$ | 1 | 1 | $\lambda_{1}$
$a$ | $c$ | 0 | 1 | $\lambda_{1}$
$a$ | $c$ | 0 | 0 | $\lambda_{1}$
$a$ | $b$ | 0 | 0 | $\lambda_{2}$
$a$ | $c$ | 0 | 1 | $\lambda_{2}$

This model does not satisfy Locality: For the hidden-variable $\lambda_{1}$,
it is possible that $a$ results in 0 and that $b$ results in $1$. However,
$(ab,01,\lambda_{1})$ is not an element of the team even though
$(ab,\lambda_{1})\in X(\bar{m},\lambda)$. Thus, Locality is falsified
according to the previous lemma. Note that, in this instance, Parameter
Independence is violated since the choice of measurement in the second
component influences the possible results in the first component. However,
Outcome Independence holds. Also, this team satisfies $\lambda$-Independence
since all possible measurements, i.e. $ab$ and $ac$, appear for both values of
the hidden-variable.

In the probabilistic case, Locality means that the probability factors over
the various components. This is in a sense a quantitative analogue of the
qualitative statement from the previous lemma.

######  Lemma 4.7.

Let $\mathbb{X}=(X,\mathbb{P})$ be a probabilistic team over
$\operatorname{Var}_{n}^{h}$. Then $\mathbb{X}\models\mathrm{Loc}^{h}_{n}$ if,
and only if the following condition (**) holds: For all $(\bar{a},c)\in
X(\bar{m},\lambda)$ and all $b_{1},\dots,b_{n}$ with $b_{i}\in X(o_{i})$

$\mathbb{P}(\bar{o}=\bar{b}\mid\bar{m}=\bar{a},\lambda=c)=\prod\nolimits_{i=1}^{n}\mathbb{P}(o_{i}=b_{i}\mid
m_{i}=a_{i},\lambda=c).$

######  Proof 4.8.

Assume that $\mathbb{X}\models\mathrm{Loc}^{h}_{n}$. Let $(\bar{a},c)\in
X(\bar{m},\lambda)$ and $b_{i}\in X(o_{i})$ for $i\leq n$. To simplify
notation, let $\bar{o}_{k}:=o_{1}\dots o_{k}$ and $\bar{b}_{k}:=b_{1}\dots
b_{k}$ We apply induction over $k$ to obtain

$\displaystyle\quad\mathbb{P}(\bar{o}_{k+1}=\bar{b}_{k+1}\mid\bar{m}=\bar{a},\lambda=c)$
$\displaystyle\qquad=\quad\mathbb{P}(o_{k+1}=b_{k+1}\mid\bar{o}_{k}=\bar{b}_{k},\bar{m}=\bar{a},\lambda=c)\cdot\mathbb{P}(\bar{o}_{k}=\bar{b}_{k}\mid\bar{m}=\bar{a},\lambda=c)$
$\displaystyle\qquad=\quad\mathbb{P}(o_{k+1}=b_{k+1}\mid\bar{m}=\bar{a},\lambda=c)\cdot\prod\nolimits_{i=1}^{k}\mathbb{P}(o_{i}=b_{i}\mid\bar{m}=\bar{a},\lambda=c)$
$\displaystyle\qquad=\quad\prod\nolimits_{i=1}^{k+1}\mathbb{P}(o_{i}=b_{i}\mid\bar{m}=\bar{a},\lambda=c)=\prod\nolimits_{i=1}^{k+1}\mathbb{P}(o_{i}=b_{i}\mid
m_{i}=a_{i},\lambda=c),$

by applying Outcome Independence, Parameter Independence, and the induction
hypothesis. Setting $k+1=n$ completes the argument.

For the converse, let $\mathbb{X}$ satisfy condition (**). We first show that
$\mathbb{X}\models\text{\rm Par-Indep}^{h}_{n}$:

$\displaystyle\mathbb{P}(o_{i}=b_{i}\mid\bar{m}=\bar{a},\lambda=c)\quad=\quad\sum\nolimits_{\bar{b}_{-i}}\mathbb{P}(\bar{o}=\bar{b},\bar{m}=\bar{a},\lambda=c)$
$\displaystyle\quad=\quad\sum\nolimits_{\bar{b}_{-i}}\prod\nolimits_{j=1}^{n}\mathbb{P}(o_{j}=b_{j}\mid
m_{j}=a_{j},\lambda=c)$ $\displaystyle\quad=\quad\mathbb{P}(o_{i}=b_{i}\mid
m_{i}=a_{i},\lambda=c)*\prod\nolimits_{j\neq
i}\sum\nolimits_{b_{j}}\mathbb{P}(o_{j}=b_{j}\mid m_{j}=a_{j},\lambda=c)$
$\displaystyle\quad=\quad\mathbb{P}(o_{i}=b_{i}\mid m_{i}=a_{i},\lambda=c).$

Outcome Independence is then shown by the following equation for all $i$:

$\displaystyle\mathbb{P}(o_{i}=b_{i},\bar{o}_{-i}=\bar{b}_{-i}\mid\bar{m}=\bar{a},\lambda=c)\quad=\quad\prod\nolimits_{j=1}^{n}\mathbb{P}(o_{j}=b_{j}\mid
m_{j}=a_{j},\lambda=c)$ $\displaystyle\quad=\quad\mathbb{P}(o_{i}=b_{i}\mid
m_{i}=a_{i},\lambda=c)*\prod\nolimits_{j\neq i}\mathbb{P}(o_{j}=b_{j}\mid
m_{j}=a_{j},\lambda=c)$ $\displaystyle\quad=\quad\mathbb{P}(o_{i}=b_{i}\mid
m_{i}=a_{i},\lambda=c)*\mathbb{P}(\bar{o}_{-i}=\bar{b}_{-i}\mid\bar{m}_{-i}=\bar{a}_{-i},\lambda=c)$
$\displaystyle\quad=\quad\mathbb{P}(o_{i}=b_{i}\mid\bar{m}=\bar{a},\lambda=c)*\mathbb{P}(\bar{o}_{-i}=\bar{b}_{-i}\mid\bar{m}=\bar{a},\lambda=c),$

where the last equality follows by Parameter Independence.

#### Unifying Relational and Probabilistic Properties.

An advantage of our framework is that it gives an elegant logical argument why
properties of probabilistic models carry over to the underlying relational
models. This behaviour is, by Theorem 3.5, an immediate consequence of the
fact that the properties in question are defined in both cases by
syntactically the same formulae from independence logic. This novel and purely
logical perspective complements earlier work on unifying relational and
probabilistic properties employing algebraic and category-theoretical tools
[4].

######  Proposition 3.

Let $\psi\in{\rm FO}(\perp)$ capture a property $P$ of both probabilistic and
relational models. If a probabilistic model satisfies $P$, its underlying
relational model also satisfies $P$. For $\psi\in{\rm
FO}(\operatorname{dep})$, the converse also holds.

In particular, this holds for every single property defined in Section 4.1.

######  Corollary 4.

If a probabilistic hidden-variable model satisfies any of the elementary
properties defined above (e.g. $\lambda$-Independence, Locality, No-
Signalling, …), its underlying relational model also satisfies the
corresponding property. For the properties which rely only on dependence atoms
(Strong-Determinism, Weak-Determinism, Single-Valuedness), the converse also
holds.

The proposition applies of course much more generally than just to the handful
of properties that we listed explicitly. Of course, every family of formulae
in ${\rm FO}(\perp)$ induces properties of relational and probabilistic models
in a way that satisfies the assumptions of 3. Since independence logic is a
rather powerful logic – recall that it can express all NP properties of teams
by [21] – this induces a very large class of properties with the
aforementioned relationship between probabilistic and relational models.

###  4.2 Connections between Properties via Logical Entailment

Implications of the form that “all models with property $P$ also satisfy
property $Q$” have been proved for instance in [1] and [13]. In our framework,
such statements are elegantly cast as entailments between formulae of
independence logic ${\rm FO}(\perp)$. Thus, they can be proven directly on the
logical level. This allows us to make use of the relationship between
$\models_{\text{rel}}$ and $\models_{\text{prob}}$ to develop the results for
both cases in parallel.

######  Theorem 4.9.

  1. 1.

Single-Valuedness implies $\lambda$-Independence:

$\mathrm{SingVal}^{h}_{n}\models_{\text{all}}\lambda\text{\rm-Indep}^{h}_{n}.$

  2. 2.

Weak Determinism implies Outcome Independence:

$\mathrm{WeakDet}^{h}_{n}\models_{\text{all}}\text{\rm Out-Indep}^{h}_{n}.$

  3. 3.

Strong Determinism corresponds to the conjunction of Weak Determinism and
Parameter Independence:

$\mathrm{StrongDet}^{h}_{n}\equiv_{\text{all}}\mathrm{WeakDet}^{h}_{n}\land\text{\rm
Par-Indep}^{h}_{n}.$

######  Proof 4.10.

By Theorem 3.8, the probabilistic case suffices for (1) and (2). Claim (1)
immediately follows from the fact that point distributions are stochastically
independent of all distributions.

For (2) we need to show that
$\mathrm{WeakDet}^{h}_{n}\models_{\text{prob}}\text{\rm Out-Indep}^{h}_{n}$.
Let $\mathbb{X}=(X,\mathbb{P})\models\mathrm{WeakDet}^{h}_{n}$. For every
$(\bar{a},c)\in X(\bar{m},\lambda)$ the distribution
$\mathbb{P}(\bar{o}\mid\bar{m}=\bar{a},\lambda=c)$ is a point distribution.
This implies that $\mathbb{X}\models o_{i}\perp_{\bar{m}\lambda}\bar{o}_{-i}$
and thereby $\mathbb{X}\models\text{\rm Out-Indep}^{h}_{n}$.

For (3) we first observe that the entailment
$\mathrm{StrongDet}^{h}_{n}\models\mathrm{WeakDet}^{h}_{n}$ is obvious in both
semantics. For
$\mathrm{StrongDet}^{h}_{n}\models_{\text{all}}\mathrm{WeakDet}^{h}_{n}\land\text{\rm
Par-Indep}^{h}_{n}$, it remains to show that
$\mathrm{StrongDet}^{h}_{n}\models_{\text{prob}}\text{\rm Par-Indep}^{h}_{n}$.
But this is trivial as well since the distribution over $o_{i}$ for a fixed
pair $(m_{i},\lambda)$ assigns, by Strong Determinism, probability 1 to a
single value. This suffices because point distributions are stochastically
independent of every other distribution and thus in particular from the
conditional distribution on $\bar{m}_{-i}$.

For the converse, we show that $\mathrm{WeakDet}^{h}_{n}\land\text{\rm Par-
Indep}^{h}_{n}\models_{\text{rel}}\mathrm{StrongDet}^{h}_{n}$. Let
$X\models\mathrm{WeakDet}^{h}_{n}\land\text{\rm Par-Indep}^{h}_{n}$, and let
$s_{1},s_{2}\in X$ agree on $m_{i}$ and $\lambda$. Then, by Parameter
Independence, there exists $s_{3}\in X$ that takes the same value on $m_{i}$
and $\lambda$ and also satisfies $s_{3}(o_{i})=s_{1}(o_{i})$ and
$s_{3}(\bar{m}_{-i})=s_{2}(\bar{m}_{-i})$. This entails that
$s_{3}(\bar{m})=s_{2}(\bar{m})$ which in turn gives, by Weak Determinism, that
$s_{3}(\bar{o})=s_{2}(\bar{o})$ and in particular
$s_{1}(o_{i})=s_{3}(o_{i})=s_{2}(o_{i})$.

It is instructive to think about the intuition for the classification of
Strong Determinism as conjunction of Weak Determinism and Parameter
Independence: Consider a model which satisfies Weak Determinism but not Strong
Determinism. In this case, full measurements $\bar{m}$ uniquely determine
outcomes $\bar{o}$ but single $m_{i}$ do not determine $o_{i}$. However, it is
then necessary that the other measurements $\bar{m}_{-i}$ contain information
about $o_{i}$ which contradicts Parameter Independence. In a sense, the
independence of other measurements is precisely the missing component to go
from Weak Determinism to Strong Determinism.

Recall that we defined Locality as conjunction of Parameter Independence and
Outcome Independence. Thus, we immediately obtain the following.

######  Corollary 5.

Strong Determinism implies Locality:
$\mathrm{StrongDet}^{h}_{n}\models_{\text{all}}\mathrm{Loc}^{h}_{n}$.

Because of 2, we can formulate implications of the form “if $h$ is a hidden-
variable model satisfying $P^{h}$, then its underlying empirical model $e$
satisfies $P^{e}$” also by entailment of properties.

######  Theorem 4.11.

The underlying empirical models of hidden-variable models that satisfy
Parameter Independence and $\lambda$-Independence fulfill No-Signalling:

$\lambda\text{\rm-Indep}^{h}_{n}\land\text{\rm Par-
Indep}^{h}_{n}\models_{\text{all}}\mathrm{NoSig}^{e}_{n}.$

Before we prove this we want to give some intuition. Recall that the only
difference between Parameter Independence and No-Signalling is that the former
requires independence of $o_{i}$ and $\bar{m}_{-i}$ conditional on
$(m_{i},\lambda)$ instead of just $m_{i}$. Intuitively, we use the
$\lambda$-Independence to obtain a “copy” of $s_{2}$ – namely $\tilde{s}_{2}$
– which agrees with $s_{1}$ on the hidden-variable to allow us to apply
Parameter Independence.

######  Proof 4.12 (Proof (relational case)).

Let $X\models\text{\rm Par-Indep}^{h}_{n}\land\lambda\text{\rm-
Indep}^{h}_{n}$. Let $i\in\\{1,\dots,n\\}$ and $s_{1},s_{2}\in X$ with
$s_{1}(m_{i})=s_{2}(m_{i})$. Choose by $\lambda$-Independence an assignment
$\tilde{s}_{2}\in X$ with $\tilde{s}_{2}(\lambda)=s_{1}(\lambda)$ and
$\tilde{s}_{2}(\bar{m})=s_{2}(\bar{m})$. Then
$s_{1}(m_{i},\lambda)=\tilde{s}_{2}(m_{i},\lambda)$ and by applying Parameter
Independence to $s_{1}$ and $\tilde{s}_{2}$, we get $s_{3}\in X$ with
$s_{3}(o_{i})=s_{1}(o_{i})$ and
$s_{3}(\bar{m}_{-i})=\tilde{s}_{2}(\bar{m}_{-i})=s_{2}(\bar{m}_{-i})$. Thus,
$X\models\mathrm{NoSig}^{e}_{n}$.

######  Proof 4.13 (Proof (probabilistic case)).

Let $\mathbb{X}=(X,\mathbb{P})\models\text{\rm Par-
Indep}^{h}_{n}\land\lambda\text{\rm-Indep}^{h}_{n}$ and $i\in\\{1,\dots,n\\}$.
Let $o\in X(o_{i}),a\in X(m_{i})$, and $\bar{a}_{-i}\in X(\bar{m}_{-i})$. We
put $\Lambda=X(\lambda)$. We have

$\displaystyle\mathbb{P}(o_{i}=o\mid\bar{m}=\bar{a})\quad=\quad\sum_{c\in\Lambda}\mathbb{P}(o_{i}=o,\lambda=c\mid\bar{m}=\bar{a})$
$\displaystyle\quad=\quad\sum_{c\in\Lambda}\mathbb{P}(o_{i}=o\mid\lambda=c,\bar{m}=\bar{a})*\mathbb{P}(\lambda=c\mid\bar{m}=\bar{a})$
$\displaystyle\quad=\quad\sum_{c\in\Lambda}\mathbb{P}(o_{i}=o\mid\lambda=c,m_{i}=a_{i})*\mathbb{P}(\lambda=c\mid\bar{m}=\bar{a})\quad\text{(by
$\text{\rm Par-Indep}^{h}_{n}$)}$
$\displaystyle\quad=\quad\sum_{c\in\Lambda}\mathbb{P}(o_{i}=o\mid\lambda=c,m_{i}=a_{i})*\mathbb{P}(\lambda=c\mid
m_{i}=a_{i})\quad\text{(by $\lambda\text{\rm-Indep}^{h}_{n}$)}$
$\displaystyle\quad=\quad\;\mathbb{P}(o_{i}=o\mid m_{i}=a_{i})$

and thus $\mathbb{X}\models o_{i}\perp_{m_{i}}\bar{m}_{-i}$.

##  5 Existence of Hidden-Variable Models via Satisfiability

We now investigate the question whether a given empirical models admits an
empirically equivalent hidden-variable model with certain given properties.
Again, our team semantical framework allows us to treat this in an elegant
fashion. Essentially, the question reduces to the satisfiability of formulae
of the form $\exists\lambda\psi$ on extensions of the given team by a finite
set of values for the hidden variable $\lambda$, where $\psi$ encodes the
properties of interest.

Notice that a team $X$ of assignments $s\colon\mathrm{dom}(X)\rightarrow A$
can of course also be understood as a team of assignments
$s\colon\mathrm{dom}(X)\rightarrow A\cup\Lambda$ for any set $\Lambda$, and
since elements of $\Lambda$ do not occur in the team, this does not change any
of the _atomic_ dependence and independence properties of $X$. However, for an
existential formula $\exists\lambda\varphi$ (or a universal one) the universe
of values that are available for $\lambda$ does of course matter.

######  Definition 5.1.

For a team $X$ with values in $A$ and a set $\Lambda$, we write $X+\Lambda$
for the team with the additional supply $\Lambda$ of values. We say that a
formula $\varphi\in{\rm FO}(\perp)$ is _satisfiable by a (finite) extension of
$X$_ if there exists a (finite) set $\Lambda$ such that
$X+\Lambda\models\psi$. All of this applies as well to probabilistic teams.

The following observation, which we formulate for probabilistic teams,
connects existence of suitable hidden-variable models with team semantics.

######  Proposition 6.

Let $\mathbb{X}$ be a probabilistic team representing an empirical model
$e_{\mathbb{X}}$. For an arbitrary property $P$ of hidden-variable models
captured by a formula $\psi\in{\rm FO}(\perp)$, the following two statements
are equivalent:

  1. 1.

There is a hidden-variable model $h_{\mathbb{P}}$ which satisfies $P$ and is
empirically equivalent to $e_{\mathbb{X}}$.

  2. 2.

$\exists\lambda\psi$ is satisfiable by a finite extension of $\mathbb{X}$.

######  Proof 5.2.

A hidden-variable model $h_{\mathbb{P}}$ (where $\lambda$ takes values in
$\Lambda$) which is empirically equivalent to $e_{\mathbb{X}}$ corresponds to
a team that can be written as a Skolem extension
$\mathbb{Y}=(\mathbb{X}+\Lambda)[\lambda\mapsto{\cal F}]$ for a suitable
function ${\cal F}\colon X\to\Delta(\Lambda)$. Meanwhile, every Skolem
extension of $\mathbb{X}+\Lambda$ represents a hidden-variable model that is
equivalent to $e_{\mathbb{X}}$. The proposition follows since
$\mathbb{X}+\Lambda\models\exists\lambda\psi$ expresses precisely that a
suitable Skolem extension of $\mathbb{X}+\Lambda$ satisfies $\psi$.

We immediately get the following connection between probabilistic and
relational existence results by our general results on the level of team
semantics.

######  Proposition 7.

Let $\psi\in{\rm FO}(\perp)$ formalize a property $P$ of both relational and
probabilistic hidden-variable models. If a probabilistic empirical model has
an empirically equivalent hidden-variable model satisfying $P$, then this also
holds for its induced relational model. If $\psi\in{\rm
FO}(\operatorname{dep})$, the converse also holds.

######  Proof 5.3.

Assume that the probabilistic case holds for a probabilistic team
$\mathbb{X}=(X,\mathbb{P})$ over $\operatorname{Var}_{n}^{e}$. Thus, there is
a finite set $\Lambda$ such that
$\mathbb{X}+\Lambda\models\exists\lambda\psi$. This implies by Theorem 3.5
that $X+\Lambda\models\exists\lambda\psi$, which was to be shown. For
$\psi\in{\rm FO}(\operatorname{dep})$, the converse follows by similar
arguments.

Again, our elementary properties can be treated as a special case of this
general result. If a probabilistic empirical model possesses an equivalent
hidden-variable model satisfying any of the elementary properties defined
above (such as Locality, $\lambda$-Independence, Strong Determinism, …), then
the same holds for its underlying relational model. For the properties that
rely only on dependence atoms (Strong-Determinism, Weak-Determinism, Single-
Valuedness), the converse also holds.

We next give logical proofs of some existence theorems – which are already
known from [1] and [13] – in our framework. We will start with a trivial one.

######  Proposition 8.

Every (relational and probabilistic) empirical model is realized by an
equivalent hidden-variable model satisfying Single-Valuedness.

######  Proof 5.4.

Recall that $\mathrm{SingVal}^{h}_{n}:=\operatorname{dep}(-,\lambda)$, and for
any team $X$, we can take an arbitrary set $\Lambda$ to get that
$X+\Lambda\models\exists\lambda\operatorname{dep}(-,\lambda)$. This
establishes the relational case, which also implies the probabilistic one.

######  Proposition 9.

Every (relational and probabilistic) empirical model is realized by an
empirically equivalent hidden-variable model satisfying Strong Determinism.

######  Proof 5.5.

Let $X$ be a team and put $\Lambda:=X$. We need to show that

$X+\Lambda\models\exists\lambda\bigwedge\nolimits_{i=1}^{n}\operatorname{dep}(m_{i}\lambda,o_{i}).$

Consider the Skolem extension $Y=(X+\Lambda)[\lambda\mapsto F]$ with
$F(s)=\\{s\\}$. For all $s,s^{\prime}\in Y$, $s(\lambda)=s^{\prime}(\lambda)$
implies that $s=s^{\prime}$. This shows that $Y$ satisfies Strong Determinism
and thus proves the relational case. Since $\mathrm{StrongDet}^{h}_{n}\in{\rm
FO}(\operatorname{dep})$, the probabilistic case also follows.

This construction shows that Strong Determinism is hardly a satisfying
property in itself; letting every fixed hidden variable deterministically
determine a measurement-outcome pair is far from desirable. A natural
additional assumption is $\lambda$-Independence, which states that the
measurement process is independent from the hidden-variables of the system to
be measured. This is by no means satisfied in the construction above; indeed,
the hidden-variables deterministically determine the measurement taken.

9 implies a result for Locality since
$\mathrm{StrongDet}^{h}_{n}\models_{\text{all}}\mathrm{Loc}^{h}_{n}$.

######  Corollary 10.

Every (relational and probabilistic) empirical model is realized by an
empirically equivalent hidden-variable model satisfying Locality.

Terms such as “local realism” appearing in the literature refer in fact to the
existence of hidden-variable models satisfying the conjunction of Locality and
$\lambda$-Independence. This is not proven above and indeed in general false
as we shall see in Section 6 when we discuss Bell’s Theorem. But if we weaken
Strong Determinism to Weak Determinism, we can realize it together with
$\lambda$-Independence.

######  Proposition 11.

Every relational empirical model and every probabilistic empirical model with
rational probabilities is realized by an empirically equivalent hidden-
variable model satisfying Weak Determinism and $\lambda$-Independence.

######  Proof 5.6.

Note that we only need to prove the probabilistic case, as the restriction to
rational probabilities does not impair the argument in the proof of 7. We
adapt a construction from [13] to our team semantic framework.

Let $\mathbb{X}=(X,\mathbb{P}_{\mathbb{X}})$ be a probabilistic team over
$\operatorname{Var}_{n}^{e}$, with $|X(\bar{m})|=L$ and $|X(\bar{o})|=K$. For
every pair $z=(\bar{a},\bar{b})\in X(\bar{m})\times X(\bar{o})$, let

$\mathbb{P}_{\mathbb{X}}(\bar{o}=\bar{b}\mid\bar{m}=\bar{a})=p(z)=\frac{r(z)}{s(z)}$

with $r(z),s(z)\in\mathbb{N}$ such that $s(z)\neq 0$ and $r(z)$ and $s(z)$ are
co-prime for each $z$. Let $N$ be the least common multiple of all numbers
$s(z)$, and choose a set $\Lambda$ with $N$ points. The idea is to make all
$\lambda\in\Lambda$ equally likely and independent from the measurements.
However, we assign a different number of hidden-variables to each measurement-
output pair as follows. For every $z$, let $N(z):=p(z)N\in\mathbb{N}$.
Clearly, for every $\bar{a}\in X(\bar{m})$ we have that $\sum_{\bar{b}\in
X(\bar{o})}N(\bar{a},\bar{b})=N$. For every $\bar{a}\in X(\bar{m})$ we thus
get a partition of $\Lambda$ into a collection
$(\Lambda(\bar{a},\bar{b}))_{\bar{b}\in X(\bar{o})}$ of disjoint sets where
$\Lambda(z)$ has $N(z)$ elements. We now define the Skolem extension
$\mathbb{Y}=\mathbb{X}[\lambda\mapsto{\cal F}]$ by the function ${\cal
F}:X\to\Delta(\Lambda)$ that maps $s\in X$ with $s(\bar{m},\bar{o})=z$ to the
uniform distribution over $\Lambda(z)$. We claim that $\mathbb{Y}$ satisfies
Weak Determinism and $\lambda$-Independence.

Weak Determinism: Weak Determinism follows immediately from the construction
of $\mathbb{Y}$. Regard arbitrary $\bar{a}\in X(\bar{m}),c\in\Lambda$. There
exists a unique $\bar{b}\in X(\bar{o})$ such that $c\in N((\bar{a},\bar{b}))$.
This is by construction the unique $\bar{b}\in X(\bar{o})$ with
$\mathbb{P}(\bar{o}=\bar{b},\lambda=c\mid\bar{m}=\bar{a})>0$.

$\lambda$-Independence: To prove $\lambda$-Independence we have to show that
$\mathbb{Y}\models\bar{m}\perp\lambda$. Regard arbitrary $\bar{a}\in
X(\bar{m})$ and $c\in\Lambda$ and choose the unique $\bar{b}$ with non-zero
probability implied by Weak Determinism. We observe that

$\displaystyle\mathbb{P}(\lambda=c\mid\bar{m}=\bar{a})\ =\
\mathbb{P}(\bar{o}=\bar{b},\lambda=c\mid\bar{m}=\bar{a})$
$\displaystyle\qquad=\quad\mathbb{P}(\lambda=c\mid\bar{o}=\bar{b},\bar{m}=\bar{a})\cdot\mathbb{P}(\bar{o}=\bar{b}\mid\bar{m}=\bar{a})=\frac{1}{N(z)}p(z)=\frac{1}{N},$

independent of $\bar{a}$. This completes the proof.

Next we provide a normal form for hidden-variable models satisfying Locality
and $\lambda$-Independence, i.e. “local realism”. This normal form is well-
known from prior literature, cf. e.g. [20, 4, 1] – nevertheless we provide an
elementary and accessible proof for the benefit of the reader new to the study
of hidden-variables.

######  Theorem 5.7.

Every relational empirical model and every probabilistic empirical model with
rational probabilities which admits an empirically equivalent hidden-variable
satisfying Locality and $\lambda$-Independence also admits an equivalent model
satisfying Strong Determinism and $\lambda$-Independence.

######  Proof 5.8 (Proof (relational case)).

Let $X$ be a team over $\operatorname{Var}_{n}^{e}$ such that
$X+\Lambda\models(\exists\lambda\in\Lambda)\lambda\text{\rm-
Indep}^{h}_{n}\land\mathrm{Loc}^{h}_{n}$. Thus, there is a Skolem extension
$Y=(X+\Lambda)[\lambda\mapsto F]$ such that $Y\models\lambda\text{\rm-
Indep}^{h}_{n}\land\mathrm{Loc}^{h}_{n}$ For $\bar{a}\in
X(\bar{m}),c\in\Lambda$ we let

$O(\bar{a},c):=\\{\bar{b}\in X(\bar{o}):(\bar{a},\bar{b},c)\in
Y(\bar{m},\bar{o},\lambda)\\}.$

By $\lambda$-Independence, $O(\bar{a},c)\neq\varnothing$. Also, for each
$i\leq n$ and $a\in X(m_{i})$, we set

$O_{i}(a,c):=\\{b\in X(o_{i}):(a,b,c)\in Y(m_{i},o_{i},\lambda)\\}.$

Note that $Y\models\mathrm{Loc}^{h}_{n}$ and Lemma 4.4 imply that
$O(\bar{a},c)=\prod_{i=1}^{n}O^{i}(a_{i},c)$.

Let $F^{i}_{c}$ be the set of all functions $f_{i}\colon X(m_{i})\to X(o_{i})$
where $f_{i}(a)\in O_{i}(a,c)$ for all $a\in X(m_{i})$. The set
$\Lambda^{\prime}$ is now defined to contain all pairs
$(c,f)=(c,(f_{1},\dots,f_{n}))$ where $c\in Y(\lambda)$ and $f_{i}\in
F^{i}_{c}$ for $i\leq n$.

Let $F^{\prime}\colon X\to{\cal P}^{+}(\Lambda^{\prime})$ be the function with
$F^{\prime}(s)=\\{(c,f)\in\Lambda^{\prime}:f_{i}(s(m_{i}))=s(o_{i})\text{ for
all $i$}\\}$. It is straightforward to see that $F^{\prime}(s)$ is indeed non-
empty. We claim that $Z:=X[\lambda\mapsto F^{\prime}]$ satisfies Strong
Determinism and $\lambda$-Independence.

Strong Determinism: Let $s,s^{\prime}\in Z$ with
$s(\lambda)=s^{\prime}(\lambda)=(c,f)$ and $s(m_{i})=s^{\prime}(m_{i})=a$. By
definition of $F^{\prime}$, it holds that
$s(o_{i})=f_{i}(s(m_{i}))=f_{i}(s^{\prime}(m_{i}))=s^{\prime}(o_{i})$.

$\lambda$-Independence: We show the slightly stronger claim that for every
$\bar{a}\in X(\bar{m})$ and $(c,f)\in\Lambda^{\prime}$ there exists some $s\in
Z$ with $s(\bar{m})=\bar{a}$ and $s(\lambda)=(c,f)$. By definition of
$\Lambda^{\prime}$, it holds that $b_{i}:=f_{i}(a_{i})\in O_{i}(a_{i},c)$ for
all $i\leq n$. Thus, $\bar{b}\in\prod_{i=1}^{n}O^{i}(a_{i},c)=O(\bar{a},c)$.
Choose $s\in X$ with $s(\bar{m})=\bar{a},s(\bar{o})=\bar{b}$. Since $(c,f)\in
F^{\prime}(s)$, our claim and thereby $\lambda$-Independence follows.

######  Proof 5.9 (Proof (probabilistic case)).

Let now $\mathbb{X}=(X,\mathbb{P}_{\mathbb{X}})$ be a probabilistic team over
$\operatorname{Var}_{n}^{e}$ with
$\mathbb{X}+\Lambda\models(\exists\lambda\in\Lambda)\lambda\text{\rm-
Indep}^{h}_{n}\land\mathrm{Loc}^{h}_{n}$, and let
$\mathbb{Y}=(\mathbb{X}+\Lambda)[\lambda\mapsto{\cal F}]$ be a Skolem
extension with $\mathbb{Y}\models\lambda\text{\rm-
Indep}^{h}_{n}\land\mathrm{Loc}^{h}_{n}$ As in the relational case we set for
$\bar{a}\in X(\bar{m}),c\in\Lambda$

$\displaystyle O(\bar{a},c)$ $\displaystyle=\\{\bar{b}\in
X(\bar{o}):(\bar{a},\bar{b},c)\in Y(\bar{m},\bar{o},\lambda)\\}$
$\displaystyle=\\{\bar{b}\in
X(\bar{o}):\mathbb{P}_{\mathbb{Y}}(\bar{o}=\bar{b}\mid\bar{m}=\bar{a},\lambda=c)>0\\},$

which is non-empty by $\lambda$-Independence. Also, we let for all $i\leq n$
and $a\in X(m_{i})$

$O_{i}(a,c):=\\{b\in X(o_{i}):(a,b,c)\in Y(m_{i},o_{i},\lambda)\\}$

such that, by Locality, $O(\bar{a},c)=\prod_{i=1}^{n}O_{i}(a_{i},c)$.

Let $Z_{i}=Y(m_{i})\times Y(o_{i})\times\Lambda$. For every triple
$z_{i}=(a_{i},b_{i},c)\in Z_{i}$, let

$\mathbb{P}_{\mathbb{Y}}(o_{i}=b_{i}\mid
m_{i}=a_{i},\lambda=c)=p_{i}(z_{i})=\frac{r_{i}(z_{i})}{s_{i}(z_{i})}.$

where $r_{i}(z)$ and $s_{i}(z)$ are co-prime natural numbers with
$s_{i}(z_{i})\neq 0$. Let $N_{i}$ be the least common multiple of the numbers
$s_{i}(z_{i})$, let $\Lambda_{i}$ be a set with $N_{i}$ elements and define

$\tilde{\Lambda}=\Lambda\times(\Lambda_{1}\times\dots\times\Lambda_{n}).$

We then put $N_{i}(z_{i})=p_{i}(z_{i})N_{i}$ and construct, for every pair
$(a_{i},c)\in Y(m_{i})\times\Lambda$ a partition
$(\Lambda_{i}(a_{i},b_{i},c))_{b_{i}\in Y(o_{i})}$ of $\Lambda_{i}$ with
$\lvert\Lambda_{i}(z_{i})\rvert=N_{i}(z_{i})$ for all $z_{i}\in Z_{i}$. This
is possible because

$\displaystyle\sum_{b_{i}\in Y(o_{i})}N_{i}(a_{i},b_{i},c)$
$\displaystyle=\sum_{b_{i}\in Y(o_{i})}p_{i}(a_{i},b_{i},c)N_{i}$
$\displaystyle=N_{i}\sum_{b_{i}\in
Y(o_{i})}\mathbb{P}_{\mathbb{Y}}(o_{i}=b_{i}\mid
m_{i}=a_{i},\lambda=c)=N_{i}.$

We now define a function ${\cal F}^{\prime}\colon X\to\Delta(\tilde{\Lambda})$
as follows. An assignment $s\in X$ with
$s(\bar{m},\bar{o},\lambda)=(\bar{a},\bar{b},c)$ defines the tuple
$(z_{1},\dots,z_{n})$ where $z_{i}=(a_{i},b_{i},c)\in Z_{i}$. The function
${\cal F}^{\prime}$ maps $s$ to the probability distribution ${\cal
F}^{\prime}_{s}$ with

${\cal
F}^{\prime}_{s}(c,(c_{1},\dots,c_{n}))=\frac{\mathbb{P}_{\mathbb{Y}}(\lambda=c\mid\bar{m}=\bar{a},\bar{o}=\bar{b})}{N_{1}(z_{1})\dots
N_{n}(z_{n})},$

if
$(c_{1},\dots,c_{n})\in\Lambda_{1}(z_{1})\times\dots\times\Lambda_{n}(z_{n})$,
and ${\cal F}^{\prime}_{s}(c,(c_{1},\dots,c_{n}))=0$, otherwise. It is
straightforward to see that this is indeed always a probability distribution.
We then define $\mathbb{Z}=\mathbb{X}[\lambda\mapsto{\cal F}^{\prime}]$ and
claim that $\mathbb{Z}$ satisfies Strong Determinism and
$\lambda$-Independence:

Strong Determinism: Regard an arbitrary $a_{i}\in X(m_{i})$ and
$(c,(c_{1},\dots,c_{n}))\in\tilde{\Lambda}$. Suppose that
$\mathbb{P}_{\mathbb{Z}}(o_{i}=b_{i}\mid
m_{i}=a_{i},\lambda=(c,(c_{1},\dots,c_{n})))>0$. By definition of ${\cal
F}^{\prime}$ it then follows that $c_{i}\in\Lambda_{i}(z_{i})$ for
$z_{i}=(a_{i},b_{i},c)$. Since $a_{i},c,c_{i}$ are fixed, this uniquely
determines $b_{i}$ and shows Strong Determinism.

$\lambda$-Independence: Here, we abuse notation a bit and write
$\lambda=(\lambda_{1},\lambda_{2})$ to refer to the two components of elements
of $\tilde{\Lambda}$. Let $\bar{a}\in X(\bar{m})$ and
$(c,(c_{1},\dots,c_{n}))\in\tilde{\Lambda}$. There is a unique $\bar{b}\in
X(\bar{o})$ with $c_{i}\in\Lambda(a_{i},b_{i},c)$ for all $i$. Thus,

$\displaystyle\mathbb{P}_{\mathbb{Z}}(\lambda=(c,(c_{1},\dots,c_{n}))\mid\bar{m}=\bar{a})=\mathbb{P}_{\mathbb{Z}}(\lambda=(c,(c_{1},\dots,c_{n}),\,\bar{o}=\bar{b}\mid\bar{m}=\bar{a})$
$\displaystyle\quad=\quad\mathbb{P}_{\mathbb{Z}}(\lambda_{2}=(c_{1},\dots,c_{n})\mid\lambda_{1}=c,\,\bar{o}=\bar{b},\,\bar{m}=\bar{a})\cdot\mathbb{P}_{\mathbb{Z}}(\lambda_{1}=c,\,\bar{o}=\bar{b}\mid\bar{m}=\bar{a}).$

######  Lemma 5.10.

$\mathbb{P}_{\mathbb{Z}}(\bar{o}=\bar{b},\lambda_{1}=c\mid\bar{m}=\bar{a})=\mathbb{P}_{\mathbb{Y}}(\lambda=c)\prod_{i=1}^{n}p_{i}(z_{i})$.

Indeed,
$\mathbb{P}_{\mathbb{Z}}(\lambda_{1}=c,\bar{o}=\bar{b},\bar{m}=\bar{a})=\mathbb{P}_{\mathbb{Y}}(\lambda=c,\bar{o}=\bar{b},\bar{m}=\bar{a})$
since marginalizing $\mathbb{Z}$ to $(\bar{m},\bar{o},\lambda_{1})$ gives rise
to $\mathbb{Y}$. Hence

$\displaystyle\mathbb{P}_{\mathbb{Z}}(\bar{o}=\bar{b},\,\lambda_{1}=c\mid\bar{m}=\bar{a})\quad=\quad\mathbb{P}_{\mathbb{Y}}(\bar{o}=\bar{b},\,\lambda=c\mid\bar{m}=\bar{a})$
$\displaystyle\qquad=\quad\mathbb{P}_{\mathbb{Y}}(\bar{o}=\bar{b}\mid\lambda=c,\,\bar{m}=\bar{a})\cdot\mathbb{P}_{\mathbb{Y}}(\lambda=c\mid\bar{m}=\bar{a}),$

and by Locality and $\lambda$-Independence of $\mathbb{Y}$ this coincides with

$\prod_{i=1}^{n}\mathbb{P}_{\mathbb{Y}}(o_{i}=b_{i}\mid
m_{i}=a_{i},\lambda=c)*\mathbb{P}_{\mathbb{Y}}(\lambda=c)\quad=\quad\mathbb{P}_{\mathbb{Y}}(\lambda=c)\prod_{i=1}^{n}p_{i}(z_{i}).$

This proves the lemma. Putting it together with the equation above we get

$\displaystyle\mathbb{P}_{\mathbb{Z}}(\lambda=(c,(c_{1},\dots,c_{n}))\mid\bar{m}=\bar{a})$
$\displaystyle\qquad=\quad\prod_{i=1}^{n}\frac{1}{N_{i}\cdot
p_{i}(z_{i})}\cdot\mathbb{P}_{\mathbb{Y}}(\lambda=c)\prod_{i=1}^{n}p_{i}(z_{i})\quad=\quad\frac{\mathbb{P}_{\mathbb{Y}}(\lambda=c)}{N_{1}\cdots
N_{n}},$

which is independent from $\bar{a}$. This proves that
$\mathbb{Z}\models\lambda\text{\rm-Indep}^{h}_{n}$.

##  6 Bell’s Theorem and Non-Locality

The famous theorem by Bell, originally formulated in the groundbreaking work
[7], showed that a certain flavor of local hidden-variable theories cannot
reproduce some predictions by quantum mechanics. This property corresponds to
the conjunction of Strong-Determinism and $\lambda$-Independence – which is by
Theorem 5.7 closely related to the conjunction of Locality and
$\lambda$-Independence – in our framework. Commonly, the class of theories
refuted by Bell’s Theorem is referred to by the name of “local realism” (cf.
[16]).

Since Bell’s work contains one of the most influential results on hidden-
variables, we think it is worthwhile to discuss how its assumptions compare to
our formulation. All important assumptions of Bell, which are led to a
contradiction, are contained in equation (2) from the original paper [7],
namely

$P(\vec{a},\vec{b})=\int\mathbb{P}(\lambda)A(\vec{a},\lambda)B(\vec{b},\lambda)\,\mathrm{d}\lambda.$

There, $\vec{a},\vec{b}$ range over measurements of two components $A$ and
$B$, $\lambda$ ranges over a space of hidden-variables, and $A$ and $B$ denote
functions that provide the outcomes of the respective components
deterministically depending on their arguments. Thus, $P(\vec{a},\vec{b})$
denotes the expectation value of the product of the outcomes of $A$ and $B$
when measurements $\vec{a},\vec{b}$ are chosen.

The assumed properties are implicitly encoded in the dependencies of the
equation above. Writing $A(\vec{a},\lambda)$ and $B(\vec{b},\lambda)$ entails
the assumption that the outcome of a component is deterministically given by
the measurement in the component together with the hidden-variable, i.e.
Strong Determinism. Writing $\mathbb{P}(\lambda)$ instead of
$\mathbb{P}(\lambda\mid\vec{a},\vec{b})$ assumes that the distribution over
$\lambda$ is independent from the measurements chosen, i.e.
$\lambda$-Independence. Thus, proving that Strong Determinism and
$\lambda$-Independence cannot generally be realized together constitutes a
proof of Bell’s No-Go-Theorem.

The proof of Bell’s Theorem is probabilistic in nature. By 7, a relational
analogue implies the probabilistic formulation. Therefore, we provide here a
relational no-go theorem based on the Hardy Paradox from [27] (instead of the
original argument due to Bell), following the presentation in [1]. We add some
further remarks. The significance of Bell’s Theorem goes far beyond the
theoretical no-go result as it allows a way to experimentally test Non-
Locality (cf. for example [16]). In this context it should be noted, that the
empirical models and teams appearing in this and related results [1] are not
just arbitrary mathematical constructions, but arise from quantum mechanical
states and measurements. We do not go into details here, but refer to [6]
where, based on [1], the notion of _quantum realisable teams_ has been spelled
out explicitly.

######  Theorem 6.1.

There exists a relational empirical model without an equivalent hidden-
variable model satisfying the conjunction of Strong Determinism and
$\lambda$-Independence.

######  Proof 6.2.

Let $X$ be an arbitrary team over $\operatorname{Var}_{2}^{e}$ which satisfies
the following assumptions:

  1. 1.

$X(m_{1},m_{2})=\\{(a_{1},b_{1}),(a_{1},b_{2}),(a_{2},b_{1}),(a_{2},b_{2})\\}$.

  2. 2.

$X(o_{1},o_{2})\subseteq\\{R,G\\}^{2}$ where $R\neq G$

  3. 3.

$(a_{1}b_{1},RR)\in X$

  4. 4.

$(a_{1}b_{2},RR)\not\in X$

  5. 5.

$(a_{2}b_{1},RR)\not\in X$

  6. 6.

$(a_{2}b_{2},GG)\not\in X$

Of course many such teams exist. Assume that $X$ has an equivalent hidden-
variable model represented by a team $Y$ with
$Y\models\mathrm{StrongDet}^{h}_{2}\land\lambda\text{\rm-Indep}^{h}_{2}$. Note
that $Y\models\text{\rm Par-Indep}^{h}_{2}$ since
$\mathrm{StrongDet}^{h}_{n}\models_{\text{rel}}\text{\rm Par-Indep}^{h}_{n}$.
Due to (3), there exists $s_{1}\in Y$ with $s(m_{1}m_{2})=a_{1}b_{1}$ and
$s(o_{1}o_{2})=RR$. Define $c=s_{1}(\lambda)$. There also exists an $s_{2}\in
Y$ with $s_{2}(m_{1}m_{2})=a_{1}b_{2}$ and $s(\lambda)=c$ due to
$\lambda$-Independence and $(a_{1},b_{2})\in X(\bar{m})=Y(\bar{m})$. Applying
Parameter Independence on $s_{1}$ and $s_{2}$ gives $s_{3}\in Y$ with
$s_{3}(\bar{m})=s_{2}$ and $s_{3}(o_{1})=s_{1}(o_{1})=R$. Assumption (4) gives
$s_{3}(o_{2})=G$.

Analogously to $s_{2}$, we have $s_{4}\in Y$ with $s_{4}(\bar{m})=a_{2}b_{2}$
and $s_{4}(\bar{m})=c$. Applying Parameter Independence on $s_{2}$ and $s_{4}$
gives $s_{5}\in Y$ with $s_{5}(\bar{m})=a_{2}b_{2}$ and $s_{5}(\bar{o})=RG$.

Next, we construct $s_{6}\in Y$ with $s_{6}(\bar{m})=a_{2}b_{1}$ and
$s_{6}(\bar{o})=RG$. However, $s_{1}(m_{2})=b_{1}=s_{6}(m_{2})$ but
$s_{1}(o_{2})=R\neq G=s_{6}(o_{2})$ which contradicts Strong Determinism.

By Theorem 5.7, we immediately obtain a no-go result for local realism;
formalizing the notion that quantum mechanics is non-local.

######  Corollary 12.

There exist a relational empirical model and a probabilistic empirical model
without empirically equivalent hidden-variable models satisfying the
conjunction of Locality and $\lambda$-Independence.

We want to conclude this section with a historical note: It shall be remarked
that Bell himself did not regard his theorem as a refutation of hidden-
variables. In fact, Bell was a proponent of Bohmian Mechanics introduced in
[11, 12] – an explicitly non-local hidden-variable interpretation of quantum
mechanics. Bell clearly emphasizes (see [10], p. 53) that the essential
argument of Bell’s Theorem does not depend on determinism or any other
property of hidden-variables but just on the kind of correlations quantum
mechanics predicts. Thus, he said, “it is a merit of the de Broglie-Bohm
version to bring this out so explicitly that it cannot be ignored” ([9], p.
159).

##  7 The Kochen-Specker Theorem and Non-Contextuality

The celebrated Kochen-Specker Theorem about the contextuality of quantum
mechanics is one of the most important results about hidden-variable models.
It is rather difficult to understand, which is also due to the fact that it is
often formulated in an imprecise way and that the notion of
(non-)contextuality is used inconsistently in the literature. We attempt to
shed light on the Kochen-Specker Theorem by discussing several variants of it,
including a formulation purely in terms of linear algebra and two different
formulations in terms of logics with team semantics, highlighting
(non)-contextuality as a team-semantical property.

###  7.1 The Linear-Algebraic Version of the Kochen-Specker Theorem

We first recall the Kochen-Specker Theorem in essentially its original form. A
_measurement context_ on a Hilbert space is a set $X$ of observables (i.e.
Hermitian operators) that are compatible in the sense that they share a common
eigenbasis (and thus commute). In quantum mechanical terms, the Kochen-Specker
Theorem states that there is a finite set $M$ of observables such that it is
impossible to assign a unique meaningful value to every observable in $M$ in a
_non-contextual_ way, i.e. independent of its measurement context $X\subseteq
M$.

######  Definition 7.1.

Let $M$ be a set of linear operators on a Hilbert space $\mathcal{H}$, A
valuation $v\colon M\to\mathbb{R}$ _respects the algebraic structure of
$\mathcal{H}$_ if for any collection $\\{A_{i}:i\in I\\}$ of pairwise
commuting operators in $M$ we have that

  * •

if $\sum_{i\in I}A_{i}=A\in M$, then $v(A)=\sum_{i\in I}v(A_{i})$, and

  * •

if $A_{i}A_{j}=A_{j}A_{i}\in M$, then $v(A_{i}A_{j})=v(A_{i})v(A_{j})$.

Note that the algebraic structure needs to be respected by $v$ only inside of
measurement contexts, i.e. for operators that commute. The product of non-
commuting observables, on the other side, is in general not an observable. The
Kochen-Specker says that, for certain small sets of observables, the algebraic
structure cannot be respected even in this weak sense.

######  Theorem 7.2 (Kochen-Specker).

For every Hilbert space $\mathcal{H}$ with $\dim\mathcal{H}\geq 3$, there
exists a finite set $M$ of Hermitian operators on $\mathcal{H}$ such that no
$v\colon M\to\mathbb{R}$ with $v\neq 0$ respects the algebraic structure of
$\mathcal{H}$.

A modern proof [15] for $\dim\mathcal{H}\geq 4$ relies on a simple
combinatorial lemma about orthonormal bases (ONB) of $\mathbb{R}^{4}$.

######  Lemma 7.3.

There exists a set $Z=\\{a_{1},\dots,a_{18}\\}\subseteq\mathbb{R}^{4}$ and
nine sets $X_{1},\dots,X_{9}$, each consisting of four elements of $Z$ that
form an ONB of $\mathbb{R}^{4}$, such that no subset $S\subseteq Z$ fulfills
$\lvert S\cap X_{j}\rvert=1$ for all $j$.

This lemma relies on an explicit construction of vectors
$a_{1},\dots,a_{18}\in\mathbb{R}^{4}$, and a collection of subsets
$X_{1},\dots,X_{9}$ that use every $a_{i}$ exactly twice. That is, for every
$1\leq i\leq 18$ there exist precisely two indices $j$ with $a_{i}\in X_{j}$.
Once this construction is complete, the lemma follows by a simple parity
argument. The explicit construction is not important for our purposes and can
be found in [15].

The Kochen-Specker Theorem (for $\dim\mathcal{H}\geq 4$) can now be
established as follows: Each vector $a\in Z$ induces an orthonormal projection
operator $A$. Let $M$ be the collection of all operators $A_{i}$, induced by
$a_{i}\in Z$, together with the identity operator $I$. For an ONB
$\\{a,b,c,d\\}$ the induced projection operators $A,B,C,D$, together with $I$,
form a measurement context of compatible observables, since they share
$\\{a,b,c,d\\}$ as a common eigenbasis. Let now $v\colon
M\rightarrow\mathbb{R}$ be a valuation that respects the algebraic structure.
We have to show that $v=0$. Otherwise, assume that $v(A)\neq 0$ for some $A\in
M$. Since $v(I)\cdot v(A)=v(I\cdot A)=v(A)$ it follows that $v(I)=1$. Further,
every projection operator $A\in M$ is idempotent, so $v(A)=v(A)^{2}$ and hence
$v(A)\in\\{0,1\\}$. Finally, if $A,B,C,D$ are projection operators
corresponding to an orthonormal basis it holds that $A+B+C+D=I$ and thereby
that $v(A)+v(B)+v(C)+v(D)=1$. Since $v(A),\dots,v(D)\in\\{0,1\\}$, it follows
that precisely one of the four projections is mapped to 1. But then the set
$S:=\\{a_{i}\in Z:v(A_{i})=1\\}$ would have the property that $|S\cap
X_{j}|=1$ for all $j$, contradicting Lemma 7.3.

For the proof of dimension three, we refer the interested reader to [28, 31].

###  7.2 Non-Contextuality as a Team Semantical Property

We now formulate the Kochen-Specker theorem in the language of teams, focusing
on the notion of non-contextuality. We provide two alternative formulations
each of which has its own advantages. To formulate this as elegantly as
possible, we first define new team semantic atoms.

######  Definition 7.4.

For $k$-tuples $\bar{x}_{1},\bar{x}_{2}$ and $m$-tuples
$\bar{y}_{1},\bar{y}_{2}$ of variables, let

$\displaystyle
X\models\operatorname{dep}((\bar{x}_{1},\bar{x}_{2}),(\bar{y}_{1},\bar{y}_{2}))\text{
if }$ $\displaystyle\text{for all }s,t\in X\text{ with
}s(\bar{x}_{1})=t(\bar{x}_{2}),$ $\displaystyle\text{ also
}s(\bar{y}_{1})=t(\bar{y}_{2}).$

Further, we define that $X\models\operatorname{nc}(x_{1}\dots x_{k},y)$ if for
all $s,t\in X$ with $t(y)\in\\{s(x_{1}),\dots,s(x_{k})\\}$ it follows that
$s(y)=t(y)$. We use this to define the atom $\operatorname{ncc}(x_{1}\dots
x_{k})$ for _non-contextual choice_ , with semantics given by

$\operatorname{ncc}(x_{1}\dots x_{k})\equiv\exists
y\left(\bigvee_{i=1}^{k}y=x_{i}\land nc(\bar{x},y)\right).$

Obviously, this new dependence atom is an extension of the regular one, with
$\operatorname{dep}(\bar{x},\bar{y})\equiv\operatorname{dep}((\bar{x},\bar{x}),(\bar{y},\bar{y}))$.
The atom $\operatorname{ncc}(x_{1}\dots x_{k})$ for non-contextual choice
expresses that one can choose for every assignment $s\in X$ an element
$s(y)\in\\{s(x_{1}),\dots,s(x_{k})\\}$ with the additional constraint that an
element that is selected in an assignment $s$ is also selected in every other
assignment $t$ it which it appears. This explains the name “non-contextual
choice”.

Since these all atoms are obviously in NP and downwards-closed, it follows by
[32] that they are definable in dependence logic. Explicit formulae for them
are given in A.

######  Definition 7.5.

A team $X$ over variables
$\operatorname{Var}_{n}^{e}=\\{m_{1},\dots,m_{n},o_{1},\dots,o_{n}\\}$ (and
the empirical model it represents) is _non-contextual_ if there exists in
every component $i\leq n$ a valuation $v_{i}\colon X(m_{i})\to X(o_{i})$ that
is consistent with the empirical model in the sense that for measurements
$\bar{m}=\bar{a}$ the outcome $\bar{o}=v_{1}(a_{1})\dots v_{n}(a_{n})$ is
possible. Formally, for every $n\in\mathbb{N}$, non-contextuality can be
defined by the formula

$\mathrm{NonContext}^{e}_{n}:=\exists v_{1}\dots v_{n}\left(\bigwedge_{1\leq
i\leq j\leq
n}^{n}\operatorname{dep}((m_{i},m_{j}),(v_{i},v_{j}))\land\bar{m}\bar{v}\subseteq\bar{m}\bar{o}\right).$

The generalized dependence atom ensures that if the same measurement appears
in components $i$ and $j$ then the valuations $v_{i},v_{j}$ agree there.
Notice that $\mathrm{NonContext}^{e}_{n}$ uses both (extended) dependence
atoms and inclusion atoms, so it is a formula of independence logic.

Thus, $X\not\models\mathrm{NonContext}^{e}_{n}$ means that there is no single,
non-contextual assignment of values to all measurements that is consistent
with the empirical model. The term _contextuality_ refers to the fact that in
this situation measurement outcomes are inherently dependent on their
measurement context, i.e. other measurements performed simultaneously. There
is no way to assign values to measurements independent of each other in a
consistent way.

With this formula we can formulate an analogue of the Kochen-Specker Theorem.
Let $e_{i}=(\delta_{i1},\dots,\delta_{i4})\in\\{0,1\\}^{4}$ with
$\delta_{ij}=1$ if, and only if, $i=j$.

######  Theorem 7.6 (Logical formulation of the Kochen-Specker Theorem).

There exists a team $X$ over variables $\\{m_{1},\dots,m_{4}\\}$ such that
every extension $Y$ of $X$ to variables $\\{m_{1},\dots,m_{4},\allowbreak
o_{1},\dots,o_{4}\\}$ which satisfies the constraint that
$Y(\bar{o})\subseteq\\{e_{1},\dots,e_{4}\\}$ violates non-contextuality, i.e.
$Y\not\models\mathrm{NonContext}^{e}_{n}$.

The Kochen-Specker Theorem gives us a class of empirical models which are
necessarily contextual: no non-contextual outcome of measurements is possible,
due to the violation of $\mathrm{NonContext}^{e}_{n}$. Note that the
constraint $Y(\bar{o})\subseteq\\{e_{1},\dots,e_{4}\\}$ corresponds to the
requirement that valuations must respect the algebraic structure of the
measurement operators. This implies that in each ONB the valuations actually
define a choice of one of the basis vectors in the ONB. It is a very
remarkable feature of the theorem that the measurement setup alone, encoded by
$X$, suffices to ensure that all compatible extensions are contextual.

Using our non-contextual choice atom we can give a different team semantical
formulation of the Kochen-Specker Theorem that makes this aspect of choice
more explicit. While the version given above is closer to the rest of our
framework and structurally more similar to the general formulation of the
Kochen-Specker Theorem, the alternative formulation below directly corresponds
to the linear algebraic argument formalized by Lemma 7.3 and is more compact
and elegant.

######  Theorem 7.7.

There is a team $X$ over the variables $\\{m_{1},\dots,m_{4}\\}$ such that
$X\not\models ncc(\bar{m})$. Furthermore, it is possible to choose $X$ with
values in $\mathbb{R}^{4}$ so that for every $s\in X$ the set
$\\{s(m_{1}),\dots,s(m_{4})\\}$ forms an ONB of $\mathbb{R}^{4}$.

######  Proof 7.8.

By Lemma 7.3 we can form the team $X$ consisting of assignments $s_{1},\dots
s_{9}$ with values in $\mathbb{R}^{4}$ such that for each $i\leq 9$, the set
$B_{i}:=\\{s_{i}(m_{1}),\dots,\allowbreak s(m_{4})\\}$ is an ONB, consisting
of four vectors from the collection $Z=\\{a_{1},\dots,a_{18}\\}$ constructed
in the proof of Lemma 7.3. We claim that $X\not\models ncc(\bar{m})$.
Otherwise there exists a choice function $f$ mapping each of the sets
$B_{1},\dots,B_{9}$ to one of its elements such that, whenever $f(B_{i})=a$
and $a\in B_{k}$, then also $f(B_{k})=a$. But this means that the image of $f$
forms a set $S\subseteq Z$ such that $|S\cap X_{i}|=1$ for all $i\leq 9$,
contradicting Lemma 7.3.

Thus, Theorem 7.7 is a team semantical formulation of Lemma 7.3 which readily
implies the Kochen-Specker Theorem.

It is an interesting question, how the treatment of (non-)contextuality via
team semantics can be taken further, to more general scenarios. There is a
vast literature on various contextuality properties, and it is not clear that
the setup of teams as it is chosen here is adequate for more general settings.
The scenarios studied here, sometimes called Bell scenarios, assume different
sets of measurements each of which can be performed independently by some
agent or site. A context is a combined choice of measurements, one by each
agent. We represent this by having for each agent a pair of variables, one of
which evaluates to the choices of measurement, the other to the observed
values.

There are more general scenarios, such as the Specker triangle or the Peres-
Mermin magic square, where certain subsets of measurements can be performed
simultaneously, but not all of them, and there are constraints on the
(Boolean) values that are observed when a possible set of measurement is
performed. Together, these constraints result in an impossibility of a global
Boolean assignment to all measurements. Abramsky and Brandenburger [4] propose
an approach where variables represent the measurements themselves (not the
agents) and the values assigned to these variables correspond the outcomes. A
context is a domain of simultaneously performable measurements (i.e.
variables) and a behaviour in this context is a relational or probabilistic
team on this domain. An empirical model is thus no longer described by a team,
but by a set of teams with different domains, one for each context.
Contextuality is then the question whether there exist a team on the domain of
all variables, whose set of restrictions to the contexts coincides with the
given empirical model. We further refer to [2, 5, 3] for more details and for
connecting these issues to applications in other areas, including logic,
constraint satisfaction problems, databases, etc. It is an interesting
challenge for future research whether logics of dependence and independence
can be sucessfully applied also this more general scenario.

## References

  * [1] S. Abramsky.  Relational Hidden Variables and Non-Locality.  Studia Logica, 101(2):411–452, 2013.  doi:10.1007/s11225-013-9477-4.
  * [2] S. Abramsky.  Contextual semantics: From quantum mechanics to logic, databases, constraints, and complexity, 2014.  arXiv:1406.7386.
  * [3] S. Abramsky and R. Barbosa.  The logic of contextuality.  In 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, pages 5:1–5:18, 2021.  doi:10.4230/LIPIcs.CSL.2021.5.
  * [4] S. Abramsky and A. Brandenburger.  The sheaf-theoretic structure of non-locality and contextuality.  New Journal of Physics, 13, 2011.  doi:10.1088/1367-2630/13/11/113036.
  * [5] S. Abramsky and G. Carú.  Non-locality, contextuality, and valuation algebras: a general theory of disagreement.  Philosophical Transactions of the Royal Society A, 377(2157), 2019\.
  * [6] S. Abramsky, J. Puljujärvi, and J. Väänänen.  Team semantics and independence notions in quantum physics, 2021.  arXiv:2107.10817.
  * [7] J. S. Bell.  On the Einstein Podolsky Rosen paradox.  Physics Physique Fizika, 1(3):195–200, 1964.  doi:10.1103/PhysicsPhysiqueFizika.1.195.
  * [8] J. S. Bell.  On the Problem of Hidden-Variables in Quantum Mechanics.  Reviews of Modern Physics, 1966.  doi:10.1103/RevModPhys.38.447.
  * [9] J. S. Bell.  de Broglie-Bohm, Delayed-Choice, Double-Slit Experiment, and Density Matrix.  International Journal of Quantum Chemistry, 18(S14):155–159, 1980\.  doi:10.1002/qua.560180819.
  * [10] J. S. Bell.  Bertlmann’s Socks and the Nature of Reality.  Journal de Physique Colloques, 42(C2):41–62, 1981.  doi:10.1051/jphyscol:1981202.
  * [11] D. Bohm.  A Suggested Interpretation of the Quantum Theory in Terms of “Hidden” Variables. I.  Physical Review, 85(2):166–179, 1952.  doi:10.1103/PhysRev.85.166.
  * [12] D. Bohm.  A Suggested Interpretation of the Quantum Theory in Terms of “Hidden” Variables. II.  Physical Review, 85(2):180–193, 1952.  doi:10.1103/PhysRev.85.180.
  * [13] A. Brandenburger and N. Yanofsky.  A classification of hidden-variable properties.  Journal of Physics A: Mathematical and Theoretical, 41(42), 2008\.  doi:10.1088/1751-8113/41/42/425302.
  * [14] J. Bub.  Von Neumann’s “No Hidden Variables” Proof: A Re-Appraisal.  Foundations of Physics, 40(9-10):1333–1340, 2010.  doi:10.1007/s10701-010-9480-9.
  * [15] A. Cabello, J. Estebaranz, and G. García-Alcaine.  Bell-Kochen-Specker theorem: A proof with 18 vectors.  Physics Letters A, 212(4):183–187, 1996.  doi:10.1016/0375-9601(96)00134-X.
  * [16] J. Clauser and A. Shimony.  Bell’s Theorem. Experimental tests and implications.  Reports on Progress in Physics, 41(12):1881–1927, 1978.  doi:10.1088/0034-4885/41/12/002.
  * [17] L. de Broglie.  La mécanique ondulatoire et la structure atomique de la matière et du rayonnement.  Journal de Physique et le Radium, 8(5):225–241, 1927.  doi:10.1051/jphysrad:0192700805022500.
  * [18] A. Durand, M. Hannula, J. Kontinen, A. Meier, and J. Virtema.  Probabilistic Team Semantics.  In F. Ferrarotti and S Woltran, editors, Foundations of Information and Knowledge Systems. FoIKS 2018, volume 10833 of Lecture Notes in Computer Science, pages 186–206. Springer International Publishing, 2018.  doi:10.1007/978-3-319-90050-6_11.
  * [19] A. Einstein, B. Podolsky, and N. Rosen.  Can Quantum-Mechanical Description of Physical Reality be Considered Complete?  Physical Review, 47(10):777–780, 1935.  doi:10.1103/PhysRev.47.777.
  * [20] A. Fine.  Joint distributions, quantum correlations, and commuting observables.  Journal of Mathematical Physics, 23(7):1306–1310, 1982.  doi:10.1063/1.525514.
  * [21] P. Galliani.  Inclusion and exclusion in team semantics — On some logics of imperfect information.  Annals of Pure and Applied Logic, 163(1):68–84, 2012.  doi:10.1016/j.apal.2011.08.005.
  * [22] P. Galliani and J. Väänänen.  On Dependence Logic.  In A. Baltag and S. Smets, editors, Johan van Benthem on Logical and Informational Dynamics, volume 5 of Outstanding Contributions to Logic, pages 101–119. Springer, 2014.  doi:10.1007/978-3-319-06025-5_4.
  * [23] D. Geiger, A. Paz, and J. Pearl.  Axioms and algorithms for inferences involving probabilistic independence.  Information and Computation, 91(1):128–141, 1991.  doi:10.1016/0890-5401(91)90077-F.
  * [24] E. Grädel and J. Väänänen.  Dependence and Independence.  Studia Logica, 101(2):399–410, 2013.  doi:10.1007/s11225-013-9479-2.
  * [25] M. Hannula, A. Hirvonen, J. Kontinen, V. Kulikov, and J. Virtema.  Facets of Distribution Identities in Probabilistic Team Semantics.  In F. Calimeri, N. Leone, and M. Manna, editors, Logics in Artificial Intelligence. JELIA 2019, volume 11468 of Lecture Notes in Computer Science, pages 304–320. Springer, 2019.  doi:10.1007/978-3-030-19570-0_20.
  * [26] M. Hannula, J. Kontinen, J. Van den Bussche, and J. Virtema.  Descriptive complexity of real computation and probabilistic independence logic.  In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’20, pages 550–563. Association for Computing Machinery, 2020.  doi:10.1145/3373718.3394773.
  * [27] L. Hardy.  Nonlocality for two particles without inequalities for almost all entangled states.  Physical Review Letters, 71(11):1665–1668, 1993.  doi:10.1103/PhysRevLett.71.1665.
  * [28] C. Held.  The Kochen-Specker Theorem.  In E. Zalta, editor, The Stanford Encyclopedia of Philosophy _(Spring 2018 Edition)_. Metaphysics Research Lab, Stanford University, 2018\.  URL: https://plato.stanford.edu/archives/spr2018/entries/kochen-specker/.
  * [29] W. Hodges.  Compositional semantics for a logic of imperfect information.  Logic Journal of IGPL, 5(4):539–563, 1997.  doi:10.1093/jigpal/5.4.539.
  * [30] J. Jarrett.  On the physical significance of the locality conditions in the bell arguments.  Noûs, 18(4):569–589, 1984.  URL: http://www.jstor.org/stable/2214878.
  * [31] S. Kochen and E. Specker.  The Problem of Hidden Variables in Quantum Mechanics.  Journal of Mathematics and Mechanics, 17(1):59–87, 1967.  URL: https://www.jstor.org/stable/24902153.
  * [32] J. Kontinen and J. Väänänen.  On Definability in Dependence Logic.  Journal of Logic, Language, and Information, 18(3):317–332, 2009\.  doi:10.1007/s10849-009-9082-0.
  * [33] M. Studeny.  Multiinformation and the Problem of Characterization of Conditional Independence Relations.  Problems of Control and Information Theory, 18(1):3–16, 1989.  URL: http://ftp.utia.cas.cz/pub/staff/studeny/multiinformation-PCIT-89.pdf.
  * [34] J. Väänänen.  Dependence Logic: A New Approach to Independence Friendly Logic.  London Mathematical Society Student Texts. Cambridge University Press, 2007.  doi:10.1017/CBO9780511611193.
  * [35] J. von Neumann.  Mathematische Grundlagen der Quantenmechanik.  Springer, 1932.  doi:10.1007/978-3-642-61409-5.
  * [36] M. Wong and C. Butz.  On the Implication Problem for Probabilistic Conditional Independency.  IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 30(6):785–805, 2000.  doi:10.1109/3468.895901.

##  Appendix A Explicit Formulae for Extended Dependence and Non-Contextual
Choice

######  Proposition 13.

The following formula $\psi\in{\rm FO}(\operatorname{dep})$ is equivalent to
the generalized dependence atom
$\operatorname{dep}((\bar{x}_{1},\bar{x}_{2}),(\bar{y}_{1},\bar{y}_{2}))$:

$\displaystyle\psi=$
$\displaystyle\forall\bar{z_{1}}\bar{z_{2}}\forall\bar{w_{1}}\bar{w_{2}}\exists
u_{1}\exists u_{2}\exists
u_{3}\big{(}\bigwedge_{i=1}^{3}\operatorname{dep}(\bar{z_{1}}\bar{z_{2}}\bar{w_{1}}\bar{w_{2}},u_{i})\land\big{[}$
$\displaystyle\phantom{{}\lor{}}\hskip
7.11317pt(u_{1}=u_{2}=u_{3}\land\bar{z_{1}}\bar{w_{1}}\mid\bar{x}_{1}\bar{y}_{1})$
$\displaystyle\lor\hskip 7.11317pt(u_{1}=u_{2}\neq
u_{3}\land\bar{z_{2}}\bar{w_{2}}\mid\bar{x}_{2}\bar{y}_{2})$
$\displaystyle\lor\hskip 7.11317pt(u_{1}\neq
u_{2}=u_{3}\land(\bar{z}_{1}\neq\bar{z}_{2}\lor\bar{w}_{1}=\bar{w}_{2}))\big{]}\big{)}$

######  Proof A.1.

In team semantics, we can compare equality only within an assignment. However,
we need to compare values of $x_{1}y_{1}$ and $x_{2}y_{2}$ across different
tuples $s,t$. We therefore create copies of $\bar{x}_{1}\bar{y}_{1}$ and
$\bar{x}_{2}\bar{y}_{2}$ and regard all possible recombinations:
$\bar{z}_{1}\bar{w}_{1}$ is to be interpreted as copy of
$\bar{x}_{1}\bar{y}_{1}$ and similarly $\bar{z}_{2}\bar{w}_{2}$ as copy of
$\bar{x}_{2}\bar{y}_{2}$. With ‘recombining’ we mean that if $\bar{a}\bar{c}$
appears as value of $s(\bar{x}_{1}\bar{y}_{1})$ and $\bar{b}\bar{d}$ as value
of $t(\bar{x}_{2}\bar{y}_{2})$, we want $\bar{a}\bar{b}\bar{c}\bar{d}$ to
appear as value of $\bar{z}_{1}\bar{z}_{2}\bar{w}_{1}\bar{w}_{2}$ within one
assignment $v$. We can then check whether
$s(\bar{x}_{1})=t(\bar{x}_{2})\rightarrow s(\bar{y}_{1})=t(\bar{y}_{2})$ holds
by checking whether $v(\bar{z}_{1})\neq v(\bar{z}_{2})\lor
v(\bar{w}_{1})=v(\bar{w}_{2})$ – and this is what is done in the third
disjunct.

The role of the $u_{i}$ and the first two disjuncts is to ensure that we only
regard values that are actually taken on by $\bar{x}_{1}\bar{y}_{1}$ and
$\bar{x}_{2}\bar{y}_{2}$ in the third disjunct.

We first extend the team via all possible values of
$\bar{z}_{1},\bar{z}_{2},\bar{w}_{1},\bar{w}_{2}$ using the universal
quantifier. We than add flags $u_{1},u_{2},u_{3}$ to every assignment that are
functionally dependent on $\bar{z}_{1}\bar{z}_{2}\bar{w}_{1}\bar{w}_{2}$. This
ensures that all assignments who agree on these copies share the same flags.
The disjuncts then ensure that all assignments with identical flags must be
assigned to the same disjunct. Therefore, we partition not really our
assignments in the disjunction but rather the values of our copies.

The first disjunct handles all copies where the value of
$\bar{z}_{1}\bar{w}_{1}$ does not in fact appear as value of
$\bar{x}_{1}\bar{y}_{1}$. Similarly, the second disjunct handles all copies
where the value of $\bar{z}_{2}\bar{w}_{2}$ does not appear as value of
$\bar{x}_{2}\bar{y}_{2}$. The elements that cannot be handled in either the
first or the second disjunct are precisely those of interest to us and must
satisfy the $\bar{z}_{1}=\bar{z}_{2}\rightarrow\bar{w}_{1}=\bar{w}_{2}$
condition from the final disjunct. This gives us the semantic of the
generalized dependence atom.

A similar approach works for the atom $\operatorname{nc}(x_{1}\dots x_{k},y)$.
Recall that $X\models\operatorname{nc}(x_{1}\dots x_{k},y)$ if for all $s,t\in
X$ with $t(y)\in\\{s(x_{1}),\dots,s(x_{k})\\}$ it follows that $s(y)=t(y)$.

######  Proposition 14.

The following $\psi\in{\rm FO}(\operatorname{dep})$ is equivalent to
$\operatorname{nc}(x_{1}\dots x_{k},y)$:

$\displaystyle\psi=$ $\displaystyle\forall z_{1}\dots z_{k}\forall
w_{1}w_{2}\exists u_{1}\exists u_{2}\exists
u_{3}\big{(}\bigwedge_{i=1}^{3}\operatorname{dep}(\bar{z}\bar{w},u_{i})\land\big{[}$
$\displaystyle\phantom{{}\lor{}}\hskip
7.11317pt(u_{1}=u_{2}=u_{3}\land\bar{z}w_{1}\mid\bar{x}y)$
$\displaystyle\lor\hskip 7.11317pt(u_{1}=u_{2}\neq u_{3}\land w_{2}\mid y)$
$\displaystyle\lor\hskip 7.11317pt(u_{1}\neq
u_{2}=u_{3}\land(w_{2}=w_{1}\lor\bigvee_{i=1}^{k}w_{2}\neq
z_{i}))\big{]}\big{)}$

The proof is structurally identical to the one above; $\bar{z}w_{1}$ serves as
a copy of $\bar{x}y$ (to simulate $s$) and $w_{2}$ as another copy of $y$ (to
simulate $t$).