0
$\begingroup$

The closure of a relation $R$ over a set $S$ is denoted $R[S]$ and calculated via $\bigcup_{i\in\mathbb{N}}Y_i$ where $Y_0=S$ and $Y_{n+1}=Y_n\cup R(Y_n)$. ($R(Y_n)$ is the image of $Y_n$ under $R$).

Given that $Q\in A\times A$, I am attempting to find and express a relation $R = \{((x_1, y_1), (x_2, y_2)):x_1,y_1\in A, \ldots \}$. The $"\ldots"$ stand in for where my wits have so far failed me, I am unable to figure it out what to place there.

$R$ is supposed to be as such that when used alongside some (I believe) $S = Q$, in the closure formula presented above, it yields the transitive closure of Q. I believe that in order for this to happen, $R[Q] = Q \circ Q$, $R[Q\circ Q] = Q\circ Q\circ Q$, et cetera.

I have attempted various solutions, them so far failing me, I can recall that I have tried at least:

  • $\ldots = x_2,y_2\in A, x_1=x_2$ - This yields far too many elements of $R$, but is seemingly a superset of the desired $R$.
  • $\ldots=x_2,y_2\in A, x_1 = x_2, x_1\in(\operatorname{domain} Q), y_2\in(\operatorname{range} Q)$ - This still yields too great an $R$, but is smaller, yet is still seemingly a superset of the desired $R$.
  • $\ldots = x_2,y_2 \in A, (x_1,x_2)\in Q$ - This is too restrictive, as $Q\circ Q$ is prone to contain pairs not in $Q$.

And some more I have since forgotten.

Would anyone mind offering me some guidance as how to construct $R$? Many thanks for all help in advance. It is preferably to avoid recursion unless absolutely unavoidable.

$\endgroup$
5
  • $\begingroup$ I don’t really get what is the initial data and what is your goal $\endgroup$
    – julio_es_sui_glace
    Commented Apr 14 at 0:05
  • $\begingroup$ If you see your relation as a graph, this would be the finite path connected component $\endgroup$
    – julio_es_sui_glace
    Commented Apr 14 at 0:16
  • $\begingroup$ @julio_es_sui_glace I believe I need to find an relation $R$ such that $R[X] = Q \circ X$. I have access to $Q$, $A$, and may assume that $X$ is $Q$ composed with itself some finite number of times. $\endgroup$
    – Aresiel
    Commented Apr 14 at 8:53
  • $\begingroup$ How do you define your composition? Do you mean $$R(X) = \{y \in A \mid \exists x \in X, R(x,y) \}$$ or $$R[X] = \{y \in A \mid \exists n \in \mathbb N, a_0, \dots a_n \mid a_0 \in X, a_n =y, R(a_k,a_{k+1}) , k<n \}$$ $\endgroup$
    – julio_es_sui_glace
    Commented Apr 14 at 10:58
  • $\begingroup$ @julio_es_sui_glace $R[X] = Q\circ X = \{ (a,c) : \exists b \in A, (a,b)\in Q, (b,c)\in X \}$. If I'm not mistaken. The issue being that I need to construct $R$ without having access to $X$. $\endgroup$
    – Aresiel
    Commented Apr 14 at 11:32

0

Reset to default

You must log in to answer this question.