3
$\begingroup$

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

  • 0
    @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. – 2012-05-28

2 Answers 2

2

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

  • 0
    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$. – 2012-05-31
1

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