Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $A$ be the set of subsets of $[n]$ that have even size, and let $B$ be the set of subsets of $[n]$ that have odd size. Establish a bijection from $A$ to $B$. The following bijection is suggested for $n=3$:

$$\matrix{A: & \{1,2\} & \{1,3\} & \{2,3\} & \varnothing\\ B: & \{1,2,3\} & \{1\} & \{2\} & \{3\}}$$

I know that first we have to establish a function that is both surjective and injective so that it is bijective. I don't know where to take a step from here in the right direction. So I need a bit of guidance.

Something suggested is let f be the piecewise function:

$$f(x) = x \setminus \{n\}\text{ if }n \in x\text{ and }f(x) = x\cup\{n\}\text{ if }n \notin x$$

share|improve this question
    
You might pick an $n$ and see how that function works if you apply it to the sets in A. Maybe that will give an idea for the general case. –  Ross Millikan Oct 6 '11 at 2:35
    
Salazar, I edited the function to what the suggestion should have been, whether it was or not: what you originally had does not make sense, since it defines $f(x)$ in a self-contradictory fashion. –  Brian M. Scott Oct 6 '11 at 3:01

4 Answers 4

up vote 3 down vote accepted

The function says to map a subset either to itself minus $\{n\}$ (if the subset contains $n$) or to itself union $\{n\}$ (if the subset does not contain $n$). Clearly a subset cannot both contain $n$ and not contain $n$, so there is no problem deciding which case we are in.

To prove the $f$ is injective, let $A_1$ and $A_2$ be two subsets and consider $f(A_1) = f(A_2)$. Either we have $$ A_1 - \{n\} = f(A_1) = f(A_2) = A_2 - \{n\} $$ or $$ A_1 \cup \{n\} = f(A_1) = f(A_2) = A_2 \cup \{n\}. $$ In either case, we can conclude that $A_1 = A_2$, and so $f$ is injective.

To prove that $f$ is surjective, let $B$ be an element of the range of $f$ (i.e. a subset of odd size). If $B$ contains $n$, then $B - \{n\}$ is a subset of even size that maps to $B$ under $f$. If $B$ does not contain $n$, then $B \cup \{n\}$ is a subset of even size that maps to $B$ under $f$. Since everything in the image has something in the domain that maps to it, $f$ is surjective.

share|improve this answer
    
This is an elementary combinatorial question, and the suggested proof is very much a combinatorial proof. –  Brian M. Scott Oct 6 '11 at 2:55
    
what if $n = 0$? –  Salazar Oct 6 '11 at 3:00
    
@Salazar: For $n=0$ the result is false: the empty set has only one subset, itself, and that set has an even number of elements. –  Brian M. Scott Oct 6 '11 at 3:02
    
That is what I thought @BrianM.Scott . So would it work to say that f: A -> B (the current function), then we define g: B -> A. I was thinking that f(g(x)) is the identity for B, and g(f(x)) for A. So this implies g is the inverse of f, so f is a bijection. –  Salazar Oct 6 '11 at 3:08
    
@Salazar: If you can find $g:B\to A$ such that $f\circ g$ is the identity, you’ve shown that $f$ is a bijection. And there’s a very good candidate for $g$: if you haven’t already spotted it, take a look at the hint in my answer. –  Brian M. Scott Oct 6 '11 at 3:11

The example shown for $n=3$ illustrates the suggested bijection (which I corrected from the version in your post): the two sets in each column differ only by the presence or absence of the number $3$. Note that $x$ and $f(x)$ always differ in size by exactly $1$, so one of them must have even size, and the other must have odd size. This shows that the suggested $f$ really does take even-sized sets to odd-sized sets. Now you have to show that $f:A\to B$ is injective and surjective.

  • To show that $f$ is injective, assume that $x,y\in A$ and $f(x) = f(y)$, and try to show that this forces $x=y$.

  • To show that $f$ is surjective, start with a set $y\in B$ and try to find an $x\in A$ such that $f(x)=y$. This isn’t hard if you think about how $f$ works. (HINT: Consider $f$ as a function from $\wp([n])\to\wp([n])$; what does $f$ do to members of $B$?)

share|improve this answer

For $n$ an odd positive integer, there is a natural procedure. The mapping that takes any subset $E$ of $[n]$ with an even number of elements to its complement $[n]\setminus E$ is a bijection from $A$ to $B$.

Dealing with even positive $n$ is messier. Here is one way. The subsets of $[n]$ can be divided into two types: (i) subsets that do not contain $n$ and (ii) subsets that contain $n$.

(i) If $E$ is a subset of $[n]$ with an even number of elements, and does not contain $n$, map $E$ to $[n-1]\setminus E$. Call this map $\phi$.

(ii) If $E$ is a subset of $n$ with an even number of elements, and contains $n$, map $E$ to $\{n\} \cup \phi^{-1}(E\setminus\{n\})$.

share|improve this answer

Number the members of the set $1,2,3,4,\ldots,n$.

For every subset with an even number of elements, there is a corresponding set with an odd number of elements, that corresponds in this way:

  • If $1$ is a member of the set with an even number of elements, then delete $1$ from the set to get a set with an odd number of elements.
  • If $1$ is not a member of the set with an even number of elements, then add $1$ to the set to get a set with an odd number of elements.

For example, suppose the set is $\{1,2,3,4\}$. Then we have this correspondence between sets with an even number of elements and sets with an odd number of elements: $$ \begin{array}{rcl} \text{even} & & \text{odd} \\ \hline \varnothing & \leftrightarrow & \{1\} \\ \{1,2\} & \leftrightarrow & \{2\} \\ \{1,3\} & \leftrightarrow & \{3\} \\ \{1,4\} & \leftrightarrow & \{4\} \\ \{2,3\} & \leftrightarrow & \{1,2,3\} \\ \{2,4\} & \leftrightarrow & \{1,2,4\} \\ \{3,4\} & \leftrightarrow & \{1,3,4\} \\ \{1,2,3,4\} & \leftrightarrow & \{2,3,4\} \end{array} $$

This won't work with the empty set because we don't have an element to which we can assign the number $1$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.