Welcome to Math Overflow

Question

4

1

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.

flag	asked Oct 18 at 20:52 Henning Arnór Úlfarsson 352●1●8

Qiaochu Yuan · Accepted Answer · 2009-10-18 21:11:08Z UTC

10

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.

edited Oct 18 at 21:11

answered Oct 18 at 20:58

Qiaochu Yuan
9,855●12●77

3

It also still has a sign homomorphism to Z/2Z. – Reid Barton Oct 18 at 21:06

As well as a nice presentation, a good notion of cycle decomposition, and so forth. The set of all bijections from a countable set to itself, on the other hand, is terrible; one can imagine a bijection which, for example, encodes Chaitin's constant. – Qiaochu Yuan Oct 18 at 21:10

Thanks for your answer! – Henning Arnór Úlfarsson Oct 18 at 21:37

The full set of bijections on Z is quite a zoo, but it's still occasionally useful (e. g., for finding explicit constructions). Also, the concept of cycle decomposition is fine as long as you allow infinite cycles (which admittedly don't look very round). – Darsh Ranjan Oct 29 at 4:12

Well, here's a worse reason than uncountability then: it's uncountably generated, and I can't imagine that it has any kind of reasonable presentation. – Qiaochu Yuan Oct 29 at 4:45

show 2 more comments

Justin · Answer 2 · 2009-10-18 20:59:58Z UTC

0

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

answered Oct 18 at 20:59

Justin
509●2●12

Definition of infinite permutations

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.