Prove that the set of permutations of a finite non-empty set is a group with respect to the composition of functions.

1.3k Views Asked by At

So, the question is in the title but i'll just repeat it formally as follows:

Let $X$ be a non-empty, finite set. Then, $P(X)$ is the set of permutations of $X$. The pair $(P(x),\circ)$, where $\circ$ denotes the composition of functions, is a group.

Honestly, I think I have this down because this is literally just an exercise in verifying that the axioms of a group hold for this particular pair. However, I just want someone to see if the structure of my proof/my wording is okay or not.


Proof Attempt:

First, we prove closure. Let $f \in P(X)$ and $g \in P(X)$. They are invertible functions so we have to prove that $f \circ g$ is invertible as well. We just have to show that $f \circ g$ is bijective.

$(f \circ g)(x_1) = (f \circ g)(x_2) \implies f(g(x_1)) = f(g(x_2)) \implies g(x_1) = g(x_2) \implies x_1 = x_2$

That proves injectivity. To prove surjectivity, consider the following:

$(f \circ g)(X) = f(g(X)) = f(X) = X$

Hence, $f \circ g$ is bijective and, therefore, is invertible. So $f \circ g \in P(X)$.

Secondly, we prove associativity. Let $f,g,h \in P(X)$. Then:

$((f \circ g) \circ h)(x) = (f \circ g)(h(x)) = f(g(h(x))) = f((g \circ h)(x)) = (f \circ (g \circ h))(x)$

Which holds for all $x \in X$.

Thirdly, we need to show the existence of an identity element. Let $I: X \to X$ be our choice of an identity element. To show that it actually is an identity:

$(f \circ I)(x) = f(I(x)) = f(x) = I(f(x)) = (I \circ f)(x)$

Finally, we need to show the existence of inverse elements. Let $f \in P(X)$. Since f is invertible, $f^{-1}$ is invertible and belongs to P(X). This shows the existence of inverses.

Since the pair clearly satisfies all the axioms of a group, it is a group.

1

There are 1 best solutions below

10
On BEST ANSWER

This proof is entirely correct. In fact, your proof never used that $X$ is finite. Thus your proof also shows that the permutations of an infinite set $X$ form a group, which is correct! You did more than you had to prove!

For extra information, a common notation to denote the permutation on a set $X$ is $\operatorname{Sym}(X)= \{f: X \to X: f \mathrm{\ bijective \ map}\}$.

If $X= \{1, \dots, n\}$, we write $S_n$ instead.

If you haven't encountered this notation before, you will probably soon see it in a group theory course.