Consider, for example, the subset of all Euler numbers for embeddings whose value is greater than 2/3=0.10101010...BIN. This includes the Euler numbers 0.1010...101011BIN for any number of repetitions of "10", corresponding to an embedding that has n branches of length 1 followed by a single branch of length 2. This set contains elements arbitrarily close to 2/3. It has no minimum. (Another interesting fact is that 2/3 itself is not an Euler number, because its binary expansion is infinite. This makes the Euler numbers for embeddings not only not well-ordered but also not closed from below.)
First, some preliminaries.
Point #1: The Euler number of a tree begins with
0.(1)h0BIN, where h is the height of the
tree.
Proof: trivial, by induction.
Point #2: Let a tree's sub-trees be the set of trees remaining if the tree's
root and all edges directly connected to the root are erased (with the
sub-trees' roots being the vertices that were at depth 1 in the original tree).
Any Euler number for a tree embedding t is
0.1t10...1tk0, where
0.t1 through 0.tk are Euler
numbers for the embeddings of each of the tree's k sub-trees.
Proof: trivial, by definition of Euler numbers.
Point #3: The sorting order for Euler numbers for a tree embedding is
lexicographic by sub-trees. (That is to say,
e(t)>e(u) if and only if
e(t1)>e(u1) or
(e(t1)=e(u1) and
e(t2)>e(u2)) or
(e(t1)=e(u1) and
e(t2)=e(u2) and
e(t3)>e(u3)), etc., where
{tk} and {uk} are the
sub-trees of t and u, respectively.)
Proof: In comparing two binary decimals, one goes from left to right until
finding the first digit where there is a difference. This is already
lexicographic sorting. It extends directly to lexicographic sorting by
sub-trees if no strings x and y exist, where x
and y correspond to the digits of the Euler tours of two tree embeddings,
such that 1x0 is a proper prefix of 1y0. However, this "if" is
trivially true: the number of
"1"s in 1x0 equals the number of "0"s in it, which is not true for any
non-trivial prefix of "1y0".
Point #4: The Euler number of a tree T is
0.1T10...1Tk0, where
0.T1 through 0.Tk are the Euler
numbers for each of its k sub-trees, sorted by decreasing value.
(We will henceforth refer to sub-trees as a sorted sequence, using this
order.)
Proof:
This is a corollary of Point #2 and Point #3, using induction on the height
of the tree.
Let us now go on to the main proof.
Let T be a set of trees and X be the set of T's Euler numbers. We are trying to find a minimum for the values in X.
As a first step, consider that from Point #1 we know that this minimum must correspond to some t in T with minimal height in T. (Height is a nonnegative integer, which is a well-ordered set, so this minimum is defined.) We can, therefore, remove from T all trees of height greater than the height of t. Equivalently, we only need to consider sets T that have some fixed height, h, to complete the proof.
This being the case, we can use induction on h. The claim is clearly true for h=0: there is only one such tree. We now assume that all sets of trees of height up to some h have a minimum, and prove for h+1.
We do this by iteratively removing from the set all trees that are not candidates to be the minimum. First, we remove all trees except those beginning with t1, where t1 is the minimal sub-tree to exist as a first sub-tree in what remains of T. The sub-trees are trees of height up to h, so the minimum exists by the induction hypothesis.
We further remove all trees except those that have a minimal number of copies of t1. (The number of copies is a natural, and therefore has a minimum.) We then continue to remove all trees except those that have t2 as their first non-t1 sub-tree, where t2 is the minimum of the candidates, then require further a minimum number of repetitions of t2, etc..
If at any point only a single tree is left, it is the minimum and we are done. (All other trees in T had Euler numbers that differed from it in a position already scanned, and the difference showed them to be larger than the one the algorithm isolated.) If at any point we reach the end of a tree, it is the minimum and we are done. (As above, all trees that were previously eliminated from T had larger Euler numbers. Any other tree still left in the set has an Euler number that has this tree's Euler number as a proper prefix. Its Euler number is therefore larger.) If there is no minimum, the process described must continue forever. However, this creates an infinite decreasing sequence, t1, t2,... of trees of height at most h, contradicting the induction hypothesis. (A well-ordered set cannot contain an infinite decreasing sequence. Consider the set of all elements in the sequence. It must have a minimum.)
Q.E.D.