6
$\begingroup$

It is well known that any permutation on a finite set is the product of two involutions. I've wondered about what can happen in infinite sets.

Asuming the axiom of choice, every permutation is still a product$^1$ of disjoint cycles, if we allow for 0-cycles$^2$, that is, permutations such that the subset where they are non-identity is isomorphic (as a set) to $\mathbb Z$, and which look like $f: \mathbb Z \to \mathbb Z$, $f(x)=x+1$ there (up to relabeling). The linked question solves it for finite cycles. And i found that we can write 0-cycles as the product of two involutions as well: the above $f$ can be written as $gh$ where $h(x)=-x+2$ and $g(x)=-x+1$.

Is it consistent with ZF for there to be a permutation of a set that is not the product of two involutions?

$^1$(We might need to use infinite products. Those still make sense if the cycles are disjoint as then each cycle affects a different part of the domain.)

$^2$I came up with the name 0-cycle. It seems like a reasonable name to me in analogy to the characteristic of a field or order of an element of a group. A $k$-cycle behaves like the $x+1$ map in $\frac{\mathbb Z}{k\mathbb Z}$.

$\endgroup$
8
  • 3
    $\begingroup$ A $0$-cycle sounds like a cycle of length $0$ to me; these are cycles of infinite length! $\endgroup$
    – Qiaochu Yuan
    Commented Jul 7 at 17:52
  • $\begingroup$ @QiaochuYuan Yeah, i'm aware not everyone might like this name lol. But it just feels so natural to parametrize the cycle types by natural numbers. $\endgroup$
    – Carla_
    Commented Jul 7 at 18:06
  • $\begingroup$ I think every permutation is a product of disjoint cycles in ZF isn't it? The choiciness in the proof comes from having to pick a bijection from each cycle of length $k$ to $\mathbb{Z}_k$. $\endgroup$
    – Zoe Allen
    Commented Jul 7 at 18:06
  • $\begingroup$ @Zoe: I don't think so. How do you do it? You have to pick an element, then consider its cycle. Then you have to pick another element outside of that cycle, then consider its cycle. And so on; this is a transfinite induction and you have to make a choice at every step. Also, "product" is a bit tricky once there are infinitely many cycles. $\endgroup$
    – Qiaochu Yuan
    Commented Jul 7 at 18:12
  • 1
    $\begingroup$ @QiaochuYuan in ZF we can make a function $(x,n) \to f^n(x)$ so by taking the image of ${x} \times \mathbb{Z}$ we have a function $x \to [x]$ where $[x]$ is the cycle corresponding to $x$. Now take the image of our infinite sex $X$ under that function and we have a partitioning of $X$ into cycles. And for any cycle, $[x]$, we can define $g(y)=y$ if $y \notin [x]$ and $g(y)=f(y)$ if $y \in [x]$. So we can define a set of functions the 'product' of which makes $f$. Is this not correct? $\endgroup$
    – Zoe Allen
    Commented Jul 7 at 18:23

1 Answer 1

Reset to default
1
$\begingroup$

I don't have an answer, but I want to note we know a lot about the structure of the involutions.

Let $\tau(x)=y$. Then we have $$\sigma(y)=f(x)$$ $$\sigma(f(x))=y$$ so $$\tau(f^{-1}(y))=f(x)$$ $$\tau(f(x))=f^{-1}(y)$$ and by repeating the argument: $$\tau(f^n(x))=f^{-n}(y)$$ This means $\tau$ maps cycles to cycles, and that those cycles must be of the same length. Furthermore, it reverses the direction of each cycle.

Intuitively, $\tau$ is effectively pairing each cycle to another cycle of the same length (possibly itself) and picking which element to reverse the cycle around (or antipodal pair of elements if the cycle length is even).

The same applies to $\sigma$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .