[FOM] Finite binary trees and ordinals

[Dennis E. Hamilton]

There are schemes for the ordinal generation of the binary trees.  I don't
know that it satisfies your conditions, but it seems to provide for a
successor process that can also be enumerated for each tree size:

Proskurowski, Andrzej.  On the Generation of Binary Trees.  Journal of the
ACM 27, 1 (January 1980), pp. 1-2.  Available at
<http://doi.acm.org/10.1145/322169.322170>.

Of the citings on the ACM digital library page, two of them might also be
promising: the David Zerling paper and the Renzo Sprugnoli paper.  

Here's the text of the abstract:
  "A binary tree may be uniquelly represented by a *code* reflecting
traversal of the corresponding *extended binary tree* in a given *monotonic*
order.  A general algorithm for constructing codes of all binary trees with
*n* vertices is presented.  Different orders of traversal yield different
orderings of the generated trees.  The algorithm is illustrated with an
example of the sequence of binary trees obtained from ballot sequences."

Ah yes, now I recognize why I remember it as providing Proskurowski
"numberings."

By "extended binary tree" is meant one in which all internal nodes have two
children.  There are no sparse internal nodes - only binary nodes (n of
them) and 0-ary leaves (n+1 of them).

The ordinal generation is of successive extended binary trees with the same
number of internal nodes.  From each one of these, one can generate the ones
that have fewer leaves (but that do not change the status of any internal
node), if desired.

 - Dennis


-----Original Message-----
From: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] On Behalf Of
Peter Smith
Sent: Wednesday, February 14, 2007 06:21
To: Foundations of Mathematics
Subject: [FOM] Finite binary trees and ordinals

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). 

[ ... ]

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 
received! 

-- 
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 

_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom