# Why does a bijection from a set to itself deserve the name "Permutation"?

Sorry for the long text; this is a nebulous question that has always been in the back of my mind, and I've had trouble putting into a short form.

"Natural" Definition

If someone on the street hears the word "permutation," I think they will naturally assume that a permutation:

• Involves rearranging objects
• The order in which the objects are written, before and after the permutation is performed, is of crucial importantce (it's really the essence of the permutation)

I would naturally expect a permutation to be an instruction, or an action. For example, I would expect a permutation to look something like

$$\sigma = \text{interchange the first two entries.}$$

Then, if we apply $$\sigma$$ to $$(A, B, C)$$ we get $$(B, C, A);$$ if we apply it to $$(4, 6, 9)$$ we get $$(6, 4, 9).$$ To me this is a very satisfying (informal) definition of a permutation, because it captures exactly what many people (or at least me) would think a permutation "should be."

Another way to define "permutation" (to me, less satisfactory than the previous, but still more satisfactory than the official definition) could be to just say that "the 3-tuple $$(B, A, C)$$ is a permutation of $$(A, B, C).$$" (In fact, I think this is the definition used in elementary Statistics books.)

Percieved Weaknesses of the Official Definition

• It makes little sense to "permute" your set of objects. If you have a set of objects $$\{4, 6, 8 \},$$ and while you are not in the room someone applies a permutation to your set, you will never know; the output of your permutation is still $$\{4, 6, 8 \}.$$ Even if they only apply the permutation to a subset, you only might be able to tell.
• Permutations seem to have nothing to do with the order that your objects are in, either before or after doing the permutation. This, like I mentioned above, seems to violate the whole point of a permutation

I call these weaknesses because they seem to violate the "person on the street" understanding of a permutation, and I know that generally mathematicians try really hard to not distort the meaning of common English words too much.

My Question

Is there really such a big disconnect between the "Natural" and Official definitions of permutations? Even if there is not, and there is a way to tediously link the natural definition with the official definition (which I'm sure there is), why does the Official definition deserve to be called a permutation more than the natural one? Is there a name for the Natural definition?

Thanks.

• Well no, it doesn't make sense to talk about the order of the elements of a set, unless perhaps it's an ordered set ... Commented Aug 20, 2019 at 22:58
• @saulspatz That's exactly my point. Before hearing the official definition of "permutation," one would expect that "permutation" has something to do with the order in which the objects are. However, in the official definition, the order is completely irrelevant.
– Ovi
Commented Aug 20, 2019 at 23:00
• Why would you want two different names for things which are so obviously related? Commented Aug 20, 2019 at 23:01
• @saulspatz Sorry it's not very obvious to me how they're related. I think one way to relate them is to always talk about permutations from $\{ 1, 2, 3, ..., n \},$ and write the sentence "this the numbers actually represent the positions of the objects." But I have never seen this done.
– Ovi
Commented Aug 20, 2019 at 23:06
• Well, it's true that the set of self-bijections and the set of linear orderings on a given finite set $X$, although they have the same size, are NOT naturally isomorphic unless $X$ has a special linear ordering (or some equivalent additional structure) on it. For example, which ordering corresponds to the identity map? Or look at the equivalence classes under relabeling -- all linear orderings are the same vs. conjugacy classes in the symmetric group. As to the usage of the same name for both things, that happens all the time since language evolves.
– Ned
Commented Aug 20, 2019 at 23:58

"Rearranging" objects is a procedure that is not inherently related with order. The relation with order is more due to how we usually list things than the essence of permutation itself.

For instance, I have three pockets in my pants, on which I put my cell phone, keys and wallet, one on each pocket. I sometimes rearrange them; driving with the wallet on the right pocket of some pants is somewhat unpleasant. I think it is natural to call this process of changing from one alocation to another a permutation, and I think people would generally agree. This is precisely a function $$f: Pockets \to Pockets$$ which tells me that whatever was in pocket $$x$$ is now in pocket $$f(x)$$. Note that I never made any ordering of the pockets.

As I mentioned in the introduction, I think you are assuming that an ordering must be given due to the same reason why I said "cell phone, keys and wallet": because this is how we are used to communicate things, by listing them.

• Thanks, this is a great example; I have to think about it for some minutes.
– Ovi
Commented Aug 20, 2019 at 23:52
• @Ovi Another example that may be useful is thinking about people changing places in a round table. Establishing a "beginning of the table" is irrelevant; the exchange of places is a permutation nonetheless. Commented Aug 21, 2019 at 0:23
• That's why you normally have some space around the area of the handbrake, dashboard, or gear stick to place some small things that were previously in your pocket. Either that, or get a bag. Commented Aug 21, 2019 at 7:36

"A bijective map from a set to itself" does not require the set to be ordered, but when applied to an ordered set, this map acts to reorder the set.

This definition is therefore a generalization of the idea of "reordering an ordered set" to a more general setting.

Often, in mathematics, a name lifts with a generalization.

• Thanks, that's a nice way of looking at it. I just wish that had been mentioned by someone somewhere. In all my searches I never found someone talking about the relationship between permutations on an ordered set and permutations on an arbritrary set. I always assumed they must be "the same" somehow, but I couldn't see how they could be the same.
– Ovi
Commented Aug 21, 2019 at 0:12
• Another example is continuity. Originally, this was defined using limits on a metric space: $\lim\limits_{x\to a}|f(x)-f(a)|=0$. This was generalized to an arbitrary topological space by saying $U$ is open implies $f^{-1}(U)$ is open. This generalization is also called continuity.
– robjohn
Commented Aug 21, 2019 at 3:53