capbtabboxtable[][] Phil. Trans. R. Soc. A

Quantum information, quantum foundations, generic inference

Samson Abramsky

# Non-locality, contextuality and valuation algebras: a general theory of
disagreement

Samson Abramsky1 Giovanni Carù1 1Department of Computer Science, University of
Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, U.K.
<EMAIL_ADDRESS>
###### Abstract

We establish a strong link between two apparently unrelated topics: the study
of conflicting information in the formal framework of valuation algebras, and
the phenomena of non-locality and contextuality. In particular, we show that
these peculiar features of quantum theory are mathematically equivalent to a
general notion of _disagreement_ between information sources. This result
vastly generalises previously observed connections between contextuality,
relational databases, constraint satisfaction problems, and logical paradoxes,
and gives further proof that contextual behaviour is not a phenomenon limited
to quantum physics, but pervades various domains of mathematics and computer
science. The connection allows to translate theorems, methods and algorithms
from one field to the other, and paves the way for the application of generic
inference algorithms to study contextuality.

###### keywords:

Contextuality, generic inference, valuation algebras, algorithms

††journal: rsta

##  1 Introduction

Non-locality and contextuality are characteristic features of quantum theory
which have been recently proven to play a crucial role as fundamental
resources for quantum information and computation [1, 2]. In 2011, Abramsky
and Brandenburger introduced an abstract mathematical framework based on sheaf
theory to describe these phenomena in a unified treatment, thereby providing a
common general theory for the study of non-locality and contextuality, which
had been carried out in a rather concrete, example-driven fashion until then
[3]. This high-level description shows that contextuality is not a feature
specific to quantum theory, but rather a general mathematical property. As
such, it can be witnessed in many areas of science, even in domains unrelated
to quantum physics.

Notable examples of the sheaf-theoretic notion of contextuality have been
found in connection with relational database theory [4], robust constraint
satisfaction [5], natural language semantics [6], and logical paradoxes [7, 8,
9]. This profusion of instances motivates the search for a general theory of
_contextual semantics_ , an all-comprehensive approach able to capture the
essence and structure of contextual behaviour. In this paper, we propose such
a general framework, based on the idea of _disagreement_ between information
sources.

The concepts of _querying_ and _combining_ _pieces of information_ are
elegantly captured by the theory of _valuation algebras_ , introduced by
Shenoy in the late 1980s [10, 11]. By constructing a natural definition of
disagreement in this framework, completely independently of quantum theory, we
show that contextuality is a special case of a situation where information
sources agree locally, yet disagree globally. The valuation algebraic
formalism captures an extremely wide range of areas of mathematics and
computer science – including relational databases [12], constraint
satisfaction problems [13], propositional logic [14, 15], and many more –
therefore, not only does the theory developed in this paper naturally
specialise to the aforementioned examples of contextuality outside the quantum
realm, but it allows this phenomenon to be recognized in a much wider range of
fields. The purpose of this paper is to introduce a general vocabulary for
contextual behaviour, which can then be used to translate theorems, methods
and algorithms from one field to the other. The generality of the valuation
algebraic framework makes the scope for potential new results extremely wide,
and lays the foundations for the application of efficient generic inference
algorithms [10, 16, 17, 18, 19, 20] to the problem of detecting contextuality.

##### Other approaches to contextuality

A number of other approaches to developing a general theory of contextuality
have emerged over the past few years [21, 22, 23, 24]; of these, the
Contextuality-by-Default approach [24] also emphasizes applications of
contextuality beyond quantum theory. However, this approach is focussed on
probabilistic models. By encompassing a wider range of models, notably
possibilistic ones, the sheaf-theoretic approach allows a much larger class of
examples to be recognized as exhibiting contextuality.

##### Outline

We begin, in Section 2, by introducing valuation algebras, inference problems,
and a few key examples. In Section 3 we introduce a general definition of
disagreement and discuss many instances of local agreement and global
disagreement. Section 4 reviews the sheaf-theoretic definition of non-locality
and contextuality, and presents the connection with disagreement. In Section
5, we show that, in many relevant valuation algebras, detecting disagreement
is in fact an inference problem, and introduce the concept of complete
disagreement. Section 6 deals with the connection between disagreement and
logical forms of contextuality. Finally, we discuss future research paths in
Section 7.

##  2 Valuation algebras and generic inference

###  2.1 Basic definitions

We begin by reviewing the language of _valuation algebras_. In the simplest
terms, a valuation algebra is a set of pieces of information, or _valuations_
, concerning some variables. Each valuation carries information about a subset
of the variables, called its _domain_. Valuations can be _combined_ together
to obtain joint information, or _projected_ to focus the available information
on specific variables.

######  Definition 2.1.

Let $V$ be a set of variables. We denote by $\mathcal{P}_{\mathsf{fin}}(V)$
the set of finite subsets of $V$. A valuation algebra over $V$ is a set $\Phi$
equipped with three operations:

  1. 1.

Labelling: $d:\Phi\rightarrow\mathcal{P}_{\mathsf{fin}}(V)::\phi\mapsto
d(\phi).$

  2. 2.

Projection:
$\downarrow:\Phi\times\mathcal{P}_{\mathsf{fin}}(V)\rightarrow\Phi::(\phi,S)\mapsto{\phi^{\downarrow
S}}$, for all $S\subseteq d(\phi)$,

  3. 3.

Combination:
$-\otimes-:\Phi\times\Phi\longrightarrow\Phi::(\phi,\psi)\mapsto\phi\otimes\psi,$

such that the following axioms are satisfied:

  1. (A1)

_Commutative Semigroup_ : $(\Phi,\otimes)$ is associative and commutative.

  2. (A2)

_Projection_ : Given $\phi\in\Phi$ and $S\subseteq d(\phi)$,

$d\left({\phi^{\downarrow S}}\right)=S.$

  3. (A3)

_Transitivity_ : Given $\phi\in\Phi$ and $S\subseteq T\subseteq d(\phi)$,

${\left({\phi^{\downarrow T}}\right)^{\downarrow S}}={\phi^{\downarrow S}}.$

  4. (A4)

_Domain_ : Given $\phi\in\Phi$,

${\phi^{\downarrow d(\phi)}}=\phi.$

  5. (A5)

_Labelling_ : For all $\phi,\psi\in\Phi$,

$d(\phi\otimes\psi)=d(\phi)\cup d(\psi)$

  6. (A6)

_Combination_ : For $\phi,\psi\in\Phi$, with $d(\phi)=S$, $d(\psi)=T$ and
$U\subseteq V$ such that $S\subseteq U\subseteq S\cup T$,

${(\phi\otimes\psi)^{\downarrow U}}=\phi\otimes{\psi^{\downarrow U\cap T}}$

The elements of a valuation algebra are called valuations. A set of valuations
is called a knowledgebase. A set of variables $D\subseteq V$ is called a
domain. The domain of a valuation $\phi$ is the set $d(\phi)$.

Intuitively, a valuation $\phi\in\Phi$ represents information about the
possible values of a finite set of variables
$d(\phi)=\\{x_{1},\dots,x_{n}\\}\subseteq V$, which constitutes the domain of
$\phi$. For any set of variables $S\subseteq V$, we denote by
$\Phi_{S}:=\\{\phi\in\Phi\mid d(\phi)=S\\}$ the set of valuations with domain
$S$. Thus, $\Phi=\bigcup_{S\subseteq V}\Phi_{S}$. The projection operation can
be interpreted as the natural process of _focusing_ information over a set of
variables to the subset relevant for a given problem. Combination, on the
other hand, models the way pieces of information can be merged to obtain
knowledge on a larger set of variables. With this interpretation, all of the
axioms above should be intuitively clear.

Besides axioms (A2)–(A6), it is often desirable to add some additional
postulates, which collectively give rise to the notion of _information
algebra_.

######  Definition 2.2.

Let $\Phi$ be a valuation algebra over a set of variables $V$.

  * •

We say that $\Phi$ has neutral elements if it satisfies

    1. (A7)

_Commutative monoid_ : For each $S\subseteq V$, there exists a _neutral
element_ $e_{S}\in\Phi_{S}$ such that

$\phi\otimes e_{S}=e_{S}\otimes\phi=\phi$

for all $\phi\in\Phi_{S}$. Such neutral elements must satisfy the following
identity:

$e_{S}\otimes e_{T}=e_{S\cup T}$

for all subsets $S,T\subseteq V$.

  * •

We say that $\Phi$ has null elements if it satisfies

    1. (A8)

_Nullity_ : For each $S\subseteq V$ there exists a _null element_
$z_{S}\in\Phi_{S}$ such that

$\phi\otimes z_{S}=z_{S}\otimes\phi=z_{S}.$

Moreover, for all $S,T\subseteq V$ such that $S\subseteq T$, we have, for each
$\phi\in\Phi_{T}$,

${\phi^{\downarrow S}}=z_{S}\Longleftrightarrow\phi=z_{T}.$ (1)

  * •

We say that $\Phi$ is idempotent if it satisfies

    1. (A9)

_Idempotency_ : For all $\phi\in\Phi$ and $S\subseteq d(\phi)$, it holds that

$\phi\otimes{\phi^{\downarrow S}}=\phi$

  * •

If $\Phi$ satisfies axioms (A7)–(A9), it is called an information algebra

There are simple intuitions behind these additional axioms. Neutral elements
correspond to ‘useless information’, in the sense that they do not improve any
other information with which they are combined. Null elements, on the other
hand, can be interpreted as destructive information, i.e. knowledge that
corrupts any other valuation to the point of making it useless. Idempotency is
the signature axiom of qualitative or logical, rather than quantitative, e.g.
probabilistic, information. It says that counting _how many times_ we have a
piece of information is irrelevant.

###  2.2 Basic examples

Information appears in many different ways: news, data, statistics,
propositions, etc. The valuation algebraic formalism brings all of these
instances within the scope of a joint theory. In this section, we present a
few examples, which are particularly meaningful for our study.

We begin by introducing the notion of _frame_. Given a variable $x\in V$, the
frame of $x$, denoted by $\Omega_{x}$, is the set of possible values for $x$.
Given a set of variables $S\subseteq V$, we can model the piece of information
constituted by variables in $S$ having acquired specific values in their
respective frames as a tuple $\mathbf{x}\in\Omega_{S}:=\prod_{x\in
S}\Omega_{x}.$ Given a tuple $\mathbf{x}\in\Omega_{S}$ and a subset
$T\subseteq S$, we will denote by $\mathbf{x}_{{}_{\downarrow T}}$ the
cartesian projection of $\mathbf{x}$ onto $\Omega_{T}$.111We have used the
different notation $(\cdot)_{{}_{\downarrow(-)}}$ for the projection of tuples
to distinguish it from the projection ${(\cdot)^{\downarrow(-)}}$ of valuation
algebras.

#### Relational databases

Consider the following data table, taken from [4].

branch-name | account-no | customer-name | balance
---|---|---|---
Cambridge | 10991-06284 | Newton | 2,567.53 GBP
Hanover | 10992-35671 | Leibniz | 11,245.75 EUR
$\dots$ | $\dots$ | $\dots$ | $\dots$

We identify the list of _attributes_ : $V\colonequals\\{\text{branch-name,
account-no, custmer-name, balance}\\}$, which label the columns of the table,
and constitute the variables of the valuation algebra we shall now define.
Each entry of the table is a tuple specifying a value for each of the
attributes. Thus, the full table is a set of tuples, or a _relation_ in
database terminology. A relational database consists of a set of such
relations [25]. Abstracting from this example, given a set of attributes $V$,
we define a relation over a finite subset $S\subseteq V$ as a subset
$R\subseteq\Omega_{S}$. The domain of $R$, often called _schema_ of $R$ in
database theory, is then $d(R)=S$. Combination is given by the _natural join_
: given two relations $R_{1}$ and $R_{2}$ with domain $S$ and $T$
respectively, then

