Re: Relations And Their Divisitudes

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

RATD.  Note 29

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

Relational Composition as Logical Matrix Multiplication (cont.)

If the 2-adic relations G and H are viewed as logical sums,
then their relational composition G o H can be regarded as
a product of sums, a fact that can be indicated as follows:

   G o H  =  (Sum_ij G_ij (i:j))(Sum_ij H_ij (i:j)).

G o H is itself a 2-adic relation over the same space X,
in other words, G o H c X x X, and this means that G o H
must be amenable to being written as a logical sum of the
following form:

   G o H  =  Sum_ij (G o H)_ij (i:j).

In this formula, (G o H)_ij is the coefficient of
G o H with respect to the elementary relation i:j.

One of the best ways to reason out what G o H should be is to ask
oneself what its coefficient (G o H)_ij should be for each of the
elementary relations i:j in turn.

So let us pose the question:

   (G o H)_ij  =  ?

In order to answer this question, it helps to realize
that the indicated product given above can be written
in the following equivalent form:

   G o H  =  (Sum_ik G_ik (i:k))(Sum_kj H_kj (k:j)).

A moment's thought will tell us that (G o H)_ij = 1
if and only if there is an element k in X such that
G_ik = 1 and H_kj = 1.

Consequently, we have the result:

   (G o H)_ij  =  Sum_k (G_ik H_kj).

This follows from the properties of boolean arithmetic,
specifically, the fact that the product G_ik H_kj is 1
if and only if both G_ik and H_kj are 1, and from the
fact that Sum_k F_k is 1 if and only if some F_k is 1.

Jon Awbrey

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o