# How many symmetric and transitive relations are there on ${1,2,3}$?

I'm trying to count the number of relations on ${1,2,3}$ that are symmetric and transitive. I know how to count the symmetric relations but I can't seem to find the method for this one.

I've counted 7: {$(1,1)$} , {$(2,2)$} , {$(3,3)$} , {$(1,2),(2,1)$}, {$(1,3),(3,1)$}, {$(2,3), (3,2)$}, {$(1,2),(2,1), (1,3),(2,3) (3,1), (3,2)$}.

Thanks.

• What have you counted 7? {(1,2),(2,1)} is symmetric. But if it were transitive, then it should also contain (1,1) and (2,2). – Swapniel Apr 7 '14 at 10:18
• Sorry, my mistake. I counted them again and I found 7. – ruplop Apr 8 '14 at 0:37
• This one is symmetric and transitive, right? {$(1,1),(1,3),(3,1),(3,3),(2,2)$} – ruplop Apr 9 '14 at 0:47
• Yes it is symmetric and transitive. – Swapniel Apr 9 '14 at 16:17
• Asked again, a couple of days later: math.stackexchange.com/questions/745923/… – Gerry Myerson Apr 10 '14 at 11:12

The number of symmetric and transitive relations on $n$ things is the number of reflexive, symmetric and transitive relations on $n+1$ things. Given a symmetric and transitive relation $R$ on $\{\,1,2,\dots,n\,\}$, chuck in $(n+1,n+1)$, and $(a,n+1)$ and $(n+1,a)$ and $(a,a)$ for every $a$ such that $(a,a)$ is not in $R$; that gives a reflexive, symmetric and transitive relation on $\{\,1,2,\dots,n+1\,\}$.