$R_{1}\otimes R_{2}:=R_{1}\Join R_{2}=\\{\mathbf{x}\in\Omega_{S\cup
T}\mid\mathbf{x}_{{}_{\downarrow S}}\in R_{1}\leavevmode\nobreak\
\wedge\leavevmode\nobreak\ \mathbf{x}_{{}_{\downarrow T}}\in R_{2}\\},$

which can be easily shown to be idempotent. Given a relation $R$ with domain
$d(R)=S$, and a subset $T\subseteq S$, we define projection as follows:

${R^{\downarrow T}}:=\\{\mathbf{x}_{{}_{\downarrow T}}\mid\mathbf{x}\in R\\}.$
(2)

For each $S\subseteq V$, we define the neutral element as $e_{S}:=\Omega_{S}$.
On the other hand, the null element is defined as $z_{S}:=\emptyset$. The set
$\Phi\colonequals\bigcup_{S\subseteq
V}\mathcal{P}_{\mathsf{fin}}(\Omega_{S})$, equipped with the operations and
elements above is thus an information algebra.

#### Semiring valuation algebras

Let $\left\langle R,+,\cdot,0,1\right\rangle$ be a commutative semiring and
$V$ a set of variables. A semiring valuation with domain a finite subset
$S\subseteq V$ is a function

$\phi:\Omega_{S}\longrightarrow R.$

Let
$\Phi\colonequals\bigcup_{S\in\mathcal{P}_{\mathsf{fin}}(V)}R^{\Omega_{S}}$ be
the set of all such valuations. We define:

  1. 1.

_Labelling_ : $d:\Phi\rightarrow\mathcal{P}(V)$, with $d(\phi)=S$ if
$\phi\in\Phi_{S}$.

  2. 2.

_Combination_ : $\otimes:\Phi\times\Phi\rightarrow\Phi$, where, for all
$\phi,\psi\in\Phi$ and $\mathbf{x}\in\Omega_{d(\phi)\cup d(\psi)}$, we have

$(\phi\otimes\psi)(\mathbf{x}):=\phi\left(\mathbf{x}_{{}_{\downarrow
d(\phi)}}\right)\cdot\psi\left(\mathbf{x}_{{}_{\downarrow d(\psi)}}\right).$

  3. 3.

_Projection_ : $\downarrow:\Phi\times\mathcal{P}(V)\rightarrow\Phi$, where,
for all $\phi\in\Phi$, $T\subseteq d(\phi)$ and $\mathbf{x}\in\Omega_{T}$, we
have

${\phi^{\downarrow
T}}(\mathbf{x}):=\sum_{{\begin{subarray}{c}\mathbf{y}\in\Omega_{S}:\\\
\mathbf{y}_{{}_{\downarrow T}}=\mathbf{x}\end{subarray}}}\phi(\mathbf{y}).$

This valuation algebra is idempotent only when $R$ is idempotent. The neutral
element $e_{S}\equiv 1$ is the function that assigns $1$ to each
$\mathbf{x}\in\Omega_{S}$. The null element $z_{S}\equiv 0$ is the
$0$-function. Semiring valuations are often referred to as $R$-potentials. In
the case where $R=\mathbb{R}_{\geq 0}$, the corresponding valuation algebra is
the one of _probability potentials_ [20].

###  2.3 Advanced examples: language and models

In many situations, information concerns the validity of propositions
formulated in a logical language $\mathcal{L}$. This idea can be captured in
considerable generality: we suppose $\mathcal{L}$ is simply a set of
_sentences_ concerning a basic set of variables $V$, regardless of its
syntactic structure, and we assume there is a set $\mathbb{M}$ of possible
_models_ for such sentences. Given a subset $Q\subseteq V$, we denote by
$\mathcal{L}_{Q}$ the sublanguage of $\mathcal{L}$ which only involves
variables in $Q$. Similarly, let $\mathbb{M}_{Q}$ be the set of models for
sentences in $\mathcal{L}_{Q}$. For each $Q\subseteq V$ we assume a binary
relation $\models_{Q}\subseteq\mathbb{M}_{Q}\times\mathcal{L}_{Q}$, and we say
that $m\in\mathbb{M}_{Q}$ is a model for $s\in\mathcal{L}_{Q}$ if and only if
$m\models_{Q}s$. We also assume $\mathbb{M}$ to be equipped with a projection
function: for all $Q\subseteq U$,

$\downarrow:\mathbb{M}_{U}\rightarrow\mathbb{M}_{Q}::m\mapsto
m_{{}_{\downarrow Q}}.$

We require this map to behave essentially like cartesian projection
[20].222More precisely, we assume $\mathbb{M}$ to be a _tuple system_ [20],
which is a generalisation of a cartesian product of sets equipped with the
usual cartesian projection. For this reason, the projection of $\mathbb{M}$
will be denoted exactly like cartesian projection. We shall not give a full
list of the axioms of a tuple system as they are not needed in this paper.
This is needed in order to model a situation where an element
$m\in\mathbb{M}_{U}$ is a model for a sentence $s$ in $\mathcal{L}_{Q}$ when
$Q$ is strictly contained in $U$. More specifically, we assume that, for any
$Q\subseteq U$, $m\in\mathbb{M}_{U}$ and $s\in\mathcal{L}_{Q}$,

$m\models_{U}\iota(s)\Leftrightarrow m_{{}_{\downarrow Q}}\models_{Q}s,$

where $\iota:\mathcal{L}_{Q}\hookrightarrow\mathcal{L}_{U}$ is the inclusion
function. This condition states that the projections $\downarrow$ and the
inclusions $\iota$ constitute an _infomorphism_ [20], which is a common aspect
of many instances of language and models, such as propositional and predicate
logic.

The following will be useful for some of the examples in Section 33.2. For all
$Q\subseteq V$ and any $S\subseteq\mathcal{L}_{Q}$, let

$\mathscr{M}_{Q}(S):=\\{m\in\mathbb{M}_{Q}:m\models_{Q}s,\forall s\in S\\}$

denote the set of models for sentences in $S$. Similarly, for all
$M\subseteq\mathbb{M}_{Q}$, let

$\mathscr{T}_{Q}(M):=\\{s\in\mathcal{L}_{Q}:m\models_{Q}s,\forall m\in M\\}.$

be the $Q$-theory of $M$, i.e. the set of sentences in $\mathcal{L}_{Q}$
satisfied by all models in $M$.

With this premise, one can define the valuation algebra of information sets
over the family
$\\{\left\langle\mathcal{L}_{Q},\mathbb{M}_{Q},\models_{Q}\right\rangle\\}_{Q\subseteq
V}$ as follows. The set of variables is $V$, and the elements of the algebra
are sets of models $M\subseteq\mathbb{M}_{Q}$, where $Q\subseteq V$ is finite.
Let
$\Phi\colonequals\bigcup_{Q\in\mathcal{P}_{\mathsf{fin}}(V)}\mathcal{P}(\mathbb{M}_{Q})$.
The operations are

  * •

_Labelling_ : Given an information set $M\subseteq\mathbb{M}_{Q}$, its label
is defined to be $d(M)=Q.$

  * •

_Combination_ : For all $M_{1}\subseteq\mathbb{M}_{Q}$ and
$M_{2}\subseteq\mathbb{M}_{U}$, let

$M_{1}\otimes M_{2}:=M_{1}\Join M_{2}=\\{m\in\mathbb{M}_{Q\cup
U}:m_{{}_{\downarrow Q}}\in M_{1}\wedge m_{{}_{\downarrow U}}\in M_{2}\\}.$

  * •

_Projection_ : Given an information set $M$ and a domain $Q\subseteq d(M)$, we
define

${M^{\downarrow Q}}:=\\{w_{{}_{\downarrow Q}}:w\in M\\}.$

The neutral elements of the algebra are the sets $e_{Q}=\mathbb{M}_{Q}$, while
the null elements are $z_{Q}=\emptyset$. The algebra is clearly idempotent,
hence it is an information algebra.

This general discussion leads to valuation algebraic representations of
propositional logic, predicate logic, linear equation systems, systems of
linear inequalities, any many other examples [26, 20]. One can also show that
the algebra of relational databases is also captured by this general setting.
For the purposes of this paper, we are particularly interested in the
instances of propositional logic and constraint satisfaction problems, which
we shall now briefly review.

#### Propositional logic

Suppose the language $\mathcal{L}$ is propositional logic over a countable set
$P$ of propositional symbols. Sentences are well-formed propositional formulae
with variables in $P$. The models $\mathbb{M}$ are just truth assignments,
i.e. maps $v:P\rightarrow\\{0,1\\}$. Therefore, $\mathbb{M}_{Q}$ is comprised
of assignments $w:Q\rightarrow\\{0,1\\}$, while the relation $\models_{Q}$ is
given by the usual semantics of classical propositional logic. The projection
function of $\mathbb{M}$ is given by function restriction: any assignment
$w:Q\rightarrow\\{0,1\\}$ can be restricted to $w|_{U}:U\rightarrow\\{0,1\\}$
for any $U\subseteq Q$. This allows to define the information algebra of
propositional information sets, where combination of
$M_{1}\subseteq\mathbb{M}_{Q}$ and $M_{2}\subseteq\mathbb{M}_{U}$ is

$M_{1}\otimes M_{2}:=\\{w\in\mathbb{M}_{Q\cup U}:w|_{Q}\in M_{1}\wedge
w|_{U}\in M_{2}\\}.$

while projection of $M\subseteq\mathbb{M}_{Q}$ to a subset $U\subseteq Q$ is
given by ${M^{\downarrow U}}:=\\{w|_{U}:w\in M\\}.$

#### Constraint satisfaction problems

Constraint satisfaction problems (CSP) are particularly useful to model
various kinds of problems in mathematics and computer science thanks to their
general and versatile formulation. A CSP is a triple $\left\langle
X,D,C\right\rangle$, where $X=\\{x_{1},\dots x_{n}\\}$ is a set of _variables_
, $D=\\{D_{1},\dots D_{n}\\}$ is the set of the respective _domains_ 333This
shall not be confused with the term _domain_ of the valuation algebra
formalism. Rather, the domain of a variable in this setting is analogue to the
concept of frame in valuation algebras. of values, and $C=\\{c_{1},\dots
c_{m}\\}$ is a set of _constraints_. Each variable $x_{i}$ can take values in
its domain $D_{i}$. A constraint $c_{i}\in C$ is a pair $\left\langle
T_{i},R_{i}\right\rangle$, where
$T_{i}:=\\{x_{i_{1}},\dots,x_{i_{k}}\\}\subseteq X$ and $R_{i}$ is a $k$-ary
relation $R\subseteq\prod_{j=1}^{k}D_{i_{j}}$. The set $T_{i}$ is also called
the _scheme_ of $c_{i}$, and it is denoted by $\mathsf{scheme}(c_{i})$,
whereas $R_{i}:=\mathsf{rel}(c_{i})$. An _evaluation_ of the variables is a
map $\mathbf{v}:S\longrightarrow\coprod_{x_{i}\in S}D_{i}$ that assigns to
each variable $x_{j}\in S$ a value $v(x_{j})$ in its domain $D_{j}$. Such a
map can be seen as an element of $D_{S}:=\prod_{x_{i}\in S}D_{i}.$ For each
$S\subseteq X$, we define $\mathbb{M}_{S}$ to be the set of all evaluations on
$S$, i.e. $\mathbb{M}_{S}:=D_{S}$. The projection of models is simple
cartesian projection. The associated language $\mathcal{L}_{S}$ is defined by

