# Cardinality of a subset acted upon by the Alternating Group, $A_n$

Suppose $X \subset \{1,2,3,\ldots,n\}$. Show that the cardinality of $X$ is $0$, $1$ or $n$, if $\forall$$b \in A_n$, $X \cap bX = \emptyset$ or $X = bX$.

It's pretty clear to me how the cardinality can be 0 or 1. But how do I show that if it isn't 0 or 1, then it must be $n$?

-
Thanks, fixed it. –  chubbycantorset Dec 2 '12 at 2:03
This is wrong, if we can pick any $b$. Perhaps you mean, "Show that the cardinality of $X$ is 0,1 or $n$ if for all $b\in A_n$, $X\cap bX\in\{\emptyset,X\}$." –  peoplepower Dec 2 '12 at 2:08

Let $X\subseteq\{1,\dots,n\}$, and suppose that for each $b\in A_n$ either $bX=X$ or $bX\cap X=\varnothing$; then $|X|$ is $0,1$, or $n$.
To prove this, let $X\subseteq\{1,\dots,n\}$ be such that for each $b\in A_n$ either $bX=X$ or $bX\cap X=\varnothing$, and suppose further that $1<|X|<n$. Let $r,s\in X$ with $r\ne s$, let $k\in\{1,\dots,n\}\setminus X$, and let $b$ be the permutation $(rsk)=(rk)(rs)\in A_n$ to get a contradiction.
If $1 < |X| < n$, there are $i,j \in X$, $i \ne j$ and $k \in \{1,\ldots, n\} \setminus X$. Can you give an $b \in A_n$ with $bX \cap X \ne \emptyset$ and $X \ne bX$ by just exchanging $i$, $j$ and $k$?