Determine the smallest cardinal of $D$ satisfying certain requirement.

Question

Define the composition of two relation $R\subset A\times B$, and $S\subset B\times C$, as $(a,c)\in R\cdot S$ iff $\exists b ((a,b)\in R\land(b,c)\in S)$. My question is given a relation $R$, what is the smallest cardinal of a set $D$ for the relation $R\subset A\times B$, such that there exists two relation $S\subset A\times D,K\subset D\times B$ such that $R=S\cdot K$?

Is there any construction of the set $D$?

Answer 1

At most the cardinality of $R$, since you can define the relation $S$ in $A\times R$, for $(a,(b,c))\in S\iff a=b$ and the relation $K$ in $R\times B$, $((a,b),c)\in K,\iff b=c$, then, $R=S\cdot K$.

My guess is the smallest cardinal of $I$, where $I$ is any indexing set such that $\{A_i\}_{i\in I}$ and $\{B_i\}_{i\in I}$ are a family of subset of $A$ and $B$, respectively, and $R=\bigcup\limits_{i\in I}A_i\times B_i$. Then you can define the relations $S\subset A\times I,K\subset I\times B$, such that $(a,i)\in S\iff a\in A_{i}$ and $(i,b)\in K\iff b\in B_i$ (so, you have $R=S\cdot K$). (of course, this cardinality isn't so easy to compute...)

Answer 2

Given a relation $R$, let $R_A$ denote the set of all first coordinates of $R$. That is, $x\in R_A$ iff $xRy$ for some $y\in B$. Likewise, $R_B$ denotes the set of all second coordinates.

Then the smallest cardinal of $D$ is bounded above by $\min\{|R_A|,|R_B|\}$.

To see this is an upper bound, assume wlog $|R_A|\leq|R_B|$ and let $D=R_A$ with $S = \{(x,x)|x\in R_A\} \subseteq A\times D$ and $K = R|_{D\times B}$.

However, without more information on $R$, nothing more can be said. Here are 2 examples to justify that statement.

${}$

I claim that sometimes this bound is optimal. For let $A = B$ and $R =\{(x,x)\in A\times A\}$ and suppose $R = S\cdot K$. Then we must have $R_A = S_A$. We may assume wlog that $K_D = D$ for other wise we can replace $D$ with $K_D$. Since $R_A = S_A$, every $a\in A$ must be paired with a corresponding $d_a \in D$. Since $|D|<|A|$, there must be some $d\in D$ with at least 2 different $a$s paired with it, that is $(a_1,d)$ and $(a_2,d)$ must both be in $S$ for $a_1\neq a_2$.

Since $K_D = D$, we know we have an ordered pair of the form $(d, a_3)$. But then $R=S\cdot K$ so $(a_1,a_3)$ and $(a_2,a_3)$ are both in $R$, showing that $a_1 = a_2$, a contradiction.

${}$

I also claim that sometimes this bound is not optimal. For, let $R = A\times A$. Let $D$ be any one point set. Let $S = A\times D$ and $K = D\times A$. Then $R = S\cdot K$ while $|D| = 1$.