The first thing to notice is that infinite permutations may have infinite support, that is, they may move infinitely many elements. Therefore, we cannot expect to express them as finite compositions of permutations having only finite support.

But if we allow (well-defined) infinite compositions, then the answer is that every permutation is a composition of transpositions. To see this, suppose that f is a permutation of ω. First, we may divide f into its disjoint orbits, where the orbit of n is defined as all the numbers of the form f^k(n) for any integer k. The action of f on each of these orbits commute with each other, because the orbits are disjoint. The finite orbits are just finite cycles, which can be expressed as a product of transpositions in the usual way. An infinite orbit looks like a copy of the integers, since it will be infinite in both directions. All such cycles are isomorphic to the shift map on the integers, which can be represented in cycle notation as (... -2 -1 0 1 2 ...). This permutation is equal to the following product of transpositions

• (... -2 -1 0 1 2 ...) = [(0 -1)(0 -2)(0 -3)...][...(0 3)(0 2)(0 1)]

Let me explain what this means. On the right hand side, I have two infinite products of transpositions. Using the usual order of product of permutations, the one on the right is first to be applied. Thus, we see that 0 gets sent to 1, and subsequently fixed by all later transpositions. So the product sends 0 to 1. Similarly, 1 gets sent to 0 and then to 2, and then unchanged. So it is easy to see that all non-negative integers are moved finitely many times and n is ultimately sent to n+1 as desired. Now, the right-hand factor fixes all negative integers, which then pass to the left factor, and it is easy to see that again only finitely many transpositions are involved. For example, -3 gets sent to 0, and then to -2, as desired. Thus, -n is mapped ultimately to -n+1, as desired. So altogether, this product is operating correctly.

  An isomorphic version of this idea can be used to represent the action of any infinite orbit, and so every permutation is a suitable well-defined product of transpositions, as desired.

The first thing to notice is that infinite permutations may have infinite support, that is, they may move infinitely many elements. Therefore, we cannot expect to express them as finite compositions of permutations having only finite support.

But if we allow (well-defined) infinite compositions, then the answer is that every permutation can be expressed as a composition of disjoint cycles and also expressed as a composition of transpositions. So the answer to question 1 is yes, and the answer to question 2 is no.

To see this, suppose that f is a permutation of ω. First, we may divide f into its disjoint orbits, where the orbit of n is defined as all the numbers of the form f^k(n) for any integer k. The action of f on each of these orbits commute with each other, because the orbits are disjoint. And the action of f on each such orbit is a cycle (possibly infinite). So f can be represented as a product of disjoint cycles. For the transposition representation, it suffices to represent each such orbit as a suitable product of transpositions. The finite orbits are just finite cycles, which can be expressed as a product of transpositions in the usual way. An infinite orbit looks exactly like a copy of the integers, with the shift map. This can be represented in cycle notation as (... -2 -1 0 1 2 ...). This permutation is equal to the following product of transpositions:

• (... -2   -1 0 1 2 ...) = [(0   -1)(0   -2)(0   -3)...][...(0 3)(0 2)(0 1)]

I claim that every natural number is moved by at most two of these transpositions, and that the resulting product is well-defined. On the right hand side of the equality, I have two infinite products of transpositions. Using the usual order of product of permutations, the right-most factor is first to be applied. Thus, we see that 0 gets sent to 1, and subsequently fixed by all later transpositions. So the product sends 0 to 1. Similarly, 1 gets sent to 0 and then to 2, and then unchanged. Similarly, it is easy to see that every non-negative integer n is sent to 0 and then to n+1 as desired. Now, the right-hand factor fixes all negative integers, which then pass to the left factor, and it is easy to see that again -n is sent to 0 and then to -n+1, as desired. So altogether, this product is operating correctly. An isomorphic version of this idea can be used to represent the action of any infinite orbit, and so every permutation is a suitable well-defined product of transpositions, as desired.

Thus, the answers to the questions in (1) are yes, and the answer to question (2) is no.

The first thing to notice is that infinite permutations may have infinite support, that is, they may move infinitely many elements. Therefore, we cannot expect to express them as finite compositions of permutations having only finite support.

But if we allow (well-defined) infinite compositions, then the answer is that every permutation is a composition of transpositions. To see this, suppose that f is a permutation of ω. First, we may divide f into its disjoint orbits, where the orbit of n is defined as all the numbers of the form f^k(n) for any integer k. The action of f on each of these orbits commute with each other, because the orbits are disjoint. The finite orbits are just finite cycles, which can be expressed as a product of transpositions in the usual way. An infinite orbit looks like a copy of the integers, since it will be infinite in both directions. All such cycles are isomorphic to the shift map on the integers, which can be represented in cycle notation as (... -2 -1 0 1 2 ...). This permutation is equal to the following product of transpositions: [(0 1)(0 2)(0 3)....][...(-3 0)(-2 0)(-1 0)]. First, let me explain what this product means. The first factor operates on the non-negative integers, and sends 0 to 1, 1 to 0 to 2, 2 to 0 to 3, etc., so it behaves properly on the non-negative integers, and the second factor fixes all positive integers. So the composition is well-defined with the right answer for non-negative naturals. Secondly, the first factor fixes all negative integers, and then the second factor sends them in finitely many moves to the right place. e.g. -3 goes to 0 and then to -2, etc. So altogether, the product is operating correctly. This same idea can be used to represent any infinite orbit, and so any permutation is a suitable well-defined product of transpositions, as desired.

Note: I just realized that I am using backwards composition notation! I'll fix this in an edit.

The first thing to notice is that infinite permutations may have infinite support, that is, they may move infinitely many elements. Therefore, we cannot expect to express them as finite compositions of permutations having only finite support.

But if we allow (well-defined) infinite compositions, then the answer is that every permutation is a composition of transpositions. To see this, suppose that f is a permutation of ω. First, we may divide f into its disjoint orbits, where the orbit of n is defined as all the numbers of the form f^k(n) for any integer k. The action of f on each of these orbits commute with each other, because the orbits are disjoint. The finite orbits are just finite cycles, which can be expressed as a product of transpositions in the usual way. An infinite orbit looks like a copy of the integers, since it will be infinite in both directions. All such cycles are isomorphic to the shift map on the integers, which can be represented in cycle notation as (... -2 -1 0 1 2 ...). This permutation is equal to the following product of transpositions

• (... -2 -1 0 1 2 ...) = [(0 -1)(0 -2)(0 -3)...][...(0 3)(0 2)(0 1)]

Let me explain what this means. On the right hand side, I have two infinite products of transpositions. Using the usual order of product of permutations, the one on the right is first to be applied. Thus, we see that 0 gets sent to 1, and subsequently fixed by all later transpositions. So the product sends 0 to 1. Similarly, 1 gets sent to 0 and then to 2, and then unchanged. So it is easy to see that all non-negative integers are moved finitely many times and n is ultimately sent to n+1 as desired. Now, the right-hand factor fixes all negative integers, which then pass to the left factor, and it is easy to see that again only finitely many transpositions are involved. For example, -3 gets sent to 0, and then to -2, as desired. Thus, -n is mapped ultimately to -n+1, as desired. So altogether, this product is operating correctly.

An isomorphic version of this idea can be used to represent the action of any infinite orbit, and so every permutation is a suitable well-defined product of transpositions, as desired.