# 11

Suppose any uncountable set  and any countable set of bijective transformations .

Then assuming that for all pairs of distinct finite sequences of transformations   and  that the set  is countable.

Then there exists a set  partitioned into  such that ..

Proof.

Consider the set of all sequences of transformations (type signature

Form the equivalence relation  by

This is the sequences that are the same up to a finite number of insertions, deletions and replacements. Discard all the sequences equivalent to any cyclic sequence. (A sequence is cyclic if .  Think if these like the digits of rationals, they might do all sorts of things at first, but eventually they repeat the same thing over and over) Call the set of remaining sequences .

Pick a representative of each equivalence class. Call this set of representatives .

Note that each equivalence class is countable, as for any  then  can be represented by  as the rest of the sequence can be filled in using the equivalence relation . Use countable union of countable sets a lot.

Note that, given any function  can be uniquely extended into a function  such that . Use the rule . This is well defined because, if we increment both  and , then we are just applying an extra function and inverse. But those cancel each other out, by the condition in the equivalence relation. Also  is a fixed constant for particular  and , because we ruled out all eventually cyclic sequences.

Pick any . For any , there must be only countably many  such that the extension of  has . Looking at the definition of the generalization above, we see its a finite composition of bijections. So Generalize:  is a bijection (type ). Let  where  are such that . Then  and . But the set of overlaps between  and  are countable (this is where we use that strange condition) And the generalization  is a bijective function of .. So this rules out a countable number of

Now there are countably many , so given the uncountability of , its possible to choose   such that .

This lets us define . Where

Originally my proof tried to use transfinite induction to construct this for every , and keep them all from overlapping. Then I realized that I only needed a single , which made the proof simpler.

New Comment