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

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$?

-
I answered your edited question already - you can always take $D = R_A = \{x\in R| xRy$ for some $y\in B\}$. – Jason DeVito May 28 '12 at 18:21
you just find a upper bound. – Minghao Liu May 28 '12 at 18:27
I see, you want a construction of the minimal $D$. Do you have a particular $R$ in mind? Note that at least in some cases, the $D$ I found is the optimal one. – Jason DeVito May 28 '12 at 18:28
I have no certain $R$ in mind, and there is another construction of upper bound finer than yours by defining two element equivalent if they have same image, then do the same as what you do on the equivalent class, but this is still not a minimal.. – Minghao Liu May 28 '12 at 18:40
@pirripedos: The minimal you can get from the equivalent classes if you make them so that not one is the subset of another. This makes the number smaller or equal to that of the equivalent classes. But I don't see an easy way to compute for an arbitrary cardinal. – Apostolos May 28 '12 at 19:05

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...)

-
your answer is wrong, for example (0,0) (1,1) (2,0) (2,1) – Minghao Liu May 30 '12 at 5:38
@pirriperdos: If $R=\{(0,0),(1,1),(2,0),(2,1)\}$, then you have $I=\{1,2\}$ and $A_1=\{0,2\},B_1=\{0\},A_2=\{1,2\},B_2=\{1\}$, so, $|D|=2$ ($D=I$) (since i couldn't figure out one $D$, with $|D|=1$, i don't think this a counterexample =p... (or i didn't get it =p)) – Yuki May 30 '12 at 17:27
I'm stupid about the counterexample. and I find that finding the smallest $|I|$ is equivalent to my question, for every $d∈D$, you can get it's image $A_d$ and $B_d$ in $A$ and $B$, then $R=\cup A_d\times B_d$. – Minghao Liu May 31 '12 at 2:09

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$.

-