are cancelled _except_ for $A$ and $B$ on the left-hand side, and $C$ and $D$
on the right-hand side, then we can conclude $A\times B\succeq C\times D$.
This is exactly what we would obtain by multiplying the probabilities of all
left-hand side terms on the left, and the probabilities all right-hand side
terms on the right, and then cancelling any terms occurring on each side.
Under the translation $\eqref{condquad}$, $\mathsf{Q5}_{n}$ corresponds to the
axiom $\mathsf{MultCan}_{n}$ from Definition 4.6.

####  4.2.2 Domotor’s argument

The necessity of axioms (schemes) $\mathsf{Q1}$-$\mathsf{Q6}_{n}$ is easily
verified. Domotor (1969, p. 66) provides an argument to the effect that these
axioms are also sufficient for the order $\succeq$ to be product-representable
by a probability measure, in the sense of condition (6). We will now give a
brief description of the proof strategy. This will serve, first, to emphasize
the algebraic nature of the problem, which involves proving the consistency of
certain polynomial constraints and thus calls for techniques beyond the
standard linear algebra involved in the purely additive setting of Theorem 3.
Secondly, as we will see, there is a step in the argument which suggests that
the proof of sufficiency is incomplete as it stands.

Suppose we are given a finite quadratic probability structure
$(\Omega,\mathcal{F},\succeq)$ as in Definition 4.7: without loss of
generality, we will assume we are working with the full powerset algebra
$\mathcal{F}=\mathcal{P}(\Omega)$. We want to show that the relation $\succeq$
is product-representable in the sense of (6). Consider the space
$\mathbb{R}^{n\times n}$ containing all indicator functions
$\mathds{1}_{A\times B}$ of products $A\times B$. Take the space of indicator
functions as vectors in $\mathbb{R}^{n\times n}$, where each
$\mathds{1}_{A\times B}$ is the vector $\mathbf{x}$ where $x_{ij}=1$ exactly
if $(\omega_{i},\omega_{j})\in A\times B$ (that is, we list all elements of
$\Omega\times\Omega$ in lexicographic order). Lift the order $\succeq$ from
$\mathcal{F}$ to $M=\\{\mathds{1}_{A\times B}\,|\,A\times B\in\mathcal{F}\\}$.
Now we apply Lemma 3.4: note that axioms $\mathsf{Q4}$ and $\mathsf{Q6}_{n}$
give us precisely conditions (a) and (b) in the statement of the Lemma. This
gives us the existence of a linear functional $\hat{\Phi}:\mathbb{R}^{n\times
n}\to\mathbb{R}$ with $\hat{\Phi}(\mathds{1}_{A\times
B})\geq\hat{\Phi}(\mathds{1}_{C\times D})$ whenever $A\times B\succeq C\times
D$. This functional is of the form

$\displaystyle\hat{\Phi}(\mathbf{x})=\mathbf{a}^{T}\mathbf{x}=(a_{11},a_{12},\dots,a_{1n},a_{21},\dots
a_{nn})$ $\displaystyle\begin{bmatrix}x_{11}\\\ x_{21}\\\ \vdots\\\
x_{nn}\end{bmatrix}$ (8)

The existence of such a linear functional already entails that there is a
measure $\mu$ on $\mathcal{P}(\Omega\times\Omega)$ that respects the ordering
on Cartesian products $\succeq$, by defining $\mu(A\times
B):=\hat{\Phi}(\mathds{1}_{A\times
B})/{\hat{\Phi}(\mathds{1}_{\Omega\times\Omega})}$. But we need to ensure that
there a measure $\mu$ representing $\succeq$ which corresponds to the product
of a measure $\mathbb{P}$ on $\mathcal{P}(\Omega)$: i.e. such that
$\mu(A\times B)=\mathbb{P}(A)\cdot\mathbb{P}(B)$.

We represent the linear functional $\hat{\Phi}$ as a bilinear functional
$\Phi:\mathbb{R}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$. It can be
represented as a matrix
$\Phi(\mathbf{x},\mathbf{y})=\mathbf{x}^{T}\mathbf{M}_{\Phi}\mathbf{y}$ where
$\mathbf{M}_{\Phi}$ is a $n\times n$ matrix: intuitively, we want the
$(i,j)$-th entry to represent the probability of
$\\{\omega_{i}\\}\times\\{\omega_{j}\\}$. We write is as

$\Phi(\mathbf{x},\mathbf{y})=\mathbf{x}^{T}\mathbf{M}_{\Phi}\mathbf{y}=(x_{1},\dots,x_{n})\begin{pmatrix}a_{11}&\dots&a_{1n}\\\
\vdots&&\vdots\\\ a_{n1}&&a_{nn}\end{pmatrix}\begin{bmatrix}y_{1}\\\ y_{2}\\\
\vdots\\\ y_{n}\end{bmatrix}$

We then have
$\Phi(\mathds{1}_{A},\mathds{1}_{B})=\hat{\Phi}(\mathds{1}_{A\times B})$. Now,
in order for $\Phi$ to give rise a product measure as required, we want to
know whether it can be decomposed as the product of linear functionals $f_{1}$
and $f_{2}$, so that we can write
$\Phi(\mathds{1}_{A},\mathds{1}_{B})=f_{1}(\mathds{1}_{A})f_{2}(\mathds{1}_{B})$.
This would suffice, as the symmetry axiom $\mathsf{Q3}$ ensures that
$\Phi(\mathds{1}_{A},\mathds{1}_{B})=\Phi(\mathds{1}_{B},\mathds{1}_{A})$
($\mathbf{M}_{\Phi}$ is symmetric), which would ensure that $f_{1}=f_{2}$.
Then setting $\mathbb{P}(A):=f_{1}(\mathds{1}_{A})/f_{1}(\mathds{1}_{\Omega})$
would give the desired measure (here $\mathsf{Q1}$ and $\mathsf{Q2}$ ensure it
is a non-degenerate measure). A general condition for a bilinear functional
being decomposable in this way given by the following standard
characterization:212121 A $n\times n$ matrix $\mathbf{M}$ has rank 1 if and
only if it can be written in the form $\mathbf{M}=\mathbf{u}\mathbf{v}^{T}$
for two vectors $\mathbf{u},\mathbf{v}$. In one direction, suppose
$\mathbf{M}_{\Psi}$ has rank one, and so is of the form
$\mathbf{u}\mathbf{v}^{T}$. Then  $\displaystyle\Psi(\mathbf{x},\mathbf{y})$
$\displaystyle=\mathbf{x}^{T}(\mathbf{u}\mathbf{v}^{T})\mathbf{y}$
$\displaystyle=(\mathbf{x}^{T}\mathbf{u})(\mathbf{v}^{T}\mathbf{y})$
$\displaystyle=(\mathbf{u}^{T}\mathbf{x})(\mathbf{v}^{T}\mathbf{y}),$ so that
we define $f_{1}(\mathbf{x}):=\mathbf{u}^{T}\mathbf{x}$ and
$f_{2}(\mathbf{x}):=\mathbf{v}^{T}\mathbf{x}$ for the decomposition into
linear functionals. Conversely, given two linear functionals generated by
respective vectors $\mathbf{u}$ and $\mathbf{v}$ in the same fashion, the
matrix $\mathbf{u}\mathbf{v}^{T}$ generates a decomposable bilinear
functional.

######  Proposition 4.8.

A bilinear functional
$\Psi:\mathbb{R}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ can be written
as $\Psi(\mathbf{x},\mathbf{y})=f_{1}(\mathbf{x})f_{2}(\mathbf{y})$ for two
linear functionals $f_{1},f_{2}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ if and
only if $\text{rank}(\mathbf{M}_{\Psi})=1$. We then say $\Psi$ is a rank-1
functional.

This is where Domotor’s argument seems to face a difficulty (or perhaps an
omission in the presentation). The proof began by establishing the existence
of the bilinear function $\Phi$ which represents the order $\succeq$. At this
point the proof proceeds to argue that $\Phi$—a generic order-preserving
linear functional obtained from Lemma 3.4—has rank 1.222222See (Domotor,,
1969, p.68). Thus the strategy seems to be to argue that any such functional
representing $\succeq$ has rank 1. This, however, is not the case, as can be
seen by a simple example. Say that two functionals $\Phi$ and $\Psi$ are
order-equivalent on $\mathcal{P}(\Omega)\times\mathcal{P}(\Omega)$ if we have
$\succeq_{\Phi}=\succeq_{\Psi}$, where we define $A\times
B\succeq_{\Phi}B\times C$ if and only if
$\Phi(\mathds{1}_{A},\mathds{1}_{B})\geq\Phi(\mathds{1}_{C},\mathds{1}_{D})$.
We can have two such functionals that are order-equivalent with only one of
them having rank 1. For instance, in the case
$\Omega=\\{\omega_{1},\omega_{2}\\}$, we can take functionals given by
matrices

$\mathbf{M}_{\Phi}=\begin{pmatrix}1/16&3/16\\\ 3/16&9/16\end{pmatrix}\text{
and }\mathbf{M}_{\Psi}=\begin{pmatrix}1/12&3/12\\\ 3/12&5/12\end{pmatrix}$

Here $\Phi$ is a rank-1 functional, whose order $\succeq_{\Phi}$ is
representable by the probability measure
$\mathbb{P}(\\{\omega_{1}\\})=\nicefrac{{1}}{{4}}$,
$\mathbb{P}(\\{\omega_{2}\\})=\nicefrac{{3}}{{4}}$. However, $\Psi$ is
evidently not rank-1. Yet the order $\succeq_{\Psi}$ agrees with
$\succeq_{\Phi}$, and thus satisfies axioms $\mathsf{Q1}$-$\mathsf{Q6}_{n}$.
The axioms $\mathsf{Q1}$-$\mathsf{Q6}_{n}$ thus cannot guarantee in general
that any linear functional that represents the order has rank 1.

Clarifying this step of the argument (and indeed, determining if this
difficulty may be due to a presentational ambiguity, rather than a logical
gap) is complicated by the fact that the author does not spell out the
decomposability argument in detail. Instead, the argument very briefly appeals
to an unstated result in geometry of webs (Aczél et al.,, 1960), from which,
given the multiplicative cancellation axiom $\mathsf{Q5}_{n}$, decomposability
is inferred.232323Unfortunately, we were unable to trace the original article
by Aczél, Pickert and Radó.

Returning to the task at hand: we know that there exists a bilinear functional
$\Phi$ which represents the order $\succeq$. In order to ensure the order is
representable via products of probabilities, we want to show that the axioms
guarantee the existence of a bilinear functional _of rank 1_ that is order-
equivalent to $\Phi$.

####  4.2.3 The (semi-)algebraic perspective on the representation problem

Whether or not the approach via web geometry can be made to succeed in showing
the sufficienty of Domotor’s axioms, there is a sense in which it not the most
natural from the perspective of investigating the additive-multiplicative
divide in probabilistic logics. Recall that Scott’s representation theorem
(Theorem 3), and thus the standard completeness proof for
$\mathcal{L}_{\text{comp}}$, directly relates the finite cancellation axioms
to certificates of inconsistency for linear inequality systems. In the same
way, it is of intrinsic interest to pursue a representation theorem for
conditional comparative probability that would directly reveal the algebraic
content of Domotor’s proposed axioms (and axiom $\mathsf{Q5}_{n}$ in
particular, which captures the multiplicative behaviour of conditional
probability orders).

It is thus worth considering a direct algebraic formulation of the problem.
Each order $\succeq$ satisfying the axioms $\mathsf{Q1}$-$\mathsf{Q6}_{n}$
generates a system of polynomial inequalities. For every set $A\subset\Omega$,
the polynomial corresponding to $A$ is given by

$p_{A}(x_{1},...,x_{n})=\sum^{n}_{i=1}\mathds{1}_{A}(\omega_{i})x_{i}.$

Now for each inequality $A\times B\succeq C\times D$ in the order, we add a
constraint

$p_{A}(\overline{x})p_{B}(\overline{x})-p_{C}(\overline{x})p_{D}(\overline{x})\geq
0,$

and similarly for strict inequalities. We need to show the resulting system is
consistent whenever $\succeq$ satisfies the axioms
$\mathsf{Q1}$-$\mathsf{Q6}_{n}$.

Note that this system of inequalities is given by quadratic forms: each
polynomial
$p_{A}(\overline{x})p_{B}(\overline{x})-p_{C}(\overline{x})p_{D}(\overline{x})$
is homogeneous of degree 2. Formulated in this way, it is clear that proving a
representation result would amount to showing that the axioms ensure that the
semi-algebraic sets defined by quadratic forms of this type are indeed
nonempty. By analogy to the case of $\mathcal{L}_{\text{comp}}$, here it is
natural to approach this problem via the Positivstellsatz (Theorem 9). As we
mentioned above, the Positivstellensatz is a semi-algebraic analogue of
hyperplane separation theorems, like those used in proving completeness for
$\mathcal{L}_{\text{comp}}$. It establishes that there exist certificates of
infeasibility of a given form for any infeasible system of polynomials. Just
as, in the additive case, any certificate of infeasibility was shown to
correspond to a failure of a finite cancellation axiom, so too, one may hope,
a failure of the Domotor axioms (and the $\mathsf{Q5}_{n}$ axiom in
particular) can always be extracted from a Positivstellensatz certificate.

We leave a definite solution to the representation problem for conditional
probability—and completeness for $\mathcal{L}_{\text{cond}}$—for further work:
as a first step, we show in the Appendix that the axioms for quadratic
probability structures are indeed sufficient for representation in the special
case of $|\Omega|=2$. The observations in this section motivate further work
on determining the adequacy of Domotor’s axioms: this is not only to ensure
that the canonical axiomatization for conditional probability orders on finite
spaces is correct as it stands, but also because, as we suggested above, it is
of intrinsic interest to pursue an alternative, algebraically transparent
proof of the representation result.

###  4.3 Complexity of multiplicative systems

The main result of this section finds a uniform complexity for all of our
multiplicative systems:

######  Theorem 10.

$\mathsf{SAT}_{\text{ind}}$, $\mathsf{SAT}_{\text{confirm}}$,
$\mathsf{SAT}_{\text{cond}}$, and $\mathsf{SAT}_{\text{poly}}$ are all
$\exists\mathbb{R}$-complete.

To show the above theorem, we borrow the following lemma from Abrahamsen et
al., (2018):

######  Lemma 4.9.

Fix variables $x_{1},...,x_{n}$, and set of equations of the form
$x_{i}+x_{j}=x_{k}$ or $x_{i}x_{j}=1$, for $i,j,k\in[n]$. Let
$\exists\mathbb{R}$-inverse be the problem of deciding whether there exist
reals $x_{1},...,x_{n}$ satisfying the equations, subject to the restrictions
$x_{i}\in[\nicefrac{{1}}{{2}},2]$. This problem is
$\exists\mathbb{R}$-complete.

We omit the proof of Lemma 4.9, but at a high level, it proceeds in two steps.
First, one shows that finding a real root of a degree-4 polynomial with
rational coefficients is $\exists\mathbb{R}$-complete, and then repeatedly
performs variable substitutions to get the constraints $x_{i}+x_{j}=x_{k}$ and
$x_{i}x_{j}=1$. Second, one shows that any such polynomial has a root within a
closed ball about the origin, and then shifts and scales this ball to contain
exactly the range $[\nicefrac{{1}}{{2}},2]$.

###### Proof of Theorem 10.

Since

$\mathsf{SAT}_{\text{ind}}\leq\mathsf{SAT}_{\text{confirm}}\leq\mathsf{SAT}_{\text{cond}}\leq\mathsf{SAT}_{\text{poly}},$

it suffices to show that $\mathsf{SAT}_{\text{ind}}$ is
$\exists\mathbb{R}$-hard and that $\mathsf{SAT}_{\text{poly}}$ is in
$\exists\mathbb{R}$. To show the former, we extend an argument given by Mossé
et al., (2022), and to show the latter, we repeat the proof given by Mossé et
al., (2022) (see also Ibeling and Icard, (2020)).

Let us first show that $\mathsf{SAT}_{\text{poly}}$ is in $\exists\mathbb{R}$.
Suppose that $\varphi\in\mathcal{L}_{\text{poly}}$ is satisfied by some model
$\mathbb{P}$. Using the fact that $\exists\mathbb{R}$ is closed under
$\mathsf{NP}$-reductions (ten Cate et al., (2013); cf. Definition 2.7) it
suffices to provide an $\mathsf{NP}$-reduction of $\varphi$ to a formula
$\psi\in\mathsf{ETR}$. Let $E$ contain all $\epsilon$ such that
$\mathbf{P}(\epsilon)$ appears in $\varphi$. Then consider the system of
equations

$\displaystyle\sum_{\delta\in\Delta_{\varphi}}\mathbf{P}(\delta)$
$\displaystyle=1$
$\displaystyle\sum_{\begin{subarray}{c}\delta\in\Delta_{\varphi}\\\
\delta\models\epsilon\end{subarray}}\mathbf{P}(\delta)$
$\displaystyle=\mathbb{P}(\epsilon)\text{ for }\epsilon\in E.$

When plugged in for $\mathbb{P}$, the measure $\mathbb{P}$ satisfies the above
system, so by Lemma 3.13, this system is satisfied by some model
$\mathbb{P}_{\text{small}}$ assigning positive (small-sized) probability to a
subset $\Delta_{\text{small}}\subseteq\Delta_{\varphi}$ of size at most
$|E|\leq|\varphi|$. Let the set $\Delta_{\text{small}}$ and the model
$\mathbb{P}_{\text{small}}$ be the certificate of the
$\mathsf{NP}$-reduction.242424Equivalently, imagine the reduction proceeding
will all possible choices of $\Delta_{\text{small}}$ and
$\mathbb{P}_{\text{small}}$. We will show that some such choice produces a
satisfiable formula $\psi$ if and only if $\varphi$ is satisfiable. The
reduction proceeds by replacing each $\epsilon\in E$ in $\varphi$ with the
$\delta\in\Delta_{\text{small}}$ which imply it, and then checking whether
$\mathbb{P}_{\text{small}}$ is a model of the resulting formula $\psi$. (The
size constraint on $E$ ensures that $\psi$ can be formed in polynomial time.)
If $\varphi$ is satisfiable, $\Delta_{\text{small}}$ and
$\mathbb{P}_{\text{small}}$ exist, so the reduction of $\varphi$ successfully
produces a satisfiable formula $\psi$. Conversely, the success of the
reduction with the witnesses $\Delta_{\text{small}}$ and
$\mathbb{P}_{\text{small}}$ ensures the satisfiability of $\varphi$, since a
model of $\psi$ is a model of $\varphi$.

Let us now show that $\mathsf{SAT}_{\text{ind}}$ is $\exists\mathbb{R}$-hard.
To do this, consider an $\exists\mathbb{R}$-inverse problem instance $\varphi$
with variables $x_{1},...,x_{n}$. It suffices to find a polynomial-time
deterministic reduction to a $\mathsf{SAT}_{\mathrm{ind}}$ instance $\psi$. We
first describe the reduction and then show that it preserves and reflects
satisfiability.

