Subsets of permutation group: Properties

In summary, the subgroup $G_x$ is a subgroup of $G$. The set $\{G_{x\rightarrow y}\mid y\in B\}\subseteq 2^G$ is a partition of $G$. Let $g\in G_{x\rightarrow y}$ and let $u\in G_x$ and $v\in G_{x\rightarrow y}$. Then it holds that $g\circ u\in G_{x\rightarrow y}$ and $g^{-1}\circ v\in G_x$. The maps \begin{align*}\alpha:G_x\rightarrow G_{x\rightarrow y
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! 😊

Let $G$ be a permutation group of a set $X\neq \emptyset$ and let $x,y\in X$. We define:
\begin{align*}&G_x:=\{g\in G\mid g(x)=x\} \\ &G_{x\rightarrow y}:=\{g\in G\mid g(x)=y\} \\ &B:=\{y\in X\mid \exists g\in G: g(x)=y\}\end{align*}

Show the following:
  1. $G_x$ is a subgroup of $G$.
  2. The set $\{G_{x\rightarrow y}\mid y\in B\}\subseteq 2^G$ is a partition of $G$.
  3. Let $g\in G_{x\rightarrow y}$ and let $u\in G_x$ and $v\in G_{x\rightarrow y}$. Then it holds that $g\circ u\in G_{x\rightarrow y}$ and $g^{-1}\circ v\in G_x$.
  4. The maps \begin{align*}\alpha:G_x\rightarrow G_{x\rightarrow y}, \ u\mapsto g\circ u \\ \beta: G_{x\rightarrow y}\rightarrow G_x, \ v\mapsto g^{-1}\circ v\end{align*} are to each other inverse bijections.
  5. Let $G$ be finite. Then it holds that $|G|=|B|\cdot |G_x|$.
I have done the following:

For 1:
We have to show the properties of a subgroup. :unsure:For 2:
We have to show that every element of $G$ is in exactly one of these subsets, right? How can we do that? :unsure:For 3:
Since $g\in G_{x\rightarrow y}$ we have that $g\in G\mid g(x)=y$.
Since $u\in G_x$ we have that $u\in G\mid u(x)=x$.
Since $v\in G_{x\rightarrow y}$ we have that $v\in G\mid v(x)=y$.

Isn't obvious that $g\circ u\in G_{x\rightarrow y}$ and $g^{-1}\circ v\in G_x$, since we look always at the outer left function? :unsure:For 5:
The is a hint given that the proof is similar to the idea to show that theere are $48$ symmetries of a cube.
How exactly can we use this? :unsure:
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
mathmari said:
For 1:
We have to show the properties of a subgroup.
Hey mathmari!

So we have to show that it is not empty, closed for composition, and closed for inverses, don't we? 🤔
mathmari said:
For 2:
We have to show that every element of G is in exactly one of these subsets, right? How can we do that?
A usual way is with a proof by contradiction.
Suppose it is not. Then there must be... 🤔
 
Last edited:
  • #3
For 1:

$G$ is the permutation group. The identity permutation is contained in $G$. We have that $\text{id}(x)=x$. So $\text{id}\in G_x$. Therefore, $G_x$ is not empty.
Let $g,h\in G_x$. Then $g(x)=x$ and $h(x)=x$ for $x\in X$. We have that $(g\circ h)(x)=g(h(x))=g(x)=x$. So $g\circ h\in G_x$ and this means that $G_x$ is closed for composition.
Let $g\in G_x$. Then $g(x)=x$. How do we show that $G_x$ is closed for inverses? :unsure: For 2:

We suppose that the set is not a partition of $G$. Then there must be anelement of $G$ that is contained it two different subsets or in no subset? :unsure:
 
  • #4
mathmari said:
For 1:
$G$ is the permutation group. The identity permutation is contained in $G$. We have that $\text{id}(x)=x$. So $\text{id}\in G_x$. Therefore, $G_x$ is not empty.
Let $g,h\in G_x$. Then $g(x)=x$ and $h(x)=x$ for $x\in X$. We have that $(g\circ h)(x)=g(h(x))=g(x)=x$. So $g\circ h\in G_x$ and this means that $G_x$ is closed for composition.
Let $g\in G_x$. Then $g(x)=x$. How do we show that $G_x$ is closed for inverses?

Since $g$ is an element of the group $G$, it must have an inverse $g^{-1}$ that is also in $G$, yes?
So we already have that $g^{-1}$ exists.
The only remaining question is whether it is in $G_x$.
Do we have that $g^{-1}(x)=x$? :unsure:

mathmari said:
For 2:
We suppose that the set is not a partition of $G$. Then there must be an element of $G$ that is contained it two different subsets or in no subset?

Indeed.
So for the first case, let's suppose that there is a $g$ is in 2 different subsets.
Then there must be a $G^1_{x\to y}\ne G^2_{x\to y}$ such that $g$ is in both yes?
What does that mean? 🤔
 
  • #5
Klaas van Aarsen said:
Since $g$ is an element of the group $G$, it must have an inverse $g^{-1}$ that is also in $G$, yes?
So we already have that $g^{-1}$ exists.
The only remaining question is whether it is in $G_x$.
Do we have that $g^{-1}(x)=x$? :unsure:

Ah yes! So since $g(x)=x\Rightarrow g^{-1}(g(x))=g^{-1}(x) \Rightarrow x=g^{-1}(x)$ and so $g^{-1}\in G_x$, right? :unsure:
Klaas van Aarsen said:
Indeed.
So for the first case, let's suppose that there is a $g$ is in 2 different subsets.
Then there must be a $G^1_{x\to y}\ne G^2_{x\to y}$ such that $g$ is in both yes?
What does that mean? 🤔

Then the sets $G^1_{x\to y}$ and $ G^2_{x\to y}$ have a non-empty intersection. Or do you mean something else? :unsure:
 
  • #6
mathmari said:
Ah yes! So since $g(x)=x\Rightarrow g^{-1}(g(x))=g^{-1}(x) \Rightarrow x=g^{-1}(x)$ and so $g^{-1}\in G_x$, right?

Yep. 😁

mathmari said:
Then the sets $G^1_{x\to y}$ and $ G^2_{x\to y}$ have a non-empty intersection. Or do you mean something else?
Let's revisit what $G_{x\to y}$ is.
If $g$ is in $G_{x\to y}$, it must map $x$ to $y$.
And if $g$ is not in $G_{x\to y}$, it must mean that $g(x)\ne y$, mustn't it?
In other words, it's not possible for there to be 2 different sets $G_{x\to y}$, is it? 🤔
 
  • #7
Klaas van Aarsen said:
Let's revisit what $G_{x\to y}$ is.
If $g$ is in $G_{x\to y}$, it must map $x$ to $y$.
And if $g$ is not in $G_{x\to y}$, it must mean that $g(x)\ne y$, mustn't it?
In other words, it's not possible for there to be 2 different sets $G_{x\to y}$, is it? 🤔

Ok!

So it remains to show that there is an element of $G$ that is in none of the susbsets, or not? :unsure:
 
  • #8
mathmari said:
So it remains to show that there is an element of $G$ that is in none of the susbsets, or not?

Yep. :)
 
  • #9
