Results 1 to 2 of 2

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

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    64

    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|$"
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    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$)).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Find a bijection f : R --> ( R - {0})
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Jul 4th 2011, 08:37 PM
  2. Replies: 1
    Last Post: Nov 4th 2009, 09:52 AM
  3. Quick questions on Group Theory - Cosets / Normal Group
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Oct 16th 2009, 08:39 AM
  4. Group Theory - Sylow Theory and simple groups
    Posted in the Advanced Algebra Forum
    Replies: 16
    Last Post: May 16th 2009, 11:10 AM
  5. Group Theory Question, Dihedral Group
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Mar 4th 2008, 10:36 AM

Search Tags


/mathhelpforum @mathhelpforum