Cómo muchas de las relaciones de equivalencia en un conjunto de 4 elementos.

Question

Sea S un conjunto que contiene 4 elementos (yo {$a,b,c,d$}). Cuántos posible las relaciones de equivalencia hay?

Así que empecé por hacer una lista de las posibles relaciones: {$(a,a)(a,b)(a,c)(a,d)(b,a)(b,b). . .(d,d)$}

{$(a,a)(a,b)(a,c). . . . . . . . . . (d,c)$}

{$(a,a)(a,b)(a,c). . . . . . . . . . (d,b)$} etc.

$\vdots$

{}

Entonces miré en el primer conjunto de relaciones: $aRa, aRb,$ etc. entonces traté de comparar las relaciones para ver si son las relaciones de equivalencia. Aquí es donde me quedé atrapado. Me di cuenta de que había demasiadas relaciones que ir a través de, (sin tener que gastar toda la semana) y que yo no quiero tener que mirar cada uno por separado. Existe una mejor manera de hacer esto o estoy en el camino correcto?

Answer 1

Una relación de equivalencia divide el conjunto subyacente en clases de equivalencia. Las clases de equivalencia de determinar la relación, y la relación que determina las clases de equivalencia. Probablemente será más fácil contar de cuántas maneras podemos dividir el conjunto en clases de equivalencia.

Podemos hacerlo por casos:

(1) todo el mundo está en la misma clase de equivalencia.

(2) todo el mundo está solo, que su clase se compone sólo de sí misma.

(3) Hay un triplete, y una persona solitaria ($4$ de los casos).

(4) Dos parejas de amigos (puede contar los casos).

(5) Dos compañeros y dos personas solitarias (de nuevo, el recuento de los casos).

Hay una manera de contar que es mucho más eficiente para grandes conjuntos subyacentes, pero para $4$, en la forma que hemos descrito es razonablemente rápido.

Answer 2

Es equivalente a la pregunta de cuántas maneras se puede particionar el conjunto! La respuesta es simplemente el 4 de Campana número: $$B_4=15$$
Calulated con bastante facilidad en el caso de un $0,1,2,3$ elemento de conjuntos (Que se puede resolver en la cabeza para ser $1,1,2,5$) utilizando la relación de recurrencia: $$B_4 = \sum_{k=0}^3 \binom{3}{k} B_k = \binom{3}{0} \cdot 1 + \binom{3}{1} \cdot 1 + \binom{3}{2} \cdot 2 + \binom{3}{3} \cdot 5=1 \cdot 1+ 3\cdot 1 + 3 \cdot 2 + 1 \cdot 5 = 15$$ El razonamiento detrás de esta relación de recurrencia es una generalización de lo que André Nicolas explicó.

Answer 3

Maneras de seleccionar cualquiera de los siguientes elementos de las 4 : (i) 1 elemento : C(4,1) (ii) 2 elementos : C(4,2) (iii) 3 elementos : C(4,3) (iv) 4 elementos : C(4,4)

Total de particiones, C = (4,1) + C(4,2) + C(4,3) + C(4,4) = 15