# Can the image of a set under a permutation be a proper subset of the set itself?

I'm working on some exercise in Fraleigh's "A First Course in Abstract Algebra" and one of them involves permutations under which the image of a certain set is a subset (proper or improper) of the set itself.

Let $A$ be a set and $B$ a subset of $A$, and let $\sigma \in S_A$. Is it ever possible for such $A,B,\sigma$ to exists such that $\sigma[B]\subset B$?

Is my below argument sound?

Since $\sigma$ is one-to-one, $\sigma[B]$ should have as many elements as $B$. Hence, if $\sigma[B]$ is a subset of $B$, it must be an improper subset, as a proper subset would require that $|\sigma[B]| < |B|$. That is, $\sigma[B] = B$.

• Are you assuming that $A$ is finite? Otherwise, being a proper subset does not mean that $|\sigma[B]|<|B|$. – Hayden Aug 18 '15 at 12:32
• Yes, $A$ is finite. – Yiyuan Lee Aug 18 '15 at 12:34
• What does "$\subset$" mean in that book? In some books, $\subset$ means $\subseteq$ and in others, $\subsetneq$. – ajotatxe Aug 18 '15 at 12:34
• @ajotatxe $A \subset B$ would mean that $A$ is a proper subset of $B$. – Yiyuan Lee Aug 18 '15 at 12:36

Since you're assuming that $A$ is finite, then so is $B,$ so your argument works. Basically, you're applying the Pigeonhole Principle.
However, when dealing with infinite sets, things may not be so straightforward. For example, consider the permutation $\sigma:\Bbb Z\to\Bbb Z$ given by $n\mapsto n+1,$ and note that $\sigma[\Bbb N]$ is a proper subset of $\Bbb N.$ Consequently, for any infinite set $A$ with a countably-infinite subset, there is a permutation $\rho$ of $A$ and some $B\subseteq A$ such that $\rho[B]$ is a proper subset of $B$.
If there is an infinite set with no countable subsets, it turns out that we can still apply a sort of Pigeonhole Principle as in the finite case. Therefore, given a set $A,$ we can see that $A$ has a countably infinite subset if and only if there is some permutation $\sigma:A\to A$ and some $B\subseteq A$ such that $\sigma[B]\subsetneq B.$
Let $n=|A|$. Then $\sigma^{n!}$ is the identity. But if $\sigma[B]\subsetneq B$ then $B=\sigma^{n!}[B]\subsetneq B$. Contradiction.