Tuesday 8 October 2013

A Simple Bijection between Even and Odd Subsets


Let $E(n)$ denote the set of even subsets (subsets of even size) and $O(n)$ the set of odd subsets (subsets of odd size) of a set $S$ containing $n$ elements.  Assuming $n \geq 1$, we can describe a simple bijection between these two sets as follows-

Let $y$ be any arbitrary element of the set $S$. Then, we simply map each $A \subseteq S$ to the set $A \triangle \{y\}$, the symmetric difference of the subset $A$ and the singleton set $\{y\}$. In other words, if the set $A$ does not contain the element $y$, then we map it to the set $A \cup \{y\}$; otherwise, if $A$ already includes the element $y$, then we map it to the set $A \setminus \{y\}$.

Under this mapping, since each subset gets mapped to a subset whose cardinality is either 1 more or 1 less than its own cardinality, its easy to see that odd subsets get mapped to even subsets while even subsets get mapped to odd subsets. Moreover, since $|E(n)| = |O(n)|$ and the mapping is one-to-one, it has to be a bijection.  

No comments:

Post a Comment