Abstract Algebra: Proof Verification Permutations on a Finite Set

131 Views Asked by At

Let $A$ be a finite set and $B$ be a subset of $A$. Let $G$ be the subset of $S_A$ consisting of all permutations $f$ of $A$ such that $f(x)∈B$ for every $x∈B$. Prove that $G$ is a subgroup of $S_A$.

My attempt-

Let $f,g∈G$.

Then for all $x∈B$, $f(x)∈B$ and $g(x)∈B$.

This implies that $f(g(x))∈B$. Thus, $G$ is closed.

Let $f∈G$

Let the elements of $B$ be $x_1,x_2,.....x_n$. Any distinct element $x_i$ of $B$ can be written as a distinct $f(x_j)$ where $x_j∈B$.

$f^{-1}(f(x_j))$ = $x_j$ by the definition of the inverse function.

We can write $f(x_j)$ as $x_i$ for some $x_i∈B$.

$f^{-1}(x_i))$ = $x_j$

Through this, we conclude that $G$ is a subgroup of $S_A$

2

There are 2 best solutions below

5
On BEST ANSWER

Your proof seems fine, but it'd be better if you explained why for all $x_i$, there exists $x_j\in B$ so that $f(x_j)=x_i$. Why does $x_j$ have to live in $B$? It's true, but why? All you know at the outset is that there exists $x_j\in A$ with that property since $f\in S_A$, so $f$ is surjective.

Here's (maybe) a simpler way to go. Use the subgroup test.

Clearly $1_{S_A}\in G$, so $G\neq \varnothing$. Let $f,g\in G$ and $x_i\in B$. The set $\{g(x_j)\}_{j=1}^n$ is a collection of $|B|=n$ distinct elements of $B$ since $x_j\neq x_k\implies g(x_j)\neq g(x_k)$ since $g$ is injective. Hence there exists $x_j\in B$ so that $g(x_j) = x_i$. So $g^{-1}(x_i) = x_j\in B$, and hence $f(g^{-1}(x_i))\in B$. So $fg^{-1}\in G$ and therefore by the subgroup test, $G$ is a group.

0
On

Your proof is correct. Here's a different proof of the fact that $f\in G\implies f^{-1}\in G$. Take $f\in G$ and suppose that $f^{-1}\notin G$. Then there's a $b\in B$ such that $f^{-1}(b)\notin B$. If you restrict $f$ to $\{f^{-1}(b)\}\cup B$, then you have an injective function from a set with $\#B+1$ elements into a set with $\#B$ elements, which is impossible.