Measure of how much information is lost in an implication

Question

In an implication like $p \implies q$, is there some measure of how much information is lost in the implication? For example, consider the following implications, where $x \in \{0,1,\ldots,9\}$:

\begin{align} P &: (x = 6) \implies (x \equiv 0 \pmod{2}) \\ Q &: (x = 6) \implies (x \equiv 0 \pmod{3}) \\ R &: (x = 6) \implies (x \equiv 6 \pmod{8}) \\ \end{align}

I would argue that less information about $x$ is lost in implication $Q$ than in implication $P$: Given that $x \equiv 0 \pmod{3}$ and $x \in \{0,1,\ldots,9\}$, there are fewer possibilities for $x$ than if you were given $x \equiv 0 \pmod{2}$.

In implication $R$, I would argue that no information about $x$ is lost, since if $x \equiv 6 \pmod{8}$ and $x \in \{0,1,\ldots,9\}$, then you can conclude $x=6$. In general, any "if and only if" relation loses no information in the implication.

I'm familiar with the concepts of Shannon entropy and (vaguely) Kolmogorov complexity. Is there an analogous measure of information loss in an implication? Perhaps one of those two could be used in some natural way here?

^{(Note: I'm not asking about the Chinese remainder theorem. I'm just using modular arithmetic as an example.)}

Answer 1

Shannon entropy, $H(X)$, can be intuitively thought of as the amount of uncertainty present in a random variable (r.v.). The conditional entropy $H(X|Y)$ is the amount of uncertainty remaining in r.v. $X$ given r.v. $Y$. This has some parallel with the information loss you described above. For example if $H(X|Y_1) < H(X|Y_2)$, then it can be considered that $Y_1$ has more information about $X$ than $Y_2$ since there is a greater reduction of uncertainty. Another measure that may be of interest to you is mutual information, which is $I(X;Y) := H(X) - H(X|Y)$. This quantity is the amount of information remaining in r.v. $X$ after we know $Y$ (and vice versa).

Unfortunately, these measure is only rigorous in a probabilistic setting. The entropy of deterministic events like $X=6$ where $\mathbb{P}(X=6)=1$ would be zero.

Hope this was useful.

Answer 2

You can certainly say that $x=6$ gives you certainty of the value, while $x\equiv 0 \pmod 2$ gives you five possibilities. That is $\log_2 5$ bits less information. Meanwhile, $x \equiv 0 \pmod 3$ gives four possibilities, so you need $2$ bits to get certainty, and $x\equiv 6 \pmod 8$ is already certain.

Answer 3

What an interesting idea! Analogous to Shannon's entropy, you can define the volume of the possible $x$ as a measure of uncertainty.

Let $P(x)$ be a unary predicate on some set $x \in X$. The predicate defines a set of atoms that it holds true, i.e, the set $A_P = \{ x \in X, P(x)\}$. If this set contains exactly one atom, we can say there is no uncertainty. In the other hand, if $A_P = X$, we know nothing about what $P$ is trying to point at. Therefore, I suggest defining the entropy of a unary predicate as:

$$ H(P) = \log \left|\{x \in X, P(x)\}\right|$$

where $|\cdot |$ is the cardinality of the set, for any $P(x) \neq \bot$, so that $A_P$ is not empty. This assumes that $X$ is countable.

This can be thought of as a special case of Shannon's entropy assuming all atoms in the set are equally likely, i.e., each possible atom has probability $\frac{1}{|A_P|}$. Thus, Shannon's entropy is: $$H\left(\frac{1}{|A_P|}, \ldots, \frac{1}{|A_P|}\right) = -|A_P| \frac{1}{|A_P|} \log_2 \left(\frac{1}{|A_P|}\right) = \log_2 |A_P|$$

Now if you want to define the information loss, we can use analogously the difference of entropies. Specifically, for $P(x) \implies Q(x)$ in your inference, note that $H(P) \leq H(Q)$, so the difference of entropy $D(P, Q) = H(Q) - H(P)$ is always non-negative. $D(P,Q)$ measures how much uncertainty you gained, which is equivalent to how much information you lost about the identity of $x$.

I can think of many extensions, but this is not my field, so I don't know the proper literature. (Multivariate predicates, and mutual information are obvious next step to take).

EDIT: Mutual information is linked to Jaccard index.