$\mathcal{L}_{S}:=\\{c_{i}\in C:\mathsf{scheme}(c_{i})\subseteq S\\}.$

We say that an evaluation $\mathbf{v}$ of the variables in $S$ satisfies a
constraint $c=\left\langle T,R\right\rangle$, if $\mathbf{v}_{{}_{\downarrow
S\cap T}}\in R$. An evaluation is called _consistent_ when it does not violate
any constraint. It is called _complete_ if it includes all variables in $X$.
It is called a _solution_ if it is consistent and complete.

Satisfiability of a constraint defines a relation $\models_{S}$ for each
subset $S\subseteq X$: given $\mathbf{v}\in\mathbb{M}_{S}$ and
$c\in\mathcal{L}_{S}$,

$\mathbf{v}\models_{S}c\Longleftrightarrow
S\cap\mathsf{scheme}(c)=\emptyset\text{ or }\mathbf{v}_{{}_{\downarrow
S\cap\mathsf{scheme}(c)}}\in\mathsf{rel}(c).$

Thus we obtain a family
$\\{\left\langle\mathcal{L}_{S},\mathbb{M}_{S},\models_{S}\right\rangle\\}_{S\subseteq
X}$. This allows to define the algebra of information sets, where combination
between $M_{1}\subseteq\mathbb{M}_{S}$ and $M_{2}\subseteq\mathbb{M}_{U}$ is

$M_{1}\otimes M_{2}:=\\{\mathbf{v}\in\mathbb{M}_{Q\cup
U}:\mathbf{v}_{{}_{\downarrow Q}}\in M_{1}\wedge\mathbf{v}_{{}_{\downarrow
U}}\in M_{2}\\},$

while projection of $M\subseteq\mathbb{M}_{Q}$ to a subset $U\subseteq Q$ is
given by ${M^{\downarrow U}}:=\\{\mathbf{v}_{{}_{\downarrow U}}:\mathbf{v}\in
M\\}.$

###  2.4 Inference problems

Since valuations model pieces of information, we are naturally drawn to
formulate the classic problem of extracting relevant knowledge about a given
query from a knowledgebase. In the valuation algebra theory, such a task is
called an _inference problem_ , and is formally defined as follows:

######  Definition 2.3.

Given a valuation algebra $\Phi$, a knowledgebase
$\\{\phi_{1},\dots,\phi_{n}\\}\subseteq\Phi$, and a domain $D\subseteq
d(\phi_{1}\otimes\cdots\otimes\phi_{n})$, we call an inference problem the
task of computing

${\phi^{\downarrow D}}={(\phi_{1}\otimes\dots\otimes\phi_{n})^{\downarrow
D}}.$

The valuation $\phi=(\phi_{1}\otimes\dots\otimes\phi_{n})$ is called joint
valuation or objective function, while $D$ is called a query.

Many natural questions in mathematics and computer science can be easily
reformulated as inference problems. This level of generality has sparked the
development of _generic inference_ [10, 16, 17, 18, 19, 20], a theory that
aims to produce high-level algorithms to solve inference problems, which can
then be applied to a wide range of situations.

##  3 A theory of disagreement

Inference problems capture the essence of information as a carrier of
knowledge used to answer specific questions. However, they do not take into
account another fundamental concept related to knowledge: disagreement. We
will now propose a general, natural definition of disagreement in the
valuation algebraic language. Then, we will show that this notion elegantly
encapsulates non-locality and contextuality.

###  3.1 Defining disagreement

Consider a valuation algebra $\Phi$, on a set of variables $V$. A natural way
to say that two valuations $\phi$ and $\psi$ in $\Phi$ agree is to say that
they provide exactly the same information when restricted to their common
variables. By directly translating this idea in symbols, we say that
$\phi_{i}$ and $\phi_{j}$ agree if

${\phi^{\downarrow d(\phi)\cap d(\psi)}}={\psi^{\downarrow d(\phi)\cap
d(\psi)}}$ (3)

Now, consider a situation where more than two valuations are involved: let
$K=\\{\phi_{1},\dots,\phi_{n}\\}\subseteq\Phi$ be a knowledgebase. One way to
generalise the definition above would be to say that the valuations in $K$
agree if they agree pairwise, a condition which we call local agreement.
However, local agreement might not be enough to indisputably conclude that
$\phi_{1},\dots,\phi_{n}$ agree on everything. Indeed, although the valuations
may provide the same information on _common_ variables, they do not
necessarily share the same _global_ information on _all_ of the variables. For
instance, different people might agree with each other on specific subjects,
while not sharing the same _global_ opinion on _all_ of the subjects. In order
to model these situations, we say that $K$ is a globally agreeing
knowledgebase if $\phi_{i},\dots,\phi_{n}$ share a common global opinion, that
is if there exists a valuation $\gamma\in\Phi_{X}$, where
$X=\bigcup_{i=1}^{n}d(\phi_{i})$, such that

${\gamma^{\downarrow d(\phi_{i})}}=\phi_{i},\leavevmode\nobreak\ \forall 1\leq
i\leq n.$ (4)

Concretely, this means that the information carried by each individual
valuation $\phi_{i}$ comes as a restriction of a ‘truth’ valuation $\gamma$
which is implicitly agreed upon by all the sources. Given this premise, we say
that $\phi_{1},\dots,\phi_{n}$ disagree if such a global valuation $\gamma$
does not exist.

Notice that, as one would expect, global agreement implies local agreement,
indeed, for all $1\leq i,j\leq n$,

${\phi_{i}^{\downarrow d_{i}\cap d_{j}}}\stackrel{{\scriptstyle\eqref{equ:
agreement}}}{{=}}{\left({\gamma^{\downarrow d_{i}}}\right)^{\downarrow
d_{i}\cap
d_{j}}}\stackrel{{\scriptstyle\ref{semigroup}}}{{=}}{\gamma^{\downarrow
d_{i}\cap
d_{j}}}\stackrel{{\scriptstyle\text{(A4)}}}{{=}}{\left({\gamma^{\downarrow
d_{j}}}\right)^{\downarrow d_{i}\cap d_{j}}}\stackrel{{\scriptstyle\eqref{equ:
agreement}}}{{=}}{\phi_{j}^{\downarrow d_{i}\cap d_{j}}}.$

where $d_{i,j}\colonequals d(\phi_{i,j})$.

###  3.2 Local agreement vs global disagreement

Local disagreement is generally easy to spot since it arises as a direct
contradiction between two information sources. A much more subtle scenario
arises when sources agree locally, yet disagree globally. In this section, we
present some interesting real-world examples of this kind of disagreement
using different valuation algebras.

######  Example 3.1.

Our first example is inspired by a recent paper by Zadrozny & Garbayo [27],
where breast cancer screening guidelines from three different accredited
sources are analysed. The following protocols are obtained by slightly
tweaking the instruction contained therein.

  1. 1.

_Screening with mammography annually, clinical breast exam annually or
biannually_

  2. 2.

_Women aged 50 to 54 years should get mammograms. Women aged 55 years and
older should switch to clinical breast exams_

  3. 3.

_Women aged 50 to 54 years should undergo an exam every year. Women aged 55
years and older should be examined every 2 years_

We can represent the information provided by these medical bodies as a
knowledgebase of the information algebra of relational databases. We have the
variables $\\{a,e,f\\}$ representing age intervals, exam type and exam
frequency respectively. The frames for each variable are
$\Omega_{a}=\\{54^{-},54^{+}\\}$, $\Omega_{e}=\\{\text{MG},\text{CBE}\\}$,
$\Omega_{f}=\\{\text{Y},\text{2Y}\\}$. Each source $i=1,2,3$ from the example
can be described by 3 relations, defined by

$\begin{split}R_{1}&=\left\\{\left\langle\text{M},\text{Y}\right\rangle,\left\langle\text{CBE},\text{Y}\right\rangle,\left\langle\text{CBE},\text{2Y}\right\rangle\right\\},\\\
R_{2}&=\left\\{\left\langle 54^{-},\text{M}\right\rangle,\left\langle
54^{+},\text{CBE}\right\rangle\right\\},\\\ R_{3}&=\left\\{\left\langle
54^{-},\text{Y}\right\rangle,\left\langle
54^{+},\text{2Y}\right\rangle\right\\},\end{split}$

with $d(R_{1})=\\{e,f\\}$, $d(R_{2})=\\{a,e\\}$ and $d(R_{3})=\\{a,f\\}$. It
is easy to see that all these sources agree locally, i.e. they do not directly
contradict each other. For instance,
${R_{1}^{\downarrow\\{e\\}}}=\\{\text{M},\text{CBE}\\}={R_{2}^{\downarrow\\{e\\}}}$.
However, we can show that they disagree globally. To see this, we combine
$R_{1},R_{2},R_{3}$:

$G:=R_{1}\otimes R_{2}\otimes
R_{3}=\left\\{\left\langle\text{M},\text{Y},54^{-}\right\rangle,\left\langle\text{CBE},\text{2Y},54^{+}\right\rangle\right\\}.$

Later, in Proposition 5.1, we will show that if a truth valuation exists, then
$G$ is one of them. Now, if we project $G$ back onto $d(R_{1})$, we have

${G^{\downarrow
d(R_{1})}}=\\{\left\langle\text{M},\text{Y}\right\rangle,\left\langle\text{CBE},\text{2Y}\right\rangle\\},$

which is different from $R_{1}$, since ${G^{\downarrow d(R_{1})}}$ does not
include $\left\langle\text{CBE},\text{Y}\right\rangle$. We conclude that a
truth valuation does not exist, and thus $R_{1},R_{2},R_{3}$ disagree
globally, despite satisfying local agreement. This means that it is impossible
to follow all the guidelines simultaneously. More specifically, since
$\left\langle\text{CBE},\text{Y}\right\rangle\notin{G^{\downarrow d(R_{1})}}$,
it is impossible to follow both guidelines 2 and 3, if one opts to undergo
clinical breast exams annually, as suggested by 1. This is a very simple
example of a real situation where information sources disagree in a very
subtle way. It is also an example of a database which does not admit a
universal relation, a property that has been proved to be equivalent to
contextuality in [4].

######  Example 3.2.

Consider the following problem. We want to colour a political map of the
geographical region surrounding Malawi using 3 colours – say red, green and
yellow – with the condition that adjacent countries should be coloured
differently. A blank map is pictured in Figure 2.

Figure 1: A blank map of the geographical region surrounding Malawi.

Figure 2: The constraint graph of the CSP. A $4$-colouring of the graph is
shown. The chromatic number of the graph is $4$.

We can model this problem as a CSP. The set of variables $V$ is constituted by
a variable for each of the 5 countries in the map, i.e.
$V=\\{\mathsf{MOZ},\mathsf{MWI},\mathsf{TZA},\mathsf{ZMB},\mathsf{ZWE}\\}$ The
domain for each variable is the set of colours we can attribute to the
country, i.e. $D=\\{g,r,y\\}$, and it is the same for each variable. Let
$S:=\\{\left\langle g,r\right\rangle,\left\langle
g,y\right\rangle,\left\langle r,y\right\rangle\\}.$ There are $8$ constraints
$c_{i}$, $1\leq i\leq 8$ defined by $\mathsf{rel}(c_{i})=S$ for all $1\leq
i\leq 8$ and

