Base case ~: For all $s,s' \in S$

$$treeS \sim treeS'$$

Step case ~: for $ t \sim t', t'' \sim t'''$ and $s,s' \in S$ $$tree_s(t,t') \sim tree_{s'}(t'',t''')$$

I was able to understand what property which should represent, which is all trees with the same structure

How can I prove this relation is reflexive by induction?

What I did was:

We want to prove $tree_s(t,t') \sim tree_{s}(t',t')$

Base case:

$tree_s \sim tree_s$ --- This is true using the base case

Induction Hypothesis:

This holds true for trees t' and t''

Step case: (i'm not quite sure from where I start, if I said first $tree_s(t,t') \sim tree_{s}(t',t')$ (which is reasonable because in the step case we replace the $treeS$ with $tree_s(t,t')$) then this is what we want to prove and we shouldn't get this without doing any induction. )


  • $\begingroup$ It is not very clear what all things are in your statement. Are you talking about binary trees and the equivalent relation being that the trees have the same structure ? But in this case your top down approach seems odd, to define it by induction a bottom up approach would be simpler. Base case is 2 leafs are always equivalent, and the step case would be s.{t1,t2}~S{T1,T2} if t1~T1 and t2~T2. So you can run an induction on the tree depth. $\endgroup$ – zwim Mar 7 '17 at 5:49
  • $\begingroup$ I think it might help to elaborate on the terminology/definitions you are using since some notations are unique to certain books. With the given information, I am having trouble identifying exactly what is being asked. $\endgroup$ – benguin Mar 7 '17 at 5:50
  • $\begingroup$ @benguin $\sim$ is a relation of full binary trees. The question is to prove that the relation is reflexive by induction. $\endgroup$ – Zed Mar 7 '17 at 5:53
  • $\begingroup$ Is $S$ supposed to be the "values" each "node" can take on and $tree_s(t,t')$ is the tree generated by considering a rooted tree whose left subtree is $t$, right subtree is $t'$, and whose root is a node that holds the value $s$? $\endgroup$ – benguin Mar 7 '17 at 6:08
  • $\begingroup$ @benguin That is true, $S$ is the label (value) and $t$ and $t'$ are subtrees. $t$ is the left subtree and the other one is the right subtree $\endgroup$ – Zed Mar 7 '17 at 6:10

Let's define binary trees $\mathcal B$ recursively by :

$\begin{cases} \varnothing\in\mathcal B \\ u\in\mathcal B\ \ \mathrm{and}\ \ u\neq\varnothing\iff u=(a,b)\ \mathrm{with}\ a\in\mathcal B,b\in\mathcal B \end{cases}$

An element $t=(\varnothing,\varnothing)$ is called a leaf, and if either $a$ or $b$ not empty then $u=(a,b)$ is called a node or subtree.

We can define the structural relation by :

$\begin{cases} \varnothing\sim\varnothing \\ (a,b)\sim (c,d)\iff (a\sim c)\land (b\sim d) \end{cases}$

Let's also define the depth $\delta$ of a tree by :

$\begin{cases} \delta(\varnothing)=0 \\ u=(a,b)\quad\mathrm{then}\quad\delta(u)=1+\max(\delta(a),\delta(b)) \end{cases}$

To study the reflexivity of the relation, we can initiate an induction on the depth of a tree.

$\mathscr P(n)=\ $"the relation $\sim$ is reflexive on trees whose depth is $\le n$"

$\mathscr P(0)$ is true since $\varnothing\sim\varnothing$ and $\delta(\varnothing)=0$.

Now let assume $\mathscr P(n)$ and let's examine $\mathscr P(n+1)$ ?

If $u\in\mathcal B$ and $\delta(u)=n+1$ then $\exists a\in\mathcal B,b\in\mathcal B$ such that $u=(a,b)$ [rem: $u$ cannot be empty otherwise, its depth would be $0$].

$\delta(u)=n+1=1+\max(\delta(a),\delta(b))\implies \delta(a)\le n\ $ and $\ \delta(b)\le n$.

So we can apply induction hypothesis to get $a\sim a$ and $b\sim b$.

By definition of $\sim$ we can also write that $(a,b)\sim(a,b)$ so $u\sim u$ and $\mathscr P(n+1)$ is proved, which completes th induction proof.

Thus $\forall u\in\mathcal B$ we have $u\sim u$.


Going off of Zwim's comment. You could induct on the depth $d$ of the tree. If the depth of the tree hasn't been defined for you, then you can define it yourself by saying that for all $s$, $tree(s)$ has a depth of $0$ and a tree of the form $tree_s(t, t')$ has a depth $1+\max\{d(t),d(t')\}$.

Now, let us induct on the depth of tree. The base case is trivial enough, so I'll just focus on the inductive step.

Suppose that the relation is transitive for all trees whose depth is $k$ or less and consider a tree $T$ whose depth is $k+1$. This tree must have the form $T= tree_s(t,t')$ for some $s \in S$ and trees $t,t'$. (The tree cannot have the form $T=tree(s)$ because trees of this form have depth $0$ and the depth of $T$ is $k+1 \geq 1 > 0$.) Notice that the depth of tree $T$ is both $k+1$ and $1+\max\{d(t),d(t')\}$ and thus $k = \max\{d(t),d(t')\}$. From here, notice that $k = \max\{d(t),d(t')\} \geq d(t)$ and similarly, $k \geq d(t')$. Thus, the trees $t,t'$ are trees of depth $k$ or less and by the inductive hypothesis, $t \sim t$ and $t' \sim t'$.

Thus, since $t \sim t$ and $t' \sim t'$ and $s,s \in S$, $$T = tree_s(t,t') \sim tree_s(t,t') = T.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.