Corresponding to the variables $x_{1},...,x_{n}$, define fresh events
$\delta_{1},...,\delta_{n}\in\sigma(\mathrm{Prop})$. Define fresh, disjoint
events $\delta_{1}^{\prime},...,\delta_{n}^{\prime}$. Let $\psi$ be the
conjunction of the constraints

$\displaystyle\frac{1}{n}\succsim\mathbf{P}(\delta_{i})$
$\displaystyle\succsim\frac{1}{4n}$ $\displaystyle\text{ for }i=1,...,n$
$\displaystyle\mathbf{P}(\delta_{i})\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\textbf{P}(\delta_{j})\land\mathbf{P}(\delta_{i}\land\delta_{j})$
$\displaystyle=\frac{1}{4n^{2}}$ $\displaystyle\text{for }x_{i}\cdot
x_{j}=1\text{ in }\varphi$
$\displaystyle\textbf{P}(\delta_{i}^{\prime})=\textbf{P}(\delta_{i})\land\textbf{P}(\delta_{j}^{\prime})=\textbf{P}(\delta_{j})\land\textbf{P}(\delta_{i}^{\prime}\lor\delta_{j}^{\prime})$
$\displaystyle=\mathbf{P}(\delta_{k})$ $\displaystyle\text{for
}x_{i}+x_{j}=x_{k}\text{ in }\varphi.$

The formula $\psi$ is not yet a formula in $\mathcal{L}_{\text{ind}}$, since
it features constraints of the form
$~{}\mathbf{P}(\alpha)~{}\succsim~{}\nicefrac{{1}}{{N}}$ and
$\nicefrac{{1}}{{N}}~{}\succsim~{}\mathbf{P}(\alpha)$. For any constraint of
the form $\mathbf{P}(\alpha)~{}\succsim~{}\nicefrac{{1}}{{N}}$, replace
$\nicefrac{{1}}{{N}}$ with $\mathbf{P}(\epsilon_{N})$, replace $\alpha$ with
$\alpha\lor\epsilon_{N}$, and require that the fresh events
$\epsilon_{1},...,\epsilon_{N}$ are disjoint with
$\textbf{P}(\lor_{i}\epsilon_{i})=1$ and
$\textbf{P}(\epsilon_{i})=\textbf{P}(\epsilon_{j})$ for $i=1,...,N$.
Similarly, for any constraint of the form
$\nicefrac{{1}}{{N}}~{}\succsim~{}\mathbf{P}(\alpha)$, replace
$\nicefrac{{1}}{{N}}$ with $\mathbf{P}(\epsilon_{N}^{\prime})$, replace
$\alpha$ with $\alpha\land\epsilon_{N}^{\prime}$, and require that the fresh
events $\epsilon_{1}^{\prime},...,\epsilon_{N}^{\prime}$ are disjoint with
$\textbf{P}(\lor_{i}\epsilon_{i}^{\prime})=1$ and
$\textbf{P}(\epsilon_{i}^{\prime})=\textbf{P}(\epsilon_{j}^{\prime})$ for
$i=1,...,N$.

This completes our description of the reduction. The map $x_{i}\mapsto
x_{i}/2n$ sends satisfying solutions of $\varphi$ to those of $\psi$, and the
inverse map $\mathbb{P}(\delta_{i})\mapsto\mathbb{P}(\delta_{i})\cdot 2n$
sends satisfying solutions of $\psi$ to those of $\varphi$. Further, the
operations performed are simple, and the introduced events
$\delta_{i},\delta_{i}^{\prime},\epsilon_{i}$ and the constraints containing
them are short, so the reduction is polynomial-time. ∎

Some authors have suggested that probability logic with conditional
independence terms may be a useful compromise between additive languages built
over linear inequalities and the evidently more complex polynomial languages
(see, e.g., Ivanovska and Giese, 2010). However, the above result shows that
even allowing simple independence statements among events (not to mention
_conditional_ independence statements among _sets of variables_) results in
$\exists\mathbb{R}$-hardness. Thus while probability logic with conditional
independence seems on its face to offer a compromise, it in fact introduces
(at least) the complexity of the maximally algebraically expressive languages
considered in this paper.

The above result shows that reasoning in the seemingly simpler systems
$\mathcal{L}_{\text{ind}}$ and $\mathcal{L}_{\text{confirm}}$ are just as
complex as $\mathcal{L}_{\text{poly}}$, because the former systems allow for
the expression of independence statements. We conclude with two observations
relating to the above result. First, a minimal extension of
$\mathcal{L}_{\text{comp}}$, discussed by Fine, (1973), remains
$\mathsf{NP}$-complete, even though it includes some mention of conditional
probability:

######  Definition 4.10.

Fix a nonempty set of proposition letters $\mathsf{Prop}$. The language
$\mathcal{L}_{\text{same cond}}$ is defined:

$\displaystyle\varphi\in\mathcal{L}_{\text{same cond}}$
$\displaystyle\iff\varphi=\mathbf{P}(\alpha|\beta)\succsim\mathbf{P}(\alpha^{\prime}|\beta)\,|\,\neg\varphi\,|\,\varphi\land\psi$
$\displaystyle\text{ for any
}\alpha,\alpha^{\prime},\beta\in\sigma(\mathsf{Prop})$

######  Fact 4.11.

$\mathsf{SAT}_{\text{same cond}}$ is $\mathsf{NP}$-complete.

###### Proof.

Hardness follows immediately from Theorem 7 and the observation that
$\mathcal{L}_{\text{same cond}}$ is at least as expressive as
$\mathcal{L}_{\text{comp}}$. To show completeness, take any
$\varphi\in\mathcal{L}_{\text{same cond}}$, and let $\psi$ be the result of
replacing each term $\mathbf{P}(\alpha|\gamma)$ in $\varphi$ with
$\mathbf{P}(\alpha\land\gamma)$. We claim that $\varphi$ and $\psi$ are
equisatisfiable. Indeed, for any measure $\mathbb{P}$, we have:

$\mathbb{P}(\alpha\land\gamma)\geq\mathbb{P}(\beta\land\gamma)\iff\mathbb{P}(\alpha|\gamma)\geq\mathbb{P}(\beta|\gamma).$

Thus the inequalities mentioned in $\varphi$ hold precisely when those
mentioned in $\psi$ hold. ∎

Second, whereas the above theorem characterizes the complexity of reasoning
about independence among events, the following result due to Lang et al.,
(2002) characterizes the complexity of reasoning about independence among two
random variables:

######  Theorem 11 (Lang et al., (2002)).

Determining independence of two random variables is complete for the
complexity class $\mathsf{coDP}$, the complement of $\mathsf{DP}$, the class
of all languages $\mathcal{L}$ such that
$\mathcal{L}=\mathcal{L}_{1}\cap\mathcal{L}_{2}$, where $\mathcal{L}_{1}$ is
in $\mathsf{NP}$ and $\mathcal{L}_{2}$ is in $\mathsf{coNP}$ (the complement
of $\mathsf{NP}$).

Lang et al., (2002) also characterize the complexity of several other tasks
concerning the (conditional) independence of sets of random variables.

##  5 Summary: The Additive-Multiplicative Divide

We identified an important dividing line in the space of probability logics,
based on the distinction between purely additive and multiplicative systems.
Additive systems can encode reasoning about systems of linear inequalities;
multiplicative systems can encode reasoning about polynomial inequality
systems that include at least quadratic constraints. The distinction between
additive and multiplicative systems robustly tracks a difference in
computational complexity: while the former are $\mathsf{NP}$-complete, the
latter are $\exists\mathbb{R}$-complete. As a consequence, inference involving
(implicitly) multiplicative notions is inherently more complex (assuming
$\mathsf{NP}\neq\exists\mathbb{R}$): this applies to various intuitively
‘qualitative’ systems for reasoning about independence
($\mathcal{L}_{\text{ind}}$), confirmation ($\mathcal{L}_{\text{confirm}}$),
or comparisons of conditional probability ($\mathcal{L}_{\text{cond}}$).

As we saw, proving completeness for the additive and multiplicative systems
involves different methods. While completeness for additive systems relies on
linear algebra (and hyperplane separation theorems or variable elimination
methods), the natural mathematical setting for multiplicative systems is
semialgebraic geometry (and completeness relies on versions of the real
Positivstellensatz).

Importantly, both in the additive and multiplicative settings, systems with
explicitly ‘numerical’ operations are more expressive and admit finite
axiomatizations, while incurring no cost in complexity. By contrast, even the
most paradigmatically ‘qualitative’ logic of unconditional comparative
probability ($\mathcal{L}_{\text{comp}}$) is not finitely
axiomatizable.252525A similar phenomenon occurs in other non-numerical systems
for probabilistic reasoning. See, for example, results on the non-finite
axiomatizability of conditional independence for discrete random variables
(Studený,, 1992) and for Gaussian random variables (Sullivant,, 2009). Thus,
from a logical perspective, there is little to be gained from restricting
attention, in applications of probability logics, to syntactically
‘qualitative’ systems without arithmetical operations.

(additive)(multiplicative)$\mathsf{NP}$-complete$\exists\mathbb{R}$-complete(no
explicit arithmetic)(explicit
arithmetic)$\mathcal{L}_{\mathrm{comp}}$$\mathcal{L}_{\mathrm{cond}}$$\mathcal{L}_{\mathrm{add}}$$\mathcal{L}_{\mathrm{poly}}$
Figure 6: The additive-multiplicative divide.

