3
$\begingroup$

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

$\endgroup$
6
  • 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, 2019 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, 2019 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, 2019 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, 2019 at 14:19
  • $\begingroup$ You don't need $A$ to be finite, but you need $B$ to be finite. $\endgroup$
    – Robert Israel
    Jun 3, 2019 at 15:17

1 Answer 1

Reset to default
4
$\begingroup$

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$.

$\endgroup$
2
  • $\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, 2019 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, 2019 at 14:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .