Prove a relation to be reflexive by induction

Question

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. )

Thanks

Answer 1

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$.

Answer 2

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.$$