Exercise 2.62

Exercise 2.62#

import pandas as pd

def prove_v_category(df, mon_prod, preorder_rel):
    for row in df.index:
        for col in df.columns:
            for idx in range(0,len(df.index)):
                a = mon_prod(df.iloc[row, idx], df.iloc[idx, col])
                assert preorder_rel(a, df.iloc[row,col]), (row,idx,col)


See also Exercise 2.35.


The first property requires that the diagonal be {car, boat, foot}:

\[ I = M = \{car, boat, foot\} \subseteq n(x,x) \]

We can check the matrix is an \(\mathcal{M}\)-category by brute force:

cbf = set([0,1,2])
bf = set([1,2])
f = set([2])
e = set()
sdf = pd.DataFrame(
    index=range(4), columns=range(4),
prove_v_category(sdf, set.intersection, lambda x,y: x <= y)
0 1 2 3
0 {0, 1, 2} {0, 1, 2} {2} {2}
1 {} {0, 1, 2} {} {}
2 {} {} {0, 1, 2} {}
3 {} {2} {1, 2} {0, 1, 2}

To get a little more intuitive feel, consider the second required property of an \(\mathcal{M}\)-category:

\[ n(x,y) ∩ n(y,z) \subseteq n(x,z) \]

For paths that are only two edges long, you can interpret this as the instructions to:

take the intersection of the sets labelling the edges in p.

For longer paths, you can see this as considering all possible intermediates y between x and z where y must be precomputed. For this to be true for all intermediates (all y) we must:

take the union of these sets over all paths p from x to y.

Larger sets indicate two nodes are “more connected” but in a boolean sense for every element in the set. You could also use a graph like this to communicate multiple ways to solve a problem.