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
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
The argument is finished.