3
$\begingroup$

I have a Set $S$, $|S|=n$, and I need to count how many symetric and transitive relations are in $S$ that are not equivalence relations.

I know how to count equivalence relations (Bell number) but I don't konw how to count the relations that are symetric and transitive at the same time.

$\endgroup$
2
  • 2
    $\begingroup$ This answer says that "The number of symmetric and transitive relations on $n$ things is the number of reflexive, symmetric and transitive relations on $n+1$ things." $\endgroup$ Commented May 15, 2016 at 21:19
  • $\begingroup$ And likewise math.stackexchange.com/questions/1770809. $\endgroup$ Commented May 15, 2016 at 21:40

1 Answer 1

Reset to default
0
$\begingroup$

There are $B_n$ equivalence relations on $[n]$. As shown in the two threads linked to in the comments, there are $B_{n+1}$ relations on $[n]$ that are symmetric and transitive. Thus there are $B_{n+1}-B_n$ relations that are symmetric and transitive but not reflexive.

$\endgroup$
6
  • $\begingroup$ I'm sorry @joriki, but I don't understand why the number of relations symetric and transitive are $B_{n+1}$. $\endgroup$ Commented May 15, 2016 at 23:52
  • $\begingroup$ @Felipe: Did you look at the two proofs provided? If so, please point out specifically what parts of the proofs you don't understand. $\endgroup$ Commented May 15, 2016 at 23:52
  • $\begingroup$ Yes, I did. I don't understand the part in where quote: "the set decomposes into two subsets; on one the partial equivalence relation is empty and on the other it is an equivalence relation." And why "the partial equivalence relations on $n$ are in bijection with the equivalence relations on $n+1$" $\endgroup$ Commented May 15, 2016 at 23:57
  • $\begingroup$ @Felipe: Decompose the set into the elements that are related to themselves and those that aren't. By the preceding conclusion that "an element related to any other element is also related to itself", the elements that aren't related to themselves aren't related to any elements at all, so the relation is empty on that subset. On the other subset, it's reflexive by construction. $\endgroup$ Commented May 16, 2016 at 0:05
  • $\begingroup$ @Felipe: The second sentence you quote is followed by its justification: "Just remove the equivalence class containing $[n+1]$". The elements in that class (except for $n+1$) form the subset on which the partial equivalence relation is empty, and the remaining classes form the classes of the subset on which the partial equivalence relation is reflexive (and is thus an equivalence relation). $\endgroup$ Commented May 16, 2016 at 0:05

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.