Définitions par induction

On remarque que l'ensemble des arbres binaires est défini par induction. C'est-à-dire à partir d'un ensemble d'atomes et de règles. Les atomes sont les éléments de l'ensemble qui sont indécomposables, par exemple l'arbre vide $\emptyset$. Les règles permettent à partir d'éléments d'un ensemble de créer d'autres éléments. Par exemple, si $A$ et $B$ sont des arbres binaires, et $r$ un noeud, alors le triplet $(A, r, B)$ est un arbre binaire.