This cannot hold, can it? Because every element of $G$ send an element of $X$ to an an element of $X$ so it must be contained in one of the subsets. Is this correct? :unsure:
 
  • #10
mathmari said:
This cannot hold, can it? Because every element of $G$ send an element of $X$ to an an element of $X$ so it must be contained in one of the subsets. Is this correct?
Close, but it's not complete. 🚷

Let's take this one step at a time.
Suppose there is a $g\in G$ such that it is in none of the sets in $\{G_{x\rightarrow y}\mid y\in B\}\subseteq 2^G$.
Let $x$ be an element in $X$.
Then $g(x)$ must indeed also be an element in $X$.
But that is not sufficient is it? There is more... 🤔
 
  • #11
Wait! 🤫
I think I made a mistake. 😊
I wrote:

Klaas van Aarsen said:
Let's revisit what $G_{x\to y}$ is.
If $g$ is in $G_{x\to y}$, it must map $x$ to $y$.
And if $g$ is not in $G_{x\to y}$, it must mean that $g(x)\ne y$, mustn't it?
In other words, it's not possible for there to be 2 different sets $G_{x\to y}$, is it?

However, suppose $g\in G$ and there are two different sets in $\{G_{x\rightarrow y}\mid y\in B\}$ that contain $g$.
Then there must be $x_1,x_2,y_1,y_2\in X$ such that $g\in G_{x_1\to y_1}$, $g\in G_{x_2\to y_2}$, and $G_{x_1\to y_1}\ne G_{x_2\to y_2}$, yes?

