[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 

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 

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 

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

Dr Peter Smith: Faculty of Philosophy, University of Cambridge

Gödel's Theorems: http://www.godelbook.net 
LaTeX for Logicians: http://www.phil.cam.ac.uk/teaching_staff/Smith/LaTeX/ 
Idle musings: http://logicmatters.blogspot.com 

More information about the FOM mailing list