# Countable sets of permutations of an infinite binary sequence

Being motivated by this recent post of mine, I am thinking about the base 2 decimal expansion of irrational algebraic numbers. My main question is whether or not the reasoning I outline below contains any major flaws.

First of all, it should be clear that in the base 2 decimal expansion of an irrational number on the interval [0,1], the digits 0 and 1 appear infinitely often; since otherwise the decimal expansion would terminate and the number would be not be irrational.

Therefore, I consider permutations of the sequence $I$ = 101010101010....

Let $K$ be the group of all permutations of $I$, and let $Q$ be an infinite subgroup of $K$.

Then I claim that every $Q$ has a basis in terms of the fundamental permutation of switching the position of two elements. This amounts to the claim that every permutation in $Q$ can be written as a countably infinite composition of switching operations.

(to be clear, a switch is a permutation $A$ik which exchanges the $i$ and $k$ positions of some infinite binary sequence)

I conjecture that $Q$ is a countably infinite subgroup of $K$ if and only if it has a basis whose elements commute (i.e. the basis of $Q$ never switches the same position in the sequence twice)

In the first direction, assume $Q$ has a commuting basis; then it's clear that the elements of $Q$ can be listed according to the order of lowest to highest positions of switches, and therefore can be counted.

In the other direction, assume $Q$ has a non-commuting basis, but is countable. Then by writing the elements of $Q$ in a list where each element is written in terms of an ordered composition of basis elements, it's clear that we can apply the diagonal method to construct an element of $Q$ which is not on the list; which is a contradiction.

(EDIT: to clarify the comment below, I originally called Q a subset, but edited it to subgroup)

-
I don't understand what you mean by a basis of a subset of a group. –  Qiaochu Yuan Jul 31 '10 at 17:20
In any case, I am pretty sure both directions of your argument are invalid. Being orderable doesn't imply be countable: a counterexample is the subgroup generated by the transpositions (2i-1, 2i) for positive integers i, which is uncountable. AS for the other direction, the subgroup of permutations which switch only finitely many locations is nonabelian but countable. –  Qiaochu Yuan Jul 31 '10 at 17:32
I think this is the weak point of my argument. I am trying to mimic the case of permutations of a finite sequence. Any permutation of a finite sequence can be written as the composition of a finite number of switching operations. So the "basis" elements are the switch operations. For the case of permutations of an infinite sequence, I believe/assume that every permutation can be written as the countably infinite ordered composition of switching operations. –  Matt Calhoun Jul 31 '10 at 17:36
Ah, sorry: in the first example I just mean the subgroup of all elements which switch 2i-1 with only 2i. In any case, whether that's true or not (with the right definition of countably infinite composition) your last two arguments are still invalid if you mean what I think you mean by "basis." –  Qiaochu Yuan Jul 31 '10 at 17:43
What is meant by "a countably infinite composition of switching operations"? As you apply the operations, one after another, a number might get moved infinitely often; where should such number be mapped under the composite permutation? For a specific example, what is the composition of $A_{12}$ followed by $A_{23}$ followed by $A_{34}$ followed by $\dots$? The number 1 gets mapped to 2 by the first switch, then to 3 by the next switch, then to 4, etc. Where does the composite permutation send 1? –  Andreas Blass Jul 31 '10 at 21:53

I believe we cannot afford pushing 1 to infinity since its image will be undefined. The question whether every permutation of the naturals could be obtained as some composition of transpositions $t_1,t_2,\dots$ is cute, and I think that the answer is Yes'': It suffices to prove this where the $t_i$ are allowed to be any finitely supported permutations, and then we pick each $t_n$ such that $t_n\cdots t_1$ restricted to $\{1,\dots,n\}$ is equal to the values of the prescribed permutation on $\{1,\dots,n\}$. Then the permutation $$\cdots t_2t_1$$ is then well defined and equal to the prescribed one.