1
$\begingroup$

I am currently struggling with this question. It is obvious that the relation is transitive however I'm not sure how to prove it.

A call graph is a relation RC and a pair (f, g)  of function names is in RC, iff the body of function f calls the function g. For example for the function
f ( ) {
g ( );
h ( );
}

the pairs (f, g) and (f, h) are in the relation RC. The transitive closure of the relation RC written as T rans(RC) is a new relation, which contains a
pair(f, f0), if there is a chain (f, f2),(f2, f3), ...,(fn−1, f0) of pairs all contained in RC. Formally
this can be defined as 

Trans(RC) = {(f, f0)| ∃(f1, ..., fn) with f = f1∧f0 = fn∧∀i ∈ {1, ...,(n−1)}(fi, fi+1) ∈ RC}

The symmetric closure of the relation RC is a new relation written as Sym(RC), which contains
all pairs (f, g) from RC along with their corresponding pairs (g, f).

(a) Prove that T rans(RC) is transitive
$\endgroup$
5
  • 1
    $\begingroup$ Can you explain in words why it is obvious to you that the relation is transitive? $\endgroup$
    – hmakholm left over Monica
    Oct 5, 2015 at 17:24
  • 1
    $\begingroup$ The proof just falls out of the definition. If $(f, f0) \in Trans(RC)$ and $(f0, g0) \in Trans(RC)$, there's a chain of pairs in $RC$ from $f$ to $f0$, and another chain of pairs in $RC$ from $f0$ to $g0$. To show that $(f, g0)$ is in $Trans(RC)$, you need a chain from $f$ to $g0$. But you know there is one. $\endgroup$
    – BrianO
    Oct 5, 2015 at 17:24
  • $\begingroup$ ^That's why it is obvious. Is that all there is to it or should I provide a more in depth proof? $\endgroup$
    – moha
    Oct 5, 2015 at 17:25
  • $\begingroup$ If the transitive closure weren't transitive, our God would be really unfair. $\endgroup$
    – Jack D'Aurizio
    Oct 5, 2015 at 17:28
  • $\begingroup$ @moha: You're probably expected to explicitly write down the chain from $f$ to $g_0$ that is obviously there. You can most probably get away with using dots ("$\ldots$") for this, since there are dots in the definition you're working from too. $\endgroup$
    – hmakholm left over Monica
    Oct 5, 2015 at 17:29

1 Answer 1

Reset to default
1
$\begingroup$

In general, if $X$ is a set, and $R\subseteq X\times X$ is a relationship, we can define a sequence of relationships:

$$\begin{align} R^1&=R\\ R^{n+1}&=R^{n}\circ R = \{(x,y)\in X\times X\mid \exists z\in X: (x,z)\in R^n\text{ and }(z,y)\in R\} \end{align} $$

We then define:

$$R^{t} = \bigcup_{i=1}^{\infty} R^{i}=\{(x,y)\mid\exists i:(x,y)\in R^{i}\}$$

This is the rigorous form of your $\mathrm{Trans}(R)$.

Step 1: Prove by induction on $n$ that if $(x,y)\in R^{n}$ and $(y,z)\in R^{m}$ then $(x,z)\in R^{m+n}$.

Step 2: Use Step 1 to show that if $(x,y),(y,z)\in R^{t}$ then $(x,z)\in R^{t}$, and therefore, $R^t$ is transitive.

$\endgroup$
3
  • $\begingroup$ I'm aware of the definition of transitivity that if there's an (x,y) and a (y,z) there must be an (x,z), however in this case that is always the case as if we call functions in the following order f { g { h();}} then we have an (f,g) and an (g,h) and naturally we have a (f,h) since h is called within g and g is already within f. However, I fear that just simply stating that won't be enough. $\endgroup$
    – moha
    Oct 5, 2015 at 17:30
  • $\begingroup$ "In this case that is always the case as if..." Sorry, but that sentence seems to have gotten away from you. I'm not following. Where does my general definition differ from your definition? $\endgroup$
    – Thomas Andrews
    Oct 5, 2015 at 17:42
  • $\begingroup$ You wanted a rigorous proof, but a rigorous proof requires a rigorous definition. The definition as given is equivalent to saying $(f,g)\in \mathrm{Trans}(RC)$ if $(f,g)\in (RC)^n$ for some $n$. $\endgroup$
    – Thomas Andrews
    Oct 5, 2015 at 17:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .