Help to inductively define finite trees

definitiondiscrete mathematicsinductionlogicrecursion

In my assignment, I have an in-depth question regarding finite trees.
We are presented with the trees in list form, and an empty list is symbolized as $\emptyset$.

Example: A symmetrical tree with two branches (read: 1 ROOT node with 2 children) is presented this way:

$(\emptyset \ \emptyset)$

(In this example, these two children are also LEAF nodes).

The task is to inductively define a set T of finite trees with roots:
The ROOT node is the node you can envision at the bottom of the tree graphic, as a root in real life.
The LEAF node is the one at the top, and there can be multiple LEAF nodes. If the finite tree only consists of the empty list, the LEAF node and the ROOT node is the same node.

If a node doesn't have a child, it is a LEAF node.

In my inductive definition of the set T, I have written the base case as such (loosely translated):

The base case states that the assumption holds for the empty list, represented as $\emptyset$. In the base case, $\emptyset$ is thus both the ROOT- and the LEAF node. This node has no children.

Another important note is this: the assignment specifies that trees are non-commutative, meaning $((\emptyset) \ \emptyset)$ is different from $(\emptyset \ (\emptyset))$.

Now in the induction step I struggle. How can I make this "not" infinite?

I have tried several times to define this step (the induction step) but I can't wrap my head around this task. Worth to mention that I'm not particularily talented within this type of operation.

Because I believe the nature of the question can be confusing (it already is for me), here's some additional details for context:

It's a Norwegian course and the main chapter of focus here is called "Closure and inductively defined sets".

We are later tasked to give recursive definitions of functions that are connected to the above presented assignment, but that's not the question I present in this post.

EDIT: Made some changes to hopefully clarify some points more clearly.

Best Answer

I am not sure to understand your problem. Anyway, an inductive definition of finite trees (with their root, nodes and leafs) is the following:

  1. Base case: $\emptyset$ is a finite tree, its root is $\emptyset$ itself, and its only leaf and only node is $\emptyset$ itself; $\emptyset$ has no children.
  2. Inductive step: for any $n \in \mathbb{N}^+$, if $t_1, \dots, t_n$ are finite trees then $(t_1 \dots t_n)$ is a finite tree, whose root is $(\dots)$ (with children $t_1, \dots, t_n$) and whose leaves are the leaves of $t_1, \dots, t_n$; the nodes of $(t_1 \dots t_n)$ are its root plus the nodes of $t_1, \dots, t_n$.
  3. Closure: Nothing else is a finite tree.

Usually the closure condition (Point 3) is left implicit in an inductive definition. It amounts to say that the set of finite trees is the smallest set such that Points 1 and 2 holds.

Why does this definition guarantee that the trees you are defining are actually finite (i.e. with a finite number of nodes)? Let us prove it... by induction! Clearly, in the base case the tree $\emptyset$ is finite, because there is only one node. In the inductive step, by induction hypothesis you know that $t_1, \dots, t_n$ are finite, and then $(t_1 \dots t_n)$ is finite since the number of its nodes is the sum of the nodes of all $t_i$'s (a finite sum of finite numbers) plus $1$. As nothing else is a finite tree (according to Point 3), we are sure that all the objects we can build in this way are finite.

As an aside remark, I advise against the idea of comparing an inductive definition to a for-loop in programming. Although both share the idea of repeating an operation, there is a fundamental difference. In a for-loop you just repeat an operation a certain number of times, while in induction the repetition also carries something at each step: the inductive hypothesis.

Related Question