# [FOM] Finite binary trees and ordinals

Peter Smith ps218 at cam.ac.uk
Wed Feb 14 09:21:22 EST 2007

```The following seem 'natural' conditions to put on a well-ordering <
of finite binary trees:

1. If A is a proper part of B, then A < B.
2  If T(A) is a tree containing A as a part, and T(B) is a properly
formed tree that results from substituting B for A, then if A < B then
T(A) < T(B).

These are simply the thoughts that a part should precede the bigger
whole which contains it, and that two wholes which differ in just one
part should be ordered to reflect the ordering of those differing
parts.

Now, it certainly is the case that there is a well-ordering that
respects 1 and 2, a well-ordering of the order-type of the ordinals
less than epsilon_0 (see e.g. http://www.ml.kva.se/preprints/meta/
JervellMon_Jun_11_10_58_31.rdf.html -- the idea goes back to
Ackermann).

But a natural question arises: What are the minimum equally
'natural' conditions that, if added to 1 and 2, ENSURE that the
well-ordering is of the order-type of the ordinals less than
epsilon_0?

As I say, that seems a natural question, but I can't find any
treatment of it. Any thoughts and/or pointers gratefully