relation symétrique, transitive mais pas d'équivalence.
Comment compter le nombre de relations binaires sur un ensemble de taille 'n' telles qu'elles soient symétriques, transitives, mais pas une relation d'équivalence (c'est-à-dire qu'elles ne sont pas réflexives).
Toute aide est appréciée. Je vous remercie.
Réponses
Supposons que vous ayez une relation symétrique et transitive $R$ sur $X$. Ensuite, il est assez simple de montrer que si vous définissez$R_0 := \{ x \in X \mid (x, x) \in R \}$, puis $R \subseteq R_0 \times R_0$, et $R$ est une relation d'équivalence sur $R_0$. Inversement, si vous avez un sous-ensemble$Y \subseteq X$ et une relation d'équivalence $S$ sur $Y$, puis $S$ en tant que sous-ensemble de $X \times X$ est symétrique et transitive.
Pour cette raison, une relation symétrique et transitive sur $X$est souvent appelée relation d'équivalence partielle , car nous avons montré qu'une relation d'équivalence partielle sur$X$ équivaut à une relation d'équivalence sur un sous-ensemble $Y \subseteq X$.
Or, le problème du comptage des relations d'équivalence sur un ensemble fini est bien étudié: le nombre de relations d'équivalence sur un ensemble de taille $n$ s'appelle le $n$e nombre de Bell ,$B_n$. Et puis, à partir de la discussion précédente, le nombre de relations d'équivalence partielle sur un ensemble de taille$n$ serait égal à $$\sum_{k=0}^n \binom{n}{k} B_k.$$ C'est parce que pour chaque $k$, nous pouvons choisir un sous-ensemble $Y$ de taille $k$ dans $\binom{n}{k}$ façons, et ensuite nous pouvons choisir la relation d'équivalence sur $Y$ dans $B_k$façons. Cependant, par une relation de récurrence bien connue sur les nombres de Bell, cette somme est précisément égale à$B_{n+1}$.
Et enfin, si l'on veut le nombre de relations symétriques et transitives non réflexives, cela équivaut au nombre de relations d'équivalence partielle qui ne sont pas aussi des relations d'équivalence, ce qui serait $B_{n+1} - B_n$.
En traçant à travers les preuves, nous pouvons donner une bijection explicite assez simple entre l'ensemble des relations d'équivalence partielle sur $\{ 1, \ldots, n \}$ et l'ensemble des relations d'équivalence sur $\{ 1, \ldots, n, n+1 \}$. À savoir, étant donné une relation d'équivalence partielle$R$ sur $\{ 1, \ldots, n \}$, on peut définir une relation d'équivalence $S$ sur $\{ 1, \ldots, n+1 \}$ en prolongeant $R$ avec une classe d'équivalence assimilant tous les éléments de $\{ 1, \ldots, n \} \setminus R_0$ avec $n+1$. Plus formellement,$$S := \{ (i, j) \in \{ 1, \ldots, n+1 \} \times \{ 1, \ldots, n+1 \} \mid (i, j) \in R \lor [(i, i) \notin R \wedge (j, j) \notin R] \}.$$ Et pour le sens inverse, étant donné une relation d'équivalence $S$ sur $\{ 1, \ldots, n+1 \}$, forment une relation d'équivalence partielle $R$ sur $\{ 1, \ldots, n \}$ en supprimant la classe d'équivalence de $n+1$. Plus formellement,$$R := \{ (i, j) \in \{ 1, \ldots, n \} \times \{ 1, \ldots, n \} \mid (i, j) \in S \wedge (i, n+1) \notin S \}.$$