The generalized Sierpinski-Mazurkiewicz theorem.

post by Donald Hobson (donald-hobson) · 2022-07-29T00:12:18.763Z · LW · GW · 4 comments

Contents

4 comments

Suppose any uncountable set $S$ and any countable set of bijective transformations $T=\{T_1,T_2,...\}{\forall }_i{T}_i:S\to S\text{bijective}$.

Then assuming that for all pairs of distinct finite sequences of transformations $[p_1,p_2,...p_m]$  and $[q_1,q_2...q_n]$ that the set $\{s\in S:p_1\circ p_2..p_m(s)=q_1\circ q_2..q_n(s\left)\right\}$ is countable.

Then there exists a set $K\subset S,K\ne \varnothing$ partitioned into $K_1,K_2,...$ such that $K_i=T_i\left(K\right)$..

Proof.

Consider the set of all sequences of transformations (type signature $N\to T$) 

Form the equivalence relation $\sim$ by $a\sim b⟺\exists m,n\in N:\forall i\in N:a_{m+i}=b_{n+i}$

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 $\exists m\forall i:a_i=a_{i+m}$.  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 $Q$.

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

Note that each equivalence class is countable, as for any $a\sim r\in R$ then $a$ can be represented by $(m,n,a_1,a_2,...a_m)$ as the rest of the sequence can be filled in using the equivalence relation $\forall i:a_{m+i}=r_{n+i}$. Use countable union of countable sets a lot.

Note that, given any function $f:R\to S$ can be uniquely extended into a function $f:Q\to S$ such that $f\left(\right[a_1,a_2,...\left]\right)=a_1\left(f\right([a2,...])$. Use the rule $f\left(a\right)=a_1\circ a_2..a_m\circ r_n^{-1}\circ r_{n-1}^{-1}..r_1^{-1}\left(f\right(r\left)\right)$. This is well defined because, if we increment both $m$ and $n$, then we are just applying an extra function and inverse. But those cancel each other out, by the condition in the equivalence relation. Also $m-n$ is a fixed constant for particular $a$ and $r$, because we ruled out all eventually cyclic sequences.

Pick any $r\in R$. For any $a,b\sim r$, there must be only countably many $s\in S$ such that the extension of $f\left(r\right)=s$ has $f\left(a\right)=f\left(b\right)$. Looking at the definition of the generalization above, we see its a finite composition of bijections. So Generalize: $f\left(r\right)\to f\left(a\right)$ is a bijection (type $S\to S$). Let $c=[a_{m+1},a_{m+2},...]$ where $m,n$ are such that $\forall i:a_{m+i}=b_{n+i}$. Then $f\left(a\right)=a_m\circ ..a_1\left(f\right(c\left)\right)$ and $f\left(b\right)=b_n\circ ..b_1\left(f\right(c\left)\right)$. But the set of overlaps between $a_m\circ ..a_1$ and $b_n\circ ..b_1$ are countable (this is where we use that strange condition) And the generalization $f\left(c\right)$ is a bijective function of $f\left(r\right)$.. So this rules out a countable number of $s\in S.$

Now there are countably many $a,b\sim r$, so given the uncountability of $S$, its possible to choose  $s=f\left(r\right)$ such that $\forall a,b\sim r:f\left(a\right)\ne f\left(b\right)$.

This lets us define $K=\left\{f\right(a):a\sim r\}$. Where $K_i=\left\{f\right(a):a\sim r,a_1=T_i\}=\left\{T_i\right(f\left(\right[a_2,a_3,..\left]\right)):a\sim r\}$

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

4 comments

Comments sorted by top scores.