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

Question

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

Answer 1

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

Answer 2

Your proof is ok. This is an alternative:

Let $n=|A|$. Then $\sigma^{n!}$ is the identity. But if $\sigma[B]\subsetneq B$ then $B=\sigma^{n!}[B]\subsetneq B$. Contradiction.