Let's take a look at an example.
Suppose $X=\{a,b,c\}$, and let $f\in G$ with $f:a\mapsto a, b\mapsto c, c\mapsto b$.
Then $\operatorname{id}, f\in G_{a\to a}$.
And $\operatorname{id}\not\in G_{b\to c}$, but $f \in G_{b\to c}$.
So $f$ is contained in two distinct sets that are both in $\{G_{x\rightarrow y}\mid y\in B\}$, isn't it? :unsure:

I am stuck now because this would proof by counterexample that statement 2 is false. :eek:
Do you see in mistake in my reasoning? 🤔
 
  • #12
Since the definition of the set is $\{G_{x\rightarrow y}\mid y\in B\}$ do we maybe have to take only different $y$'s but same $x$'s ?
I mean one subset is $G_{x\rightarrow y_1}$ and an other one is $G_{x\rightarrow y_2}$ with $y_1\neq y_2$ and both are in $B$ ?
Or is there no logic at this? :unsure:
 
  • #13
mathmari said:
Since the definition of the set is $\{G_{x\rightarrow y}\mid y\in B\}$ do we maybe have to take only different $y$'s but same $x$'s ?
I mean one subset is $G_{x\rightarrow y_1}$ and an other one is $G_{x\rightarrow y_2}$ with $y_1\neq y_2$ and both are in $B$ ?
Or is there no logic at this?
Yes. That makes sense and would explain it. :cool:
 
  • #14
We consider a $x\in X$.

We suppose that $g\in G_{x\rightarrow y_1}$ and $g\in G_{x\rightarrow y_2}$ with $y_1\neq y_2$ for $y_1, y_2\in B$.
Then we have that $g(x)=y_1$ and $g(x)=y_2$. Then $g$ is not injective and this is not true since $g$ is a permutation.
So we get a contradiction and so $g$ must be in at most one subset.
Is this correct?

Then we suppose that $g$ is not contained in one subset. That means that there is a $y$ such that $g\notin G_{x\rightarrow y}$ and so $g(x)\neq y$ and since $y$ is any element in $X$ then we get a contradiction since $g$ has to map $x$ to some $y$.
Therefore $g$ must be in exactly one subset.
Is this correct?

:unsure:
 
  • #15
Yep. All correct. :)
 
  • #16
Great! ☺

So let's consider question 3. Is it correct what I had done in my initial post? :unsure:

Could you give me a hint for the question 4 ? :unsure:

At 5:
We have that $\{G_{x\rightarrow y}\mid y\in B\}\subseteq 2^G$ is a partition of $G$. Does this mean that $|G|=|\{G_{x\rightarrow y}\mid y\in B\}|$ ?
If it is like that, then we have to show that $|\{G_{x\rightarrow y}\mid y\in B\}|=|B|\cdot |G_x|$, right? :unsure:
 
Last edited by a moderator:
  • #17
mathmari said:
So let's consider question 3. Is it correct what I had done in my initial post?

Yes.
Still, I would state explicitly that the conditions are met.
For instance $(g\circ u)(x)=g(u(x))=g(x)=y\implies g\circ u\in G_{x\to y}$. :geek:

mathmari said:
Could you give me a hint for the question 4 ?

Let $f$ be an element of $G$.
What is $\alpha(\beta(f))$ and what does it mean? 🤔

