I have been going through Pinter's A Book of Abstract Algebra recently and one question bugs me more than any other.

When discussing the properties of permutations on a general set $A$, he asks

Let $A$ be a finite set, and $B$ a subset of $A$. Let $G$ be the subset of $S_A$ (the symmetric group on $A$) consisting of all the permutations $f$ on $A$ such that $f(x)\in B$ for all $b\in B$. Prove that G is a subgroup of $S_A$.

I am fine with this, and I prove it this way:

i) if $f,g\in G$, then $(f\circ g)(x)=f(g(x))$, but $g(x)$ takes every $b\in B$ to some element in $B$. Similarly, if $f(x)$ takes in only the output of $g$, it will map all $b\in B$ to some element of $B$. Thus, $G$ is closed under composition of functions.

ii) Clearly, if $f$ takes any $b\in B$ to some element of $B$, then the same must be true for the permutations that "undoes" what $f$ did. Therefore, $f^{-1}$ is also in $G$.

From this, we can conclude $G$ is a subgroup of $S_A$.

The thing I do not understand is how this conclusion changes if $A$ is an infinite set. Pinter says there exists a counterexample to this, but I cannot find one. I.e., if $A$ an infinite set, it is not always true that $G$ is a subgroup of $S_A$.

Also, is my above proof valid; am I missing anything? It does not seem like I am using the assumption that $A$ is a finite set, so something tells me there must be a mistake somewhere.

Thank you in advance for any response.

edit: wording

  • 1
    $\begingroup$ If $B$ is infinite, then $f(B) = \{f(b) : b \in B \}$ could be a proper subset of $B$. In that case, your argument (ii) does not work. $\endgroup$ – Derek Holt Jun 3 '19 at 14:02
  • 1
    $\begingroup$ By the way, the wording in your answer isnot good. You don't mean "... takes every $b \in B$ to another element of $B$", because you also want to allow the possibility $g(b)=b$. The word "another" means "a different" in normal English. $\endgroup$ – Derek Holt Jun 3 '19 at 14:05
  • $\begingroup$ Thank you for pointing out the wording. I agree that it is not as precise as it could be. $\endgroup$ – bluestool Jun 3 '19 at 14:13
  • 1
    $\begingroup$ Why the downvote? The question is clear, the OP shows work and correctly wonders, observing that one of the hypotheses seems unnecessary. $\endgroup$ – Ethan Bolker Jun 3 '19 at 14:19
  • $\begingroup$ You don't need $A$ to be finite, but you need $B$ to be finite. $\endgroup$ – Robert Israel Jun 3 '19 at 15:17

Suppose $A$ is the set of integers and $B$ the set of positive integers. Then the shift function $f$ that maps $n$ to $n+1$ maps $B$ to itself but its inverse doesn't.

Now go back to your proof and see where you should use the finiteness of $A$.

  • $\begingroup$ I suppose the assumption of finiteness would be required in ii), since it does not affect i). In ii), the set $A$ being finite guarantees that $f^{-1}$ will map back to $B$ by the pigeonhole principle? And this would fail if $A$ is infinite, wouldn't it? $\endgroup$ – bluestool Jun 3 '19 at 14:12
  • $\begingroup$ I don't see how the pigeonhole principle shows what you need about the inverse of $f$. Bur you should be able to show that $f$ has finite order, and use that. $\endgroup$ – Ethan Bolker Jun 3 '19 at 14:16

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.