Induction rules for reflexive, transitive closure
-
04-11-2019 - |
Question
I'm trying to solve an exercise on inductive definitions, the premiss is:
Let $\to$ be a relation on $A$ and $\to^*$ its reflexive, transitive closure, which is defined by following two rules:
- $a \to^*a$ (reflexive)
- ${a \to^*b \quad b \to c \over a \to^*c }$ (step)
The questions are:
- What are the induction rules for $\to^*$?
- Show that $\to^*$ is reflexive.
- Show that $\to^*$ is transitive.
The first question startles me, I view ${a \to^*b \quad b \to c \over a \to^*c }$ as the induction rule. Is this the complete answer?
And can I show the reflexivity with ${a \to^*b \quad b \to a \over a \to^*a }$?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange