# Proof that composition of two permutations is again a permutation.

Permutations are symmetries of a (not necessarily finite) set $$X$$, often denoted as Sym(T). That is, a permutation $$p: X\to X$$ is a bijective map from a set $$X$$ to itself.

I wish to prove the following and wish to check my approach:

The composition of two permutations is again a permutation.

Approach:

Proof 1

Given two permutations $$p_1$$ and $$p_2$$ we know that these are bijective, therefore by definition of a bijection: $$\forall y \in X \quad \exists ! x\in X: p(x)=y$$

In English: Every element in the codomain, corresponds to a unique element in the domain. It thus uniquely pairs elements in the codomain to elements in the domain.

We now consider the composition of these two permutations and show it is bijection from $$X$$ to itself. To prove bijectivity one can prove that there exists one unique element in the domain, for every element in the codomain.

Consider an arbitrary $$z\in X$$, we then know since $$p_1$$ is permutation (bijection), so there is some unique $$y$$, such that $$p_1(y)=z$$ Now since $$y\in X$$, by there must exist a unique element $$x$$, such that we can write: $$p_2 (x)=y$$ We conclude that: $$p_1(p_2(x))=p_1(y)=z$$ Since for every element $$z$$ in the codomain $$X$$, there exists a unique element $$x$$ in the domain, we have a bijective map. This means that the composition $$p_1 \circ p_2$$ is again a permutation on $$X$$. $$\square$$

Proof 2:

Canonical approach: Let $$f$$ and $$g$$ be bijective maps from a set $$X$$ to itself. We will prove that the composition $$f \circ g$$ is bijective.

Injectivity: (each element that is reached is reached once)

Consider arbitrary $$a, b \in X$$ such that: $$f(g(a))=f(g(b))$$ by injectivity of $$f$$ we know that $$g(a)=g(b)$$. Now by injectivity of $$g$$ we have that $$a=b$$, hence the composition $$f \circ g$$ is injective.

surjectivity: (each element is reached) We have to prove that for every element $$b \in X$$, there exists some element $$a$$ sucht that $$f(g(a))=b$$. Indeed we have bijective maps so the inverse map is a well-defined bijective map for each of these maps $$f, g$$. Consider the element $$a=g^{-1}( f^{-1}(b))$$ and observe: $$f(g(a))=f(g(g^{-1}( f^{-1}(b))))=f(f^{-1}(b))=b$$ By the associativity property of maps (and the fact that composition of a map with its inverse yields the identity).

Injectivity and surjectivity both hold therefore the composition is bijective. (every element is reached exactly once)

Proof 3 Alternatively, by the pigeonhole principle we have that for finite sets of the same cardinality a map is surjective if and only if it is injective.

Consider arbitrary $$a, b \in X$$ such that: $$f(g(a))=f(g(b))$$ by injectivity of $$f$$ we know that $$g(a)=g(b)$$. Now by injectivity of $$g$$ we have that $$a=b$$, hence the composition $$f \circ g$$ is injective.

Now we also know the composition is surjective and therefore bijective.

• This is more a question to the community. Is a symmetry of a set a standard English wording to mention a bijection map from a set $X$ onto itself? – mathcounterexamples.net Feb 4 at 16:22
• I didn't say it was incorrect -- merely that in about 45 years of doing various kinds of mathematics, I hadn't encountered it. – John Hughes Feb 4 at 16:26
• Dick Gross is a wonderful guy, and was a terrific colleague when he was at Brown. I admire his use of this term. I revise my claim: I've heard the term used exactly once in 45 years of doing mathematics. – John Hughes Feb 4 at 16:46
• Being French, I'm not at the best place to comment English math words. I see at least one issue to use the word symmetry instead of a permutation of a set... in affine geometry, a rotation will also be named a symmetry. Something to become mad! – mathcounterexamples.net Feb 4 at 17:01
• "In English: For every element in the domain, there exists a unique element in the codomain." That is not a correct translation of the notion of bijection. – John Hughes Feb 4 at 19:08

This is a "I have a lovely proof but the margin is too large to fit it" type situation. If your proof is more than two lines and contains more than definitions, then it's too long and too complicated.

Claim: If $$f:X\to Y$$ and $$g:Y \to Z$$ are bijections then $$g\circ f: X \to Z$$ is a bijection (and if $$X = Y =Z$$ then $$f,g,g\circ f$$ are permutations).

Proof: As $$g$$ is a bijection, for any $$z \in Z$$ there is a unique $$y_z \in Y$$ so that $$g(y_z) = z$$; and as $$f$$ is a bijection, for that $$y_z$$ there is a unique $$x_{y_z}$$ so that $$f(x_{y_z}) = y_z$$, and therefore $$g\circ f(x_{y_z}) = z$$. And, if it's not immediately apparent, $$x_{y_z}$$ is uniquely such as no other $$x \in X$$ is such that $$f(x) = y_z$$ and no other $$y \in Y$$ is such that $$g(y) = z$$.

(The above proof is probably at least $$85\%$$ longer than it needs to be.)

• Notice that this proof is almost the exact opposite of the one given by OP (in Proof 1), who shows only that for every $x \in X$, then map $g\circ f$ produces exactly one element of $Z$ (i.e., that $g \circ f$ is a function). – John Hughes Feb 6 at 13:48

First, a bjection is an injective and surjective map. So it would be more clear (at least this is my perception) to prove that a composition of permutations is both injective and surjective.

Second, this is not specific to permutations of a set. This is a general fact: composition of two bijections is a bijection. So it would be interesting to use or proof this general fact.

The essence of the proof that you seem to be trying to formulate is this:

Theorem 1: If $$f: A \to A$$ is a surjective map of a finite set, then it's also injective, and vice-versa.

That's a true (and useful) statement, but it, too, requires proof.

But if we suppose that it's been proved somewhere, your proof of the claim about permutations would look like this:

Let $$f = p_1 \circ p_2$$. Then the image of $$f$$ is \begin{align} Im(f) &= \{ f(x) \mid x \in X \} \\ &= \{ p_1(p_2(x)) \mid x \in X \} & \text{by the definition of f} \\ &= \{ p_1(y) \mid y = p_2(x) \text{ and } x \in X \} & \text{substitution} \\ \end{align} But the set \begin{align} Z &= \{ p_2(x) \mid x \in X \} \end{align} is exactly the image of $$p_2$$; because $$p_2$$ is surjective, this is all of $$X$$. So we can continue \begin{align} Im(f) &= \{ p_1(y) \mid y = p_2(x) \text{ and } x \in X \} & \text{substitution} \\ &= \{ p_1(y) \mid y \in Im (p_2)\} & \text{definition of image} \\ &= \{ p_1(y) \mid y \in X\} & \text{because p_2 is surjective} \\ &= Im(p_1) & \text{definition of image} \\ &= X & \text{because p_1 is surjective} \\ \end{align}

So $$f$$, a map from the finite set $$X$$ to itself, is surjective. It's therefore (by Theorem 1) also injective, hence bijective.

Of course, you still need to prove Theorem 1 to make this a valid proof.

• Again a semantic question. In French a permutation is a bijection from a whatever set $X$ onto itself. Your answer seems to indicate that in English permutations only involve finite sets. Is that correct? – mathcounterexamples.net Feb 4 at 20:40
• Permutations are just rearrangements of a set of arbitrary size, not necessarily finite. But for finite sizes we have the pigeonhole principle that states that for $f: X \to Y$ and |X|=|Y|, we have that surjectivity implies injectivity, implies bijectivity. – Wesley Strik Feb 4 at 21:50
• Finite permutations are particularly interesting in group theory and combinatorics however – Wesley Strik Feb 4 at 21:51
• My answer was about the (now substantially edited) proof attempt in the original, which appeared to try to claim that injectivity of a map $X \to X$ followed by surjectivity (or at least that seemed to me to be what OP was getting at, although as my other answer showed, it wasn't really much of a proof of anything). Looking at the function $n \mapsto 2n$ on the integers, it clear that such a proof only works when $X$ is finite, or when you know something more about the map. – John Hughes Feb 4 at 22:09

It seems to me that you're proving something more general: a composition of bijections is a bijection. Let me work through your proof with you.

Consider an arbitrary $$x\in X$$,

It might be nice to start by telling the reader what you're proving. So you could write "To show that $$p_1 \circ p_2$$ is surjective, consider an arbitrary $$x \in X$$."

we then know that: $$(p_1\circ p_2)(x)=p_1(p_2(x))$$

This statement is true by the definition of composition. I think you can safely eliminate it. What you really want to say is "We'd like to show that there's an element $$z \in X$$ with $$p_1 \circ p_2(z) = p_1(p_2(z)) = x.$$"

Now since $$x\in X$$, by (**) there must exist a unique element $$y$$, such that we can write:

$$p_1(p_2(x))=p_1(y)$$

I don't know what the back-quote before the "(y)" means; I'll assume it was a typo. There's obviously an element with this property, namely $$y = p_2(x)$$. You claim that it's unique, but you don't say why; a good proof of a fact at this level would include a reason for a claim of uniqueness.

And again since $$y\in X$$, by (*) there must exist a unique element $$z$$, such that we can write: $$p_1(p_2(x))=p_1(y)=z$$

Sure there is -- the element $$z$$ is ... well... it's $$p_1(p_2(x))$$. Again, you've given no explanation of uniqueness.

Since for every element in the domain $$x$$, there exists a unique element in the entire codomain,

This statement, as written, is false -- there may be many elements in the codomain. You can say that for every element $$x$$ in the domain, there's a unique element $$z$$ in the codomain with $$z = p_1(p_2(x))$$, and that's true, but it's true no matter what the functions $$p_1$$ and $$p_2$$ are -- they could both be constant functions. So you haven't yet proved anything useful about permutations.

we have a bijective map.

And this statement is false, because the preceding conclusion is true even if $$p_1$$ and $$p_2$$ are constant maps.

This means that the composition $$p_1 \circ p_2$$ is again a permutation on $$X$$. $$\square$$

====

I'm not going to try to get you started on a proof of the more general claim:

Suppose $$f:A \to B$$ and $$g: B \to C$$ are bijections. Then $$h = g\circ f$$ is also a bijection.

Do you see how I've clearly stated what I aim to prove? That's always a good start. Now let's proceed.

To show this, we must show $$h$$ is both an injection and a surjection. To show $$h$$ is injective, we must show that if $$h(a_1) = h(a_2)$$, then $$a_1 = a_2$$.

I've copied down the definition of "injective" here, adapting it to the names used in my theorem. What we need to show is an if-then statement, so we assume the "if" part:

Suppose that $$h(a_1) = h(a_2)$$. Then $$g(f(a_1)) = g(f(a_2))$$, by the definition of $$h$$.

Notice that I explained why my second statement was true ("by the definition of $$h$$"). That's essential in a proof.

Now we'd like to show that $$a_1 = a_2$$, but we're not quite there yet. So far we have two items in $$b$$ (namely $$f(a_1)$$ and $$f(a_2)$$, and when we apply $$g$$ to each of them, we get the same result. What does this tell you about those two items? And why can you draw that conclusion?

From here, I'm going to let you proceed on your own for a bit, and see where you get.