Composition with graded predicates [efr-0009]

June 5, 2024
Eigil Fjeldgren Rischel

Suppose $T: X \to \Delta (Y)$ is a stochastic map, and suppose $\phi ^\epsilon$ is a graded predicate on $Y$ (in particular, $\phi ^\epsilon (y) \Rightarrow \phi ^{\epsilon '}(y)$ if $\epsilon < \epsilon '$ ).

Then we can define $T^{-1}(\phi )^\epsilon$ , a graded predicate on $X$ , by $T^{-1}(\phi )^\epsilon (x)$ if there exists $\epsilon _1 + \epsilon _2 = \epsilon$ with $P(\phi ^{\epsilon _1}(Tx)) > 1-\epsilon _2$

Every graded predicate $\phi$ on $X$ is the pullback of the predicate $x = \top$ on $\{\bot ,\top \}$ along a unique stochastic map $[\phi ]: X \to \{\bot ,\top \}$ (which carries $x$ to the distribution which is $\bot$ with probability $\inf _{\phi ^\epsilon (x)} \epsilon$ ). Thus a graded predicate is essentially a stochastic version of an ordinary predicate (which is a deterministic map to $\{\bot ,\top \}$ ). Under this equivalence, the operation $T^{-1}$ is simply precomposition with $T$ .

Let $p,q: X \to \Omega$ be two stochastic maps to the subobject classifier (i.e $\{\bot ,\top \}$ ). Defining logical operations on such objects is problematic essentially because of the lack of independence---if $p,q$ classify the probability that some $f(X)$ lie in two different subsets $P,Q$ , there is essentially no way to recover the probability of the intersection, or the union, since we can't see their correlation. We can consider a few different options---writing $p(x),q(x) \in [0,1]$ for the probability of truth (assuming that we're in a setting where $\Delta (\Omega ) = [0,1]$ ).

$\min (p+q,1)$ is the probability of $p \vee q$ if they are maximally disjoint, i.e completely disregarded the possibility of overlap. Dually, $\max (p+q-1,0)$ is the probability of $p \wedge q$ if they are maximally disjoint
$\max (p,q)$ is the probability of $p \wedge q$ if they are maximally overlapping, and dually $\min (p,q)$ is the probability of $p \vee q$ if they are minimally overlapping
$pq$ is the probability of $p \wedge q$ if they are independent, and dually $p+q-pq$ is the probability of $p \vee q$ if they are independent

In the language of error credits, adding an error credit of $\epsilon$ amounts to taking $\wedge (1-\epsilon )$ with the "maximally disjoint" assumption (this gives the smallest possible probability of truth, i.e. it's the strongest assumption you can make).