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 ..


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
4 comments, sorted by Click to highlight new comments since: Today at 9:55 PM

Huh, that's a really cool theorem. Someone should make a distillation of this post with cool fractal visualizations (see e.g. Chaos Games for some idea of the relation).

Sure. The image is kind of a diffuse cloud of points. Its actually dense on the plane. But I can still kind of plot it by gradually fading points out. The transforms I used are shifting right by 0.1 and rotating clockwise by 1 radian. Ie this image is K, st shift_right(K)  Rotate_clockwise(K)=K

That does not look like it will be mapped into a subset of itself if I shift it right by 0.1.

  Here is a link (as lesswrong doesn't seem to support animated gifs in comments)

Note that the points are gradually fading out, if you shift a bright point right by 0.1, you find a slightly fainter point.