$\displaystyle
T_{1}=\\{\mathsf{MOZ},\mathsf{MWI}\\},T_{2}=\\{\mathsf{MOZ},\mathsf{TZA}\\},T_{3}=\\{\mathsf{MOZ},\mathsf{ZMB}\\},T_{4}=\\{\mathsf{MOZ},\mathsf{ZWE}\\},$
$\displaystyle
T_{5}=\\{\mathsf{MWI},\mathsf{TZA}\\},T_{6}=\\{\mathsf{MWI},\mathsf{ZWE}\\},T_{7}=\\{\mathsf{TZA},\mathsf{ZMB}\\},T_{8}=\\{\mathsf{ZMB},\mathsf{ZWE}\\},$

where $T_{i}=\mathsf{scheme}(c_{i})$ for all $1\leq i\leq 8$. Consider the
valuation algebra of information sets for CSPs. The knowledgebase for this
problem is comprised of $8$ valuations $\\{\phi_{i}\\}_{i=1}^{8}$ defined by

$\displaystyle\phi_{i}:=\mathcal{M}_{T_{i}}(C)=\\{\mathbf{v}\in
D_{T_{i}}:\mathbf{v}\models_{T_{i}}c_{j},\leavevmode\nobreak\ \forall 1\leq
j\leq 8\\}.$

For instance,
$\phi_{1}=\\{\left\langle\mathsf{MOZ},\mathsf{MWI}\right\rangle\mapsto\left\langle
g,r\right\rangle,\text{ or }\left\langle g,y\right\rangle,\text{ or
}\left\langle r,y\right\rangle\\}.$ It is easy to see that all the valuations
agree locally, indeed, for all $1\leq i,j\leq 8$, we either have $T_{i}\cap
T_{j}=\emptyset$, in which case local agreement is trivially satisfied, or
$T_{i}\cap T_{j}$ has exactly one element $t$, and we have

${\phi_{i}^{\downarrow T_{i}\cap T_{j}}}=\\{t\mapsto g\text{ or }r\text{ or
}y\\}={\phi_{j}^{\downarrow T_{i}\cap T_{j}}}.$

However, the $\phi_{i}$’s disagree globally. Indeed, if there was a valuation
$\gamma$ which projects onto each $\phi_{i}$, it would imply that there is a
solution to the CSP, and thus a colouring of the map using only three colours.
It is easy to see that this is not the case by simply looking at the
_constraint graph_ (cf. Figure 2) of the problem, and conclude that its
chromatic number is $4$.

######  Example 3.3.

To cite an example from logic, consider the the famous liar’s paradox, whose
structure has been linked to contextuality in [7]. The standard paradox
consists of the sentence:

$S:S\text{ is false}.$

We can generalise this to a _liar cycle_ of length $n$, i.e. a sequence of
statements:

$S_{1}:S_{2}\text{ is true},\quad\quad S_{2}:S_{3}\text{ is
true},\quad\quad\dots\quad\quad S_{n-1}:S_{n}\text{ is true},\quad\quad
S_{n}:S_{1}\text{ is false}.$

These statements can be modelled as a series of formulae in propositional
logic. Let $V:=\\{s_{1},\dots,s_{n}\\}$ be a set of variables, each
representing one of the statements $S_{i}$ above. The $n$ liar cycle can be
rewritten as follows:

$s_{1}\leftrightarrow s_{2},\quad\quad s_{2}\leftrightarrow
s_{3},\quad\quad\dots\quad\quad s_{n-1}\leftrightarrow s_{n},\quad\quad
s_{n}\leftrightarrow\neg s_{1}.$ (5)

We define the following valuations:

$\phi_{n}:=\mathcal{M}_{\\{s_{1},s_{n}\\}}(\\{s_{n}\leftrightarrow\neg
s_{1}\\})=\\{\mathbf{v}::\left\langle
s_{1},s_{n}\right\rangle\mapsto\left\langle 1,0\right\rangle\text{ or
}\left\langle 0,1\right\rangle\\},$

and for all $1\leq i\leq n-1$,

$\phi_{i}:=\mathcal{M}_{\\{s_{i},s_{i+1}\\}}(\\{s_{i}\leftrightarrow
s_{i+1}\\})=\\{\mathbf{v}::\left\langle
s_{i},s_{i+1}\right\rangle\mapsto\left\langle 0,0\right\rangle\text{ or
}\left\langle 1,1\right\rangle\\}.$

It is easy to see that the $\phi_{i}$’s agree locally. Indeed, both $0$ and
$1$ are valid assignments for a single variable, which is the most two
valuations can have in common. On the other hand, the fact that the liar cycle
gives rise to a paradox means that the valuations do not agree globally.
Indeed, a global assignment of truth values to each $s_{1},\dots,s_{n}$
consistent with formulae (5) is impossible, as they collectively yield
$s_{1}\leftrightarrow\neg s_{1}$.

##  4 Non-locality and contextuality

We shall now expose a surprising connection between the valuation algebraic
theory of disagreement with a completely different topic, namely the study of
non-locality and contextuality in quantum foundations. This will show that all
of the examples of local agreement vs global disagreement we have just
presented are in fact mathematically equivalent to contextuality. We will
adopt the sheaf-theoretic description of contextuality developed in [3]. We
will now review the main definition, assuming basic knowledge of sheaf theory
and category theory.

###  4.1 The sheaf-theoretic structure of non-locality and contextuality

Our starting point is a simple idealised experiment, depicted in Figure 4.

Figure 3: A schematic representation of the experiment.

$A$ | $B$ | $(0,0)$ | $(1,0)$ | $(0,1)$ | $(1,1)$
---|---|---|---|---|---
$a_{1}$ | $b_{1}$ | $\nicefrac{{1}}{{2}}$ | $0$ | $0$ | $\nicefrac{{1}}{{2}}$
$a_{1}$ | $b_{2}$ | $\nicefrac{{3}}{{8}}$ | $\nicefrac{{1}}{{8}}$ | $\nicefrac{{1}}{{8}}$ | $\nicefrac{{3}}{{8}}$
$a_{2}$ | $b_{1}$ | $\nicefrac{{3}}{{8}}$ | $\nicefrac{{1}}{{8}}$ | $\nicefrac{{1}}{{8}}$ | $\nicefrac{{3}}{{8}}$
$a_{2}$ | $b_{2}$ | $\nicefrac{{1}}{{8}}$ | $\nicefrac{{3}}{{8}}$ | $\nicefrac{{3}}{{8}}$ | $\nicefrac{{1}}{{8}}$

Figure 4: Bell’s empirical model

Suppose there are two agents, Alice and Bob, who can each independently select
one of two different measurements to perform on their respective share of a
given system: $a_{1},a_{2}$ for Alice, $b_{1},b_{2}$ for Bob. After a
measurement is performed, one of two possible outcomes, $0$ or $1$, is
observed. Note that only one measurement per party can be chosen at a time, so
that there are four possible sets of jointly performable measurements, or
_contexts_ : $\\{a_{1},b_{1}\\}$, $\\{a_{1},b_{2}\\}$, $\\{a_{2},b_{1}\\}$,
$\\{a_{2},b_{2}\\}$. When a context is chosen, and measurement outcomes
$o_{A},o_{B}\in\\{0,1\\}$ are observed, the corresponding _event_ can be
modelled as a tuple $\mathbf{e}=\left\langle o_{A},o_{B}\right\rangle\in
O\times O$, where $O\colonequals\\{0,1\\}$ is the _set of outcomes_. Repeated
runs of the experiment allow relative frequencies to be tabulated, which can
be described as a family of probability distributions
$e_{C}:\mathcal{E}(C)\rightarrow\mathbb{R}_{\geq 0}$ over the events
$\mathcal{E}(C)\colonequals\prod_{m\in C}O$ of each context
$C=\\{a_{i},b_{j}\\}$. We shall call such a family an _empirical model_. A key
example of an empirical model is Bell’s model [28, 29, 30], which is displayed
in Table 4. The probability distributions observed in Bell’s model are the
ones predicted by quantum theory in a particular experiment [29]. As such,
they verify the _no-signalling_ or _no-disturbance condition_ , a property of
all distributions arising from quantum experiments, which states that the
statistics observed by one party do not depend on the other party’s choice of
measurement. In essence, this means that the marginals of the distributions at
each context agree at their intersection.

The key feature of Bell’s model is that it is _contextual_ or, more precisely,
_non-local_. While non-locality was originally formulated in terms of the non-
existence of a local hidden-variable theory, it was observed originally by
Fine [31], and subsequently shown in a much more general form in [3], that
this is equivalently formulated as the impossibility of finding a global
probability distribution $d:\mathcal{E}(X)\rightarrow\mathbb{R}_{\geq 0}$ such
that each empirically observed distribution $e_{C}$ corresponds to the
marginal of $d$ with respect to the events in $C$. Hence, the properties of
the system we are measuring are not predetermined, but rather depend on the
measurements we choose to perform. This phenomenon cannot be witnessed in
classical physics, and constitutes one of the most peculiar features of
quantum theory.

By abstracting from this particular example, one can formulate an extremely
general definition of non-locality and contextuality using sheaf theory. We
begin by defining a general measurement scenario as a triple $\left\langle
X,\mathcal{M},(O_{m})_{m\in X}\right\rangle$, where $X$ is a finite set of
measurement labels, $\mathcal{M}\subseteq\mathcal{P}(X)$ is a measurement
cover, i.e. the collection of contexts, and $O_{m}$ is the set of outcomes for
measurement $m\in X$. For instance, the scenario above has
$X=\\{a_{1},b_{1},a_{2},b_{2}\\}$,
$\mathcal{M}=\\{\\{a_{i},b_{j}\\}:i,j=1,2\\}$ and $O_{m}=O=\\{0,1\\}$ for all
$m\in X$. This is the canonical example of a so-called Bell-type scenario,
which is a class of scenarios involving several experimenters, who can each
choose to perform one measurement at a time. In a Bell-type scenario with $n$
parties, $X$ can be partitioned into $n$ subsets $X_{1},\dots,X_{n}$, where
$X_{i}$ represents the measurements available to the $i$-th party, and the
contexts are of the form $\mathcal{M}=\\{\\{m_{1},\dots,m_{n}\\}:m_{i}\in
X_{i},\leavevmode\nobreak\ \forall 1\leq i\leq n\\}$.

The events of a scenario are defined by the sheaf of events
$\mathcal{E}:\mathcal{P}(X)^{op}\rightarrow\textbf{Set}$, where we have
$\mathcal{E}(U)\colonequals\prod_{m\in U}O_{m}$ for all $U\subseteq
U^{\prime}$, and the restriction maps are given by cartesian projection: for
all $U\subseteq U^{\prime}\subseteq X$,

$\mathcal{E}(U\subseteq
U^{\prime})\colonequals\rho_{U}^{U^{\prime}}:\mathcal{E}(U^{\prime})\longrightarrow\mathcal{E}(U)::\mathbf{x}\longmapsto\mathbf{x}|_{U}\colonequals\mathbf{x}_{{}_{\downarrow
U}}.$

It is easy to verify that $\mathcal{E}$ is indeed a sheaf.

Now that we have abstracted the concept of measurement scenario, we want to
formally capture empirical models. In order to describe probability
distributions in the most general sense, we will consider distributions over
any semiring. Given a semiring $R$, we define the $R$-distribution functor
$\mathcal{D}_{R}:\textbf{Set}\rightarrow\textbf{Set}$ as follows: for any set
$A$ and any function $f:A\rightarrow B$,

$\begin{split}\mathcal{D}_{R}(S)&\colonequals\left\\{d:S\rightarrow
R:|\mathsf{supp}(d)|<\infty\text{ and }\sum_{s\in S}d(s)=1\right\\}\\\
\mathcal{D}_{R}(f)&:\mathcal{D}_{R}(A)\longrightarrow\mathcal{D}_{R}(B)::d\longmapsto\lambda
b.\sum_{\begin{subarray}{c}a\in A:\\\ f(a)=b\end{subarray}}d(a).\end{split}$

With this premise, distributions over events of $\left\langle
X,\mathcal{M},(O_{m})\right\rangle$ can be modelled by the presheaf
$\mathcal{D}_{R}\mathcal{E}\colonequals\mathcal{D}_{R}\circ\mathcal{E}:\mathcal{P}(X)^{op}\rightarrow\textbf{Set}$.
Therefore, an empirical model will be comprised of a family
$\\{e_{C}\in\mathcal{D}_{R}(C)\\}_{C\in\mathcal{M}}$ of local sections of
$\mathcal{D}_{R}\mathcal{E}$. In order to capture the property of no-
signalling, we require the family $\\{e_{C}\\}_{C\in\mathcal{M}}$ to be
compatible,444The concept of _compatibility_ introduced here shall not be
confused with the notion of _compatible measurements_ of quantum theory, which
describes jointly-performable measurements. i.e. such that $e_{C}|_{C\cap
C^{\prime}}=e_{C^{\prime}}|_{C\cap C^{\prime}}$ for all
$C,C^{\prime}\in\mathcal{M}$. In other words, for any event
$\mathbf{s}\in\mathcal{E}(C\cap C^{\prime})$, we have:

$e_{C}|_{C\cap
C^{\prime}}(\mathbf{s})=\sum_{\begin{subarray}{c}\mathbf{x}\in\mathcal{E}(C):\\\
\mathbf{x}|_{C\cap
C^{\prime}}=\mathbf{s}\end{subarray}}e_{C}(\mathbf{x})=\sum_{\begin{subarray}{c}\mathbf{y}\in\mathcal{E}(C^{\prime}):\\\
\mathbf{y}|_{C\cap
C^{\prime}}=\mathbf{s}\end{subarray}}e_{C}(\mathbf{y})=e_{C^{\prime}}|_{C\cap
C^{\prime}}(\mathbf{s}),$

which corresponds precisely to the property of no-signalling.

Different semirings describe different kinds of empirical models. When
$R=\mathbb{R}_{\geq 0}$ we say that the model is probabilistic; when
$R=\mathbb{B}$, it is possibilistic, which means that we are only concerned
with whether events are possible or not, regardless of their probability of
occurring. Notice that, by disregarding the value of individual probabilities,
every probabilistic empirical model $\\{e_{C}\in\mathcal{D}_{\mathbb{R}_{\geq
0}}\mathcal{E}(C)\\}_{C\in\mathcal{M}}$ gives rise to a possibilistic model
$\\{\tilde{e}_{C}\in\mathcal{D}_{\mathbb{B}}\mathcal{E}(C)\\}_{C\in\mathcal{M}}$,
where
$\tilde{e}_{C}\colonequals\chi_{\mathsf{supp}(e_{C})}:\mathcal{E}(C)\rightarrow\\{0,1\\}$
is the characteristic function of the support of the distribution $e_{C}$.

We say that an empirical model $\\{e_{C}\\}_{C\in\mathcal{M}}$ is contextual
if there is no global section for the family $\\{e_{C}\\}_{C\in\mathcal{M}}$,
that is, if there is no global distribution $d:\mathcal{E}(X)\rightarrow R$
such that $d|_{C}=e_{C}$ for all $C\in\mathcal{M}$. If the scenario is Bell-
type, then we say that the model is non-local.555Note that the term _local_
reviewed here has a completely different meaning to the one introduced earlier
in the notion of _local agreement_ Hence, non-locality is simply a special
case of contextuality.

If an empirical model is possibilistic, we say that it is logically
contextual. By extension, we say that a probabilistic model
$\\{e_{C}\\}_{C\in\mathcal{M}}$ is logically contextual if its possibilistic
collapse $\\{\tilde{e}_{C}\\}_{C\in\mathcal{M}}$ is logically contextual. It
can be shown that this property is strictly stronger than regular
(probabilistic) contextuality.

An even more restrictive kind of contextuality arises in some models. Suppose
we have a global section for a possibilistic model
$\\{e_{C}\\}_{C\in\mathcal{M}}$, i.e. a distribution
$d:\mathcal{E}(X)\rightarrow\mathbb{B}$ such that $d|_{C}=e_{C}$ for all
$C\in\mathcal{M}$. The support of $d$ is a set of global events
$\mathbf{g}\in\mathcal{E}(X)$ which are compatible with the model, i.e. such
that $e_{C}(\mathbf{g}_{{}_{\downarrow C}})=1$ for all $C\in\mathcal{M}$. In
extreme situations, not only it might not be possible to find such a global
distribution $d$, but there might not even be any global event $\mathbf{g}$
compatible with the model at all. This property is called strong
contextuality, and it is strictly stronger than logical contextuality. This
leads to the following hierarchy of different strengths of contextuality:

$\text{(probabilistic) contextuality}\leavevmode\nobreak\ \leavevmode\nobreak\
<\leavevmode\nobreak\ \leavevmode\nobreak\ \text{logical
contextuality}\leavevmode\nobreak\ \leavevmode\nobreak\ <\leavevmode\nobreak\
\leavevmode\nobreak\ \text{strong contextuality}.$ (6)

Typical quantum examples of each of these levels are Bell’s model
(probabilistic), Hardy’s model [32, 33] (logical) and the Greenberger-Horne-
Zeilinger (GHZ) model [34, 35] (strong).

###  4.2 Valuation algebras and sheaf theory

Remarkably, many of the properties of valuation algebras can also be
effectively captured by sheaf theory. Just like presheaves deal with the
restriction and localisation of topological structures and their extendability
through a ‘gluing’ process, valuation algebras model the focus of knowledge
and information, and represent the natural framework to study how local
information can be extended through a ‘combination’ process.

Let $\Phi$ be a valuation algebra on a set of variables $V$. We define a
functor

$\Phi:\mathcal{P}(V)^{op}\longrightarrow\textbf{Set},$ (7)

where $\Phi(S):=\Phi_{S}$ for all $S\subseteq V$, and restriction maps are
given by the projector operator: for all $S\subseteq T\subseteq V$, we have

$\Phi(S\subseteq
T)=\rho_{S}^{T}:\Phi_{T}\longrightarrow\Phi_{S}::\phi\longmapsto{\phi^{\downarrow
T}}.$

We can easily check that $\Phi$ is a functor. Indeed, by (A2), we have, for
all $S\subseteq V$ and for all $\phi\in\Phi_{S}$,

$\rho_{S}^{S}(\phi)={\phi^{\downarrow S}}={\phi^{\downarrow
d(\phi)}}\stackrel{{\scriptstyle\ref{projection}}}{{=}}\phi,$

and, by (A3), for all $S\subseteq T\subseteq U\subseteq V$ and
$\phi\in\Phi_{U}$,

$\rho_{S}^{T}\circ\rho_{T}^{U}(\phi)={\left({\phi^{\downarrow
T}}\right)^{\downarrow
S}}\stackrel{{\scriptstyle\ref{transitivity}}}{{=}}{\phi^{\downarrow
S}}=\rho_{S}^{U}(\phi).$

This sheaf-theoretic perspective allows to capture the restriction or
localisation of the information carried by a valuation algebra.

It is important to keep in mind that the presheaf description of a valuation
algebra only accounts for the restriction process. The combination operation
is unique to each valuation algebra, although there are some general
constructions, as we shall see later on in Section 55.2.

With this premise, it is easy to convert the definitions of local and global
agreement in sheaf-theoretic terms. A locally agreeing knowledgebase
$K=\\{\phi_{1},\dots,\phi_{n}\\}$ is nothing but a compatible family of local
sections of $\Phi$. On the other hand, $K$ agrees globally if and only if
there is a global section for $K$.

###  4.3 Contextuality and disagreement

It is now time to reveal the link between contextuality and disagreement
underpinning the theory presented thus far. We have purposely kept the
connection implicit until now, so as to show how the theory of disagreement
can be developed completely independently of the concept of contextuality.

#### No-signalling and local agreement.

Let $e=\\{e_{C}\in\mathcal{D}_{R}\mathcal{E}(C)\\}_{C\in\mathcal{M}}$ be an
empirical model over a measurement scenario $\left\langle
X,\mathcal{M},(O_{m})\right\rangle$. Let us take $X$ as a set of variables on
which to build a suitable valuation algebra. for each measurement $m\in X$, we
let $\Omega_{m}\colonequals O_{m}$, so that $\Omega_{C}=\mathcal{E}(C)$ for
any context $C\in\mathcal{M}$.

We can interpret each $e_{C}$ as a valuation of the algebra $\Phi$ of
$R$-potentials. From this viewpoint, the empirical model $e$ is nothing but a
knowledgebase of $\Phi$. Then, the property of no-signalling – i.e. the
compatibility of $\\{e_{C}\\}_{C\in\mathcal{M}}$ – corresponds precisely to
local agreement. Hence, to summarise, one can think of an empirical model as a
locally agreeing knowledgebase of $\Phi$.

#### Contextuality and global disagreement.

By considering no-signalling empirical models as locally agreeing
knowledgebases of the algebra of $R$-potentials, a striking connection with
the theory of disagreement arises: non-locality and contextuality are just
special instances of a locally agreeing knowledgebase which disagrees
globally:

######  Theorem 4.1 (See A for the proof).

Let $e=\\{e_{C}\\}_{C\in\mathcal{M}}$ be an empirical model. Then $e$ is
contextual if and only if the locally-agreeing knowledgebase
$K=\\{e_{C}\\}_{C\in\mathcal{M}}\subseteq\Phi$ disagrees globally.

Therefore, from a structural perspective, these counterintuitive phenomena of
quantum physics are exhibiting exactly the same kind of behaviour as the
examples introduced in Section 3, and, indeed, as any instance of local
agreement vs global disagreement arising from the valuation algebra framework.
This result is a major generalisation of the connections observed in [4], [5],
and [7] which are limited to relational databases, CSPs, and logical paradoxes
respectively. It further proves that contextuality is not a phenomenon limited
to quantum physics, but it is a general concept which pervades various
domains, most of which are completely unrelated to quantum theory.

This connection can be further explored to include all the levels of strength
of contextuality presented in (6), as we shall see in Section 6. Moreover, it
paves the way for the application of methods of generic inference to the study
of contextuality via the reformulation of the problem of detecting
contextuality as an inference problem, which is also presented in Section 6.

##  5 Disagreement, complete disagreement and inference problems

Studying global disagreement amounts to looking for a global truth, which is
shared by all the sources of information. It is thus natural to ask whether it
is possible to recover it from the collective information of the sources and
the structure of the valuation algebra. It turns out that, in a variety of
situations, the global truth valuation can appear only in one form, which
makes the problem of finding it significantly easier and, crucially,
equivalent to an inference problem. In order to prove this, we will need to
introduce the concept of an _ordered valuation algebra_.

###  5.1 Ordered valuation algebras

Given a valuation algebra $\Phi$ on a set of variables $V$, and two valuations
$\phi,\psi\in\Phi_{S}$ for some $S\subseteq V$, one could raise the following
question: _how does the information carried by $\phi$ compare to the one
carried by $\psi$?_ _Is there a way of quantifying the amount of information
represented by a valuation?_ The answer to this question is given by extending
the present framework to the one of _ordered valuation algebras_ [36]. An
ordered valuation algebra is a valuation algebra equipped with a completeness
relation $\preceq$, which aims to capture how informative a valuation is with
respect to others.

