Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.