I am currently working through Chiswell/Hodges's "Mathematical logic" (Oxford University Press, 2007) and am stuck at an exercise (3.2.6) regarding isomorphisms between two planar trees. This is the exercise:
"Suppose $(N_1, D_1)$ and $(N_2, D_2)$ are planar trees. An isomorphism from $(N_1, D_1)$ to $(N_2, D_2)$ is a bijection $f : N_1 → N_2$ such that for every node $μ \in N_1$, if $D_1(μ) = (ν1,… ,νn)$ then $D_2(fμ) = (fν1,… ,fνn)$. We say that two planar trees are isomorphic if there is an isomorphism from the first to the second. (Then isomorphism is an equivalence relation.) Prove: If $f$ and $g$ are two isomorphisms from $(N_1,D_1)$ to $(N_2,D_2)$ then $f = g$. [If $(N_1,D_1)$ has height $n$, prove by induction on $k$ that for each $k$, the functions $f$ and $g$ agree on all nodes of height $n − k$ in $N_1$.]"
I don't really know how to proceed in the demanded induction. I would be very thankful for help!
Relevant definitions from this chapter might be:
"Definition 3.2.1 A (planar) tree is an ordered pair $(N,D)$ where
(a) $N$ is a finite non-empty set whose elements are called nodes;
(b) $D$ is a function that takes each node μ in $N$ to a sequence (possibly empty) of distinct nodes:
(3.17) $$D(μ) = (ν_1,… ,ν_n)$$
the nodes $ν_1, . . . , ν_n$ are called the daughters of μ, and μ is called the mother
of $ν_1,… ,ν_n$;
(c) every node except one has exactly one mother; the exception is a node called
the root, in symbols √, which has no mother;
(d) there are no cycles, that is, sequences
(3.18) $$ν_1,ν_2,… ,ν_k (k > 1)$$
where $ν_k =ν_1$ and each $ν_i$ with $1\leq i<k$ has mother $ν_{i+1}$." (p. 38)
"Definition 3.2.2
(a) In a tree, an edge is an ordered pair of nodes $(μ,ν)$, where μ is the mother of ν. (So the lines in a tree diagram represent the edges.) Mixing metaphors, we describe a node as a leaf of a tree if it has no daughters. (Botanically speaking our trees are upside down, with their root at the top and their leaves at the bottom.)
(b) The number of daughters of a node is called its arity. (So the leaves are the nodes of arity 0.)
(c) We define a height for each node of a tree as follows. Every leaf has height 0. If μ is a node with daughters $ν_1,… ,ν_n$, then the height of μ is
(3.19) $$\text{max}\{\text{height}(ν_1 ), . . . , \text{height}(ν_n )\} + 1$$
The height of a tree is defined to be the height of its root (cf. (3.15)).
(d) A path from node ν to node μ is a set of nodes $\{ν_0,… ,ν_k\}$ where $ν_0$ is ν, $ν_k$ is μ, and for each $i<k,ν_i$ is the mother of $ν_{I+1}$. A path from the root to a leaf μ is called a branch (to μ)." (p. 39)
"Definition 3.2.5 A compositional definition δ is a set of rules that tell us how to put a left labelling on any parsing tree, in such a way that the left label on any node μ—write it $δ(μ)$—is determined by just two things:
- the right-hand label on μ and
- the sequence of values $(δ(ν_1), . . . , δ(ν_n))$ where μ has daughters $ν_1, . . . , ν_n$ from left to right." (p. 40)
Best Answer
In general, formation and detection of isomorphism among trees is a complicated problem of graph theory. However, we deal here with quite a restricted class of rooted and labelled trees which facilitates the task substantially.
For a complete exposition of a proof by induction, we begin with the least value of the inductive variable, $k = 0$, which corresponds to the height $n$, that is, the root node. Then, we proceed to exhaust all the possible structural cases, similar to the inductive definition of formulas:
We notice that the variety of structural cases are also restricted: The logical vocabulary is fixed across trees. Thus, only the signature $\sigma$ remains to vary.
Suppose $(N_1, D_1)$ is of signature $\sigma_1$ and $(N_2, D_2)$ is of signature $\sigma_2$. So, $f: N_1 → N_2$ is virtually a one-to-one and onto map from $\sigma_1$ to $\sigma_2$:
$\mu\mapsto \mu '$
$\nu_1\mapsto \nu_1 '$ and so on.
$g: N_1 → N_2$ is also virtually $f$ possibly except for the distinction that $g$ maps to different $\sigma_2$-symbols than $f$ does:
$\mu\mapsto \mu ''$
$\nu_1\mapsto \nu_1 ''$ and so on.
Consequently, $f$ and $g$ only produce alphabetic variants of a parsing tree, which is irrelevant for isomorphism, hence $f = g$.