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:

  1. $a \to^*a$ (reflexive)
  2. ${a \to^*b \quad b \to c \over a \to^*c }$ (step)

The questions are:

  1. What are the induction rules for $\to^*$?
  2. Show that $\to^*$ is reflexive.
  3. 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
scroll top