El problema en el que estoy trabajando es, "Demostrar que un poset finito puede ser reconstruido a partir de su relación de cubrimiento. [Pista: Demuestra que el poset es el cierre reflexivo transitivo de su relación de cubrimiento.]"
He estado buscando en mi libro de texto y en internet la definición de cierre reflexivo transitivo, pero no tuve éxito.
¿Alguien podría explicarme este concepto por favor?
Supongamos que $R$ es una relación en un conjunto $A$. El cierre transitivo reflexivo de $R$ es la relación más pequeña $S$ en $A$ tal que
Si $R$ ya es reflexiva y transitiva, entonces $R$ es su propio cierre transitivo reflexivo, pero no es el caso con tus relaciones de cobertura.
Una forma de construir el cierre transitivo reflexivo de $R$ es comenzar expandiendo $R$ a $$R_r=R\cup\{\langle a,a\rangle:a\in A\}\;,$$ agregando a $R$ todos los pares $\langle a,a\rangle$ que no estén en él. Luego, cada vez que tengas $\langle x,y\rangle$ y $\langle y,z\rangle$ en $R_r$, agrega $\langle x,z\rangle$ si aún no está ahí para obtener $R_r^2$. Repite para obtener $R_r^3$. Si $A$ es finito, después de un número finito de pasos no se agregará nada nuevo; la relación resultante $R_r^*$ es el cierre transitivo reflexivo de $R$.
¿Qué quieres decir con esto, "Si $R$ ya es reflexiva y transitiva, entonces $R$ es su propio cierre reflexivo transitivo, pero ese no es el caso con tus relaciones de cobertura." ¿Una relación de cobertura no es transitiva ni reflexiva?
@EMACK: Puedes formar el cierre transitivo reflexivo de cualquier relación, no solo de relaciones de cobertura, y yo estaba hablando allí sobre la situación general, específicamente, sobre lo que se entiende por cierre transitivo reflexivo. Una relación de cobertura puede ser transitiva, pero generalmente no lo es, y nunca es reflexiva, por lo que ese comentario realmente no se refiere a este problema específico. Sin embargo, es parte de comprender qué es el cierre transitivo reflexivo de una relación en general.
@BrianScott ¿Por qué una relación de cobertura no suele ser transitiva; por qué nunca es reflexiva?
Supongamos que $R$ es una relación en $A$ (es decir, $R\subseteq A\times A$).
El cierre transitivo reflexivo de $R$ en $A$ es la relación más pequeña $R'$ tal que $R\subseteq R'$ y $R'$ es transitiva y reflexiva.
Para ver que tal relación existe, puede construirla interna o externamente:
Internamente toma $R_0=R\cup\{(a,a)\mid a\in A\}$; y $R_{n+1}=R_n \circ R$, donde $\circ$ denota la composición de relaciones [1]. Entonces definimos $R'=\bigcup_{n\in\mathbb N} R_n$. Se puede demostrar que esta es una relación reflexiva y transitiva, y que si $S$ es reflexiva y transitiva y $R\subseteq S$ entonces $R'\subseteq S$.
Externamente se puede simplemente tomar $R'=\bigcap S$ donde $S$ es una relación reflexiva y transitiva en $A$, y $R\subseteq R$. No es difícil ver que la intersección de relaciones reflexivas es reflexiva, y de manera similar para la transitividad. Se sigue que $R'$ tiene las propiedades de minimalidad deseadas.
[1]: $R \circ S = \{(x,z) \in X \times Z \mid \exists y. (x,y) \in R \land (y,z) \in S \}$
Recuerde que una relación $E \subseteq A\times A$ es reflexiva si para todo $a \in A$ tenemos $aEa.
Recuerde que una relación $E \subseteq A\times A$ es transitiva si para todo $a, b, c \in A$ tenemos $aEb$ y $bEc$ implica $aEc$.
Sea $R \subseteq A\times A$ cualquier relación.
El cierre reflexivo $R'$ de $R$ es la relación reflexiva más pequeña que contiene a $R$.
El cierre transitivo $R'$ de $R$ es la relación transitiva más pequeña que contiene a $R$.
Por ejemplo, si tuviéramos la siguiente relación $1R2$ y $2R3$ entonces no tenemos $1R3$ o $1R1$, pero esto lo tenemos en el cierre reflexivo y transitivo.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
¿Es la relación en cuestión 2-aria? Es decir, ¿se asume siempre que la aridad es 2? Es decir, ¿la pregunta se refiere únicamente a relaciones binarias?