These results also illustrate how ease of elicitation and complexity of
inference might come apart. As we noted, the use of comparative probability is
sometimes motivated by the view that ‘qualitative’ judgments are more
intuitive, or easier to elicit, than explicitly ‘quantitative’ ones. While
these claims are somewhat difficult to substantiate (see the discussion below
in Section 6.2), our results give a concrete sense in which intuitions about
the ease of elicitation of certain comparative judgments do not reflect the
complexity of _inference_ involving these judgments. Consider, for example,
the case of $\mathcal{L}_{\text{cond}}$ and $\mathcal{L}_{\text{add}}$. While
at first blush there may be something more immediate about comparisons of
conditional probabilities that are not explicitly numerical, as opposed to
comparisons expressible in $\mathcal{L}_{\text{add}}$ (‘is $A$ twice as likely
as $B$?’), our results suggest that reasoning with the former is more complex
than reasoning with the latter.

While the distinction between additive and multiplicative systems is an
informative dividing line that is useful in classifying the landscape of
probability logics, investigating this divide also illustrates that the very
distinction between qualitative and quantitative reasoning remains somewhat
elusive. Certainly, _prima facie_ natural ways to formulate the distinction,
based on the simplicity and intuitiveness of comparative judgments, or on the
explicit presence of arithmetical operators, do not seem to capture any clear
or robust distinction that tracks properties of logical interest such as
complexity, expressivity, and axiomatizability. We are thus left with the
question of how to give concrete substance to the often invoked, but never
delineated, qualitative/quantitative distinction: are there any structural
properties of inference that are characteristic of _qualitative_ reasoning in
probabilistic contexts? We turn to this question next.

##  6 What is the Quantitative-Qualitative Distinction?

Before concluding we briefly consider the larger conceptual questions with
which we began. How might we understand the prevalent distinction between
quantitative and qualitative formulations of probabilistic principles and
inference patterns, particularly in light of the landscape of systems we have
explored in the present work? We begin by entertaining several suggestions
from the literature.

###  6.1 Previous Suggestions

As briefly discussed in the introduction, gestures toward a distinction
between qualitative and quantitative formulations of probability can be found
throughout the literature, going back at least as far as Keynes, (1921). In
the seminal work by de Finetti on comparative probability, the express goal
was to ‘start out with only qualitative notions’ before ‘one arrives at a
quantitative measure of probability’ (de Finetti,, 1937, p. 101). However,
while the distinction often arises as informal motivation, there has been less
explicit discussion of what exactly the distinction might be. A survey of the
literature reveals two families of proposals. _Syntactic_ proposals locate the
distinction in formal syntax, whereas _semantic_ proposals focus instead on
the variety of models a system admits.

####  6.1.1 Syntactic Proposals

The passage quoted above from de Finetti, (1937) invites a view on which the
distinction tracks whether _numbers_ , or more generally _arithmetical
concepts_ , appear explicitly in our formal language. Comparative probability
languages like $\mathcal{L}_{\text{comp}}$ and perhaps also
$\mathcal{L}_{\text{cond}}$, on this view, are typically qualitative, since
there are no numerical terms or operations. In a recent paper, Delgrande et
al., (2019) state this view clearly:

> ‘What distinguishes qualitative from quantitative probability (truth valued)
> logics is that qualitative probability logics do not employ quantities or
> arithmetic operations in the syntax, and the informal reading of the
> qualitative probability formulas do not require a quantitative
> interpretation.’

On this picture, comparative judgments do not involve any explicit reference
to numbers, so such systems would count as qualitative. By contrast, a
language like $\mathcal{L}_{\text{add}}$ would presumably be considered
quantitative, since it involves an explicit addition-like
operator.262626Notably, the system introduced by Delgrande et al., (2019) also
employs an ‘addition-like’ operator, allowing for a simple finite
axiomatization of what is essentially our language $\mathcal{L}_{\text{add}}$.
The target in this paper rather appears to be the extension from Fagin et al.,
(1990) that includes explicit constant terms for integers.

While there may be extra-logical reasons to focus attention on qualitative
systems in this sense, such restrictions come at a logical price. At no
increase in reasoning complexity, the presence of arithmetical functions
affords simple finite axiomatizations, as well as greater expressivity. We
return to potential extra-logical, viz. empirical, motivations below in §6.2.

####  6.1.2 Semantic Proposals

An alternative way of drawing the distinction appeals not to the syntax, but
to the semantics of the system. The quotation from Delgrande et al., (2019)
also gestures at such a view, according to which qualitative systems do not
_require_ a quantitative interpretation. The suggestion seems to be that
qualitative systems are sufficiently general that they also admit
interpretations that do not involve numbers in any explicit way.

All of the systems we studied here are interpreted relative to a probability
space $(\Omega,\mathcal{F},\mathbb{P})$. But some of them also admit
alternative interpretations. Take, for instance, $\mathcal{L}_{\text{add}}$.
Consider any totally ordered commutative monoid $(M;\oplus,\sqsupseteq)$ that
also satisfies the following two conditions:

  1. 1.

Double Cancellation: if $a\oplus e\sqsupseteq c\oplus f$ and $b\oplus
f\sqsupseteq d\oplus e$, then $a\oplus b\sqsupseteq c\oplus d$;

  2. 2.

Contravenience: if $a\oplus b\sqsupseteq c\oplus d$ and $d\sqsupseteq b$, then
$a\sqsupseteq c$.

Then our earlier results imply:

######  Corollary 6.1.

Consider any mapping $[\\![\mbox{\em$\cdot$\/}]\\!]$ from
$\sigma(\mathsf{Prop})$ to a totally ordered commutative monoid
$(M;\oplus,\sqsupseteq)$. If $[\\![\mbox{\em$\cdot$\/}]\\!]$ also satisfies
the following three conditions:

  1. 1.

Monotonicity:
$[\\![\mbox{\em$\alpha$\/}]\\!]\sqsupseteq[\\![\mbox{\em$\beta$\/}]\\!]$,
whenever $\models\beta\rightarrow\alpha$,

  2. 2.

Non-triviality:
$[\\![\mbox{\em$\bot$\/}]\\!]\not\sqsupseteq[\\![\mbox{\em$\top$\/}]\\!]$, and

  3. 3.

Additivity:
$[\\![\mbox{\em$\alpha\vee\beta$\/}]\\!]=[\\![\mbox{\em$\alpha$\/}]\\!]\oplus[\\![\mbox{\em$\beta$\/}]\\!]$,
whenever $\models\beta\rightarrow\neg\alpha$

then we will obtain completeness for the system $\mathsf{AX}_{\text{add}}$
(and hence also $\mathsf{AX}_{\text{comp}}$).

The assumptions above are enough to guarantee soundness of
$\mathsf{AX}_{\text{base}}$, as well as axioms $\mathsf{Add}$,
$\mathsf{2Canc}$ and $\mathsf{Contr}$. The remaining three axioms of
$\mathsf{AX}_{\text{add}}$ follow from the fact that $M$ is a totally ordered
commutative monoid. Completeness will follow immediately, since we always have
a countermodel in the non-negative rationals $(\mathbb{Q}^{+};+,\geq)$, by
Theorem 2. The same obviously applies to the smaller system,
$\mathsf{AX}_{\text{comp}}$.272727This observation mirrors the classic result
of Gurevich and Kokorin, (1963), showing that every two (totally) ordered
Abelian groups have the same existential (or universal) first-order theory.

However, there are also other commutative monoids that do not explicitly
involve numbers but still satisfy Double Cancellation and Contravenience. For
example, we could take $M=\\{a\\}^{*}$ to be the set of all finite strings
over a unary alphabet (the ‘free monoid’ over $\\{a\\}$), with $\oplus$ string
concatenation and $\sqsupseteq$ the relation of string containment. Since
$x\mapsto kx$ for any positive integer $k$ is an embedding of
$(\mathbb{Q}^{+};+,\geq)$ to itself, we can always find countermodels in
$(\mathbb{N};+,\geq)$, which is in turn isomorphic to
$(\\{a\\}^{*};\oplus,\sqsupseteq)$, so we have:

######  Corollary 6.2.

$\mathsf{AX}_{\text{add}}$ (and $\mathsf{AX}_{\text{comp}}$) is complete with
respect to interpretations in $(\\{a\\}^{*};\oplus,\sqsupseteq)$.

On this alternative interpretation, the ‘probability’ of an event is taken to
be simply a string in unary.

To the extent that the multiplicative systems do not enjoy such alternative
interpretations, our division appears to harmonize with this distinction. We
leave as an open question whether systems like $\mathsf{AX}_{\text{poly}}$ can
be interpreted in models that are not (isomorphic to some sub-semiring of) the
real numbers or the unit interval.

A more radical way of drawing the distinction is to insist not that a system
possess non-numerical models in order to be qualitative, but that the system
have no straightforward models that _are_ numerical. For instance, in the
literature on uncertain reasoning, systems that license inferences like
$A,B\;|\\!\\!\\!\sim A\wedge B$ have been deemed qualitative, since they
correspond to intuitive, non-numerical patterns, but are incompatible with
straightforward probabilistic interpretations (e.g., according to which $A$ is
accepted just in case $\mathbb{P}(A)>\theta$ for some threshold $\theta$). For
instance, Hawthorne and Makinson, (2007) give voice to this perspective when
they write:

> ‘Broadly speaking, there are two ways of approaching the formal analysis of
> uncertain reasoning: quantitatively, using in particular probability
> relationships, or by means of qualitative criteria. As is widely recognized,
> the consequence relations that are generated in these two ways behave quite
> differently.’

Systems of non-monotonic reasoning can often be given quantitative
probabilistic interpretations (see, e.g., Pearl, 1989), and there are various
ways of ameliorating the inferential tensions in these contexts (Leitgeb,,
2017; Mierzewski,, 2020). But such resolution usually comes at the expense of
quantitative granularity typical of numerical probabilistic reasoning. In any
case, on this way of drawing the distinction, none of the systems we have
studied in the present work would count as qualitative, even the basic
comparative system $\mathsf{AX}_{\text{comp}}$.

