1
$\begingroup$

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 for your help.

  • 0
    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\}$."2012-12-02

2 Answers 2

0

The result is easily seen to be false as stated. I suspect that the correct result is this:

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

0

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