On Trees

Let's talk about integers with trees.

First, let's define trees. A tree is any number, or any monary operation on a tree, or any binary operation on two trees. Trees can also be called tree expressions

The basic integer, of course, is zero (ask any computer science professor, and chances are they'll tell you that it is a natural number, and the first natural number, to boot). Let's define two monary operations of integers, increment (s, for successor), and decrement (p, for predecessor).

Therefor, s(0) = 1, s(s(0)) = 2, and so on. Similarly, p(0) = -1, p(p(0)) = -2, and so on. Let's also define the following rules, where n is any tree expression:

1: s(p(n))=n
2: p(s(n))=n

With these definitions in hand, we can define a binary operation of trees, addition, +(m,n), with the following rules, where m and n are tree expressions.

1: +(m, 0) = m
2: +(m, n) = +(s(m), p(n))
3: +(m, n) = +(p(m), s(n))

This recursive definition covers all the addition of integers. Challenge: prove that addition, defined like this, is associative and commutative.

The definition of subtraction is similar, but different in some important ways. Define subtractions as a binary operation -(m, n), where m and n are tree expressions, with the following rules.

1: -(m, 0) = m
2: -(m, n) = -(pm, pn)
3: -(m, n) = -(sm, sn)

These definitions are relatively straightforward, but allow us between them to define multiplication, a binary operation x(m, n), where m and n are tree expressions, with the following rules. In the following rules, s(0) is written as 1, s(s(0)) as 2, and p(0) as -1.

1: x(m, 1) = m
2: x(m, -1) = -(m, x(m, 2))
3: x(m, n) = +(m, x(m, p(n)))
4: x(m, n) = -(x(m, s(n)), m)

Enjoy!

Put some pants on,
-Stinja