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),
    data=[[cbf,cbf,f,f],[e,cbf,e,e],[e,e,cbf,e],[e,f,bf,cbf]]
)
display(sdf)
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.