Prove that the transitive closure of a relation is transitive

38 Views Asked by At

I've been thinking about this question for a while but can't exactly figure out how to do it. I'm thinking it has something to do with showing that given $(x, y)$ and $(y, z)$ within compositions of $R$, then $(x, z)$ is present within the closure. For context, the book I'm using defines the transitive closure of $R$ as $R^+ = \bigcup_{0 < n \in \mathbb{N}} R^n$, where $R^1 = R$, $R^{n+1} = R^n | R$, the composition of $R^n$ and $R$, and $R$ is a binary relation.