######  Definition 5.1.

Let $\Phi$ be a valuation algebra with null elements on a set of variables
$V$. Then, $\Phi$ is an ordered valuation algebra if there exists a partial
order $\preceq$ on $\Phi$ such that the following additional axioms are
verified:

  * (A10)

_Partial order_ : For all $\phi,\psi\in\Phi$, $\phi\preceq\psi$ implies
$d(\phi)=d(\psi)$. Moreover, for every $S\subseteq V$ and
$\Psi\subseteq\Phi_{S}$, the infimum $\inf(\Psi)$ exists.

  * (A11)

_Null element_ : For all $S\subseteq V$, we have $\inf(\Phi_{S})=z_{S}.$

  * (A12)

_Monotonicity of combination_ : For all
$\phi_{1},\phi_{2},\psi_{1},\psi_{2}\in\Phi$ such that
$\phi_{1}\preceq\phi_{2}$ and $\psi_{1}\preceq\psi_{2}$ we have
$\phi_{1}\otimes\psi_{1}\preceq\phi_{2}\otimes\psi_{2}.$

  * (A13)

_Monotonicity of projection_ : For all $\phi,\psi\in\Phi$, if
$\phi\preceq\psi$ then ${\phi^{\downarrow S}}\preceq{\psi^{\downarrow S}},$
for all $S\subseteq d(\phi)=d(\psi)$.

It can be shown that all the instances of valuation algebras presented in the
previous sections can be ordered. For instance, the algebra of relational
databases has an order structure simply given by inclusions. We can
incorporate some of the axioms in the structure of the presheaf (7) by simply
rewriting it as $\Phi:\mathcal{P}(V)^{op}\longrightarrow\textbf{Pos}$, where
Pos denotes the category of posets and monotone maps.

###  5.2 A general construction for composition

An interesting aspect brought to light by the order structure of valuation
algebras is that the composition laws of many algebras are uniquely
characterised by the same categorical construction.

Let $\Phi$ be an ordered valuation prealgebra, viewed as a presheaf. Thanks to
the universal property of products of the category Set, we have, for all
$S,T\subseteq V$, the following diagram:

${\Phi(S)}$${\Phi(S)\times\Phi(T)}$${\Phi(T)}$${\Phi(S\cup
T)}$$\pi_{1}$$\pi_{2}$$\rho_{S}^{S\cup T}$$\rho_{T}^{S\cup
T}$$\begin{subarray}{c}\left\langle\rho_{S}^{S\cup T},\rho_{T}^{S\cup
T}\right\rangle\\\ \leavevmode\nobreak\ \leavevmode\nobreak\ \\\
\leavevmode\nobreak\ \leavevmode\nobreak\ \\\ \leavevmode\nobreak\
\leavevmode\nobreak\ \\\ \leavevmode\nobreak\ \leavevmode\nobreak\ \\\
\leavevmode\nobreak\ \leavevmode\nobreak\ \\\ \leavevmode\nobreak\
\leavevmode\nobreak\ \\\ \leavevmode\nobreak\ \leavevmode\nobreak\
\end{subarray}$

This leads to the following definition: an adjoint valuation algebra is an
ordered valuation algebra $\Phi$ such that its combination operation $\otimes$
is the right adjoint of the map $\left\langle\rho_{S}^{S\cup
T},\rho_{T}^{S\cup T}\right\rangle$, defined in the diagram above. In this
case, $\otimes$ is the unique map such that

$\mathsf{id}_{\Phi(S\cup T)}\leq\otimes\circ\left\langle\rho_{S}^{S\cup
T},\rho_{T}^{S\cup T}\right\rangle,\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \left\langle\rho_{S}^{S\cup
T},\rho_{T}^{S\cup
T}\right\rangle\circ\otimes\leq\mathsf{id}_{\Phi(S)\times\Phi(T)},$ (8)

where $\leq$ is the pointwise order inherited by the partial order $\preceq$
of the algebra.

Adjoint valuation algebras are extremely common: relational databases, CSPs,
propositional logic, predicate logic, linear equations, linear inequalities,
can all be proven to be adjoint (see Proposition A.1 in AA.2).

####  5.2.1 Detecting disagreement is an inference problem

The most important aspect of adjoint valuation algebras is that, given a
globally agreeing knowledgebase, if a truth valuation exists, then it can be
obtained by simply combining all the available information. This is the
content of the following proposition, which generalises Proposition 2.3 in
[4].

######  Proposition 5.1 (See A for the proof).

Let $\Phi$ be an adjoint valuation algebra on a set of variables $V$. Let
$K=\\{\phi_{1},\dots,\phi_{n}\\}\subseteq\Phi$ be a knowledgebase. Let
$\gamma=\bigotimes_{i=1}^{n}\phi_{i}.$ Then $\phi_{1},\dots,\phi_{n}$ agree
globally if and only if ${\gamma^{\downarrow d(\phi_{i})}}=\phi_{i}$. In this
case, $\gamma$ is the most informative of all the possible truth valuations.

Thanks to this proposition, the quest for a global truth valuation becomes a
much easier task. This, in turn, makes the problem of detecting disagreement
significantly simpler. In fact, we can reformulate it as an inference problem.
Given a knowledgebase $\\{\phi_{1},\dots,\phi_{n}\\}$, it is sufficient to
solve the problem

${(\phi_{1}\otimes\dots\otimes\phi_{n})^{\downarrow d(\phi_{i})}}$ (9)

for all $1\leq i\leq n$. Then, the knowledgebase agrees globally if and only
if the solution to each problem is $\phi_{i}$.

###  5.3 Complete disagreement

Let $\phi_{1},\phi_{2}\in\Phi$ be two valuations of an adjoint information
algebra $\Phi$, and let $d(\phi_{1})=S$, $d(\phi_{2})=T$, with $S\cap
T\neq\emptyset$. By Proposition 5.1, to say that $\phi_{1}$ and $\phi_{2}$
disagree amounts to say that not _all_ the information carried by $\phi_{1}$
and $\phi_{2}$ can be preserved by combining them. However, _some_ of this
information is preserved, namely the quantities
$\psi_{1}\colonequals{(\phi_{1}\otimes\phi_{2})^{\downarrow S}}$ and
$\psi_{2}\colonequals{(\phi_{1}\otimes\phi_{2})^{\downarrow T}}$. Indeed,
$\psi_{1}\preceq\phi_{1}$ and $\psi_{2}\preceq\phi_{2}$ represent exactly the
portion of information on which the original valuations _do_ agree. This can
be easily shown by arguing that $\psi_{1}$ and $\psi_{2}$ agree on their
common variables:

${\psi_{1}^{\downarrow S\cap T}}={\left({(\phi_{1}\otimes\phi_{2})^{\downarrow
S}}\right)^{\downarrow S\cap T}}={(\phi_{1}\otimes\phi_{2})^{\downarrow S\cap
T}}={\left({(\phi_{1}\otimes\phi_{2})^{\downarrow T}}\right)^{\downarrow S\cap
T}}={\psi_{2}^{\downarrow S\cap T}}.$

However, there may be situations where $\psi_{1}$ and $\psi_{2}$ are null
elements of the algebra. This corresponds to a situation where $\phi_{1}$ and
$\phi_{2}$ disagree _completely_. In this case, we have
$\phi_{1}\otimes\phi_{2}=z_{S\cup T}.$ The liar cycle of Example 3.3 gives a
compelling example of complete disagreement. Let us compute the global
valuation $\gamma:=\bigotimes_{i=1}^{n}\phi_{n}$. We have

$\bigotimes_{i=1}^{n-1}\phi_{i}=\left\\{\mathbf{v}\in\mathbb{M}_{V}:\mathbf{v}(\left\langle
s_{1},\dots,s_{n}\right\rangle)=\left\langle 0,0,\dots,0\right\rangle\text{ or
}\left\langle 1,1,\dots,1\right\rangle\right\\}$

Hence,

$\begin{split}\gamma&=\left\\{\mathbf{v}\in\mathbb{M}_{V}:\mathbf{v}(\left\langle
s_{1},\dots,s_{n}\right\rangle)=\left\langle 0,0,\dots,0\right\rangle\text{ or
}\left\langle 1,1,\dots,1\right\rangle\right\\}\\\
&\otimes\left\\{\mathbf{v}\in\mathbb{M}_{\\{s_{1},s_{n}\\}}:\mathbf{v}(\left\langle
s_{1},s_{n}\right\rangle)=\left\langle 1,0\right\rangle\text{ or }\left\langle
0,1\right\rangle\right\\}=\emptyset=z_{V},\end{split}$

Hence, we conclude that this knowledgebase disagrees completely, despite
agreeing locally.

In light of this discussion, we introduce the following definition: we say
that $\phi_{1},\dots,\phi_{n}$ disagree completely if
$\gamma:=\bigotimes_{i=1}^{n}\phi_{i}=z_{V}$, or, equivalently by axiom (A8),
if there exists a $1\leq i\leq n$ such that

${(\phi_{1}\otimes\dots\otimes\phi_{n})^{\downarrow
d(\phi_{i})}}=z_{d(\phi_{i})}.$

##  6 Disagreement and possibilistic forms of contextuality

In this section we investigate the link between disagreement and possibilistic
forms of contextuality, i.e. logical and strong. This will lead us to
establish a connection between strong contextuality and complete disagreement,
and to prove that the problem of detecting logical forms of contextuality can
be rephrased as an inference problem for the valuation algebra of relational
databases.

An alternative definition of possibilistic empirical models, developed in [7],
will be particularly useful: a possibilistic empirical model on a scenario
$\left\langle X,\mathcal{M},(O_{m})\right\rangle$ can be equivalently defined
as a subpresheaf $\mathcal{S}\subseteq\mathcal{E}$ which verifies the
following properties:

  1. 1.

$\mathcal{S}(C)\neq\emptyset$ for all $C\in\mathcal{M}$

  2. 2.

$\mathcal{S}$ is _flasque beneath the cover_ , i.e. the map
$\mathcal{S}(U\subseteq U^{\prime})$ is surjective whenever $U\subseteq
U^{\prime}\subseteq C$ for some $C\in\mathcal{M}$.

  3. 3.

Every compatible family
$\\{\mathbf{s}_{C}\in\mathcal{S}(C)\\}_{C\in\mathcal{M}}$ induces a global
section $\mathbf{g}\in\mathcal{S}(X)$ such that
$\mathbf{g}\mid_{C}=\mathbf{s}_{C}$ for all $C\in\mathcal{M}$. Note that this
global section is unique since $\mathcal{S}$ is a subpresheaf of the sheaf
$\mathcal{E}$.

Then, possibilistic forms of contextuality can be shown to correspond to the
following properties [7]. Let
$\mathcal{S}:\mathcal{P}(X)^{op}\rightarrow\textbf{Set}$ be a possibilistic
model on a scenario $\left\langle X,\mathcal{M},(O_{m})\right\rangle$.

  * •

Given a context $C\in\mathcal{M}$ and a section $\mathbf{s}\in\mathcal{S}(C)$,
$\mathcal{S}$ is logically contextual at $\mathbf{s}$, or
$\mathsf{LC}(\mathcal{S},\mathbf{s})$, if $\mathbf{s}$ is not a member of any
compatible family.

  * •

$\mathcal{S}$ is strongly contextual, or $\mathsf{SC}(\mathcal{S})$, if
$\mathsf{LC}(\mathcal{S},\mathbf{s})$ for all $\mathbf{s}$. In other words, by
condition 3, $\mathcal{S}$ does not have any global section:
$\mathcal{S}(X)=\emptyset$.

