# Thread: Group Theory - Find a bijection F: Xo -> Xe (Xo-odd, Xe-even)

1. ## Group Theory - Find a bijection F: Xo -> Xe (Xo-odd, Xe-even)

Hi, I have the following problem. I have solved the second part, but I don't know how to solve the first one.

Let $\displaystyle X_o$ be the set of all odd cardinality subsets of the set $\displaystyle X$, and let $\displaystyle X_e$ be the set of all even cardinality subsets of the set $\displaystyle X$. Do the following:
- Find a bijection $\displaystyle F:X_o -> X_e$,
- Express $\displaystyle |X_o|$ and $\displaystyle |X_e|$ in terms of the number $\displaystyle |X|$.

So the part I don't know is the first one, but here is what I got for the second one. Is it OK? And do you know a bijection for the first part? Thanks!

"There is a bijection between $\displaystyle X_o$ and $\displaystyle X_e$ because $\displaystyle |X_o|=|X_e|$.

Also, we know that if $\displaystyle |X|=2^n$, we have $\displaystyle |Xe|=2^(n-1)$ and $\displaystyle |X_o|=2^(n-1)$. But we also know that in every set $\displaystyle X$, we only have odd and even subsets, so if $\displaystyle |X_o|=|X_e|$ then we can say

$\displaystyle |X|=|X_o|+|X_e|$, so $\displaystyle |X_o|=(1/2)*|X|$ and $\displaystyle |X_e|=(1/2)*|X|$"

2. Basically, you just need to show that $\displaystyle |X_o| = |X_e|$.

You can, if you wish, note that if |X| is odd then the complement of every even set us a unique odd set, and your done (taking the complement of X with X to be the empty set, and even set). This is just an observation, it isn't needed to prove the result per se.

Now, if |X|=n is then induct on n. n=1 can be checked manually (note that the empty set is take to be even).

Let $\displaystyle Y=X\setminus\{x\}$ where $\displaystyle x \in X$ is some arbitrary element. The result holds for Y. Can you conclude that the result thus holds for X? (The subsets of X are the subsets of Y together with all the subsets of Y with x (as in, if $\displaystyle S \subset Y$ the $\displaystyle S\cup \{x\} \subset X$)).