mathmari said:
At 5:
We have that $\{G_{x\rightarrow y}\mid y\in B\}\subseteq 2^G$ is a partition of $G$. Does this mean that $|G|=|\{G_{x\rightarrow y}\mid y\in B\}|$ ?
If it is like that, then we have to show that $|\{G_{x\rightarrow y}\mid y\in B\}|=|B|\cdot |G_x|$, right?
What does the Orbit-stabilizer theorem say? 🤔
 
  • #18
Klaas van Aarsen said:
Yes.
Still, I would state explicitly that the conditions are met.
For instance $(g\circ u)(x)=g(u(x))=g(x)=y\implies g\circ u\in G_{x\to y}$. :geek:

Ah ok! And respectively: $(g^{-1}\circ v)(x)=g^{-1}(v(x))=g^{-1}( y )$. This the last one equal to $x$ because $g\in G_{x\rightarrow y}$ and so $g(x)=y$ and so $x=g^{-1}( y )$ ? :unsure:
Klaas van Aarsen said:
Let $f$ be an element of $G$.
What is $\alpha(\beta(f))$ and what does it mean? 🤔

We have that $$\alpha(\beta(f))=\alpha (g^{-1}\circ f)=g\circ g^{-1}\circ f=f$$ This means that $\alpha$ is the left inverse of $\beta$.
We have that $$\beta(\alpha(f))=\beta (g\circ f)=g^{-1}\circ g\circ f=f$$ This means that $\beta$ is the right inverse of $\alpha$.
So $\alpha=\beta^{-1}$ and $\beta=\alpha^{-1}$ and since these maps are invertible it follows that they are bijections.

Does this mean that these two are to each other inverse bijections? :unsure:
 
  • #19
mathmari said:
Ah ok! And respectively: $(g^{-1}\circ v)(x)=g^{-1}(v(x))=g^{-1}( y )$. This the last one equal to $x$ because $g\in G_{x\rightarrow y}$ and so $g(x)=y$ and so $x=g^{-1}( y )$ ?

Yep.
So $(g^{-1}\circ v)(x)=x \implies (g^{-1}\circ v)\in G_x$. :geek:
mathmari said:
Does this mean that these two are to each other inverse bijections?
Yep. 😏
 

1. What is a permutation group?

A permutation group is a mathematical concept that represents a set of objects and the ways in which those objects can be rearranged or permuted. It is a fundamental concept in abstract algebra and has applications in various fields such as group theory, combinatorics, and cryptography.

2. What is a subset of a permutation group?

A subset of a permutation group is a smaller group that is formed by selecting a specific number of elements from the original group. This subset will still exhibit the same properties and structure as the original group, but with fewer elements.

3. What are the properties of a subset of a permutation group?

A subset of a permutation group will have the same properties as the original group, such as closure, associativity, identity element, and inverse elements. However, the subset may not have the same number of elements or exhibit the same symmetry as the original group.

4. How are subsets of permutation groups useful?

Subsets of permutation groups are useful in various mathematical and practical applications. They can help in simplifying complex problems, provide insight into the structure of a larger group, and aid in the study of group theory and abstract algebra.

5. Can a subset of a permutation group itself be a permutation group?

Yes, a subset of a permutation group can itself be a permutation group. This subset will exhibit the same properties as the original group, but with a smaller number of elements. However, not all subsets of a permutation group will be permutation groups, as they must still satisfy the group axioms.

Similar threads

  • Linear and Abstract Algebra
Replies
1
Views
730
  • Linear and Abstract Algebra
Replies
19
Views
1K
  • Linear and Abstract Algebra
Replies
7
Views
1K
Replies
2
Views
940
  • Linear and Abstract Algebra
Replies
7
Views
968
  • Linear and Abstract Algebra
Replies
7
Views
1K
  • Linear and Abstract Algebra
Replies
16
Views
1K
  • Linear and Abstract Algebra
Replies
9
Views
851
  • Linear and Abstract Algebra
2
Replies
52
Views
2K
  • Linear and Abstract Algebra
Replies
9
Views
942
Back
Top