Structured numbers. Properties of a hierarchy of operations on binary trees (Q1386446)

The product of two positive integers \(a\) and \(b\) can be defined as the sum of \(b\) factors each equal to \(a\). The \(b\)th exponent of \(a\), denoted by \(a\uparrow b\), can similarly be defined as the product of \(b\) factors each equal to \(a\). The process of getting new operations by repeating old ones ends with exponentiation because this last operation is not associative. For \[ \underbrace {a\uparrow a\uparrow a\uparrow \ldots \uparrow a}_{_b\text{factors}} \] to be well defined, both the number of factors, and the order in which the operations \(\uparrow\) are performed, have to be specified. A way of doing this is to ask the second operand to carry not only a quantitative information, the number of times \(a\) is repeated, but also a structured information, the order in which the operations \(\uparrow\) are performed. Binary trees are naturally designated object to convey such a structured information. In this paper, we introduce a hierarchy of operations on binary trees. The operations are obtained by successive repetition of one initial operation. The first three operations are generalizations of the operations of addition, multiplication and exponentiation for natural numbers. We show that our hierarchy satisfies a range of algebraic properties that generalize the usual properties for addition, multiplication and exponentiation of natural numbers, and we justify the use of binary trees as one representation of the notion of structured number.