4
$\begingroup$

This is an extremely simple fact, but I want to make sure that the assertions I am making are valid. In particular, I assert several times that a function is a permutation if and only if it is a bijection from a finite set to itself. If this is fine, I believe my arguments below are likely fine. I cannot think of a good counterexample to this.

There are four requirements we need to verify: closed under product operations, associative, has an identity, and closed under inverses.

Closed under product operation: An element of $S_n$ is a permutation of the elements $1, 2, \ldots, n$. This is a bijection $\alpha: \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\}$. A composition of these bijections, $\alpha$ and $\beta$, is another bijection from $\{1, 2, \ldots, n\}$ to $\{1, 2, \ldots, n\}$, and hnce $\alpha \beta$ is another permutation of the elements $\{1, 2, \ldots, n\}$.

Associativity. An element of $S_n$ is a permutation, i.e., a function from a set to itself, and function composition can easily be shown to be associative. For simplicity, take $f, g, h$ to be well-defined functions that map $A$ to $A$. For any $a \in A$, we have: $$((f \circ g) \circ h)(a) = (f \circ g)(h(a)) = f(g(h(a))$$ $$(f \circ (g \circ h))(a) = f((g \circ h)(a)) = f(g(h(a)).$$ Hence, composing permutations is associative because permutations are just functions.

Identity. The identity permutation, $\text{id}$, sends every element to itself. For any $\alpha \in S_n$ and any $x \in \{1, 2, 3, \ldots,n\}$, we have: \begin{align*} (\alpha \circ \text{id})(x) = \alpha(\text{id}(x)) = \alpha(x) \\ (\text{id} \circ \alpha)(x) = \text{id}(\alpha(x)) = \alpha(x). \end{align*} Hence, the identity permutation is the identity element in the group.

Inverses. Let $\sigma \in S_n$. Then, $\sigma$ is a bijection from $\{1, 2, \ldots, n\}$ to $\{1, 2, \ldots, n\}$. A function is bijective if and only if it is invertible. Hence, another bijection, $\sigma^{-1}$, also exists. Since this is a bijection from a set of finite elements to itself, it is also a permutation of $\{1, 2, \ldots, n\}$, and hence lives in $S_n$.

$\endgroup$
2
  • 9
    $\begingroup$ Yes, it is fine. $\endgroup$ Mar 9 '20 at 23:33
  • 1
    $\begingroup$ "There are four requirements we need to verify". I believe the things went historically the other way around: after having realized that the set of bijections on a set does fulfill the four properties, where "Inverses" is actually the qualifying one (e.g. associativity holds for any map on a set), someone thought to define "group" an algebric structure patterned upon the "4 properties" of the bijections. $\endgroup$
    – user750041
    Mar 10 '20 at 11:24
1
$\begingroup$

Your proof is correct and rather well-written.

In particular, I assert several times that a function is a permutation if and only if it is a bijection from a finite set to itself. If this is fine, I believe my arguments below are likely fine. I cannot think of a good counterexample to this.

With regards to this problem, yes, it is true that a function is a permutation if and only if it is a bijection from a finite set to itself. This is true essentially by definition of the word "permutation". In other contexts, the definition of permutation might be extended to allow bijections from any arbitrary (finite or infinite) set to itself (e.g. $x\mapsto 1/x$ is a bijection from $(0,\infty)$ to itself, and so is a permutation of $(0,\infty)$), but of course this is not relevant here since we are only looking at finite sets $\{1,2,\dots,n\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.