# Counterexample in permutations of $S_A$ with A an infinite set

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

• 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. – Derek Holt Jun 3 '19 at 14:02
• 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. – Derek Holt Jun 3 '19 at 14:05
• Thank you for pointing out the wording. I agree that it is not as precise as it could be. – bluestool Jun 3 '19 at 14:13
• Why the downvote? The question is clear, the OP shows work and correctly wonders, observing that one of the hypotheses seems unnecessary. – Ethan Bolker Jun 3 '19 at 14:19
• You don't need $A$ to be finite, but you need $B$ to be finite. – 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$$.
• 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? – bluestool Jun 3 '19 at 14:12
• 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. – Ethan Bolker Jun 3 '19 at 14:16