Número de relaciones simétricas y reflexivas

Question

Consideremos un conjunto no vacío A que contiene n objetos. ¿Cuántas relaciones en A son simétricas y reflexivas?

La respuesta a esto es $2^p$ donde $p=$ $n \choose 2$ . Sin embargo, no entiendo por qué esto es así. ¿Alguien puede explicarlo?

Answer 1

Para ser reflexivo, debe incluir todos los pares $(a,a)$ con $a\in A$ . Para ser simétrico, siempre que incluya un par $(a,b)$ debe incluir el par $(b,a)$ . Así que se trata de elegir qué $2$ -subconjuntos de elementos de $A$ corresponderán a los pares asociados. Si se elige un subconjunto $\{a,b\}$ con dos elementos, corresponde a la suma de ambos $(a,b)$ y $(b,a)$ a su relación.

Cuántos $2$ -subconjuntos de elementos hace $A$ ¿tiene? Desde $A$ tiene $n$ elementos, tiene exactamente $\binom{n}{2}$ subconjuntos de tamaño $2$ .

Así que ahora quieres elegir una colección de subconjuntos de $2$ -elementos. Hay $\binom{n}{2}$ de ellos, y puedes elegir o no elegir cada uno de ellos. Así que tienes $2^{\binom{n}{2}}$ formas de elegir los pares de elementos distintos que estarán relacionados.

Answer 2

Ser reflexivo significa que $(x,x)\in R$ para todos $x\in A$ . Ser simétrico significa que $(x,y)\in R$ implica que $(y,x)\in R$ también.

Comience por enumerar $A$ como $A=\{a_1,\dots,a_n\}$ . Entonces dejemos que $B$ sea el conjunto $$\{(a_i,a_j)\mid 1\le i<j\le n\}.$$ Tenga en cuenta que si $x\ne y$ son elementos de $A$ Entonces, o bien $(x,y)\in B$ o $(y,x)\in B$ pero no ambos.

Dejemos que $S$ sea cualquier subconjunto de $B$ . Sea $$R_S=S\cup\{(y,x)\mid (x,y)\in S\}\cup\{(x,x)\mid x\in A\}.$$ Entonces $R_S$ es una relación simétrica y reflexiva sobre $A$ .

Tenga en cuenta que hay $2^{|B|}$ subconjuntos de $B$ y que si $S\ne S'$ son subconjuntos de $B$ entonces $R_S\ne R_{S'}$ . Además, tenga en cuenta que $|B|=\binom{n}2$ . (Si la última igualdad no está clara, observe que $$B=\{(a_1,a_j)\mid j>1\}\cup\{(a_2,a_j)\mid j>2\}\cup\dots$$ así que $|B|=(n-1)+(n-2)+\dots+1$ y es sabido que la última suma es igual a $n(n-1)/2=\binom n2$ .

Esto demuestra que el número de relaciones simétricas y reflexivas en $A$ es al menos $2^p$ con $p=\binom n2$ .

Para ver la igualdad, basta con comprobar que cualquier relación de este tipo $R$ es $R_S$ para algunos $S\subseteq B$ . Pero, teniendo en cuenta $R$ , dejemos que $S=\{(a_i,a_j)\in R\mid i<j\}$ . Se trata de un subconjunto de $B$ y es fácil comprobar que $R=R_S$ .

Answer 3

Tal vez puedas verlo así: una relación $R$ en $A$ es un subconjunto de $A\times A$ y es simétrica si y sólo si $(x,y)\in R \implies (y,x)\in R$ Además, si la relación es reflexiva, entonces $(x,x)\in R$ para todos $x\in A$ . Entonces se puede determinar de forma única tal relación diciendo qué subconjuntos de dos elementos distintos de $A$ "pertenecer" a $R$ en el sentido de que $\{x,y\}\in R \iff (x,y),(y,x)\in R$ . Ahora bien, se sabe que el número de subconjuntos con dos elementos distintos de $A$ es $\binom{n}{2}$ y el número de subconjuntos de un conjunto con $p$ elementos es $2^p$ . Lo siento si he sido demasiado oscuro.

Answer 4

Sólo hay una forma de hacer que la relación sea reflexiva: todos los pares ordenados $(x,x), x\in A$ debe estar en la relación. Así que el número de relaciones simétricas reflexivas en $A$ es el mismo que el número de formas de sumar pares simétricos $(a,b),(b,a)$ , donde $a\neq b$ en la relación.

Dejemos que $S$ sea un subconjunto de $2^A$ formado por subconjuntos de 2 elementos. Entonces $S$ da lugar exactamente a una relación simétrica reflexiva sobre $A$ . Por ejemplo, si $A=\lbrace 1,2,3,4\rbrace$ , entonces un ejemplo de $S$ es $\lbrace \lbrace 1,2\rbrace, \lbrace 1,4\rbrace, \lbrace 3,2\rbrace\rbrace$ . La relación inducida por $S$ es $$\lbrace (1,2), (2,1), (1,4), (4,1), (2,3), (3,2)\rbrace$$ además de todo $(x,x), x\in A$ . A la inversa, toda relación simétrica reflexiva sobre $A$ surge de esta manera.

Dado que hay $p={n\choose 2}$ subconjuntos de 2 elementos, hay $2^p$ tal $S$ 's. Por lo tanto, la respuesta a su pregunta es $2^p$ .

Answer 5

También se puede pensar en ello como una matriz de $nxn$ siendo los elementos de la matriz $(a_i,a_j)$ con $ a_i,a_j \in A$ . Los elementos de la diagonal principal tienen que estar incluidos en R porque R es reflexivo. Para el resto de $n^2-n$ , escogiendo un par del triángulo superior digamos $(a_2,a_1)$ implica que también está eligiendo $(a_1,a_2)$ . Así que en realidad sólo tienes $\frac{n^2-n}{2}$ elementos para elegir. Esto puede hacerse en $2^{\frac{n^2-n}{2}}$ formas.