Question

I've been trying to find a definition of an infinite permutation on-line without much success. Does there exist a canonical definition or are there various ways one might go about defining this?

The obvious candidate I guess would be a bijection p : {1,2,...} -> {1,2,...} between the natural numbers. One might also try to use the Robinson-Schensted correspondence between permutations of length n and pairs of standard Young tableaux of size n. Then one would need a definition of infinite Young tableaux.

Another correspondence that might be used is between permutations and permutation matrices.

Answer 1

There are two closely related definitions which satisfy the properties you want.

First, consider group $\Sigma_k$ the bijections $\pi: \Bbb Z \to \Bbb Z$ such that $\pi(x+k) = \pi(x)+k$ for all $x$. Note that $S_k$ is a subgroup in $\Sigma_k$ - simply take any permutation of ${1,\ldots,k}$ and extend it periodically to all $x$. This group (introduced by Lusztig) is finitely generated and is closely related to affine Lie algebra $\widehat A_k$. The RSK does not exactly work here, but Lusztig does study the shape of Young diagrams (of what would be resulting two tableaux). The shape is a partition of $k$, and can be described using decreasing subsequences, extending Curtis Green's theorem (I forgot if this is in Lusztig's paper or my own easy observation).

Second, a somewhat related definition is the group $\Phi_k$ of bijections $\pi: \Bbb N \to \Bbb N$ such that $\pi(x+k) = \pi(x)+k$ for all $x$ large enough. I studied this definition in this paper. This group $\Phi_k$ is also finitely generated. It is very suitable for RSK, which is not always, but sometimes invertible. The asymptotic shape I defined is essentially the same as Lusztig's. Neither I nor anyone else studied the infinite matrix extension. The infinite permutation version is already difficult enough.

Answer 2

The bijection definition is fine, although it's not a very nice group. One might also consider the group generated by all transpositions on {1, 2, ...}, which is the subgroup of all bijections that fix all but finitely many elements, and this group is likely to be much nicer; it's countable, for one thing.

Edit: I guess it's worth noting that as far as I can tell the term infinite symmetric group is used by mathematicians to refer to the subgroup I described.

Answer 3

A permutation on a set A (which need not be countable) is just a bijective map A -> A.

Answer 4

Fon-Der-Flaass and Frid have recently introduced and studied infinite permutations as linear orderings of countable sets with respect to a given "natural" linear ordering. That is, given a countable set X (usually ℕ or ℤ), an infinite permutation π of X is a linear ordering ≤_π of X that may differ from the "natural" linear ordering of X. If we take X to be finite, then this definition coincides with usual definition of a finite permutation as a bijective map from X to itself.