###  6.2 Empirical Issues

Some of the motivations for less quantitative formulations of probability come
not from issues of logic and complexity, but rather from empirical concerns. A
common thought is that eliciting comparative judgments may be in some way more
tractable. Relatedly, numerous authors have suggested that quantitative
judgments may not always be empirically meaningful in the same way that
qualitative judgments may be.

The intuition behind this motivation is clear enough. Comparative judgments
introspectively appear easier to make than numerical comparisons, and echoing
the earlier suggestions by Keynes, Koopman and others, some more recent
authors have concluded that they are in some sense more psychologically ‘real’
(e.g., Stefánsson, 2017). Indeed, it has long been appreciated that binary
comparative judgments in general can be more stable or reliable than absolute
judgments, even to the extent that some recent researchers advocate replacing
the latter with the former to mitigate noise in judgment (Kahneman et al.,,
2021). Such judgments play a central role in algorithms for probabilistic
inference as well, under the assumption that probabilistic
comparisons—especially between hypothesis that are ‘nearby’ in a larger state
space—are relatively easy (Sanborn and Chater,, 2016, p. 887).

Similar arguments about the ease and naturalness of qualitative judgments have
been marshalled for conditional independence relationships, purportedly
arising from even more fundamental qualitative causal intuitions (Pearl,,
2009, p. 21).

####  6.2.1 Direct Measurements of Probability

For the specific problem of eliciting subjective probabilities, not only is
stability across time and contexts important—it is also significant that the
whole pattern of attitudes be consistent with at least one probabilistic
representation in the first place. It was pointed out already by Suppes,
(1974) that verifying this in the purely comparative setting, even for a small
number of basic events, involves a combinatorial explosion of pairs to check.
Worse yet, we now have overwhelming evidence (e.g., from the long line of work
starting with Tversky and Kahneman, 1974) that ordinary judgments about
comparative probability routinely violate even the most basic axioms, such as
$\mathsf{Dist}$. Similar experimental patterns confront the logic of
(conditional) independence (e.g., Rehder, 2014). These considerations, at the
very least, put pressure on any claim to the effect that qualitative judgments
enjoy special empirical tractability.

Once we abandon the ambition of eliciting coherent, fully specified patterns
of judgments, the numerical/non-numerical distinction again begins to appear
somewhat arbitrary. Contemporary methods for probability elicitation tend to
be partial, and they handle numerical judgments in a similar way to their
treatment of purely comparative judgments (e.g., Lambert et al., 2008). In the
behavioral sciences, probabilities are commonly measured on continuous sliding
scales, or on 7-point Likert scales (e.g., ‘extremely unlikely’ to ‘extremely
likely’), often with a background assumption that such responses will be noisy
reflections of an underlying psychological mechanism, estimable from many
samples of the population (see, e.g., Luce and Suppes, 1965; Icard, 2016;
Sanborn and Chater, 2016 for discussion). From this perspective, comparative
judgments may tend to be robust because they are often relatively insensitive
to random perturbations. At the same time, we might expect a claim that ‘$A$
and $B$ are _equally likely_ ’ to be more fickle than a claim like, ‘$C$ is
_more than twice as likely_ as $D$’. So there again may be nothing distinctive
about non-numerical comparisons in this regard.

####  6.2.2 Indirect Measurement via Preference

A prominent way of thinking about subjective probability takes it to be not a
primitive notion, but rather derivative from an agent’s preferences over
‘gambles’ or ‘acts’. On this alternative view such preferences, as revealed in
choice behavior, form the empirical basis of probability attributions. As long
as the pattern of choices satisfies certain sets of axioms, a representation
in terms of (fully quantitative, and typically unique) probabilities together
with utilities is guaranteed (e.g., as in Savage’s 1954 classic
axiomatization). These axioms tend to be quite strong, and there have been
countless criticisms of them, on both descriptive and normative grounds.
Though interesting variants and weakenings have been proposed (e.g., Joyce,
2009; Gaifman and Liu, 2018), it appears that the assumptions required will be
at least as demanding as those made in the purely probabilistic case.

Indeed, in the preferential setting there is a precise sense in which
comparative probability judgments emerge as a special case of uncertain
gambles. We would say that an agent considers $\alpha$ more likely than
$\beta$ if they prefer a gamble that returns a good outcome in case of
$\alpha$ to one that returns the same good outcome in case of $\beta$. Axioms
can be stated to guarantee that the resulting order will be probabilistically
representable (see Krantz et al., 1971, §5.2.4), though, yet again, even the
most basic of these have been questioned. For instance, in Ellsberg’s (1961)
celebrated counterexample to Savage’s sure-thing principle, people tend to
prefer a gamble on $A$ to one on $B$, while simultaneously preferring a gamble
on $B\vee C$ to one on $A\vee C$, where $C$ is incompatible with $A$ and with
$B$. This leads to a blatant violation of quasi-additivity
($\mathsf{Quasi^{\prime}}$).

Nonetheless, if one is willing to weaken the axioms required to guarantee
probabilistic representability (or simply disregard their systematic
violation), these basic gambles can be elaborated to extract probability
judgments with greater numerical content, including ratio comparisons (typical
of $\mathcal{L}_{\text{add}}$ and beyond). The basic idea, following Ramsey,
(1926) (see also Davidson and Suppes, 1956; Elliott, 2017, _inter alia_), is
to begin with a way of eliciting meaningful utilities for outcomes, and then
to use these utilities to measure probability judgments. For instance, if it
can be determined that an agent judges outcome $O_{2}$ be to at least twice as
desirable as $O_{1}$, then someone who prefers a gamble returning $O_{1}$ if
$\alpha$, to one returning $O_{2}$ if $\beta$, might be taken to judge
$\alpha$ more than _twice as likely_ as $\beta$.

Could such methods be employed to determine not just additive constraints on
probabilities, but also multiplicative constraints? Supposing we could
establish that the utility of $O_{2}$ were greater than that of $O_{1}$
_squared_ , for instance, we might conclude that $\alpha$ has probability
greater than the square of $\beta$’s probability. The problem with this
suggestion is that most approaches to utility, including those that descend
from Ramsey, (1926), assume that utilities are meaningful only up to linear
transformation, so such conclusions would not be well defined. Thus, even in
this context of empirical questions, we see that the natural dividing line may
not be numerical or quantitative constraints per se, but rather additive
versus multiplicative constraints.

##  7 Conclusion and Open Questions

Through a broad distinction between additive and multiplicative formalisms for
probabilistic reasoning, we have explored the landscape of probability logics
with respect to fundamental questions about expressivity, computational
complexity, and axiomatization. What emerges is a remarkably robust divide
that cross-cuts some tempting ways of dividing the space based on intuitions
about quantitative versus qualitative representation and reasoning. In
addition to the technical contributions summarized above in §5, we also
canvassed some of the empirical considerations that have motivated special
attention to comparative and other ‘purely qualitative’ judgments. At present
it is not clear that the latter enjoy any distinctive empirical status, and if
anything, the relevant empirical boundaries may better track the additive-
multiplicative distinction that has been our focus here.

It is certainly not an aim of this paper to discourage the use and exploration
of qualitative probability. On the contrary, as we have discussed, such
systems present rich opportunities for systematic logical investigation.
Moreover, a number of recent authors have found such languages useful for
stating and evaluating epistemological principles in a general and relatively
neutral manner (e.g., Narens, 2007; Eva, 2019; Liu, 2020; Mayo-Wilson and
Saraf, 2020, _inter multa et alia_). This is especially evident in settings
where agreement with a probability measure is not assumed, or is even
precluded (e.g., Dubois and Prade, 1988; DiBella, 2022). These considerations
are rather different from many of the original motivations that prompted study
of such systems, viz. simplicity and empirical tractability. From a logical
perspective—concerning complexity, axiomatizability, and expressivity—and
potentially also from an empirical perspective, prohibition on the use of
simple numerical primitives appears Procrustean.

A number of significant technical questions and directions on this subject
merit further exploration. In addition to the outstanding issue of
substantiating Domotor’s (1969) argument for representation of comparative
conditional probability (represented here as $\mathcal{L}_{\text{cond}}$), we
also mention the following directions:

  * •

Many authors have argued that the comparability of $\succsim$ should be
rejected, on both normative and empirical grounds (Keynes,, 1921; Fine,, 1973;
Walley,, 1991; Gaifman,, 2009; Liu,, 2020). All of the systems presented in
this paper could alternatively be interpreted relative to _sets_ of
probability measures. Logical systems for such settings have received
considerable investigation (see, e.g., Ding et al., 2021 for an overview). It
seems plausible that many of the results here would extend with little change;
however, our proof methods often employed normal forms whose exact character
depended on comparability. Working through this setting in detail would be
worthwhile.

  * •

It is easy to imagine natural extensions of the languages considered here,
including varieties of explicit quantification. For instance, Speranski,
(2017) studies probability logics extending (what we here called)
$\mathcal{L}_{\text{add}}$ with quantification over events, while Abadi and
Halpern, (1994) explore a range of _first order_ extensions of
$\mathcal{L}_{\text{add}}$ and (what we called) $\mathcal{L}_{\text{poly}}$
with quantification over both field terms and (a second sort of) objects.
Generally speaking, these extensions result in a significant complexity
increases, leading to undecidability (in the best cases),
$\Pi^{1}_{1}$-hardness, and even $\Pi^{1}_{\infty}$-hardness. However, there
are ways of curtailing this complexity (e.g., by restricting to bounded finite
domains), and it could be enlightening to investigate our more refined space
of languages in those settings.

  * •

