Let and let . Under the notation of the previous exercise, prove that . Show also that the map is an injective homomorphism .
(In particular, show that . It is at this point that the in the definition of are needed. The underlying reason for this that if is the tuple with 1 in position and 0 elsewhere, then acts on on the left by . If the tuple is represented by the formal sum , then this left group action on the extends to a left group action on the set of all formal sums by . Note that the coefficient of on the right hand side is , thus the right hand side may be rewritten as , which is precisely the formal sum representation of . In other words, any permutation of the “position vectors” (which fixes their coefficients) is the same as the inverse permutation on the coefficients (fixing the ). If one uses in place of in the definition of then the map is not necessarily a homomorphism – it corresponds to a right group action.)
First we show that this mapping is a homomorphism. Let .
We have . Thus , hence this mapping is a homomorphism.
Now suppose the are nontrivial and let be in the kernel of . Then for all , . Since the are nontrivial, we may choose such that any given pair of entries consists of distinct elements of . Thus for all , and in fact . Thus the kernel of is trivial, hence is injective.
Note that the nontrivial condition on is necessary because otherwise, and .
Let be a group and let be an abelian, normal subgroup of . Show that acts (on the left) by conjugation on by . (In particular, show that this action is well defined.) Give an explicit example to show that this action is not well defined if is nonabelian.
To see well definedness, suppose . That is, . Now ; note that since is normal, hence since is abelian. Thus , and the action is well defined.
Clearly we have and . So acts on .
Now identify in . Note that has index 2, hence is normal, and that is nonabelian. Moreover, and are distinct representatives of . However, and , so that the action described above is not well defined.
Suppose acts on on the left via . Denote the corresponding right action of on by ; that is, . Prove that the induced equivalence relations and , defined by if and only if for some and if and only if for some , are the same relation. (That is, prove that if and only if .)
If , then for some . Then , so that . Thus , and since is reflexive, .
If , then for some . Then , so that . Thus , and since is reflexive, .
Suppose acts transitively on and let be normal. Let be the distinct orbits of on .
 Prove that permutes the sets in the sense that for each and each there exists a such that . Prove that is transitive on . Deduce that all orbits of on have the same cardinality.
 Prove that if then and that . [Hint: Note that and use the Second Isomorphism Theorem.]
 Let and . Now is an arbitrary orbit of on . Moreover, for some . Then , since is normal. Thus permutes the orbits .
Now let be arbitrary; since the action of on is transitive, there exists such that . Then ; thus the action of on the orbits is transitive.
Let be arbitrary, and let such that . Because is normal, for every there exists a unique such that . We have a mapping given by . Because , this mapping is bijective, and . Because the action of is transitive on the orbits, all orbits have the same cardinality.
 Let . We can restrict the action of on the orbits of to ; with this action we have . Clearly ; thus . Considering now the (transitive) action of on the orbits of , we have .
We claim that . Proof of claim: Suppose . Now , so that in particular for some . Then , so that . Thus . Now suppose . Then for some and . Now , so that . Thus .
Let act transitively on the set . A block is a nonempty subset such that for all either or .
 Prove that if is a block containing and we define then .
 Prove that if is a block then is a partition of .
 A (transitive) group is called primitive if the only blocks in are the trivial ones the singletons and itself. Prove that is primitive on . Prove that is not primitive as a permutation group on the four vertices of a square.
 Let act transitively on . Prove that is primitive on if and only if for all , is maximal in .
 Note that is not empty since . Now let . Note that , so that . Thus . By the subgroup criterion, .
Now suppose . We have , so that . Hence is nonempty, and we have since is a block. Thus . By a previous exercise, .
 First we show that . The direction is clear. : Let and . Since the action of is transitive, there exists such that . Then , so that .
Now suppose . Then there exist such that . Now , so that is not empty. Thus , and we have . So elements of are pairwise disjoint; hence is a partition of .

 Let be a proper nonempty subset. Then there exist elements and . Suppose is a block. Consider ; since , we have . Let and be the remaining elements of . If , then , a contradiction; similarly for . Thus . Now clearly itself is a block, and any proper block must be a singleton. Thus this action of is primitive.
 We saw previously that , where are labels on the vertices of a square (written clockwise). Consider the set . We see that
So that is a nontrivial block; hence this action is not primitive.
 We begin with some lemmas.
Lemma 1: Let act transitively on and let be a block under the action. Then if and only if . Proof: The direction is clear. Suppose is a proper subset and let , . Now and , so that . Since is a block, we have . But since and , a contradiction. So is not proper, and we have .
Now we move to the main result.
Suppose is primitive on ; then the only blocks of are and the singletons. Now let and let be a subgroup with . We consider the set .
We claim that is a block. Proof of claim: is not empty since . Now let . If , then . If , then . Suppose that ; say that for some . Then , so that . But then , a contradiction. Thus if , then . Hence is a block.
Next we claim that . Proof of claim: If , then . Suppose . Then for some , hence . Then , so that .
Since is primitive on and , we have or . If , we have , so that . If , we have . Thus is a maximal subgroup of .
Suppose that for all , is a maximal subgroup in . Let be a block with . Now by part 1 above. Since is maximal, there are two cases.
If and such that , then since acts transitively there exists such that . Now , a contradiction. Thus .
If , then by Lemma 1 we have .
Thus is primitive on .
Repeat the previous example with each of the following actions.
 acting on the set by
 acting on the set of all nonempty subsets of by .
 For acting on :
 We compute the orbits as follows.
 , , and , so that .
 , , , , and , so that .
 , , , , and , so that .
 , , , , , and , so that .
 , , , , , and , so that .
This exhausts the elements of .
 We fix the labeling
Now under the permutation representation , we have
 If , then so that . In particular, consider . Since , we have .
Each remaining orbit has order 6. Thus, if , , then ; hence .
 For acting on :
 We compute the orbits as follows.
 We have , , and . Thus .
 We have , , and . Thus .
 There is only one remaining element of . Thus .
 We fix the labeling
Under the permutation representation ,
 If , then , so that . In particular, since , we have .
If , we similarly have . In particular, since , we have .
Now , so that .