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 Rr=R∪{⟨a,a⟩:a∈A}, agregando a R todos los pares ⟨a,a⟩ que no estén en él. Luego, cada vez que tengas ⟨x,y⟩ y ⟨y,z⟩ en Rr, agrega ⟨x,z⟩ si aún no está ahí para obtener R2r. Repite para obtener R3r. 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?