Are there any relations R of size 15 on the set {1, 2, 3, 4, 5, 6} such that R is both transitive and symmetric?

Question

Are there any relations R of size 15 on the set {1, 2, 3, 4, 5, 6} such that R is both transitive and symmetric?

Hi, I'm gonna share my thoughts on this problem and my answer and hopefully someone can correct me if I'm way off (as it is my homework :)).

Ok, the set is of size 6. Let us look at the partition corresponding to the relation R. Suppose that is has parts P1, ..., Pn of sizes m1, ..., mn, respectively. For each index k=1, ..., n the part Pk contributes mk*(mk-1) ordered pairs to R, since:

mk=2 -> Pk(a,b) which contributes: (a,b),(b,a)

mk=3 -> Pk(a,b,c) which contributes: (a,b);(b,a);(c,a) (a,c);(b,c);(c,b)

and so on (assuming that I can't use reflexivity mk=1 should not be allowed)

Thus I should try to satisfy the following eq.

1) SUM mk=6, where k=1,...,n

2) SUM mk*(mk-1)=15, where k=1,...,n

Since 6 can be partitioned into 11 ways, satisfying eq. 1:

6, 5+1, 4+2, 4+1+1, 3+3, 3+2+1, 3+1+1+1, 2+2+2, 2+2+1+1, 2+1+1+1+1, 1+1+1+1+1+1

And since no one of these satisfy eq.2 we can't have a relation R of size 15 on the set {1, 2, 3, 4, 5, 6} (we should be able to exclude all combinations containing 1, since we did not allow mk=1).

Even if we allow symmetry (mk=1), and eq.2 gets modified to SUM mk^2=15 none of the partitions of 6 solves this eq. either.

So, am I wrong or can I deliver this to my teacher?

Answer 1

Let $A=\{1,2,3,4,5,6\}$. Suppose that $R$ is a symmetric, transitive relation on $A$. For each $a\in A$ let $C_a=\{a\}\cup\{b\in A:\langle a,b\rangle\in R\}$.

• Show that $\{C_a:a\in A\}$ is a partition of $A$.
• Show that if $|C_a|>1$, then $C_a\times C_a\subseteq R$, so $|R|\ge|C_a|^2$.
• Show that if $C_a=\{a\}$, then $R$ may but need not contain $\langle a,a\rangle$.

You’ll need to use the following fact: if $\langle a,b\rangle\in R$, where $a\ne b$, then by symmetry $\langle b,a\rangle\in R$, and transitivity then implies that $\langle a,a\rangle,\langle b,b\rangle\in R$.

If $|R|=15$, we must have $|C_a|\le 3$ for all $a\in A$. Since $3\cdot2^2=12<15$, we must have at least one $a\in A$ such that $|C_a|=3$. Thus, the only possibilities for the cardinalities of the sets $C_x$ are $\langle 3,3\rangle$, $\langle 3,2,1\rangle$, and $\langle 3,1,1,1\rangle$. The first of these would make $|R|=3^2+3^2=18$. The second would make $|R|$ either $3^2+2^2+1^2=14$ or $3^2+2^2=13$. What are the possible cardinalities of $R$ in the third case?