A potentially more modest, but quite useful extension to any of these systems
would be to add _exponentiation_ , e.g., the function $e^{x}$. As such systems
would also encode logarithms, this would allow reasoning about (conditional)
entropy as well. It is unclear at present whether adding exponentiation to
$\mathcal{L}_{\text{poly}}$ would even result in a decidable system. By a
theorem of Macintyre and Wilkie, (1995), a positive answer to this question
would also settle Tarski’s (1951) well known ‘exponential function problem’
which has been open since the 1940s. Whether the problem may be easier for
some weaker systems we have considered here remains to be seen. Moreover, it
may be feasible to address questions of axiomatizability without solving that
outstanding open problem.

These are just some of the questions that will need to be answered before we
have a fully comprehensive understanding of the space of natural probabilistic
languages.

## References

  * Abadi and Halpern, (1994) Abadi, M. and Halpern, J. Y. (1994).  Decidability and expressiveness for first-order logics of probability.  Information and Computation, 112:1–36.
  * Abrahamsen et al., (2018) Abrahamsen, M., Adamaszek, A., and Miltzow, T. (2018).  The art gallery problem is $\exists\mathbb{R}$-complete.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 65–73.
  * Abrahamsen et al., (2021) Abrahamsen, M., Kleist, L., and Miltzow, T. (2021).  Training neural networks is $\exists\mathbb{R}$-complete.  In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS).
  * Aczél et al., (1960) Aczél, J., Pickert, G., and Radó, F. (1960).  Nomogramme, gewebe, und quasigruppen.  Mathematica (Cluj), 2(25):5–24.
  * Bilò and Mavronicolas, (2017) Bilò, V. and Mavronicolas, M. (2017).  $\exists\mathbb{R}$-complete decision problems about symmetric Nash equilibria in symmetric multi-player games.  In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
  * Burgess, (2010) Burgess, J. P. (2010).  Axiomatizing the logic of comparative probability.  Notre Dame Journal of Formal Logic, 51(1):119–126.
  * Cardinal, (2015) Cardinal, J. (2015).  Computational geometry column 62.  ACM SIGACT News, 46(4):69–78.
  * Carnap, (1950) Carnap, R. (1950).  Logical Foundations of Probability.  University of Chicago Press.
  * ten Cate et al., (2013) ten Cate, B., Kolaitis, P. G., and Othman, W. (2013).  Data exchange with arithmetic operations.  In Proceedings of the 16th International Conference on Extending Database Technology, pages 537–548.
  * Chvátal, (1983) Chvátal, V. (1983).  Linear programming.  Macmillan.
  * Cook, (1971) Cook, S. A. (1971).  The complexity of theorem-proving procedures.  In Proceedings of the third annual ACM symposium on Theory of computing, pages 151–158.
  * Davidson and Suppes, (1956) Davidson, D. and Suppes, P. (1956).  A finitistic treatment of subjective probability and utility.  Econometrica, 24(3):264–275.
  * Delgrande et al., (2019) Delgrande, J. P., Renne, B., and Sack, J. (2019).  The logic of qualitative probability.  Artificial Intelligence, 275:457–486.
  * DiBella, (2022) DiBella, N. (2022).  Fair infinite lotteries, qualitative probability, and regularity.  Philosophy of Science.  forthcoming.
  * Ding et al., (2020) Ding, Y., Harrison-Trainor, M., and Holliday, W. H. (2020).  The logic of comparative cardinality.  The Journal of Symbolic Logic, 83(3):972–1005.
  * Ding et al., (2021) Ding, Y., Holliday, W. H., and Icard, T. F. (2021).  Logics of imprecise comparative probability.  International Journal of Approximate Reasoning, 132:154–180.
  * Domotor, (1969) Domotor, Z. (1969).  Probabilistic relational structures and their applications.  Technical report 144. Institute for Mathematical Studies in the Social Sciences, Stanford University.
  * Dubois and Prade, (1988) Dubois, D. and Prade, H. (1988).  Possibility Theory.  Plenum Press, New York.
  * Elliott, (2017) Elliott, E. (2017).  Ramsey without ethical neutrality: A new representation theorem.  Mind, 126(501):1–51.
  * Ellsberg, (1961) Ellsberg, D. (1961).  Risk, ambiguity, and the Savage axioms.  Quarterly Journal of Economics, 75(4):643–669.
  * Erickson et al., (2020) Erickson, J., Van Der Hoog, I., and Miltzow, T. (2020).  Smoothing the gap between NP and $\exists\mathbb{R}$.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1022–1033. IEEE.
  * Eva, (2019) Eva, B. (2019).  Principles of indifference.  Journal of Philosophy, 116(7):390–411.
  * Fagin et al., (1990) Fagin, R., Halpern, J. Y., and Megiddo, N. (1990).  A logic for reasoning about probabilities.  Information and Computation, 87(1-2):78–128.
  * Fine, (1973) Fine, T. L. (1973).  Theories of probability: An examination of foundations.  Academic press.
  * de Finetti, (1937) de Finetti, B. (1937).  La prévision: ses lois logiques, ses sources subjectives.  Annales de l’Institut Henri Poincaré, 7:1–68.
  * Fishburn, (1996) Fishburn, P. C. (1996).  Finite linear qualitative probability.  Journal of Mathematical Psychology, 40:64–77.
  * Fishburn, (1997) Fishburn, P. C. (1997).  Failure of cancellation conditions for additive linear orders.  Journal of Combinatorial Designs, 5(5):353–365.
  * Franklin, (2001) Franklin, J. (2001).  The Science of Conjecture: Evidence and Probability before Pascale.  The Johns Hopkins University Press.
  * Gaifman, (2009) Gaifman, H. (2009).  Interview.  In Hájek, A. and Hendricks, V. F., editors, Probability and Statistics: 5 Questions. Automatic Press.
  * Gaifman and Liu, (2018) Gaifman, H. and Liu, Y. (2018).  A simpler and more realistic subjective decision theory.  Synthese, 195(10):4205–4241.
  * Gärdenfors, (1975) Gärdenfors, P. (1975).  Qualitative probability as an intensional logic.  Journal of Philosophical Logic, 4(2):171–185.
  * Gurevich and Kokorin, (1963) Gurevich, Y. S. and Kokorin, A. I. (1963).  Universal equivalence of ordered abelian groups.  Algebra i Logika. Sem., 2(1):37–39.  (Russian).
  * Hawthorne and Makinson, (2007) Hawthorne, J. and Makinson, D. C. (2007).  The quantitative/qualitative watershed for rules of uncertain inference.  Studia Logica, 86(2):247–297.
  * van der Hoek, (1996) van der Hoek, W. (1996).  Qualitative Modalities.  International Journal of Uncertainty, Fuzziness, and Knowledge-Based Systems, 4(1):45–59.
  * Ibeling and Icard, (2020) Ibeling, D. and Icard, T. (2020).  Probabilistic reasoning across the causal hierarchy.  In Proceedings of the AAAI Conference on Artificial Intelligence, pages 10170–10177.
  * Icard, (2016) Icard, T. F. (2016).  Subjective probability as sampling propensity.  The Review of Philosophy and Psychology, 7(4):863–903.
  * Ivanovska and Giese, (2010) Ivanovska, M. and Giese, M. (2010).  Probabilistic logic with conditional independence formulae.  In Proceedings of the European Conference on Artificial Intelligence (ECAI).
  * Joyce, (2009) Joyce, J. M. (2009).  The Foundations of Causal Decision Theory.  Cambridge University Press.
  * Kahneman et al., (2021) Kahneman, D., Sibony, O., and Sunstein, C. R. (2021).  Noise: A Flaw in Human Judgment.  Little, Brown & Co.
  * Keynes, (1921) Keynes, J. M. (1921).  A Treatise on Probability.  Macmillan.
  * Kolmogorov, (1933) Kolmogorov, A. N. (1933).  Grundbegriffe der Wahrscheinlichkeitsrechnung.  Springer.
  * Konek, (2019) Konek, J. (2019).  Comparative probabilities.  In Weisberg, J. and Pettigrew, R., editors, The Open Handbook of Formal Epistemology, pages 267–348. Philpapers.
  * Koopman, (1940) Koopman, B. O. (1940).  The axioms and algebra of intuitive probability.  Annals of Mathematics, pages 269–292.
  * Kraft et al., (1959) Kraft, C. H., Pratt, J. W., and Seidenberg, A. (1959).  Intuitive probability on finite sets.  The Annals of Mathematical Statistics, 30(2):408–419.
  * Krantz et al., (1971) Krantz, D. H., Luce, R. D., Suppes, P., and Tversky, A. (1971).  Foundations of Measurement, volume 1.  Academic Press, New York.
  * Lambert et al., (2008) Lambert, N., Pennock, D. M., and Shoham, Y. (2008).  Eliciting properties of probability distributions.  In Proceedings of the 9th ACM Conference on Electronic Commerce (EC), pages 129–138.
  * Lang et al., (2002) Lang, J., Liberatore, P., and Marquis, P. (2002).  Conditional independence in propositional logic.  Artificial Intelligence, 141(1-2):79–121.
  * Leitgeb, (2017) Leitgeb, H. (2017).  The Stability of Belief.  Oxford University Press.
  * Liu, (2020) Liu, Y. (2020).  Incomplete preference and indeterminate comparative probabilities.  The British Journal for the Philosophy of Science.  Forthcoming.
  * Luce and Suppes, (1965) Luce, R. D. and Suppes, P. (1965).  Preference, utility, and subjective probability.  In Luce, R. D., Bush, R. R., and Galanter, E. H., editors, Handbook of Mathematical Psychology, volume 3, pages 249–410. Wiley.
  * Macintyre and Wilkie, (1995) Macintyre, A. and Wilkie, A. J. (1995).  On the decidability of the real exponential field.  In Odifreddi, P., editor, Kreiseliana. About and Around Georg Kreisel, pages 441–467. A. K. Peters.
  * Mayo-Wilson and Saraf, (2020) Mayo-Wilson, C. and Saraf, A. (2020).  Qualitative robust Bayesianism and the likelihood principle.  Manuscript, University of Washington.
  * Mierzewski, (2020) Mierzewski, K. (2020).  Probabilistic stability, AGM revision operators and maximum entropy.  The Review of Symbolic Logic.  Forthcoming.
  * Mossé et al., (2022) Mossé, M., Ibeling, D., and Icard, T. (2022).  Is causal reasoning harder than probabilistic reasoning?  The Review of Symbolic Logic.  Forthcoming.
  * Motzkin, (1951) Motzkin, T. (1951).  Two consequences of the transposition theorem on linear inequalities.  Econometrica, 19(2):184–185.
  * Narens, (1980) Narens, L. (1980).  On qualitative axiomatizations for probability theory.  Journal of Philosophical Logic, 9:143–151.
  * Narens, (2007) Narens, L. (2007).  Theories of Probability: an Examination of Logical and Qualitative Foundations.  World Scientific Publishing Company.
  * Pearl, (1989) Pearl, J. (1989).  Probabilistic semantics for non-monotonic reasoning: A survey.  In Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 505–516.
  * Pearl, (2009) Pearl, J. (2009).  Causality.  Cambridge University Press.
  * Perović et al., (2008) Perović, A., Ognjanović, Z., Rašković, M., and Marković, Z. (2008).  A probabilistic logic with polynomial weight formulas.  In International Symposium on Foundations of Information and Knowledge Systems, pages 239–252. Springer.
  * Ramsey, (1926) Ramsey, F. P. (1926).  Truth and probability.  In Braithwaite, R. B., editor, Foundations of Mathematics and Other Essays.
  * Rehder, (2014) Rehder, B. (2014).  Independence and dependence in human causal reasoning.  Cognitive Psychology, 17:54–107.
  * Rényi, (1955) Rényi, A. (1955).  On a new axiomatic theory of probability.  Acta Mathematica Hungarica, 6(3):285–335.
  * Ruiz-Vanoye et al., (2011) Ruiz-Vanoye, J. A., Pérez-Ortega, J., Díaz-Parra, O., Frausto-Solís, J., Huacuja, H. J. F., Cruz-Reyes, L., et al. (2011).  Survey of polynomial transformations between NP-complete problems.  Journal of computational and applied mathematics, 235(16):4851–4865.
  * Sanborn and Chater, (2016) Sanborn, A. N. and Chater, N. (2016).  Bayesian brains without probabilities.  Trends in Cognitive Sciences, 20(12):883–893.
  * Savage, (1954) Savage, L. J. (1954).  The Foundations of Statistics.  John Wiley and Sons.
  * Schaefer, (2009) Schaefer, M. (2009).  Complexity of some geometric and topological problems.  In International Symposium on Graph Drawing, pages 334–344. Springer.
  * Schaefer, (2013) Schaefer, M. (2013).  Realizability of graphs and linkages.  In Thirty Essays on Geometric Graph Theory, pages 461–482. Springer.
  * Schrijver, (1998) Schrijver, A. (1998).  Theory of Linear and Integer Programming.  John Wiley & Sons.
  * Scott, (1964) Scott, D. (1964).  Measurement structures and linear inequalities.  Journal of Mathematical Psychology, 1(2):233–247.
  * Scott and Krauss, (1966) Scott, D. and Krauss, P. (1966).  Assigning probabilities to logical formulas.  Studies in Logic and the Foundations of Mathematics, 43:219–264.
  * Segerberg, (1971) Segerberg, K. (1971).  Qualitative probability in a modal setting.  Proceedings of the Second Scandinavian Logic Symposium, 63:341–352.
  * Speranski, (2017) Speranski, S. O. (2017).  Quantifying over events in probability logic: An introduction.  Mathematical Structures in Computer Science, 27(8):1581–1600.
  * Stefánsson, (2017) Stefánsson, H. O. (2017).  What is ‘real’ in probabilism?  Australasian Journal of Philosophy, 95(3):573–587.
  * Stengle, (1974) Stengle, G. (1974).  A nullstellensatz and a positivstellensatz in semialgebraic geometry.  Mathematische Annalen, 207(2):87–97.
  * Studený, (1992) Studený, M. (1992).  Conditional independence relations have no finite complete characterization.  In Information Theory, Statistical Decision Functions and Random Processes., pages 377–396. Transactions of the 11th Prague Conference vol. B (S. Kubik, J.A. Visek eds.).
  * Sullivant, (2009) Sullivant, S. (2009).  Gaussian conditional independence relations have no finite complete characterization.  Journal of Pure and Applied Algebra, 213:1502–1506.
  * Suppes, (1974) Suppes, P. (1974).  The measurement of belief.  The Journal of the Royal Statistical Society, Series B, 36(2):160–191.
  * Suppes, (1994) Suppes, P. (1994).  Qualitative theory of subjective probability.  In Wright, G. and Ayton, P., editors, Subjective Probability, pages 17–37. John Wiley & Sons.
  * Tarski, (1951) Tarski, A. (1951).  A Decision Method for Elementary Algebra and Geometry.  The University of California Press.
  * Tversky and Kahneman, (1974) Tversky, A. and Kahneman, D. (1974).  Judgment under uncertainty: Heuristics and biases.  Science, 185(4157):1124–1131.
  * Vaught, (1954) Vaught, R. L. (1954).  Remarks on universal classes of relational systems.  Indagationes Mathematicae, 16:589–591.
  * Walley, (1991) Walley, P. (1991).  Statistical Reasoning with Imprecise Probabilities.  Chapman & Hall.
  * Williamson, (2013) Williamson, D. (2013).  Lecture Notes on Mathematical Programming I.  Cornell University.

