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...101011_{BIN} 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) ^{h}0_{BIN}, 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.1t_{1}0...1t_{k}0, where
0.t_{1} through 0.t_{k} 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(t_{1})>e(u_{1}) or
(e(t_{1})=e(u_{1}) and
e(t_{2})>e(u_{2})) or
(e(t_{1})=e(u_{1}) and
e(t_{2})=e(u_{2}) and
e(t_{3})>e(u_{3})), etc., where
{t_{k}} and {u_{k}} 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

**Point #4: The Euler number of a tree T is
0.1T_{1}0...1T_{k}0, where
0.T_{1} through 0.T_{k} 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 *t*_{1}, where *t*_{1} 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 *t*_{1}. (The number of copies is a natural, and therefore has
a minimum.) We then continue to remove all trees except those that have
*t*_{2} as their first non-*t*_{1} sub-tree, where
*t*_{2} is the minimum of the candidates, then require further
a minimum number of repetitions of *t*_{2}, 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, *t*_{1},
*t*_{2},... 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.