3
$\begingroup$

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$

  • 0
    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.2011-10-06

4 Answers 4

3

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.

  • 0
    @Salazar I suspect it was implicit in the problem that $n \geq 1$, since otherwise (as Brian pointed out) there are no odd-sized subsets to consider (and moreover the result is false).2011-10-06
3

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

2

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

2

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\})$.