## Appendix: Finite Cancellation and $\mathsf{AX}_{\textnormal{add}}$

To help clarify the relationship between $\mathsf{AX}_{\textnormal{add}}$ and
the standard axiomatization of comparative probability, one can verify the
soundness of the finite cancellation scheme by deriving it in our additive
system:

######  Proposition .1.

Each instance of $\mathsf{FinCan}_{n}$ is derivable in
$\mathsf{AX}_{\textnormal{add}}$.

###### Proof.

We use all of the axioms of $\mathsf{AX}_{\textnormal{add}}$, and we appeal to
$\mathsf{Assoc}$, $\mathsf{Comm}$, and the rules and axioms of
$\mathsf{AX}_{\textnormal{base}}$ (such as Boolean reasoning) without mention.
At a high level, the idea of the proof is simply to combine all the
inequalities together (using $\mathsf{2Canc}$) and then cancel a number of
terms from both side (using $\mathsf{Contr}$).

The first observation is that
$(\alpha_{1},\dots,\alpha_{n})\equiv_{0}(\beta_{1},\dots,\beta_{n})$ implies
that $\mathbf{P}(\delta)\approx\mathsf{0}$ for every _unbalanced_ state
description $\delta$ over these $2n$ formulas. By $\mathsf{Dist}$ and
$\mathsf{Add}$,
$(\alpha_{1},\dots,\alpha_{n})\equiv_{0}(\beta_{1},\dots,\beta_{n})$ allows us
to obtain
$\sum_{\delta\in\mathcal{B}}\mathbf{P}(\delta)\approx\sum_{\delta\in\Delta}\mathbf{P}(\delta)$.
By multiple applications of $\mathsf{Contr}$—and in particular its
consequence, $\mathsf{1Canc}$—we can cancel all of the summands from the left
side, ending (by another application of $\mathsf{Contr}$) with
$\mathsf{0}\approx\sum_{\delta\in\Delta-\mathcal{B}}\mathbf{P}(\delta)$. By
yet further applications of $\mathsf{Contr}$ we conclude that
$\mathbf{P}(\delta)\approx\mathsf{0}$ for each unbalanced
$\delta\in\Delta-\mathcal{B}$.

Let $\Delta_{\alpha_{i}}$ be those state descriptions with $\alpha_{i}$
occurring positively (i.e., not negated), and likewise for
$\Delta_{\beta_{i}}$. By $\mathsf{Add}$ we know that
$\mathbf{P}(\alpha_{i})\approx\sum_{\delta\in\Delta_{\alpha_{i}}}\mathbf{P}(\delta)$,
and likewise for each $\delta$. By the previous observation that
$\mathbf{P}(\delta)\approx\mathsf{0}$ for unbalanced sequences, we can
conclude that
$\mathbf{P}(\alpha_{i})\approx\sum_{\delta\in\mathcal{B}_{\alpha_{i}}}\mathbf{P}(\delta)$,
with $\mathcal{B}_{\alpha_{i}}=\Delta_{\alpha_{i}}\cap\mathcal{B}$. So each
remaining conjunct $\alpha_{i}\succsim\beta_{i}$ in the antecedent can be
rewritten as
$\sum_{\delta\in\mathcal{B}_{\alpha_{i}}}\mathbf{P}(\delta)\succsim\sum_{\delta\in\mathcal{B}_{\beta_{i}}}\mathbf{P}(\delta)$.
By axiom $\mathsf{2Canc}$ we can combine all of these sums together, producing
an inequality of the form:

$\displaystyle\sum_{\delta\in\mathcal{B}_{\alpha_{1}}}\mathbf{P}(\delta)+\dots+\sum_{\delta\in\mathcal{B}_{\alpha_{n-1}}}\mathbf{P}(\delta)$
$\displaystyle\succsim$
$\displaystyle\sum_{\delta\in\mathcal{B}_{\beta_{1}}}\mathbf{P}(\delta)+\dots+\sum_{\delta\in\mathcal{B}_{\beta_{n-1}}}\mathbf{P}(\delta).$
(9)

The crux of the proof is now to consider which terms will be cancelled from
both sides (once again appealing to $\mathsf{Contr}$). Any state description
$\delta\in\mathcal{B}_{\beta_{n}}$ will appear once more on the left than on
the right, so $\mathbf{P}(\delta)$ will still remain as a summand on the left.
All other terms on the left will be cancelled. Similarly for the right, we
will end up with the sum of terms for state descriptions in
$\mathcal{B}_{\alpha_{n}}$, so that (9) becomes simply

$\displaystyle\sum_{\delta\in\mathcal{B}_{\beta_{n}}}\mathbf{P}(\delta)$
$\displaystyle\succsim$
$\displaystyle\sum_{\delta\in\mathcal{B}_{\alpha_{n}}}\mathbf{P}(\delta),$

or, in other words, by the observations above, our desired consequent
$\beta_{n}\succsim\alpha_{n}$. ∎

The next observation shows that de Finetti’s original proposal captures the
first three levels of finite cancellation:

######  Proposition .2.

$\mathsf{Quasi}$ and $\mathsf{FinCan}_{3}$ are equivalent over
$\mathsf{AX}_{\text{base}}$.

## Appendix: Quadratic Qualitative Probability Structures for $n=2$

######  Proposition .3.

The Domotor axioms $\mathsf{Q1}$–$\mathsf{Q4}$, the $n=2$ instance of
$\mathsf{Q5}$, and $\mathsf{Q6}$ are complete for models with a binary event
space $\Omega=\\{0,1\\}$.

###### Proof.

We aim to show there is a positive symmetric bilinear functional
$\Phi:\mathbb{R}^{2}\times\mathbb{R}^{2}\to\mathbb{R}$ representing the order
that is additionally rank $1$, and therefore factors as a product of measures.
Q1–Q4, Q6 give everything except rank $1$. The matrix of such a rank $1$ is,
up to normalization,

$\displaystyle\text{either }\begin{bmatrix}1&x\\\ x&x^{2}\end{bmatrix}\text{
or }\begin{bmatrix}0&0\\\ 0&1\end{bmatrix}$

where $x\geq 0$. Let $\textbf{0}=\\{0\\}$ and $\textbf{1}=\\{1\\}$. The latter
matrix represents the total preorder

$\displaystyle(\varnothing,\cdot)\sim(\textbf{0},\textbf{0})\sim(\textbf{0},\Omega)\sim(\textbf{0},\textbf{1})\prec(\textbf{1},\textbf{1})\sim(\textbf{1},\Omega)\sim(\Omega,\Omega)$
(10)

where the $\cdot$ in $(\varnothing,\cdot)$ stands for any (or every) one of
the four subsets of $\Omega$.

In the case of the former matrix, for $A,B\subset\Omega$ we find

$\displaystyle\Phi(\mathbbm{1}_{A},\mathbbm{1}_{B})=(1+x^{2})\sum_{a\in
A}\mathfrak{x}(a)\sum_{b\in B}\mathfrak{x}(b)$ (11)

where the term $\mathfrak{x}(\omega)$ for $\omega\in\Omega$ is defined to be
$1$ if $\omega=0$ and $x$ if $\omega=1$. Considering the various (unordered)
choices of $A,B$, we see that (11) gives $10$ polynomials in $x$, in fact $7$
if we observe that all corresponding to $(\varnothing,\cdot)$ are identically
$0$. Below we plot these curves as a function of $x$. Without loss we have
divided each by the prefactor $1+x^{2}$ appearing in (11).

By inspecting282828This can be made fully rigorous via e.g. Sturm sequences.
the intersections and their induced subdivisions in the first
quadrant292929The order (10) arising from the degenerate matrix
$\begin{bmatrix}0&0\\\ 0&1\end{bmatrix}$ corresponds to $x=+\infty$ on the
plot. we count $8$ total preorders

$\displaystyle(\varnothing,\cdot)\sim(\textbf{1},\Omega)\sim(\textbf{0},\textbf{1})\sim(\textbf{1},\textbf{1})\prec(\textbf{0},\textbf{0})\sim(\textbf{0},\Omega)\sim(\Omega,\Omega)$
(12)
$\displaystyle(\varnothing,\cdot)\prec(\textbf{1},\textbf{1})\prec(\textbf{0},\textbf{1})\prec(\textbf{1},\Omega)\prec(\textbf{0},\textbf{0})\prec(\textbf{0},\Omega)\prec(\Omega,\Omega)$
(13)
$\displaystyle(\varnothing,\cdot)\prec(\textbf{1},\textbf{1})\prec(\textbf{0},\textbf{1})\prec(\textbf{0},\textbf{0})\sim(\textbf{1},\Omega)\prec(\textbf{0},\Omega)\prec(\Omega,\Omega)$
(14)
$\displaystyle(\varnothing,\cdot)\prec(\textbf{1},\textbf{1})\prec(\textbf{0},\textbf{1})\prec(\textbf{0},\textbf{0})\prec(\textbf{1},\Omega)\prec(\textbf{0},\Omega)\prec(\Omega,\Omega)$
(15)
$\displaystyle(\varnothing,\cdot)\prec(\textbf{0},\textbf{0})\sim(\textbf{1},\textbf{1})\sim(\textbf{0},\textbf{1})\prec(\textbf{0},\Omega)\sim(\textbf{1},\Omega)\prec(\Omega,\Omega)$
(16)
$\displaystyle(\varnothing,\cdot)\prec(\textbf{0},\textbf{0})\prec(\textbf{0},\textbf{1})\prec(\textbf{1},\textbf{1})\prec(\textbf{0},\Omega)\prec(\textbf{1},\Omega)\prec(\Omega,\Omega)$
(17)
$\displaystyle(\varnothing,\cdot)\prec(\textbf{0},\textbf{0})\prec(\textbf{0},\textbf{1})\prec(\textbf{1},\textbf{1})\sim(\textbf{0},\Omega)\prec(\textbf{1},\Omega)\prec(\Omega,\Omega)$
(18)
$\displaystyle(\varnothing,\cdot)\prec(\textbf{0},\textbf{0})\prec(\textbf{0},\textbf{1})\prec(\textbf{0},\Omega)\prec(\textbf{1},\textbf{1})\prec(\textbf{1},\Omega)\prec(\Omega,\Omega)$
(19)

Thus we have $9$ total preorders (10), (12)–(19) representable by a rank $1$.

We claim these are exactly the ones satisfying the stated Domotor axioms. The
soundness direction is straightforward while the completeness direction can be
shown via casework. Note that the $n=2$ instance of $\mathsf{Q5}$ is just
monotonicity (in both arguments, by symmetry), namely that

$\displaystyle(A,B)\preceq(A,C)\Rightarrow(D,B)\preceq(D,C)$

and analogously in the first argument. This presumes that
$(\varnothing,\Omega)\prec(A,B)$ and $(\varnothing,\Omega)\prec(D,C)$. We also
have strict monotonicity. Below we will generally take
$\mathsf{Q1}$–$\mathsf{Q4}$ for granted, which just amount to the axioms of a
nondegenerate total preorder, symmetric on the pairs. Our cases are:

  1. 1.

If $(\textbf{0},\Omega)\prec(\textbf{1},\Omega)$:

    1. (a)

If $(\varnothing,\Omega)\sim(\textbf{0},\textbf{0})$: conclude order (10), by
$\mathsf{Q5}$ and $\mathsf{Q6}$.

    2. (b)

If $(\varnothing,\Omega)\prec(\textbf{0},\textbf{0})$: by $\mathsf{Q5}$
conclude
$(\textbf{0},\textbf{0})\prec(\textbf{0},\textbf{1})\prec(\textbf{1},\textbf{1})$.
By $\mathsf{Q6}$ conclude $(\textbf{1},\Omega)\prec(\Omega,\Omega)$.

      1. i.

If $(\textbf{1},\textbf{1})\prec(\textbf{0},\Omega)$: order (17)

      2. ii.

If $(\textbf{1},\textbf{1})\sim(\textbf{0},\Omega)$: order (18)

      3. iii.

If $(\textbf{1},\textbf{1})\succ(\textbf{0},\Omega)$: order (19)

  2. 2.

If $(\textbf{0},\Omega)\sim(\textbf{1},\Omega)$ conclude order (16), by
repeated applications of $\mathsf{Q5}$ and $\mathsf{Q6}$.

  3. 3.

If $(\textbf{0},\Omega)\succ(\textbf{1},\Omega)$:

    1. (a)

If $(\varnothing,\Omega)\sim(\textbf{1},\textbf{1})$: conclude order (12) by
$\mathsf{Q5}$, $\mathsf{Q6}$.

    2. (b)

If If $(\varnothing,\Omega)\prec(\textbf{1},\textbf{1})$: by $\mathsf{Q5}$
conclude
$(\textbf{1},\textbf{1})\prec(\textbf{0},\textbf{1})\prec(\textbf{0},\textbf{0})$.
By $\mathsf{Q6}$ conclude $(\textbf{0},\Omega)\prec(\Omega,\Omega)$.

      1. i.

If $(\textbf{0},\textbf{0})\prec(\textbf{1},\Omega)$: order (15)

      2. ii.

If $(\textbf{0},\textbf{0})\sim(\textbf{1},\Omega)$: order (14)

      3. iii.

If $(\textbf{0},\textbf{0})\succ(\textbf{1},\Omega)$: order (13)

∎