We saw in the previous post that the problem of producing our isomorphism is solved provided we can produce a sufficiently large coherent collection of coi triples. But how is this to be accomplished? For example, given a (perhaps quite complicated) word , is there a way to find some
and coi
from
to
so that the one-element collection
is coherent? More challengingly, if we have already defined a coherent collection
of coi triples and we are given a word
then can we find
and
so that the slightly larger collection
is again coherent? And even if we can surmount this challenge for a reasonable coherent collection, might we still fail to produce a sufficiently large coherent collection on account of the fact that
but
.
In other words, we may have exhausted the codomain but have failed to fully extend the homomorphism to have the appropriate domain. The reverse problem could also occur: we could exhaust the codomain before producing the isomorphism.
The last two potential problems are solved by alternately considering the elements of and
, ensuring that no
-classes of words are left out of the homomorphism by a transfinite induction. The addition of “just one more coi” can require a great deal of technical care, and we will attempt to give the big ideas behind the ability to do so. We let
where
is the smallest subscript on a letter in
(and
) and similarly
where
is the smallest second subscript of a letter in the word
.
To begin our collection of coi we notice that is coherent (each
is obviously the empty function). So far our collection is countable (since
) and more particularly of cardinality less than
. Next one can prove the following (we’ll number lemmas within this post).
Lemma 1. Suppose that is coherent and that
.
(1) If then we can find
and
so that
is coherent, and
, and
provided
.
(2) If then we can find
and
so that
is coherent, and
, and
provided
.
The proof of this not-very-surprising lemma uses the fact that changing finitely many pure p-chunks of a word does not change the equivalence class. Next we tackle infinitary concatenations of order type
(and we will need to use the crucial fact that the coi collection is not very large).
Lemma 2. Suppose that is coherent,
, and
.
(1) If and we can write
with each
and
, then we can find
and
so that
is coherent.
(2) If and we can write
with each
and
, then we can find
and
so that
is coherent.
To prove part (1) we inductively use Lemma 1 (1) to produce a coherent collection so that
and
. Now an obvious candidate for
would be
, and this infinitary concatenation is indeed a word by the requirement
, but it may not be reduced. Therefore we instead will introduce a sequence of words
with
and
and so that each concatenation
is reduced. The ability to make such a selection is guaranteed be the fact that the number of pure elements in
is at most
. The fact that
is reduced uses the fact that each subword was reduced (and we allowed
to have cardinality either
or
depending on how the word
ends and how the word
begins). The function
will be given in the obvious way:
and the tedious check that
is coherent (and therefore so is ) uses the fact that
.
The proof for part (2) is somewhat similar: one inductively extends to a larger coherent collection
using Lemma 1 (2), but “buffer” words are selected during the induction to be of form
. The sequences
and
are selected so that for each
we have
(this selection makes use of the fact that ).
Another difficult situation arises with concatenations which are of order type .
Lemma 3. Suppose that is coherent,
, and
.
(1) If and we can write
with each
and
and
is a maximal such interval, then we can find
and
so that
is coherent.
(2) If and we can write
with each
and
and
is a maximal such interval, then we can find
and
so that
is coherent.
For (1) we make a list so that for each
exactly one of
or
appears in the enumeration. As in Lemma 2 we produce a coherent collection
by inductively using Lemma 1 and the sequence is again selected to satisfy nice properties; for example the values
shrink to
quite rapidly. Now we select two buffer words
, this time for both the front and tail of the word
, so that
is reduced and some other technical properties hold. Now define the word
where
and
with
if and only if
. From how cleverly the buffer words were selected, one argues that
is reduced, and a coi
is produced from the collection
in the natural way. Part (2) requires similar modifications as those used in Lemma 2 (2). In both (1) and (2) the ability to select suitably nice buffer words makes essential use of the fact that
.
Lemma 4. Suppose that is coherent,
, and
.
(1) If then there exists
and
so that
is coherent.
(2) If then there exists
and
so that
is coherent.
The proof of part (2) is essentially that of part (1), with obvious modifications. For (1) we ask whether there exists a sequence of intervals in
where all
have the same minimum or all have the same maximum,
is properly included into
,
for all
, and
. If such an interval does not exist then we proceed to the next paragraph. If it does exist, then we extend the coi collection so as to include
using Lemma 2 (1) (applied to
in case all the
have a common maximum) and we once again ask whether such a sequence exists for the new collection. We do this over and over again, taking unions of the previously defined coherent collections at limit ordinals. Using certain parameters to keep track of how many times this process iterates, we deduce that it can only be executed countably many times. Thus we move on to the next step.
If is in
, where
is the slightly enlarged coi collection, then we produce
and
using Lemma 1 (1). Else we can write
where
is infinite dense-in-itself and each interval
is nonempty and maximal such that
. The set
may have a maximum and/or minimum, so we let
be the subset excluding such elements. Then
and we use Lemma 4 (1) to extend to a collection, say, indexed by
, so that
and by applying Lemma 1 (1) perhaps once or twice (in case we have a maximum and/or minimum in
) we then obtain the
and
so that the collection
is coherent.
Now that we are armed with Lemma 4 we can define a suitable collection by induction over . Let
(respectively
) be a well-ordering of
(resp.
) such that each element has fewer than
predecessors. We already have
in our collection, where
is an enumeration. Recall that each ordinal
can be expressed uniquely as
where
is either zero or a limit ordinal and
; in particular each ordinal can be considered either even or odd depending on the number
.
Suppose that we have already defined a coherent collection for all
where
is an ordinal below
. Then the collection
is coherent (this is easy to check). If
is even then we select
such that
(such a
exists using a cardinality argument) which is minimal under
and by Lemma 4 (1) we choose suitable
and
to coherently extend and write
,
, and
. In case
is odd we instead select
with
which is minimal under
, use Lemma 4 (2) and extend accordingly. Thus we obtain a larger coherent collection
.
Perform the process on all and it is clear that
is coherent and
and similarly
.
The argument is finished.