Let $\left\langle X,\mathcal{M},(O_{m})\right\rangle$ be a scenario, and
consider the valuation algebra $\Phi$ of relational databases on the set of
variables $X$, where we define the frame of each variable $m\in X$ to be
$\Omega_{m}\colonequals O_{m}$. In particular, this means that for any context
$C\in\mathcal{M}$ we have $\Omega_{C}=\mathcal{E}(C)$. Now, suppose we have a
possibilistic empirical model
$\mathcal{S}:\mathcal{P}(X)^{op}\rightarrow\textbf{Set}$ over $\left\langle
X,\mathcal{M},(O_{m})\right\rangle$. We associate to it the knowledgebase
$K=\\{\mathcal{S}(C)\subseteq\mathcal{E}(C)=\Omega_{C}\\}_{C\in\mathcal{M}}\subseteq\Phi.$

######  Proposition 6.1 (See A for the proof).

The knowledgebase $K$ agrees locally.

This means that a possibilistic empirical model corresponds to a locally-
agreeing knowledgebase of the algebra or relational databases. We now have all
the elements to establish the connection between global disagreement and
logical forms of contextuality

######  Proposition 6.2 (See A for the proof).

The knowledgebase $K$ disagrees globally if and only if $\mathcal{S}$ is
logically contextual. It disagrees completely if and only if $\mathcal{S}$ is
strongly contextual.

Notice that the first part of the proposition reiterates the idea, expressed
in Section 44.3, that contextuality in an empirical model corresponds to an
instance local agreement vs global disagreement.666In fact the two results
coincide, as one can show that the algebra of relational databases is
equivalent to the one of Boolean potentials via the isomorphism
$\mathcal{P}(X)\cong 2^{X}$. The statement connecting strong contextuality
with complete disagreement, on the other hand, is a new addition to the
theory.

###  6.1 Detecting logical and strong contextuality is an inference problem

Thanks to Proposition 6.2 and the results of the previous sections, we can
easily translate the problem of detecting logical and strong contextuality
into inference problems. This aspect is particularly important since it allows
to apply the numerous efficient algorithms developed by the long-established
theory of generic inference. The following proposition follows immediately
from Proposition 6.2 and the results of Sections 55.25.2.1 and 55.3:

######  Proposition 6.3.

Let $\mathcal{S}:\mathcal{P}(X)\rightarrow\textbf{Set}$ be an empirical model
over a scenario $\left\langle X,\mathcal{M},(O_{m})\right\rangle$. Then

  * •

The model $\mathcal{S}$ is logically contextual if and only if there exists a
context $\overline{C}\in\mathcal{M}$ such that the inference problem

${\left(\bigotimes_{C\in\mathcal{M}}\mathcal{S}(C)\right)^{\downarrow\overline{C}}}$
(10)

for the algebra of relational databases has a solution different from
$\mathcal{S}(\overline{C})$.

  * •

The model $\mathcal{S}$ is strongly contextual if and only if, there exists a
$\overline{C}\in\mathcal{M}$, such that the solution to the inference problem
(10) is $z_{\overline{C}}$. Notice that, by (1) in (A8), this is equivalent to
saying that $\bigotimes_{C}\mathcal{S}(C)=z_{X}$.

It follows that, in order to determine whether a model $\mathcal{S}$ is
strongly contextual, one has to solve a single inference problem (10): if the
result is $z_{\overline{C}}$, then $\mathcal{S}$ is strongly contextual. On
the other hand, to determine whether $\mathcal{S}$ is logically contextual,
one has to solve $|\mathcal{M}|$ distinct problems, in the worst case
scenario. This reformulation is particularly important since it allows to use
efficient algorithms of generic inference to solve (10). We have already
started to explore this possibility in separate work, and it has been possible
to develop new algorithms for the detection of logical forms of contextuality
which significantly outperform the current state of the art [37, 38].

##  7 Conclusions

We have presented a general definition of different forms of disagreement
between information sources in the abstract framework of valuation algebras.
In particular, we identified three kinds of disagreement: local, global and
complete, and presented examples of each of them using different valuation
algebras. A particular attention has been given to instances of knowledgebases
which agree locally but disagree globally. By recovering the valuation
algebraic formalism in sheaf-theoretic terms, we showed that sheaf-theoretic
contextuality is simply a special case of such a knowledgebase, where the
valuation algebra in question is the one of $R$-potentials, while strong
contextuality is a special case of complete disagreement for the algebra of
relational databases. This result is a vast generalisation of the previously
observed connections between contextuality and relational databases,
constraint satisfaction problems, and logical paradoxes, and constitutes a
promising attempt to establish a general theory of contextual semantics. The
main advantage of such an abstract and flexible treatment is that it
significantly widens the scope for the observation of contextual behaviour,
and could potentially lead to the transfer of results and methods for
disagreement across the many different fields captured by the valuation
algebraic framework.

In separate work, we have started to explore this potential by applying
popular inference algorithms such as the fusion [39] and collect [11] methods
to detect contextuality in empirical models. This problem is notoriously
complex from a computational perspective [5], and very few algorithms have
been developed for this specific task. Yet computational explorations of
logical forms of contextuality, however limited, have proved very useful for
the advancement of the theory [5, 40], and would greatly benefit from any
algorithmic improvement. For this reason, the theory introduced in this paper
represents a major opportunity to enhance our understanding of contextuality.

The authors declare no competing interests. Both the authors contributed
equally to this work. Their names are listed in alphabetical order. The
authors would like to thank Rui Soares Barbosa for helpful discussions.
Support from the following is gratefully acknowledged: EPSRC EP/N018745/1,
‘Contextuality as a Resource in Quantum Computation’ (SA); EPSRC Doctoral
Training Partnership, and Oxford–Google Deepmind Graduate Scholarship (GC).

## References

  * [1] Howard M, Wallman J, Veitch V, Emerson J.  Contextuality supplies the ‘magic’ for quantum computation.  Nature. 2014 06;510(7505):351–355.
  * [2] Raussendorf R.  Contextuality in measurement-based quantum computation.  Physical Review A. 2013 Aug;88(2):022322.
  * [3] Abramsky S, Brandenburger A.  The sheaf-theoretic structure of non-locality and contextuality.  New Journal of Physics. 2011;13(11):113036.  Eprint available at arXiv:1102.0264 [quant-ph].
  * [4] Abramsky S.  Relational databases and Bell’s theorem.  In: Tannen V, Wong L, Libkin L, Fan W, Tan WC, Fourman M, editors. In search of elegance in the theory and practice of computation: Essays dedicated to Peter Buneman. vol. 8000 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 2013. p. 13–35.  Eprint available at arXiv:1208.6416 [cs.LO].
  * [5] Abramsky S, Gottlob G, Kolaitis PG.  Robust constraint satisfaction and local hidden variables in quantum mechanics.  In: Rossi F, editor. Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. AAAI Press; 2013. p. 440–446.
  * [6] Abramsky S, Sadrzadeh M.  Semantic unification: A sheaf theoretic approach to natural language.  In: Casadio C, Coecke B, Moortgat M, Scott P, editors. Categories and types in logic, language, and physics: Essays Dedicated to Jim Lambek on the occasion of his 90th birthday. vol. 8222 of Lecture Notes in Computer Science. Springer; 2014. p. 1–13.  Eprint available at arXiv:1403.3351 [cs.CL].
  * [7] Abramsky S, Barbosa RS, Kishida K, Lal R, Mansfield S.  Contextuality, cohomology and paradox.  In: Kreutzer S, editor. 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). vol. 41 of Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik; 2015. p. 211–228.
  * [8] Abramsky S, Barbosa RS, Carù G, Perdrix S.  A complete characterization of all-versus-nothing arguments for stabilizer states.  Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences. 2017;375(2106).  Available from: http://rsta.royalsocietypublishing.org/content/375/2106/20160385.
  * [9] de Silva N. Logical paradoxes in quantum computation; 2017.  Eprint available at arXiv:1709.00013 [quant-ph].
  * [10] Shenoy PP.  A valuation-based language for expert systems.  International Journal of Approximate Reasoning. 1989;3(5):383–411.  Available from: http://www.sciencedirect.com/science/article/pii/0888613X89900091.
  * [11] Shenoy PP, Shafer G, Shachter RD, Levitt TS, Kanal LN, Lemmer JF.  In: Axioms for Probability and Belief-Function Propagation. vol. 9. North-Holland; 1990. p. 169–198.  Available from: http://www.sciencedirect.com/science/article/pii/B9780444886507500196.
  * [12] Kohlas J, Stärk RF.  Information algebras and information systems.  Citeseer; 1996.
  * [13] Kohlas J, Shenoy PP.  Computation in valuation algebras.  In: Handbook of defeasible reasoning and uncertainty management systems. Springer; 2000. p. 5–39.
  * [14] Shenoy PP.  Consistency in valuation-based systems.  ORSA Journal on Computing. 1994;6(3):281–291.
  * [15] Kohlas J, Haenni R, Moral S.  Propositional information systems.  Journal of Logic and Computation. 1999;9(5):651–681.  Available from: http://dx.doi.org/10.1093/logcom/9.5.651.
  * [16] Shafer GR, Shenoy PP. Local computation in hypertrees; 1991.  Tech. Rept. School of Business, University of Kansas.
  * [17] Kohlas J.  Information Algebras.  Springer; 2003.
  * [18] Pouly M.  A generic framework for local computation.  Université de Fribourg; 2008.
  * [19] Pouly M.  NENOK — A software architecture for generic inference.  International Journal on Artificial Intelligence Tools. 2010;19(01):65–99.  Available from: https://doi.org/10.1142/S0218213010000042.
  * [20] Pouly M, Kohlas J.  Generic Inference: A Unifying Theory for Automated Reasoning.  John Wiley & Sons; 2012.
  * [21] Spekkens RW.  Contextuality for preparations, transformations, and unsharp measurements.  Physical Review A. 2005;71(5):052108.
  * [22] Cabello A, Severini S, Winter A.  Graph-theoretic approach to quantum correlations.  Physical Review Letters. 2014;112:040401.
  * [23] Acín A, Fritz T, Leverrier A, Sainz AB.  A combinatorial approach to nonlocality and contextuality.  Communications in Mathematical Physics. 2015;334(2):533–628.
  * [24] Dzhafarov EN, Kujala JV.  Context–content systems of random variables: The Contextuality-by-Default theory.  Journal of Mathematical Psychology. 2016;74:11–33.
  * [25] Ullman JD.  Principles of database systems.  Galgotia publications; 1984.
  * [26] Wilson N, Mengin J.  Logical deduction using the local computation framework.  In: European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty. Springer; 1999. p. 386–396.
  * [27] Zadrozny W, Garbayo L. A Sheaf Model of Contradictions and Disagreements. Preliminary Report and Discussion; 2018.  Eprint available at arXiv:1801.09036 [cs.CL].
  * [28] Bell JS.  On the Einstein-Podolsky-Rosen paradox.  Physics. 1964;1(3):195–200.
  * [29] Clauser JF, Horne MA, Shimony A, Holt RA.  Proposed experiment to test local hidden-variable theories.  Physical Review Letters. 1969 Oct;23(15):880–884.
  * [30] Bell JS.  Speakable and unspeakable in quantum mechanics: Collected papers on quantum philosophy.  Cambridge University Press; 1987.
  * [31] Fine A.  Hidden variables, joint probability, and the Bell inequalities.  Physical Review Letters. 1982 Feb;48(5):291–295.
  * [32] Hardy L.  Quantum mechanics, local realistic theories, and Lorentz-invariant realistic theories.  Physical Review Letters. 1992 May;68(20):2981–2984.
  * [33] Hardy L.  Nonlocality for two particles without inequalities for almost all entangled states.  Physical Review Letters. 1993;71(11):1665–1668.
  * [34] Greenberger DM, Horne MA, Zeilinger A.  Going beyond Bell’s theorem.  In: Kafatos M, editor. Bell’s theorem, quantum theory, and conceptions of the universe. vol. 37 of Fundamental Theories of Physics. Kluwer; 1989. p. 69–72.
  * [35] Greenberger DM, Horne MA, Shimony A, Zeilinger A.  Bell’s theorem without inequalities.  American Journal of Physics. 1990;58(12):1131–1143.
  * [36] Haenni R.  Ordered valuation algebras: a generic framework for approximating inference.  International Journal of Approximate Reasoning. 2004;37(1):1–41.
  * [37] Carú G.  Logical and Topological Contextuality in Quantum Mechanics and Beyond.  University of Oxford; 2019.
  * [38] Abramsky S, Carù G.  Generic inference algorithms for contextuality; 2019.  Forthcoming.
  * [39] Shenoy PP.  Valuation-based systems: A framework for managing uncertainty in expert systems.  In: Fuzzy logic for the management of uncertainty. John Wiley & Sons, Inc.; 1992. p. 83–104.
  * [40] Mansfield S, Fritz T.  Hardy’s non-locality paradox and possibilistic conditions for non-locality.  Foundations of Physics. 2012;42:709–719.  Eprint available at arXiv:1105.1819 [quant-ph].

##  Appendix A Proofs

###  A.1 Theorem 4.1

###### Proof.

If $e$ is non-contextual, then there exists a global distribution
$d:\mathcal{E}(X)\rightarrow R$ such that $d|_{C}=e_{C}$ for all
$C\in\mathcal{M}$. Hence $d$ is a global truth valuation for the knowledgebase
$K$. Conversely, suppose $K$ agrees globally, which means that there exists a
global $R$-potential $d:\Omega_{X}=\mathcal{E}(X)\rightarrow R$ such that
${d^{\downarrow C}}=e_{C}$ for all $C\in\mathcal{M}$. The only thing we need
to prove is that $d$ is an $R$-distribution, i.e. that it is normalised. Let
$\ast$ denote the unique $\emptyset$-tuple and let $C\in\mathcal{M}$ be an
arbitrary context. We have:

$\begin{split}\sum_{\mathbf{g}\in\mathcal{E}(X)}d(\mathbf{g})&=\sum_{\begin{subarray}{c}\mathbf{g}\in\mathcal{E}(X):\\\
\mathbf{g}_{{}_{\downarrow\emptyset}}=\ast\end{subarray}}d(\mathbf{g})={d^{\downarrow\emptyset}}(\ast)={\left({d^{\downarrow
C}}\right)^{\downarrow\emptyset}}(\ast)={(e_{C})^{\downarrow\emptyset}}(\ast)\\\
&=\sum_{\begin{subarray}{c}\mathbf{x}\in\mathcal{E}(C):\\\
\mathbf{x}_{{}_{\downarrow\emptyset}}=\ast\end{subarray}}e_{C}(\mathbf{x})=\sum_{\mathbf{x}\in\mathcal{E}(C)}e_{C}(\mathbf{x})=1.\end{split}$

∎

###  A.2 Adjoint information algebras

######  Proposition A.1.

The algebra of information sets related to a family
$\\{\left\langle\mathcal{L}_{Q},\mathbb{M}_{Q},\models_{Q}\right\rangle\\}_{Q\subseteq
V}$ defined over any language $\mathcal{L}$ and set of models $\mathbb{M}$ is
adjoint.

###### Proof.

It is sufficient to prove (8):

  * •

Let $M\subseteq\mathbb{M}_{Q\cup U}$, where $Q,U\subseteq V$.

$\begin{split}{M^{\downarrow Q}}\otimes{M^{\downarrow
U}}&=\\{\mathbf{x}_{{}_{\downarrow Q}}:\mathbf{x}\in
M\\}\otimes\\{\mathbf{x}_{{}_{\downarrow U}}:\mathbf{x}\in M\\}\\\
&=\left\\{\mathbf{v}\in\mathbb{M}_{Q\cup U}:\exists\mathbf{x},\mathbf{y}\in
M\text{ s.t. }(\mathbf{v}_{{}_{\downarrow Q}}=\mathbf{x}_{{}_{\downarrow
Q}})\wedge(\mathbf{v}_{{}_{\downarrow U}}=\mathbf{y}_{{}_{\downarrow
U}})\right\\}.\end{split}$

Then, clearly, $M\subseteq{M^{\downarrow Q}}\otimes{M^{\downarrow U}}$.

  * •

Now, let $M_{1}\subseteq\mathbb{M}_{Q}$ and $M_{2}\subseteq\mathbb{M}_{U}$. We
have

$\begin{split}{(M_{1}\otimes M_{2})^{\downarrow
Q}}&={\\{\mathbf{v}\in\mathbb{M}_{Q\cup U}:(\mathbf{v}_{{}_{\downarrow Q}}\in
M_{1})\wedge(\mathbf{v}_{{}_{\downarrow U}}\in M_{2})\\}^{\downarrow Q}}\\\
&=\left\\{\mathbf{v}_{{}_{\downarrow Q}}:\mathbf{v}\in\mathbb{M}_{Q\cup
U}\wedge(\mathbf{v}_{{}_{\downarrow Q}}\in
M_{1})\wedge(\mathbf{v}_{{}_{\downarrow U}}\in M_{2})\right\\}\subseteq
M_{1}.\end{split}$

One proves that ${(M_{1}\otimes M_{2})^{\downarrow U}}\subseteq M_{2}$ in the
same way.

∎

###  A.3 Proposition 5.1

###### Proof of Proposition 5.1.

Suppose $\delta\in\Phi_{V}$ is a truth valuation for $K$. Then we have

$\delta\preceq\bigotimes_{i=1}^{n}{\delta^{\downarrow
d(\phi_{i})}}=\bigotimes_{i=1}^{n}\phi_{i}=\gamma$

Moreover, because projection is monotone by axiom (A13), we have

$\phi_{i}\preceq{\delta^{\downarrow
d(\phi_{i})}}\stackrel{{\scriptstyle\text{(A13)}}}{{\preceq}}{\gamma^{\downarrow
d(\phi_{i})}}\preceq\phi_{i}.$

Thus $\gamma$ is a truth valuation for $K$. ∎

###  A.4 Proposition 6.1

###### Proof of Proposition 6.1.

Let $\mathbf{x}\in\mathcal{E}(C\cap C^{\prime})=\Omega_{C\cap C^{\prime}}$. We
have

$\begin{split}{i_{\mathcal{S}(C)}^{\downarrow C\cap
C^{\prime}}}(\mathbf{x})&=\max_{\mathbf{y}\in\mathcal{E}(C\setminus
C^{\prime})}i_{\mathcal{S}(C)}(\mathbf{x},\mathbf{y})=\begin{cases}1&\text{ if
}\exists\mathbf{y}\in\mathcal{E}(C\setminus
C^{\prime}):\left\langle\mathbf{x},\mathbf{y}\right\rangle\in\mathcal{S}(C),\\\
0&\text{ otherwise.}\end{cases}\\\ &=\begin{cases}1&\text{ if
}\mathbf{x}\in\mathcal{S}(C\cap C^{\prime})\\\
0&\text{otherwise}\end{cases}=i_{\mathcal{S}(C\cap C^{\prime})}\end{split}$

where the penultimate equality follows from the fact that $\mathcal{S}$ is
flasque beneath the cover, and $C\cap C^{\prime}\subseteq C\in\mathcal{M}$.
With the same argument we show that ${i_{\mathcal{S}(C^{\prime})}^{\downarrow
C\cap C^{\prime}}}=i_{\mathcal{S}(C\cap C^{\prime})}$, and we conclude

${i_{\mathcal{S}(C)}^{\downarrow C\cap C^{\prime}}}=i_{\mathcal{S}(C\cap
C^{\prime})}={i_{\mathcal{S}(C^{\prime})}^{\downarrow C\cap C^{\prime}}},$

which means that $K$ agrees locally. ∎

###  A.5 Proposition 6.2

###### Proof of Proposition 6.2.

We will denote $\Gamma:=\bigotimes_{C\in\mathcal{M}}S(C)$.

  * •

Suppose $K$ disagrees globally. By Proposition 5.1, there exists a context
$C_{0}\in\mathcal{M}$ such that ${\Gamma^{\downarrow
C_{0}}}\neq\mathcal{S}(C_{0})$. Since the algebra of relational databases is
adjoint, by Proposition 5.1, this implies ${\gamma^{\downarrow
C_{0}}}\subset\mathcal{S}(C_{0})$, which means that there exists a local
section $\mathbf{x}\in\mathcal{S}(C_{0})$ such that
$\mathbf{x}\notin{\Gamma^{\downarrow C_{0}}}$. We will now show that
$\mathcal{S}$ is logically contextual at $\mathbf{x}$. Suppose
$\neg\mathsf{LC}(\mathcal{S},\mathbf{x})$ by contradiction. Then there exists
a global section $\mathbf{g}\in\mathcal{S}(X)$ such that
$\mathbf{g}_{{}_{\downarrow C_{0}}}=\mathbf{x}$. Because
$\mathbf{g}\in\mathcal{S}(X)$, we have $\mathbf{g}_{{}_{\downarrow
C}}\in\mathcal{S}(C)$ for all $C\in\mathcal{M}$, which implies
$\mathbf{g}\in\Gamma$. Then, $\mathbf{x}=g_{{}_{\downarrow
C_{0}}}\in{\Gamma^{\downarrow C_{0}}}$, which is a contradiction.

Now, Suppose $\mathcal{S}$ is logically contextual at a section
$\mathbf{x}\in\mathcal{S}(C_{0})$. If $\mathbf{x}\in{\Gamma^{\downarrow
C_{0}}}$, then there exists a $\mathbf{g}\in\Gamma$ such that
$\mathbf{g}_{{}_{\downarrow C_{0}}}=\mathbf{x}$. Since $\mathbf{g}\in\Gamma$,
we have $\mathbf{g}_{{}_{\downarrow C}}\in\mathcal{S}(C)$ for all
$C\in\mathcal{M}$. Thus, by condition (3) of the definition of a possibilistic
empirical model, $\mathbf{g}\in\mathcal{S}(X)$, which means that $\mathbf{g}$
is a global is a global section extending $\mathbf{x}$. This contradicts the
fact that $\mathcal{S}$ is logicallly contextual at $\mathbf{x}$. We conclude
that $\mathbf{x}\notin{\Gamma^{\downarrow C_{0}}}$. Thus
${\Gamma^{\downarrow(}}C_{0})\neq\mathcal{S}(C_{0})$, hence $K$ disagrees
globally.

  * •

We will now prove that $K$ disagrees completely if and only if $\mathcal{S}$
is strongly contextual. Recall that the null element of the algebra is the
emptyset $z_{X}=\emptyset$. We have

$\begin{split}\neg\mathsf{SC}(\mathcal{S})&\Leftrightarrow\exists\mathbf{g}\in\mathcal{S}(X)\Leftrightarrow\exists\mathbf{g}\in\mathcal{E}(X):\mathbf{g}_{{}_{\downarrow
C}}\in\mathcal{S}(C)\leavevmode\nobreak\ \forall C\in\mathcal{M}\\\
&\Leftrightarrow\exists\mathbf{g}\in\mathcal{S}(X):\mathbf{g}\in\Gamma\Leftrightarrow\Gamma\neq
0.\end{split}$

∎