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

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

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\begingroup$ +1: Very nice! And a fine example of an argument that may break down when dealing with infinite sets. $\endgroup$ – Cameron Buie Aug 18 '15 at 12:58

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.